Effiziente Klassifizierung mitSupport-Vektor-Maschinen

Markus Thom

HauptseminarNeuroinformatik,Universität Ulm, Abteilung Neuroinformatik, SS 2007

Zusammenfassung

Wir stellen eine Methode zur effizienten Klassifizierung mit Support-Vektor-Maschinen vor, die sichbeispielsweise zur Suche von Objekten in Bildern eignet. Dabei wird aus einer gegebenen SVM einereduzierte SVM berechnet, die über eine fest vorgegebene Anzahl von Support-Vektoren verfügt und einebestmögliche Annäherung an die Original-SVM darstellt. Dadurch werden die Vorteile einer Support-Vektor-Maschine wie optimale Generalisierung mit denen eines schnellen Klassifikators kombiniert.

1 Motivation

Support-Vektor-Maschinen (SVMs) wurden bereits erfolgreich in der Gesichts- [4] und Fußgän-gererkennung [3] eingesetzt. Hierbei besteht die Aufgabe darin, auf einem beliebigen Bild alleObjekte einer bestimmten Klasse zu erkennen, und deren Position und Skalierung auszugeben.In der Praxis wird dabei mit Hilfe eines Suchfensters, das inunterschiedlichen Skalierungenüber das zu untersuchende Bild verschoben wird, jeder Ausschnitt durch die SVM klassifiziert.Da mit diesem Vorgehen mehrere zehntausend Ausschnitte proBild untersucht werden müssen,ist es auf aktuellen Maschinen nicht echtzeitfähig.

Aus diesem Grund versucht man, einen Klassifikator mit geringerer Komplexität aus einer ge-gebenen SVM zu berechnen. Man erhält so durch eine Relaxationdes ursprünglichen Problems,nämlich dass die trennende Hyperebene nicht in Abhängigkeit von den Trainingsbeispielen aus-gedrückt werden muss und dass die zugehörigen Gewichte unbeschränkt sein können, eine re-duzierte Support-Vektor-Maschine (RVM). Da die Laufzeit der Klassifikation mit einer SVMlinear in der Anzahl der Support-Vektoren ist, konzentrieren wir uns darauf, diese Anzahl zureduzieren und alle sonstigen Parameter, wie die Wahl des verwendeten Kernels, nicht zu ver-ändern.

Der Rest dieser Ausarbeitung ist wie folgt strukturiert: in Abschnitt 2 wird kurz das Konzeptder SVM erläutert; in Abschnitt 3 wird die Berechnung einer Annäherung einer SVM durcheine RVM beschrieben; in Abschnitt 4 werden Ergebnisse des Verfahrens auf Spielzeugdatenund auf praxisnahen Daten vorgestellt; im letzten Abschnitt 5 werden schließlich aufbauendeVerfahren vorgestellt, durch die eine weitere Verbesserung der Laufzeit erreicht wird.

2 Support-Vektor-Maschinen

Ist eine MengeX =

(x(i),yi)∣

∣

∣i ∈ 1, . . . , l

⊆Rd×±1 von Trainingsdaten aus demEin-

gaberaumRd, versehen mit einerbinären Klassifizierungaus±1 gegeben, berechnet der

Support-Vektor-Maschinen-Trainingsalgorithmus eine Hyperebene mit maximalen Rand, dieX(bestmöglich) in zwei Klassen trennt. Der Algorithmus berechnet dabei Gewichteα1, . . . ,αl ∈R, mit deren Hilfe sich der Normalenvektor der trennenden Hyperebene in Abhängigkeit derTrainingsdatenX als Ψ := ∑l

i=1αix(i) ergibt. Die Vektorenx(i) für die αi 6= 0 gilt heißen dieSupport-Vektorender Support-Vektor-Maschine. Der Algorithmus berechnet außerdem einenSchwellwertθ ∈ R, mit dem zur Klassifizierung die Indikatorfunktion des offenen Halbrau-mes

x∈ Rd∣

∣ 〈x,Ψ〉 > θ

verwendet wird. Hierbei ist〈·, ·〉 : Rd ×R

d → R, (x,y) 7→ xty daskanonische innere Produkt imRd.

