Implementación de un SVM binario lineal (máquina de vectores de soporte)

Question

Quiero implementar un clasificador SVM simple, en el caso de datos binarios de gran dimensión (texto), para los cuales creo que una SVM lineal simple es lo mejor. El motivo para implementarlo yo mismo es básicamente que quiero aprender cómo funciona, por lo tanto, no es lo que quiero usar una biblioteca.

El problema es que la mayoría de los tutoriales van a una ecuación que se puede resolver como un "problema cuadrático", ¡pero nunca muestran un algoritmo real! Entonces, ¿podría apuntarme a una implementación muy simple que podría estudiar, o (mejor) a un tutorial que abarque todos los detalles de la implementación?

¡Muchas gracias!

Answer 1

Algunos pseudocódigo para el método secuencial mínimo de optimización (SMO) se puede encontrar en este documento por John C. Platt: Fast Training of Support Vector Machines using Sequential Minimal Optimization. También hay una implementación de Java del algoritmo SMO, que se desarrolla con fines de investigación y educación (SVM-JAVA).

Otros métodos comúnmente utilizados para resolver el problema de optimización QP incluyen:

• gradientes conjugados con restricciones
• métodos de punto interior
• métodos de conjunto activo

Pero tenga en cuenta que algunos conocimientos de matemáticas es necesario para entender esto (multiplicadores de Lagrange, condiciones de Karush-Kuhn-Tucker, etc.).

Answer 2

¿Está interesado en usar granos o no? Sin kernels, la mejor forma de resolver este tipo de problemas de optimización es a través de varias formas de descendencia de gradiente estocástica. 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 núcleos pero se puede modificar; sin embargo, sería más complejo, tanto en términos de código como de complejidad de tiempo de ejecución.

Answer 3

Tenga una mirada en LIBLINEAR y de SVM no lineal a libsvm

Answer 4

El siguiente documento "Pegasos: Primal Solver estimado sub-gradiente de SVM" parte superior de la página 11 describe el algoritmo Pegasos también para kernels.It puede ser descargado de http://ttic.uchicago.edu/~nati/Publications/PegasosMPB.pdf

Parece ser un híbrido de descenso de coordenadas y descenso de subgrado. Además, la línea 6 del algoritmo es incorrecta. En el predicado, la segunda aparición de y_i_t debería reemplazarse con y_j en su lugar.