Bases estadístiasdel reonoimiento de patronesCésar Martínezmartinez _AT_ fih.unl.edu.arInteligenia ComputaionalFICH-UNL5 de setiembre de 2011

Introdu

ión Reonoimiento estadístio de patrones FinDe�niionesPatrón:Objeto de interés que es identi�able del resto.Posiblemente difusos, no bien de�nidos, no visibles o tangibles.Ej: una huella digital, la voz de una persona, una ara, et.Reonoimiento de patrones (RP):Estudio de los proesos de perepión y razonamiento humanos:apaidad de distinguir y aislar los patrones,reunirlos en grupos,asignarles un nombre identi�atorio a ada grupo.Objetivo del RP: rear sistemas informátios que imiten elomportamiento desripto.Inteligenia Computaional (FICH, UNL) Bases estadístias del RP 5 de setiembre de 2011 2 / 24

Introdu

ión Reonoimiento estadístio de patrones FinParadigma de trabajo oneptual(a) Adquisiión: transdu

ión del mundo real a la representaión digital.(b) Proesamiento digital: aondiionamiento y representaión alternativa.() Clasi�aión: deisión sobre la lase.

Inteligenia Computaional (FICH, UNL) Bases estadístias del RP 5 de setiembre de 2011 3 / 24

Introdu

ión Reonoimiento estadístio de patrones FinParadigma de trabajo funional

Inteligenia Computaional (FICH, UNL) Bases estadístias del RP 5 de setiembre de 2011 4 / 24

Introdu

ión Reonoimiento estadístio de patrones FinAproximaionesAproximaión geométria o estadístia:Basada en la Teoría Estadístia de la Deisión.Representaión de patrones omo vetores numérios.Representaión de lases mediante patrones prototipo.Tipos de lasi�adores: gaussianos, basados en distania, et.Aproximaión estrutural o sintátia:Basada en la Teoría de Lenguajes Formales.Representaión de patrones omo adenas de símbolos.Utilizaión de reglas sintátias para espei�ar los patrones válidos deuna lase.Tipos de lasi�adores: autómatas, gramátias, HMM, et.Inteligenia Computaional (FICH, UNL) Bases estadístias del RP 5 de setiembre de 2011 5 / 24

Introdu

ión Reonoimiento estadístio de patrones FinAproximaionesAproximaión geométria o estadístia:Basada en la Teoría Estadístia de la Deisión.Representaión de patrones omo vetores numérios.Representaión de lases mediante patrones prototipo.Tipos de lasi�adores: gaussianos, basados en distania, et.Aproximaión estrutural o sintátia:Basada en la Teoría de Lenguajes Formales.Representaión de patrones omo adenas de símbolos.Utilizaión de reglas sintátias para espei�ar los patrones válidos deuna lase.Tipos de lasi�adores: autómatas, gramátias, HMM, et.Inteligenia Computaional (FICH, UNL) Bases estadístias del RP 5 de setiembre de 2011 5 / 24

Introdu

ión Reonoimiento estadístio de patrones FinEjemplo de aproximaión geométriaClasi�aión de romosomas: representaión numéria������������

���

����

�����

������Inteligenia Computaional (FICH, UNL) Bases estadístias del RP 5 de setiembre de 2011 6 / 24

Introdu

ión Reonoimiento estadístio de patrones FinEjemplo de aproximaión sintátiaClasi�aión de romosomas: representaión estruturalCuanti�aión en 6 niveles: 3334122511114221111111224444444Cálulo de diferenias: Σ = {=, A, a, . . . , E, e}Mayúsulas: diferenia positiva.Minúsulas: diferenia negativa.

A: diferenia de 1, E: diferenia de 5.Representaión típia (C19):==AA=Cd===Cb=a======A=C======Clasi�adores: autómatas.Inteligenia Computaional (FICH, UNL) Bases estadístias del RP 5 de setiembre de 2011 7 / 24

Introdu

ión Reonoimiento estadístio de patrones FinDe�niionesAdquisiión y preproeso de datos: vetor numério que representa alpatrón natural.Formalmente, un patrón es una variable aleatoria n-dimensionaly = [y1 y2 . . . yn]

T , on yi ∈ R para i = 1, 2, . . . , n, que representaun punto en el espaio de patrones P ∈ Rn.

Inteligenia Computaional (FICH, UNL) Bases estadístias del RP 5 de setiembre de 2011 8 / 24