Das vom Trainingsalgorithmus zu lösende Optimierungsproblem lässt sich ausschließlich inAbhängigkeit von inneren Produkten im Eingaberaum formulieren; durch den Kernel-Trickwird die Support-Vektor-Maschine nichtlinear. Dazu seiΦ : R

d → F eineMerkmalstransfor-mationin denMerkmalsraumF , welcher für gewöhnlich ein Hilbert-Raum ist, d.h. ein vollstän-diger und mit einem inneren Produkt versehener Vektorraum.Die Funktionκ : R

d ×Rd → R,

(x,y) 7→ 〈Φ(x),Φ(y)〉, die ein inneres Produkt im Merkmalsraum berechnet, wirdKernel ge-nannt. Während der Merkmalsraum höherdimensional als der Eingaberaum oder sogar unend-lichdimensional ist, finden dort keine expliziten Berechnungen statt. Vielmehr wird der Ker-nel benutzt, um alle Berechnungen inF implizit durchzuführen. Beispielsweise schreiben wir‖·‖ : F → R, x 7→ ‖x‖ :=

√

〈x,x〉 für die durch das innere Produkt inF induzierte Norm. Da-

mit ist dann‖Ψ‖2 = ∑li, j=1αiα j

⟨

Φ(x(i)),Φ(x( j))⟩

= ∑li, j=1αiα jκ

(

x(i),x( j))

, was allein durch

κ ausgedrückt werden kann.

In völliger Analogie zum linearen Fall ergibt sich der Normalenvektor der trennenden Hyper-ebene zuΨ := ∑l

i=1αiΦ(x(i)). Zur Klassifizierung wird dann die Indikatorfunktion von

x∈ Rd∣

∣

∣〈Φ(x),Ψ〉 > θ

=

x∈ Rd

∣

∣

∣

∣

∣

l

∑i=1

αiκ(

x,x(i))

> θ

benutzt.

Beispiele für populäre Kernel sind

• lineare Kernelκ(x,y) = 〈x,y〉,• polynomielle Kernelκ(x,y) = (γ〈x,y〉+c0)

d mit γ,c0 ≥ 0 undd ∈ N,• sigmoide Kernelκ(x,y) = tanh(γ〈x,y〉+c0) mit γ > 0 undc0 < 0 und• RBF-Kernelκ(x,y) = k(‖x−y‖) für eine Funktionk: R≥0 → R≥0.

Im Weiteren beschränken wir uns auf RBF-Kernel nach Gauß,

κ(x,y) = exp(

−γ · ‖x−y‖2)

mit γ > 0,

die sich in der Objekterkennung in Bildern bestens bewährt haben. Die Ableitung des Gauß-

2

Kernels lässt sich offenbar wieder in Abhängigkeit vom Kernel selbst ausdrücken:

∂∂y

κ(x,y) = 2γ(x−y)κ(x,y)

3 Annäherung des Normalenvektors

Es sei nunΨ := ∑li=1αiΦ(x(i)) ∈ F mit αi ∈ R

× und x(i) ∈ Rd für i ∈ 1, . . . , l der Norma-

lenvektor einer Support-Vektor-Maschine im Merkmalsraum, gegeben durchl Support-Vekto-ren. Weiter sei fürm∈ 1, . . . , l ein VektorΩ := ∑m

i=1βiΦ(z(i)) ∈ F gegeben, mit Vektorenz(1), . . . ,z(m) ∈ R

d aus dem Eingaberaum und zugehörigen Koeffizientenβ1, . . . ,βm ∈ R.

Um für eine beliebige Eingabex ∈ Rd die Differenz der Abweichung der Aktivierung der

SVM und ihrer Näherung zu minimieren, genügt es,‖Ψ−Ω‖ zu minimieren. Mit der Cauchy-Schwarz-Ungleichung und wegen‖Φ(x)‖ = 1 für allex∈ R

d für Gauß-Kernel gilt nämlich:

|〈Φ(x),Ψ〉−〈Φ(x),Ω〉| = |〈Φ(x),Ψ−Ω〉| ≤ ‖Φ(x)‖ · ‖Ψ−Ω‖ = ‖Ψ−Ω‖

