Obliczanie współczynników Lagrange'a dla SVM w Pythonie

10

Próbuję napisać pełną implementację SVM w Pythonie i mam kilka problemów z obliczaniem współczynników Lagrange'a.

Najpierw pozwól mi przeformułować to, co rozumiem z algorytmu, aby upewnić się, że jestem na dobrej drodze.

Jeśli jest zbiorem danych, a jest etykietą klasy , toy i{ - 1 , 1 } x ii , y i ( w T x i + b ) 1x1,x2,...,xnyi{1,1}xi

i,yi(wTxi+b)1

Musimy więc rozwiązać problem optymalizacji

minimalizujw2

z zastrzeżeniem yi(wTxi+b)1

Pod względem współczynników Lagrange'a przekłada się to na znalezienie w , b i α=(α1,α2,...αn)0 i 0 minimalizując:

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

Teraz, ponieważ

Lw=0w=αiyixi
i
Lb=0yiαi=0
możemy przepisać go jako
L(α,w,b)=Q(α)=αi12αiαjyiyjxiTxj
z ograniczeniami
αi0 and αiyi=0

Próbuję więc rozwiązać problem optymalizacji za pomocą Pythona, a jedyny darmowy pakiet, jaki mogłem znaleźć, to cvxopt .

Chciałbym pomóc w rozwiązaniu tego problemu, nie mogłem znaleźć żadnego dobrego przykładu na ten temat i chociaż rozumiem teorię, trudno mi przetłumaczyć to na kod (spodziewałbym się czegoś przeciwnego, ponieważ jestem więcej z podstaw programowania).

Zauważ, że w pewnym momencie będę chciał go rozwiązać, używając jądra ale nie jestem pewien, jakie są implikacje dotyczące rozwiązania tego problemu w kodzie.

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

Jakakolwiek pomoc byłaby bardzo mile widziana, naprawdę jestem zagubiony jak zaimplementować to w Pythonie. Jeśli masz lepszy moduł do rozwiązania problemu optymalizacji, chciałbym o nim również przeczytać.

Charles Menguy
źródło

Odpowiedzi:

4

Wcześniej użyłem cvxopt do implementacji SVM, jednak w Matlabie nie python. Z pewnością spełni twoje zadanie, czy jego wydajność będzie zależeć od tego, do czego go używasz. Najbardziej wydajne maszyny SVM nie korzystają z pakietu solvera QP, wykorzystują niektóre optymalizacje unikalne dla SVM. Wielu używa algorytmu SMO do jego rozwiązania.

LibSVM to pakiet SVM, który wykorzystuje algorytm do wyboru zestawu roboczego przy użyciu informacji drugiego rzędu dla maszyn wsparcia wektorowego . Kod jest open source, jeśli chcesz sprawdzić, jak został zaimplementowany. Ma również interfejs python.

SVMLight to kolejny pakiet, używają innego algorytmu (zobacz ich witrynę w celu uzyskania informacji). Jest to również oprogramowanie typu open source i ma interfejs python.

karenu
źródło
Dzięki za pouczającą odpowiedź (która, jak sądzę, zastępuje moją), i witamy w scicomp!
Aron Ahmadia
Daj +1 ciekawej odpowiedzi i zacząłem patrzeć na twoje świetne linki, które bardzo mi pomagają!
Charles Menguy
2

Ogólną postacią problemu optymalizacji jest program kwadratowy , niezależnie od tego, czy używasz sztuczki jądra, czy jądra liniowego. Wygląda na cvxoptto, że wystarczy do tego, co próbujesz zrobić, ale inni pythonowie również mieli szczęście z OpenOpt .

Aron Ahmadia
źródło
Aron, czy wiesz, czy opakowanie Ipopt Python kiedykolwiek zostało naprawione?
Geoff Oxberry
Jeden ze studentów Davida Ketchesona sprawił, że współpracował z OpenOpt (który może używać go z algorytmem quasi-Newton), ale miał pewne trudności z uruchomieniem stosu OpenOpt w systemie OS X.
Aron Ahmadia