Navigation

Von Bäumen, Netzen und Maschinen

Drei Klassifizierungsverfahren

In einem vergangenen Post habe ich bereits über künstliche Intelligenz und maschinelles Lernen im Allgemeinen gesprochen. In diesem Artikel möchte ich nun drei ganz konkrete Verfahren des maschinellen Lernens vorstellen, genauer gesagt drei Klassifizierungsverfahren.

Klassifizierung ist ein Teilbereich des überwachten Lernens, bei dem aus einer Reihe von Eingabe-Ausgabe-Paaren eine Regel abgeleitet werden soll, die Eingabe auf Ausgabe abbildet.1 Diese Lernaufgabe wird im maschinellen Lernen auch „Funktionenlernen aus Beispielen“ genannt,2 die gelernten Regeln häufig „Modelle“. Bei den Eingabedaten spricht man auch von „feature variables“ oder einem Merkmalsvektor, bei den Ausgabedaten von „target variables“,3 die im Falle von Klassifizierung aus einer endlichen Wertemenge aus zuzuordnenden „Klassen“ oder „Labels“ stammen.1

Klassifizierungs-Algorithmen bestehen in der Regel aus drei Phasen: In einer Lern- oder Trainingsphase werden Regeln aus Beispielen (beschriftete Daten aus Eingabedaten mit zugeordneten Ausgabedaten), auch Trainingsdaten genannt, abgeleitet. Diese Regeln werden in einer Test- oder Validierungsphase auf andere, ebenfalls beschriftete Daten angewendet, damit geprüft werden kann, wie gut die gelernten Regeln bei anderen Eingabewerten funktionieren.3 Danach können die so trainierten Klassifikatoren in der praktischen Anwendung auf neue, unbeschriftete Daten angewendet werden. Dies ist ein Thema, mit dem sich die Literatur in der Regel nicht mehr beschäftigt.

Im Folgenden sollen drei großen Gruppen der Klassifizierungs-Algorithmen sowie ihre jeweilige Funktion beschrieben werden. Zuvor soll jedoch noch ein wichtiges allgemeines Konzept der Klassifizierung eingeführt werden. Lösungen für Klassifikationsaufgaben haben immer das Risiko der Überanpassung (englisch „Overfitting“), bei der die Entscheidungs-Regeln zu stark auf die Trainingsdaten angepasst wurden und somit bei den Validierungsdaten und damit in der späteren praktischen Anwendung nicht ausreichend gut funktionieren.

We will say that a hypothesis overfits the training examples if some other hypothesis that fits the training examples less well actually performs better over the entire distribution of instances.4

Abb. 1: Zu komplexes Modell

Abb. 1: Zu komplexes Modell

Abb. 2: Zu einfaches Modell

Abb. 2: Zu einfaches Modell

Eine Veranschaulichung des Konflikts aus Überanpassung und zu starker Generalisierung ist in den Abbildungen 1 und 2 dargestellt. Die grüne Kurve beschreibt die tatsächliche Verteilung der Daten in der Realität, die grünen Punkte die zum Training verwendeten Beispiele. Die rote Kurve stellt die gelernte Verteilung der Daten dar, die in Abbildung 1 zwar sehr nah an den Beispieldaten ist, aber nicht der realen Verteilung der Daten entspricht. In Abbildung 2 hingegen ist die gelernte rote Kurve zu einfach, um die tatsächliche Verteilung der Daten ausreichend gut anzunähern.

Entscheidungsbäume

Entscheidungsbäume gehören zu den einfachsten Methoden des maschinellen Lernens und den intuitivsten Verfahren zur Klassifizierung.13 Sie funktionieren, indem sie die Menge möglicher Eingabewerte durch hierarchische Unterteilung so weit eingrenzen, bis eine Zuordnung einer bestimmen Klasse möglich ist.3 Ein einfacher Entscheidungsbaum ist in Abbildung 3 abgebildet. Um ein neues Eingabebeispiel zu klassifizieren, wird dem Baum entsprechend der an Kanten festgelegten Bedingungen gefolgt, bis man an einem Endknoten eine Klasse erhält.4

Abb. 3: Ein einfacher Entscheidungsbaum: „Soll ich einen Spaziergang machen?“

Abb. 3: Ein einfacher Entscheidungsbaum: „Soll ich einen Spaziergang machen?“