Wir werden zunächst die Annäherung vonΨ für m= 1 kurz beschreiben und danach die Ver-allgemeinerung für beliebigesm∈ 1, . . . , l ausführlich diskutieren.

3.1 Iterative Annäherung

Wir folgen [6] und [7]. Wir sind daran interessiert,Ψ durch Ω := βz anzunähern. Hat maneine solche Näherung gefunden, kann man das Verfahren iterieren, indem manΨ′ := Ψ−Ω alsResidualvektor setzt und schließlichΨ′ annähert.

Anstatt

‖Ψ−Ω‖2 =l

∑i, j=1

αiα jκ(

x(i),x( j)

)

−2l

∑i=1

αiβκ(

x(i),z)

+β2κ(z,z)

zu minimieren, wird die orthogonale Projektion vonΨ auf 〈Φ(z)〉,

∥

∥

∥

∥

〈Ψ,Φ(z)〉〈Φ(z),Φ(z)〉

Φ(z)−Ψ∥

∥

∥

∥

2

= ‖Ψ‖2−〈Ψ,Φ(z)〉2

〈Φ(z),Φ(z)〉

minimiert. Es genügt also,〈Ψ,Φ(z)〉2 zu maximieren. Man beachte, dass dieses Problem un-abhängig vonβ ist. Als notwendige Bedingung an ein Extremum muss die Ableitung nachzverschwinden, also muss

l

∑i=1

αiκ(

x(i),z)(

x(i)−z)

= 0

gelten. Man erhält als Fixpunktiterationsvorschrift

z(neu) :=∑l

i=1αiκ(

x(i),z)

x(i)

∑li=1αiκ

(

x(i),z) .

3

Nach Wahl eines Startwertsz∈ Rd führt man obige Vorschrift solange aus, bis sich

∥

∥z−z(neu)∥

∥

nicht mehr entscheidend verändert. Da so nur lokale Minima gefunden werden, lohnt es sich,den Vorgang für unterschiedliche Startwerte zu wiederholen.

3.2 Simultane Annäherung

Wir verallgemeinern das eben beschriebene Verfahren für eine simultane Annäherung durchmSupport-Vektoren. Offensichtlich lässt sich auch diese Methode durch Definition eines Resi-dualvektors iterieren.

Schreibeα := (α1, . . . ,αl )t ∈ R

l , X :=(

x(1), . . . ,x(l))

∈ Rd×l , β := (β1, . . . ,βm)t ∈ R

m und

Z :=(

z(1), . . . ,z(m))

∈ Rd×m. Dann ist

f : Rm×R

d×m → R, (β,Z) 7→ ‖Ψ−Ω‖2

die zu minimierende Zielfunktion. Schreibe weiter

KX :=(

κ(

x(i),x( j)

))

i, j∈1,...,l∈ R

l×l ,

KZX :=(

κ(

z(i),x( j)

))

i∈1,...,m, j∈1,...,l∈ R

m×l bzw.

KZ :=(

κ(

z(i),z( j)

))

i, j∈1,...,m∈ R

m×m

für dieKernel-MatrixvonX, (Z,X) bzw.Z. Damit gilt offenbar

f (β,Z) = ‖Ψ−Ω‖2 = 〈Ψ−Ω,Ψ−Ω〉 = 〈Ψ,Ψ〉−2〈Ψ,Ω〉+ 〈Ω,Ω〉

=l

∑i, j=1

αiα jκ(

x(i),x( j)

)

−2l

∑i=1

m

∑j=1

αiβ jκ(

x(i),z( j)

)

+m

∑i, j=1

βiβ jκ(

z(i),z( j)

)

= αtKXα−2βtKZXα+βtKZβ.

Fürk∈ 1, . . . ,m ist

∂ f∂βk

= −2l

∑i=1

m

∑j=1

∂∂βk

αiβ jκ(

x(i),z( j)

)

+m

∑i, j=1

∂∂βk

βiβ jκ(

z(i),z( j)

)

= −2l

∑i=1

αiκ(

z(k),x(i)

)

+2m

∑i=1

βiκ(

z(i),z(k)

)

= −2etkKZXα+2et

