PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul H: Support Vector Machines und Zustandsbasierte Netze

Support Vector Machines

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. LS Minimierung)

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

SVM sind (zunächst) lineare Klassifikatoren!

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul H: Support Vector Machines und Zustandsbasierte Netze

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

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul H: Support Vector Machines und Zustandsbasierte Netze

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)

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul H: Support Vector Machines und Zustandsbasierte Netze

Training

• Das Lernen von w und γ erfordert die Berechnung des Abstandes von allen Dateninstanzen 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

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul H: Support Vector Machines und Zustandsbasierte Netze

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

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul H: Support Vector Machines und Zustandsbasierte Netze

• D.h. SVM zu trainieren ist das Minimierungsproblem:

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

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

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul H: Support Vector Machines und Zustandsbasierte Netze

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

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul H: Support Vector Machines und Zustandsbasierte Netze

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

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul H: Support Vector Machines und Zustandsbasierte Netze

Multiklassen SVM

Jedes Multiklassenproblem mit m verschiedenen (diskreten) Klassenwerten kann auf m binäre Klassifikationsprobleme transformiert werden

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

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul H: Support Vector Machines und Zustandsbasierte Netze

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

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul H: Support Vector Machines und Zustandsbasierte Netze

Beispiel

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul H: Support Vector Machines und Zustandsbasierte Netze

Sugiyama, ItSML, pp 303

Zusammenfassung

• 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

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul H: Support Vector Machines und Zustandsbasierte Netze

Zustandsbasierte Netze

Bisher wurden nur "vorwärtsgerichtete" ANN betrachtet (Feed forward/ FF-ANN)

Die Ausgänge von FF-ANN hängen nur von aktuellen Eingängen ab!

Rückgekoppelte ANN (Recurrent / RNN) besitzen Zusatnd und Gedächtnis!

Eignung für Daten- und Zeitserienprädiktion!

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul H: Support Vector Machines und Zustandsbasierte Netze

Wiederholung: FF-ANN

• Ein vorwärtsgekoppeltes ANN (Feed forward) besteht aus Neuronen die jeweils durch Funktionen f(i):i → o repräsentiert werden können.

• Die Funktionen f werden als azyklischer gerichteter Graph dargestellt (also das NN), d.h., kein Neuron hat ein Eingangssignal von nachfolgenden Neuronen (die das Ausgangssignal dieses Neurons enthalten)

D.h: Das aktuelle Ausgangssignal y eine FF-ANN hängt nur von den aktuellen Eingangssignalen x ab!

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul H: Support Vector Machines und Zustandsbasierte Netze

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul H: Support Vector Machines und Zustandsbasierte Netze

Recurrent ANN: Die Rückkopplung

• Ausgänge von Ausgangs- oder inneren Neuron werden auf Eingänge von vorherigen Neuronen gekoppelt

• Dadurch werden die Netzwerke zustandsbasiert, d.h., die aktuellen Ausgänge hängen neben den aktuellen Werten der Eingänge von der Historie der Werte von Ein- und Ausgängen ab!

• Recurrent ANN (RNN) sind durch hohe "Instabilität" schwierig mit gradientenbasierten Verfahren zu trainieren!

• Daher im Laufe der Zeit verbesserte Architekturen wie LSTM oder GRU Netzwerke

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul H: Support Vector Machines und Zustandsbasierte Netze

LSTM Netzwerke

• Long-short-term Memory (LSTM) Netzwerke bilden eine bekannte Architektur die:
  • Für die Daten- und zeitserienprädiktion verwendbar sind
  • Mit gradientenbasierten Trainingsverfahren einigermaßen stabil (konvergent) trainiert werden können

Daten- und Zeitserien

• Es sei {x_n}^t eine Serie von Eingabedaten (z.B. zeitaufgelöstes Sensorsignal einer Ultraschallmessung), d.h. {x_n}={x₁,x₂,..,x_t}
• Die einzelnen Werte (skalar oder vektoriell) sind aufeinanderfolgend → Ordnungsrelation

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul H: Support Vector Machines und Zustandsbasierte Netze

