PDF de programación - Notas de Reconocimiento de Patrones

Univ. Michoacana de San Nicolas de Hgo.

Facultad de Ingeniería Eléctrica
División de estudios de Postgrado

Maestría y Doctorado en Ciencias en Ing

Eléctrica

Opción Sistemas Computacionales

Notas de Reconocimiento de Patrones

José Antonio Camarena Ibarrola

Marzo de 2009

2

Índice general

1. Introducción

7
1.1. Esquema de un Sistema de Reconocimiento de Patrones . . . .
8
1.1.1. Adquisición de Datos . . . . . . . . . . . . . . . . . . .
8
1.1.2. Extracción de Características
. . . . . . . . . . . . . . 10
1.1.3. Elección del Modelo
. . . . . . . . . . . . . . . . . . . 11
1.1.4. Entrenamiento . . . . . . . . . . . . . . . . . . . . . . 11
1.1.5. Evaluación del Modelo . . . . . . . . . . . . . . . . . . 12
1.2. Aprendizaje Supervisado . . . . . . . . . . . . . . . . . . . . . 13
1.3. Aprendizaje no supervisado . . . . . . . . . . . . . . . . . . . 13
1.3.1. Agrupamiento de datos . . . . . . . . . . . . . . . . . . 14
1.4. Reforzamiento del Aprendizaje . . . . . . . . . . . . . . . . . . 14
. . . . . . . . . . . . . . . . . 15
1.5. Clasificador Lineal Vs No-lineal

2. El clasificador Bayesiano

17

2.1. Clasificador Bayesiano basado la minimización del régimen de

errores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2. Criterio Minimax . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3. Funciones Discriminantes y Superficies de Decisión . . . . . . 24
2.3.1. Clasificador de mas de 2 clases . . . . . . . . . . . . . . 24
2.3.2. El Dicotomizador . . . . . . . . . . . . . . . . . . . . . 24
2.4. Funciones discriminantes para la densidad Normal . . . . . . . 26
2.4.1. Caso Matriz de Co-varianzas diagonal y única . . . . . 27
2.4.2. Caso Matriz de Co-variancias única . . . . . . . . . . . 34
2.4.3. Caso Matriz de Co-variancias arbitraria . . . . . . . . . 39
2.5. Acotamiento del error para densidades normales . . . . . . . . 45
2.5.1. Cota de Chernoff . . . . . . . . . . . . . . . . . . . . . 47
2.5.2. Cota de Bhattacharyya . . . . . . . . . . . . . . . . . . 47
2.6. Curvas ROC . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

3

4

ÍNDICE GENERAL

2.7. Clasificador Bayesiano para características discretas . . . . . . 51
2.7.1. Características binarias e independientes . . . . . . . . 52
2.7.2. Ejemplo . . . . . . . . . . . . . . . . . . . . . . . . . . 54
2.8. Clasificador Bayesiano para características ruidosas y/o ausentes 55
2.8.1. Ejemplo . . . . . . . . . . . . . . . . . . . . . . . . . . 56

3. Estimación de parámetros

59
3.1.
Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.2. Estimador de Máxima Verosimilitud . . . . . . . . . . . . . . 59

3.2.1. Ejemplo de estimación de vector de medias asu-miendo

distribución Normal . . . . . . . . . . . . . . . . . . . . 61
3.2.2. Ejemplo de aplicación a distribución uniforme . . . . . 63
3.3. Estimador Bayesiano . . . . . . . . . . . . . . . . . . . . . . . 64
3.3.1. Aprendizaje Bayesiano . . . . . . . . . . . . . . . . . . 64
3.3.2. Caso Gaussiano univariado y multivariado . . . . . . . 65