kKZβ = 2etk (KZβ−KZXα) ,

wobeiek ∈ Rm denk-ten kanonischen Einheitsvektor bezeichnet. Damit ist dieAbleitung nach

β gegeben durch∂ f∂β = 2(KZβ−KZXα). Wenn ein Extremum vorliegt, muss∂ f

∂β verschwinden,und wir erhalten Proposition 18.2 aus [7]:

KZβ = KZXα ⇐⇒ β = K−1Z KZXα

Wenn diez(i) paarweise verschieden sind, dann hatKZ nach [7], Theorem 2.18, vollen Rangund ist damit invertierbar, also istβ nach dieser Wahl wohldefiniert. Bemerkenswert an dieser

4

Identität ist, dass das optimaleβ zum Minimieren vonf bereits durchX, α undZ gegeben ist.Egal auf welche Weise eine NäherungZ berechnet wird, durch Auswerten dieser Identität wirddann ein optimaler Gewichtsvektorβ für Z berechnet, derf minimiert. Dies lässt sich auch aufdas iterative Vorgehen anwenden, indem bei jeder Definitiondes Residualvektors in Iterationm≤ m für bereits gefundene Vektorenz(1), . . . ,z(m) optimale Gewichteβ1, . . . ,βm berechnetwerden.

DaKZ symmetrisch ist, gilt dies auch fürK−1Z , mithin ist

f (K−1Z KZXα,Z) = αtKXα−2αtKt

ZXK−1Z KZXα+αtKt

ZXK−1Z KZK−1

Z KZXα= αtKXα− (KZXα)t K−1

Z (KZXα) .

Damit ist fürµ∈ 1, . . . ,m undν ∈ 1, . . . ,d

∂ f

∂z(µ)ν

= −2l

∑i=1

m

∑j=1

∂

∂z(µ)ν

αiβ jκ(

x(i),z( j)

)

+∂

∂z(µ)ν

m

∑i, j=1

βiβ jκ(

z(i),z( j)

)

= −4γetµ

(

l

∑i=1

αiβµ

(

x(i)−z(µ))

κ(

z(µ),x(i)

)

−m

∑i=1

βiβµ

(

z(i)−z(µ))

κ(

z(µ),z(i)

)

)

,

und somit

∂ f

∂z(µ)= −4γβµ

(

l

∑i=1

αietµKZXeix

(i)−m

∑i=1

βietµKZeiz

(i)

+z(µ)

(

m

∑i=1

βietµKZei −

l

∑i=1

αietµKZXei

))

mit ∑mi=1βiet

µKZei = etµKZβ und∑l

i=1αietµKZXei = et

µKZXα. WegenKZβ = KZXα ist schließlich

∂ f

∂z(µ)= −4γβµ

(

X ·(

α∗KtZXeµ

)

−Z ·(

β∗KtZeµ)

)

,

wobei∗ die eintragsweise Multiplikation bezeichnet, welche eineniedrigere Auswertungsprio-rität als die Matrixmultiplikation· habe.

Schreibe nunJ :=(

1 . . . 1)

∈ R1×m. Dann ist

∂ f∂Z

= −4γ(βJ)t ∗(

X ·(

αJ∗KtZX

)

−Z ·(

βJ∗KtZ

)

)

.

Aus dieser Identität lässt sich eine Fixpunktiterationsvorschrift herleiten:

Z(neu) := X ·(

αJ∗KtZX

)

·(

βJ∗KtZ

)−1

5

Fürm= 1 ergibt sichZ(neu)= X ·

(

α∗KtZX

)

· (KZXα)−1 ,

die in Abschnitt 3.1 vorgestellte Fixpunktiterationsvorschrift.

3.3 Algorithmus

Die Verwendung der verallgemeinerten Fixpunktiterationsvorschrift für m > 1 hat sich aufGrund numerischer Instabilitäten nicht als effektiv erwiesen. Stattdessen haben wir einen Gradi-entenabstieg mit Momentumterm verwendet, wobei die Startwerte eine Teilmenge der Support-Vektoren der Eingabe-SVM waren.

Zur Berechnung der NäherungΩ verfahren wir wie folgt:

(1) Eingabe ist eine Matrix mit den Support-VektorenX ∈ Rd×l , der zugehörige Gewichts-

vektorα ∈ Rl , der Parameter des Gauß-Kernelsγ > 0, sowie eine Lernrateη > 0 und ein

Momentumfaktorζ ∈ [0,1).(2) Bestimme Prototypen für den StartwertZ ∈ R

d×m aus den Support-VektorenX; das Ver-hältnis von positiven zu negativen Protoypen (gemäß Gewichtsvektorα) von Z soll dabeidas gleiche wie das vonX sein.

(3) Führe solange einen Gradientenabstieg mit Momentumterm aus, bis sich die Güte der Nä-herung‖Ψ−Ω‖2 nicht mehr wesentlich verbessert:

∆Z(neu) := −(1−ζ)η∂ f∂Z

+ζ∆Z

Z(neu) := Z+∆Z

Dabei ist ein Startwert von∆Z = 0∈ Rd×m gesetzt.

(4) Ausgabe ist dann das endgültigeZ aus dem letzten Schritt sowie der zugehörige optimaleGewichtsvektorβ = K−1

Z KZXα ∈ Rm.

Um f zu berechnen, genügt es dabei, die Kernel-MatrixKX einmal zu berechnen, d.h. manminimiert die AbbildungZ 7→ −(KZXα)t K−1

Z (KZXα). Die Zeitkomplexität für eine Iterationist dannO(dlm+m3) Operationen, wobeiO(dlm) Operationen für das Berechnen der Kernel-Matrix KZX und beim Berechnen des Gradienten für den TermX · (αJ∗Kt

ZX) benötigt werdenundO(m3) Operationen für das Invertieren der Kernel-MatrixKZ benötigt werden.

Dieses Vorgehen hat sich – im Gegensatz zur Verwendung der Fixpunktiterationsvorschrift –als äußerst robust erwiesen. Einzig die Wahl der Lernrateη erwies sich als kritischer Parameter:während bei Spielzeugdatenη ∈ [10−3,10−1] gute Ergebnisse brachte, musste auf natürlichenDaten aus der bildbasierten Objekterkennungη ∈ [10−10,10−7] gewählt werden.

4 Ergebnisse

Das beschriebene Verfahren wurde in MATLAB implementiert und auf einigen Datensätzengetestet. Zum Training der Support-Vektor-Maschinen wurde LIBSVM [1] verwendet.

6

4.1 Toy-Datensatz

Dieser künstliche Datensatz wurde von Hand zusammengestellt. Er beinhaltet 471 Datenpunk-te aus[0,1]2 ⊆ R

2, wobei 191 Datenpunkte positiv und 280 Datenpunkte negativklassifiziertwurden. Die SVM wurde mit ParameternC = 1 undγ = 15 trainiert und wählte sichl = 130Support-Vektoren aus, dabei hatten 64 Support-Vektoren positives Gewicht und 66 Support-Vektoren hatten negatives Gewicht.

Es wurde eine RVM mitm = 13 Support-Vektoren aus der SVM nach obigem Verfahren mitη = 10−3 und ζ = 0,9 berechnet. Abbildung 1 zeigt den Verlauf der Zielfunktionwährendder Optimierung: bereits nach 120 Schritten wurde ein lokales Minimum gefunden. Die Normdes SVM-Normalenvektors war hierbei‖Ψ‖ = 8,40, die Annäherung nach Auswahl der Start-werte war‖Ψ−Ω0‖ = 4,85, die Annäherung nach Konvergenz in einem lokalen Minimum‖Ψ−Ω‖ = 0,34.

Abbildung 2 zeigt die Aktivierung der SVM und der RVM auf dem Einheitsquadrat sowie dievorgegebene Trainingsmenge. Am rechten unteren Rand sieht man eine Abweichung, die ineiner Falschklassifizierung der RVM resultiert, wenn man die SVM als Referenz verwendet.Man beachte, dass sich in diesem Bereich keine Trainingsdaten befunden haben.

0 20 40 60 80 100 120 140 160 180 2000

0.5

1

1.5

2

2.5

3

3.5

4

4.5

5

Iterationen