Introdu

ión Reonoimiento estadístio de patrones FinDe�niionesAdquisiión y preproeso de datos: vetor numério que representa alpatrón natural.Formalmente, un patrón es una variable aleatoria n-dimensionaly = [y1 y2 . . . yn]

T , on yi ∈ R para i = 1, 2, . . . , n, que representaun punto en el espaio de patrones P ∈ Rn.Extra

ión de araterístias: informaión relevante para lalasi�aión.Formalmente, dado un onjunto de patrones n-dimensionales y setrata de obtener un nuevo onjunto de representaionesx = [x1 x2 . . . xd]

T , donde d ≤ n.Cambio en el espaio de representaión: transformaiones lineales quemaximizan la varianza (d = n).Redu

ión de dimensionalidad de los datos (d < n).Espaio de araterístias: E ∈ Rd.Inteligenia Computaional (FICH, UNL) Bases estadístias del RP 5 de setiembre de 2011 8 / 24

Introdu

ión Reonoimiento estadístio de patrones FinDe�niionesExtra

ión de araterístias: propiedades deseablesPreisión: representaiones diferentes para objetos diferentes.Uniidad o determinismo: representaión únia para ada objeto.Continuidad en el espaio: inmunidad al ruido y apaidad degeneralizaión.Clases informaionales: salidas del sistemaNúmero de lases: cConjunto de (etiquetas de) lases: Ω = {ω1, ω2, . . . , ωc}Conjunto extendido: Ω∗ = {ω1, ω2, . . . , ωc, ω0}, donde ω0es la lase de rehazo.Inteligenia Computaional (FICH, UNL) Bases estadístias del RP 5 de setiembre de 2011 9 / 24

Introdu

ión Reonoimiento estadístio de patrones FinDe�niionesExtra

ión de araterístias: propiedades deseablesPreisión: representaiones diferentes para objetos diferentes.Uniidad o determinismo: representaión únia para ada objeto.Continuidad en el espaio: inmunidad al ruido y apaidad degeneralizaión.Clases informaionales: salidas del sistemaNúmero de lases: cConjunto de (etiquetas de) lases: Ω = {ω1, ω2, . . . , ωc}Conjunto extendido: Ω∗ = {ω1, ω2, . . . , ωc, ω0}, donde ω0es la lase de rehazo.Inteligenia Computaional (FICH, UNL) Bases estadístias del RP 5 de setiembre de 2011 9 / 24

Introdu

ión Reonoimiento estadístio de patrones FinDe�niionesClasi�ador estadístio: máquina formada por c (funiones)disriminantesgi : E → R, 1 ≤ i ≤ ctal que dado un patrón x ∈ E,

x se asigna a la lase ωi si gi(x) > gj(x) ∀j 6= i..

. .

.

.

Inteligenia Computaional (FICH, UNL) Bases estadístias del RP 5 de setiembre de 2011 10 / 24

Introdu

ión Reonoimiento estadístio de patrones FinRegiones y fronteras de deisiónRegiones de deisión: un lasi�ador divide el espaio en c regiones dedeisión R1, R2, . . . , Rc, tal queRi = {x ∈ E : gi(x) > gj(x) ∀j 6= i}Fronteras de deisión: super�ies del espaio que separan regiones dedeisión ontiguas.Hipersuper�ies de�nidas por: gi(x) − gj(x) = 0, i 6= j, 1 ≤ i, j ≤ c

xx

x

xx

x

x

xx

xx

xx

xx

xx

x

R1

R2Inteligenia Computaional (FICH, UNL) Bases estadístias del RP 5 de setiembre de 2011 11 / 24

Introdu

ión Reonoimiento estadístio de patrones FinClasi�adores estadístios básiosLas FD son ombinaiones lineales o uadrátias de las omponentes delvetor de araterístias.Clasi�ador lineal:g(x) =

d∑i=1

wixi + w0 = wtx + w0Parámetros: d + 1. Fronteras: hiperplanos.Clasi�ador uadrátio:

g(x) =d∑

i=1

d∑j=1

wijxixj +d∑

i=1

wixi + w0 = xtWx + wtx + w0Parámetros: 12d(d + 1) + d + 1. Fronteras: hiperuádrias.Inteligenia Computaional (FICH, UNL) Bases estadístias del RP 5 de setiembre de 2011 12 / 24

Introdu

