Reconocimiento Patrones Cap2

Reconocimiento de Patrones Tema 2: Reconocimiento Estadstico de Patrones

Escuela Tcnica Superior de Ingeniera Informtica. Universidad de La Laguna

Fernando Prez Nava

Introduccin

Por qu una aproximacin estadstica en el RP? La utilizacin de caractersticas para representar una entidad provoca una

prdida de informacin. Esto implica que los valores de las caractersticas tienen asociado un determinado nivel de certeza.

El Reconocimiento Estadstico de Patrones (REP) se basa en: Considerar un patrn como un conjunto de d caractersticas numricas que

se interpretan como un vector d dimensional Asumir que la certeza de que el vector represente una determinada entidad

viene dada a travs de una distribucin de probabilidad asociada a las caractersticas

Es la aproximacin ms extendida debido a: La fundamentacin de la aproximacin en una teora matemtica slida

como la teora de la probabilidad. Su mayor presencia temporal en el rea de RP (desde finales de los aos

30). Su mayor aplicabilidad:

Clasificacin con valores de las caractersticas perdidas Toma de decisiones que minimizan la prdida esperada



Fernando Prez Nava

Recordatorio de Probabilidad (1)

Cuando estamos en un entorno en el que no existe certeza absoluta es necesario tener alguna forma de modelar la incertidumbre.

Dentro de la IA existen muchas formas de modelar la incertidumbre: probabilidad, lgica difusa, teora de Dempster-Shaffer.

Puede comprobarse (Cox 1946) que si se pretende trabajar de forma consistente con niveles de certeza, stos nmeros deben cumplir las reglas de la teora de la probabilidad.

La Teora de la Probabilidad (TP) asocia un valor numrico entre 0 y 1 a la certeza en un evento. La certeza absoluta de que un evento ocurrir toma el valor 1 y la certeza completa de que un evento no ocurrir toma el valor 0.

(Cox, 1946) Cox R.T, Probability, Frequency, and Reasonable Expectation, Am. Jour. Phys., 14, 1-13, (1946).



Fernando Prez Nava

Recordatorio de Probabilidad (2)

Las probabilidades se manipulan con dos reglas sencillas: Regla del Producto

Dadas dos variables X e Y que pueden tomar un conjunto finito de valores si llamamos P(x,y) a la probabilidad conjunta de que ocurran X=x e Y=y entonces:

P(x,y)=P(y|x)P(x)donde:P(y|x) es la probabilidad condicional de que Y=y dado que X=xP(x) es la probabilidad marginal de que X=x independientemente de YDe forma similar: P(x,y)=P(x|y)P(y)

Regla de la suma Dadas de nuevo las variables X e Y se tiene:

donde la suma se hace sobre todos los valores x de la variable XDe forma similar: =