||Ψ −

Ω||

Abbildung 1. Güte der Approximation‖Ψ−Ω‖ des SVM-Normalenvektors im Verlauf des Optimie-rungsverfahrens für die Toy-Datensatz-SVM

7

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

−2.5

−2

−1.5

−1

−0.5

0

0.5

1

1.5

2

(a) ∑li=1 αiκ

(

x,x(i))

−θ

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

−2.5

−2

−1.5

−1

−0.5

0

0.5

1

1.5

2

(b) ∑mi=1 βiκ

(

x,z(i))

−θ

Abbildung 2. Ergebnisse auf dem Toy-Datensatz: (a) Aktivierung derSVM mit 130 Support-Vektoren;(b) Aktivierung der RVM mit 13 Support-Vektoren; schwarze Kreuze und Kreise sind Trainingsdaten(positiv bzw. negativ klassifiziert), weiße Kreuze und Kreise sind Support-Vektoren der SVM in (a) bzw.der RVM in (b), wobei Kreuze positives Gewicht und Kreise negativesGewicht bedeuten

8

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

−0.2

−0.15

−0.1

−0.05

0

0.05

0.1

0.15

0.2

(a)∣

∣∑li=1 αiκ

(

x,x(i))

−∑mi=1 βiκ

(

x,z(i))∣

∣ ·(

2χFalschklassifizierung der RVM−1)

−0.4 −0.2 0 0.2 0.4 0.6 0.8 1 1.2−0.4

−0.2

0

0.2

0.4

0.6

0.8

1

1.2

7.85

7.9

7.95

8

8.05

8.1

8.15

8.2

8.25

8.3

8.35

(b) ‖Ψ−Ω‖ für Ω = βz

Abbildung 3. Ergebnisse auf dem Toy-Datensatz: (a) absolute Differenz der Aktivierung von SVM undRVM, negiert bei Falschklassifizierung der RVM; weiße Markierungensind Support-Vektoren der RVM;(b) Zielfunktion für Annäherung durch einen Vektor; weiße Markierungen sind Support-Vektoren derSVM, schwarze Markierungen sind Startwerte für Optimierung, rote Markierungen sind Support-Vekto-ren der RVM; die RVM-Support-Vektoren und ihre Startwerte sind durcheinen Pfeil verbunden

9

Abbildung 3a zeigt den Unterschied zwischen der Aktivierung der SVM und der Aktivierungder RVM. Ganz deutlich ist hier die Falschklassifizierung amrechten unteren Rand zu erkennen.Man erkennt auch, dass die Abweichung unter der theoretischen Schranke von‖Ψ−Ω‖= 0,34bleibt.

Abbildung 3b zeigt die Zielfunktion für Annäherung durch einen Vektor. Außerhalb des Be-reichs, in dem die Support-Vektoren der SVM liegen, ist keine Approximierung zu erreichen.Dies rechtfertigt die Wahl des Startwerts fürZ als Prototypen aus den Support-VektorenX. DieWahl der Klasseneinteilung ist dabei nicht das ausschlaggebende; sofern erforderlich verändertsich das Vorzeichen des Gewichts der Support-Vektoren, wieauf der Abbildung zu erkennen ist:Startwerte mit positivem Gewicht werden zu endgültigen Werten mit negativem Gewicht undumgekehrt. Bei Verwendung eines iterativen Verfahrens hätten die Näherungsvektoren – je nachStartwert – unter Umständen weite Wege über flache Plateaus zurücklegen müssen. Hier bewirktder Momentumterm eine Beschleunigung der Konvergenz. Auffallend ist auch, dass kein Sup-port-Vektor der RVM im genauen Zentrum eines Minimums der Zielfunktion für Annäherungdurch einen Vektor liegt. An diesem Beispiel wird also die Notwendigkeit der simultanen Annä-herung ersichtlich; bei iterativer Annäherung sollte alsonach Abschluss noch eine zweite Phaseerfolgen, in der die Näherung noch mit der simultanen Annäherung verbessert wird.

4.2 Splice-Datensatz

