Expectation-Maximization algoritmo para reconocimiento de patrones

Autor: Jesús Emeterio Navarro Barrientos

Asesores: Prof. Dr. Raúl Rojas y Dr. Johan Van Horebeek

Fecha: Junio 2001

Objetivo: Este proyecto muestra el algoritmo EM (Expectation-Maximization), su implementacion y algunos ejemplos de su uso para el reconócimiento y la caracterización del dígito cero en imágenes.

Descarga aqui el reporte tecnico de este proyecto.

Algoritmo EM

El objetivo de este algoritmo es tomar una serie de datos de cualquier dimensión y asignarle una serie de funciones gaussianas de probabilidad a los clusters que encuentra en estos datos. Para esto el algoritmo obtiene las distancias que hay entre los datos y las medias de las Gaussianas, de esta manera

obtiene un peso para cada dato, este peso varia de acuerdo a la probabilidad encontrada para cada dato de que pertenezca a un determinado kernel o gaussiana, de esta manera en cada iteracion del algoritmo se van modificando las medias y las matrices de covarianzas de los kerneles gaussianos a manera que se van acercando a posibles clusters encontrados en los datos.

El algoritmo EM consta básicamente de los siguientes tres pasos:

• 1. Paso de iniciación

  2. Paso E

  3. Paso M

Los pasos E y M se repiten en un ciclo que termina una vez que converge el algoritmo, es decir una vez que ya no hay cambios significativos en las Gaussianas que se calculan.

Paso de iniciación

Este paso consiste en tomar los datos de entrada e introducirlos en una matriz de datos característicos X de dimensiones m × n, donde m es la cantidad de muestras o datos, y n es la dimension de cada dato.

El siguiente paso consiste en asignar un numero aleatorio a las medias de las distribuciones Gaussianas, esto se hace tomando el rango de valores posibles de los datos y se le asigna a cada kernel gaussiano una media aleatoria. Las medias para cada Gaussiana y para cada dimensi´on se almacenan en una matriz M de dimensiones k × n, donde k es el numero de gaussianas (kerneles).

Por ultimo se asignan valores iniciales aleatorios al vector de matrices de covarianza que le corresponde a cada Gaussiana utilizada como función kernel. el vector es de dimensión k y cada matriz es de dimensión n × n.

Paso E

En este paso se realiza el calculo de las distancias W de los datos con respecto a las medias de las Gaussianas, para esto se utiliza una matriz de pesos W de dimensiones k × m, estos Ws son los pesos que tomara el algoritmo para cada dato en el espacio de muestras.

Paso M

En este paso se realiza el calculo de las nuevas medias y las nuevas matrices de covarianza.

Resultados

A continuación se muestran los resultados obtenidos en el programa realizado en el lenguaje de programación C++ Builder. En este programa es solo necesario especificar el directorio de trabajo donde residen las imágenes de las cuales el programa obtendrá una serie de características. La siguiente figura muestra un ejemplo para un conjunto de prueba en 2 dimensiones, para 50 muestras, 30 localizadas en un cluster cercano al cero, las otras 20, en un cluster superior, utilizando dos Gaussianas se obtuvieron los siguientes resultados. Como se aprecia, las medias para los dos clusters fueron encontradas correctamente y no hubo colapso de alguna Gaussiana.

A continuación se muestran tres ejemplos para la serie de imágenes correspondientes al cero, con diferente numero de Gaussianas, a las cuales se les obtiene su área y perímetro como características, teniendo así un numero de características igual a dos, i.e. características de dimensión 2-D, las cuales facilitan mostrar gráficamente. Finalmente se muestra un ejemplo para una serie de características de orden 32 para la distribución Blackjump.

Primer ejemplo

Ejecución del programa con 106 imagenes de ceros, utilizando dos Gaussianas, no se aprecian clusters, sin embargo las medias se acomodan a los datos, y encuentran

posibles dos medias, que a simple vista pudiera ser mejor un solo cluster global, pero se puede pensar que entre mas Gaussianas abarquen el espacio sea mejor la clasificación, aunque el tiempo de realización y complejidad del algoritmo aumenten.

Segundo ejemplo

Para el mismo conjunto de imagenes ahora utilizando tres gaussianas, se puede apreciar que las medias ahora se sitúan entre los datos, con la característica

especial que una de ellas se situa conforme avanzan las iteraciones en el centro de los datos, la solución de la derecha se obtuvo en la iteracion 50, donde ya no se registraron cambios notorios en las medias ni las covarianzas.

Tercer Ejemplo

Mismo conjunto de imágenes, ahora para cuatro Gaussianas, se puede inferir de estos ejemplos, que conforme se aumente el numero de Gaussianas estas se iran situando entre los datos, obteniendo clusters mas pequenos y que aumentan la complejidad del algoritmo, sin una mejora significativa aparente en la obtencion de clusters, esto debido al espacio de muestra.

Conclusiones

En este proyecto, se implemento el algoritmo EM encontrando varios detalles durante la implementacion, asi como complejidad en el manejo de las matrices. Obteniendo al final un programa que encontraba eficazmente las medias ideales para los clusters del espacio muestral. Se tuvo problemas con la matriz de covarianzas, primero su correcta definición para cada muestra y para cada kernel Gaussiano, ademas de que al correr los progrmas frecuentemente para dimensiones grandes de los datos se encontraban errores de divisiones entre cero, o operaciones de punto flotante no validas, ya que algunos valores de la matriz de covarianza se hacian cero con forme se iteraba el algoritmo, lo que ocasionaba serios problemas después al realizar las operación con esta matriz.

Se comprobó que el algoritmo es eficiente con un ejemplo con datos obtenidos de la caracterización de las imagenes correspondientes a Ceros de una base de datos de imágenes propia creada en el CIMAT, se encontro que con dos Gaussianas se obtenían los clusters del espacio de dos dimensiones. Para un espacio de 8 dimensiones utilizando las características de la distribución Blackjump, se pudo apreciar que varias Gaussianas tendian a colapsarse, teniendo prácticamente 2 Gaussianas con valores de medias diferentes. Finalmente, se puede concluir que el algoritmo EM implementado para obtener un clasificador para dígitos, supera en rapidez y eficiencia a otros algoritmos, por ejemplo los basados en redes neuronales.