machine-learning - vectorial - support vector regression
Implementando un SVM lineal, binario(máquina de vectores de soporte) (4)
Quiero implementar un clasificador SVM simple, en el caso de datos binarios de alta dimensión (texto), para lo cual creo que es mejor un SVM lineal simple. La razón para implementarlo yo mismo es básicamente que quiero aprender cómo funciona, por lo que usar una biblioteca no es lo que quiero.
El problema es que la mayoría de los tutoriales suben a una ecuación que se puede resolver como un "problema cuadrático", ¡pero nunca muestran un algoritmo real! Entonces, ¿podría indicarme una implementación muy simple que podría estudiar o (mejor) un tutorial que vaya hasta los detalles de la implementación?
¡Muchas gracias!
¿Está interesado en usar kernels o no? Sin los núcleos, la mejor manera de resolver este tipo de problemas de optimización es a través de varias formas de descenso de gradiente estocástico. Una buena versión se describe en http://ttic.uchicago.edu/~shai/papers/ShalevSiSr07.pdf y tiene un algoritmo explícito.
El algoritmo explícito no funciona con los kernels pero puede modificarse; sin embargo, sería más complejo, tanto en términos de código como de complejidad de tiempo de ejecución.
Eche un vistazo a liblinear y para SVM no lineales en libsvm
El siguiente artículo "Pegasos: Primal Sub-GrAdient SOlver estimado para SVM" en la parte superior de la página 11 describe el algoritmo de Pegasos también para kernels. Se puede descargar desde http://ttic.uchicago.edu/~nati/Publications/PegasosMPB.pdf
Parece ser un híbrido de descenso de coordenadas y subgrado. Además, la línea 6 del algoritmo es incorrecta. En el predicado, la segunda aparición de y_i_t debe reemplazarse con y_j en su lugar.
John C. Platt puede encontrar algunos pseudocódigo para el método de optimización mínima secuencial (SMO) en este documento: Capacitación rápida de máquinas de vectores de soporte mediante la optimización mínima secuencial . También hay una implementación de Java del algoritmo SMO, que se desarrolla con fines educativos y de investigación ( SVM-JAVA ).
Otros métodos comúnmente utilizados para resolver el problema de optimización de QP incluyen:
- gradientes conjugados restringidos
- métodos de punto interior
- métodos de conjunto activo
Pero tenga en cuenta que se necesita algo de conocimiento matemático para comprender esto (multiplicadores de Lagrange, condiciones de Karush-Kuhn-Tucker, etc.).