Grundsätzlich können die unterschiedlichen Attribute der Eingabedaten in jedem Pfad des Baumes in beliebiger Reihenfolge vorkommen. So könnte in Abbildung 3 auch „Aussicht“ statt „Temperatur“ der Wurzelknoten des Baums sein. Da dies jedoch in exponentiellem Berechnungsaufwand resultieren würde, werden Entscheidungsbäume in einem „top-down“ genannten Verfahren von der Baumwurzel gebildet, sodass für jeden Knoten das Attribut als Entscheidungsvariable verwendet wird, das die „größte Verbesserung der Klassifikationsleistung erbringen würde“.2

Um diese Verbesserung messbar zu machen, wurden verschiedene Entscheidungsgrößen entwickelt, die die Basis unterschiedlicher Typen von Entscheidungsbäumen bilden. Einer der ersten Entscheidungsbäume verwendete beispielsweise die Reduktion der Entropie innerhalb der mittels der neuen Entscheidungsvariable eingeteilten Untergruppen als einen solchen Maßstab. Der weit verbreitete CART-Entscheidungsbaum (CART steht dabei für Classification and Regression Tree) verwendet den Gini-Index als Maßstab für Ungleichverteilung:3

$$ \operatorname{Gini}(X_i):=\sum_{y\in Y}{p_{iy}(1-p_{iy})}=1-\sum_{y\in Y}{p_{iy}^2} $$

\(p_{iy}\) ist dabei die Wahrscheinlichkeit, zufällig den Wert \(y\) aus dem Wertebereich \(Y\) in der Menge \(X_i\) auszuwählen, \(p_{iy}(1-p_{iy})\) entsprechend die Wahrscheinlichkeit, ihn zufällig falsch zu klassifizieren – was wahrscheinlicher ist, wenn die Werte eher ungleich verteilt sind. Ein Wert nahe \(0\) bedeutet eine also gleichmäßige Verteilung der Werte aus dem Wertebereich \(Y\) in der Menge \(X_i\), ein Wert nahe \(1\) eine Ungleichverteilung. Für die Entwicklung eines Entscheidungsbaums sind jene Mengen besser, deren Werte gleichverteilt sind, wodurch sie besser zu einer Klasse zugeordnet werden können. Der Informationsgewinn \(\Delta F\), den es bei jeder Aufteilung des Entscheidungsbaums zu maximieren gilt, wird wie folgt definiert:3

$$ \Delta F_{\operatorname{Gini}}(S):=\operatorname{Gini}(X) - \sum_{i\in S}{\frac{|X_i|}{|X|}\operatorname{Gini}(X_i)} $$

\(X\) ist dabei die Menge der Werte, die es an einem Knoten des Entscheidungsbaums aufzuspalten gilt, \(S\) das Kriterium, nach dem Teilmengen \(X_i\) aus \(X\) gebildet werden. Ziel ist es, das Kriterium \(S\) auszuwählen, bei dem \(\Delta F_{\operatorname{Gini}}\) maximal ist.3

Entscheidungsbäume neigen jedoch zur Überanpassung, da der Trainingsfehler auf einer bestimmten Menge Trainingsdaten minimiert wird. Die trainierten Bäume werden daher in der Regel mit einer anderen Datenmenge (Validierungsdaten) in einem zweiten Schritt „gestutzt“ (Pruning).2 Bei CART-Entscheidungsbäumen wird ein Verfahren verwendet, das Teilbäume anhand eines Komplexitäts-Nutzen-Verhältnisses bewertet und bei Bedarf durch einzelne Blätter ersetzt.3

Ein Problem von Entscheidungsbäumen ist ihre strukturelle Instabilität. Bereits kleine Veränderungen in den Trainingsdaten können wegen des Top-Down-Ansatzes zu einer vollkommen anderen Reihenfolge der Entscheidungs-Attribute auf den einzelnen Ebenen des Baumes führen. Mit Methoden wie Bagging und Boosting werden daher mehrere Entscheidungsbäume auf unterschiedlichen Teilmengen der Trainingsdaten trainiert. Bei der Anwendung der so trainierten Bäume auf neue zu klassifizierende Daten findet schlussendlich eine (gewichtete) Mehrheitsentscheidung statt:2 Klassifizieren zum Beispiel 90 Bäume die Daten als „Klasse A“ und nur 10 die Daten als „Klasse B“, wird „Klasse A“ als Gesamtentscheidung angenommen. Random Forests sind eine von Leo Breiman entwickelte Umsetzung unter anderem des Bagging-Verfahrens, bei dem Overfitting durch die große Zahl der Bäume vermieden wird.56