3.4. Algoritmo EM (Maximización del valor esperado de la log-

verosimilitud . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.4.1. Estimación de Parámetros con datos faltantes . . . . . 68
3.4.2. Aplicación del Algoritmo EM al entrenamiento de Mod-

elos Ocultos de Markov . . . . . . . . . . . . . . . . . . 69

3.4.3. Aplicación a Estimación de Parámetros en mezclas de

3.5. Análisis de Componentes principales
3.6. Técnicas no paramétricas de estimación de parámetros

gaussianas . . . . . . . . . . . . . . . . . . . . . . . . . 72
. . . . . . . . . . . . . . 72
. . . . 75
3.6.1. Método de Ventanas de Parzen . . . . . . . . . . . . . 77
3.6.2. Método de los K-Vecinos más cercanos . . . . . . . . . 80

4. Redes Neuronales

81
4.1. El Perceptrón generalizado . . . . . . . . . . . . . . . . . . . . 83
4.1.1. La regla delta . . . . . . . . . . . . . . . . . . . . . . . 84
4.2. Topología de redes neuronales . . . . . . . . . . . . . . . . . . 85
4.3. Funciones de activación . . . . . . . . . . . . . . . . . . . . . . 87
4.3.1. Función sigmoidea . . . . . . . . . . . . . . . . . . . . 88
4.4. Aprendizaje . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.4.1. Propagación hacia atrás
. . . . . . . . . . . . . . . . . 89
4.4.2. Red con una capa oculta . . . . . . . . . . . . . . . . . 91
4.5. Memorias Asociativas . . . . . . . . . . . . . . . . . . . . . . . 92

ÍNDICE GENERAL

5

5. Métodos estocásticos

95
5.1. Recocido simulado . . . . . . . . . . . . . . . . . . . . . . . . 95
5.1.1. El Algoritmo de Recocido Simulado . . . . . . . . . . . 97
5.1.2. El recocido simulado como una variante del “HillClimb-

ing” . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
5.2. Redes de Boltzman . . . . . . . . . . . . . . . . . . . . . . . . 101
5.2.1. Aprendizaje en las máquinas de Boltzmann . . . . . . 103
5.2.2. Costos computacionales de la Máquina de Boltzmann . 104
5.3. Algoritmos genéticos . . . . . . . . . . . . . . . . . . . . . . . 104
5.4. Programación genética . . . . . . . . . . . . . . . . . . . . . . 107
5.4.1. El método grow . . . . . . . . . . . . . . . . . . . . . . 109
5.4.2. El método full . . . . . . . . . . . . . . . . . . . . . . . 109
5.4.3. Operadores Genéticos . . . . . . . . . . . . . . . . . . . 109
5.4.4. Función de Calidad . . . . . . . . . . . . . . . . . . . . 110
5.4.5. Selección . . . . . . . . . . . . . . . . . . . . . . . . . . 110

6. Técnicas de Agrupamiento

113
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
6.1. K-medias
6.2. K-medias dinámico . . . . . . . . . . . . . . . . . . . . . . . . 115
. . . . . . . . . . . . . . . . . . . . . 116
6.3. K-medias difuso (KMD)
6.4. Vecinos mas cercanos mutuos
. . . . . . . . . . . . . . . . . . 117
6.5. Agrupamiento Jerarquico . . . . . . . . . . . . . . . . . . . . . 118
6.6. Análisis de componentes principales . . . . . . . . . . . . . . . 122
6.6.1. Método basado en las covarianzas . . . . . . . . . . . . 123
6.6.2. Método basado en correlaciones . . . . . . . . . . . . . 123
6.6.3. Limitaciones . . . . . . . . . . . . . . . . . . . . . . . . 124
6.6.4. Ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . 124
6.7. Redes auto-organizantes de Kohonen . . . . . . . . . . . . . . 125

6

ÍNDICE GENERAL

Capítulo 1

Introducción

Estas notas fueron desarrolladas como apoyo a los estudiantes que cur-
san la materia de Reconocimiento de Patrones en la Maestría y el Doctor-
ado en Ingeniería Eléctrica, opción Sistemas Computacionales. El programa
de esta materia incluye temas de diversos libros los cuales son difíciles de
conseguir y de algunos artículos científicos, las presentes notas son un com-
pendio que se apega a los temas que indica el programa. Los ejemplos que
se incluyen han sido desarrollados a mucho mayor detalle que lo que usual-
mente aparece en la bibliografía. Finalmente todavía ocurre sobre todo en
los estudiantes de maestría (Quizás de Doctorado no) que se les dificulta la
comprensión de material escrito en Inglés, estas notas son un apoyo tam-
bién para aquellos alumnos con dificultades de lectura del inglés técnico del
área de reconocimiento de patrones. Estas notas se encuentran a disposi-
ción de los estudiantes o de cualquier interesado en los temas de este curso
en http://lc.fie.umich.mx/∼camarena/NotasReconPat.pdf. Se agradecen las
observaciones y comentarios, favor de dirigirlos a [email protected]

Atentamente: Dr. José Antonio Camarena Ibarrola. Autor

7

8

CAPÍTULO 1. INTRODUCCI ÓN

Sistemas de Reconocimiento de voz (ASR por Automatic Speech Recog-
nition); Reconocimiento de huellas dactilares (AFIS por Automatic Finger-
print Identification System); Reconocimiento de rostros, de firmas, de retina
y muchos otros pertenecen a un área de la Inteligencia Artificial denominada
Reconocimiento de Patrones. Un sistema basado en reconocimiento de pa-
trones tiene el objetivo de identificar la clase a la que pertenece un patron
que se le presenta, dicho de otra manera tiene la responsabilidad de clasificar
objetos.

1.1. Esquema de un Sistema de Reconocimien-

to de Patrones

Para cumplir su misión, un sistema de reconocimiento debe primero ex-
traer características a partir la señal cualquiera que sea su naturaleza (señal
de audio, imagen, etc.), dichas características deben ser robustas, es decir
deberían permanecer en la señal aunque esta sufra deformaciones por ruido
u otras formas de degradación. Para extraer dichas características se utilizan
una variedad de técnicas de procesamiento digital de señales que en muchas
ocasiones hacen uso de alguna transformación. En la Figura 1.1 se muestra
el proceso de reconocimiento de un patrón a partir de una señal, el pre-
procesamiento de la señal normalmente incluye la segmentación, es decir, la
separación del área de interés del resto de la señal, por ejemplo, un sistema de
reconocimiento de rostros debe ubicar el área donde se encuentra realmente
el rostro en la imagen capturada para separarla del resto (Ej, del fondo de
la imagen), el preprocesamiento implica casi siempre una normalización, por
ejemplo, un sistema de reconocimiento de firmas debe ser independiente del
color de tinta con el que un individuo ha firmado, por eso el preprocesamien-
to convertiría en esta etapa la imagen a color a una imagen en tonos de gris.
El clasificador en sí compara las características extraídas de la señal con las
características de los patrones conocidos a los que previamente se les extrajo
dichas características.

1.1.1. Adquisición de Datos

Para poder aplicar las técnicas de procesamiento de señales que habrán
de extraer características que permitan realizar la labor de un reconocedor
de patrones se debe contar con un subsistema de adquisición de datos, el cual

1.1. ESQUEMA DE UN SISTEMA DE RECONOCIMIENTO DE PATRONES9

Figura 1.1