Clasificador lineal

En el aprendizaje automático , un clasificador lineal toma una decisión de clasificación para cada objeto en función de una combinación lineal de sus características . Estos clasificadores funcionan bien para problemas prácticos como la clasificación de documentos y, de manera más general, para problemas con muchas variables ( características ), alcanzando niveles de precisión comparables a los de los clasificadores no lineales y requiriendo menos tiempo para entrenarlos y usarlos. ^[1]

Definición

Si el vector de características de entrada al clasificador es un vector real , entonces la puntuación de salida es ${\vec {x}}$

y=f({\vec {w}}\cdot {\vec {x}})=f\left(\sum _{j}w_{j}x_{j}\right),

donde es un vector real de pesos y f es una función que convierte el producto escalar de los dos vectores en la salida deseada. (En otras palabras, es una función lineal o de una forma sobre R ). El vector de peso se aprende a partir de un conjunto de muestras de entrenamiento etiquetadas. A menudo, f es una función de umbral , que asigna todos los valores de por encima de un cierto umbral a la primera clase y todos los demás valores a la segunda clase; por ejemplo, ${\vec {w}}$ ${\vec {w}}$ ${\vec {x}}$ ${\vec {w}}$ ${\vec {w}}\cdot {\vec {x}}$

f(\mathbf {x} )={\begin{casos}1&{\text{if }}\ \mathbf {w} ^{T}\cdot \mathbf {x} >\theta ,\\0& {\text{de lo contrario}}\end{casos}}

El superíndice T indica la transposición y es un umbral escalar. Una f más compleja podría indicar la probabilidad de que un elemento pertenezca a una determinada clase. ${\estilo de visualización \theta}$

Para un problema de clasificación de dos clases, se puede visualizar el funcionamiento de un clasificador lineal como la división de un espacio de entrada de alta dimensión con un hiperplano : todos los puntos de un lado del hiperplano se clasifican como "sí", mientras que los demás se clasifican como "no".

Un clasificador lineal se utiliza a menudo en situaciones en las que la velocidad de clasificación es un problema, ya que suele ser el clasificador más rápido, especialmente cuando es escaso. Además, los clasificadores lineales suelen funcionar muy bien cuando el número de dimensiones en es grande, como en la clasificación de documentos , donde cada elemento en es normalmente el número de ocurrencias de una palabra en un documento (véase matriz de términos de documento ). En tales casos, el clasificador debe estar bien regularizado . ${\vec {x}}$ ${\vec {x}}$ ${\vec {x}}$

Modelos generativos vs modelos discriminativos

Existen dos grandes clases de métodos para determinar los parámetros de un clasificador lineal . Pueden ser modelos generativos y discriminativos . ^[2]^[3] Los métodos del primero modelan la distribución de probabilidad conjunta , mientras que los métodos del segundo modelan funciones de densidad condicional . Algunos ejemplos de estos algoritmos son: ${\vec {w}}$ $P({\rm {clase}}|{\vec {x}})$

Análisis discriminante lineal (LDA): asume modelos de densidad condicional gaussianos
Clasificador Bayes ingenuo con modelos de eventos Bernoulli multinomiales o multivariados.

El segundo conjunto de métodos incluye modelos discriminativos , que intentan maximizar la calidad de la salida en un conjunto de entrenamiento . Los términos adicionales en la función de costo de entrenamiento pueden realizar fácilmente la regularización del modelo final. Algunos ejemplos de entrenamiento discriminativo de clasificadores lineales incluyen:

Regresión logística : estimación de máxima verosimilitud asumiendo que el conjunto de entrenamiento observado fue generado por un modelo binomial que depende de la salida del clasificador. ${\vec {w}}$
Perceptrón : un algoritmo que intenta corregir todos los errores encontrados en el conjunto de entrenamiento.
Análisis discriminante lineal de Fisher: un algoritmo (diferente de "LDA") que maximiza la relación entre la dispersión entre clases y la dispersión dentro de las clases, sin ningún otro supuesto. Es, en esencia, un método de reducción de dimensionalidad para la clasificación binaria. ^[4]
Máquina de vectores de soporte : un algoritmo que maximiza el margen entre el hiperplano de decisión y los ejemplos en el conjunto de entrenamiento.