Neuronale Netze

Ein künstliches neuronales Netz ist ein Graph aus miteinander verbundenen Einheiten, die ein mathematisches Modell biologischer Neuronen repräsentieren.3 Eine einzelne dieser Einheiten, wie sie in Abbildung 4 dargestellt ist, besteht dabei aus mehreren Eingangssignalen \(s_1, s_2, \ldots, s_J\), die multipliziert mit Übertragungsgewichten \(w_{i1}, w_{i2}, \ldots, w_{iJ}\) zu einem Potential \(u_i\) aufsummiert werden. Dieses wird mit einer Aktivierungsfunktion \(\Phi\) in ein Ausgabesignal, die Erregung \(e_i\), umgewandelt.21.

Abb. 4: Ein künstliches Neuron. Abbildung aus [3]

Abb. 4: Ein künstliches Neuron. Abbildung aus [3]

Durch Verknüpfung der künstlichen Neuronen können so beliebig komplexe Strukturen konstruiert werden. Durch die Definition einer einfachen Aktivierungsfunktion

$$ \Phi(u) = \begin{cases} u\ge\vartheta &: 1\\ \text{sonst} &: 0 \end{cases} $$

und geschickte Wahl der Gewichte \(w_{ij}\) sowie des Schwellwerts \(\vartheta\) kann bereits mit einem einzelnen Neuron das logische UND beziehungsweise ODER dargestellt werden.5 Fügt man vor die Ebene des Ausgabe-Neurons eine weitere Ebene mit sogenannten „versteckten Neuronen“ (einen hidden layer), so lassen sich bereits beliebige Boole’sche Ausdrücke darstellen und beliebige Funktionen annähern.7

Abb. 5: Ein Multi Layer Perceptron mit sigmoidaler Aktivierungsfunktion. Abbildung aus [4]

Abb. 5: Ein Multi Layer Perceptron mit sigmoidaler Aktivierungsfunktion. Abbildung aus [4]

Die Einführung von Ebenen versteckter Neuronen, die jeweils nur vollständig mit der darauffolgenden Schicht verbunden sind (feedforward), wie es in Abbildung 5 dargestellt ist, ermöglicht die Durchführung selbst komplexer Klassifikationsaufgaben. Man spricht von „multi-layer feedforward networks“ oder Multi Layer Perceptrons (MLPs), sowie Deep Learning.3

Zur Bestimmung der Gewichte \(w_{ij}\) wurden verschiedene Lernregeln entwickelt. Effizientes Training von MLPs wurde erst 1986 durch die Entwicklung von Back-Propagation möglich,83 das auf Gradientabstieg (gradient descent) basiert und bereits 1974 durch Paul Werbos vorgeschlagen wurde.79 Ziel ist die Minimierung des Fehlers \(E\) an den Neuronen \(i\) des Output Layers, wobei \(t_i\) die entsprechenden Trainingswerte sind. \(E\) wird wie folgt definiert:24

$$ E := \frac{1}{2}\sum_i{\left(e_i-t_i\right)^2}= \frac{1}{2}\sum_i{\left[\Phi\left(\sum_j{w_{ij}s_j}\right)-t_i\right]^2} $$

Dieser Fehler \(E\) ist nun abhängig von der Wahl der Gewichte \(w_{ij}\). Jedes einzelne Gewicht \(w_{pq}\) wird dann iterativ gemäß der Ableitung des Fehlers nach dem entsprechenden Gewicht angepasst:34

$$ \begin{aligned} w_{pq}&\leftarrow w_{pq}+\nabla w_{pq}\\ \nabla w_{pq}&=-\eta\frac{\partial E}{\partial w_{pq}} \end{aligned} $$
Abb. 6: Veranschaulichung des Gradientabstiegs beim Back-Propagation-Algorithmus

Abb. 6: Veranschaulichung des Gradientabstiegs beim Back-Propagation-Algorithmus

In der ersten Gleichung ist die Veränderung \(\nabla w_{pq}\) angegeben, die in der zweiten Gleichung iterativ auf das Gewicht \(w_{pq}\) angewendet wird. \(\nabla\) ist dabei der Nabla-Operator, der dazu verwendet wird, den Gradienten anzugeben. \(\eta\) ist dabei ein beim Training zu wählender Faktor, der die Lerngeschwindigkeit bestimmt. In Abbildung 6 ist ein Iterationsschritt für ein Gewicht visualisiert. Für Gewichte des Output Layers lässt sich die partielle Ableitung trivial bestimmen. Es gilt2

