LPBoost

El algoritmo de potenciación por programación lineal ( LPBoost ) es un clasificador supervisado perteneciente a la familia de clasificadores boosting . LPBoost maximiza el margen entre muestras de entrenamiento de diferentes clases y, por lo tanto, también pertenece a la clase de algoritmos de clasificación por margen .

Consideremos una función de clasificación.${\displaystyle f:{\mathcal {X}}\to \{-1,1\},}$ que clasifica muestras de un espacio${\displaystyle {\mathcal {X}}}$en una de dos clases, etiquetadas como 1 y -1, respectivamente. LPBoost es un algoritmo para aprender dicha función de clasificación, a partir de un conjunto de ejemplos de entrenamiento con etiquetas de clase conocidas. LPBoost es una técnica de aprendizaje automático especialmente adecuada para la clasificación conjunta y la selección de características en dominios estructurados.

Como en todos los clasificadores de boosting, la función de clasificación final tiene la forma

${\displaystyle f({\boldsymbol {x}})=\sum _{j=1}^{J}\alpha _{j}h_{j}({\boldsymbol {x}}),}$

dónde${\displaystyle \alpha _{j}}$son ponderaciones no negativas para clasificadores débiles${\displaystyle h_{j}:{\mathcal {X}}\to \{-1,1\}}$Cada clasificador débil individual${\displaystyle h_{j}}$Puede que sea solo un poco mejor que el azar, pero la combinación lineal resultante de muchos clasificadores débiles puede funcionar muy bien.

Construcciones de LPBoost${\displaystyle f}$comenzando con un conjunto vacío de clasificadores débiles. Iterativamente, se selecciona un único clasificador débil para agregar al conjunto de clasificadores débiles considerados, se agrega y todos los pesos${\displaystyle {\boldsymbol {\alpha }}}$Se ajustan los clasificadores débiles existentes. Este proceso se repite hasta que no queden clasificadores débiles por añadir.

La propiedad de que todos los pesos del clasificador se ajusten en cada iteración se conoce como propiedad totalmente correctiva . Los métodos de boosting antiguos, como AdaBoost, no poseen esta propiedad y convergen más lentamente.

En términos más generales, dejemos${\displaystyle {\mathcal {H}}=\{h(\cdot$ ;\omega )|\omega \in \Omega \}} sea el conjunto posiblemente infinito de clasificadores débiles, también denominados hipótesis . Una forma de escribir el problema que resuelve LPBoost es como un programa lineal con infinitas variables.

El programa lineal primal de LPBoost, que optimiza sobre el vector de pesos no negativos.${\displaystyle {\boldsymbol {\alpha }}}$, el vector no negativo${\displaystyle {\boldsymbol {\xi }}}$de variables de holgura y el margen${\displaystyle \rho }$es lo siguiente.

${\displaystyle {\begin{array}{cl}{\underset {{\boldsymbol {\alpha }},{\boldsymbol {\xi }},\rho }{\min }}&-\rho +D\sum _{n=1}^{\ell }\xi _{n}\\{\textrm {sb.t.}}&\sum _{\omega \in \Omega }y_{n}\alpha _{\omega }h({\boldsymbol {x}}_{n};\omega )+\xi _{n}\geq \rho ,\qquad n=1,\dots ,\ell ,\\&\sum _{\omega \in \Omega }\alpha _{\omega }=1,\\&\xi _{n}\geq 0,\qquad n=1,\puntos,\ell ,\\&\alpha _{\omega }\geq 0,\qquad \omega \in \Omega ,\\&\rho \in {\mathbb {R} }.\end{array}}}$

Observe los efectos de las variables de holgura.${\displaystyle {\boldsymbol {\xi }}\geq 0}$: su norma uno se penaliza en la función objetivo mediante un factor constante.${\displaystyle D}$, lo cual, si es lo suficientemente pequeño, siempre conduce a un programa lineal factible primal.

Aquí adoptamos la notación de un espacio de parámetros${\displaystyle \Omega }$, de tal manera que para una elección${\displaystyle \omega \in \Omega }$el clasificador débil${\displaystyle h(\cdot$ ;\omega ):{\mathcal {X}}\to \{-1,1\}} está definido de forma única.

Cuando el programa lineal anterior se escribió por primera vez en publicaciones tempranas sobre métodos de boosting, se descartó por intratable debido a la gran cantidad de variables.${\displaystyle {\boldsymbol {\alpha }}}$Solo más tarde se descubrió que tales programas lineales pueden resolverse de manera eficiente utilizando la técnica clásica de generación de columnas .

