Bases estadísti asdel re ono imiento de patronesCésar Martínez martinez _AT_ fi h.unl.edu.arInteligen ia Computa ionalFICH-UNL5 de setiembre de 2011

Introdu ión Re ono imiento estadísti o de patrones FinDeni ionesPatrón:Objeto de interés que es identi able del resto.Posiblemente difusos, no bien denidos, no visibles o tangibles.Ej: una huella digital, la voz de una persona, una ara, et .Re ono imiento de patrones (RP):Estudio de los pro esos de per ep ión y razonamiento humanos: apa idad de distinguir y aislar los patrones,reunirlos en grupos,asignarles un nombre identi atorio a ada grupo.Objetivo del RP: rear sistemas informáti os que imiten el omportamiento des ripto.Inteligen ia Computa ional (FICH, UNL) Bases estadísti as del RP 5 de setiembre de 2011 2 / 24

Introdu ión Re ono imiento estadísti o de patrones FinParadigma de trabajo on eptual(a) Adquisi ión: transdu ión del mundo real a la representa ión digital.(b) Pro esamiento digital: a ondi ionamiento y representa ión alternativa.( ) Clasi a ión: de isión sobre la lase.

Inteligen ia Computa ional (FICH, UNL) Bases estadísti as del RP 5 de setiembre de 2011 3 / 24

Introdu ión Re ono imiento estadísti o de patrones FinParadigma de trabajo fun ional

Inteligen ia Computa ional (FICH, UNL) Bases estadísti as del RP 5 de setiembre de 2011 4 / 24

Introdu ión Re ono imiento estadísti o de patrones FinAproxima ionesAproxima ión geométri a o estadísti a:Basada en la Teoría Estadísti a de la De isión.Representa ión de patrones omo ve tores numéri os.Representa ión de lases mediante patrones prototipo.Tipos de lasi adores: gaussianos, basados en distan ia, et .Aproxima ión estru tural o sintá ti a:Basada en la Teoría de Lenguajes Formales.Representa ión de patrones omo adenas de símbolos.Utiliza ión de reglas sintá ti as para espe i ar los patrones válidos deuna lase.Tipos de lasi adores: autómatas, gramáti as, HMM, et .Inteligen ia Computa ional (FICH, UNL) Bases estadísti as del RP 5 de setiembre de 2011 5 / 24

Introdu ión Re ono imiento estadísti o de patrones FinAproxima ionesAproxima ión geométri a o estadísti a:Basada en la Teoría Estadísti a de la De isión.Representa ión de patrones omo ve tores numéri os.Representa ión de lases mediante patrones prototipo.Tipos de lasi adores: gaussianos, basados en distan ia, et .Aproxima ión estru tural o sintá ti a:Basada en la Teoría de Lenguajes Formales.Representa ión de patrones omo adenas de símbolos.Utiliza ión de reglas sintá ti as para espe i ar los patrones válidos deuna lase.Tipos de lasi adores: autómatas, gramáti as, HMM, et .Inteligen ia Computa ional (FICH, UNL) Bases estadísti as del RP 5 de setiembre de 2011 5 / 24

Introdu ión Re ono imiento estadísti o de patrones FinEjemplo de aproxima ión geométri aClasi a ión de romosomas: representa ión numéri a

Inteligen ia Computa ional (FICH, UNL) Bases estadísti as del RP 5 de setiembre de 2011 6 / 24

Introdu ión Re ono imiento estadísti o de patrones FinEjemplo de aproxima ión sintá ti aClasi a ión de romosomas: representa ión estru turalCuanti a ión en 6 niveles: 3334122511114221111111224444444Cál ulo de diferen ias: Σ = =, A, a, . . . , E, eMayús ulas: diferen ia positiva.Minús ulas: diferen ia negativa.

A: diferen ia de 1, E: diferen ia de 5.Representa ión típi a (C19):==A A=Cd===Cb=a======A=C======Clasi adores: autómatas.Inteligen ia Computa ional (FICH, UNL) Bases estadísti as del RP 5 de setiembre de 2011 7 / 24