$$ \frac{\partial E}{\partial w_{pq}} = (e_p-t_p)\Phi'(u_p)s_q =: -\delta_ps_q. $$

Um die partiellen Ableitungen für die Gewichte \(\tilde w_{pq}\) eines Hidden Layers zu bestimmen, muss in der Gleichung für das Eingangssignal \(s_j\) des Output Layers die Formel zu dessen Berechnung aus dem Hidden Layer \(s_j = \Phi(\sum_k \tilde w_{jk}s_k)\) eingesetzt werden, wobei \(s_k\) die Eingangssignale des Hidden Layers sind. Durch Umformen erhält man2

$$ \frac{\partial E}{\partial\tilde w_{pq}} = -\sum^I_{i=1} \delta_iw_{ip}\Phi'(\tilde u_p)s_q =: -\tilde\delta_ps_q. $$

Wie leicht ersichtlich ist, unterscheiden sich die Terme zur Berechnung der partiellen Ableitung des Fehlers \(E\) für Output Layer und Hidden Layer nur in \(\delta_p\) bzw. \(\tilde\delta_p\). \(\tilde\delta_p\) enthält insbesondere jeweils die \(\delta_i\) des nachfolgenden Layers, sodass alle \(\delta_p\) und \(\tilde\delta_p\) hierarchisch vom Output Layer bis zum vordersten Hidden Layer berechnet werden können (wodurch sich der Name „Back-Propagation“ ergibt). Dies funktioniert theoretisch mit beliebig vielen Hidden Layers.

Wichtige Voraussetzung für Back-Propagation ist Differenzierbarkeit der Aktivierungsfunktion \(\Phi(u)\), wobei trotzdem eine „schrittartige“ Struktur wie im oben vorgestellten naiven Ansatz angestrebt werden soll. In der Praxis (und zum Beispiel in Abbildung 5) wird häufig eine Sigmoidfunktion wie etwa die logistische Funktion verwendet:321

$$ \Phi(u)=\frac{1}{1+e^{-u}} $$

Bei Back-Propagation muss beachtet werden, dass insbesondere ein ungeschickt gewähltes \(\eta\) dazu führen kann, dass das Training nur in einem (unter Umständen sehr schlechten) lokalen Minimum statt eines gewünschten globalen resultiert. Eine Erweiterung des Back-Propagation-Algorithmus führt daher den Momentum-Faktor ein, der beim Gradientabstieg auch die Veränderung der Gewichte bei der letzten Iteration einbezieht. Außerdem beeinflussen die initialen Werte der Gewichte \(w_{ij}\) das Trainings-Ergebnis, weswegen sie häufig gemäß der Standardnormalverteilung zufällig belegt werden. Zudem werden die numerischen Eingabedaten häufig normalisiert, sodass sie im Wertebereich von \([-1,1]\) liegen.3

Für kategorische Variablen hat sich das sogenannte „One-Hot“-Encoding etabliert, bei dem pro Eingangssignal eine Klasse existiert. Ist eine Klasse aktiv, ist der Wert des entsprechenden Signals \(1\); der aller anderen ist \(0\). Auch im Output Layer kann diese Kodierung verwendet werden. So wird jene Klasse als ausgewählt angenommen, deren Neuron den größten Ausgabewert hat.3 Da diese Werte in der Praxis jedoch nie eindeutig \(1\) und \(0\) sein werden, können sie auch als Abschätzung der Wahrscheinlichkeit der korrekten Klassifizierung verwendet werden.3

Ein wichtiger Teil beim Training von neuronalen Netzen ist die Vermeidung von Überanpassung durch zu häufige Iteration %Ein Wichtiger Teil? des Back-Propagation-Algorithmus. Eine häufig genutzte Methode ist hierbei die regelmäßige Abschätzung des Klassifizierungs-Fehlers während des Trainings mit einem separaten Satz an Validierungsdaten, um einen geeigneten Zeitpunkt zum Abbruch des Trainings zu finden.321 Weitere Herausforderungen sind die Wahl einer geeigneten Netzstruktur (Anzahl und Größe der Hidden Layer) sowie der Umgang mit zu kleinen Mengen an Trainingsdaten bei zu vielen Parametern, was in einer unverhältnismäßig großen Zahl an anzupassenden Gewichten resultiert.3

