[MÚSICA] En el vÃdeo anterior hemos introducido los fundamentos del esquema de Bag of Words para la clasificación de imágenes. Tal como vimos en Bag of Words para poder representar una imagen, primero lo que vamos a tener que hacer es determinar lo que llamamos el vocabulario de palabras visuales que será lo que se utilizará para después poder calcular el histograma que nos sirve para representar toda la imagen. En este vÃdeo nos vamos a centrar precisamente en este paso, en el paso de construcción de vocabulario. Vamos a ver un método básico que se conoce como K-means que nos va a permitir encontrar grupos de caracterÃsticas similares y poder determinar un representante para cada uno de los grupos que van a ser cada una de nuestras palabras visuales. Como vemos en la figura, el paso de construcción del vocabulario va a ser independiente del esquema global de clasificación. Lo vamos a realizar una única vez como paso previo para entrenar y aplicar el sistema de clasificación. El conjunto de palabras visuales que obtenemos con la construcción del vocabulario es el que se utiliza para representar y clasificar cualquier imagen. Para construir el vocabulario vamos a partir de un conjunto de imágenes especÃficas que van a tener que ser suficientemente representativas del tipo de imágenes que queremos clasificar. En estas imágenes lo primero que vamos a hacer es detectar y describir los puntos de interés, tal como you explicamos la semana pasada. El resultado, va a ser pues un conjunto de puntos que vamos a poder representar en el espacio multidimensional del descriptor. Nuestro objetivo va a ser para poder encontrar las palabras visuales va a ser encontrar grupos de puntos que tengan una descripción similar para asà poder definir cada una de las palabras visuales como un representante de cada uno de estos puntos. Para encontrar esta agrupación, vamos a tener que encontrar la frontera que separa los grupos pero partiendo únicamente del valor de los descriptores, sin tener previamente una etiqueta asociada a cada punto. De hecho, de alguna manera, lo que tenemos que ser capaces es de descubrir la etiqueta de cada punto. Fijémonos que aunque en este caso también queremos encontrar una frontera entre los puntos del espacio, el problema es diferente al que tenemos cuando queremos entrenar un clasificador, you que cuando entrenamos un clasificador para cada muestra en el conjunto de entrenamiento, tenemos previamente asociada una etiqueta y ahora no tenemos etiquetas. Este tipo de problema que es encontrar una separación óptima entre las muestras sin conocer su etiqueta es lo que se conoce como aprendizaje no supervisado, a diferencia de lo que es el aprendizaje supervisado, que es el que realizamos cuando entrenamos un clasificador y sà que conocemos la etiqueta de cada muestra. En concreto, al proceso de agrupar puntos similares se le conoce en inglés como clustering, y uno de los algoritmos más básicos y populares para ello es el algoritmo de K-means, que es precisamente lo que explicaremos en lo que queda de vÃdeo. El algoritmo de K-means va a tomar como entrada un conjunto de muestras representadas con algún descriptor. pero también el número final de grupos o de clusters que queremos obtener. Este número es el parámetro k del algoritmo y vamos a tener que fijarlo de entrada. Como resultado final el algoritmo nos va a devolver un representante para cada uno de los k grupos que queremos determinar. Los diferentes grupos de muestras van a quedar determinados por la distancia de cada muestra al representante del grupo. Cada muestra será asignada al grupo que tenga el representante más cercano. Como veremos a continuación en el vÃdeo, el algoritmo se va a basar en un proceso iterativo en el que a partir de una primera inicialización, cada muestra se va a asignar al representante más cercano, y esta asignación se va a utilizar para recalcular los representantes de cada cluster. De esta forma, el objetivo final del algoritmo consiste en encontrar una agrupación que minimice la distancia de todas las muestras al representante de cada uno de los clusters. Vamos pues a ver los, el funcionamiento concreto del algoritmo del K-means. Como hemos dicho el primer paso del algoritmo consiste en inicializar los representantes de cada cluster. Normalmente y para simplificar, esta inicialización se realiza de forma aleatoria y escogemos k puntos aleatorios entre todo el conjunto de muestras. Si por ejemplo, si queremos 4 clusters, podrÃamos escoger estos 4 puntos de forma aleatoria como representantes de los clusters, que en la notación que utilizaremos los representaremos asà como el conjunto de los representantes de cada uno de los clusters. A partir de esta inicialización el algoritmo va repitiendo alternativamente 2 pasos, el primer paso es lo que llamamos el paso de asignación, en el que para cada muestra se calcula la distancia a todos los representantes y cada muestra queda asignada al cluster que tiene el representante más cercano. Y esto lo obtenemos con esta expresión, donde vemos que en un cluster tenemos todas las muestras cuya distancia al representante de ese cluster es la mÃnima de las distancias de esa muestra a todos los clusters. Con el ejemplo que estamos utilizando, podrÃamos tener esta primera asignación de muestras a cada uno de los clusters. Si nos fijamos seguramente esta no es la agrupación óptima que podrÃamos definir nosotros, ni seguramente es la que cumple con el objetivo que nos hemos marcado de minimizar la distancia de las muestras al representante de cada cluster. Por lo tanto el algoritmo continúa y continúa con un segundo paso que es el que llamamos modificación de representantes de cada cluster, en el que a partir de las primera asignación que se ha hecho, se recalcula el representante de cada cluster y se redefine como la media de todas las muestras que se habÃan asignado a ese cluster. Con este ejemplo podrÃamos obtener estos nuevos representantes o media de las muestras asignadas. Fijémonos en una cosa, al calcular cada representante como la media de las muestras, estos representantes you no tienen por qué ser una de las muestras originales y por eso en la figura lo representamos como un cuadrado y no como un cÃrculo. Este recálculo de los representantes nos va a modificar las fronteras de los clusters y por lo tanto si ahora repetimos la asignación de muestras a los representantes, vamos a obtener un resultado diferente del que habrÃamos obtenido la primera vez. Por lo tanto el algoritmo va a ir repitiendo sucesivamente los pasos de asignación y de modificación y en cada repetición se irá modificando la distribución de las muestras en clusters y asà nos iremos acercando a la solución final. El criterio de finalización del algoritmo va a ser cuando la asignación de muestras a los clusters se estabilice, y por lo tanto you no haya más cambios de una asignación a la siguiente. AsÃ, por ejemplo en una segunda iteración del algoritmo, podrÃamos tener esta nueva asignación de muestras a cada cluster. Si nos fijamos y comparamos con la anterior, veremos que algunas muestras han cambiado de cluster y aunque todavÃa no podemos considerar que sea una solución óptima, los cambios que se han producido you nos van acercando a esta solución óptima. Después de esta nueva asignación, volverÃamos a recalcular los representantes de cada uno de los clusters y obtendrÃamos estos nuevos representantes de aquÃ. Si estos representantes los volvemos a utilizar para volver a asignar las muestras en el paso de asignación, podrÃamos tener esta nueva asignación que vemos aquÃ, que posiblemente you podrÃa ser la asignación óptima que darÃamos nosotros y que cumpla con el criterio de distancia mÃnima. Esta asignación nos permitirÃa recalcular estos representantes que tenemos aquÃ, y si volviésemos a repetir el paso de asignación, verÃamos que you no se produce ningún nuevo cambio, con lo que you podrÃamos dar por finalizado el algoritmo con estos representantes para cada uno de los clusters que a partir de estos representantes nos define, esta, una frontera entre los diferentes grupos de muestras. Esta es la configuración básica del algoritmo, y si nos fijamos podemos ver que el resultado final del algoritmo dependerá en buena medida de tener una correcta inicialización de los representantes de cada cluster, es decir, diferentes inicializaciones nos van a dar al final un resultado también diferente. Como es difÃcil fijar una inicialización óptima, una estrategia común consiste en repetir el algoritmo varias veces, cada vez con una inicialización aleatoria diferente, y al final escoger de todos los resultados que nos ha dado el algoritmo, el resultado óptimo. Entendiendo por resultado óptimo aquél que va a minimizar la suma de distancias de todas las muestras al representante de cada cluster, es decir, sumamos las distancias de todas las muestras al representante de su cluster, sumamos para todos los clusters y la agrupación que de la distancia mÃnima, esa es la óptima. Hasta aquà la descripción del algoritmo del K-means. Vamos a ver cómo se integra este algoritmo del K-means en la construcción del vocabulario para el Bag of Words. En primer lugar, you sabemos que el conjunto de representantes que nos devuelve el algoritmo del K-means es lo que utilizaremos como palabras visuales. En la utilización del algoritmo nos queda por resolver una cuestión que es cómo fijamos el parámetro k del algoritmo que nos determina el número de clusters, y por lo tanto el número de palabras visuales. Desgraciadamente, no existe una manera de fijar de forma óptima y automática este parámetro, por lo que tenemos que pasar al método de validación experimental. Es decir, vamos a tener que probar diferentes valores de k, construir el vocabulario para cada uno de ellos, entrenar todo el sistema de clasificación, evaluarlo con algún conjunto de evaluación y al final seleccionar el valor de k, el número de palabras visuales que nos permita entrenar el clasificador que tenga un mejor rendimiento. Sà que podemos decir que como norma general, los valores óptimos de k suelen ser grandes, es decir están más cerca del rango de millares de palabras visuales que del rango de unas pocas decenas. Con este número elevado de palabras visuales, lo que conseguimos es tener una representación de las imágenes que sea más discriminativa y por lo tanto también más robusta. De todas formas y como you hemos dicho no hay fórmulas mágicas, por lo que tendremos que probar para cada problema y para cada tipo de imagen diferentes valores y al final escoger el mejor. En este vÃdeo hemos abordado el problema de la construcción del vocabulario como un paso previo, que es necesario para poder obtener las palabras visuales, que después nos permiten representar las imágenes en el esquema del bag of words. Hemos visto que la construcción del vocabulario es un ejemplo de un problema de aprendizaje no supervisado y más en concreto de clustering. Y hemos explicado el algoritmo de K-means como un primer algoritmo básico de clustering y que por lo tanto nos permite definir el vocabulario. Más adelante, a lo largo del curso, you veremos otras variantes para la construcción del vocabulario, que pueden permitir obtener un mejor conjunto de palabras visuales.
