Impulsar la programación lineal ( LPBoost ) es un clasificador supervisado desde el impulso de la familia de los clasificadores. LPBoost maximiza un margen entre las muestras de entrenamiento de diferentes clases y, por lo tanto, también pertenece a la clase de algoritmos de clasificación supervisada que maximizan los márgenes. Considere una función de clasificación
que clasifica muestras de un espacio en una de dos clases, etiquetadas como 1 y -1, respectivamente. LPBoost es un algoritmo para aprender dicha función de clasificación dado un conjunto de ejemplos de entrenamiento con etiquetas de clase conocidas. LPBoost es una técnica de aprendizaje automático y especialmente adecuada para aplicaciones de clasificación conjunta y selección de características en dominios estructurados.
Descripción general de LPBoost
Como en todos los clasificadores impulsores, la función de clasificación final es de la forma
dónde son ponderaciones no negativas para clasificadores débiles. Cada clasificador débil individual puede ser un poco mejor que aleatorio, pero la combinación lineal resultante de muchos clasificadores débiles puede funcionar muy bien.
Construcciones LPBoost comenzando con un conjunto vacío de clasificadores débiles. Iterativamente, se selecciona, agrega un solo clasificador débil para agregar al conjunto de clasificadores débiles considerados, y todos los pesospara el conjunto actual de clasificadores débiles se ajustan. Esto se repite hasta que no queden clasificadores débiles para agregar.
La propiedad de que todos los pesos de los clasificadores se ajustan en cada iteración se conoce como propiedad totalmente correctiva . Los primeros métodos de refuerzo, como AdaBoost , no tienen esta propiedad y convergen más lentamente.
Programa lineal
De manera más general, dejemos ser el conjunto posiblemente infinito de clasificadores débiles, también denominados hipótesis . Una forma de escribir el problema que LPBoost resuelve es como un programa lineal con infinitas variables.
El programa lineal primario de LPBoost, optimizando sobre el vector de peso no negativo , el vector no negativo de variables de holgura y el margen es el siguiente.
Tenga en cuenta los efectos de las variables de holgura : su norma única está penalizada en la función objetivo por un factor constante , que, si es lo suficientemente pequeño, siempre conduce a un programa lineal factible primario.
Aquí adoptamos la notación de un espacio de parámetros , tal que para una elección el clasificador débil está definido de forma única.
Cuando el programa lineal anterior se escribió por primera vez en las primeras publicaciones sobre métodos de refuerzo, se descartó como intratable debido a la gran cantidad de variables . Solo más tarde se descubrió que esos programas lineales pueden resolverse de manera eficiente utilizando la técnica clásica de generación de columnas .
Generación de columnas para LPBoost
En un programa lineal, una columna corresponde a una variable primaria. La generación de columnas es una técnica para resolver grandes programas lineales. Por lo general, funciona en un problema restringido, tratando solo con un subconjunto de variables. Al generar variables primarias de forma iterativa y bajo demanda, eventualmente se recupera el problema original sin restricciones con todas las variables. Al elegir inteligentemente las columnas para generar el problema, se puede resolver de manera que, al mismo tiempo que se garantiza que la solución obtenida sea óptima para el problema completo original, solo se debe crear una pequeña fracción de columnas.
Problema dual de LPBoost
Las columnas del programa lineal primario corresponden a las filas del programa lineal dual . El programa lineal dual equivalente de LPBoost es el siguiente programa lineal.
Para programas lineales, el valor óptimo del problema primario y dual son iguales. Para los problemas primarios y duales anteriores, el valor óptimo es igual al "margen blando" negativo. El margen suave es el tamaño del margen que separa las instancias de entrenamiento positivas de las negativas menos las variables de holgura positivas que conllevan penalizaciones para las muestras que violan el margen. Por lo tanto, el margen suave puede ser positivo, aunque no todas las muestras están separadas linealmente por la función de clasificación. Este último se denomina "margen duro" o "margen realizado".
Criterio de convergencia
Considere un subconjunto de las restricciones satisfechas en el problema dual. Para cualquier subconjunto finito podemos resolver el programa lineal y así satisfacer todas las restricciones. Si pudiéramos probar que de todas las restricciones que no agregamos al problema dual no se viola ninguna restricción única, habríamos probado que resolver nuestro problema restringido es equivalente a resolver el problema original. Más formalmente, dejemosser el valor de función objetivo óptimo para cualquier instancia restringida. Entonces, podemos formular un problema de búsqueda para la 'restricción más violada' en el espacio del problema original, es decir, encontrar como
Es decir, buscamos el espacio para un solo tocón de decisión maximizando el lado izquierdo de la restricción dual. Si la restricción no puede ser violada por ninguna elección de tope de decisión, ninguna de las restricciones correspondientes puede estar activa en el problema original y el problema restringido es equivalente.
Constante de penalización
El valor positivo de la constante de penalización debe encontrarse utilizando técnicas de selección de modelos . Sin embargo, si elegimos, dónde es el número de muestras de entrenamiento y , luego el nuevo parámetro tiene las siguientes propiedades.
- es un límite superior en la fracción de errores de entrenamiento; eso es, si denota el número de muestras de entrenamiento mal clasificadas, luego .
- es un límite inferior en la fracción de muestras de entrenamiento fuera o en el margen.
Algoritmo
- Aporte:
- Conjunto de entrenamiento ,
- Etiquetas de formación ,
- Umbral de convergencia
- Producción:
- Función de clasificación
- Inicialización
- Pesos, uniforme
- Borde
- Recuento de hipótesis
- Iterar
- Si luego
- rotura
- solución del LPBoost dual
- Multiplicadores lagrangianos de solución al problema dual LPBoost
Tenga en cuenta que si el umbral de convergencia se establece en la solución obtenida es la solución óptima global del programa lineal anterior. En la práctica, se establece en un valor positivo pequeño para obtener una buena solución rápidamente.
Margen realizado
El margen real que separa las muestras de entrenamiento se denomina margen realizado y se define como
El margen realizado puede ser y será normalmente negativo en las primeras iteraciones. Para un espacio de hipótesis que permite seleccionar cualquier muestra individual, como suele ser el caso, el margen realizado eventualmente convergerá a algún valor positivo.
Garantía de convergencia
Si bien se ha demostrado que el algoritmo anterior converge, a diferencia de otras formulaciones de impulso, como AdaBoost y TotalBoost , no hay límites de convergencia conocidos para LPBoost. Sin embargo, en la práctica, se sabe que LPBoost converge rápidamente, a menudo más rápido que otras formulaciones.
Estudiantes de base
LPBoost es un método de aprendizaje conjunto y, por lo tanto, no dicta la elección de los alumnos base, el espacio de hipótesis. Demiriz y col. mostró que bajo supuestos leves, se puede utilizar cualquier alumno básico. Si los aprendices básicos son particularmente sencillos, a menudo se los denomina tocones de decisión .
El número de alumnos básicos que se utilizan comúnmente con Boosting en la literatura es grande. Por ejemplo, si, un alumno básico podría ser una máquina vectorial de soporte de margen suave lineal . O incluso más simple, un simple muñón de la forma
Los tocones de decisión anteriores se ven solo a lo largo de una sola dimensión del espacio de entrada y simplemente establece el umbral de la columna respectiva de la muestra utilizando un umbral constante . Entonces, puede decidir en cualquier dirección, dependiendo de para una clase positiva o negativa.
Dados los pesos de las muestras de entrenamiento, la construcción del muñón de decisión óptimo del formulario anterior simplemente implica buscar a lo largo de todas las columnas de la muestra y determinar , y para optimizar la función de ganancia.
Referencias
- Impulso de programación lineal a través de la generación de columnas , A. Demiriz y KP Bennett y J. Shawe-Taylor. Publicado en 2002 en Kluwer Machine Learning 46, páginas 225–254.