La implementación de una lineal, SVM binario (máquina de vectores de soporte)

Question

Quiero poner en práctica un simple clasificador SVM, en el caso de datos de alta dimensión binarios (texto), por lo cual creo que un simple SVM lineal es mejor. La razón de su aplicación a mí mismo es, básicamente, que quiero aprender cómo funciona, así 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 de segundo grado", pero nunca muestran un algoritmo de verdad! Así que ¿podría indicar tanto un aplicación muy sencilla que pude estudiar, o (mejor) a un tutorial que va todo el camino a los detalles de implementación?

Muchas gracias!

Answer 1

Algunos pseudocódigo para la secuencial mínimo de optimización (SMO) método se puede encontrar en este documento por John C. Platt: Formación rápida de máquinas de vectores soporte usando mínimo de optimización secuencial . También hay una implementación de Java del algoritmo SMO, que se desarrolló para la investigación y el propósito de la educación ( SVM-JAVA ).

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

• gradientes conjugados restringida
• métodos de punto interior
• métodos de conjunto activo

Pero tenga en cuenta que se necesita un poco de conocimiento de matemáticas para entender estas cosas (multiplicadores de Lagrange, condiciones Karush-Kuhn-Tucker, etc.).

Answer 2

¿Está usted interesado en el uso de granos o no? Sin granos, la mejor manera de resolver este tipo de problemas de optimización es a través de diversas formas de descenso de gradiente estocástico. Una buena versión se describe en http://ttic.uchicago.edu/~shai/papers /ShalevSiSr07.pdf y que tiene un algoritmo explícito.

El algoritmo explícito no funciona con los núcleos, pero puede ser modificado; Sin embargo, sería más complejo, tanto en términos de tiempo de ejecución de código y complejidad.

Answer 3

Tener un vistazo a LIBLINEAR y de SVM no lineal a libsvm

Answer 4

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

Parece que es un híbrido de coordenadas de descenso y descenso subgradiente. Además, la línea 6 del algoritmo es erróneo. En el predicado la segunda aparición de y_i_t debe ser reemplazado con y_j su lugar.