ión Reonoimiento estadístio de patrones FinEjemplo: OCR de dígitos manusritosUnidimensional: brillo global.

Inteligenia Computaional (FICH, UNL) Bases estadístias del RP 5 de setiembre de 2011 13 / 24

Introdu

ión Reonoimiento estadístio de patrones FinEjemplo: OCR de dígitos manusritosBidimensional: brillo de mitad superior (x1) e inferior (x2).

Inteligenia Computaional (FICH, UNL) Bases estadístias del RP 5 de setiembre de 2011 14 / 24

Introdu

ión Reonoimiento estadístio de patrones FinDe�niiones de teoría de la deisiónProbabilidad a priori P (ωi) de una lase ωi: probabilidad de que unamuestra arbitraria perteneza a ωi.�Probabilidad de observar la etiqueta c sin saber qué muestra es�Puede verse omo la proporión de muestras de ωi respeto al total(onoimiento que se tiene antes de haer los experimentos).Condiiones:- 0 ≤ P (ωi) ≤ 1, para i = 1, . . . , c.- ∑ci=1

P (ωi) = 1.Clasi�ador trivial de dos lases basado en probabilidades a priori:Deidir por ω1 si P (ω1) > P (ω2)Deidir por ω2 si P (ω1) < P (ω2)Inteligenia Computaional (FICH, UNL) Bases estadístias del RP 5 de setiembre de 2011 15 / 24

Introdu

ión Reonoimiento estadístio de patrones FinDe�niiones de teoría de la deisiónDensidad ondiional P (x|ωi) de una lase ωi: funión de densidad deprobabilidad que arateriza la distribuión estadístia de las muestrasde ωi.�Probabilidad de observar la muestra x sabiendo que la etiqueta es c�El vetor de araterístias x se onsidera una variable aleatoriad-dimensional de funión de densidad P (x|ωi) uando las muestrasperteneen a ωi.Condiiones:- P (x|ωi) ≥ 0, para i = 1, . . . , c.- ∫

EP (x|ωi) dx = 1.

Inteligenia Computaional (FICH, UNL) Bases estadístias del RP 5 de setiembre de 2011 16 / 24

Introdu

ión Reonoimiento estadístio de patrones FinDe�niiones de teoría de la deisiónLa probabilidad onjunta P (x, ωi) muestra-lase se de�ne omoP (x, ωi) = P (ωi)P (x|ωi)�Probabilidad de observar la muestra x on la etiqueta c�La densidad inondiional P (x) de las muestras se de�ne omo

P (x) =c∑

j=1

P (x, ωj) =c∑

j=1

P (x|ωj)P (ωj)�Probabilidad de observar la muestra x sin saber uál es su etiqueta�La densidad inondiional arateriza la distribuión estadístia de lasmuestras on independenia de las lases a las que perteneen.Se umple que: P (x) ≥ 0, y ∫E

P (x) dx = 1.Inteligenia Computaional (FICH, UNL) Bases estadístias del RP 5 de setiembre de 2011 17 / 24

Introdu

ión Reonoimiento estadístio de patrones FinDe�niiones de teoría de la deisiónLa probabilidad onjunta P (x, ωi) muestra-lase se de�ne omoP (x, ωi) = P (ωi)P (x|ωi)�Probabilidad de observar la muestra x on la etiqueta c�La densidad inondiional P (x) de las muestras se de�ne omo

P (x) =c∑

j=1

P (x, ωj) =c∑

j=1

P (x|ωj)P (ωj)�Probabilidad de observar la muestra x sin saber uál es su etiqueta�La densidad inondiional arateriza la distribuión estadístia de lasmuestras on independenia de las lases a las que perteneen.Se umple que: P (x) ≥ 0, y ∫E

P (x) dx = 1.Inteligenia Computaional (FICH, UNL) Bases estadístias del RP 5 de setiembre de 2011 17 / 24

Introdu

ión Reonoimiento estadístio de patrones FinDe�niiones de teoría de la deisión

Signi�ado de: P (ω = 0) = 0,5; P (x = 45|ω = 0) = 0,033;P (x = 45, ω = 0) = 0,016; P (x = 45) = 0,054.Inteligenia Computaional (FICH, UNL) Bases estadístias del RP 5 de setiembre de 2011 18 / 24

Introdu

