Stefan Bosse - Maschinelles Lernen - Regression und Support Vector Machines -

Regression und Support Vector Machines

Wie funktioniert Regression?

SVM gehören zu den Regressionsverfahren

SVM nutzen aber bei der Parameteranpassung (Training) eine andere Fehlerfunktion (Loss) als bei anderen gängigen Regressionsverfahren (z.B. Least-Square Minimierung)

SVM können primär kategorische und weniger numerische Zielvariablen abbilden

SVM sind aber (zunächst) lineare Klassifikatoren!

Stefan Bosse - Maschinelles Lernen - Regression und Support Vector Machines - Regressionsverfahren

Regressionsverfahren

• Klassifikationsprobleme sind durch Booleschen Ausgabevariablen gekennzeichnet (Klasse c_i={true,false})

• Bei Regressionproblemen findet hingegen eine Ausgabe mit kontinuierlichen Variablen statt, idealerweise y ∈ [0,1]

• D.h. es gibt Trainingsdaten mit:

$${D}={X}^{{t}}={{\left\lbrace\vec{{x}}^{{t}},{r}^{{t}}\right\rbrace}_{{{t}={1}}}^{{{N}}}}$$

wobei r ∈ ℝ. Wenn Rauschen vernachlässigt wird handelt es sich um ein reines Interpolationsproblem.

• Das Ziel ist es nun, eine Funktion f(x) zu finden, die die Trainingsdaten optimal repräsentiert (also die beste Hypothese g von f finden)

Stefan Bosse - Maschinelles Lernen - Regression und Support Vector Machines - Regressionsverfahren

Beispiel

Stefan Bosse - Maschinelles Lernen - Regression und Support Vector Machines - Regressionsverfahren

Es wird immer einen Fehler ε geben:

$${r}^{{t}}={f{{\left(\vec{{x}}^{{t}}\right)}}}+\epsilon$$

• Ziel der Regression ist es diesen Fehler über eine Verlustfunktion zu minimieren in dem Parameter Θ der Funktion f angepasst werden:

$$\text{arg}\ \text{ }\ {\underset{{\theta}}{{\text{min}}}}\ \text{ }\ \epsilon\to{E}{\left({g}{\mid}{X}\right)}=\frac{{1}}{{N}}\sum{\left({r}^{{t}}-{g{{\left(\vec{{x}}^{{t}}\right)}}}\right)}^{{2}}$$

Stefan Bosse - Maschinelles Lernen - Regression und Support Vector Machines - Regressionsverfahren

Lineare Multivariate Regression

• Es wird angenommen dass die Funktion f(x) durch eine lineare Funktion über x abgebildet werden kann.
• Dann gilt:

$${g{{\left(\vec{{x}}\right)}}}={w}_{{1}}{x}_{{1}}+{w}_{{2}}{x}_{{2}}+..+{w}_{{d}}{x}_{{d}}+{w}_{{0}}={\sum_{{{j}={1}}}^{{{d}}}}{w}_{{d}}{x}_{{d}}+{w}_{{0}}$$

• Bei nichtlinearen Zusammenhängen wird die Regressionsfunktion noch komplexer!

Stefan Bosse - Maschinelles Lernen - Regression und Support Vector Machines - Regressionsverfahren

Nichtlineare Univariate Regression

• Es gibt nur eine Eingabevariable und die Hypothesenfunktion wird durch ein Polynom k-ter Ordnung approximiert:

$${g{{\left({x}\right)}}}={w}_{{0}}+{w}_{{1}}{x}+{w}_{{2}}{x}^{{2}}+..+{w}_{{k}}{x}^{{k}}={\sum_{{{j}={1}}}^{{{k}}}}{w}_{{j}}{x}^{{j}}+{w}_{{0}}$$

• Wird von einem Polynom ersten Grades ausgegangen (Gerade) dann gilt es folgende Gleichung zu bestimmen und das Minimierungsproblem zu lösen:

$${g{{\left({x}\right)}}}={w}_{{1}}{x}+{w}_{{0}}\\ {E}{\left({w}_{{1}},{w}_{{0}}{\mid}{X}^{{t}}\right)}=\frac{{1}}{{N}}{\sum_{{{t}={1}}}^{{{N}}}}{\left({r}^{{t}}-{\left({w}_{{1}}{x}^{{t}}+{w}_{{0}}\right)}\right)}^{{2}}$$

Stefan Bosse - Maschinelles Lernen - Regression und Support Vector Machines - Regressionsverfahren

• Den Minimumspunkt dieser Fehlergleichung findet man durch Gradientenbildung der Parameter, das bedeutet dann:

$${w}_{{1}}=\frac{{\sum_{{t}}{x}^{{t}}{r}^{{t}}-\overline{{x}}\overline{{r}}{N}}}{{\sum_{{t}}{\left({x}^{{t}}\right)}^{{2}}-{N}\overline{{x}}^{{2}}}}\\ {w}_{{0}}=\overline{{r}}-{w}_{{1}}\overline{{x}}\\ \overline{{x}}=\sum_{{t}}\frac{{x}^{{t}}}{{N}},\overline{{r}}=\sum_{{t}}\frac{{r}^{{t}}}{{N}}$$

Stefan Bosse - Maschinelles Lernen - Regression und Support Vector Machines - Regressionsverfahren

Nichtlineare Multivariate Regression

• Sehr hochdimensionales Problem! Und i.A. völlig unterbestimmt (d.h. kein eindeutigen Zusammenhänge zwischen x und y)

$${g{{\left(\vec{{x}}\right)}}}={\sum_{{{i}={1}}}^{{{d}}}}{\sum_{{{j}={1}}}^{{{k}}}}{w}_{{{i},{j}}}{{x}_{{i}}^{{j}}}+{w}_{{0}}$$

• Es können auch exponentielle, logarithmische, und sinusoidale Terme hinzukommen!

• Ein numerisches Lösen ist meist nicht mehr möglich; daher Verwendung nichtlinearer Randbedingungslöser sowie statistische Verfahren wie randomiserte Monte Carlo Simulation und Simmuliertes Abkühlen (Evolutionäre Algorithmen?)

Stefan Bosse - Maschinelles Lernen - Regression und Support Vector Machines - Regressionsverfahren

Stefan Bosse - Maschinelles Lernen - Regression und Support Vector Machines - Direkte Lösungsverfahren

Direkte Lösungsverfahren

Single Value Decomposition (SVD)

4

• Erweiterung der Eigenwertanalyse und verwendet Matrixalgebra und Inversionsmethoden

• Ansatz: Dekomposition einer (nichtlinearen) Funktion f(x,Θ) mit b Basisfunktionen ϕ, z.B. sin oder ähnlich, mit Parametersatz Θ:

$${{f}_{\Theta}{\left(\vec{{x}}\right)}}={\sum_{{{j}={1}}}^{{{b}}}}\Theta_{{j}}\phi_{{j}}{\left({x}\right)}\\ {{f}_{\Theta}{\left(\vec{{x}}\right)}}=\vec{\Theta}^{{T}}\vec{\phi}{\left({x}\right)}$$

• Z.B. ϕ(x) = (1,x,x²,..,x^b-1)^T, oder ϕ(x) = (1,sin(x),cos(x),sin(2x),...)^T

Stefan Bosse - Maschinelles Lernen - Regression und Support Vector Machines - Direkte Lösungsverfahren

• Die gesamte Trainingstabelle wird in Matrixform repräsentiert, und somit erhält man eine Parametermatrix Φ mit den Basisfunktionstermen für die anzupassenden Funktion f(x)_Θ (Design Matrix):

