Combinación de Clasificadores

Reconocimiento de Patrones

2003

Basado en notas de curso del Prof. Josef Kittler

Contenido:

• Introducción

• Diferentes enfoques o aproximaciones a la combinación de clasificadores

• Estratégias de combinación

• Comparación experimental

• Conclusiones

Introducción

• Algunas razones de porque combinar clasificadores:– Disponemos de clasificadores distintos trabajando en

distintos contexto y con representaciones o descripciones distintas del mismo problema. Ej: Identificación de una persona a través de su voz, cara, firma.

– Disponemos de conjuntos de entrenamiento distintos tomados en tiempos distintos o con atributos distintos.

Introducción

– Clasificadores distintos entrenados con los mismos datos pueden tener diferente performance global y local. Cada clasificador tiene su región del espacio de caracteristicas donde es el “mejor”.

– Algunos clasificadores como las redes neuronales muestran resultados distintos con las distintas inicializaciones debido a lo aleatorio del procedimiento de entrenamiento.

Introducción

• Resumiendo: existe una diversidad de diseños de clasificadores

• Objetivo: – En el pasado: encontrar el “mejor” clasificador.– En el presente: sacar provecho de la diversidad utilizar

distintos clasificadores para obtener mayor eficiencia y precisión. Clasificadores distintos se equivocan en muestras distintas.

• Especialmente útiles si los clasificadores individuales son independientes.

Esquemas de combinación• De acuerdo a su arquitectura:

– Paralela: Se seleccionan las salidas de los clasificadores individuales o se pesan antes de ser combinados.

– Cascada o combinación serie: se invocan los distintos clasificadores en forma secuencial. Primero se pasa por los más baratos y menos costosos y luego se refina.

– Jerárquica: se combinan los clasificadores en una forma estructurada como la de los árboles de decisión. Cada nodo se asocia con un clasificador complejo (muy eficiente y flexible)

Estrategías de combinación o fusión

• Existe consenso entre los investigadores que la combinación de clasificadores mejora la precisión. Esta mejora depende fundamentalmente de la diversidad de los clasificadores y en segundo término de la estrategia de fusión. De todas formas la elección apropiada de la estrategia puede mejorar el desempeño del conjunto.

Estrategías de combinación • Promedio• mediana• Mínimo• máximo• Mayoría de Votos: Se asigna la clase que obtuvo

más votos de acuerdo a la decisión de los clasificadores individuales.

• Reglas de combinación basadas en la suma y el producto

Enfoques

• Multiples clasificadores que utilizan la misma representación. Por ejemplo todos estiman la p.d.f.

• Multiples clasificadores cada uno usando una representación distinta.

• Multiples clasificadores, cada uno especializado en una región del espacio de características.

• Clasificadores en varias etapas. Se usa la salida de un clasificador como características para la próxima etapa.

Igual representación

• Ej: batería de clasificadores k-NN cada uno con distinto k. Redes neuronales con distinta inicialización, conjuntos de entrenamiento.

