Implementieren einer linearen, binary SVM (Support-Vektor-Maschine)

Question

Ich mag einen einfachen SVM-Klassifikator, im Fall von hochdimensionalen Binärdaten (Text) implementieren, für die ich denke, ein einfache lineare SVM am besten ist. Der Grund für das es selbst Umsetzung ist im Grunde, dass ich lernen will, wie es funktioniert, so unter Verwendung einer Bibliothek ist nicht das, was ich will.

Das Problem ist, dass die meisten Tutorials zu einer Gleichung nach oben, der als „quadratischem Problem“ gelöst werden kann, aber sie zeigen nie einen tatsächlichen Algorithmus! So könnten Sie mir zeigen entweder auf eine sehr einfache Implementierung ich studieren konnte, oder (besser) zu einem Tutorial, das den ganzen Weg zu den Implementierungsdetails geht?

Vielen Dank!

Answer 1

Einig Pseudo-Code für die Sequential Minimal Optimization (SMO) -Methode kann in diesem Beitrag von John C. Platt zu finden: Fast Ausbildung von Support Vector Machines mit Sequential Minimal Optimization . Es gibt auch eine Java-Implementierung des SMO-Algorithmus, der für die Forschung und pädagogischen Zweck entwickelt wird ( SVM-JAVA ).

Andere Methoden häufig verwendet, um das QP Optimierungsproblem zu lösen ist:

• erzwungener konjugierten Gradienten
• innerer Punkt Methoden
• aktive Satz Methoden

Aber beachten Sie, dass einige mathematische Kenntnisse erforderlich diese Dinge (Lagrange-Multiplikatoren, Karush-Kuhn-Tucker-Bedingungen, etc.) Zu verstehen.

Answer 2

Haben Sie Interesse Kernel oder nicht in Verwendung? Ohne Kern, der beste Weg, diese Art von Optimierungsproblemen zu lösen, ist durch verschiedene Formen der stochastischen Gradientenabfallsaktualisierung. Eine gute Version ist in der http://ttic.uchicago.edu/~shai/papers /ShalevSiSr07.pdf und das hat einen expliziten Algorithmus.

Der explizite Algorithmus nicht mit Kerneln arbeiten, aber geändert werden kann; wäre es jedoch komplexe, sowohl in Bezug auf Code und Laufzeitkomplexität sein.

Answer 3

Hier finden Sie aktuelle liblinear und für nicht lineare SVM ist bei LIBSVM

Answer 4

Das folgende Papier „Pegasos: Primal Geschätzt Unter GRADIENT Solver für SVM“ oben auf der Seite 11 beschreibt den Pegasos-Algorithmus auch für kernels.It kann von http://ttic.uchicago.edu/~nati/Publications/PegasosMPB.pdf

Es scheint ein Hybrid zu sein Abstammungs und Subgradienten Abstieg koordinieren. Auch die Leitung 6 des Algorithmus ist falsch. In dem Prädikat soll der zweite Auftritt von y_i_t mit y_j statt ersetzt werden.