Nichtlineare SVM-Klassifizierung mit RBF-Kernel

8

Ich implementiere einen nichtlinearen SVM-Klassifikator mit RBF-Kernel. Mir wurde gesagt, dass der einzige Unterschied zu einer normalen SVM darin bestand, dass ich das Punktprodukt einfach durch eine Kernelfunktion ersetzen musste: Ich weiß, wie eine normale lineare SVM funktioniert, dh nachdem ich das quadratische Optimierungsproblem (doppelte Aufgabe) gelöst habe, berechne ich die optimale Teilungshyperebene als und der Versatz der Hyperebene , wobei eine Liste meiner Trainingsvektoren ist, ihre jeweiligen Bezeichnungen sind ( ),w=iSVhiyixib=1

K(xi,xj)=exp(||xixj||22σ2)
w=iSVhiyixi
b=1|SV|iSV(yij=1N(hjyjxjTxi))
xyyi{1,1}h sind die Lagrange-Koeffizienten und ist ein Satz von Unterstützungsvektoren. Danach kann ich und alleine verwenden, um einfach zu klassifizieren: .SVwbcx=sign(wTx+b)

Ich glaube jedoch nicht, dass ich so etwas mit einem RBF-Kernel machen kann. Ich fand einige Materialien, die darauf hindeuten, dass . Das würde es einfach machen. Trotzdem glaube ich nicht, dass eine solche Zerlegung für diesen Kernel existiert und sie wird nirgendwo erwähnt. Ist die Situation so, dass alle Unterstützungsvektoren für die Klassifizierung benötigt werden? Wenn ja, wie klassifiziere ich in diesem Fall?K(x,y)=ϕ(x)ϕ(y)

Jan Hadáček
quelle
Keine vollständige Antwort, aber ich hatte diese Folien bei uni: patterns.enm.bris.ac.uk/files/lecture10-2010.pdf
Tristan

Antworten:

19

Lassen Sie Ihren Eingabebereich darstellen, dh den Bereich, in dem sich Ihre Datenpunkte befinden. Stellen Sie sich eine Funktion so vor, dass sie einen Punkt aus Ihrem Eingabebereich entnimmt und einem Punkt in zuordnet . Nehmen wir nun an, wir haben alle Ihre Datenpunkte von auf diesen neuen Bereich abgebildet . Wenn Sie nun versuchen, das normale lineare svm in diesem neuen Raum anstelle von zu lösen , werden Sie feststellen, dass alle früheren Arbeiten einfach gleich aussehen, außer dass alle Punkte als dargestellt werden ΦXΦ:XFXFXFFXxiΦ(xi)und anstatt (Punktprodukt) zu verwenden, das das natürliche innere Produkt für den euklidischen Raum ist, ersetzen wir es durch das das natürliche innere Produkt im neuen Raum darstellt . Am Ende würde Ihr so aussehen:xTyΦ(x),Φ(y)Fw

w=iSVhiyiΦ(xi)

und daher

w,Φ(x)=iSVhiyiΦ(xi),Φ(x)

In ähnlicher Weise ist

b=1|SV|iSV(yij=1N(hjyjΦ(xj),Φ(xi)))

und Ihre Klassifizierungsregel sieht folgendermaßen aus: .cx=sign(w,Φ(x)+b)

So weit so gut, es gibt nichts Neues, da wir die normale lineare SVM einfach auf einen anderen Raum angewendet haben. Der magische Teil ist jedoch dieser -

Nehmen wir an, es gibt eine Funktion so dass . Dann können wir alle obigen Punktprodukte durch ersetzen . Ein solches wird als Kernelfunktion bezeichnet. k ( x i , x j ) = Φ ( x i ) , Φ ( x j ) k ( x i , x j ) kk:X×XRk(xi,xj)=Φ(xi),Φ(xj)k(xi,xj)k

wb

w,Φ(x)=iSVhiyik(xi,x)
b=1|SV|iSV(yij=1N(hjyjk(xj,xi)))

Für welche Kernelfunktionen gilt die obige Ersetzung? Nun, das ist eine etwas komplizierte Frage, und Sie möchten vielleicht richtiges Lesematerial aufnehmen, um diese Implikationen zu verstehen. Ich möchte jedoch nur hinzufügen, dass das oben Gesagte für den RBF-Kernel gilt.

wxw

hiFXΦkΦ

maxihii,jyiyjhihjk(xi,xj)subject to : iyihi=0,hi0
TenaliRaman
quelle
@ JanHadáček Gern geschehen! Gut zu wissen, dass meine Antwort verständlich ist, ich hatte Angst, dass sie zu verdichtet sein könnte :-)
TenaliRaman
Sehr schöne Erklärung
Londoner Typ