Clasificador lineal

En el aprendizaje automático , un clasificador lineal toma una decisión de clasificación para cada objeto basándose en una combinación lineal de sus características . Una definición más sencilla es decir que un clasificador lineal es aquel cuyos límites de decisión son lineales . Estos clasificadores funcionan bien para problemas prácticos como la clasificación de documentos y, en general, para problemas con muchas variables ( características ), alcanzando niveles de precisión comparables a los de los clasificadores no lineales, a la vez que requieren menos tiempo de entrenamiento y uso. ^{[ 1 ]}

Definición

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

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

dónde ${\vec {w}}$ 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, ${\vec {w}}$ es una función lineal o de una sola forma ${\vec {x}}$ sobre R .) El vector de peso ${\vec {w}}$ se aprende a partir de un conjunto de muestras de entrenamiento etiquetadas. A menudo, f es una función umbral , que asigna todos los valores de ${\vec {w}}\cdot {\vec {x}}$ por encima de un cierto umbral a la primera clase y todos los demás valores a la segunda clase; por ejemplo,

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 transpuesta y $\theta$ es un umbral escalar. Una f más compleja podría dar la probabilidad de que un elemento pertenezca a una clase determinada.

Para un problema de clasificación binaria, se puede visualizar el funcionamiento de un clasificador lineal como la división de un espacio de entrada de alta dimensión mediante 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 usa a menudo en situaciones donde la velocidad de clasificación es un problema, ya que suele ser el clasificador más rápido, especialmente cuando ${\vec {x}}$ es escaso. Además, los clasificadores lineales suelen funcionar muy bien cuando el número de dimensiones en ${\vec {x}}$ es grande, como en la clasificación de documentos , donde cada elemento en ${\vec {x}}$ es típicamente el número de ocurrencias de una palabra en un documento (ver matriz documento-término ). En tales casos, el clasificador debe estar bien regularizado .

Modelos generativos frente a modelos discriminativos

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

Análisis discriminante lineal (LDA): asume modelos de densidad condicional gaussiana.
Clasificador Naive Bayes con modelos de eventos de 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 regularizar fácilmente el modelo final. Ejemplos de entrenamiento discriminativo de clasificadores lineales incluyen:

Regresión logística : estimación de máxima verosimilitud de ${\vec {w}}$ suponiendo que el conjunto de entrenamiento observado fue generado por un modelo binomial que depende de la salida del clasificador.
Perceptrón : un algoritmo que intenta corregir todos los errores encontrados en el conjunto de entrenamiento.
Análisis discriminante lineal de Fisher: un algoritmo (distinto de "LDA") que maximiza la relación entre la dispersión entre clases y la dispersión dentro de las clases, sin ninguna otra suposición. 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 del conjunto de entrenamiento.

Nota: A pesar de su nombre, LDA no pertenece a la clase de modelos discriminativos en esta taxonomía. Sin embargo, su nombre cobra sentido al comparar 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 vestigio histórico. ^{[ 5 ]}

El entrenamiento discriminativo suele ofrecer mayor precisión que el modelado de las funciones de densidad condicional . Sin embargo, el manejo de datos faltantes suele ser más sencillo con los modelos de densidad condicional .

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

Formación discriminativa

El entrenamiento discriminativo de clasificadores lineales generalmente se lleva a cabo de manera supervisada , mediante un algoritmo de optimización que recibe un conjunto de entrenamiento con salidas deseadas y una función de pérdida que mide la discrepancia entre las salidas del clasificador y las salidas deseadas. De esta manera, 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 impide que los parámetros se vuelvan demasiado grandes (lo que provoca 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 más comunes 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 este tipo de problemas; entre los más populares para la clasificación lineal se encuentran el descenso de gradiente ( estocástico ) , L-BFGS , el descenso de coordenadas y los métodos de Newton .

Véase también

Notas

1 2 3 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) del original el 10 de junio de 2017.
↑ T. Mitchell, Clasificadores generativos y discriminativos: Naive Bayes y regresión logística. Versión preliminar, 2005
↑ AY Ng y MI Jordan. Sobre clasificadores discriminativos frente a generativos: una comparación de 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 . Publicación de Wiley-Interscience (Segunda edición). Nueva York Chichester Weinheim Brisbane Singapur Toronto: John Wiley & Sons, Inc. pág. 117. ISBN 978-0-471-05669-0.

Lecturas adicionales

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

[ieee-1] 1 2 3 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) del original el 10 de junio de 2017.

[2] T. Mitchell, Clasificadores generativos y discriminativos: Naive Bayes y regresión logística. Versión preliminar, 2005

[3] AY Ng y MI Jordan. Sobre clasificadores discriminativos frente a generativos: una comparación de regresión logística y Naive Bayes. En NIPS 14, 2002.

[4] RO Duda, PE Hart, DG Stork, "Clasificación de patrones", Wiley, (2001). ISBN 0-471-05669-3

[5] Duda, Richard O.; Hart, Peter E.; Stork, David G. (2001). Clasificación de patrones . Publicación de Wiley-Interscience (Segunda edición). Nueva York Chichester Weinheim Brisbane Singapur Toronto: John Wiley & Sons, Inc. pág. 117. ISBN 978-0-471-05669-0.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]