clasificador de margen

En el aprendizaje automático , un clasificador de margen es un clasificador que puede proporcionar una distancia asociada desde el límite de decisión para cada ejemplo. Por ejemplo, si se usa un clasificador lineal (por ejemplo, perceptrón o análisis discriminante lineal ), la distancia (típicamente distancia euclidiana , aunque se pueden usar otros) de un ejemplo desde el hiperplano de separación es el margen de ese ejemplo.

La noción de margen es importante en varios algoritmos de clasificación de aprendizaje automático, ya que puede usarse para limitar el error de generalización del clasificador. Estos límites se muestran frecuentemente utilizando la dimensión VC . De particular importancia es el error de generalización vinculado a los algoritmos de refuerzo y las máquinas de vectores de soporte .

Definición de margen de la máquina vectorial de soporte

Consulte máquinas de vectores de soporte e hiperplano de margen máximo para obtener más detalles.

Margen para impulsar algoritmos

El margen para un algoritmo de refuerzo iterativo dado un conjunto de ejemplos con dos clases se puede definir de la siguiente manera. Al clasificador se le proporciona un par de ejemplo donde es un espacio de dominio y es la etiqueta del ejemplo. Luego, el algoritmo de impulso iterativo selecciona un clasificador en cada iteración donde hay un espacio de posibles clasificadores que predicen valores reales. Luego, esta hipótesis se pondera según lo seleccionado por el algoritmo de refuerzo. En la iteración , el margen de un ejemplo se puede definir como ${\displaystyle (x,y)}$ ${\displaystyle x\in X}$ ${\displaystyle y\in Y=\{-1,+1\}}$ ${\displaystyle h_{j}\in C}$ ${\displaystyle j}$ ${\displaystyle C}$ ${\displaystyle \alpha _{j}\in R}$ ${\displaystyle t}$ ${\displaystyle x}$

${\displaystyle {\frac {y\sum _{j}^{t}\alpha _{j}h_{j}(x)}{\sum |\alpha _{j}|}}.}$

Según esta definición, el margen es positivo si el ejemplo está etiquetado correctamente y negativo si el ejemplo está etiquetado incorrectamente.

Esta definición puede modificarse y no es la única forma de definir el margen para los algoritmos de impulso. Sin embargo, hay razones por las que esta definición puede resultar atractiva. ^[1]

Ejemplos de algoritmos basados ​​en márgenes

Muchos clasificadores pueden dar un margen asociado para cada ejemplo. Sin embargo, sólo algunos clasificadores utilizan información del margen mientras aprenden de un conjunto de datos.

Muchos algoritmos de impulso se basan en la noción de margen para dar ponderación a los ejemplos. Si se utiliza una pérdida convexa (como en AdaBoost , LogitBoost y todos los miembros de la familia de algoritmos AnyBoost), entonces un ejemplo con un margen más alto recibirá menos (o igual) peso que un ejemplo con un margen más bajo. Esto lleva al algoritmo de impulso a centrar el peso en ejemplos de bajo margen. En algoritmos no convexos (por ejemplo, BrownBoost ), el margen todavía dicta la ponderación de un ejemplo, aunque la ponderación no es monótona con respecto al margen. Existen algoritmos de refuerzo que probablemente maximizan el margen mínimo (por ejemplo, consulte ^[2] ).

Las máquinas de vectores de soporte probablemente maximizan el margen del hiperplano de separación. Las máquinas de vectores de soporte que se entrenan utilizando datos ruidosos (no existe una separación perfecta de los datos en el espacio dado) maximizan el margen suave. Puede encontrar más información sobre esto en el artículo sobre la máquina de vectores de soporte .

El algoritmo de perceptrón votado es un algoritmo de maximización de márgenes basado en una aplicación iterativa del algoritmo de perceptrón clásico .

Límites de error de generalización

Una motivación teórica detrás de los clasificadores de margen es que su error de generalización puede estar limitado por parámetros del algoritmo y un término de margen. Un ejemplo de tal límite es el del algoritmo AdaBoost. ^[1] Sea un conjunto de ejemplos muestreados independientemente al azar de una distribución . Supongamos que la dimensión VC del clasificador base subyacente es y . Entonces con probabilidad tenemos el límite ${\displaystyle S}$ ${\displaystyle m}$ ${\displaystyle D}$ ${\displaystyle d}$ ${\displaystyle m\geq d\geq 1}$ ${\displaystyle 1-\delta }$

${\displaystyle P_{D}\left({\frac {y\sum _{j}^{t}\alpha _{j}h_{j}(x)}{\sum |\alpha _{j}|}}\leq 0\right)\leq P_{S}\left({\frac {y\sum _{j}^{t}\alpha _{j}h_{j}(x)}{\sum |\alpha _{j}|}}\leq \theta \right)+O\left({\frac {1}{\sqrt {m}}}{\sqrt {d\log ^{2}(m/d)/\theta ^{2}+\log(1/\delta )}}\right)}$

para todos . ${\displaystyle \theta >0}$

Referencias

1. Robert E. Schapire, Yoav Freund, Peter Bartlett y Wee Sun Lee. (1998) "Impulsar el margen: una nueva explicación de la eficacia de los métodos de votación", The Annals of Statistics , 26(5):1651–1686
2. Manfred Warmuth, Karen Glocer y Gunnar Rätsch. Impulso de algoritmos para maximizar el margen blando. En las Actas de avances en sistemas de procesamiento de información neuronal 20, 2007, págs. 1585-1592.