• Supongamos:

)/(max1

)/(max)/(

..1

..1

xwPe

xwPxwP

imi

B

imi

s

• Cada uno de los N clasificadores estima la probabilidad a posteriori como:

j : es el error de estimación del clasificador j-esimo

• ¿Que pasa con la probabilidad de error si clasificamos utilizando la salida de N clasificadores?

)/()/()/(ˆ xwxwPxwP ijii

• Supongamos: • Promediamos la salida de los N clasificadores.• El error de estimación es insesgado, con media

nula y varianza e2 .

• Este estimador es insesgado y su varianza se reduce en N.

N

jii xwP

NxwP

1

)/(ˆ1)/(

N

xwPxwPE eii

22)/()/(

¿Que pasa con la Pe?

• La reducción de la varianza impacta la probabilidad de error.

• Para saber cuanto, tenemos que conocer cual es la probabilidad de que el sistema de RP realice un error que exceda el error de bayes. Esto ocurre cuando una clase wi ws al ser estimada tiene mayor probabilidad a posteriori.

jixwPxwP ji ,0)/(ˆ)/(ˆ 0)/()/()/()/( xwxwPxwxwP jjii

)/()/()/()/( xwPxwPxwxw ijji

•Asumirimos que el error de estimación tiene distribución gaussiana con media nula y varianza 2.

•La diferencia tiene distribución gaussiana media nula y varianza 2 2

• Solo las clases wk cuya probabilidad a posteriori es comparable a P(ws/x) contribuyen con probabilidad no despreciable.

m

sii

m

jjie

m

sijjiwi

jiji

PQxP

PQxP

PQxP

,1 1,

,1,

,,

)()(

)()(

)()(

Ps,k>0 pequeño

Pj,k>0 jk,s Qjk1

• El término determinante es Qsk

• El error promedio adicional al de Bayes va a ser:

dxxpxPe e )()(

• Cada probabilidad Qij depende fuertemente de la varianza del error.

• Si trabajamos con N clasificadores (expertos) la varianza se reduce en un factor de N.

• Las mejoras solo se logran en la cercanía de las fronteras de decisión (donde la probabilidad de error es mayor).

• Las mejoras locales se ven diluidas por el promediado en regiones grandes.

• Toda mejora es bienvenida especialmente cuando se está trabajando cerca del 100%

Otras reglas de combinación

• Se obtienen reduciones similares en la varianza del error utilizando reglas del tipo:

max, min y mediana.• Se puede ver que la ganancia depende del número

de expertos, la función distribución del error y del orden de la función de ordenamiento.

• Aunque las ganancias no son tan importantes comparadas con la del promediador estas reglas de combinación son más robustas a outliers.

• Si los estimadores tienen diferente varianza la regla de combinación tiene que tenerlo en cuenta,

Por Ej:

N

ji

jN

j j

i xwPxwP1

2

12

)/(ˆ11

1)/(

Representaciones diferentesSi Suponemos:

1. Independencia:

2. Las probabilidades a posteriori no se desvian substancialmente de las probabilidades a priori:

R

ikkRk xwPwPRxxxwP1

21 )/()()1()..../(

R

ikkR

Rk xwPwPxxxwP1

)1(21 )/()()..../(

Comentarios sobre las hipótesis

• En algunos casos estas hipótesis son válidas

• En otros, son una buena aproximación de trabajo

• Estan implicitas en todos los esquemas de combinación de clasificadores existentes.

Estrategías de combinación

• Regla del máximo:

• Regla del mínimo:

• Regla de la mediana:

)/(maxmax 11 ikRi

mk xwP

)/(minmax 11 ikRi

mk xwP

)/(max 11 ikRi

mk xwPmediana

Ejemplo-Aplicación

• Problema de test: reconocimiento de caracteres

• Se usan 4 clasificadores:– Gaussiano– Red neuronal– HMM (Hidden Markov Model)– Clasificador estructural

Desempeño individual

Clasificador Desempeño

Estructural 90.85%

Gaussiano 93.93%

Red Neuronal 93.2%

HMM 94.77%

Desempeño combinaciónRegla de combinación Desempeño

Voto por mayoria 97.96%

Regla de la suma 98.05%

Regla del máximo 93.93%

Regla del minimo 86.00%

Regla del producto 84.69%

Regla de la mediana 98.19%

Comentarios

• Las reglas del producto y el mínimo tienen desempeño similar y son peores que el mejor clasificador individual.

• Los mejores resultados se obtienen con el promedio y la mediana

• El de voto por mayoria tiene un desempeño cercano a estos últimos.

• La regla del maximo tiene un comportamiento mejor que cualquiera de los clasificadores individuales.

Conclusiones

• Se puede reducir el error de cada clasificador individual utilizando combinación de clasificadores

• Los esquemas basados en un regla de suma tienen mejor desempeño que su contraparte de producto. Esto es consecuencia directa de la menor sensibilidad frente a los errores de esta regla. (Demostración Kittler)