Introdu ión Re ono imiento estadísti o de patrones FinDeni ionesAdquisi ión y prepro eso de datos: ve tor numéri o 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 espa io de patrones P ∈ R

n.

Inteligen ia Computa ional (FICH, UNL) Bases estadísti as del RP 5 de setiembre de 2011 8 / 24

Introdu ión Re ono imiento estadísti o de patrones FinDeni ionesAdquisi ión y prepro eso de datos: ve tor numéri o 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 espa io de patrones P ∈ R

n.Extra ión de ara terísti as: informa ión relevante para la lasi a ión.Formalmente, dado un onjunto de patrones n-dimensionales y setrata de obtener un nuevo onjunto de representa ionesx = [x1 x2 . . . xd]

T , donde d ≤ n.Cambio en el espa io de representa ión: transforma iones lineales quemaximizan la varianza (d = n).Redu ión de dimensionalidad de los datos (d < n).Espa io de ara terísti as: E ∈ Rd.Inteligen ia Computa ional (FICH, UNL) Bases estadísti as del RP 5 de setiembre de 2011 8 / 24

Introdu ión Re ono imiento estadísti o de patrones FinDeni ionesExtra ión de ara terísti as: propiedades deseablesPre isión: representa iones diferentes para objetos diferentes.Uni idad o determinismo: representa ión úni a para ada objeto.Continuidad en el espa io: inmunidad al ruido y apa idad degeneraliza ión.Clases informa ionales: salidas del sistemaNúmero de lases: cConjunto de (etiquetas de) lases: Ω = ω1, ω2, . . . , ωcConjunto extendido: Ω∗ = ω1, ω2, . . . , ωc, ω0, donde ω0es la lase de re hazo.Inteligen ia Computa ional (FICH, UNL) Bases estadísti as del RP 5 de setiembre de 2011 9 / 24

Introdu ión Re ono imiento estadísti o de patrones FinDeni ionesExtra ión de ara terísti as: propiedades deseablesPre isión: representa iones diferentes para objetos diferentes.Uni idad o determinismo: representa ión úni a para ada objeto.Continuidad en el espa io: inmunidad al ruido y apa idad degeneraliza ión.Clases informa ionales: salidas del sistemaNúmero de lases: cConjunto de (etiquetas de) lases: Ω = ω1, ω2, . . . , ωcConjunto extendido: Ω∗ = ω1, ω2, . . . , ωc, ω0, donde ω0es la lase de re hazo.Inteligen ia Computa ional (FICH, UNL) Bases estadísti as del RP 5 de setiembre de 2011 9 / 24

Introdu ión Re ono imiento estadísti o de patrones FinDeni ionesClasi ador estadísti o: máquina formada por c (fun iones)dis riminantesgi : 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

.

.

. .

.

.

Inteligen ia Computa ional (FICH, UNL) Bases estadísti as del RP 5 de setiembre de 2011 10 / 24

Introdu ión Re ono imiento estadísti o de patrones FinRegiones y fronteras de de isiónRegiones de de isión: un lasi ador divide el espa io en c regiones dede isión R1, R2, . . . , Rc, tal queRi = x ∈ E : gi(x) > gj(x) ∀j 6= iFronteras de de isión: super ies del espa io que separan regiones dede isión ontiguas.Hipersuper ies denidas 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 Inteligen ia Computa ional (FICH, UNL) Bases estadísti as del RP 5 de setiembre de 2011 11 / 24

Introdu ión Re ono imiento estadísti o de patrones FinClasi adores estadísti os bási osLas FD son ombina iones lineales o uadráti as de las omponentes delve tor de ara terísti as.Clasi ador lineal:g(x) =

d∑i=1

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

g(x) =d∑

i=1

d∑j=1

wijxixj +d∑

i=1

wixi + w0 = xtWx + w

tx + w0Parámetros: 1

2d(d + 1) + d + 1. Fronteras: hiper uádri as.Inteligen ia Computa ional (FICH, UNL) Bases estadísti as del RP 5 de setiembre de 2011 12 / 24

