Stefan Bosse - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN ::

Regressionsverfahren, SVM und KNN

Bisher wurden vor allem kategorische Zielvariablen betrachtet. Nun soll ein Schwerpunkt auf numerischen Variablen liegen.

Stefan Bosse - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN ::

Regressionsverfahren, SVM und KNN

Bisher wurden vor allem kategorische Zielvariablen betrachtet. Nun soll ein Schwerpunkt auf numerischen Variablen liegen.

Regressionsverfahren passen eine parametrisierte mathematische Funktion an Messdaten an.

Stefan Bosse - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN ::

Regressionsverfahren, SVM und KNN

Bisher wurden vor allem kategorische Zielvariablen betrachtet. Nun soll ein Schwerpunkt auf numerischen Variablen liegen.

Regressionsverfahren passen eine parametrisierte mathematische Funktion an Messdaten an.

Neben den "klassischen" Regressionsverfahren wie Least Square Fit gehören grundsätzlich auch Support Vector Machines (SVM) und Künstliche Neuronale Netzwerke dazu!

Stefan Bosse - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN ::

SVM gehören zu den Regressionsverfahren

Stefan Bosse - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN ::

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)

Stefan Bosse - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN ::

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

Stefan Bosse - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN ::

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 - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN :: 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 ∈ ℝ (kontinuierliche Zielvariable). 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 - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN :: Regressionsverfahren

Beispiel

Stefan Bosse - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN :: Regressionsverfahren

Es wird immer einen Fehler ε geben (Rauschen in den "Trainingsdaten" r):

$${y}{\left(\vec{{x}}^{{t}}\right)}={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 - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN :: Regressionsverfahren

Lineare Multivariate Regression

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

$${y}_{{p}}{\left(\vec{{x}}\right)}={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 - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN :: 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 - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN :: 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 - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN :: 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}}$$

• 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 - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN :: Regressionsverfahren

Stefan Bosse - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN :: Regressionsverfahren

Stefan Bosse - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN :: 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 - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN :: 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 - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN :: 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 - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN :: Support Vector Machines (SVM)

Support Vector Machines (SVM)

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

Stefan Bosse - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN :: Binärer Klassifikator

Binärer Klassifikator

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

$$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

• y kann tatsächlich auch außerhalb der Grenzen [-1,1] liegen (klar: Polynome haben keine Grenzen)!

Stefan Bosse - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN :: 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 - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN :: 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 - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN :: 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 - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN :: 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 - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN :: 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 - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN :: 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 (zur Erinnerung: i ist der i-te Datenpunkt, d.h. die i-te Dateninstanz).

Stefan Bosse - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN :: Training

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

Stefan Bosse - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN :: Training

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

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

Stefan Bosse - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN :: Multiklassen SVM

Multiklassen SVM

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

Stefan Bosse - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN :: R SVM (custom)

R SVM (custom)

model <- svm(
    x = data.frame, 
    y? = vector, # scaled to [-1,1]?
    formula? = y ~ x,
    # 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 = string|list, # linear, rbf, .. list(type= 'rbf', sigma= 0.5) .. 
    # list( type = "polynomial", c =  1, d = 5=
)

Stefan Bosse - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN :: Beispiel

Beispiel

Stefan Bosse - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN :: Künstliche Neuronale Netze

Künstliche Neuronale Netze

• Ein Künstliches Neuronales Netz (KNN) ist ein gerichteter Graph bestehend aus einer Menge von Knoten N und Kanten E die die Knoten verbinden
  • Knoten: Neuron oder Perzeptron mit einem oder mehreren Eingängen I und einem Ausgang o; Berechnungsfunktion g(I): I → o
  • Kanten: Gewichteter Datenfluss vom Ausgang eines Neurons zum Eingang eines anderen (oder des selben) Neurons

Stefan Bosse - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN :: Künstliche Neuronale Netze

• Zusammengefasst ausgedrückt:

$$\begin{gathered} M(X):X \to Y,X = \{ {x_i}\} ,Y = \{ {y_j}\} \hfill \\ KNN = \left\langle {{N_x},{N_d},{N_y},E} \right\rangle \hfill \\ {N_x} = \{ {n_i} : n_i \leftrightarrow \{x_j\} \} ,{N_d} = \{ n_d: n_i \leftrightarrow n_j\}, {N_y} = \{ {n_k}: n_k \leftrightarrow y_k\} \hfill \\ n = g(\vec{p},\vec{w},b): \vec{p}\rightarrow o = f(\sum_i w_ip_i+b) \hfill \\ E = \{ {e_{ij}}:{n_i} \mapsto {n_j}w_{ij} \} \hfill \ \end{gathered}$$

• f ist eine Transferfunktion die die akkumulierten Eingangswerte auf den Ausgangswert o abbildet, und g ist dann die gewichtete und akkumulative Transferfunktion

Stefan Bosse - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN :: Künstliche Neuronale Netze

• Unterschied (künstliches) Neuron und Perzeptron:
  • Ein Neuron ist immer eine Elementarzelle
  • Ein Perzeptron kann ein einzelnes Neuron oder ein Netzwerk aus Neuronen beschreiben
• Daher gibt es:
  • Single Layer Perceptron (SLP) → Nur Eingangs- N_x und Ausgangsneuronen N_y
  • Multi Layer Perceptron (MLP) → + Innere Neuronen N_d

Stefan Bosse - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN :: Das Neuron

Das Neuron

15 Ein einzelnes Neuron mit einem einzelnen Eingang p und einem Ausgang o. w ist ein Gewichtungsfaktor (ein Gewicht für eingehendes p) und b ist ein Bias (Offset)

Stefan Bosse - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN :: Das Mehreingangsneuron

Das Mehreingangsneuron

15 Ein einzelnes Neuron mit einem Eingangsvektor p und einem skalaren Ausgang o. w ist ein Gewichtungsfaktorvektor (ein Gewicht für eingehendes p) und b ist ein Bias (Offset)

Stefan Bosse - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN :: Neuronale Netze und Matrizen

Neuronale Netze und Matrizen

• Neuronale Netze werden durch eine Graphenstruktur (statische Parameter) und mathematisch durch Matrizen (dynamische Parameter) beschrieben:

15 Ein einzelnes Neuron mit einem Eingangsvektor p und einem skalaren Ausgang o. w ist ein Gewichtungsfaktorvektor (ein Gewicht für eingehendes p) und b ist ein Bias (Offset); jetzt in Matrizenform (Annotation)

Stefan Bosse - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN :: Schichten von Neuronalen Netzen

Schichten von Neuronalen Netzen

• I.A. werden Neuronen von neuronalen Netzen in Schichten (Layer) angeordnet und gruppiert
  • Günstig für Matrixalgebra
  • Aber nicht notwendig!

15

Stefan Bosse - Automatische Schadensdiagnostik - Modul E Regressionsverfahren, SVM und KNN :: Struktur eines KNN

Struktur eines KNN

15