A implementação de um linear, binário SVM (support vector machine)

Question

Eu quero implementar um simples classificador SVM, em caso de alta-dimensional de dados binários (texto), para o qual eu acho uma SVM linear simples é o melhor.A razão para a implementação de mim é basicamente o que eu precisava para aprender como ele funciona, assim, a utilizar uma biblioteca não é o que eu quero.

O problema é que a maioria dos tutoriais de ir até uma equação que pode ser resolvido como um "quadrática problema", mas eles nunca mostram um algoritmo real!Então, você poderia me apontar para uma forma muito simples de implementação que eu poderia estudar, ou (melhor) para um tutorial que vai todo o caminho para os detalhes de implementação?

Muito obrigado!

Answer 1

Alguns pseudocódigo para o Sequential Minimal Optimization (SMO), o método pode ser encontrado neste papel por John C.Platt: Treinamento rápido de Máquinas de Vetor de Suporte usando Sequencial Mínima de Otimização.Há também uma implementação em Java do algoritmo SMO, que é desenvolvido para a pesquisa e o propósito educativo (SVM-JAVA).

Outros métodos mais comumente utilizados para resolver o QP problema de otimização incluem:

• constrangido, conjugado gradientes
• métodos de ponto interior
• active conjunto de métodos

Mas esteja ciente de que algum tipo de conhecimento matemático é necessário para entender essas coisas (multiplicadores de Lagrange, Karush–Kuhn–Tucker, condições, etc.).

Answer 2

Você está interessado em usar kernels ou não? Sem kernels, a melhor maneira de resolver esses tipos de problemas de otimização é através de várias formas de ascendência de gradiente estocástica. Uma boa versão é descrita em http://ttic.uchicago.edu/~shai/papers/shalevsisr07.pdf E isso tem um algoritmo explícito.

O algoritmo explícito não funciona com kernels, mas pode ser modificado; No entanto, seria mais complexo, tanto em termos de complexidade de código quanto de tempo de execução.

Answer 3

Dê uma olhada no Liblinear e no SVM não linear no LibSVM

Answer 4

O documento a seguir "Pegasos: Solucionador sub-gradiente estimado primal para SVM" O topo da página 11 descreve o algoritmo Pegasos também para kernels. http://ttic.uchicago.edu/~nati/publications/pegasosmpb.pdf

Parece ser um híbrido de descida de coordenadas e sub -graduação. Além disso, a linha 6 do algoritmo está errada. No predicado, a segunda aparição de y_i_t deve ser substituída por y_j.