Quelltext der Seite Verschiedene Techniken für maschinelles Lernen und Deep Learning

<span id="sec:Ver_Tech_ML_DL"></span>
= Verschiedene Techniken für maschinelles Lernen und Deep Learning =

<span id="support-vektor-maschinen"></span>
== Support-Vektor-Maschinen ==

Support-Vektor-Maschinen (support vector machines - SVMs) sind moderne Klassifikatoren. In ihrer ursprünglichen Form können sie auf die Klassifizierung mit zwei Klassen angewendet werden (binären Klassifikator - binary classifier). Die gute Klassifizierungsfähigkeit von SVMs basiert auf der Idee, dass eine Erhöhung der Dimensionalität der Eingabedaten eine bessere Trennbarkeit der Klassen ermöglicht. Je höher die Dimension der Projektion der Eingabedaten, desto größer ist die Wahrscheinlichkeit einer besseren Trennfähigkeit der entsprechenden Hyperebenen. Der Name SVM kommt von den Support-Vektoren, den Feature Vektoren des Trainingssatzes, die am Rand der Klassen im hochdimensionalen Raum liegen. Es stellt sich heraus, dass sie die optimale Entscheidungsfläche vollständig bestimmen.

SVMs werden für verschiedene reale Probleme eingesetzt, darunter unter anderem die Erkennung handschriftlicher Zeichen (hand-written character recognition), die Bildklassifizierung, die Klassifizierung von Satellitendaten (satellite data classification) und Klassifizierungsaufgaben in den Biowissenschaften (classification tasks in biological sciences).

<span id="lineare-svm-mit-linear-trennbaren-klassen"></span>
=== Lineare SVM mit linear trennbaren Klassen ===

Eine SVM ist linear, wenn ihre Entscheidungsfläche im Raum der Eingabevektoren linear ist, also eine Hyperebene ist. Angenommen, der Eingabedaten ist durch die <math display="inline">L</math>-dimensionalen Vektoren <math display="inline">{\bf x}_1, \ldots, {\bf x}_N</math> und ihre entsprechenden Klassenbezeichnungen <math display="inline">y_1,\ldots, y_N</math> gegeben. Die beste Trennfähigkeit kann durch <math display="inline">L-1</math>-dimensionale Hyperebenen erreicht werden. Die Klassen sind linear trennbar, wenn zwischen den Klassen Hyperebenen liegen. In diesem Unterabschnitt diskutieren wir lineare SVM mit linear trennbaren Klassen.

<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Optimale Hyperebene als Entscheidungsflächen'''''</span>

Im Allgemeinen gibt es bei linear trennbaren Klassen viele Hyperebenen, die die Klassen trennen können. Ihre Trennfähigkeit hängt jedoch von ihrer Positionierung zu den Klassen der Eingabedaten ab, siehe Abbildung [[#fig:SVM_2|26]].

<div id="fig:SVM_2" class="figure">

[[Datei:SVM_WIPE_1.jpg|460px|thumb|center|Abbildung 26: Abhängigkeit der Trennfähigkeit von Hyperebenen von ihrer Position zu den Klassen der Eingabedaten (Quelle: [https://en.wikipedia.org/wiki/Support_vector_machine Wikipedia_SVM]).]] <span id="fig:SVM_2" label="fig:SVM_2"></span>


</div>


Intuitiv ergibt die Hyperebene mit dem größten Abstand zu den Klassen die größte Trennungsfähigkeit. Der Abstand einer Hyperebene zu den Klassen entspricht dem Abstand zu ihren nächstgelegenen Punkten. Die Summe der Abstände von einer Hyperebene zu den Klassen wird als Margin bezeichnet. Z. B. in Abbildung [[#fig:SVM_2|26]] H1 trennt die Klassen gar nicht. H2 und H3 schon, aber H2 nur mit einer kleinen Margin. H3 ist die Hyperebene, die die Klassen mit der maximalen Margin trennt.

Tatsächlich kann gezeigt werden, dass die Hyperebene mit dem größten Margin als Entscheidungsfläche die optimale ist, in dem Sinne, dass sie bei der Klassifizierung den geringeren Generalisierungsfehler verursacht. Die optimale Hyperebene wird als Hyperebene mit maximalem Margin bezeichnet.

<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Optimierungsaufgabe zum Finden der Maximum-Margin Hyperebene'''''</span>

Jede Hyperebene kann durch eine lineare Gleichung in Normalform beschrieben werden als <math display="block">{\bf w}^T {\bf x} + c = 0.</math> Hier ist <math display="inline">{\bf w}</math> ein <math display="inline">N</math>-dimensionaler Normalenvektor, d. h. er ist rechtwinklig zur Hyperebene und die Konstante <math display="inline">c</math> hängt von der Größe von <math display="inline">{\bf w}</math> ab (Multiplikation der obigen Gleichung mit einer beliebigen Konstante <math display="inline">k</math> bleibt die Richtung von <math display="inline">{\bf w}</math> gleich, aber sowohl seine Größe als auch <math display="inline">c</math> ändern sich). Die Projektion eines beliebigen Punktes <math display="inline">{\bf x}</math> als Vektor auf die Richtung von <math display="inline">{\bf w}</math> ist <math display="inline">\frac{{\bf w}^T {\bf x}}{\lVert {\bf w} \rVert}</math>. Andererseits impliziert die Gleichung der Hyperebene, dass für jeden auf der Hyperebene liegenden Punkt <math display="inline">{\bf w}^T {\bf x} = -c</math> gilt. Somit ist die Projektion eines beliebigen Punktes <math display="inline">{\bf x}</math>, der auf der Hyperebene liegt, als Vektor auf die Richtung von <math display="inline">{\bf w}</math> kann durch <math display="block">\frac{-c}{\lVert {\bf w} \rVert}</math> gegeben werden. Wählen wir die Konstante <math display="inline">c</math> in den Gleichungen der an den Klassengrenzen liegenden Hyperebenen als <math display="inline">b-1</math> und <math display="inline">b+1</math>, was für diese Hyperebenen zu den Gleichungen als <math display="block">\begin{aligned}
&{\bf w}^T {\bf x} + b = 1,  \\
&{\bf w}^T {\bf x} + b = -1 
\end{aligned}</math> führt. Dann entspricht der Margin für eine Hyperebene, die auf halber Strecke zwischen den oben genannten Hyperebenen liegt, <math display="inline">\rho({\bf w},b)</math> dem Abstand zwischen diesen Hyperebenen. Der kann als Differenz der Projektionen jedes auf diesen Hyperebenen liegenden Punktes auf ihren Normalenvektor berechnet werden, der durch <math display="block">\rho({\bf w},b) = \frac{(1-b)}{\lVert {\bf w} \rVert} - \frac{(-b-1)}{\lVert {\bf w} \rVert}= \frac{2}{\lVert {\bf w} \rVert}</math> gegeben ist.

Daraus folgt, dass die Maximierung der Margin gleichwertig mit der Minimierung von <math display="inline">\lVert {\bf w} \rVert^2</math> ist.

