Berechnung der Lagrange-Koeffizienten für SVM in Python

10

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 istx1,x2,...,xnyi{1,1}xi

i,yi(wTxi+b)1

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

minimierew2

vorbehaltlich yi(wTxi+b)1

In Bezug auf Lagrange-Koeffizienten bedeutet dies, dass w , b und α=(α1,α2,...αn)0 und 0 minimiert wird:

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

Da nun

Lw=0w=αiyixi
und
Lb=0yiαi=0
wir können es umschreiben als
L(α,w,b)=Q(α)=αi12αiαjyiyjxiTxj
mit Einschränkungen
αi0 and αiyi=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(α,w,b)=Q(α)=αi12αiαjyiyjK(xi,xj)

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.

Charles Menguy
quelle

Antworten:

4

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.

Karenu
quelle
Vielen Dank für die informative Antwort (die meiner Meinung nach meine ersetzt) ​​und willkommen bei scicomp!
Aron Ahmadia
+1 interessante Antwort und ich habe angefangen, mir deine tollen Links anzuschauen, die mir sehr helfen!
Charles Menguy
2

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 .

Aron Ahmadia
quelle
Aron, wissen Sie, ob der Ipopt Python-Wrapper jemals repariert wurde?
Geoff Oxberry
Einer von David Ketchesons Schülern brachte es mit OpenOpt zum Laufen (das es mit einem Quasi-Newton-Algorithmus verwenden kann), hatte jedoch einige Schwierigkeiten, den OpenOpt-Stack unter OS X zum
Laufen zu bringen.