Introdu ión Re ono imiento estadísti o de patrones FinEjemplo: OCR de dígitos manus ritosUnidimensional: brillo global.

Inteligen ia Computa ional (FICH, UNL) Bases estadísti as del RP 5 de setiembre de 2011 13 / 24

Introdu ión Re ono imiento estadísti o de patrones FinEjemplo: OCR de dígitos manus ritosBidimensional: brillo de mitad superior (x1) e inferior (x2).

Inteligen ia Computa ional (FICH, UNL) Bases estadísti as del RP 5 de setiembre de 2011 14 / 24

Introdu ión Re ono imiento estadísti o de patrones FinDeni iones de teoría de la de isiónProbabilidad a priori P (ωi) de una lase ωi: probabilidad de que unamuestra arbitraria pertenez a a ωi.Probabilidad de observar la etiqueta c sin saber qué muestra esPuede verse omo la propor ión de muestras de ωi respe to al total( ono imiento que se tiene antes de ha er los experimentos).Condi iones:- 0 ≤ P (ωi) ≤ 1, para i = 1, . . . , c.- ∑c

i=1P (ωi) = 1.Clasi ador trivial de dos lases basado en probabilidades a priori:De idir por ω1 si P (ω1) > P (ω2)De idir por ω2 si P (ω1) < P (ω2)Inteligen ia Computa ional (FICH, UNL) Bases estadísti as del RP 5 de setiembre de 2011 15 / 24

Introdu ión Re ono imiento estadísti o de patrones FinDeni iones de teoría de la de isiónDensidad ondi ional P (x|ωi) de una lase ωi: fun ión de densidad deprobabilidad que ara teriza la distribu ión estadísti a de las muestrasde ωi.Probabilidad de observar la muestra x sabiendo que la etiqueta es cEl ve tor de ara terísti as x se onsidera una variable aleatoriad-dimensional de fun ión de densidad P (x|ωi) uando las muestraspertene en a ωi.Condi iones:- P (x|ωi) ≥ 0, para i = 1, . . . , c.- ∫

EP (x|ωi) dx = 1.

Inteligen ia Computa ional (FICH, UNL) Bases estadísti as del RP 5 de setiembre de 2011 16 / 24

Introdu ión Re ono imiento estadísti o de patrones FinDeni iones de teoría de la de isiónLa probabilidad onjunta P (x, ωi) muestra- lase se dene omoP (x, ωi) = P (ωi)P (x|ωi)Probabilidad de observar la muestra x on la etiqueta cLa densidad in ondi ional P (x) de las muestras se dene 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 etiquetaLa densidad in ondi ional ara teriza la distribu ión estadísti a de lasmuestras on independen ia de las lases a las que pertene en.Se umple que: P (x) ≥ 0, y ∫E

P (x) dx = 1.Inteligen ia Computa ional (FICH, UNL) Bases estadísti as del RP 5 de setiembre de 2011 17 / 24

Introdu ión Re ono imiento estadísti o de patrones FinDeni iones de teoría de la de isiónLa probabilidad onjunta P (x, ωi) muestra- lase se dene omoP (x, ωi) = P (ωi)P (x|ωi)Probabilidad de observar la muestra x on la etiqueta cLa densidad in ondi ional P (x) de las muestras se dene 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 etiquetaLa densidad in ondi ional ara teriza la distribu ión estadísti a de lasmuestras on independen ia de las lases a las que pertene en.Se umple que: P (x) ≥ 0, y ∫E

P (x) dx = 1.Inteligen ia Computa ional (FICH, UNL) Bases estadísti as del RP 5 de setiembre de 2011 17 / 24

Introdu ión Re ono imiento estadísti o de patrones FinDeni iones de teoría de la de isió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.Inteligen ia Computa ional (FICH, UNL) Bases estadísti as del RP 5 de setiembre de 2011 18 / 24