yyxx ),(P)P(

=x

yxy ),(P)P(



Fernando Prez Nava

Recordatorio de Probabilidad (3) A partir de la regla del producto se obtiene la Regla de Bayes:

con:

Podemos considerar P(x) como la probabilidad a priori (inicial) de que X=x antes de observar la variable Y.Entonces P(x|y) nos dice la probabilidad de que X=x despus de observar la variable Y.

La regla de Bayes proporciona por tanto la forma de adaptarnuestras creencias iniciales a la vista de nueva informacin

)(P)P()|P()|P(

yxxyyx =

==xx

xxyyxy )(P)|(P),(P)P(



Fernando Prez Nava

La frecuencia relativa de un evento es el cociente entre el nmero de veces que se presenta un evento y el nmero total de observaciones

Las frecuencias relativas y las probabilidades tienen propiedades muy parecidas: Ambas toman valores entre 0 y 1 Ambas cumplen la Regla del Producto, la Regla de la Suma y la

Regla de Bayes De hecho, la frecuencia relativa de un evento converge* a su

probabilidad cuando el nmero de observaciones tiende a infinito.

Frecuencias Relativas y Probabilidades

*Converge con probabilidad 1

Ejemplo de convergencia de frecuencias relativas a probabilidadesAzul: Probabilidad de obtener n caras al tirar 4 monedasRojo: Frecuencia relativa del nmero de caras tras 100 lanzamientos



Fernando Prez Nava

Teora de Decisin Bayesiana (TDB): Motivacin (1)

Retomemos el experimento de la clasificacin con 2 Clases, salmones y rdalos. (w1 y w2)

Supongamos que la caracterstica elegida es la longitud (X) y supongamos por simplificar que sta toma 3 valores: x1=corta (0-40 cm), x2=media(40-100 cm) y x3=larga (>100 cm)

Supongamos que tenemos el siguiente conjunto de entrenamiento: H={(x1, w2), (x2, w2), (x2, w2), (x2, w2), (x2, w2), (x2, w2), (x2, w2), (x3, w2), (x3, w2), (x1, w1), (x1, w1), (x1, w1), (x1, w1), (x2, w1), (x2, w1), (x2, w1), (x2, w1), (x2, w1), (x3, w1), (x3, w1)}

Como disearas el clasificador? Cul sera tu eleccin (w1 o w2) si:

Se observa X= x1 (Corta) Se observa X= x2 (Media) Se observa X= x3 (Larga)



Fernando Prez Nava

TDB: Motivacin (2) Un criterio sencillo: buscar la regla que produzca menos errores o

lo que es lo mismo elegir la clase de mayor frecuencia absoluta (o relativa)

La frecuencia relativa del error de esta regla es 8/20 y no hay ninguna regla con menor error sobre este conjunto de entrenamiento*.

4 5 2

1 6 2

4/20 5/20 2/201/20 6/20 2/20

Frecuencias absolutas

Frecuencias relativas

x1 x2 x3

x1 x2 x3

Decisin. Naranja:Salmn, Violeta:Rdalo.

*Hay otra regla con el mismo error

w1

w2

w1

w2

1 6 2

4 5 2Errores absolutos sobre el conjunto de entrenamiento. Amarillo: Valores mnimos

x1 x2 x3

Elijo w1

Elijo w2

1/20 6/20 2/204/20 5/20 2/20Errores relativos sobre el conjunto de entrenamiento. Amarillo: Valores mnimos

x1 x2 x3

Elijo w1

Elijo w2



Fernando Prez Nava

TDB: Motivacin (3) A que se aproxima la tabla de errores relativos cuando el nmero

de muestras tiende a infinito?

Converge a la probabilidad de error. Por tanto en el caso ideal de un nmero infinito de muestras la relacin entre frecuencias relativas y probabilidades sugiere utilizar : Elegir w1 si P(x, w1) > P(x, w2) Elegir w2 si P(x, w2) > P(x, w1)

La intuicin es buena. La regla anterior es ptima.

1/20 6/20 2/204/20 5/20 2/20Errores relativos sobre el conjunto de entrenamiento. Amarillo: Valores mnimos

x1 x2 x3

Elijo w1

Elijo w2

P(x1,w2) P(x2,w2) P(x3,w2)P(x1,w1) P(x2,w1) P(x3,w1)

Probabilidad de error.

x1 x2 x3

Elijo w1

Elijo w2



Fernando Prez Nava

TDB: Motivacin (4) La regla:

Elegir w1 si P(x, w1) > P(x, w2) Elegir w2 si P(x, w2) > P(x, w1)

se puede escribir como (utilizando la regla del producto): Elegir w1 si P(x |w1) P(w1) > P(x |w2) P(w2) Elegir w2 si P(x |w2) P(w2) > P(x |w1) P(w1)

P(x |wi) se llama distribucin de la caracterstica en la clase e indica la probabilidad de los valores de X dentro de la clase wiP(wi) se llama probabilidad a priori de la clase e indica la probabilidad de que aparezca un objeto de la clase wi

o dividiendo en ambos miembros por p(x) se obtiene: Elegir w1 si P(w1 |x) > P(w2 | x) Elegir w2 si P(w2 |x) > P(w1 | x)

P(wi | x) se llama probabilidad a posteriori de la clase e indica la probabilidad de la clase tras haber observado la variable X

entonces, la regla ptima consiste en elegir la clase ms probable tras haber observado el valor x.



Fernando Prez Nava

TDB: Motivacin (5) Volviendo al problema del pescado cmo interpretamos las

probabilidades P(wi), P(x |wi), P(wi |x) 4 5 2

1 6 2Frecuencias absolutas

x1 x2 x3

x1 x2 x3

w1

w2

Frecuencias relativa de X en w1

x1 x2 x3

w1

Frecuencias relativa de cada clase

w1

w2

11/209/20

4/11 5/11 2/11 1/9 6/9 2/9Frecuencias relativa de X en w2

w2

x1 x2 x3

Frecuencias relativa de w1 dado X

x1 x2 x3

w1

4/5 5/11 2/4 1/5 6/11 2/4Frecuencias relativa de w2 dado X

w2

x1 x2 x3Elegir w2Elegir w1

Regiones de decisin: Representacin grfica



Fernando Prez Nava

Recordatorio de Probabilidad (4) Variables Aleatorias Continuas

Cuando una variable X toma valores reales la probabilidad de tomar un valor especfico es siempre nula. Por ello se habla de la probabilidad de que tome valores en un intervalo (a,b) mediante una funcin de densidad p(x):

En general, todas las definiciones dadas para variables discretas se pasan a continuas cambiando sumas por integrales. As si X e Y son continuas las reglas del producto, suma y de Bayes quedan:

Cuando se tiene un vector de variables aleatorias X=(X1, X2,... Xn)Tse tiene una funcin de densidad multidimensional p(x)

=b

a

dxxpbax )()),((P

= dxyxpyp ),()( )()()|()|(

ypxpxypyxp =)()|(),( xpxypyxp =

=R

dpR xxx )()(P



Fernando Prez Nava

Teora de la Decisin Bayesiana (TDB)

La TDB proporciona un marco terico para tomar decisiones en situaciones de incertidumbre.

En nuestro caso la decisin ser la clasificacin de un patrn en una determinada clase

La TDB proporciona el clasificador ptimo (clasificador bayesiano) para un conjunto de caractersticas dadas En el marco de la TDB un clasificador es ptimo si produce la

mnima probabilidad de error (o el riesgo de la clasificacin). La TDB necesita que todas las distribuciones de probabilidad de

las caractersticas p(x |wi) en cada clase sean conocidas.En la prctica esto nunca ocurre, por lo que es necesario inferir (de lasmuestras) la forma de las distribuciones de probabilidad. Tambin es necesario inferir las probabilidades a priori P(wi)



Fernando Prez Nava

TDB: Enfoque formal (1) Informacin disponible:

Clases: wi, i=1...c Caractersticas : X variable aleatoria multidimensional. Probabilidades: P(wi), p(x | wi), i=1...c Mediante la Regla de Bayes:

Ejemplo:

=

===

c

iii

iii ppcip

p1

)P()|()(con...1,)()P()|()|P( wwwww xx

x

xx

p(x | w1)

p(x | w2) p(x | w3)

p(x | w4) P(w1| x)

P(w2|x) P(w3 |x)

P(w4 |x)Distribucin de X en cada clase

Probabilidades a posterioriProbabilidades a priori iguales



Fernando Prez Nava

TDB: Enfoque formal (2)

Probabilidad de error Elegir wi

Regla de decisin Bayesiana (ptima): Elegir wi si P(wi | x) P(wj | x) ij

p(x | wi)P(wi) p(x | wj)P(wj) ij

Propiedad: Hace mnima la probabilidad de error:

= xxx d )()|P()(P pErrorError

P(w1| x)

P(w2|x) P(w3 |x)

P(w4 |x)

)|P(1)|P()|(P,1

xxx ic

ikkkError ww ==

=

Elegir w1

Elegir w2

Elegir w4

Elegir w3

Elegir w4



Fernando Prez Nava

Decisin Bayesiana con Riesgo (DBR): Motivacin (1)

Retomemos el experimento anterior con 2 Clases: salmones y rdalos. (w1 y w2); una caracterstica: longitud con tres valores x1=corta, x2=media y x3=larga y el conjunto de entrenamiento:

H={(x1, w2), (x2, w2), (x2, w2), (x2, w2), (x2, w2), (x2, w2), (x2, w2), (x3, w2), (x3, w2), (x1, w1), (x1, w1), (x1, w1), (x1, w1), (x2, w1), (x2, w1), (x2, w1), (x2, w1), (x2, w1), (x3, w1), (x3, w1)}

Los errores que aparecen al realizar la clasificacin son: Elegir w1 (salmn) cuando la clase verdadera es w2 (rdalo) Elegir w2 (rdalo) cuando la clase verdadera es w1 (salmn) El salmn es un pescado ms caro que el rdalo. Supongamos que:

Si eliges w1 cuando la clase verdadera es w1 has detectado un salmn. El costo de procesamiento del sistema es de 11= 1 unidad monetaria

Si eliges w1 cuando la clase verdadera es w2 proporcionas un producto de peor calidad de la especificada y eso cuesta en sanciones 12= 11 unidades monetarias.

Si eliges w2 cuando la clase verdadera es w1 proporcionas un producto de mayor calidad de la necesaria y eso cuesta 21= 10 unidades monetarias.

Si eliges w2 cuando la clase verdadera es w2 has detectado un rdalo. El costo de procesamiento del sistema es de 22=1 unidad monetaria

Qu elegiras ahora w1 o w2 para X=x1, X=x2 y X=x3 ?



Fernando Prez Nava

DBR:Motivacin (2) Con la notacin utilizada ij es el costo de

elegir la clase wi cuando la verdadera es wj:

Una regla que parece lgica es elegir la clase que produzca el menor costo

El costo relativo de esta regla es 93/20 (mnimo sobre H)

4 5 2

1 6 2

4/20 5/20 2/201/20 6/20 2/20

Frecuencias absolutas

Frecuencias relativas

x1 x2 x3

x1 x2 x3

Decisin. Naranja:Salmn, Violeta:Rdalo

w1

w2

w1

w2

Costo relativos: Amarillo: costos mnimos

14+111=15 15+116=71 12+112=2411+104=41 16+105=56 12+102=22

Costos absolutos. Amarillo: costos mnimos

x1 x2 x3Elijo w

1

Elijo w2

w1

Elijow

2

11=1 12=1121=10 22=1

Clase Verdaderaw

1 w

2

14/20+111/20=15/20 15/20+116/20=71/20 12/20+112/20=24/2011/20+104/20=41/20 16/20+105/20=56/20 12/20+102/20=22/20

x1 x2 x3Elijo w

1

Elijo w2



Fernando Prez Nava

DBR:Motivacin (3) A que se aproxima la tabla de costos relativos cuando el nmero

de muestras tiende a infinito?

Por tanto en el caso ideal de un nmero infinito de muestras la relacin entre frecuencias relativas y probabilidades sugiere utilizar: Elegir w1 si 11 P(x, w1) + 12 P(x, w2) < 21 P(x, w1) + 22 P(x, w2) Elegir w2 si 21 P(x, w1) + 22 P(x, w2) < 11 P(x, w1) + 12 P(x, w2)

Costo medio

11P(x1,w1)+12P(x1,w2) 11P(x2,w1)+12P(x2,w2) 11P(x1,w1)+12P(x1,w2)21P(x1,w1)+22P(x1,w2) 21P(x1,w1)+22P(x1,w2) 21P(x1,w1)+22P(x1,w2)

x1 x2 x3

Elijo w1

Elijo w2

Costo relativos: Amarillo: costos mnimos

14/20+111/20=15/20 15/20+116/20=71/20 12/20+112/20=24/2011/20+104/20=41/20 16/20+105/20=56/20 12/20+102/20=22/20

x1 x2 x3

Elijo w1

Elijo w2



Fernando Prez Nava

DBR: Motivacin (4)

La intuicin es correcta. La regla: Elegir w1 si 11 P(x, w1) + 12 P(x, w2) < 21 P(x, w1) + 22 P(x, w2) Elegir w2 si 21 P(x, w1) + 22 P(x, w2) < 11 P(x, w1) + 12 P(x, w2)

es ptima La regla se puede escribir dividiendo por P(x) como:

Elegir w1 si 11 P(w1|x) + 12 P(w2|x) < 21 P(w1|x) + 22 P(w2|x) Elegir w2 si 21 P(w1|x) + 22 P(w2|x) < 11 P(w1|x) + 12 P(w2|x)

Se suele escribir: R(w1 |x)= 11 P(w1|x) + 12 P(w2|x)R(w2|x)= 21 P(w1|x) + 22 P(w2|x)

a R(wi |x) se le llama riesgo de elegir wi dado x e indica el costo de elegir wi tras haber observado el valor x

entonces, la regla ptima consiste en elegir la clase con menor costo tras haber observado el valor x



Fernando Prez Nava

DBR: Enfoque formal (1)

Informacin disponible: Clases: wi, i=1...c Caractersticas : X variable aleatoria multidimensional. Probabilidades: P(wi), p(x | wi), i=1...c Mediante la Regla de Bayes:

Acciones:i, i=1...c; i = Elegir wi Riesgos: i,j = (i |wj) i=1...c, j=1...c. Indica el riesgo de elegir wi

cuando la verdadera clase es wj

Funcin de riesgo dado un valor de x:ci

c

jjjii ,...1)|P()|()|R(

1==

=

xx ww

=

===

c

iii

iii ppcip

p1

)P()|()(con...1,)()P()|()|P( wwwww xx

x

xx



Fernando Prez Nava

DBR: Enfoque formal (2)

Regla de decisin bayesiana (ptima):

Elegir i si R(i| x) R(j| x) ij Esto es, elegir la clase con menor riesgo dado el valor de x

Propiedad: Hace mnimo el riesgo total:

= xxxx d )()|)(R( pR



Fernando Prez Nava

Clasificadores y su Representacin

Definicin formal de Clasificador Mecanismo de eleccin entre las distintas clases de un problema

de R.P. Representacin

Se suele representar por medio de un conjunto de funciones discriminantes gi(x). De esta forma el clasificador asigna el vector de caractersticas x a la clase wi si gi(x) gj(x) para todo ij.

x1

x2.

.

.

xd

g1

g2.

.

.

gc

g1(x)g2(x)

.

.

.

gc(x)

max (x)

Entrada Clculo de las Funciones Discriminantes Selector de Mximo Decisin

Esquema de un clasificador genrico

xVector deCaractersticas



Fernando Prez Nava

Funciones Discriminantes y Regiones de Decisin

Ejemplos de funciones discriminantes: Caso Bayesiano: gi(x)=P(wi|x) Caso Bayesiano con riesgo: gi(x)=-R(i|x)

o alguna expresin equivalente como: gi(x)=ln (p(x|wi) ) + ln (P(wi)) para el caso Bayesiano.

Regiones de decisin Todo clasificador divide el espacio de caractersticas en regiones

de decisin Ri donde se elige la clase i. La frontera entre dos regiones de decisin de llama frontera de decisin.

Utilizando las funciones discriminante las regiones de decisin se escriben para cada clase wi como Ri={x/gi(x) gj(x) ij}

Si Ri son Rj contiguas entonces la frontera de decisin es la interseccin de las dos regiones RiRj={x/gi(x)=gj(x)}.



Fernando Prez Nava

Recordatorio de Probabilidad (5)Variable Aleatoria Normal

La normal es la variable aleatoria continua ms importante. Cuando hay una nica variable se llama normal unidimensional,

cuando hay varias variables que se distribuyen de forma normal ala distribucin conjunta se la llama normal multidimensional

La normal unidimensional N(,) Funcin de densidad: Algunas propiedades

Su valor medio E(X) es igual a Su varianza es igual a V(X)=

0,2

1)( 22)(

21

2>=

pi

x

exp

N(-3,2) N(0,1) N(3,0.5)Normal unidimensional. Representacin grfica



Fernando Prez Nava

Recordatorio de Probabilidad (6) Independencia

Dos variables X e Y son independientes si conocer una no proporciona informacin sobre la otra, es decir:

Esperanza de una variable aleatoria. Nos informa del valor medio de la variable:

En el caso multidimensional es un vector: Varianza y covarianza de variables aleatorias.

La varianza es una medida de dispersin: La covarianza es una medida de relacin:

En el caso multidimensional se tiene la matriz de covarianzas:

=

-

)()E( dxxpxX

=

-

2 )())E(()V( dxxpXxX

=

-

),())E(())E((),Cov( dxdyyxpYyXxYX

)()(),()()|( ypxpyxpxpyxp ==

= xxxX dp )()E(

= xxxxxxX dp )())E(())E(()Cov( '



Fernando Prez Nava

Recordatorio de Probabilidad (7) La normal multivariante es la distribucin conjunta de varias variables

normales. Funcin de densidad N(,)

Propiedades Su valor medio es ahora un vector E(X)= = (1, 2,..., d)T con i =E(Xi) La dispersin y relacin entre las variables se refleja en la matriz de

covarianzas =E( (X- ) (X- )T ) = (ij) con ij = E((Xi- i)(Xj- j)) En particular los elementos de la diagonal de la matriz , ii = E((Xi- i)2) son

iguales a la varianza de la variable Xi Los elementos fuera de la diagonal ij miden la covarianza entre las variables Xi

y XjUna covarianza positiva indica que cuando crece Xi crece XjUna covarianza cero indica que Xi es independiente de XjUna covarianza negativa indica que cuando crece Xi decrece Xj

0)|(| positiva definida y simtricaelementos, x de matriz

,

,

)2(1)( )()(2

1

2/12/

1T

>

=

ddep

d

d

Rxx

xx

pi



Fernando Prez Nava

Regiones de Decisin: El caso Normal (1) Estudiaremos las funciones discriminantes y fronteras de

decisin que aparecen cuando la distribucin de las caractersticas en cada clase es normal multidimensional, es decir: p(x|wi)~N(i ,i )

Primer caso: Las matrices de covarianzas de todas las clases son iguales,

diagonales y todos los elementos de la diagonal son iguales.i =2I , donde I es la matriz identidad.

Esto significa que dentro de cada clase todas las variables son independientes y tienen la misma varianza 2

La frontera de decisin es lineal y perpendicular a la recta que une las medias de las dos clases

))P(ln(2

1

1)(

T20

2

0T

iiii

ii

iii

a

ag

w+=

=

+=

a

xax

aaa

aa

x

a

xxa

T2

2

2

0

0T

)P()P(ln)(

21

0)(

=

+=

=

=

ji

ji

ji

w

w

R2

R1

1

2

Funcin discriminante Superficie de decisin Representacin Grfica



Fernando Prez Nava

Segundo caso: Las matrices de covarianzas de todas las clases son iguales, esto

es: i = con una matriz comn.

La frontera de decisin es lineal pero en general no es perpendicular a la recta que une las medias de las dos clases

Tercer caso: Las matrices de covarianzas son distintas.

Las fronteras de decisin son cudricas

Regiones de Decisin: El caso Normal (2)

))P(ln(21

)(

1T0

10

T

iiii

ii

iii

a

ag

w+=

=

+=

a

xax

ddd

x

ddaxxa

+=

==

=

)P()P(ln1)(

21

,

0)(

21T0

10

T

ji

ji

ji

w

w R1

R21

2

Funcin discriminante Superficie de decisin Representacin Grfica

))P(ln(||ln'

,

)( TT

iiiiii

iiiii

iiii

a

ag

w++=

==

++=

11

0

11

0

2

1

2

1

2

1

aA

xaxAxx

R1

R1 R2R1

R1R1

R1R1

R2 R2

R2

R2R2

R1

Funcin discriminante Representacin Grfica



Fernando Prez Nava

Resumiendo... Las buenas noticias;

Cuando se conoce la estructura de probabilidad del problema:P(wi), p(x|wi)

siempre se puede encontrar el clasificador ptimo (clasificadorbayesiano):

Las malas noticias: En prcticamente ningn problema prctico se conoce la estructura

de probabilidad del problema. Qu hacer entonces? Dos ideas:

Intentar estimar las probabilidades P(wi), p(x|wi) a partir de un conjunto de entrenamiento. Estimar P(wi) con precisin es fcil. Estimar p(x|wi) es un problema difcil.

Olvidarnos del clasificador bayesiano e introducir otros criterios (por ejemplo geomtricos) con la esperanza de obtener un buen clasificador aunque no sea ptimo.

Elegir wi si P(wi | x) P(wj | x) ijp(x | wi)P(wi) p(x | wj)P(wj) ij



Fernando Prez Nava

El mapa del RP Estadstico

Densidades condicionales

en cada clase p(x|wi)

Aprendizaje Supervisado

Tcnicas Paramtricas

Tcnicas No Paramtricas

Estimacin Paramtrica

Clsica

Estimacin Bayesiana

Estimacin no

ParamtricaClsica

Construccin de Fronterasde Decisin

Conocidas

Desconocidas

DecisinBayesiana

Aprendizajeno Supervisado

Tcnicas Paramtricas

Tcnicas No Paramtricas

Estimacin enmezclas

Anlisis deAgrupamientos

TEMA 2

TEMA 3

TEMAS 4,5

TEMA 8

Documents

Reconocimiento Patrones Cap2