$$\hat{\Phi}={\left(\matrix{\phi_{{1}}{\left(\vec{{x}}_{{1}}\right)}&..&\phi_{{b}}{\left(\vec{{x}}_{{1}}\right)}\\\ldots&\ldots&\ldots\\\phi_{{1}}{\left(\vec{{x}}_{{n}}\right)}&..&\phi_{{b}}{\left(\vec{{x}}_{{n}}\right)}}\right)}$$

Stefan Bosse - Maschinelles Lernen - Regression und Support Vector Machines - Direkte Lösungsverfahren

• Die Lösung (der Funktionsparameter Θ) geschieht dann doch Matrixinversion der Designmatrix Φ:

$$\hat{\Theta}_{{{L}{S}}}={\left(\Phi^{{T}}\Phi\right)}^{{-{1}}}\Phi^{{T}}{y}\\ \hat{\Theta}_{{{L}{S}}}=\Phi^{{G}}{y}$$

mit Φ^G als generalisierte Inverse der Matrix Φ

Stefan Bosse - Maschinelles Lernen - Regression und Support Vector Machines - Support Vector Machines (SVM)

Support Vector Machines (SVM)

• SVM Verfahren gehören zu den "Maximum Margin" Methoden

Stefan Bosse - Maschinelles Lernen - Regression und Support Vector Machines - Binärer Klassifikator

Binärer Klassifikator

• Ein binärer Klassifikator soll durch eine lineare Funktion repräsentiert werden (y={-1,+1}):

$$f(\vec{x}):\vec{x} \rightarrow y=\vec{w}^T\vec{x}+\gamma$$

Dabei sind w und γ die Parameter des Modells die durch das Training an das Problem angepasst werden müssen.

• w ist ein Normalenvektor der bei einem binären Klassifikationsproblem die beiden Instanzklassen trennt

Stefan Bosse - Maschinelles Lernen - Regression und Support Vector Machines - Binärer Klassifikator

4 (Oben) w ist der Normalenvektor und γ die Verschiebung der Trennungsgrenze für zwei Klasseninstanzen (Unten) Verschiedene w/γ Varianten der Trennungsgrenze mit unterschiedlichen Rändern (Sicherheitsbereichen)

Stefan Bosse - Maschinelles Lernen - Regression und Support Vector Machines - Training

Training

• Das Lernen von w und γ erfordert die Berechnung des Abstandes von allen Dateninstanzen (x,y)_i von der Trenngrenze. Die Abstände müssen positiv sein:

$$f(\vec{x}_i)y_i=(\vec{w}^T\vec{x}_i+\gamma)y_i > 0, \forall i$$

für alle Dateninstanzen D={(x_i,y_i)}ⁿ.

• Da w und γ beliebig gewählt werden können, kann die Randbedingung auch mit (..)y_i ≥ 1 gewählt werden.

• Weiterhin kann es sinnvoll sein alle Dateninstanzen um den Ursprung des Koordinatensystems zu zentrieren

Stefan Bosse - Maschinelles Lernen - Regression und Support Vector Machines - Training

Wichtig: Die Werte für y liegen im Intervall [-1,1]!

• Alle Probleme die (..)y_i ≥ 1 erfüllen mit einem (w,γ) sind linear separierbar.

• Es gibt unendlich viele Lösungen (also Entscheidungsgrenzen)

• Man wählt das (w,γ) aus bei der alle Dateninstanzen die größte Trennung besitzen (breitester Trennbereich, siehe Abb.)

• Der Abstand der Dateninstanzen D ist definiert als das Minimum des normalisierten Abstandes:

$$m_i=(\vec{w}^T\vec{x}_i+\gamma)y_i/||\vec{w}||$$

Stefan Bosse - Maschinelles Lernen - Regression und Support Vector Machines - Training

• D.h. SVM zu trainieren ist das Minimierungsproblem zu lösen:

$$\mathop {\min }\limits_i \frac{(\vec{w}^T\vec{x}_i+\gamma)y_i}{||w||}=\frac{1}{||w||}$$