Somit beträgt der Abstand zwischen der Hyperebene, die auf halbem Weg zwischen den obigen Hyperebenen liegt, und einer von ihnen <math display="inline">\frac{1}{\lVert {\bf w} \rVert}</math>, was impliziert, dass für die Gleichung der Hyperebene, die auf halbem Weg zwischen die obigen Hyperebenen liegt, <math display="inline">\frac{(1-b)}{\lVert {\bf w} \rVert} - \frac{(-c)}{\lVert {\bf w} \rVert}= \frac{1} {\lVert {\bf w} \rVert}</math> gilt, woraus <math display="inline">c=b</math> und somit ist diese Gleichung durch <math display="block">{\bf w}^T {\bf x} + b = 0</math> gegeben. Diese Hyperebenen und die oben genannten Abstände sind in Abbildung [[#fig:SVM_3|27]] dargestellt.

<div id="fig:SVM_3" class="figure">

[[Datei:SVM_WIPE_3.jpg|460px|thumb|center|Abbildung 27: Hyperebene, die auf halber Strecke zwischen den Klassen liegt, deren Abstände und Margin (Quelle: [https://en.wikipedia.org/wiki/Support_vector_machine Wikipedia_SVM]).]] <span id="fig:SVM_3" label="fig:SVM_3"></span>


</div>


Wählen wir die Bezeichnungen <math display="inline">y_i=1</math> und <math display="inline">y_i=-1</math> für die erste bzw. zweite Klasse. Dann erfüllen alle Vektoren der Eingabedaten, die zur ersten und zweiten Klasse gehören, jeweils die Ungleichungen <math display="block">\begin{aligned}
&{\bf w}^T {\bf x}_i + b \geq 1,   \mathrm{~wenn~} y_i = 1  \mathrm{~and~}  \\
&{\bf w}^T {\bf x}_i + b \leq -1.   \mathrm{~wenn~} y_i = -1.
\end{aligned}</math>

Diese beiden Ungleichungen können in einer äquivalenten kompakten Form als <math display="block">y_i({\bf w}^T {\bf x}_i + b) \geq 1</math> geschrieben werden. Wenn man all dies zusammenfügt, ergibt sich die Optimierungsaufgabe mit Nebenbedingungen (constrained optimization task) zum Finden der Maximum-Margin Hyperebene als <math display="block">\begin{aligned}
  &({\bf w}, b) = \arg \min_{{\bf w}, b} \lVert {\bf w} \rVert^2, ~ \mathrm{~unter~den~Bedingungen~}~ \\
  &  y_i({\bf w}^T {\bf x}_i + b) \geq 1, ~~i=1,\ldots,N.
\end{aligned}</math>

<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Quadratisches Programm (quadratic programming problem) für die Lagrange-Multiplikatoren'''''</span>

Um das Optimierungsproblem mit Nebenbedingungen zu lösen, die Lagrange-Funktion wird konstruiert als <math display="block">L({\bf w}, b, {\boldsymbol{\Lambda}}) = \frac{1}{2} {\bf w}^T{\bf w} - \sum_{i=1}^N \lambda_i \left( y_i ({\bf w}^T {\bf x}_i + b) -1\right),</math>

wobei die Elemente von <math display="inline">{\boldsymbol{\Lambda}}^T =(\lambda_1,\ldots,\lambda_N)</math> aufgrund der Nebenbedingungen die nicht negativen Lagrange-Multiplikatoren sind. Berechnen die ersten Ableitungen nach <math display="inline">{\bf w}</math> und <math display="inline">b</math> bei Minimum <math display="inline">{\bf w}^{*}</math> und <math display="inline">b^{*}</math> ergibt <math display="block">\left.{\frac{ \partial L({\bf w}, b, {\boldsymbol{\Lambda}})}{\partial {\bf w}}}\right|_{{\bf w}={\bf w}^{*}} = \left({\bf w}^{*} - \sum_{i=1}^N \lambda_i y_i {\bf x}_i \right) =0,</math> und <math display="block">\left.{\frac{ \partial L({\bf w}, b, {\boldsymbol{\Lambda}})}{\partial b}}\right|_{b=b^{*}} = \sum_{i=1}^N \lambda_i y_i =0.</math>

Wenn man sie in die Lagrange-Funktion bei <math display="inline">{\bf w} = {\bf w}^{*}</math> und <math display="inline">b=b^{*}</math> einsetzt, erhält man <math display="block">\begin{aligned}
L({\bf w}^{*}, b^{*}, {\boldsymbol{\Lambda}}) &= \frac{1}{2} {{\bf w}^{*}}^T{\bf w}^{*} -  \sum_{i=1}^N \lambda_i y_i {{\bf w}^{*}}^T {\bf x}_i - \sum_{i=1}^N \lambda_i y_i b^{*} +  \sum_{i=1}^N \lambda_i\\
&= \frac{1}{2} {{\bf w}^{*}}^T{\bf w}^{*} - {{\bf w}^{*}}^T{\bf w}^{*} + \sum_{i=1}^N \lambda_i \\
&= \sum_{i=1}^N \lambda_i - \frac{1}{2} {{\bf w}^{*}}^T{\bf w}^{*}\\
&= \sum_{i=1}^N \lambda_i - \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \lambda_i \lambda_j y_i y_j {\bf x}_i {\bf x}_j.
\end{aligned}</math>

Einführung des Label Vektors <math display="inline">{\bf y}</math> und der symmetrischen Matrix <math display="inline">N \times N</math> <math display="inline">{\bf D}</math> als <math display="block">\begin{aligned}
  & {\bf y}^T = (y_1,\ldots, y_N), \\   
  &{\bf D} = [{\bf D}_{ij}]=[y_i y_j {\bf x}_i {\bf x}_j]
\end{aligned}</math>

ermöglicht die Erstellung eines quadratischen Programms in Vektor-Matrix-Notation für die Lagrange-Multiplikatoren as <math display="block">\begin{aligned}
    &\arg \max_{{\boldsymbol{\Lambda}}} L({\boldsymbol{\Lambda}}) = \arg \max_{{\boldsymbol{\Lambda}}} {\boldsymbol{\Lambda}}^T {\bf e} - \frac{1}{2}{\boldsymbol{\Lambda}}^T {\bf D}{\boldsymbol{\Lambda}}, ~ \mathrm{~unter~den~Bedingungen~}~ \\
    & {\boldsymbol{\Lambda}}^T {\bf y} = 0, ~ \mathrm{~fuer~}~{\boldsymbol{\Lambda}} \geq {\bf 0},
\end{aligned}</math> wobei <math display="inline">{\bf e}</math> für den <math display="inline">N</math>-dimensionalen Einheitsvektor steht.

<div class="remark">

'''Bemerkung 1'''.  ''Die Nebenbedingung <math display="inline">{\boldsymbol{\Lambda}}^T {\bf y} = 0</math> ist dieselbe wie die partielle Ableitung der Lagrange-Funktion nach <math display="inline">b</math> in Vektorform. Die andere partielle Ableitung und die ursprünglichen Nebenbedingungen sind hier nicht notwendig, da die Zielfunktion im obigen quadratischen Programmierproblem nicht von <math display="inline">{\bf w}</math> abhängt.''


</div>
<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Die Eigenschaften der optimalen Hyperebene'''''</span>

Nach dem Kuhn-Tucker-Theorem <math display="block">\begin{aligned}
    \lambda_{i}^{*} \left(y_i({{\bf w}^{*}}^T{\bf x}_i + b^{*}) \right) = 0, ~~ i= 1, \ldots, N
\end{aligned}</math> gilt für die optimalen Parameter der Lagrange-Funktion. Daraus folgt, dass <math display="inline">\lambda_{i}^{*} \neq 0</math> nur für die Fälle gilt, in denen die Ungleichung-Constraint zu einer Gleichheit wird, d. h. wenn <math display="block">\begin{aligned}
     y_i({{\bf w}^{*}}^T{\bf x}_i + b^{*}) - 1 = 0  ~\Leftrightarrow~ y_i({{\bf w}^{*}}^T{\bf x}_i + b^{*}) =1
\end{aligned}</math> gilt. Die Vektoren <math display="inline">{\bf x}_i</math> der Eingabedaten, die die obige Gleichheit erfüllen, werden Support-Vektoren genannt. Dies sind die Vektoren, die zu den an den Klassengrenzen liegenden Hyperebenen passen.

Für die optimale Hyperebene gelten folgende Eigenschaften:

* <span>'''P.1'''</span> Der Parametervektor <math display="inline">{\bf w}^{*}</math> der optimalen Hyperebene kann als lineare Kombination der Support-Vektoren als <math display="block">{\bf w}^{*} = \sum_{i=1}^N \lambda_{i}^{*} y_i {\bf x}_i.</math> ausgedrückt werden.
* <span>'''P.2'''</span> Die Support-Vektoren bestimmen vollständig die optimale Hyperebene, also sowohl <math display="inline">{\bf w}^{*}</math> als auch <math display="inline">b^{*}</math>.
* <span>'''P.3'''</span> Zwischen dem Wert der Lagrange-Funktion im Optimum und dem Margin für die optimale Hyperebene, <math display="inline">\rho^{*}</math> gilt die Relation, <math display="block">L({\bf w}^{*}, b^{*}, {\boldsymbol{\Lambda}}^{*}) = \frac{2}{{\rho^{*}}^2}.</math>

Die Gleichung von <span>'''P.1'''</span> kann durch Umstellen der Gleichung erhalten werden, die als erste Ableitung der Lagrange-Funktion nach <math display="inline">{\bf w}</math> erhalten wurde. Die <math display="inline">{\bf x}_i</math>-s für jedes <math display="inline">\lambda_{i}^{*} \neq 0</math> erfüllen die Gleichheit <math display="inline">y_i({{\bf w}^{*}}^T{\bf x  }_i + b^{*}) =1</math> und somit sind sie Support-Vektoren. Daher wird <math display="inline">{\bf w}^{*}</math> in der Expression in <span>'''P.1'''</span> als Linearkombination der Support-Vektoren angegeben. Dies legt nahe, dass nur diese Vektoren des Eingabedaten einen effektiven Beitrag zum Parametervektor <math display="inline">{\bf w}^{*}</math> leisten, was den Namen „Support-Vektor“ erklärt.

Nachdem <math display="inline">{\bf w}^{*}</math> bestimmt wurde, kann <math display="inline">b^{*}</math> durch Einsetzen eines beliebigen Support-Vektoren in die Gleichung <math display="inline">y_i({{\bf w}^{*}}^T {\bf x}_i + b^{*}) =1</math> berechnet werden. Damit ist <span>'''P.2'''</span> gezeigt.

Um <span>'''P.3'''</span> zu zeigen, stellen wir eine Beziehung zwischen <math display="inline">{{\bf w}^{*}}^T {\bf w}^{*}</math> und <math display="inline">\sum_{i=1}^N \lambda_{i}^{*}</math> her als <math display="block">{{\bf w}^{*}}^T {\bf w}^{*}= \sum_{i=1}^N \lambda_{i}^{*} y_i  {{\bf w}^{*}}^T {\bf x}_i = \sum_{i=1}^N \lambda_{i}^{*} (1-y_i b^{*}) = \sum_{i=1}^N \lambda_{i}^{*},</math> wobei <span>'''P.1'''</span>, die Gleichheit <math display="inline">y_i({{\bf w}^{*}}^T{\bf x}_i + b^{*}) =1</math> für die Support-Vektoren und die Beziehung <math display="inline">\sum_{i=1}^N \lambda_i y_i =0</math> bei <math display="inline">\lambda_i =\lambda_{i}^{*}</math> verwendet wurden. Die Anwendung dieser Beziehung auf die Lagrange-Funktion im Optimum führt zu <math display="block">L({\bf w}^{*}, b^{*}, {\boldsymbol{\Lambda}}^{*}) = \sum_{i=1}^N \lambda_{i}^{*} - \frac{1}{2} {{\bf w}^{*}}^T{\bf w}^{*} = \frac{1}{2} {{\bf w}^{*}}^T{\bf w}^{*}</math> Kombiniert man es mit dem Ausdruck der Margin <math display="inline">\rho({\bf w}, b)=\frac{2}{\lVert {\bf w} \rVert}</math> bei <math display="inline">{\bf w} = {\bf w }^{*}</math> und <math display="inline">b=b^{*}</math> ergibt <math display="block">{\rho^{*}}^2 = \frac{4}{2 L({\bf w}^{*}, b^{*}, {\boldsymbol{\Lambda}}^{*})} = \frac{2}{L({\bf w}^{*}, b^{*}, {\boldsymbol{\Lambda}}^{*})},</math> woraus <span>'''P.3'''</span> direkt folgt.

<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Optimaler Hyperebenen-Algorithmus'''''</span>

Basierend auf den obigen Unterkapiteln kann ein Algorithmus zur Bestimmung des linearen SVM-Klassifikators mit linear trennbaren Klassen erstellt werden, d. h. um die Parameter <math display="inline">{\bf w}</math> und <math display="inline">b</math> zu berechnen. Dieser optimale Hyperebenen-Algorithmus besteht aus den folgenden Schritten:

# Berechnen das optimale <math display="inline">{{\boldsymbol{\Lambda}}^{*}}^T =(\lambda_1^{*},\ldots,\lambda_N^{*})</math>, durch Löung des quadratischen Programms <math display="block">\begin{aligned}
    &\arg \max_{{\boldsymbol{\Lambda}}} L({\boldsymbol{\Lambda}}) = \arg \max_{{\boldsymbol{\Lambda}}} {\boldsymbol{\Lambda}}^T {\bf e} - \frac{1}{2}{\boldsymbol{\Lambda}}^T {\bf D}{\boldsymbol{\Lambda}}, ~ \mathrm{~unter~den~Bedingungen~}~ \\
    & {\boldsymbol{\Lambda}}^T {\bf y} = 0, ~ \mathrm{~fuer~}~{\boldsymbol{\Lambda}} \geq {\bf 0},
\end{aligned}</math>
# Berechnen die optimalen Parametergewichte <math display="inline">{\bf w}^{*}</math> basierend auf der Eigenschaft <span>'''P.1'''</span>, d. h. aus <math display="inline">\lambda_{i}</math>-s und aus den Support-Vektoren unter Verwendung der Gleichung <math display="block">{\bf w}^{*} = \sum_{i=1}^N \lambda_{i}^{*} y_i {\bf x}_i.</math>
# Berechnen den Parameter <math display="inline">b^{*}</math>, indem einen Support-Vektor in die Gleichung <math display="inline">y_i({{\bf w}^{*}}^T{\bf x}_i + b^{*}) =1</math> eingesetzt wird.

<span id="lineare-svm-mit-linear-nicht-trennbaren-klassen"></span>
=== Lineare SVM mit linear nicht trennbaren Klassen ===

Wenn die Klassen linear nicht trennbar sind, gibt es keine Hyperebene, die alle Trainingsbeispiele korrekt trennen kann. In diesem Fall kann man nach der Hyperebene suchen, die die meisten Trainingsbeispiele trennen kann, d. h. was den geringsten Fehler bei der Trennung macht. Daher muss der Fehler bei der Trennung in die Formulierung der Optimierungsaufgabe zum Finden der optimalen Hyperebene einbezogen werden.

<div id="fig:SVM_4" class="figure">

[[Datei:SVM_cmu_edu_1.jpg|460px|thumb|center|Abbildung 28: Hyperebene für linear nicht trennbare Klassen mit fehlerhaft getrennten Trainingsbeispielen (Quelle: [https://www.cs.cmu.edu/~aarti/Class/10701_Spring21/Lecs/svm_dual_kernel_inked.pdf cmu_edu]).]] <span id="fig:SVM_4" label="fig:SVM_4"></span>


</div>


<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Optimierungsaufgabe zum Finden der optimalen Hyperebene'''''</span>

Sei <math display="inline">\xi_i</math> der Fehler des fälschlicherweise getrennten Trainingsbeispiels <math display="inline">{\bf x}_i</math>, der im der ausgewählten Hyperebene zugeordneten Margin liegt, siehe Abbildung [[#fig:SVM_4|28]]. Die Trainingsbeispiele mit <math display="inline">\xi_i=0</math> (grüne Kreise) sind Support-Vektoren. Die Trainingsbeispiele mit <math display="inline">0 < \xi_i < 1</math> (lila Kreise) sind richtig klassifiziert, liegen aber innerhalb des Margins. Die Trainingsbeispiele mit <math display="inline">1 < \xi_i</math> (lila Kreise) sind falsch klassifiziert. Die zuvor für die linear separierbaren Klassen festgelegte Nebenbedingungen müssen geändert werden, da die fehlerhaft separierten Trainingsbeispiele innerhalb des Margins liegen. Die richtige Nebenbedingung, die den Fehler des fälschlicherweise getrennten Trainingsbeispiele berücksichtigt, kann wie folgt formuliert werden:

<math display="block">y_i({\bf w}^T {\bf x}_i + b) \geq 1 - \xi_i, ~~ \mathrm{~wobeie~}~~\xi_i \geq 0, ~~i=1,\ldots,N.</math>

Jetzt wollen wir nicht nur <math display="inline">\lVert {\bf w} \rVert^2</math> sondern auch den Gesamtfehler bei der Trennung minimieren, um einen großen Margin zu haben. Hier den Gesamtfehler kann als <math display="block">\sum_{i=1}^{N} \xi_i</math> ausgedrückt werden.

Je kleiner der Wert <math display="inline">\lVert {\bf w} \rVert^2</math>, desto größer der Margin, was zu einem größeren Gesamtfehler bei der Trennung führt. Somit stehen der Wert <math display="inline">\lVert {\bf w} \rVert^2</math> und der Gesamtfehler bei der Trennung im Kompromiss zueinander. Daher ist die Optimierungsaufgabe mit Nebenbedingungen zum Finden der optimalen Hyperebene für linear nicht trennbare Klassen wird durch <math display="block">\begin{aligned}
  &({\bf w}, b) = \arg \min_{{\bf w}, b} \frac{1}{2}\lVert {\bf w} \rVert^2 + G \sum_{i=1}^{N} \xi_i, ~ \mathrm{~unter~den~Bedingungen~}~ \\
  &  y_i({\bf w}^T {\bf x}_i + b) \geq 1- \xi_i, ~~ \mathrm{~und~}~~\xi_i \geq 0, ~~i=1,\ldots,N
\end{aligned}</math> gegeben, wobei <math display="inline">G</math> eine Konstante ist, die die Gewichtung der beiden zu minimierenden Ziele festlegt. Die optimale Hyperebene wird Soft-Margin-Hyperebene genannt. Der Name kommt von der Art dieses Margin, der das Überhängen mehrerer Trainingsbeispiele ermöglicht. Es kann gezeigt werden, dass alle Eigenschaften <span>'''P.1'''</span> - <span>'''P.3'''</span> auch für diesen nicht trennbaren Fall gelten.

<div class="remark">

'''Bemerkung 2'''.  ''Wenn diese Optimierung mit einem hohen Wert von <math display="inline">G</math> angewendet wird, dann verhält sie sich ähnlich wie die Optimierung für trennbare Klassen.''


</div>
<span id="svm-mit-nichtlinearem-kernel"></span>
=== SVM mit nichtlinearem Kernel ===

Im Fall linear nicht trennbarer Klassen kann eine bessere Trennbarkeit durch die Verwendung einer nichtlinearen Entscheidungsfläche anstelle einer Hyperebene erreicht werden. Dies wird in Abbildung [[#fig:SVM_5|29]] veranschaulicht.

<div id="fig:SVM_5" class="figure">

[[Datei:SVM_WIPE_2a.jpg|460px|thumb|center|Abbildung 29: Nichtlineare Entscheidungsfläche für nicht trennbare Klassen (Quelle: [https://en.wikipedia.org/wiki/Support_vector_machine Wikipedia_SVM]).]] <span id="fig:SVM_5" label="fig:SVM_5"></span>


</div>


<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Die Idee der nichtlinearen SVM'''''</span>

Aus diesem Grund wird die Theorie der Support Vector Machine auf nichtlineare Entscheidungsflächen erweitert. Die Idee dieser Erweiterung besteht darin, die Eingabevektoren <math display="inline">{\bf x}_i</math> in <math display="inline">M</math>-dimensionale Vektoren umzuwandeln, indem eine <math display="inline">M</math>-dimensionale Vektorfunktion <math display="inline">\phi()</math> auf sie angewendet und dann eine optimale Hyperebene im <math display="inline">M</math>-dimensionalen Raum der transformierten Vektoren konstruiert wird. Durch richtig ausgewählte Vektorfunktion <math display="inline">\phi()</math> werden die transformierten Klassen im <math display="inline">M</math>-dimensionalen Raum wieder durch eine optimale Hyperebene linear trennbar ! Dies ist in Abbildung [[#fig:SVM_6|30]] illustriert.

<div id="fig:SVM_6" class="figure">

[[Datei:SVM_WIPE_2.jpg|460px|thumb|center|Abbildung 30: Nichtlineare Entscheidungsfläche für nicht trennbare Klassen (Quelle: [https://en.wikipedia.org/wiki/Support_vector_machine Wikipedia_SVM]).]] <span id="fig:SVM_6" label="fig:SVM_6"></span>


</div>


Dann ist die potentielle Entscheidungsgrenze eine <math display="inline">M</math>-dimensionale Hyperebene für die transformierten Vektoren <math display="inline">{\boldsymbol{\phi}}({\bf x}_i) = (\phi_1({\bf x}_i), \ldots, \phi_M( {\bf x}_i)</math>, für <math display="inline">i=1,\ldots,N</math> mit den Parametern <math display="inline">{\bf w}</math> und <math display="inline">b</math>, welche die Form <math display="block">f({\bf x}) = {\bf w}^T {\boldsymbol{\phi}}({\bf x}) + b</math> hat.

Unter Anwendung der Eigenschaft <span>'''P.1'''</span> der Soft-Margin-Hyperebene im <math display="inline">M</math>-dimensionalen Raum der transformierten Vektoren kann der optimale Parametervektor <math display="inline">{\bf w}^{*}</math> als Linearkombination von der Support-Vektoren im transformierten Raum als <math display="block">{\bf w}^{*} = \sum_{i=1}^{N} \lambda_i^{*} y_i  {\boldsymbol{\phi}}({\bf x}_i)</math> bestimmt werden. Wenn man es in die Expression der Entscheidungsgrenze einsetzt, kann man die Entscheidungsfläche <math display="inline">f^{*}({\bf x})</math> als <math display="block">f^{*}({\bf x}) = \sum_{i=1}^{N} \lambda_i^{*} y_i {\boldsymbol{\phi}}({\bf x})^T {\boldsymbol{\phi}}({\bf x}_i) + b^{*}.</math> ausdrücken.

<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Der Kernel-Trick'''''</span>

Das einzige Rechenproblem besteht darin, potenzielle hochdimensionale Räume zu behandeln, die in <math display="inline">{\boldsymbol{\phi}}({\bf x})</math> für große Werte von <math display="inline">M</math> entstehen. Tatsächlich ist es jedoch nicht erforderlich. Die Entscheidungsfunktion (decision function) <math display="inline">f^{*}({\bf x})</math> hängt nur vom Skalarprodukt <math display="inline">{\boldsymbol{\phi}}({\bf x})^T {\boldsymbol{\phi}}({\bf x}_i)</math> und nicht von den einzelnen Vektoren <math display="inline">{\boldsymbol{\phi}}({\bf x})</math> und <math display="inline">{\boldsymbol{\phi}}({\bf x}_i)</math> ab. Unter bestimmten Bedingungen gibt es Funktionen K(<span>'''u'''</span>, <span>'''v'''</span>), die wie folgt faktorisiert werden können. <math display="block">K({\bf u}, {\bf v}) = {\boldsymbol{\phi}}({\bf u}) {\boldsymbol{\phi}}({\bf v}).</math>

Mit einer solchen Funktion <math display="inline">K({\bf u}, {\bf v})</math> kann die Entscheidungsgrenze <math display="inline">f^{*}({\bf x})</math> in der Form <math display="block">f^{*}({\bf x}) = \sum_{i=1}^{N} \lambda_i^{*} y_i  K({\bf x}, {\bf x}_i) + b^{*}</math> geschrieben werden. Die Funktion <math display="inline">K({\bf u}, {\bf v})</math> eine Skalarfunktion ist. Dies bedeutet, dass es ausreicht, statt potenziell hochdimensionalen Vektorfunktionen <math display="inline">{\boldsymbol{\phi}}</math> zunächst einen von interner Form von <math display="inline">K(,)</math> abhängigen Operator, wie z.B. Skalarprodukt oder eine beliebige Distanz, auf die Vektoren <math display="inline">{\bf x}</math>, <math display="inline">{\bf x}_i</math> anzuwenden, und das Ergebnis dann in die Skalarfunktion <math display="inline">K()</math> einzusetzen, die dann rechnerisch leicht berechenbar ist.

Die Funktion <math display="inline">K({\bf u}, {\bf v})</math> wird Kernel genannt und die Idee, sie zu verwenden, anstatt die Vektorenfunktion <math display="inline">{\boldsymbol{\phi}}()</math> zu behandeln, was die Berechnung leicht berechenbar macht, nennt man Kernel-Trick. Maschinen, die den Kernel-Trick anwenden, werden Kernel-Maschinen benannt.

<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Eigenschaften von SVM mit nichtlinearem Kernel'''''</span>

Die Hauptmerkmale von SVM mit nichtlinearem Kernel kann wie folgt zusammengefasst werden.

# Seine Entscheidungsfunktion <math display="inline">f^{*}({\bf x})</math> kann mit der Hilfe Kernel <math display="inline">K({\bf x}, {\bf x}_i)</math> ausgedrückt werden.
# Seine Entscheidungsfunktion ist nichtlinear im Raum des Eingabevektors.
# Der nichtlinear transformierte Vektorraum kann hochdimensional sein.
# Die nichtlineare Entscheidungsfläche ist eine Soft-Margin-Hyperebene im transformierten Vektorraum.
# Die Entscheidungsfläche wird mit dem Soft-Margin-Hyperplane-Algorithmus berechnet, mit der einzigen Unterschied zur Einstellung der Matrix <math display="inline">{\bf D}</math> als <math display="block">{\bf D} = [{\bf D}_{ij}]=[y_i y_j K({\bf x}_i, {\bf x}_j)].</math>

<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Ausgewählte nichtlineare Kernel'''''</span>

Nachfolgend sind einige häufig verwendete nichtlineare Kernel aufgeführt.

* Polynomkernel – für Klassifikator vom Grad <math display="inline">d</math> <math display="block">K({\bf u}, {\bf v}) = ({\bf u} {\bf v} + a)^d</math> Für <math display="inline">a=0</math> und <math display="inline">d=1</math> wird es zum linearen Kernel.
* Potentialfunktion <math display="block">K({\bf u}, {\bf v}) = exp\left(- \frac{\lVert {\bf u} - {\bf v} \rVert)}{\sigma}\right)</math>
* Gaußsche Radialfunktion als Kernel (Gaussian radial function) <math display="block">K({\bf u}, {\bf v}) = exp\left(- \frac{\lVert {\bf u} - {\bf v} \rVert^2)}{2 \sigma^2}\right)</math>
* Sigmoid- oder hyperbolische Tangensfunktion <math display="block">K({\bf u}, {\bf v}) = \tanh \left(\alpha {\bf u} {\bf v} + \beta \right),  \mathrm{~fuer~einige~} \alpha > 0  \mathrm{~und~} \beta < 0</math>

<span id="erweiterungen"></span>
=== Erweiterungen ===

SVM verfügt über mehrere Erweiterungen. Nachfolgend befindet sich eine kurze Zusammenfassung der wichtigsten von denen.

* Multiklassen-SVM. Multiclass SVM ist ein Klassifikator, der für mehr als zwei Klassen entwickelt wurde. Der vorherrschende Realisierungsansatz führt auf Klassifikatoren mit zwei Klassen zurück. Eine dieser Methoden ist die Eins-gegen-Alle-Methode (one-versus-all), bei der für jede Klasse ein Klassifikator angewendet wird, um sie vom Rest zu trennen, und der Klassifikator mit der höchsten Ausgabe gewinnt.
* Transduktive SVM. Transduktive SVM realisiert halbüberwachtes Lernen. Neben dem beschrifteten Trainingdaten wird ein unbeschriftet Daten von Vektoren <math display="inline">{\bf x}^{'}_j</math>, <math display="inline">j=1,\ldots, U</math> bereitgestellt. Die Optimierungsaufgabe wird modifiziert, indem neben den Parametern <math display="inline">{\bf w}</math> und <math display="inline">b</math> auch nach den vorherzusagenden Labels <math display="inline">y^{'}_j</math> gesucht wird und die Nebenbedingungen durch <math display="inline">y^{'}_i ( {\bf w}^T {\bf x}_i + b) \geq 1</math> und <math display="inline">y^{'}_i \in {-1,1}</math> ergänzt werden.
* Support-Vektor-Clustering (SVC). SVC ist eine Maschine, die unüberwachtes Lernen realisiert.
* Strukturierte SVM (structured SVM). Strukturierte SVM ist eine Verallgemeinerung von SVM, die strukturierte und unendlich viele Labels ermöglicht.
* Support-Vector-Regression (SVR). SVR basiert auf der an die Regression angepassten SVM-Theorie. Jetzt ist <math display="inline">{\bf w}^T {\bf x}_i + b</math> der vorhergesagte Wert und <math display="inline">y_i</math> die richtige Ausgabe, wobei beide stetige Werte annehmen. Dann wird die Regression durch die Optimierungsaufgabe mit der Nebenbedingung <math display="inline">|y_i - ({\bf w}^T {\bf x}_i + b)|\leq \epsilon</math> bestimmt, wobei <math display="inline">\epsilon</math> ein freier Schwellenwert für Fehler (error threshold) ist.

<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Implementierung'''''</span>

Normalerweise ist vor der Berechnung von SVM eine Vorverarbeitung der Trainingsdaten erforderlich. Zu den notwendigen Vorverarbeitungsschritten gehören:

* Skalierung mit Methoden wie Min-Max, Dezimalskalierung (decimal scaling) oder Z-Score.
* Mittelwertnormalisierung (mean normalization), d. h. Subtrahieren des Mittelwerts von den Vektoren.
* Varianznormalisierung (variance normalization), d. h. Division jeder Vektorkomponente durch ihre Varianz.

Kernel SVM ist in vielen ML Softwarepaketen implementiert, darunter unter anderem

* P-Pack SVM mit Subgradienten-Verfahren,
* MATLAB, SAS,
* LIBSVM, SVMlight,kernlab, JKernelMachines und
* scikit-learn Python-Bibliothek.

<span id="entscheidungsbäume-und-random-forests"></span>
== Entscheidungsbäume und Random Forests ==

Klassifikations- und Regressionsbäume (Classification and Regression Trees - CART) sind Entscheidungsbäume, die für Klassifikations- und Regressionsaufgaben verwendet werden können. In diesem Unterabschnitt diskutieren wir den Ansatz von Entscheidungsbäume für Klassifikationsaufgaben.

Klassifikationsbäume realisieren eine hierarchische Partitionierung des Raumes der Eingabevektoren. Die Eingabevektoren werden auch als Featurevektoren genannt, da jede einzelne Komponente der Eingabevektoren ein Merkmal (also Feature) darstellt. Die Partitionierung führt zu einzelnen disjunkten Bereichen des Raumes der Eingabevektoren, von denen jeder einer Klasse zugeordnet ist. Die Grundidee des Klassifikationsbaums ist also die Zuordnung disjunkter Bereiche des Raumes der Eingabevektoren zu Klassen, was sich wesentlich von den Ideen anderer Klassifikationsmethoden unterscheidet, wie z. B. neuronalen Netzen, die Diskriminanzfunktionen realisieren, oder Support Vector Machines, die Entscheidungsgrenzen als Hyperebene realisieren.

<span id="ein-medizinisches-beispiel"></span>
=== Ein medizinisches Beispiel ===

In einem medizinischen Beispiel werden die Patienten in Hochrisiko- und Niedrigrisiko-Patienten eingeteilt. Die Einteilung erfolgt durch Fragen an die Patienten. Die Fragen können in einem binären Baum organisiert werden, siehe Abbildung [[#fig:CART_Med_Exa|31]].

<div id="fig:CART_Med_Exa" class="figure">

[[Datei:CART_1_MedExa.jpg|460px|thumb|center|Abbildung 31: Ein medizinisches Beispiel für einen Klassifikationsbaum (Quelle: [CARTPennStateCourse(2024)]).]] <span id="fig:CART_Med_Exa" label="fig:CART_Med_Exa"></span>


</div>


Jede Frage bezieht sich auf ein Merkmal (Feature), das eine Variable im Raum der Eingabevektoren darstellt. Solche Variablen sind systolischer Blutdruck, Alter und das Vorhandensein einer Sinustachykardie. Somit verwendet die Aufgabe einen dreidimensionalen Raum der Eingabevektoren, wobei zwei Dimensionen sind kontinuierlich, während die letzte diskret ist (kann nur den Wert logisch wahr oder falsch aufnehmen). Auf diese Weise entspricht jedes Blatt des Binärbaums einem disjunkten Bereich des Raums der Eingabevektoren.

<span id="erstellen-eines-entscheidungsbaums"></span>
=== Erstellen eines Entscheidungsbaums ===

Der Entscheidungsbaum wird iterativ aufgebaut, wobei in jeder Iteration eine der resultierenden Regionen der vorherigen Iteration in zwei weitere disjunkte Regionen aufgeteilt wird. Jede Region wird normalerweise entlang einer Komponente des Eingabevektors aufgeteilt. Dies entspricht einer Frage wie „Ist <math display="inline">x_j \leq k</math>, wobei die Aufteilung entlang der <math display="inline">j</math>-ten Komponente der Eingabevektoren durchgeführt wird und <math display="inline">k</math> eine mögliche Position für die Aufteilung ist. Dies wird in Abbildung [[#fig:CART_Split_Steps|32]] veranschaulicht.

<div id="fig:CART_Split_Steps" class="figure">

{| class="wikitable"
|-
| style="text-align: left;"| [[Datei:CART_2p1.jpg|300px|thumb|center|]]
| style="text-align: left;"| [[Datei:CART_2p2.jpg|300px|thumb|center|]]
| style="text-align: left;"| [[Datei:CART_2p3.jpg|300px|thumb|center|]]
|}
Abbildung 32: Veranschaulichung der iterativen Aufteilung des Raums der Eingabevektoren in jedem Schritt entlang einer Komponente des Eingabevektors (Quelle: [CARTPennStateCourse(2024)]).

</div>

Dabei ist <math display="inline">X</math> der gesamte Raum der Eingabevektoren und <math display="inline">X_i</math>-s, <math display="inline">i= 1,\ldots</math> stehen für die einzelnen Regionen des Raums der Eingabevektoren als Ergebnis der aktuellen Aufteilung. Aufgrund der binären Baumdarstellung wächst der Baum in jeder Iteration und jede Region kann auch als Knoten im binären Baum dargestellt werden.

Um den Entscheidungsbaum mittels der oben beschriebenen iterativen Aufteilung zu konstruieren, müssen die Teilaufgaben im Voraus festgelegt werden.

* Auswahl der nächsten Aufteilung (split), d. h. Entscheidung, welcher Knoten (d. h. Region) und wie aufgeteilt werden soll.
* Bereitstellung eines Abbruchkriteriums (stopping criterion) für das Wachstum des Baums.
* Zuweisen einer Klasse zu jedem Blatt des endgültigen Baums.

<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Auswahl der nächsten Aufteilung'''''</span>

Es besteht der Bedarf an einem Maß, mit deren Hilfe aus allen Kandidaten-Aufteilungen die nächstbeste Aufteilung ausgewählt werden kann. Jeder<br />
Kandidaten-Aufteilung kann durch den aufzuteilenden Knoten <math display="inline">t</math> und eine Aufteilung <math display="inline">s</math> angegeben werden, der die für die Aufteilung zu verwendende Komponente des Eingabevektors und seine Position angibt.

Ein häufig verwendetes Maß zur Auswahl der nächstbesten Aufteilung ist das Maß „Goodness of split“ („Güte der Aufteilung“). Die &quot;Goodness of split&quot; einer Kandidaten-Aufteilung kann jedoch berechnet werden, indem die Impurity-Funktion (Unreinheitsfunktion) auf einige Knoten angewendet wird. Daher führen wir zunächst die Impurity-Funktion ein.

<span>''<math display="inline">\mathrm{\ \ \ \ \ \ }</math> Die Impurity-Funktion''</span>

Intuitiv ist eine Region „rein“, wenn die meisten Punkte (d. h. Beispiele der Trainingsdaten) zur selben Klasse gehören. Dazu muss gemessen werden, wie unrein (impure) eine Region ist. Ein Beispiel zum Erstellen reiner Regionen in zwei Aufteilungsschritten ist in Abbildung [[#fig:CART_Clear_Regions|33]] dargestellt.

<div id="fig:CART_Clear_Regions" class="figure">

{| class="wikitable"
|-
| style="text-align: left;"| [[Datei:CART_3p1.jpg|800px|thumb|center|]]
| style="text-align: left;"| [[Datei:CART_3p2.jpg|800px|thumb|center|]]
|}
Abbildung 33: Ein Beispiel zum Erstellen reiner Regionen in zwei Aufteilungsschritten (Quelle: [CARTPennStateCourse(2024)]).

</div>

Nach der ersten Aufteilung gehören nur zwei Punkte auf der linken Seite zur durch Kreise gekennzeichneten Klasse. Durch Anwenden der zweiten Teilung ist es möglich, einen Baum mit 100 % reinen Knoten zu erhalten. Man kann beobachten, dass nach jedem Aufteilungsschritt die Reinheit zunimmt oder gleichwertig die Impurity abnimmt.

Seien <math display="inline">p_1, \ldots, p_C</math> die Wahrscheinlichkeiten, dass ein markierter Datenpunkt in der Region zur Klasse <math display="inline">1,\ldots, C</math> gehört. Dann ist die Impurity-Funktion <math display="inline">\phi()</math> auf <math display="inline">p_1, \ldots, p_C</math>, <math display="inline">p_c \geq 0</math> für <math display="inline">c=1,\ldots, C</math> und <math display="inline">\sum_{c=1}^C p_c = 1</math> durch ihre folgenden Eigenschaften definiert:

# Die Funktion <math display="inline">\phi()</math> hat ein Maximum nur bei gleichmäßig verteilten <math display="inline">p_c</math>-s, d. h. wenn alle <math display="inline">p_c</math>-s gleich sind.
# Die Funktion <math display="inline">\phi()</math> hat ein Minimum an Punkten, wenn einer der <math display="inline">p_c</math>-Werte <math display="inline">1</math> und alle anderen <math display="inline">0</math> sind.
# Die Funktion <math display="inline">\phi()</math> ist symmetrisch in <math display="inline">p_1, \ldots, p_C</math><br />
<math display="inline">\Rightarrow</math> <math display="inline">\phi()</math> hat für jede Permutation von <math display="inline">p_1, \ldots, p_C</math> den gleichen Wert.

Sei <math display="inline">p(t)</math> die Wahrscheinlichkeit, dass ein Punkt (= Featurevektor eines Beispiels einer Trainingsdata) im Knoten <math display="inline">t</math> liegt. Ähnlich sei <math display="inline">p(c,t)</math> die Wahrscheinlichkeit, dass ein Punkt im Knoten <math display="inline">t</math> liegt und zur Klasse <math display="inline">c</math> gehört. Darüber hinaus sei <math display="inline">p(c|t)</math>, <math display="inline">c=1,\ldots,C</math> die bedingte Wahrscheinlichkeit, dass ein Punkt zur Klasse <math display="inline">c</math> gehört, vorausgesetzt, dass er im Knoten <math display="inline">t</math> liegt. Diese bedingten Wahrscheinlichkeiten können basierend auf ihren Definitionen als <math display="inline">p(c|t) = \frac{p(c,t)}{p(t)}</math> berechnet werden. Dann ist das Impurity-Measure (Unreinheitsmaß) des Knotens <math display="inline">t</math>, <math display="inline">i(t)</math> als <math display="block">i(t) = \phi\left(p(1|t), p(2|t),\ldots, p(C|t)\right)</math> gegeben.

Die am häufigsten verwendeten Impurity-Funktionen sind

# Entropie (entropy): <math display="inline">\sum_{c=1}^C p_c log \frac{1}{p_c}</math> (For <math display="inline">p_c = 0</math> apply <math display="inline">\lim_{p_c \rightarrow 0 } p_c log \frac{1}{p_c} = 0</math>.)
# Fehlklassifizierungsrate (missclassification rate): <math display="inline">1-\max_{c}p_c</math>.
# Gini-Index (Gini index): <math display="inline">\sum_{c=1}^C p_c(1-p_c) = 1 - \sum_{c=1}^C p_c^2</math>.

Es ist wichtig zu verstehen, dass es egal ist, welche Impurity-Funktion angewendet wird, da ihre Fähigkeit zur Messung der Impurity durch ihre Eigenschaften gewährleistet wird, die für alle Impurity-Funktionen gelten.

<span>''<math display="inline">\mathrm{\ \ \ \ \ \ }</math> Auswahl basierend auf dem Maß „Goodness of split“''</span>

Der linke und rechte Kindknoten des Knotens <math display="inline">t</math> werden jeweils als <math display="inline">t_L</math> und <math display="inline">t_R</math> bezeichnet. <math display="inline">p(t_L)</math> und <math display="inline">p(t_R)</math> bezeichnen die Wahrscheinlichkeit, dass sich ein Punkt im Knoten <math display="inline">t_L</math> bzw. <math display="inline">t_R</math> befindet. Dann sind die bedingten Wahrscheinlichkeiten, dass sich ein Punkt im Knoten <math display="inline">t_L</math> und <math display="inline">t_R</math> befindet, wenn der Punkt im Knoten <math display="inline">t</math> ist, durch

<math display="block">\begin{aligned}
&p_L = \frac{p(t_L)}{p(t)} \\
&p_R = \frac{p(t_R)}{p(t)}
\end{aligned}</math> gegeben.

Basierend auf der Definition von <math display="inline">i(t)</math> kann die „Goodness of split“ einer<br />
Kandidaten-Aufteilung <math display="inline">s,t</math> als die Differenz der Impurity des Knotens <math display="inline">t</math> und der gewichteten Summe der Impurity der linken und rechten untergeordneten Knoten angegeben werden. Mit anderen Worten

<math display="block">\phi(s,t) = \Delta i(s,t)= i(t) - p_L i(t_L) - p_R i(t_R).</math>

Somit drückt die oben definierte „Goodness of split“ den Gewinn aus, wenn der Kandidaten-Aufteilung <math display="inline">(s,t)</math> angewendet wird, d. h. wenn die durch <math display="inline">s</math> angegebene Aufteilung auf Knoten <math display="inline">t</math> angewendet wird. Hier sind <math display="inline">p_L</math> und <math display="inline">p_R</math> Gewichte oder Anteile von Punkten, die zu linken und rechten Knoten gehen.

Die gewichtete Impurity (weighted impurity) des Knotens <math display="inline">t</math> wird definiert als <math display="block">I(t) = p(t)i(i).</math> Dies kann als die Impurity des Knotens <math display="inline">t</math> interpretiert werden, gewichtet mit dem Anteil seiner Punkte im Baum.

Dann wird die Differenz des gewichteten Impurity-Mass des übergeordneten Knotens <math display="inline">t</math> und der linken und rechten untergeordneten Knoten definiert als <math display="block">\begin{aligned}
\Phi(s,t) &= \Delta I(s,t)= I(t) - I(t_L) - I(t_R)= p(t)i(t) - p(t_L)i(t_L) - p(t_R)i(t_R) \\
&= p(t)i(t) - p(t)p_L i(t_L) - p(t)p_R i(t_R) = p(t)\Delta i(s,t). 
\end{aligned}</math>

<span>''<math display="inline">\mathrm{\ \ \ \ \ \ }</math> Auswahl basierend auf der Twoing Rule''</span>

Eine andere Möglichkeit, die nächste Aufteilung auszuwählen, ist die Anwendung der Twoing Rule. Diese Regel wählt die nächste Aufteilung aus, die den Gesamtunterschied der Posterior-Wahrscheinlichkeiten der Klassen maximiert und die Anteile der Punkte ausgleicht, die auf die untergeordneten Knoten fallen. Mit anderen Worten wählt die Twoing Rule am Knoten <math display="inline">t</math> die Aufteilung aus, die das Optimierungskriterium

<math display="block">\max_{s}  \frac{p_L p_R}{4}\left(\sum_{c} |p(c|t_L) - p(c|t_R)| \right)^2</math> erfüllt.

Der Term in der Klammer stellt die Gesamtdifferenz der<br />
Posterior-Wahrscheinlichkeiten der Klassen dar, während der Multiplikationsfaktor <math display="inline">\frac{p_L p_R}{4}</math> im Maximumkriterium das Ausgleichsziel umsetzt.

<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Das Problem des guten Abbruchkriterium'''''</span>

Wenn man die &quot;Goodness of split&quot; zur Auswahl der nächsten Aufteilung anwendet, ist zu erwarten, dass die gewichtete Impurity mit jedem Schritt abnimmt. Der Baum, der durch iterative Auswahl der nächstbesten Aufteilung wächst, ist jedoch ein Greedy Algorithmus. Daher kann auf eine schlechte Aufteilung mit niedrigem <math display="inline">\Delta I(s,t)</math> eine gute Aufteilung mit höherem <math display="inline">\Delta I(s,t)</math> folgen. Daher wäre ein Abbruchkriterium wie das Abbrechen des Wachstums des Entscheidungsbaums, wenn <math display="inline">\Delta I(s,t)</math> unter einen bestimmten Schwellenwert fällt, kein zufriedenstellendes Abbruchkriterium. Ebenso würde ein „Vorausblick“ auf weitere Schritte in der Entwicklung von <math display="inline">\Delta I(s,t)</math> dieses Problem nicht lösen, da die weitere Entwicklung von <math display="inline">\Delta I(s,t)</math> nach diesen Schritten unbekannt ist, d. h. eine gute Aufteilung mit höherem <math display="inline">\Delta I(s,t)</math> könnte auch nach diesen Schritten folgen.

Daher kann auf diese Weise kein gutes Abbruchkriterium festgelegt werden. Deshalb lässt sich die richtige Strategie wie folgt feststellen.

* Lassen den Baum zunächst wachsen, bis er ausreichend groß ist, und
* Prune (beschneiden) ihn dann gemäß einem zufriedenstellenden Kriterium, siehe Unterabschnitt [[#subsec:prune|4.2.3]].

Das Erreichen einer ausreichend großen Größe kann beispielsweise anhand eines der folgenden Kriterien entschieden werden.

* Lassen den Baum wachsen, bis alle Knoten rein sind (= nur noch eine Klasse enthalten).
* Lassen den Baum wachsen, bis die Anzahl der Datenpunkte unter eine vordefinierte Grenze fällt, z. B. 6.

<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Zuweisen eine Klasse jedem Blatt''''' </span>

Nachdem der Entscheidungsbaum fertig ist, wird jedem Blatt eine Klasse zugewiesen. Die angewandte Regel ist unkompliziert: Jedem Blatt wird die Klasse mit der höchsten Wahrscheinlichkeit zugewiesen. Mit anderen Worten: Die dem Blattknoten <math display="inline">t</math> zugewiesene Klasse <math display="inline">c^*(t)</math> kann als

<math display="block">c^*(t) = \arg\max_{c}  p(c|t)</math> gegeben werden.

<span id="subsec:prune"></span>
=== Pruning ===

Die Beschreibung des Pruning (Beschneidung) bedarf einiger Vorüberlegungen (preliminary considerations).

<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Vorüberlegungen'''''</span>

<span>''<math display="inline">\mathrm{\ \ \ \ \ \ }</math> Optimale Teilbäume''</span>

Das Finden eines optimalen Teilbaums mittels erschöpfender Suche ist keine praktikable Strategie, da die Anzahl der Teilbäume auch bei einem mittelgroßen Baum beträchtlich groß sein kann. Stattdessen wird eine effizientere Methode benötigt, die die folgenden Voraussetzungen erfüllt.

* Der Teilbaum nach dem Pruning sollte in einem vordefinierten Sinne optimal sein.
* Die Methode zur Bestimmung dieses optimalen Teilbaums sollte rechnerisch handhabbar sein.

<span>''<math display="inline">\mathrm{\ \ \ \ \ \ }</math> Fehlklassifizierungsrate''</span>

Die Fehlklassifizierungsrate ist die Wahrscheinlichkeit der Fehlklassifizierung (misclassification) in einem bestimmten Blattknoten, welche durch die Resubstitutionsschätzung (resubstitution estimate) <math display="inline">r(t)</math> charakterisiert wird. Aufgrund der Klassenzuweisungsregel (class assign rule), dass jedem Blatt die Klasse mit der höchsten Wahrscheinlichkeit zugewiesen wird, ist <math display="inline">r(t)</math> gegeben als

<math display="block">r(t) = 1- p(c^*(t)|t) = 1 - \max_{c}  p(c|t).</math>

Wir definieren <math display="inline">R(t)= r(t)p(t)</math>. Seien <math display="inline">T</math> und <math display="inline">\tilde{T}</math> die Bezeichnungen des gesamten Baums bzw. der Menge der Blattknote. Der Klassifizierungsfehler für den gesamten Baum, <math display="inline">R(T)</math>, ist definiert als die Summe der gewichteten Resubstitutionsschätzung über die Menge der Blattknoten, <math display="inline">\tilde{T}</math>, mit anderen Worten <math display="block">R(T) = \sum_{t \in \tilde{T}} R(t) = \sum_{t \in \tilde{T}} r(t)p(t).</math>

Eine wesentliche Aussage ist, dass die Aufteilung eines Knotens in zwei Kindknoten immer den Klassifizierungsfehler für den gesamten Baum verringert. Dies folgt aus <math display="block">R(t) \geq R(t_L) + R(t_LR),</math>

welches eine Folge der Klassenzuweisungsregel ist und kann wie folgt nachgewiesen werden.

<math display="block">\begin{aligned}
p(c^*(t)|t) &= p(c^*(t), t_L|t) + p(c^*(t), t_R|t) = p(c^*(t)| t_L)p(t_L|t) + p(c^*(t)|t_R)p(t_R|t) \\
&= p(c^*(t)| t_L)p(t_L|t) + p(c^*(t)|t_R)p(t_R|t) = p_L p(c^*(t)| t_L) + p_R p(c^*(t)|t_R) \\
&\leq p_L \max_{c}  p(c|t_L) + p_R \max_{c}  p(c|t_R). 
\end{aligned}</math>

Daher gilt <math display="block">\begin{aligned}
r(t) &= 1- p(c^*(t)|t) \geq 1 - \left(p_L \max_{c}  p(c|t_L) + p_R \max_{c}  p(c|t_R) \right) \\
&= p_L \left(1-\max_{c}  p(c|t_L)\right) + p_R \left(1-\max_{c}  p(c|t_R)\right)= p_L r(t_L) + p_R r(t_R), 
\end{aligned}</math>

aus denen <math display="block">\begin{aligned}
R(t) &= p(t)r(t) \geq p(t) p_L r(t_L) + p(t) p_R r(t_R) \\
&= p(t_L)r(t_L) + p(t_R)r(t_R) = R(t_L)+R(t_R)
\end{aligned}</math> folgt.

<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Minimal Cost-Complexity Pruning'''''</span>

<span>''<math display="inline">\mathrm{\ \ \ \ \ \ }</math> Begriffe und Notationen''</span>

Zur Beschreibung des Prunings werden verschiedene Begriffe und Notationen eingeführt.

* Descendant (Nachkomme): Ein Knoten <math display="inline">t_2</math> ist ein Descendant von Knoten <math display="inline">t_1</math>, wenn es einen Pfad von <math display="inline">t_1</math> nach unten im Baum zu Knoten <math display="inline">t_2</math> gibt.
* Ancestor (Vorfahr): <math display="inline">t_1</math> ist Ancestor von <math display="inline">t_2</math>, wenn <math display="inline">t_2</math> ein Descendant von <math display="inline">t_1</math> ist.
* Branch (Zweig) <math display="inline">T_t</math> des Baums <math display="inline">T</math> mit Wurzelknoten <math display="inline">t \in T</math>: besteht aus Knoten <math display="inline">t</math> und allen seinen Descendants.
* Pruning a branch (Das Beschneiden eines Zweigs) <math display="inline">T_t</math> aus einem Baum <math display="inline">T</math> bedeutet das Löschen aller Knoten des Zweigs <math display="inline">T_t</math>, außer dem Wurzelknoten.

<span>''<math display="inline">\mathrm{\ \ \ \ \ \ }</math> Kosten-Komplexität-Kriterium (cost-complexity criterion) zum Finden des optimalen Teilbaums''</span>

Der Klassifizierungsfehler <math display="inline">R(T)</math> ist kein geeignetes Maß, um den optimalen Teilbaum (optimal subtree) zu finden, da er mit zunehmendem Baum monoton abnimmt und somit den größten Baum bevorzugt. Das Hinzufügen eines Strafterms (penalty term), der kleinere Bäume bevorzugt, führt jedoch zu einem ausgewogenen Maß (balanced measure), dessen Minimierung zum Finden des optimalen Teilbaums geeignet ist.

Sei <math display="inline">|\tilde{T}|</math> die Anzahl der Blattknoten in der Menge <math display="inline">\tilde{T}</math> und <math display="inline">\eta</math> ein Komplexitätsparameter (complexity parameter). Die Kosten-Komplexität (cost-complexity) eines Baums <math display="inline">T</math> ist durch

<math display="block">R_{\eta}(T) = R(T) + \eta |\tilde{T}|</math> definiert.

Weiterhin sei <math display="inline">T_0</math> der initiale Baum (initial tree), der durch Wachstum auf eine ausreichend große Größe erhalten wird, und <math display="inline">\hat{T}</math> die Menge der Teilbäume des Baums <math display="inline">T</math>. Dann soll der optimale Teilbaum eine minimale Kosten-Komplexität aufweisen <math display="block">\arg\min_{T \in \hat(T_0)} R_{\eta}(T) = \min_{T \in \hat(T_0)} \left(R(T) + \eta |\tilde{T}|\right).</math>

Hier begünstigt der Strafterm <math display="inline">\eta |\tilde{T}|</math> in der Zielfunktion (objective function) kleinere Bäume und der Komplexitätsparameter <math display="inline">\eta</math> gibt die Wichtigkeitsgewichtung (importance weight) der Größe des Baums an.

Es kann vorkommen, dass mehrere Teilbäume dieselbe minimale<br />
Kosten-Komplexität aufweisen, z. B. einer mit kleinerer Größe, aber höherem Klassifizierungsfehler. In diesem Fall wird der Teilbaum mit der kleinsten Größe bevorzugt. Daher kann der optimale Teilbaum <math display="inline">T^*(\eta)</math> als der mit der minimalen Größe unter der Teilbäume mit minimaler Kosten-Komplexität angegeben werden. Es kann wie folgt als Optimierungsproblem formuliert werden. <math display="block">\begin{aligned}
T^*(\eta) &= \arg\min_{T \in \hat{T}_0} R_{\eta}(T) = \arg\min_{T \in \hat{T}_0} \left(R(T) + \eta |\tilde{T}|\right), \\
|T^*(\eta)| &\leq T(\eta) \mathrm{\ \ }\mathrm{~fuer~alle~} \mathrm{\ \ } T(\eta) \mathrm{~mit~} T(\eta) = T^*(\eta).
\end{aligned}</math>

Da es nur endlich viele Teilbäume des Baums <math display="inline">T_0</math> gibt, ergibt <math display="inline">R_{\eta}(T^*(\eta))</math> nur für endlich viele <math display="inline">\eta</math>-s unterschiedliche Werte. Daher ist <math display="inline">R_{\eta}(T^*(\eta))</math> als Funktion von <math display="inline">\eta</math> eine stückweise Treppenfunktion mit Sprüngen (piecewise step function with jumps).

<span>''<math display="inline">\mathrm{\ \ \ \ \ \ }</math> Weakest-Link-Cutting''</span>

Wir erweitern die Definition der Kosten-Komplexität vom Baum auch auf Knoten. Für den Knoten <math display="inline">t \in T</math> ist seine Kosten-Komplexität als

<math display="block">R_{\eta}(t) = R(t) + \eta</math> definiert.

Die Weakest-Link-Cutting-Methode bestimmt den optimalen Teilbaum durch Durchlaufen der optimalen Teilbäume <math display="inline">R_{\eta}(T^*(\eta))</math> als Funktion von <math display="inline">\eta</math> von <math display="inline">\eta=0</math> bis <math display="inline">\eta=1</math>, indem sie den nächsten Sprungpunkt (jump point) in <math display="inline">\eta</math> rekursiv bestimmt. Das Durchlaufen der optimalen Teilbäume erfordert für jeden Knoten <math display="inline">t</math> den Vergleich von

<math display="block">\begin{aligned}
R_{\eta}(t) &= R(t) + \eta \mathrm{\ \ }\mathrm{~und~} \\
R_{\eta}(T_t) &= R(T_t) + \eta |\tilde{T}_t|.
\end{aligned}</math>

Beginnend mit <math display="inline">\eta=0</math> wissen wir bereits, dass <math display="inline">R_{0}(T_t) < R_0(t)</math> für jedes <math display="inline">t \in T_0</math>, d.h. der optimale Teilbaum für <math display="inline">\eta =0</math> ist der initiale Baum <math display="inline">T_0</math> selbst. Diese Ungleichung gilt auch für einige kleine <math display="inline">\eta</math>. Durch schrittweises Erhöhen von <math display="inline">\eta</math> wird der Punkt erreicht, an dem <math display="inline">R_{\eta}(T_t) = R_{\eta}(t)</math>, da der Koeffizient von <math display="inline">\eta</math> in <math display="inline">R_{\eta}(T_t)</math> größer als in <math display="inline">R_{\eta}(t)</math> ist. Der Wert von <math display="inline">\eta</math> an diesem Punkt kann aus der Gleichheit bestimmt werden, was zum Wert

<math display="block">\frac{R(t) - R(T_t)}{|\tilde{T}_t|-1}.</math> an diesem Gleichheitspunkt (equality point) führt.

Direkt über diesem <math display="inline">\eta</math> ist der Wert <math display="inline">R_{\eta}(T_t) > R_{\eta}(t)</math>, was bedeutet, dass das Pruning des Zweigs <math display="inline">T_t</math> zu einem Teilbaum mit geringerer Kosten-Komplexität führt. Es kann jedoch vorkommen, dass dieser Gleichheitspunkt für einen anderen Knoten früher erreicht wird, d. h. bei geringerem <math display="inline">\eta</math>. Daher tritt der erste Sprung in minimaler Kosten-Komplexität, <math display="inline">R_{\eta}(T^*(\eta))</math>, am Gleichheitspunkt mit dem kleinsten <math display="inline">\eta</math> unter den Gleichheitspunkten aller Nicht-Blattknoten (non-leaf nodes) des Baums <math display="inline">T_0</math> auf. Der Wert von <math display="inline">\eta</math> an diesem Sprungpunkt von <math display="inline">R_{\eta}(T^*(\eta))</math> wird mit <math display="inline">\eta_1</math> bezeichnet und kann wie folgt berechnet werden.

<math display="block">\eta_1 = \min_{t \in T_0\ \tilde{T}_0} \frac{R(t) - R(T_t)}{|\tilde{T}_t|-1}.</math>

Sei <math display="inline">t_1</math> der Knoten, an dem diese erste Gleichheit auftritt, mit anderen Worten <math display="block">t_1 = \arg\min_{t \in T_0\ \tilde{T}_0} \frac{R(t) - R(T_t)}{|\tilde{T}_t|-1}.</math> Then just above <math display="inline">\eta_1</math> the optimal subtree, i.e. the subtree with the smallest cost-complexity is the one, which is obtained by pruning the branch <math display="inline">T_{t_1}</math> from <math display="inline">T_0</math>, which is denoted as <math display="inline">T_1= T_0 \ T_{t_1}</math>. Repeating the gradually increase of <math display="inline">\eta</math> and the computation of the next jump point based on the cost-complexity of the actual optimal subtree, a recursive algorithm can be defined to obtain the jump points <math display="inline">\eta_i</math> and the optimal subtrees in the individual <math display="inline">\eta</math> regions. In each step the algorithm prunes the branch, whose cost-complexity becomes larger than the one of its root node at earliest in <math display="inline">\eta</math>, which can be seen as the weakest-link. That is why the algorithm is called weakest-link cutting algorithm. Its schematic operation is given in Algorithm .

Dann ist knapp über <math display="inline">\eta_1</math> der optimale Teilbaum, d. h. der Teilbaum mit der geringsten Kosten-Komplexität, derjenige, der durch Pruning den Zweig <math display="inline">T_{t_1}</math> von <math display="inline">T_0</math> erhalten wird, was als <math display="inline">T_1= T_0 \ T_{t_1}</math> bezeichnet wird. Durch Wiederholen der schrittweisen Erhöhung von <math display="inline">\eta</math> und der Berechnung des nächsten Sprungpunkts basierend auf der Kosten-Komplexität des aktuell optimalen Teilbaums kann ein rekursiver Algorithmus definiert werden, um die Sprungpunkte <math display="inline">\eta_i</math> und die optimalen Teilbäume in den einzelnen <math display="inline">\eta</math>-Regionen zu erhalten. In jedem Schritt führt der Algorithmus das Pruning den Zweig durch, dessen Kostenkomplexität in <math display="inline">\eta</math> am frühesten größer wird als die seines Wurzelknotens, der als Weakest-Link (schwächstes Glied) angesehen werden kann. Aus diesem Grund wird der Algorithmus als Weakest-Link-Cutting-Algorithmus (Algorithmus zum Beschneiden des schwächsten Glieds) bezeichnet. Seine schematische Funktionsweise ist im Algorithmus  angegeben.

<br />
Algorithm  Weakest-Link-Cutting-Algorithmus<br />
<span>'''—————————————————————————————'''</span><br />
Eingabe:<br />
- der initiale Baum <math display="inline">T_0</math> Ausgabe:<br />
- Folge von Sprungpunkten <math display="inline">\eta_i</math>, <math display="inline">i \geq 1</math>, - Folge von optimalen Teilbäumen <math display="inline">T_i</math> in den einzelnen Regionen <math display="inline">[\eta_{i} - \eta_{i+1})</math>, <math display="inline">i \geq 0</math> und <math display="inline">\eta_0 =0</math>.<br />
<span>'''—————————————————————————————'''</span><br />
1 Initialisierung: <math display="inline">T_{act} = T_0</math>, <math display="inline">\eta_{act} = 0</math>, <math display="inline">\eta_{next} = 0</math>, <math display="inline">\mathrm{\ \ \ \ \ }</math> <math display="inline">\eta[]=0</math>, <math display="inline">t[]=0</math>, <math display="inline">T[]=0</math>, <math display="inline">\eta[0]=0</math>, <math display="inline">T[0]=T_0</math>, <math display="inline">i=1</math><br />
2 while <math display="inline">\eta_{next} < 1</math><br />
3    <math display="inline">\Delta \eta = \min_{t \in T_{act}\ \tilde{T}_{act}} \frac{R(t) - R(T_t)}{|\tilde{T}_t|-1}</math><br />
4    <math display="inline">\eta_{next} = \eta_{act} + \Delta \eta</math><br />
5    <math display="inline">\eta[i]=\eta_{next}</math><br />
6    <math display="inline">t[i] = \arg\min_{t \in T_{act}} \ \tilde{T}_{act} \frac{R(t) - R(T_t)}{|\tilde{T}_t|-1}</math><br />
7    <math display="inline">T[i]= T_{act} \ T_{t[i]}</math><br />
8    Update <math display="inline">T_{act} = T[i]</math>, <math display="inline">\eta_{act} = \eta_{next}</math><br />
9    Inkrement <math display="inline">i</math> as <math display="inline">i=i+1</math><br />
10 end<br />
<span>'''—————————————————————————————'''</span><br />


<span id="eigenschaften-des-entscheidungsbaums"></span>
=== Eigenschaften des Entscheidungsbaums ===

Ein wesentliches Merkmal des Entscheidungsbaumansatzes (decision tree approach) ist, dass der Raum seiner Eingabevektoren explizit vorgegeben ist, d. h. die Dimensionen der Eingabevektoren sind explizit bekannt. Dies ist ein wesentlicher Unterschied zu HMMs oder neuronalen Netzwerken, deren Eingabevektoren (=Featurevektoren) implizit bestimmt werden.

Nachfolgend wird eine Liste über die Vorteile des Entscheidungsbaumansatzes angeführt.

* Der Entscheidungsbaumansatz verarbeitet nicht nur Ordinalvariablen (Ordinalskala), sondern auch kategorische Variablen (Nominalskala).
* Der Entscheidungsbaumansatz ist invariant gegenüber monotonen Transformationen der Featurekomponenten als Ordinalvariablen.
* Der Entscheidungsbaumansatz liefert eine Schätzung der Fehlklassifizierungsrate für jede Klasse.
* Der Entscheidungsbaum ist robust gegenüber fehlklassifizierten Punkten (misclassified points) im Trainingsdaten und Ausreißern (outliers).
* Der Entscheidungsbaum ist leicht zu interpretieren, was ihn insbesondere in medizinischen Anwendungsszenarien attraktiv macht.

<span id="subsub:RF"></span>
=== Random Forest ===

<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Bootstrap-Aggregation - Bagging'''''</span>

Das bisher besprochene Training ist ein deterministischer Prozess, der dieselben Parameter aus demselben Trainingsdaten ergibt. Ein anderer Ansatz besteht darin, eine zufällige Komponente in den Trainingsprozess einzuführen und mehrere Durchläufe desselben Trainingsdaten mit dem zufällig modifizierten Trainingsprozess durchzuführen. Eine solche zufällige Modifikation kann beispielsweise darin bestehen, in jedem Durchgang eine zufällig ausgewählte Teilmenge der Trainingsdaten zu nehmen und nur diese Teilmenge für das Training in diesem Durchgang zu verwenden. Die Ergebnisse nach jedem Durchgang werden angesammelt und das Endergebnis wird aus der Sammlung der Ergebnisse durch eine zweckmäßige Kombination erstellt. Hier sind die Ergebnisse beispielsweise die Parameter des Modells. Die Kombination der angesammelten Ergebnisse kann beispielweise durch Mittelwertbildung (by averaging), gewichtete Mittelwertbildung (by weighted averaging), Berechnung des Medians (computing the median) oder durch Anwendung einer Mehrheitswahl (majority voting) erfolgen. Dieser Ansatz wird als Bootstrap-Aggregation genannt oder mit dem Akronym Bagging bezeichnet.

Das Ziel von Bagging ist normalerweise, die Varianz im Ergebnis zu verringern. Die Varianz des Stichprobenmittelwerts nimmt proportional zur Anzahl der Stichproben ab und daher das Ansammlung und Mittelwertbildung mehrerer Ergebnisse eine reduzierende Wirkung auf die Varianz hat.

Bootstrap-Aggregation hat mehrere Vorteile.

* Die Mittelung über eine Sammlung trainierter Parameter reduziert Overfitting, da sie die erfasste Entwicklung zwischen den Trainingsbeispielen, die von der zugrunde liegenden Verteilung abweichen, teilweise aufhebt.
* Die Mittelung über eine Sammlung trainierter Parameter führt zu einem stabileren Endergebnis.
* Modelle mit hoher Kapazität können aufgrund der reduzierten Overfitting eine flexiblere Anpassung (fitting) erreichen.
* Die Mittelung über eine Sammlung trainierter Parameter führt zum Aufbrechen des Bias-Varianz-Kompromisses (siehe in Absatz [[#subsec:bias_variance|[subsec:bias_variance]]]), indem die Varianz neben dem gleichen Bias reduziert wird.

Bootstrap-Aggregation wurde von Leo Breiman [Breiman(1996)] entwickelt.

<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Random Forest'''''</span>

Random Forest ist eine Bootstrap-Aggregation, die auf Klassifizierungs- und Regressionsbäume angewendet wird. In Random Forest werden mehrere Bäume trainiert. Während des Trainings jedes Baums wird nur eine zufällig ausgewählte Teilmenge von Komponenten des Eingabevektoren berücksichtigt, die für die Aufteilung verwendet wird.

Leo Breiman hat umfangreiche Experimente mit Random Forest durchgeführt. Er fand heraus, dass es insgesamt etwas besser abschneidet als Support Vector Machines.

<span id="convolutional-neural-networks-für-bildverarbeitung"></span>
== Convolutional Neural Networks für Bildverarbeitung ==

Convolutional Neural Networks (CNNs) sind eine Subklasse von KNNs, die sich für die Verarbeitung von Eingaben in Gridform, insbesondere von Bildern, eignen. Die Convolutional im Namen von CNN ergibt sich aus der Convolution Layer, die den Kernbaustein von CNN ist. Der Convolution Layer realisiert einen mathematischen Convolution (= Faltungsoperation). CNNs eignen sich besonders zum Extrahieren lokales Features und komplexerer Muster wie Texturen (textures). Hier lokal bedeutet, dass diese Features nur von den Pixeln abhängen, die sich um das betrachtete Pixel herum befinden.

Als Beispiel nehmen wir ein Feature, das durch Subtrahieren des Werts des linken Nachbarpixels vom Wert jedes einzelnen Pixels erstellt wird. Diese Funktion eignet sich zur Erkennung von Konturen, genauer gesagt von Kanten mit vertikalen Komponenten, was eine mögliche Teilaufgabe der Objekterkennung darstellt. Dies ist in Abbildung [[#fig:CNN_9.6|34]] dargestellt.

<div id="fig:CNN_9.6" class="figure">

[[Datei:CNN_9.6.jpg|460px|thumb|center|Abbildung 34: Vertikale Kantenerkennung (Quelle: [Goodfellow et al.(2016)]).]] <span id="fig:CNN_9.6" label="fig:CNN_9.6"></span>


</div>


Das Bild auf der rechten Seite zeigt die Anwendung des Feature zur Konturerkennung auf das Originalbild auf der linken Seite.

<span id="die-mathematische-convolution"></span>
=== Die mathematische Convolution ===

Die stetige Version des Faltungsoperators ist ein Integral einer Multiplikation zweier Funktionen <math display="inline">x(\tau)</math> und <math display="inline">w(t-\tau)</math>, über die reellwertige Variable <math display="inline">\tau</math> als

<math display="block">s(t) = \int x(\tau) w(t-\tau) d\tau.</math>

Das resultierende Integral hängt nur von <math display="inline">t</math> ab. Solche Operatoren kommen in vielen technischen Teilgebieten vor, wie z.B. Beschreiben der Wahrscheinlichkeitsdichtefunktion der Summe zweier unabhängiger Zufallsvariablen mit den Wahrscheinlichkeitsdichtefunktionen <math display="inline">x(t)</math> und <math display="inline">w(t)</math> oder Entrauschen des Signals <math display="inline">x(t)</math> durch Bildung seines gewichteten Durchschnitts durch Anwendung von <math display="inline">t</math> abhängige Gewichte <math display="inline">w(t)</math>.

Das Argument des Integrals reicht in seiner allgemeinsten Form von <math display="inline">-\infty</math> bis <math display="inline">\infty</math>, hängt aber normalerweise vom Kontext ab. Im Beispiel pdf der Summe unabhängiger nicht negativer Zufallsvariablen geht das Integral von <math display="inline">0</math> bis unendlich, während im zweiten Beispiel <math display="inline">t</math> die Zeit darstellen kann und das Integral von <math display="inline">0</math> bis <math display="inline">t</math> geht. Werte für <math display="inline">\tau > t</math> zu haben, würde bedeuten, auch zukünftige Werte des Signals <math display="inline">x(\tau)</math> in die Berechnung des entrauschten Werts bei <math display="inline">t</math>, <math display="inline">s(t)</math>, einzubeziehen, was normalerweise im realen Kontext nicht möglich ist.

Die Convolution wird in der Regel mit einem Sternchen bezeichnet. <math display="block">s(t) = (x*w)(t) ~  \mathrm{~oder~vereinfacht~} s=x*w.</math> Die erste und die zweite Funktion, <math display="inline">x(t)</math> und <math display="inline">w(t)</math> werden als Eingabe und Kernel bezeichnet. Die Ausgabefunktion, <math display="inline">s(t)</math>, wird im neuronalen Netzwerkkontext auch als Feature-Map genannt.

<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Die diskrete Convolution'''''</span>

Die diskrete Convolution ist analog definiert und kann als <math display="block">s(n) = \sum_{m=-\infty}^{\infty} x(m) w(n-m)</math> angegeben werden.

<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Die zweidimensionale Convolution'''''</span>

Convolution kann auch als mehrdimensionaler Operator definiert werden. Die zweidimensionale diskrete Convolution kann wie folgt angegeben werden: <math display="block">S(n,m) = (I*K)(n,m)= \sum_{i}\sum_{j} I(i,j) K(n-i,m-j).</math>

Bei Anwenden auf ein Bild, beschreibt <math display="inline">I</math> das zweidimensionale Bild und <math display="inline">K</math> ist ein zweidimensionaler Kernel. Beide werden als zweidimensionales endliches Array dargestellt und die resultierende Matrix, <math display="inline">S(n,m)</math> wird als Ausgabematrix genannt. In diesem Fall können die Funktionen <math display="inline">I(n,m)</math> und <math display="inline">K(n,m)</math> in der oben angeführten Formel mit Ausnahme einer endlichen Menge von Punkten als Null angenommen werden. Auf diese Weise kann die unendliche Summe in der Convolution tatsächlich eine endliche Summe auch darstellen. Mehrdimensionale Arrays werden auch als Tensoren bezeichnet.

Die Convolution ist ein kommutativer Operator, was bedeutet, dass <math display="inline">S(n,m)</math> auch als <math display="block">S(n,m) = (K*I)(n,m)= \sum_{i}\sum_{j} I(n-i,m-j)K(i,j)</math> angegeben werden kann. Dies kann gezeigt werden, wenn den Umtausch <math display="inline">(n-i) \rightarrow i</math> und <math display="inline">(m-j) \rightarrow j</math> im Expression von <math display="inline">(I*K)(n,m)</math> mit Summierung über <math display="inline">-\infty</math> zu <math display="inline">\infty</math> durchgeführt werden. Dieser Ausdruck von <math display="inline">S(n,m)</math> wird auch als Form mit Kernel-Flipping bezeichnet. Normalerweise ist dies die Form, die im ML-Kontext implementiert wird.

<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Illustration der Convolution'''''</span>

Die Anwendung der zweidimensionalen Convolution lässt sich anhand der Form mit Kernel-Flipping veranschaulichen. Die Gewichte werden in einem Kernelfenster angeordnet (d.h. die Elemente von K()) und auf das Bildfeld des Pixels angewendet, über denen das Kernelfenster positioniert ist. Dies ergibt einen Wert der Ausgabe. Durch horizontales und vertikales Verschieben des Kernelfensters über alle möglichen Positionen ergeben sich alle Werte des Ausgabetensors. Dies wird in Abbildung [[#fig:CNN_conv_oper|35]] dargestellt.

<div id="fig:CNN_conv_oper" class="figure">

[[Datei:CNN_conv_oper.jpg|460px|thumb|center|Abbildung 35: Illustration der 2D-Convolution anhand des Kernelfensters basierend auf der Form mit Kernel-Flipping (Quelle: [Reynolds(2021)]).]] <span id="fig:CNN_conv_oper" label="fig:CNN_conv_oper"></span>


</div>
 Beispielsweise kann die Convolution der vertikalen Kantenerkennung, die in Abbildung [[#fig:CNN_9.6|34]] illustriert wurde, mit dem in Abbildung [[#fig:CNN_own_1|36]] dargestellten Kernelfenster realisiert werden.

<div id="fig:CNN_own_1" class="figure">

[[Datei:kernel_matrix_vertical_edge_detection.jpg|460px|thumb|center|Abbildung 36: Kernelfenster der vertikalen Kantenerkennung.]] <span id="fig:CNN_own_1" label="fig:CNN_own_1"></span>


</div>


<span id="motivation-aus-rechnerischer-sicht"></span>
=== Motivation aus rechnerischer Sicht ===

Die Anwendung der Convolution in NN ist auch aus rechnerischer Sicht vorteilhaft. Die rechnerischen Vorteile der Verwendung der Convolution in NNs zum Extrahieren lokaler Features können wie folgt aufgeführt werden:

* Sparse Connectivity (dünn besetzte Konnektivität),
* Parameter-Sharing und
* Äquivarianz zu verschieben (eqivariance to shift).

<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Sparse Connectivity'''''</span>

Lokale Features werden nur durch eine begrenzte Anzahl benachbarter Pixel beeinflusst. Bei seiner Realisierung ist jede Einheit der nächsten Layer nur mit einigen Einheiten der tatsächlichen Layer verbunden. Wenn jede Einheit der nächsten Layer nur mit <math display="inline">k</math> der <math display="inline">n</math> Einheiten der tatsächlichen Layer verbunden ist, verringert sich die erforderliche Anzahl von Operationen an jeder Einheit der nächsten Layer ebenfalls um <math display="inline">\mathcal{O}(n)</math> zu <math display="inline">\mathcal{O}(k)</math>. Dies ist eine große Errungenschaft, da <math display="inline">k</math> normalerweise mehrere Größenordnungen kleiner als <math display="inline">n</math> sein kann. Diese Sparse Connectivity, sowohl von unten als auch von oben betrachtet, ist in Abbildung [[#fig:CNN_9.2_9.3|37]] dargestellt.

<div id="fig:CNN_9.2_9.3" class="figure">

{| class="wikitable"
|-
| style="text-align: left;"| [[Datei:CNN_9.2.jpg|460px|thumb|center|]]
| style="text-align: left;"| [[Datei:CNN_9.3.jpg|460px|thumb|center|]]
|}
Abbildung 37: Sparse Connectivity von unten (Links) und von oben (Rechts) (Quelle: [Goodfellow et al.(2016)]).
</div>


In einem tiefen CNN mit mehr Hidden Layer können die tieferen Hidden Layer jedoch indirekt mit mehr Eingabeeinheiten interagieren. Dies ist in Abbildung [[#fig:CNN_9.4|38]] dargestellt.

<div id="fig:CNN_9.4" class="figure">

[[Datei:CNN_9.4.jpg|460px|thumb|center|Abbildung 38: Der rezeptive Bereich der Einheiten in tieferen Hidden Layer (Quelle: [Goodfellow et al.(2016)]).]] <span id="fig:CNN_9.4" label="fig:CNN_9.4"></span>


</div>


<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Parameter-Sharing'''''</span>

Die Verwendung der Convolution in NN bedeutet, dass auch für Bildfelder von mehreren Pixels dieselben Gewichte angewendet werden, siehe Abbildung [[#fig:CNN_conv_oper|35]] im Falle von 2-D-Convolution. Dies wird als Parameter-Sharing bezeichnet. In einem Fully-Connected neuronalen Netzwerkmodell wird jeder Gewichtungsparameter nur einmal verwendet, um genau eine Eingabeeinheit zu gewichten und nur einen Ausgabewert zu berechnen. Im Convolutional Neuronalen Netzen wird jedes Gewicht im Kernel für jede Eingabeeinheit verwendet.

<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Äquivarianz zu verschieben'''''</span>

Die Äquivarianz von Convolution und Verschiebung bedeutet, dass der Umtausch der Reihenfolge von Convolution und Verschiebung das Ergebnis nicht ändert. Daraus folgt, dass die Anwendung desselben Convolution Kernel auf ein verschobenes Bild zur gleichen Ausgabe führt, jedoch verschoben. Daher können Teilaufgaben wie z.B. die Konturerkennung mit den gleichen Gewichtsparametern (d. h. mit den gleichen lokalen Features) im gesamten Bild unabhängig von der verschobenen Position des Objekts durchgeführt werden. Somit die Einführung eines neuen lokalen Features wegen der Verschiebung des Bildes ist nicht erforderlich. Aber die Convolution hat keine Äquivarianz zu anderen Transformationen wie der Drehung oder Skalierung eines Bildes.

<span id="pooling"></span>
=== Pooling ===

Jedes Element des Ausgabetensors der Convolution liefert einen Wert über das lokale Feature, das der Kernel an dieser Position realisiert. Pooling reduziert die Dimensionen der Ausgabe, indem die Ausgaben von Clustern neuronaler Einheiten zu einer Ausgabe kombiniert werden. Dies kann auch als eine zusammenfassende Statistik gesehen werden.

<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Typische Pooling Operationen'''''</span>

Zu den typischen Pooling Operationen gehören Max-Pooling, Average-Pooling, <math display="inline">L^2</math>-Norm-Pooling oder Weighted-Average-Pooling. Max-Pooling liefert die maximale Ausgabe unter den benachbarten Positionen innerhalb eines rechteckigen Bereichs. Dies ist beispielsweise bei der Konturerkennung sinnvoll, um den schärfsten Unterschied zwischen den benachbarten Pixelwerten extrahieren, der die wahrscheinlichste Position der Kontur darstellt. Das Average-Pooling gibt den Durchschnitt der Ausgaben innerhalb eines rechteckigen Bereichs um die betrachtete Position zurück. Dies ist sinnvoll, z.B. bei Teilaufgaben wie der Einstufung eines bestimmten lokalen Feature, bei dem die räumliche Dichte der größeren Ausgabewerte dieses lokalen Feature proportional zum ausgabenden Wert ist. Ebenso bezieht sich die Norm <math display="inline">L^2</math> auch auf die Ausgaben innerhalb eines rechteckigen Bereichs um die betrachtete Position. Das Weighted-Average-Pooling berechnet gewichtete Summen unter Anwendung von Gewichtungen basierend auf der Entfernung von der betrachteten Position.

<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Lerninvarianz'''''</span>

Pooling kann zum Lernen der skaleninvarianten und/oder orientierungsinvarianten Detektion von Features verwendet werden. Dies wird dadurch realisiert, dass Pooling auf separat parametrisierte Convolutionen angewendet wird. Dies ist für den Fall der Zeichenerkennung von Zahlen mit unterschiedlichen Orientierungen in Abbildung [[#fig:CNN_9.9|39]] dargestellt.

<div id="fig:CNN_9.9" class="figure">

[[Datei:CNN_9.9.jpg|460px|thumb|center|Abbildung 39: Erlernen des Erkennens des Zahlzeichens ,5“ invariant zu seiner Position (Quelle: [Goodfellow et al.(2016)]).]] <span id="fig:CNN_9.9" label="fig:CNN_9.9"></span>


</div>


Jede Einheit der Convolution Layer (Convolution Unit) ist parametrisiert, um eine große Ausgabe für unterschiedlich positionierte Zahlenzeichen „5“ zu liefern. Die Versorgung einer Max-Pooling-Einheit mit diesen Ausgaben führt zu einer großen Ausgabe für jedes der unterschiedlich positionierten Zahlenzeichen „5“. Basierend auf das Label „5“ kann das Modell darauf trainiert werden, das Zahlenzeichen „5“ zu erkennen, das von seiner Position abhängt.

<span id="convolution-block"></span>
=== Convolution Block ===

<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Nichtlineare Aktivierungsfunktion'''''</span>

Die Ausgabe jeder Convolution Unit durchläuft normalerweise eine nichtlineare Aktivierungsfunktion (nonlinear activation function), bevor sie zur Einheit der Pooling Layer (Pooling Unit) gelangt. Die nichtlineare Aktivierungsfunktion führt zumindest annähernd eine Abbildung eines bestimmten Eingabebereichs auf einen Ausgabewert (z.B. 0 oder 1) durch. Dies kann so gesehen werden, dass einige Eingabewerte gezwungen werden, sich einem vordefinierten Ausgabewert anzunähern, wodurch im Wesentlichen eine Polarisierung oder Detektorfunktionalität (detection functionality) realisiert wird. Eine der am häufigsten verwendeten nichtlinearen Aktivierungsfunktionen in CNN ist die Rectified Linear Unit, <math display="inline">ReLU(z)</math>.

<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Zusammensetzung eines Convolution Blocks'''''</span>

Ein typischer Convolution Block besteht aus drei Komponenten, in der folgenden Reihenfolge.

# Convolutional Layer
# Detektor Layer (=Nichtlineare Aktivierungsfunktion)
# Pooling Layer

In Diagrammen von CNN-Architekturen werden die Nichtlineare Aktivierungsfunktion oft mit Convolutional Layer zusammen in einem gemeinsamen rechteckigen Box dargestellt. In der sogenannten komplexen Layer-Terminologie werden die drei Komponenten als „Stages“ genannt und die Komponente zusammen als Convolutional Layer.

<span id="weitere-typische-layers-eines-cnns"></span>
=== Weitere typische Layers eines CNNs ===

<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Flatten Layer'''''</span>

Die Flatten Layer wird benötigt, um die Ausgabenwerten in 2D-Matrixform in einen Vektor umzuwandeln, der die Einspeisung in die Dense Layer ermöglicht. Diese Layer hat keine Parameter zu trainieren.

<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Dense Layer'''''</span>

Die Dense Layer (dichte Schicht) ist eine Fully-Connected Layer (vollständig verbundene Schicht), also jede ihrer Einheiten mit der Ausgaben aller Einheiten der vorherigen Layer verbunden ist. Die Dense Layer lernt, die Features auf hohem Abstraktionsniveau aus den Convolution Blocks zu kombinieren, um die Klassifizierungsaufgabe zu erfüllen.

<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Dropout layer'''''</span>

Die Dropout Layer realisiert eine so genannte Regularisierungstechnik ([https://en.wikipedia.org/wiki/Regularization_(mathematics) regularization technique]), um die Overfitting zu reduzieren. Sie wendet Dropout an, bei dem die Ausgabe zufällig ausgewählter Einheiten in jeder Trainingsphase auf Null gesetzt wird. Dies führt zu einem zufällig unterschiedlichen Menge aktiver Neuralen Einheiten in jeder Trainingsphase, was das Netzwerk dazu anregt, weniger empfindlich auf die Gewichte bestimmter Neuralen Einheiten zu reagieren und so zu einer höheren Generalisierungsfähigkeit führt.

<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Output layer'''''</span>

Die Output Layer hat so viele Einheiten wie die Anzahl der Klassen in der Klassifizierungsaufgabe. Bei Klassifizierungsaufgaben mit mehreren Klassen besteht sie nur aus einer Softmax Funktion, die die Ausgabe der vorherigen Ebene in Wahrscheinlichkeiten der einzelnen Klassen umwandelt. Das Ergebnis der Klassifizierungsaufgabe, d. h. die vorhergesagte Klasse, ist dann derjenige mit der höchsten Wahrscheinlichkeit.

<span id="convolution-in-der-praxis"></span>
=== Convolution in der Praxis ===

Normalerweise wendet ein CNN viele Convolution an, um mehr Features extrahieren zu können. Um die Effizienz des Trainings zu erhalten, wird dieses als Parallelrechnung (parallel computation), z.B. durch Ausnützung der Parallelrechner-Fähigkeiten einer Grafikkarte implementiert.

<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Convolution on grid of vectors'''''</span>

Bisher wurde das Eingabebild (input image) als Raster realer Werte behandelt. In der Praxis handelt es sich bei der Eingabe eines CNN jedoch eher um ein Gitter von Vektoren (grid of vectors). Beispielsweise wird jedes Pixel eines Farbbildes durch ein Vektor der Dimension 3 beschrieben, die die Intensitäten von Rot, Grün und Blau beschreiben.

<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Zero Padding'''''</span>

Die Darstellung der Convolution durch Verschieben des Kernelfensters zeigt sofort, dass die Convolution mit der Kernelbreite (kernel width) <math display="inline">k</math> dazu führt, dass die Ausgabebreite(output width) mit <math display="inline">(k-1)</math> schrumpft. Dies kann vermieden werden, indem vor und nach jeder Eingabezeile einige Nullen hinzugefügt werden. Dies wird als Zero Padding (Nullauffüllung) bezeichnet. Zero Padding ermöglicht die unabhängige Steuerung der Ausgabegröße und Kernelbreite. Hier betrachten wir drei Sonderfälle der Zero Padding. Sie werden in der MATLAB-Terminologie als

* gültige Convolution (valid convolution),
* gleiche Convolution (same convolution) und
* vollständige Convolution (full convolution)

bezeichnet.

Bei einer gültigen Convolution gibt es keine Zero Padding. Es sind nur die Positionen des Kernelfensters erlaubt, an denen es vollständig im Bild enthalten ist. Somit schrumpft die Ausgabebreite bei Anwenden von jedem Convolution Layer, was die Anzahl der anwendbaren Convolution Layer begrenzt. Bei gleicher Convolution werden der Eingabe so viele Nullen hinzugefügt, womit die Ausgabe die gleiche Breite wie die Breite der Eingabe kommt. Dies bedeutet, dass zu jeder Zeile der Eingabe genau <math display="inline">(k-1)</math> Nullen hinzugefügt werden. Normalerweise werden diese Nullen vor dem linken und nach dem rechten Rand des Eingabegitters geteilt, was bedeutet, dass die Pixel am Rand des Eingabegitters Einfluss auf weniger Ausgabepixel haben als diejenigen, die sich innerhalb des Eingabegitters befinden. Die Vermeidung dieses Unterschieds motiviert die vollständige Convolution, bei der der Eingabe so viele Nullen hinzugefügt werden, dass ausreicht, um auch die Pixel am Rand des Eingabegitters <math display="inline">k</math>-mal zu besuchen. Dies wird erreicht, indem <math display="inline">(k-1)</math> Nullen sowohl vor dem linken als auch nach dem rechten Rand des Eingabegitters hinzugefügt werden. Dies führt jedoch dazu, dass die Ausgabe breiter wird, d. h. die Ausgabegröße wird um <math display="inline">(k-1)</math> größer als die Eingabegröße. Die verschiedenen Sonderfälle des Zero Padding sind in Abbildung [[#fig:CNN_9.13|40]] dargestellt.

<div id="fig:CNN_9.13" class="figure">

[[Datei:CNN_9.13.jpg|460px|thumb|center|Abbildung 40: Zero Padding für gültige (Oberes) und gleiche (Unteres) Convolution (Quelle: [Goodfellow et al.(2016)]).]] <span id="fig:CNN_9.13" label="fig:CNN_9.13"></span>


</div>


<span id="cnn-beispielarchitekturen-für-die-bildklassifizierung"></span>
=== CNN Beispielarchitekturen für die Bildklassifizierung ===

<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Eine einfache Musterarchitektur'''''</span>

Eine einfache Beispielarchitektur für die Bildklassifizierung ist in Abbildung [[#fig:CNN_9.11|41]] dargestellt.

<div id="fig:CNN_9.11" class="figure">

[[Datei:CNN_9.11.jpg|460px|thumb|center|Abbildung 41: Beispielarchitektur für die Bildklassifizierung 256 x 256 x 3 (Quelle: [Goodfellow et al.(2016)]).]] <span id="fig:CNN_9.11" label="fig:CNN_9.11"></span>


</div>


In der ersten Convolution Stage wird 16 parallele Convolution angewendet, um die Extraktion komplexerer lokaler Features und/oder das Erlernen von Invarianzen zu ermöglichen. Diese Beispielarchitektur zeigt die Positionierung der typische Layers in einer CNN-Architektur.

<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Einige bekannte CNN-Architekturen'''''</span>

Nachstehed sind einige bekannte CNN-Architekturen mit Links zu ihren Beschreibungen aufgeführt.

* [https://en.wikipedia.org/wiki/LeNet LeNet-5]
* [https://en.wikipedia.org/wiki/AlexNet AlexNet]
* [https://www.geeksforgeeks.org/vgg-16-cnn-model/ VGG-16]
* [https://en.wikipedia.org/wiki/Inceptionv3 Inception-v3]
* [https://en.wikipedia.org/wiki/Residual_neural_network ResNet-50]

<span id="subsec:RNN"></span>
== Recurrent Neural Network ==

Feedforward Neural Network werden durch gleichzeitige Eingabe (Input) gespeist. Im Gegensatz dazu sind Recurrent Neural Networks - RNN (rekurrentes neuronales Netzwerk) in der Lage, sequentielle Eingaben zu verarbeiten. Es eignet sich für Aufgaben, bei denen es um Eingaben mit sequentiellem Charakter geht, wie z.B. Text, gesprochene Sprache. Die sequentielle Natur der Eingabe spiegelt sich oft in ihrer zeitlichen Natur wider.

Ein Recurrent Neural Network ist ein neuronales Netzwerk, dessen Netzwerkarchitektur einen Zyklus aufweist, d. h. der Wert einer Unit in einer Layer des Netzwerks hängt von ihrer eigenen vorherigen Ausgabe als Eingabe ab. Diese Abhängigkeit ermöglicht, dass die Ausgabe des Recurrent Neural Network aufgrund seiner wiederkehrenden Verbindungen von Hunderten (theoretisch unendlich vielen) vorherigen Input Units abhängt. Diese langfristige Abhängigkeit von der Zeit ist das Novum des RNN, das neue Möglichkeiten für das Recurrent Neural Network eröffnet, beispielsweise wenn es zur Sprachmodellierung verwendet wird.

Der Zyklus in der Netzwerkarchitektur eines Recurrent Neural Network macht es leistungsstark, erschwert jedoch die Schlussfolgerung seiner Ausgabe aus seinen Eingaben und macht auch das Training des Netzwerks komplizierter.

<span id="einfaches-recurrent-neural-network"></span>
=== Einfaches Recurrent Neural Network ===

Wir wollen uns nur mit einer eingeschränkten Unterklasse der allgemeinen Klasse Recurrent Neural Network befassen, den sogenannten Elman Networks (Elman-Netzwerken) [Elman(1990)] oder einfachen Recurrent Neural Network. Diese dient auch als Basis für weitere Architekturen von Recurrent Neural Network, wie z.B. das LSTM (siehe Unterabschnitt [[#subsubsec:LSTM|4.4.4]]). Von nun an werden wir dieses einfache Recurrent Neural Network als Recurrent Neural Network oder RNN bezeichnen.

Wir werden den Index <math display="inline">t</math> verwenden, um die Zeit des gegebenen Vektors darzustellen, wie z.B. <math display="inline">{\bf x}_t</math> repräsentiert den Eingabevektor zum Zeitpunkt <math display="inline">t</math> oder <math display="inline">{\bf h}_t</math> repräsentiert den Ausgabevektor der einzigen Hidden Layer zum Zeitpunkt <math display="inline">t</math>. Die Architektur des RNN ist in Abbildung [[#fig:RNN_9.1|42]] dargestellt ([Elman(1990)]).

<div id="fig:RNN_9.1" class="figure">

[[Datei:RNN_9.1.jpg|460px|thumb|center|Abbildung 42: Die Architektur des einfachen Recurrent Neural Network (Quelle: [JurafskyMartin(2023)]).]] <span id="fig:RNN_9.1" label="fig:RNN_9.1"></span>


</div>


Wie in Abb. 9.1 zu sehen ist, liegt das Wesentliche des RNN in der wiederkehrenden Verknüpfung vom Ausgang der Hidden Layer mit dem Eingang der Hidden Layer, der in der gestrichelten Linie dargestellt ist. Die Ausgabe der Hidden Layer zum vorherigen Zeitpunkt realisiert einen Speicher und kann als Kontext angesehen werden, der Informationen über die Verarbeitung früherer Eingaben kodiert. Noch wichtiger ist, dass im RNN keine Längenbeschränkung für diesen Kontext auferlegt wird. Im Prinzip kann dieser Kontext Informationen bis zum Anfang der Eingabesequenz (input sequence) erfassen.

<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Vorwärtsinferenz (Forward Inference)'''''</span>

Der Ausgabewert der Hidden Layer zum Zeitpunkt <math display="inline">t-1</math> wird bei der Berechnung des Ausgabewerts der Hidden Layer zum Zeitpunkt <math display="inline">t</math> einbezieht, indem ein neuer Satz von Gewichten darauf angewendet wird, die durch die Matrix <math display="inline">{\bf U}</math> dargestellt werden. Somit kann die zeitabhängige Berechnung des RNN wie folgt angegeben werden:

<math display="block">\begin{aligned}
& {\bf h}_t = f_h({\bf U}{\bf h}_{t-1} + {\bf W}{\bf x}_{t})\\
& {\bf y}_t = {\bf F}_o({\bf V}{\bf h}_{t}). 
\end{aligned}</math>

Die Aktivierungsfunktion der Output Layer <math display="inline">{\bf F}_o({\bf z}_{t})</math> ist normalerweise eine Softmax Funktion, also eine Vektorwertige Funktion. Das Hinzufügen der Zeitabhängigkeit zur Beschreibung von RNN scheint dieses Netzwerk komplexer zu machen, aber tatsächlich kann seine Berechnung durch die Einführung des Vektors <math display="inline">{\bf h}_{t-1}</math> auf eine Berechnung eines entprechenden Feedforward Network zurückgeführt werden. Dies ist in Abbildung [[#fig:RNN_9.2|43]] dargestellt.

<div id="fig:RNN_9.2" class="figure">

[[Datei:RNN_9.2.jpg|460px|thumb|center|Abbildung 43: Die Einfaches Recurrent Neural Network, dargestellt als entsprechendes Feedforward Network (Quelle: [JurafskyMartin(2023)]).]] <span id="fig:RNN_9.2" label="fig:RNN_9.2"></span>


</div>


Der sequentielle Charakter des RNN kann durch zeitliches Ausrollen hervorgehoben werden. Dies ist in Abbildung [[#fig:RNN_9.4|44]] dargestellt.

<div id="fig:RNN_9.4" class="figure">

[[Datei:RNN_9.4.jpg|460px|thumb|center|Abbildung 44: Die Einfaches Recurrent Neural Network, dargestellt im zeitlichen Ablauf (Quelle: [JurafskyMartin(2023)]).]] <span id="fig:RNN_9.4" label="fig:RNN_9.4"></span>


</div>


<span>'''''<math display="inline">\mathrm{\ \ \ \ }</math> Training'''''</span>

RNN zu trainieren bedeutet, die Parameter der Gewichtsmatrizen <math display="inline">{\bf W}</math>, <math display="inline">{\bf U}</math> und <math display="inline">{\bf V}</math> zu lernen. Aufgrund der wiederkehrenden Struktur des Netzwerks sind vor der Gestaltung des Trainings folgende Überlegungen notwendig.

* Die Berechnung des Loss zum Zeitpunkt <math display="inline">t</math> erfordert die Ausgabe der Hidden Layer zum Zeitpunkt <math display="inline">t-1</math>.
* Die Ausgabe der Hidden Layer zum Zeitpunkt <math display="inline">t</math> beeinflusst nicht nur die Ausgabe des Netzwerks zum Zeitpunkt <math display="inline">t</math>, sondern auch die Ausgabe der Hidden Layer zum Zeitpunkt <math display="inline">t+1</math>.<br />
<math display="inline">\Leftrightarrow</math> Die Berechnung des Fehlers am Ausgang der Hidden Layer zum Zeitpunkt <math display="inline">t</math> erfordert die Kenntnis seiner Auswirkung auf <math display="inline">{\bf y}_{t}</math> und alle <math display="inline">{\bf y}_{t+i}</math> und <math display="inline">{\bf h}_{t+i}</math>, <math display="inline">i \geq 1</math>.

Daraus folgt, dass das Training von RNN das Ausrollen des Recurrent Neural Network in ein Feedforward Network erfordert und das Training dann auf diesem Feedforward Network auf übliche Weise durchgeführt werden kann, einschließlich der folgenden zwei Durchgänge:

* Vorwärtsinferenz, Berechnung von <math display="inline">{\bf h}_{t}</math> und <math display="inline">{\bf y}_{t}</math> und Speichern von <math display="inline">{\bf h}_{t}</math> für die Verwendung des nächsten Zeitschritts <math display="inline">t \geq 1</math> sowie die Akkumulation des Loss bei jedem Zeitschritt.
* Rückwärtsdurchlauf (backward pass), um den Fehler der Ausgabe der Hidden Layer für jeden rekursiven Rückschritt zu berechnen und zu speichern sowie den Gradient zu berechnen.

Dieser Ansatz zum Training von RNN wird als Backpropagation Through Time [Werbos(1974)] bezeichnet.

Bei Anwendungen mit längeren Eingabesequenzen, wie z.B. Streaming, Spracherkennung, muss das Ausrollen auf Segmente mit fester Länge beschränkt werden, da das Ausrollen der gesamten Eingabesequenz praktisch nicht möglich ist.

<span id="stacked-rnn"></span>
=== Stacked RNN ===

Stacked RNN (gestapeltes RNN) ist eine Erweiterung von RNN, bei der die gesamte Ausgabesequenz eines RNN als Eingabesequenz für ein nächstes RNN verwendet wird. Die Architektur des Stacked RNN ist in Abbildung [[#fig:RNN_9.10|45]] dargestellt.

<div id="fig:RNN_9.10" class="figure">

[[Datei:RNN_9.10.jpg|460px|thumb|center|Abbildung 45: Architektur des Stacked RNN (Quelle: [JurafskyMartin(2023)]).]] <span id="fig:RNN_9.10" label="fig:RNN_9.10"></span>


</div>


Stacked RNNs haben im Allgemeinen höhere Fähigkeiten als ein RNN. Dies liegt daran, dass allgemein davon ausgegangen wird, dass jede Layer eine andere Abstraktionsebene einführt. Allerdings steigt der Zeit- und Ressourcenbedarf des Trainings mit der Anzahl der Layer schnell an. Die optimale Anzahl der Layer hängt von den Anforderungen der Anwendung ab.

<span id="bidirektionales-rnn"></span>
=== Bidirektionales RNN ===

Die Idee des bidirektionalen RNN [SchusterPaliwal(1997)] besteht darin, nicht nur die Kontextinformationen aus dem linken Teil der Folge von Eingabevektoren (linker Kontext), sondern auch aus dem rechten Teil davon zu verwenden. In Anwendungen, in denen die Sequenz keine Zeit darstellt und die gesamte Eingabesequenz verfügbar ist, ist diese Architektur sinnvoll. Es stellt sicher, dass Kontokontextinformationen nicht nur von links, sondern auch von rechts genutzt werden, was z. B. die Leistung der Klassifizierungsaufgabe verbessert.

Im RNN repräsentiert die Ausgabe der Hidden Layer zum Zeitpunkt <math display="inline">t</math> die Kontextinformationen aus dem linken Teil der Folge von Eingabevektoren. Dies kann als Vorwärts-RNN angesehen werden, da die Hidden Layer die Informationen über die Eingabevektoren von links nach rechts weitergibt. Ein ähnlicher Rückwärts-RNN kann eingerichtet werden, dessen Hidden Layer die Informationen über die Eingabevektoren von rechts nach links weitergibt. Somit können die Ausgabevektoren der Vorwärts- und Rückwärts-RNNs, als Hidden Layers, zum Zeitpunkt <math display="inline">t</math>, <math display="inline">{\bf h}_{t}^f</math> und <math display="inline">{\bf h}_{t}^b</math> als

<math display="block">\begin{aligned}
& {\bf h}_{t}^f = RNN_{forward}({\bf x}_{1}, \ldots, {\bf x}_{t})\\
& {\bf h}_{t}^b = RNN_{backward}({\bf x}_{t}, \ldots, {\bf x}_{n}) 
\end{aligned}</math> beschrieben werden, wobei <math display="inline">n</math> ist die Anzahl der Eingabevektoren in der Eingabesequenz. Die Parametergewichte des Rückwärts-RNN können durch das Training eines RNN auf einer umgekehrten Eingabesequenz erlernt werden.

Dann werden die gesamten Zustands- oder Kontextinformationen zum Zeitpunkt <math display="inline">t</math> zusammengestellt, indem sowohl die linken als auch die rechten Kontextinformationen kombiniert werden. Dies geschieht durch die Kombination der Vektoren <math display="inline">{\bf h}_{t}^f</math> und <math display="inline">{\bf h}_{t}^b</math>, die die linken und die rechten Kontextinformationen darstellen. Mögliche Kombinationsvarianten sind Verkettung (concatenation), Multiplikation oder elementweise Addition. Beispielsweise kann durch Anwenden der Verkettung der Vektor <math display="inline">{\bf h}_{t}</math>, der die gesamten Kontextinformationen darstellt, als

<math display="block">{\bf h}_{t} = [{\bf h}_{t}^f {\bf h}_{t}^b],</math> angegeben werden, wobei <math display="inline">[{\bf a} {\bf b}]</math> für die Verkettung der Vektoren <math display="inline">{\bf a}</math> und <math display="inline">{\bf b}</math> steht. Ein solches bidirektionales RNN mit Verkettung ist in Abbildung [[#fig:RNN_9.11|46]] dargestellt.

<div id="fig:RNN_9.11" class="figure">

[[Datei:RNN_9.11.jpg|460px|thumb|center|Abbildung 46: Bidirektionales RNN mit separat trainierten Modellen in Vorwärts- und Rückwärtsrichtung (Quelle: [JurafskyMartin(2023)]).]] <span id="fig:RNN_9.11" label="fig:RNN_9.11"></span>


</div>


<span id="subsubsec:LSTM"></span>
=== Das LSTM ===

Eine Einschränkung von RNN besteht darin, dass es für Aufgaben, bei denen Informationen berücksichtigt werden müssen, die weit vom aktuellen Index <math display="inline">t</math> entfernt sind, nicht effektiv ist. Der Grund dafür ist, dass die in <math display="inline">{\bf h}_{t}</math> kodierten Informationen eher lokal sind und somit den Einfluss näherer Teile der Eingabesequenz widerspiegeln.

Um dieses Problem zu lösen, wurden kompliziertere RNN-Architekturen entworfen, die explizit diejenige Informationsteile steuern, die vergessen beziehungsweise für die zukünftige Verwendung gespeichert werden sollen, und diese Steuerung dynamisch über die Zeit durchführen. Eine solche RNN-Architektur ist das neuronale Netzwerk Long Short-Term Memory (LSTM)<br />
Das LSTM wird als Hidden Unit realisiert. Es führt zu jedem Zeitpunkt <math display="inline">t</math>, einen Kontextvektor, <math display="inline">{\bf c}_{t}</math>, ein. Der Kontextvektor wird zur Maskierung bei der Berechnung der tatsächlichen Ausgabe der Hidden Unit zum Zeitpunkt <math display="inline">t</math>, <math display="inline">{\bf h}_{t}</math> verwendet. Andererseits wird der Kontextvektor bei jedem Zeitschritt aktualisiert, d. h. <math display="inline">{\bf c}_{t}</math> wird aus <math display="inline">{\bf c}_{t-1}</math> berechnet. Während dieses Updates wird

* ein Teil des Kontextvektors <math display="inline">{\bf c}_{t-1}</math> durch Maskierung mit dem Forget Gate <math display="inline">{\bf f}_{t}</math> gelöscht (welches <math display="inline">{\bf k}_{ t}</math> resultiert) und
* ein Teil der eigentlichen Information <math display="inline">{\bf g}_{t}</math>, die aus <math display="inline">{\bf h}_{t-1}</math> und <math display="inline">{\bf x}_{t}</math> wie üblich extrahiert, wird durch Maskierung mit dem Add Gate <math display="inline">{\bf i}_{t}</math> bewahrt (welches <math display="inline">{\bf j}_{t}</math> resultiert) und
* die Summe von <math display="inline">{\bf k}_{t}</math> und <math display="inline">{\bf j}_{t}</math> gebildet um den aktualisierten Kontextvektor <math display="inline">{\bf c}_{t}</math> anzugeben.

Die elementweise Multiplikation (auch als Hadamard-Produkt von Vektoren bezeichnet) wird mit <math display="inline">\odot</math> bezeichnet, und die Sigmoid Aktivierungsfunktionen werden zur Realisierung der Funktionalität der Maskierung verwendet. Das Sigmoid wird aufgrund seiner Eigenschaft ausgewählt, indem seine Eingabe entweder in Richtung <math display="inline">0</math> oder <math display="inline">1</math> zu werfen. Genauer gesagt werden die oben genannten Vektoren, wie folgt, berechnet.

# Löschen eines Teils von <math display="inline">{\bf c}_{t-1}</math> durch Maskieren mit dem Forget Gate <math display="inline">{\bf f}_{t}</math> <math display="inline">\Rightarrow</math> <math display="inline">{\bf k}_{t}</math> <math display="block">\begin{aligned}
    & {\bf f}_{t} = \sigma({\bf U}_{f}{\bf h}_{t-1} + {\bf W}_{f}{\bf x}_{t}) \\
    & {\bf k}_{t} = {\bf c}_{t-1} \odot {\bf f}_{t}. 
    
\end{aligned}</math>
# Extrahieren der tatsächlichen Informationen <math display="inline">{\bf g}_{t}</math> aus <math display="inline">{\bf h}_{t-1}</math> und <math display="inline">{\bf x}_{t}</math> sowie Bewahren eines Teils davon durch Maskieren mit das Add Gate <math display="inline">{\bf i}_{t}</math> <math display="inline">\Rightarrow</math> <math display="inline">{\bf j}_{t}</math> <math display="block">\begin{aligned}
    & {\bf g}_{t} = tanh(({\bf U}_{g}{\bf h}_{t-1} + {\bf W}_{g}{\bf x}_{t})
    & {\bf i}_{t} = \sigma({\bf U}_{i}{\bf h}_{t-1} + {\bf W}_{i}{\bf x}_{t}) \\
    & {\bf j}_{t} = {\bf g}_{t} \odot {\bf i}_{t}. 
    
\end{aligned}</math>
# Zusammenstellen des aktualisierten Kontextvektors durch Summieren von <math display="inline">{\bf k}_{t}</math> und <math display="inline">{\bf j}_{t}</math> <math display="inline">\Rightarrow</math> <math display="inline">{\bf c}_{t}</math> <math display="block">\begin{aligned}
    & {\bf c}_{t} = {\bf k}_{t} + {\bf j}_{t}. 
    
\end{aligned}</math>
# Berechnen von <math display="inline">{\bf o}_{t}</math> auf übliche Weise aus <math display="inline">{\bf h}_{t-1}</math> und <math display="inline">{\bf x}_{t}</math> sowie erstellen den Ausgabevektor der Hidden Unit durch Maskieren von <math display="inline">{\bf o}_{t}</math> mit dem tatsächlichen Kontextvektor <math display="inline">{\bf c}_{t}</math> <math display="inline">\Rightarrow</math> <math display="inline">{\bf h}_{t}</math> <math display="block">\begin{aligned}
    & {\bf o}_{t} = \sigma({\bf U}_{o}{\bf h}_{t-1} + {\bf W}_{o}{\bf x}_{t}) \\
    & {\bf h}_{t} = {\bf o}_{t} \odot tanh({\bf c}_{t}).
    
\end{aligned}</math>

Die gesamte Berechnung der neuronalen LSTM-Einheit ist in Abbildung [[#fig:RNN_9.13|47]] dargestellt.

<div id="fig:RNN_9.13" class="figure">

[[Datei:RNN_9.13.jpg|460px|thumb|center|Abbildung 47: Die Berechnungsarchitektur einer neuronalen LSTM-Einheit (Quelle: [JurafskyMartin(2023)]).]] <span id="fig:RNN_9.13" label="fig:RNN_9.13"></span>


</div>


Der Vergleich der Eingabe- und Ausgabeschnittstellen der neuronalen Einheiten FNN, RNN und LSTM ist in Abbildung [[#fig:RNN_9.14|48]] zu sehen.

<div id="fig:RNN_9.14" class="figure">

[[Datei:RNN_9.14.jpg|460px|thumb|center|Abbildung 48: Neuronale Einheiten von (a) FNN, (b) RNN und (c) LSTM (Quelle: [JurafskyMartin(2023)]).]] <span id="fig:RNN_9.14" label="fig:RNN_9.14"></span>


</div>