Desarrollo y pruebas de algoritmo Adaboost

El algoritmo Adaboost es un metaclasificador, es decir, obtiene un nuevo clasificador a partir de un conjunto de clasificadores (pool de clasificadores), consiguiendo así un clasificador más eficiente.

La salida del Adaboost es el signo de la suma ponderada de las salidas de cada uno de los clasificadores ante un vector de características xi (puede dar el valor 1 o -1). El cálculo de los coeficientes de ponderación (alfas) se realiza de manera progresiva, haciendo un testeo de los clasificadores con datos de entrenamiento. Se asignan penalizaciones a los clasificadores según el error cometido y dependiendo de ese porcentaje de error se pueden calcular los pesos. Este cálculo de las alfas se calcula en base a la relación entre la suma de los pesos correctos, Wc, y erróneos, We.

-          La función de la salida, Y, para un patrón: 

Siendo “n” el número de clasificadores seleccionados, “α” el coeficiente de ponderación, “x” es el patrón y “k” el resultado de cada unos de los clasificadores seleccionados.

-          Cálculo de los coeficientes de ponderación:

Donde αm>0, debe ser estrictamente positivo.

Testear el código con diferentes probabilidades de error

Dado el código del algoritmo adaboost desarrollado en el que se decidió tomar una tasa de error inicial de 40%, se va a proceder a cambiar la probabilidad de error del primer clasificador del 40% al 30%, para hacer esto se tiene que decrementar el valor de la variable “Tasa_error” de 0.4 a 0.3. Además, se van a realizar incrementos del 5% por cada clasificador, para lo cual, se tiene que multiplicar una vez realizado la simulación de los primeros patrones de cada clasificador multiplicar la variable “Tasa_error” por un valor de 1.05 consiguiendo así incrementar, haciendo que se incremente en un 5%, respecto a la tasa de error anterior consiguiendo así un nuevo valor para la tasa de error.

Para este nuevo código realizado, deberíamos obtener los siguientes resultados. El primer clasificador será evaluado con una tasa de error del 30%, sin embargo, a medida que se van evaluando los siguientes clasificadores, la tasa de error ira aumentando lo que implica que se le está pidiendo una mayor probabilidad de acierto al clasificador. Esto implica que los primeros clasificadores tendrán una valoración mayor, es decir, serán mejores clasificadores, dada la tasa de error, que los últimos clasificadores.

Mostrar para una probabilidad de error dada tratad de mostrar con evoluciona el error total del Adaboost cuando crece el número de clasificadores
 

Para estudiar cómo afecta el número de clasificadores al algoritmo Adaboost se han realizado 30 iteraciones con cada valor de número de clasificadores escogidos. La razón de haber realizado 30 iteraciones con cada valor es para intentar reducir el efecto de la aleatoriedad en la creación de los clasificadores iniciales. De este modo se ha calculado la media para cada caso obteniendo los siguientes resultados.

Nº clasificadores	Media de la tasa de error
5	37%
10	32.33%
15	31.83%
20	29.5%

Se observa como a medida que aumenta el número de clasificadores se reduce la tasa de error del algoritmo. Sin embargo, estamos realizando clasificadores aleatorios, lo que hace muy difícil obtener conclusiones precisas.

     En que se basa el algoritmo Adaboost y cómo funciona el código desarrollado

    Algoritmo Adaboost

La palabra Adaboost, viene de la contracción de “Adaptative boosting” donde el término boosting hace referencia a un tipo de algoritmos cuya finalidad es encontrar una hipotesis fuerte a partir de hipótesis simples y débiles, es decir, un buen clasificador a partir de clasificadores simples y débiles. Por otro lado, el término Adaptative viene de la adaptación de los clasificadores débiles de manera iterativa, de modo que cada nuevo clasificador se enfoca en los datos que fueron erroneamente clasificados por su predecesor, de esta manera el algoritmo se adapta y logra obtener mejores resultados.

El algoritmo, por lo tanto, explicándolo de manera muy general, realiza el siguiente proceso:

Para un patrón de entradas de datos xi, cada clasificador débil hT emite una clasificación, esa clasificación será un 1 o un -1 en función del clasificador y del patrón de datos.

Finalmente, en la salida H(x) se obtendrá el signo de una suma ponderada a partir de la clasificación de los distintos clasificadores, donde:

h1, h2, …, hT denotan los clasificadores seleccionados del conjunto de clasificaciones, es decir, del pool de clasificadores. Las constantes ∝1, ∝2,…,∝𝑇 son las ponderaciones asignadas a la clasificación de cada uno de los clasificadores.

La evolución del algoritmo, funciona de la siguiente manera. En cada iteración necesitamos hacer un ranking de todos los clasificadores, con el fin de seleccionar el mejor de todo el conjunto. En la iteración número T, ya se ha realizado la inclusión de T-1 clasificadores dentro de los escogidos, y necesitamos escoger el siguiente clasificador.

La combinación lineal de los clasificadores actual es:

Y para la próxima ejecución queremos extenderlo a:

En la primera iteración (T=1), (𝑇−1) es cero. Definimos el coste total, o el error total como:

Dado que nuestra intención es escoger el próximo clasificador, reescribimos la expresión como:

Donde:

Durante las próximas iteraciones, el vector 𝑤 (𝑇) representará el peso asociado a cada punto en la prueba de la iteración T. Podemos convertir el sumatorio del error en dos sumas:

Esto significa que el coste total es el coste ponderado de todos los aciertos más el coste ponderado de todos los fallos. Escribiendo el primer sumando como 𝑊𝑐 𝑒−∝𝑇 y el segundo como 𝑊𝑒 𝑒∝𝑇, simplificamos la notación a:

Por lo tanto, para la selección de hm minimizar E es equivalente a minimizar 𝑒∝𝑇𝐸y por ello:

Dado que e^2aT > 0, se puede reescribir la expresión como

Ahora, (𝑊𝑐 + ) es la suma de las ponderaciones de todos los puntos de entrada, pudiéndose tratar como una constante en cada iteración.

Una vez escogido el mejor clasificador de acuerdo a los fallos del clasificador anterior, debemos determinar su ponderación ∝𝑇. Derivando la ecuación anterior e igualando a cero, obtenemos:

De esta manera se puede observar como el calor óptimo de ∝𝑇 es:

Recordando que W es la suma de las ponderaciones podemos reescribir la expresión como:

Donde 𝑒𝑇=𝑊𝑒/𝑊, es el porcentaje de error dada la ponderación de los puntos de entrada.

          Código desarrollado

 

      Aplicarlo a un problema concreto como el de la clasificación de  cruces y rectángulos

Para realizar la clasificación de las cruces y rectángulos, en primer lugar, se tiene que ejecutar el archivo con el cual se consigue la variable x, en la cual se almacenan los valores del área en la primera fila y los valores del perímetro en la segunda fila. Mediante estos dos valores se podrá clasificar las cruces y los rectángulos, en caso de tener un mayor perímetro en la mayoría de los casos se tratará de una cruz, mientras cuanto mayor sea el área se tratará en mayor probabilidad de un rectángulo.

Para la realización de los clasificadores se crean diferentes rectas, con las que se clasificarán las figuras. Los parámetros de la recta son variables para cada clasificador. En caso de que una imagen se encuentre por encima de la recta del clasificador se obtendrá un signo positivo, y por el contrario si se encuentra por debajo se tendrá un signo negativo. Los clasificadores tendrán la siguiente forma:

Hay que tener en cuenta que P es el perímetro de la imagen, mientras que A es el área de la imagen. Para cada clasificador se realizarán tantos patrones como imágenes se tienen. Los valores de a1, a2 y a3 se cambiarán tras calcular todos los signos con todas las imágenes para un clasificador.

En el código desarrollado en primer lugar con el vector x obtenido se comienza un bucle for el cual se repetirá tantas veces como clasificadores se desean tener. En este bucle for se obtendrán las constantes de cada uno de los clasificadores, con lo que se tendrán tantas constantes como número de clasificadores. Tras la obtención del valor se realiza otro bucle for el cual se repetirá tantas veces como patrones se tienen, en este caso son el número de imágenes que se tienen que son 20. Dentro de este bucle for se realiza en primer lugar la obtención de los parámetros perímetro y área de la imagen correspondiente. Obtenidos los parámetros se procede a almacenar el valor que da el clasificador en una matriz, y se obtiene el signo del clasificador y también se almacena. Por último, se representa la recta y se guardan las constantes del clasificador, para posteriormente verlas.

Tras obtener la matriz K se procede a realizar el Adaboost. En primer lugar, se inicializan un conjunto de vectores en los que se irán almacenando los valores que se van obteniendo a lo largo del tiempo. En segundo lugar, se inicializa un bucle for el cual se repite tantas veces como clasificadores se tienen, dentro de este bucle se tendrá otro bucle for el cual se repetirá tantas veces como clasificadores se tienen en el pool, en este pool se almacenan los clasificadores que no se han seleccionado para el cálculo de la alpha correspondiente. Dentro de este último bucle for se recorren cada uno de los patrones dentro del pool y se obtiene la Wc y la We de cada uno de ellos, con esto se calcula la alpha del correspondiente al patrón y se almacena en un vector. Una vez obtenidos los alphas de un clasificador se obtiene el alpha de mayor valor del clasificador y se almacena, en caso de ser 0 o negativo se termina el proceso. Se realiza esto con cada uno de los clasificadores del sistema. Por último, tras obtener las alphas se entra en otro for en el cual se calculará la tasa de error que se obtiene con los clasificadores. El bucle for se repetirá tantas veces como patrones se tienen. Una vez realizado esto se calcula la C para cada clasificador, para ello se hace un sumatorio del valor de alpha multiplicado por el valor de la K correspondiente a ese patrón y ese clasificador, para realizar eso se aplica un bucle for. Se obtiene el signo de la C obtenida y se si este valor es diferente al que debería tener el patrón se suma 1 al error, por último, se divide el error por el número de patrones que se tienen, en este caso las 20 imágenes.

El código desarrollado es el siguiente:

Tras realizarse 30 ejecuciones se ha obtenido una tasa de error media de 28,73%.