Dieser Datensatz stammt von [2]; die Aufgabe besteht hierbei darin, zwei unterschiedlicheTypen von Spleißstellen in der DNS zu unterscheiden, nämlich zwischen Stellen vom TypExon/Intron und denen vom Typ Intron/Exon. Die Daten liegenim R

61, der Lerndatensatz ent-hält 1000 Beispiele, der Testdatensatz enthält 2175 Beispiele. Zum Trainieren der SVM wurdeeine Gitter-Suche mit 5-facher Kreuzvalidierung durchgeführt, die beste Genauigkeit von 0,868wurde fürC = 2 undγ = 0.03125 erreicht, wie aus Abb. 4 ersichtlich. Die SVM wählte sichl = 690 Support-Vektoren aus, es ist‖Ψ‖ = 25,07.

Für m∈ 1,2,3,4,8,17,34,69 wurden Näherungen mit den Parameternη = 0,1 undζ = 0,9berechnet, die Schwellwerte der RVMs wurden auf den der Original-SVM gesetzt. In Tabelle 1sind zusätzlich zur Güte der Näherung die Genauigkeit, Erkennungs- und Falschalarmrate aufdem Testdatensatz aufgeführt. Man sieht dass sich die Güte der Näherung für wachsendesmverbessert, so wie die Genauigkeit auf dem Testdatensatz. Für m≥ 3 gibt es nur sehr geringeAbweichungen zwischen den Näherungen und der Original-SVM.

Abb. 5 zeigt die ROC-Kurven der SVM und der Näherungen auf dem Testdatensatz; durch Va-riation des Schwellwertes der SVM-Entscheidungsfunktionwurden Erkennungs- und Falscha-larmrate gegeneinander aufgetragen. Fürm= 3 ist noch ein kleiner Unterschied zwischen derNäherung und der Original-SVM zu erkennen, fürm≥ 4 können die Kurven kaum noch unter-schieden werden.

In Abb. 6 sieht man die relevanten Daten im Verlauf des Optimierungsverfahrens, nämlich denWert der Zielfunktionf sowie die Norm des Gradienten vonf . Nach 1500 Iterationen ist be-reits keine wesentliche Verbesserung mehr zu erreichen, obwohl die Graphen durch den hohenMomentumterm bedingt Oszillationen aufzeigen.

10

log2 C

log 2 γ log

2(C) = 1, log

2(γ) = −5 ⇒ ACC = 0.868

−5 0 5 10 15

−14

−12

−10

−8

−6

−4

−2

0

2

0.55

0.6

0.65

0.7

0.75

0.8

0.85

Abbildung 4. Genauigkeit auf dem Splice-Datensatz in Abhängigkeit der TrainingsparameterC undγ

m ‖Ψ−Ω0‖ ‖Ψ−Ω‖ Genauigkeit Erkennungsrate Falschalarmrate

690 0 0 0,904 0,890 0,080

69 23,30 15,04 0,905 0,888 0,076

34 24,14 17,02 0,899 0,882 0,083

17 24,66 18,90 0,903 0,882 0,074

8 24,82 20,63 0,898 0,891 0,094

4 24,93 21,52 0,899 0,891 0,093

3 24,95 21,94 0,894 0,866 0,076

2 25,01 23,22 0,753 0,950 0,461

1 25,01 24,12 0,520 0,097 0,021

Tabelle 1. Ergebnisse auf dem Splice-Datensatz

11

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Falschalarmrate

Erk

ennu

ngsr

ate

SVM (690 Support−Vektoren)RVM (69 Support−Vektoren)RVM (34 Support−Vektoren)RVM (17 Support−Vektoren)RVM (8 Support−Vektoren)RVM (4 Support−Vektoren)RVM (3 Support−Vektoren)RVM (2 Support−Vektoren)RVM (1 Support−Vektor)

Abbildung 5. ROC-Kurven auf dem Splice-Datensatz

0 500 1000 1500 2000 250015

16

17

18

19

20

21

22

23

24

Iterationen

||Ψ −

Ω||

(a)‖Ψ−Ω‖

0 500 1000 1500 2000 25000

20

40

60

80

100

120

140

Iterationen

||gra

d f||

(b)∥

∥

∥

∂ f∂Z

∥

∥

∥