• Aporte:
  • Conjunto de entrenamiento${\displaystyle X=\{{\boldsymbol {x}}_{1},\dots ,{\boldsymbol {x}}_{\ell }\}}$,${\displaystyle {\boldsymbol {x}}_{i}\in {\mathcal {X}}}$
  • Etiquetas de entrenamiento${\displaystyle Y=\{y_{1},\dots ,y_{\ell }\}}$,${\displaystyle y_{i}\in \{-1,1\}}$
  • Umbral de convergencia${\displaystyle \theta \geq 0}$
• Producción:
  • Función de clasificación${\displaystyle f:{\mathcal {X}}\to \{-1,1\}}$

1. Inicialización
   1. Pesos, uniforme${\displaystyle \lambda _{n}\leftarrow {\frac {1}{\ell }},\quad n=1,\dots ,\ell }$
   2. Borde${\displaystyle \gamma \leftarrow 0}$
   3. Recuento de hipótesis${\displaystyle J\leftarrow 1}$
2. Iterar
   1. ${\displaystyle {\hat {h}}\leftarrow {\underset {\omega \in \Omega }{\textrm {argmax}}}\sum _{n=1}^{\ell }y_{n}h({\boldsymbol {x}}_{n};\omega )\lambda _{n}}$
   2. si${\displaystyle \sum _{n=1}^{\ell }y_{n}{\hat {h}}({\boldsymbol {x}}_{n})\lambda _{n}+\gamma \leq \theta }$entonces
      1. romper
   3. ${\displaystyle h_{J}\leftarrow {\hat {h}}}$
   4. ${\displaystyle J\leftarrow J+1}$
   5. ${\displaystyle ({\boldsymbol {\lambda }},\gamma )\leftarrow }$solución del LPBoost dual
   6. ${\displaystyle {\boldsymbol {\alpha }}\leftarrow }$Multiplicadores de Lagrange de la solución al problema dual LPBoost
3. ${\displaystyle f({\boldsymbol {x}}):={\textrm {sign}}\left(\sum _{j=1}^{J}\alpha _{j}h_{j}({\boldsymbol {x}})\right)}$

Tenga en cuenta que si el umbral de convergencia se establece en${\displaystyle \theta =0}$La solución obtenida es la solución óptima global del programa lineal anterior. En la práctica,${\displaystyle \theta }$Se establece en un valor positivo pequeño para obtener una buena solución rápidamente.

LPBoost es un método de aprendizaje en conjunto y, por lo tanto, no impone la elección de los aprendices base ni el espacio de hipótesis.${\displaystyle {\mathcal {H}}}$Demiriz et al. demostraron que, bajo supuestos poco estrictos, se puede utilizar cualquier modelo base. Si los modelos base son particularmente simples, a menudo se les denomina árboles de decisión .

El número de aprendices base comúnmente utilizados con Boosting en la literatura es grande. Por ejemplo, si${\displaystyle {\mathcal {X}}\subseteq {\mathbb {R} }^{n}}$, un aprendiz base podría ser una máquina de vectores de soporte de margen suave lineal . O incluso más simple, un simple tronco de la forma

${\displaystyle h({\boldsymbol {x}};\omega \in \{1,-1\},p\in \{1,\dots ,n\},t\in {\mathbb {R} }):=\left\{{\begin{array}{cl}\omega &{\textrm {if~}}{\boldsymbol {x}}_{p}\leq t\\-\omega &{\textrm {otherwise}}\end{array}}\right..}$

La decisión anterior plantea interrogantes únicamente a lo largo de una sola dimensión.${\displaystyle p}$del espacio de entrada y simplemente aplica un umbral a la columna correspondiente de la muestra utilizando un umbral constante.${\displaystyle t}$Entonces, puede decidir en cualquier dirección, dependiendo de${\displaystyle \omega }$para una clase positiva o negativa.

Dados los pesos para las muestras de entrenamiento, la construcción del árbol de decisión óptimo de la forma anterior simplemente implica buscar a lo largo de todas las columnas de muestras y determinar${\displaystyle p}$,${\displaystyle t}$y${\displaystyle \omega }$para optimizar la función de ganancia.

• Optimización de la programación lineal mediante generación de columnas , A. Demiriz, KP Bennett y J. Shawe-Taylor. Publicado en 2002 en Kluwer Machine Learning 46, páginas 225–254.