Neuronale Netze sind ein sehr mächtiges Werkzeug, das sich in vielen Bereichen einsetzen lässt. So lassen sich MLPs auch für Regressionsprobleme verwenden und mit dem Hinzufügen von „Convolutions“ genannten Schichten lassen sich unter anderem Bilderkennungsprobleme effizient lösen.7 Die flexible Verschaltung von Neuronen ermöglicht darüber hinaus Netzwerke, bei denen sich Verbindungen nicht nur vorwärts, sondern auch wieder zurück zu Neuronen in vorigen Schichten erstrecken. Solche rekurrenten neuronalen Netze ermöglichen die Simulation von Gedächtnis-Prozessen, was sich zum Beispiel zur Vervollständigung von Mustern nutzen lässt.71 Darüber hinaus können neuronale Netze auch im Bereich des unüberwachten Lernens und des Verstärkungslernens eingesetzt werden. Die vielfältige Nutzung in Forschung und Praxis ist starkes Indiz für die Vorteile neuronaler Netze.10

Nachteil neuronaler Netze ist insbesondere die schwere Verständlichkeit der generierten Modelle4 und die komplexe Anpassung der Struktur und Parameter des Netzes13 sowie die Dauer des Trainings.4

Support Vector Machines

Support Vector Machines (deutsch vereinzelt auch „Stützvektormethode“2) sind der neueste und zurzeit „populärste Ansatz für überwachtes Lernen“.1 Sie wurden in den 1990ern von Vladimir Vapnik et al. (Dieser Artikel verwendet die englische Transkription des russischen Namens) mit der Motivation entwickelt, die Überanpassung bestehender Modelle wie Entscheidungsbäume und neuronale Netze zu vermeiden.311

Die Idee hinter Support Vector Machines ist es, Klassifizierungsaufgaben nicht durch „Lernen“ einer Funktion (wie etwa bei neuronalen Netzen), sondern durch „Konstruktion“ einer idealen Trennlinie zu lösen. Die Trainingsdaten \(S\) in der Form

$$ S_i=\left\{\left(\vec x_i, y_i\right);\,\vec x_i\in\mathbb R^n, y_i=\pm 1\right\}, $$

wie sie in Abbildung 7 beispielhaft für \(n=2\) dargestellt sind, und sollen durch eine Hyperebene \(\mathcal H\), definiert durch eine lineare Funktion \(h(\vec x) = \vec w^\intercal \vec x + b = 0\) mit einem Vektor an Gewichten \(\vec w\), so voneinander getrennt werden, dass der Mindestabstand \(M\) der Punkte \(\vec x\) von \(\mathcal H\) maximal ist. Man spricht in diesem Fall vom Maximum Margin Classifier.31

Abb. 7: Zwei Klassen von Punkten, die durch eine Hyperebene getrennt werden

Abb. 7: Zwei Klassen von Punkten, die durch eine Hyperebene getrennt werden

Der Abstand eines Punktes \(\vec x\) von \(\mathcal H\) lässt sich definieren als

$$ \text{Abstand}(\vec x, \mathcal H)=\frac{|\vec w^\intercal \vec x + b|}{\|\vec w\|} $$

wobei \(\|\cdot\|\) ein Abstandsmaß wie zum Beispiel die euklidische Norm \(\|\vec w\|=\sqrt{\vec w^2}\) ist.2 \(\vec w^\intercal\) drückt aus, dass der Vektor \(\vec w\) transponiert wird, sodass das Produkt \(\vec w^\intercal\vec x\) ein Skalar ist. Für Punkte \(\vec x\) auf der richtigen Seite \(y\) von \(\mathcal H\) gilt3

$$ |\vec w^\intercal \vec x + b| = y(\vec w^\intercal \vec x + b). $$

Die Maximierung des Abstandes lässt sich also als das folgende Optimierungsproblem formulieren:

$$ \begin{array}{rl} \text{Maximiere}&M\\ \text{Bedingung}&\forall i: \dfrac{y_i(\vec w^\intercal \vec x_i + b)}{\|\vec w\|}\ge M \end{array} $$

Das Problem an dieser Formulierung ist jedoch, dass durch Skalierung der Hyperebene unendlich viele optimale Lösungen existieren. Daher wird diese normiert, indem \(M\|\vec w\|=1\) gesetzt wird. Wird \(M\) maximiert, muss also \(\|\vec w\|\) minimiert werden. Durch Multiplikation der Nebenbedingungen mit \(\|\vec w\|\) ergibt sich somit

