Bases estadísticas
del reconocimiento de patrones
César Martínez
cmartinez _AT_ fich.unl.edu.ar
Inteligencia Computacional
FICH-UNL
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Percepción humana
Tarea muuuuy simple: ¿Cuántas llaves hay?
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 2 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Percepción humana
Tarea simple: ¿Cuántas llaves hay?
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 3 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Percepción humana
Tarea no tan simple: ¿Cuántas llaves hay?
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 4 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Percepción humana
Tarea compleja: ¿Cuántas llaves hay?
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 5 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Aprendizaje maquinal
Problema: ¿Cómo enseñarle a una máquina a que emule las tareashumanas de detección, percepción, identificación, reconocimiento, etc.?
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 6 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Aprendizaje maquinal
Objetivo: Programar máquinas para
aprender a realizar una tarea,
mejorando su desempeño
basado en la experiencia.
Restricciones adicionales:
mínima intervención humana posible,
con reducido conjunto de ejemplos,
etc...
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 7 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Aprendizaje maquinal
Objetivo: Programar máquinas para
aprender a realizar una tarea,
mejorando su desempeño
basado en la experiencia.
Restricciones adicionales:
mínima intervención humana posible,
con reducido conjunto de ejemplos,
etc...
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 7 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Conceptos básicos de
Aprendizaje Maquinal
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 8 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Contexto de la disciplina
Podemos considerar dos ramas de la Inteligencia Artificial (IA):
IA clásica:
Modelado del proceso de razonamiento humano mediante técnicas dela Lógica.Aprendizaje deductivo.
Reconocimiento de Formas:
Modelado del proceso de percepción humano mediante técnicas de laTeoría de la Decisión Estadística y de la Teoría de los Lenguajes
Formales.Aprendizaje inductivo.
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 9 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Contexto de la disciplina
Podemos considerar dos ramas de la Inteligencia Artificial (IA):
IA clásica:
Modelado del proceso de razonamiento humano mediante técnicas dela Lógica.Aprendizaje deductivo.
Reconocimiento de Formas:
Modelado del proceso de percepción humano mediante técnicas de laTeoría de la Decisión Estadística y de la Teoría de los Lenguajes
Formales.Aprendizaje inductivo.
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 9 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Contexto de la disciplina
Vista como una disciplina de la IA...
Adquisición y representación del conocimiento: conformación yalmacenamiento de conjuntos de patrones o prototipos.
Aprendizaje: algoritmos de aprendizaje inductivo a partir de unconjunto de entrenamiento.
Clasificación: etiquetado de patrones nuevos utilizando el conjunto declases disponible.
Evaluación: mecanismos para evaluar la bondad, confianza o error delsistema.
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 10 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Definiciones
Patrón:
Objeto de interés que es identificable del resto.Posiblemente difusos, no bien definidos, no visibles o tangibles.Ej: una huella digital, la voz de una persona, una cara, etc.
Reconocimiento de patrones (RP):Estudio de los procesos de percepción y razonamiento humanos:
capacidad de distinguir y aislar los patrones,
reunirlos en grupos,
asignarles un nombre identificatorio a cada grupo.
Objetivo del RP: crear sistemas informáticos que imiten elcomportamiento descripto.
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 11 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Paradigma de trabajo conceptual
(a) Adquisición: transducción del mundo real a la representación digital.
(b) Procesamiento digital: acondicionamiento y representación alternativa.
(c) Clasificación: decisión sobre la clase.
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 12 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Paradigma de trabajo funcional
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 13 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Aproximaciones
Aproximación geométrica o estadística:
Basada en la Teoría Estadística de la Decisión.Representación de patrones como vectores numéricos.Representación de clases mediante patrones prototipo.Tipos de clasificadores: gaussianos, basados en distancia, etc.
Aproximación estructural o sintáctica:
Basada en la Teoría de Lenguajes Formales.Representación de patrones como cadenas de símbolos.Utilización de reglas sintácticas para especificar los patrones válidos deuna clase.Tipos de clasificadores: autómatas, gramáticas, HMM, etc.
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 14 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Aproximaciones
Aproximación geométrica o estadística:
Basada en la Teoría Estadística de la Decisión.Representación de patrones como vectores numéricos.Representación de clases mediante patrones prototipo.Tipos de clasificadores: gaussianos, basados en distancia, etc.
Aproximación estructural o sintáctica:
Basada en la Teoría de Lenguajes Formales.Representación de patrones como cadenas de símbolos.Utilización de reglas sintácticas para especificar los patrones válidos deuna clase.Tipos de clasificadores: autómatas, gramáticas, HMM, etc.
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 14 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Ejemplo de aproximación geométrica
OCR de dígitos manuscritos:
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 15 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Ejemplo de aproximación geométrica
OCR de dígitos manuscritos:
Característica simple: cálculo de brillo de partes superior e inferior
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 16 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Ejemplo de aproximación geométrica
Clasificador geométrico con funciones lineales:
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 17 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Ejemplo de aproximación sintáctica
Descripción de dígitos mediante cadenas de contorno:
1
2 0
3
000...03332323...22111
1
2
0
3
4
5
6
7
000...066655...1122244...222
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 18 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Ejemplo de aproximación sintáctica
Clasificador sintáctico basado en autómatas:
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 19 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Conceptos de
clasificación estadística
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 20 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Definiciones
Adquisición y preproceso de datos: vector numérico que representa alpatrón natural.Formalmente, un patrón es una variable aleatoria n-dimensionaly = [y1 y2 . . . yn]
T , con yi ∈ R para i = 1, 2, . . . , n, que representaun punto en el espacio de patrones P ∈ R
n.
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 21 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Definiciones
Adquisición y preproceso de datos: vector numérico que representa alpatrón natural.Formalmente, un patrón es una variable aleatoria n-dimensionaly = [y1 y2 . . . yn]
T , con yi ∈ R para i = 1, 2, . . . , n, que representaun punto en el espacio de patrones P ∈ R
n.
Extracción de características: información relevante para laclasificación.Formalmente, dado un conjunto de patrones n-dimensionales y setrata de obtener un nuevo conjunto de representacionesx = [x1 x2 . . . xd]
T , donde d ≤ n.
Cambio en el espacio de representación: transformaciones lineales quemaximizan la varianza (d = n).Reducción de dimensionalidad de los datos (d < n).
Espacio de características: E ∈ Rd.
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 21 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Definiciones
Extracción de características: propiedades deseables
Precisión: representaciones diferentes para objetos diferentes.Unicidad o determinismo: representación única para cada objeto.Continuidad en el espacio: inmunidad al ruido y capacidad degeneralización.
Clases informacionales: salidas del sistema
Número de clases: cConjunto de (etiquetas de) clases: Ω = ω1, ω2, . . . , ωcConjunto extendido: Ω∗ = ω1, ω2, . . . , ωc, ω0, donde ω0
es la clase de rechazo.
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 22 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Definiciones
Extracción de características: propiedades deseables
Precisión: representaciones diferentes para objetos diferentes.Unicidad o determinismo: representación única para cada objeto.Continuidad en el espacio: inmunidad al ruido y capacidad degeneralización.
Clases informacionales: salidas del sistema
Número de clases: cConjunto de (etiquetas de) clases: Ω = ω1, ω2, . . . , ωcConjunto extendido: Ω∗ = ω1, ω2, . . . , ωc, ω0, donde ω0
es la clase de rechazo.
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 22 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Definiciones
Clasificador estadístico: máquina formada por c (funciones)discriminantes
gi : E → R, 1 ≤ i ≤ c
tal que dado un patrón x ∈ E,
x se asigna a la clase ωi si gi(x) > gj(x) ∀j 6= i
.
.
. .
.
.
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 23 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Regiones y fronteras de decisión
Regiones de decisión: un clasificador divide el espacio en c regiones de
decisión R1, R2, . . . , Rc, tal que
Ri = x ∈ E : gi(x) > gj(x) ∀j 6= i
Fronteras de decisión: superficies del espacio que separan regiones dedecisión contiguas.Hipersuperficies definidas por: gi(x)− gj(x) = 0, i 6= j, 1 ≤ i, j ≤ c
x x
x
x x
x
x
x x
x x
x x
x x
x x
x
R 1
R 2
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 24 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Clasificadores estadísticos básicos
Las FD son combinaciones lineales o cuadráticas de las componentes delvector de características.
Clasificador lineal:
g(x) =d∑
i=1
wixi + w0 = wtx+ w0
Parámetros: d+ 1. Fronteras: hiperplanos.
Clasificador cuadrático:
g(x) =d∑
i=1
d∑j=1
wijxixj +d∑
i=1
wixi + w0 = xtWx+w
tx+ w0
Parámetros: 12d(d+ 1) + d+ 1. Fronteras: hipercuádricas.
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 25 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Ejemplo: OCR de dígitos manuscritos
Unidimensional: brillo global.
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 26 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Ejemplo: OCR de dígitos manuscritos
Bidimensional: brillo de mitad superior (x1) e inferior (x2).
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 27 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Definiciones de teoría de la decisión
Probabilidad a priori P (ωi) de una clase ωi: probabilidad de que unamuestra arbitraria pertenezca a ωi.
“Probabilidad de observar la etiqueta c sin saber qué muestra es“
Puede verse como la proporción de muestras de ωi respecto al total(conocimiento que se tiene antes de hacer los experimentos).
Condiciones:
- 0 ≤ P (ωi) ≤ 1, para i = 1, . . . , c.-∑c
i=1P (ωi) = 1.
Clasificador trivial de dos clases basado en probabilidades a priori:
Decidir por ω1 si P (ω1) > P (ω2)Decidir por ω2 si P (ω1) < P (ω2)
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 28 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Definiciones de teoría de la decisión
Densidad condicional P (x|ωi) de una clase ωi: función de densidad deprobabilidad que caracteriza la distribución estadística de las muestrasde ωi.
“Probabilidad de observar la muestra x sabiendo que la etiqueta es c”
El vector de características x se considera una variable aleatoriad-dimensional de función de densidad P (x|ωi) cuando las muestraspertenecen a ωi.
Condiciones:
- P (x|ωi) ≥ 0, para i = 1, . . . , c.-∫EP (x|ωi) dx = 1.
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 29 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Definiciones de teoría de la decisión
La probabilidad conjunta P (x, ωi) muestra-clase se define como
P (x, ωi) = P (ωi)P (x|ωi)
“Probabilidad de observar la muestra x con la etiqueta c”
La densidad incondicional P (x) de las muestras se define como
P (x) =c∑
j=1
P (x, ωj) =c∑
j=1
P (x|ωj)P (ωj)
“Probabilidad de observar la muestra x sin saber cuál es su etiqueta“
La densidad incondicional caracteriza la distribución estadística de lasmuestras con independencia de las clases a las que pertenecen.
Se cumple que: P (x) ≥ 0, y∫EP (x) dx = 1.
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 30 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Definiciones de teoría de la decisión
La probabilidad conjunta P (x, ωi) muestra-clase se define como
P (x, ωi) = P (ωi)P (x|ωi)
“Probabilidad de observar la muestra x con la etiqueta c”
La densidad incondicional P (x) de las muestras se define como
P (x) =c∑
j=1
P (x, ωj) =c∑
j=1
P (x|ωj)P (ωj)
“Probabilidad de observar la muestra x sin saber cuál es su etiqueta“
La densidad incondicional caracteriza la distribución estadística de lasmuestras con independencia de las clases a las que pertenecen.
Se cumple que: P (x) ≥ 0, y∫EP (x) dx = 1.
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 30 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Definiciones de teoría de la decisión
Significado de: P (ω = 0) = 0,5; P (x = 45|ω = 0) = 0,033;
P (x = 45, ω = 0) = 0,016; P (x = 45) = 0,054.
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 31 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Definiciones de teoría de la decisión
Supongamos que tenemos conocidas P (ωi), P (x|ωi) y una medida de x.¿Cómo influye este conocimiento sobre la decisión del clasificador?
Probabilidad a posteriori P (ωi|x) de una clase ωi: probabilidad deque una muestra particular x pertenezca a ωi.
”Probabilidad de observar la etiqueta c sabiendo que la muestra es x“
Se calcula mediante la regla de Bayes:
P (ωi|x) =P (x|ωi)P (ωi)
P (x)=
P (x|ωi)P (ωi)∑cj=1 P (x|ωj)P (ωj)
Se cumple que: 0 ≤ P (ωi|x) ≤ 1, y∑c
i=1 P (ωi|x) = 1.
Puede verse como una actualización de P (ωi) después de observar x.
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 32 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Definiciones de teoría de la decisión
Idea para un clasificador...
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 33 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Clasificador de Bayes
Regla de clasificación de Bayes: asignar a x la clase con mayorprobabilidad a posteriori.
ω = argmaxωi:1≤i≤c P (ωi|x)
Clasificador de Bayes: utiliza las probabilidades a posteriori comofunciones discriminantes. Es de mínimo error basado en FDmonótonas crecientes f(·).
gi(x) = P (ωi|x) =P (x|ωi)P (ωi)
P (x)
≡ P (x|ωi)P (ωi)
≡ logP (x|ωi) + log P (ωi)
Equivalencia entre clasificadores:
(g1, . . . , gc) ≡ (f(g1), . . . , f(gc)) ≡ (g′1, . . . , g′c) si Rc = R′
c ∀c.
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 34 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Clasificador de Bayes
Error de Bayes a posteriori: probabilidad de error puntual dado por
P (error|x) = 1− max1≤i≤c
P (ωi|x)
Probabilidad media de error del clasificador:
P (error) =
∫E
P (error|x)P (x)dx
Problemas con el cálculo analítico del error:
P (ωi) y P (x|ωi) desconocidas.Regiones de integración complejas.
Solución: estimación del error.
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 35 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Clasificador de Bayes
Error de Bayes a posteriori: probabilidad de error puntual dado por
P (error|x) = 1− max1≤i≤c
P (ωi|x)
Probabilidad media de error del clasificador:
P (error) =
∫E
P (error|x)P (x)dx
Problemas con el cálculo analítico del error:
P (ωi) y P (x|ωi) desconocidas.Regiones de integración complejas.
Solución: estimación del error.
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 35 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Aplicaciones del RP
OCR manuscrito:
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 36 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Aplicaciones del RP
Reconocimiento de señales de tráfico:
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 37 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Aplicaciones del RP
Reconicimiento facial, expresiones y emociones:
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 38 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Aplicaciones del RP
Detección de malezas en aplicaciones agrícolas:
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 39 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Aplicaciones del RP
Reconocimiento de sonidos masticatorios en rumiantes:
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 40 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Aplicaciones del RP
Reconocimiento de sonidos masticatorios en rumiantes:
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 41 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Aplicaciones del RP
Reconocimiento de sonidos masticatorios en rumiantes:
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 42 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Aplicaciones del RP
Reconocimiento de Imágenes
OCR - Análisis de documentos - Rec. de firmas - Identif. de patentes -Detección de defectos en piezas industriales (control de calidad) - Rec.de gestos faciales
Reconocimiento de Habla y Lenguaje
Rec. de palabras aisladas y discurso continuo - Identif. del locutor -Traducción automática - Comprensión
Aplicaciones Biomédicas
Segmentación de tejido en imágenes médicas - Bioidentificación(huellas dactilares, palma, iris, otros)
Economía
Minería de datos - Detección de patrones de fraude
Aplicaciones en astronomía, agricultura, protección civil, etc.
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 43 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Fin
Bibliografía:
- Duda R., Hart P, Stork D., Pattern Classification, Second Edition.Wiley-Interscience, 2000. Capítulos 1, 2.1 a 2.6, 3.1 a 3.2.
- Lista de la cátedra
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 44 / 44