ión Reonoimiento estadístio de patrones FinDe�niiones de teoría de la deisiónSupongamos que tenemos onoidas P (ωi), P (x|ωi) y una medida de x.¾Cómo in�uye este onoimiento sobre la deisión del lasi�ador?Probabilidad a posteriori P (ωi|x) de una lase ωi: probabilidad deque una muestra partiular x perteneza a ωi.�Probabilidad de observar la etiqueta c sabiendo que la muestra es x�Se alula 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 umple que: 0 ≤ P (ωi|x) ≤ 1, y ∑ci=1 P (ωi|x) = 1.Puede verse omo una atualizaión de P (ωi) después de observar x.Inteligenia Computaional (FICH, UNL) Bases estadístias del RP 5 de setiembre de 2011 19 / 24

Introdu

ión Reonoimiento estadístio de patrones FinDe�niiones de teoría de la deisión

Idea para un lasi�ador...Inteligenia Computaional (FICH, UNL) Bases estadístias del RP 5 de setiembre de 2011 20 / 24

Introdu

ión Reonoimiento estadístio de patrones FinClasi�ador de BayesRegla de lasi�aión de Bayes: asignar a x la lase on mayorprobabilidad a posteriori.ω̂ = arg máxωi:1≤i≤c P (ωi|x)Clasi�ador de Bayes: utiliza las probabilidades a posteriori omofuniones disriminantes. Es de mínimo error basado en FDmonótonas reientes f(·).

gi(x) = P (ωi|x) = P (x|ωi)P (ωi)P (x)≡ P (x|ωi)P (ωi)

≡ log P (x|ωi) + log P (ωi)Equivalenia entre lasi�adores:(g1, . . . , gc) ≡ (f(g1), . . . , f(gc)) ≡ (g

′1, . . . , g

′c) si Rc = R′c ∀c.Inteligenia Computaional (FICH, UNL) Bases estadístias del RP 5 de setiembre de 2011 21 / 24

Introdu

ión Reonoimiento estadístio de patrones FinClasi�ador de BayesError de Bayes a posteriori: probabilidad de error puntual dado porP (error|x) = 1 − máx

1≤i≤cP (ωi|x)Probabilidad media de error del lasi�ador:

P (error) = ∫E

P (error|x)P (x)dxProblemas on el álulo analítio del error:P (ωi) y P (x|ωi) desonoidas.Regiones de integraión omplejas.Soluión: estimaión del error.Inteligenia Computaional (FICH, UNL) Bases estadístias del RP 5 de setiembre de 2011 22 / 24

Introdu

ión Reonoimiento estadístio de patrones FinClasi�ador de BayesError de Bayes a posteriori: probabilidad de error puntual dado porP (error|x) = 1 − máx

1≤i≤cP (ωi|x)Probabilidad media de error del lasi�ador:

P (error) = ∫E

P (error|x)P (x)dxProblemas on el álulo analítio del error:P (ωi) y P (x|ωi) desonoidas.Regiones de integraión omplejas.Soluión: estimaión del error.Inteligenia Computaional (FICH, UNL) Bases estadístias del RP 5 de setiembre de 2011 22 / 24

Introdu

ión Reonoimiento estadístio de patrones FinApliaiones del RPReonoimiento de ImágenesOCR - Análisis de doumentos - Re. de �rmas - Identif. de patentes -Dete

ión de defetos en piezas industriales (ontrol de alidad) - Re.de gestos faialesReonoimiento de Habla y LenguajeRe. de palabras aisladas y disurso ontinuo - Identif. del loutor -Tradu

ión automátia - ComprensiónApliaiones BiomédiasSegmentaión de tejido en imágenes médias - Bioidenti�aión(huellas datilares, palma, iris, otros)EonomíaMinería de datos - Dete

ión de patrones de fraudeApliaiones en astronomía, agriultura, prote

ión ivil, et.Inteligenia Computaional (FICH, UNL) Bases estadístias del RP 5 de setiembre de 2011 23 / 24

Introdu

ión Reonoimiento estadístio de patrones FinFinBibliografía:- Duda R., Hart P, Stork D., Pattern Classi�ation, Seond Edition.Wiley-Intersiene, 2000. Capítulos 1, 2.1 a 2.6, 3.1 a 3.2.- Lista de la átedra

Inteligenia Computaional (FICH, UNL) Bases estadístias del RP 5 de setiembre de 2011 24 / 24

Introducción

Reconocimiento estadístico de patrones

Fin