Introdu ión Re ono imiento estadísti o de patrones FinDeni iones de teoría de la de isiónSupongamos que tenemos ono idas P (ωi), P (x|ωi) y una medida de x.¾Cómo inuye este ono imiento sobre la de isión del lasi ador?Probabilidad a posteriori P (ωi|x) de una lase ωi: probabilidad deque una muestra parti ular x pertenez a a ωi.Probabilidad de observar la etiqueta c sabiendo que la muestra es xSe al ula 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 ∑c

i=1 P (ωi|x) = 1.Puede verse omo una a tualiza ión de P (ωi) después de observar x.Inteligen ia Computa ional (FICH, UNL) Bases estadísti as del RP 5 de setiembre de 2011 19 / 24

Introdu ión Re ono imiento estadísti o de patrones FinDeni iones de teoría de la de isión

Idea para un lasi ador...Inteligen ia Computa ional (FICH, UNL) Bases estadísti as del RP 5 de setiembre de 2011 20 / 24

Introdu ión Re ono imiento estadísti o de patrones FinClasi ador de BayesRegla de lasi a ión de Bayes: asignar a x la lase on mayorprobabilidad a posteriori.ω = arg maxωi:1≤i≤c P (ωi|x)Clasi ador de Bayes: utiliza las probabilidades a posteriori omofun iones dis riminantes. Es de mínimo error basado en FDmonótonas re ientes 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)Equivalen ia entre lasi adores:(g1, . . . , gc) ≡ (f(g1), . . . , f(gc)) ≡ (g′1, . . . , g

′c) si Rc = R′

c ∀c.Inteligen ia Computa ional (FICH, UNL) Bases estadísti as del RP 5 de setiembre de 2011 21 / 24

Introdu ión Re ono imiento estadísti o de patrones FinClasi ador de BayesError de Bayes a posteriori: probabilidad de error puntual dado porP (error|x) = 1 − max

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

P (error) =

∫E

P (error|x)P (x)dxProblemas on el ál ulo analíti o del error:P (ωi) y P (x|ωi) des ono idas.Regiones de integra ión omplejas.Solu ión: estima ión del error.Inteligen ia Computa ional (FICH, UNL) Bases estadísti as del RP 5 de setiembre de 2011 22 / 24

Introdu ión Re ono imiento estadísti o de patrones FinClasi ador de BayesError de Bayes a posteriori: probabilidad de error puntual dado porP (error|x) = 1 − max

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

P (error) =

∫E

P (error|x)P (x)dxProblemas on el ál ulo analíti o del error:P (ωi) y P (x|ωi) des ono idas.Regiones de integra ión omplejas.Solu ión: estima ión del error.Inteligen ia Computa ional (FICH, UNL) Bases estadísti as del RP 5 de setiembre de 2011 22 / 24

Introdu ión Re ono imiento estadísti o de patrones FinApli a iones del RPRe ono imiento de ImágenesOCR - Análisis de do umentos - Re . de rmas - Identif. de patentes -Dete ión de defe tos en piezas industriales ( ontrol de alidad) - Re .de gestos fa ialesRe ono imiento de Habla y LenguajeRe . de palabras aisladas y dis urso ontinuo - Identif. del lo utor -Tradu ión automáti a - ComprensiónApli a iones Biomédi asSegmenta ión de tejido en imágenes médi as - Bioidenti a ión(huellas da tilares, palma, iris, otros)E onomíaMinería de datos - Dete ión de patrones de fraudeApli a iones en astronomía, agri ultura, prote ión ivil, et .Inteligen ia Computa ional (FICH, UNL) Bases estadísti as del RP 5 de setiembre de 2011 23 / 24

Introdu ión Re ono imiento estadísti o de patrones FinFinBibliografía:- Duda R., Hart P, Stork D., Pattern Classi ation, Se ond Edition.Wiley-Inters ien e, 2000. Capítulos 1, 2.1 a 2.6, 3.1 a 3.2.- Lista de la átedra

Inteligen ia Computa ional (FICH, UNL) Bases estadísti as del RP 5 de setiembre de 2011 24 / 24