• Jede Dateninstanz die nicht in den Trennbereich "eindringt" ist ein Supportvektor!

Stefan Bosse - Maschinelles Lernen - Regression und Support Vector Machines - Training

Harter Trennungsbereich (Hard SVM)

• Bei einer "harten" Trennung einer SVM gilt dann:

$$\mathop {\min }\limits_i 1/2 ||w||^2, (\vec{w}^T\vec{x}_i+\gamma)y_i \geqslant 1, \forall i$$

Stefan Bosse - Maschinelles Lernen - Regression und Support Vector Machines - Training

Weicher Trennungsbereich (Soft SVM)

• Die SVM mit harten Trennungsbereich erfordert lineare Separierbarkeit der Dateninstanzen

  • Ist in der Realität aber nicht immer oder eher selten gegeben

• Die weiche Trennung durch eine SVM führt einen Fehlerparametervektor ξ={ξ_i}ⁿ für die Bestimmung des Trennbereichs ein:

$$\mathop {\min }\limits_{\forall i:w,\xi,\gamma} \left[1/2 ||w||^2 + C\sum_i\xi_i\right],\\ (\vec{w}^T\vec{x}_i+\gamma)y_i \geqslant 1 - \xi_i, \xi_i \geqslant 0, \forall i$$

• Sie lässt einzelne nicht (linear) separierbare Datenpunkte zu.

Stefan Bosse - Maschinelles Lernen - Regression und Support Vector Machines - Training

4 Weicher Trennbereich einer SVM (Soft margin SVM). Durch ξ werden kleine Klassifikationsfehlerbereiche erlaubt.

Stefan Bosse - Maschinelles Lernen - Regression und Support Vector Machines - Training

Dabei ist C ein einstellbarer Parameter der den Fehler steuert und für den gilt:

$${C}=\alpha_{{i}}+\beta_{{i}}$$

Stefan Bosse - Maschinelles Lernen - Regression und Support Vector Machines - Multiklassen SVM

Multiklassen SVM

• Anders als bei ANN ist bei SVMs aber nur eine One-hot Kodierung möglich (ggfs. mit Softmaxfunktion).

Stefan Bosse - Maschinelles Lernen - Regression und Support Vector Machines - ML Framework API für SVM

ML Framework API für SVM

ML.learn({
    algorithm:ML.ML.SVM,
    x:number [][], 
    y:number [],
    // threshold function on output? highest value of multi-svms is winner
    threshold:boolean,  
    // default : 1.0. C in SVM.
    C : number, 
    // default : 1e-4. Higher tolerance --> Higher precision
    tol : number, 
    // default : 20. Higher max_passes --> Higher precision
    max_passes : number,
    // default : 1e-5. Higher alpha_tolerance --> Higher precision
    alpha_tol : number, 
    kernel : { type: 'rbf', sigma: 0.5 } 
    // { type: "polynomial", c: 1, d: 5}
}) → model

Stefan Bosse - Maschinelles Lernen - Regression und Support Vector Machines - Beispiel

Beispiel

Stefan Bosse - Maschinelles Lernen - Regression und Support Vector Machines - Beispiel

Sugiyama, ItSML, pp 303

Zusammenfassung

• Regressionsverfahren werden auf kontinuierliche Zielvariablen angewendet (der Hypothesenraum kann bei nichtlinearen Problemen sehr groß werden)

• Eine SVM wird als binärer Klassifikator verwendet und wird i.A. durch eine lineare Funktion (Kernel) repräsentiert

  • Das Problem sollte dann linear separierbar sein!

• Multiklassenprobleme werden auf Multi-SVMs zurückgeführt

  • Verwendung einer Softmax Funktion für eindeutige Klassentrennung

• Das Training einer SVM ist ein Minimierungsproblem dass den Trennbereich maximiert und den Fehler minimiert