Click here to load reader

Bases estad sticas del reconocimiento de patrones

  • View
    0

  • Download
    0

Embed Size (px)

Text of Bases estad sticas del reconocimiento de patrones

Bases estadísticas del reconocimiento de patronesPercepción humana
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
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
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
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 tareas humanas 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
mejorando su desempeño
etc...
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Aprendizaje maquinal
mejorando su desempeño
etc...
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Conceptos básicos de
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Contexto de la disciplina
IA clásica:
Modelado del proceso de razonamiento humano mediante técnicas de la Lógica. Aprendizaje deductivo.
Reconocimiento de Formas:
Modelado del proceso de percepción humano mediante técnicas de la Teoría de la Decisión Estadística y de la Teoría de los Lenguajes
Formales. Aprendizaje inductivo.
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Contexto de la disciplina
IA clásica:
Modelado del proceso de razonamiento humano mediante técnicas de la Lógica. Aprendizaje deductivo.
Reconocimiento de Formas:
Modelado del proceso de percepción humano mediante técnicas de la Teoría de la Decisión Estadística y de la Teoría de los Lenguajes
Formales. Aprendizaje inductivo.
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Contexto de la disciplina
Adquisición y representación del conocimiento: conformación y almacenamiento de conjuntos de patrones o prototipos.
Aprendizaje: algoritmos de aprendizaje inductivo a partir de un conjunto de entrenamiento.
Clasificación: etiquetado de patrones nuevos utilizando el conjunto de clases disponible.
Evaluación: mecanismos para evaluar la bondad, confianza o error del sistema.
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,
Objetivo del RP: crear sistemas informáticos que imiten el comportamiento 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
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 de una 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 de una 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:
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
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
1
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Ejemplo de aproximación sintáctica
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
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Definiciones
Adquisición y preproceso de datos: vector numérico que representa al patrón natural. Formalmente, un patrón es una variable aleatoria n-dimensional y = [y1 y2 . . . yn]
T , con yi ∈ R para i = 1, 2, . . . , n, que representa un punto en el espacio de patrones P ∈ R
n.
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Definiciones
Adquisición y preproceso de datos: vector numérico que representa al patrón natural. Formalmente, un patrón es una variable aleatoria n-dimensional y = [y1 y2 . . . yn]
T , con yi ∈ R para i = 1, 2, . . . , n, que representa un punto en el espacio de patrones P ∈ R
n.
Extracción de características: información relevante para la clasificación. Formalmente, dado un conjunto de patrones n-dimensionales y se trata de obtener un nuevo conjunto de representaciones x = [x1 x2 . . . xd]
T , donde d ≤ n.
Cambio en el espacio de representación: transformaciones lineales que maximizan la varianza (d = n). Reducción de dimensionalidad de los datos (d < n).
Espacio de características: E ∈ R d.
Inteligencia Computacional (FICH, UNL) Bases estadísticas del Reconocimiento de Patrones 21 / 44
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Definiciones
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 de generalización.
Clases informacionales: salidas del sistema
Número de clases: c Conjunto de (etiquetas de) clases: = {ω1, ω2, . . . , ωc} Conjunto 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
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 de generalización.
Clases informacionales: salidas del sistema
Número de clases: c Conjunto de (etiquetas de) clases: = {ω1, ω2, . . . , ωc} Conjunto 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
gi : E → R, 1 ≤ i ≤ c
tal que dado un patrón x ∈ E,
.
.
. .
.
.
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 de decisión contiguas. Hipersuperficies definidas por: gi(x)− gj(x) = 0, i 6= j, 1 ≤ i, j ≤ c
x x
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 del vector de características.
Clasificador lineal:
g(x) = d∑
i=1
Parámetros: d+ 1. Fronteras: hiperplanos.
Clasificador cuadrático:
g(x) = d∑
i=1
t x+ w0
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.
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 una muestra 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:
i=1 P (ω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 de probabilidad que caracteriza la distribución estadística de las muestras de ωi.
“Probabilidad de observar la muestra x sabiendo que la etiqueta es c”
El vector de características x se considera una variable aleatoria d-dimensional de función de densidad P (x|ωi) cuando las muestras pertenecen a ωi.
Condiciones:
- P (x|ωi) ≥ 0, para i = 1, . . . , c. - ∫ E P (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∑
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 las muestras con independencia de las clases a las que pertenecen.
Se cumple que: P (x) ≥ 0, y ∫ E P (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∑
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 las muestras con independencia de las clases a las que pertenecen.
Se cumple que: P (x) ≥ 0, y ∫ E P (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 de que 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)∑c j=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...
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 mayor probabilidad a posteriori.
ω = argmaxωi:1≤i≤c P (ωi|x)
Clasificador de Bayes: utiliza las probabilidades a posteriori como funciones discriminantes. Es de mínimo error basado en FD monótonas crecientes f(·).
gi(x) = P (ωi|x) = P (x|ωi)P (ωi)
P (x)
Equivalencia entre clasificadores:
(g1, . . . , gc) ≡ (f(g1), . . . , f(gc)) ≡ (g′1, . . . , g ′ c) si Rc = R′
c ∀c.
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− max 1≤i≤c
P (ωi|x)
P (error) =
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.
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− max 1≤i≤c
P (ωi|x)
P (error) =
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.
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Aplicaciones del RP
Introducción Aprendizaje maquinal Reconocimiento estadístico de patrones Fin
Aplicaciones del RP
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
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
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
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
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
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
Economía
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
Introducción