$$ \begin{array}{rl} \text{Minimiere}&\|\vec w\|\\ \text{Bedingung}&\forall i: y_i(\vec w^\intercal \vec x + b)\ge 1 \end{array} $$

In der Literatur wird der zu minimierende Term häufig in einen äquivalenten Ausdruck umformuliert, was die spätere Berechnung vereinfacht, da zum Beispiel der Wurzelterm der euklidischen Norm entfällt.311

$$ \begin{array}{rl} \text{Minimiere}&\frac{1}{2}\|\vec w\|^2\\ \text{Bedingung}&\forall i: y_i(\vec w^\intercal \vec x + b) \ge 1 \end{array} $$

Dieses Gleichungssystem kann mit Hilfe von Lagrange-Relaxion gelöst werden,311 auf die hier jedoch nicht näher eingegangen werden soll. Die Lösung besteht aus dem Parameter \(b\) sowie einem Vektor \(\vec\alpha\), aus dem sich unter Zunahme der verwendeten Trainingsdatensätze \((\vec x_i,y_i)\) der Gewichtsvektor \(\vec w\) bestimmen lässt.3

In Abbildung 7 ist leicht erkennbar, dass im Gegensatz zu den bisher besprochenen Verfahren nicht alle Trainingsdaten für die exakte Position der Hyperebene verantwortlich sind, sondern nur diejenigen, die nah an der trennenden Hyperebene liegen. Diese Punkte werden Support Vectors genannt. Nur für einen Support Vector \(\vec x_i\) ist der Wert \(\alpha_i\) ungleich \(0\).

Dieser Ansatz der Support Vector Machines führt zu einer bedeutenden Einschränkung für die Daten: Sie müssen durch eine Hyperebene trennbar, „linear separabel“12 sein. Dies muss jedoch aus zwei Gründen nicht immer der Fall sein. Diesen kann mit unterschiedlichen Maßnahmen begegnet werden:

Abb. 8: Fehlerhafte/verrauschte Trainingsdaten

Abb. 8: Fehlerhafte/verrauschte Trainingsdaten

Abb. 9: Nicht linear trennbare/separable Daten

Abb. 9: Nicht linear trennbare/separable Daten

Soft-Margin

Wie in Abbildung 8 dargestellt, ist es möglich, dass in den Trainingsdaten Fehler vorliegen, zum Beispiel weil sie verrauscht sind. Damit die Berechnung der Hyperebene nicht scheitert, wird eine Schlupfvariable \(\xi(\vec w,b; \vec x_i, y_i)\) definiert, die fehlerhafte Daten nicht verbietet, aber bestraft.3 Man spricht hierbei von Soft-Margin-Klassifikatoren.1 Das Optimierungsproblem kann weiterhin analog mittels Lagrange-Relaxion gelöst werden.

Kernel-Trick

Wie in Abbildung 9 dargestellt, ist es möglich, dass die Daten ihrer Struktur nach schlicht nicht linear separierbar sind. Hier wird ein Kernel-Trick genanntes Verfahren angewendet: Die Datenpunkte \(\vec x\) werden mit Hilfe einer nicht-linearen Funktion \(\Phi(\vec x)\) in einen (in der Regel) höherdimensionalen Raum abgebildet, in welchem sie linear trennbar sind (wie zum Beispiel in Abbildung 10). Durch Rücktransformation der in diesem höherdimensionalen Raum gelernten Hyperebene können sie beliebigen nicht-linearen Entscheidungs-Grenzen entsprechen.23 Diese Transformation lässt sich bei der Lösung des Optimierungsproblems in Form einer sogenannten Kernel-Funktion \(K(\vec x, \vec z)=\Phi(\vec x)^\intercal\Phi(\vec z)\) einsetzen, sodass zeitaufwendige Berechnungsschritte vermieden und sogar Räume mit unendlich vielen Dimensionen verwendet werden können.31

Abb. 10: Mit (\Phi(\vec x) = [x_1^2\ x_2^2]^\intercal) transformierte Daten

Abb. 10: Mit \(\Phi(\vec x) = [x_1^2\ x_2^2]^\intercal\) transformierte Daten