$$f_\delta(\{s_i\}_i^n,n): {s_{n-m},s_{n-m+1},..s_n} \rightarrow s_{n+\delta}$$

Datenserie und Prädiktion s(n+δ)

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul H: Support Vector Machines und Zustandsbasierte Netze

• Neben der Prädiktion von "zukünftigen" Entwicklungen einer Variable x_i kann auch eine zukünftige Prognostik einer anderen Zielvariable y_i erfolgen:

$$f_\delta(\{x_i\}_i^n,n): \{x_{n-m},x_{n-m+1},..x_n\} \rightarrow y_{n+\delta}$$

• Etwaige Zielvariablen könnten aus dem Signal abgeleitete Eigenschaften (Merkmale) sein:
  • Schadensinformation
  • Änderung einer zweiten Sensorvariable
  • Zustandsvariable
  • Veränderung von Betriebsbedingungen
  • Prozessparameter

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul H: Support Vector Machines und Zustandsbasierte Netze

Netzwerkarchitekturen

(Oben) Die Datenserie kann sequentiell (in ein RNN/LSTM) oder auch (Unten) parallel in ein FNN eingegeben werden

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul H: Support Vector Machines und Zustandsbasierte Netze

LSTM Zelle

• Eine LST Zelle besteht aus:

  • Einer "Speicherzelle"
  • Mehreren Gattern die aktiv Verbindungen (Kanten) zwischen Neuronen steuern, d.h., effektiv das Kantengewicht in Abhängigkeit von Ausgangswerten von Neuronen verändern /Ventile/

• Ein wichtige Rolle bei der Speicherung vergangener Daten (Gedächnis) ist das Vergessen gesteuert durch das "Forget Gate"

Beispiel für eine "gedämpfte" Gedächnisfunktion: Ein Tiefpassfilter 1. Ordnung

$$f(x,n)=f(n-1)\sdot\alpha+\beta \sdot x$$

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul H: Support Vector Machines und Zustandsbasierte Netze

• Der Parameter β=(0,1) bestimmt den Einfluß neuer Werte x und der Parameter α=(0,1) bestimmt den Einfluß alter Werte (Vergessen); i.A. α=1-β

Aufbau einer LSTM Zelle mit zentraler Speicherzelle (Neuron) und den Gattern

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul H: Support Vector Machines und Zustandsbasierte Netze

LSTM Demo

• Lernen einer Prädiktorfunktion für Datenserien nach der Sinusfunktion mit LSTM Netzwerk:

$$f_\delta(x_n): x_n \rightarrow x_{n+\delta}$$

• Für jedes δ={1,2,..,m} muss eine eigene Prädiktorfunktion f_δ erzeugt und trainiert werden

• Konfiguration des Netzwerks: [1,l,1], wobei l={1,2,..} die Anzahl der LSTM Zellen in der inneren Schicht ist.

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul H: Support Vector Machines und Zustandsbasierte Netze

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul H: Support Vector Machines und Zustandsbasierte Netze

Zusammenfassung

• Diskrete Daten- und Zeitserien x(i) kommen in der Mess- und Prüftechnik als Sensorsignal häufig vor, aber auch bei

  • Wirtschaftsdaten (Aktienkurse), Wetterdaten, Klimadaten, usw.

• Die Vorhersage von unbekannten zukünftigen Datenwerten aus historischen bekannten Datenwerten erfordert zustandsbasierte Prädiktorfunktionen sofern es

  • keinen ausgewiesenen Start- und Endpunkt gibt (also sequentielle Aktivierung von M).
  • Gibt es ausgewiesene Start- und Endpunkte der Serie kann auch eine zustandslose Prädiktorfunktion verwendet werden (parallele Aktivierung einer Auswahl von Datenpunkten)

PD Stefan Bosse - Maschinelles Lernen und Datenanalyse - Modul H: Support Vector Machines und Zustandsbasierte Netze

• Die Long Short Term Memory Zelle ist eine bekannte Architektur für eine RNN PF mit Zustand (Speicher)

• Problem beim Trainieren von RNN ist Instabilität und der Zustandsspeicher (wirkt sich auf Fehlerberechnung ungünstig aus)