Calculando coeficientes de Lagrange para SVM em Python

10

Estou tentando escrever uma implementação SVM completa em Python e tenho alguns problemas ao calcular os coeficientes de Lagrange.

Primeiro, deixe-me reformular o que entendo no algoritmo para garantir que estou no caminho certo.

Se x1,x2,...,xn é um conjunto de dados e yi{1,1} é o rótulo da classe xi , em seguida,

i,yi(wTxi+b)1

Então, só precisamos resolver um problema de otimização para

w2

sujeito ayi(wTxi+b)1

Em termos de coeficientes de Lagrange, isso se traduz em encontrar , e e minimizando:wbα=(α1,α2,...αn)00

L(α,w,b)=12w2αi(yi(wTx+b)1)

Agora, como e podemos reescrevê-lo como com restrições

Lw=0w=αiyixi
Lb=0yiαi=0
L(α,w,b)=Q(α)=αi12αiαjyiyjxiTxj
αi0 and αiyi=0

Então, estou tentando resolver o problema de otimização usando o Python, e o único pacote gratuito que consegui encontrar é chamado cvxopt .

Gostaria de alguma ajuda para resolver isso, não consegui encontrar um bom exemplo disso e, embora eu entenda a teoria, estou tendo dificuldades para traduzi-la em código (eu esperava o oposto, pois estou mais de um plano de programação).

Observe que em algum momento eu desejarei resolvê-lo usando Kernels mas não tenho certeza de quais são as implicações em resolver isso no código.

L(α,w,b)=Q(α)=αi12αiαjyiyjK(xi,xj)

Qualquer ajuda seria muito apreciada, estou realmente perdido em como implementar isso em Python. Se você tem um módulo melhor para resolver o problema de otimização, também gostaria de ler sobre isso.

Charles Menguy
fonte

Respostas:

4

Eu usei o cvxopt para implementar um SVM antes, no entanto, no matlab não no python. Definitivamente, ele servirá ao seu propósito, seja eficiente o suficiente, dependendo do que você está usando. Os SVMs mais eficientes não usam um pacote solucionador QP, eles aproveitam algumas otimizações exclusivas do SVM. Muitos usam um algoritmo de estilo SMO para resolvê-lo.

LibSVM é um pacote SVM que usa o algoritmo em Seleção de conjuntos de trabalho usando informações de segunda ordem para máquinas de vetores de suporte de treinamento . O código é de código aberto, se você estiver interessado em ver como é implementado. Ele também possui uma interface python.

O SVMLight é outro pacote, eles usam um algoritmo diferente (consulte o site para referências). Também é de código aberto e possui uma interface python.

karenu
fonte
Obrigado pela resposta informativa (que eu acho que substitui a minha), e bem-vindo ao scicomp!
Aron Ahmadia
+1 resposta interessante e eu comecei a olhar para os seus ótimos links que estão me ajudando muito!
Charles Menguy
2

A forma geral do seu problema de otimização é um programa quadrático , independentemente de você estar usando o truque do kernel ou um kernel linear. Parece que cvxoptserá suficiente para o que você está tentando fazer, mas outros pitonitas aqui também tiveram sorte com o OpenOpt .

Aron Ahmadia
fonte
Aron, você sabe se o wrapper do Ipopt Python foi corrigido?
Geoff Oxberry
Um dos alunos de David Ketcheson tenho que trabalhar com OpenOpt (que pode usá-lo com um algoritmo quasi-Newton), mas teve algumas dificuldades com a obtenção da pilha OpenOpt acontecendo OS X.
Aron Ahmadia