Abbildung 6. Ergebnisse auf dem Splice-Datensatz: relevante Daten im Verlauf des Optimierungsver-fahrens fürm= 69. Fürζ = 0,9 oszillieren zwar die Graphen bei sich verbessernder Annäherung,dieKonvergenz ist aber deutlich schneller als bei geringeren Momentumfaktoren.

12

In Abb. 7 wird die simultane Annäherung mit der iterativen Annäherung verglichen. Für dieiterative Annäherung wurden in jeder Stufe fünfzehn Startwerte aus den Support-Vektoren ge-wählt, pro Startwert ein Gradientenabstieg fürm= 1 durchgeführt und dann das beste Ergebnisgenommen. Die iterative Annäherung erreichte einen Endwert von ‖Ψ−Ω‖ = 17.52, die si-multane Annäherung hat diesen Wert bereits fürm= 29 unterboten.

0 10 20 30 40 50 60 6914

16

18

20

22

24

26 Güte der Approximierungen

Anzahl reduzierter Support−Vektoren m

||Ψ −

Ω||

iterativsimultan

Abbildung 7. Vergleich der simultanen und der iterativen Annäherung aufdem Splice-Datensatz

5 Ausblick

Wir haben ein Verfahren zur Reduzierung der Komplexität einer Support-Vektor-Maschine be-schrieben. Dabei wurde mittels Gradientenabstieg mit Momentumterm der maximale Unter-schied zwischen der Aktivierung der SVM und ihrer Näherung minimiert. In den vorgestelltenFällen ist somit eine Reduktion auf ein Zehntel oder weniger der Komplexität möglich, ohnewesentliche Einschnitte in der Genauigkeit der Klassifikation hinnehmen zu müssen.

Eine weitere Beschleunigung wird in [5] erreicht: beim Evaluieren der SVM liegt beim Berech-nen von‖x−y‖ = xtx−2xty+ yty für den Gauß-Kernel eine hohe Last, wobeix ein Support-Vektor undy ein zu überprüfender Bildausschnitt ist. Daxtx konstant ist, kann es vor der Eva-luierungsphase berechnet und gespeichert werden,yty kann mit Hilfe des Integralbildes [8] der

13

quadrierten Pixel schnell berechnet werden. Um nun auch 2xty schnell berechnen zu können,wird für x eine optimale Näherung mit blockartiger Struktur berechnet. Durch diese Näherungkann dann 2xty mit Hilfe des Integralbildes schnell berechnet werden, wasschließlich eine er-hebliche Beschleunigung beim Abtasten eines gesamten Bildeseinbringt.

Literatur

[1] Chih-Chung Chang, Chih-Jen Lin:LIBSVM: a library for support vector machines,2001, Softwareavailable athttp://www.csie.ntu.edu.tw/~cjlin/libsvm

[2] D.J. Newman, S. Hettich, C.L. Blake, C.J. Merz:UCI Repository of machine learningdatabases,http://www.ics.uci.edu/~mlearn/MLRepository.html, University of California,Irvine, Dept. of Information and Computer Sciences

[3] Constantine Papageorgiou, Tomaso Poggio:Trainable Pedestrian Detection,Proceedings ofInternational Conference on Image Processing, Kobe, Japan, October 1999

[4] Edgar Osuna, Robert Freund, Federico Girosi:Training Support Vector Machines: an Application toFace Detection,Proceedings of the 1997 Conference on Computer Vision and Pattern Recognition

[5] M. Rätsch, G. Teschke, S. Romdhani, T. Vetter:Wavelet Frame Accelerated Reduced Support VectorMachine,under review, 2006.

[6] Bernhard Schölkopf et al.:Input Space Versus Feature Space in Kernel-Based Methods,IEEETransactions on Neural Networks, Vol. 10, No. 5, September 1999

[7] Bernhard Schölkopf, Alexander J. Smola:Learning with Kernels. Support Vector Machines,Regularization, Optimization, and Beyond,The MIT Press, 2002

[8] P. Viola, M. Jones:Rapid object detection using a boosted cascade of simple features,ProceedingsIEEE Conf. on Computer Vision and Pattern Recognition, 2001

14