Berechnung der Lagrange-Koeffizienten für SVM in Python

Ich versuche, eine vollständige SVM- Implementierung in Python zu schreiben, und habe einige Probleme bei der Berechnung der Lagrange-Koeffizienten.

Lassen Sie mich zunächst umformulieren, was ich aus dem Algorithmus verstehe, um sicherzustellen, dass ich auf dem richtigen Weg bin.

Wenn ein Datensatz ist und die Klassenbezeichnung von , dann ist$x_1, x_2, ..., x_n$$y_i \in \{-1, 1\}$$x_i$

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

Wir müssen also nur ein Optimierungsproblem lösen, um

minimiere$\|w\|^2$

vorbehaltlich $y_i(w^Tx_i + b) \geq 1$

In Bezug auf Lagrange-Koeffizienten bedeutet dies, dass $w$ , $b$ und $\alpha=(\alpha_1, \alpha_2, ... \alpha_n) \neq0$ und $\geq0$ minimiert wird:

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

Da nun

$$\frac{\partial L}{\partial w}=0 \implies w=\sum \alpha_i y_i x_i$$ und $$\frac{\partial L}{\partial b}=0 \implies \sum y_i \alpha_i = 0$$ wir können es umschreiben als $$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$$ mit Einschränkungen $$\alpha_i \geq 0 \ \text{and} \ \sum \alpha_i y_i = 0$$

Ich versuche also, das Optimierungsproblem mit Python zu lösen, und das einzige kostenlose Paket, das ich finden konnte, heißt cvxopt .

Ich hätte gerne Hilfe, um das zu lösen, ich konnte kein gutes Beispiel dafür finden, und obwohl ich die Theorie verstehe, fällt es mir schwer, sie in Code zu übersetzen (ich hätte das Gegenteil erwartet, da ich es bin mehr aus dem Programmierhintergrund).

Beachten Sie, dass ich es irgendwann mit den Kerneln aber ich bin mir nicht sicher, welche Auswirkungen dies auf die Lösung dieses Problems im Code hat.

$$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)$$

Jede Hilfe wäre sehr dankbar, ich bin wirklich verloren, wie man dies in Python implementiert. Wenn Sie ein besseres Modul zur Lösung des Optimierungsproblems haben, würde ich auch gerne darüber lesen.

Ich habe cvxopt verwendet, um eine SVM zu implementieren, jedoch in Matlab nicht Python. Es wird definitiv Ihren Zweck erfüllen, ob es effizient genug ist, hängt davon ab, wofür Sie es verwenden. Die effizientesten SVMs verwenden kein QP-Solver-Paket, sondern nutzen einige Optimierungen, die nur für SVM gelten. Viele verwenden einen SMO- Algorithmus, um ihn zu lösen.

LibSVM ist ein SVM-Paket, das den Algorithmus bei der Auswahl von Arbeitssätzen unter Verwendung von Informationen zweiter Ordnung für das Training von Support-Vektormaschinen verwendet . Der Code ist Open Source, wenn Sie sich für die Implementierung interessieren. Es hat auch eine Python-Oberfläche.

SVMLight ist ein weiteres Paket, sie verwenden einen anderen Algorithmus (Referenzen finden Sie auf ihrer Website). Es ist auch Open Source und hat eine Python-Oberfläche.

Die allgemeine Form Ihres Optimierungsproblems ist ein quadratisches Programm , unabhängig davon, ob Sie den Kernel-Trick oder einen linearen Kernel verwenden. Es hört sich so an cvxopt, als würde es für das, was Sie versuchen, ausreichen, aber auch andere Pythonauts hier haben Glück mit OpenOpt gehabt .