Nota: A pesar de su nombre, LDA no pertenece a la clase de modelos discriminativos de esta taxonomía. Sin embargo, su nombre tiene sentido cuando comparamos LDA con el otro algoritmo principal de reducción de dimensionalidad lineal : el análisis de componentes principales (PCA). LDA es un algoritmo de aprendizaje supervisado que utiliza las etiquetas de los datos, mientras que PCA es un algoritmo de aprendizaje no supervisado que ignora las etiquetas. En resumen, el nombre es un artefacto histórico. ^[5]

El entrenamiento discriminativo suele producir una mayor precisión que el modelado de funciones de densidad condicional ^{[ cita requerida ]} . Sin embargo, el manejo de datos faltantes suele ser más sencillo con los modelos de densidad condicional ^{[ cita requerida ]} .

Todos los algoritmos de clasificación lineal enumerados anteriormente se pueden convertir en algoritmos no lineales que operan en un espacio de entrada diferente , utilizando el truco del núcleo . $\varphi ({\vec {x}})$

Entrenamiento discriminativo

El entrenamiento discriminativo de clasificadores lineales se lleva a cabo habitualmente de forma supervisada , mediante un algoritmo de optimización al que se le proporciona un conjunto de entrenamiento con resultados deseados y una función de pérdida que mide la discrepancia entre los resultados del clasificador y los resultados deseados. De este modo, el algoritmo de aprendizaje resuelve un problema de optimización de la forma ^[1]

{\underset {\mathbf {w} }{\arg \min }}\;R(\mathbf {w} )+C\sum _{i=1}^{N}L(y_{i} ,\mathbf {w} ^{\mathsf {T}}\mathbf {x} _{i})

dónde

$w$ es un vector de parámetros del clasificador,
$L (y i, w T x i)$ es una función de pérdida que mide la discrepancia entre la predicción del clasificador y la salida verdadera $y i$ para el $i$ 'ésimo ejemplo de entrenamiento.
$R (w)$ es una función de regularización que evita que los parámetros sean demasiado grandes (causando sobreajuste ), y
$C$ es una constante escalar (establecida por el usuario del algoritmo de aprendizaje) que controla el equilibrio entre la regularización y la función de pérdida.

Las funciones de pérdida populares incluyen la pérdida de bisagra (para SVM lineales) y la pérdida logarítmica (para regresión logística lineal). Si la función de regularización $R$ es convexa , entonces el problema anterior es convexo . ^[1] Existen muchos algoritmos para resolver tales problemas; los populares para la clasificación lineal incluyen el descenso de gradiente ( estocástico ) , L-BFGS , el descenso de coordenadas y los métodos de Newton .

Véase también

Notas

^ abc Guo-Xun Yuan; Chia-Hua Ho; Chih-Jen Lin (2012). "Avances recientes en la clasificación lineal a gran escala" (PDF) . Proc. IEEE . 100 (9). Archivado (PDF) desde el original el 10 de junio de 2017.
^ T. Mitchell, Clasificadores generativos y discriminativos: Bayes ingenuo y regresión logística. Versión preliminar, 2005
^ AY Ng y MI Jordan. Comparación entre clasificadores discriminativos y generativos: una comparación entre regresión logística y Naive Bayes. en NIPS 14, 2002.
^ RO Duda, PE Hart, DG Stork, "Clasificación de patrones", Wiley, (2001). ISBN 0-471-05669-3
^ Duda, Richard O.; Hart, Peter E.; Stork, David G. (2001). Clasificación de patrones . Una publicación de Wiley-Interscience (segunda edición). Nueva York Chichester Weinheim Brisbane Singapur Toronto: John Wiley & Sons, Inc. p. 117. ISBN 978-0-471-05669-0.

Lectura adicional

Y. Yang, X. Liu, "Un nuevo examen de la categorización de textos", Actas de la Conferencia ACM SIGIR, págs. 42-49, (1999). artículo @ citeseer
R. Herbrich, "Clasificadores de núcleo de aprendizaje: teoría y algoritmos", MIT Press, (2001). ISBN 0-262-08306-X