Support Vector Machines, wie sie bisher beschrieben wurden, erlauben nur die Unterscheidung zweier unterschiedlicher Klassen. Es existieren jedoch verschiedene Verfahren, mit denen auch Klassifizierungsaufgaben mit mehreren Ziel-Klassen durch die Verknüpfung mehrerer Support Vector Machines gelöst werden können.3 Auf eine nähere Beschreibung dieser Verfahren wird hier jedoch verzichtet.

Vorteil von Support Vector Machines ist ihre gute Generalisierung31 sowie ihre Anwendbarkeit bei einer sehr großen Zahl an Merkmalen.2 Nachteil ist die Notwendigkeit der manuellen Auswahl eines geeigneten Kernels bei nicht linear trennbaren Daten.

Fazit

Ich hoffe, ich habe Sie, werte Leser, mit den mathematischen Grundlagen der einzelnen Verfahren nicht zu sehr abgeschreckt und konnte Ihnen stattdessen die Grundprinzipien, Vorteile und Nachteile von drei sehr wichtigen Methoden innerhalb der künstlichen Intelligenz in fundierter Form nahebringen.

Ich möchte nicht verschweigen, dass es noch einige weitere Verfahren innerhalb des maschinellen Lernens gibt – K-Nearest Neighbor und Naive Bayes zum Beispiel. Den mathematisch interessierten Lesern kann ich eine mehrwöchige, kostenlose Online-Schulung von Andrew Ng, der unter anderem das Projekt Google Brain gegründet hat, nur nahelegen.13 Hier werden zwar auch bei weitem nicht alle Themen besprochen, dafür wird jedoch sehr viel Wert auf die Herleitung und die Grundlagen gelegt.

Zum Abschluss kann ich Ihnen nur empfehlen, einmal durch eines der hier angesprochenen Übersichtsbücher durchzublättern (so es denn in der örtlichen Bibliothek verfügbar ist), um zu sehen, wie umfangreich dieses Thema, das unseren Alltag immer tiefer durchdringt, doch ist.


  1. Stuart Russel; Peter Norvig. Künstliche Intelligenz: Ein moderner Ansatz. 3., aktualisierte Auflage. München: Pearson, 2012.
  2. Günther Görz, Hrsg. Handbuch der Künstlichen Intelligenz. 5., überarbeitete und aktualisierte Auflage. München: Oldenbourg, 2014.
  3. Charu C. Aggarwal, Hrsg. Data Classification: Algorithms and Applications. Boca Raton: CRC Press, 2015.
  4. Tom M. Mitchell. Machine Learning. New York, NY, USA: McGraw-Hill, 1997.
  5. Leo Breiman. „Random Forests“. In: Machine Learning 45.1 (2001), S. 5–32.
  6. Adele Cutler; D. Richard Cutler; John R. Stevens. „Random Forests“. In: Ensemble Machine Learning: Methods and Applications. Hrsg. von Cha Zhang und Yunqian Ma. Boston, MA: Springer US, 2012, S. 157–175. DOI: 978-1-4419-9326-7_5.
  7. Haohan Wang; Bhiksha Raj. „On the Origin of Deep Learning“. In: CoRR abs/1702.07800 (2017). Link (besucht am 27.03.2017).
  8. Vladimir N. Vapnik. The nature of statistical learning theory. 2. ed. Statistics for engineering and information science. New York: Springer, 2000.
  9. Paul Werbos. „Beyond regression: New tools for prediction and analysis in the behavioral sciences“ Diss. Cambridge, Massachusetts: Harvard University, Aug. 1974.
  10. Terry T. Um Awesome – Most Cited Deep Learning Papers. 2017. Link (besucht am 30.03.2017).
  11. Bernhard E. Boser; Isabelle M. Guyon; Vladimir N. Vapnik. „A Training Algorithm for Optimal Margin Classifiers“. In: Proceedings of the Fifth Annual Workshop on Computational Learning Theory. COLT ’92. Pittsburgh, Pennsylvania, USA: ACM, 1992, S. 144–152. DOI: 10.1145/130385.130401.
  12. Wolfgang Ertel. Grundkurs Künstliche Intelligenz: Eine praxisorientierte Einführung. 1. Auflage. Wiesbaden: Vieweg, 2008.
  13. Andrew Ng Machine Learning. Online-Schulung der Stanford University auf Coursea. Link (besucht am 28.06.2017).

Titelbild: albyantoniazzi (CC BY-NC-SA 2.0)
Ebenfalls erschienen im Neologismus 17-07

Mehr lesen