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

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 i ∀ i , y i ( w T x i + b ) ≥ $x_1, x_2, ..., x_n$$y_i \in \{-1, 1\}$$x_i$

$$\forall i, y_i(w^Tx_i + b) \geq 1$$

Musimy więc rozwiązać problem optymalizacji

minimalizuj$\|w\|^2$

z zastrzeżeniem $y_i(w^Tx_i + b) \geq 1$

Pod względem współczynników Lagrange'a przekłada się to na znalezienie $w$ , $b$ i $\alpha=(\alpha_1, \alpha_2, ... \alpha_n) \neq0$ i $\geq0$ minimalizując:

$$L(\alpha, w, b) = \frac12 \|w\|^2 - \sum \alpha_i(y_i(w^Tx + b)-1)$$

Teraz, ponieważ

$$\frac{\partial L}{\partial w}=0 \implies w=\sum \alpha_i y_i x_i$$ i $$\frac{\partial L}{\partial b}=0 \implies \sum y_i \alpha_i = 0$$ możemy przepisać go jako $$L(\alpha, w, b) = Q(\alpha)=\sum \alpha_i - \frac12\sum \sum \alpha_i \alpha_j y_i y_j x_i^T x_j$$ z ograniczeniami $$\alpha_i \geq 0 \ \text{and} \ \sum \alpha_i y_i = 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(\alpha, w, b) = Q(\alpha)=\sum \alpha_i - \frac12\sum \sum \alpha_i \alpha_j y_i y_j K(x_i,x_j)$$

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ć.

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.

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 .