Kurs:Maschinelles Lernen/Klassifikation mittels Gradientenabstieg

Vorherige Seite: K2 - Feature Engineering
Nächste Seite: K3 - Klassifikation mittels Support Vector Machines

Formulierung des Problems und passender Hypothesen

Als Eingabedaten liegen wieder Punkte ${\vec {x}}$ aus dem $X=\mathbb {R} ^{d}$ vor. Für eine binäre Klassifikation, die hier betrachtet werden soll, sind die möglichen Ausgabewerte aus dem Raum $Y=\{0,1\}$. Das bedeutet, es müssen Hypothesen gesucht werden, die Abbildungen der Form

$h:\mathbb {R} ^{d}\to \{0,1\}$

sind.

Im Kapitel über Vektoren war zu erkennen, dass der Raum $R^{d}$ durch eine Hyperebene, welche durch

${\vec {n}}\cdot {\vec {x}}-c=0$

beschrieben wird, in zwei Bereiche geteilt wird. Daher läge es nahe eine Hypothese der Art

$h_{\vec {w}}({\vec {x}})=\Theta ({\vec {w}}\cdot {\vec {x}}+w_{0})$

zu formulieren, wobei

$\Theta (x)={\begin{cases}1&\quad x\geq 0\\0&\quad x<0\end{cases}}$

die Theta-Funktion ist. Diese Form einer Hypothese ist allerdings für ein Gradientenabstiegsverfahren ungeeignet, da die Theta-Funktion an der Stelle $x=0$ nicht differenzierbar ist.

Statt der Theta-Funktion wird daher die Sigmoidfunktion (auch als logistische Funktion bezeichnet)

$\mathrm {sig} :\mathbb {R} \to (0,1),\,\,x\mapsto \mathrm {sig} (x)={\frac {1}{1+\mathrm {e} ^{-x}}}$

betrachtet werden. Sie verfügt über die Grenzwerte

$\lim \limits _{x\to -\infty }\mathrm {sig} (x)=0\quad \quad \lim \limits _{x\to +\infty }\mathrm {sig} (x)=1$

und ist mit der Ableitung

$\mathrm {sig} '\!(x)=\mathrm {sig} (x)(1-\mathrm {sig} (x))$

in jedem Punkt differenzierbar. Damit kann dann zur Optimierung die Hypothese

$h_{\vec {w}}({\vec {x}})=\mathrm {sig} ({\vec {w}}\cdot {\vec {x}}+w_{0})={\frac {1}{1+\mathrm {e} ^{-({\vec {w}}\cdot {\vec {x}}+w_{0})}}}$

verwendet werden, womit die Idealen Gewichte ${\hat {\vec {w}}}$ bestimmt werden. Zur schlussendlichen Klassifikation muss aber die Theta-Funktion

${\hat {h}}_{\hat {\vec {w}}}({\vec {x}})=\Theta ({\hat {\vec {w}}}\cdot {\vec {x}}+{\hat {w}}_{0})$

verwendet werden.

Verlustfunktion und empirisches Risiko

Für Klassifikationsverfahren wird mit der Vereinbarung $0\cdot \ln {(0)}=0$ die Kreuzentropie

$l(h(x),y)=-[y\ln {(h(x))}+(1-y)\ln {(1-h(x))}]$

als Verlustfunktion verwendet. Durch Einsetzen der Hypothese mit der Sigmoid-Funktion kann diese zu

$l(h_{\vec {w}}({\vec {x}}),y)=\ln {\left(1+\mathrm {exp} \left((-1)^{y}({\vec {w}}\cdot {\vec {x}}+w_{0})\right)\right)}$

bestimmt werden.

Für das empirische Risiko

${\hat {R}}={\frac {1}{N}}\sum _{i=1}^{N}l(h_{\vec {w}}({\vec {x}}_{i}),y_{i})$

für einen vorliegenden Datensatz mit $N$ Datenpunkten kann so der Ausdruck

${\hat {R}}={\frac {1}{N}}\sum _{i=1}^{N}\ln {\left(1+\mathrm {exp} \left((-1)^{y_{i}}({\underline {X}}'{\vec {w}})_{i}\right)\right)}$

gefunden werden. Darin taucht die erweiterte Datenmatrix ${\underline {X}}'$ in einem Matrixvektorprodukt mit ${\vec {w}}$ auf. (Dies lässt sich in bspw. in Python mit numpy besonders effizient durchführen. Die Summe über $i$ trifft hingegen nicht mit den indizierten Größen auf, so dass diese explizit bestimmt werden muss.)

Wird der Gradient des empirischen Risikos bestimmt, so kann der Ausdruck

${\frac {\partial {\hat {R}}}{\partial w_{l}}}={\frac {1}{N}}\sum _{i=1}^{N}{\frac {(-1)^{y_{i}}{\underline {X}}'_{il}}{1+\mathrm {exp} (-(-1)^{y_{i}}({\underline {X}}'{\vec {w}})_{i})}}$

gefunden werden.

In der Praxis wird hierbei der Faktor ${\frac {1}{N}}$ oft ignoriert. Durch die Einführung eines Hyperparametrs $a>0$ kann die Entscheidung an der Sigmoidfunktion mit $\mathrm {sig} (ax)$ noch härter gemacht werden. In diesem Fall nehmen das empirische Risiko und sein Gradient die Formen

${\hat {R}}={\frac {1}{N}}\sum _{i=1}^{N}\ln {\left(1+\mathrm {exp} \left(a(-1)^{y_{i}}({\underline {X}}'{\vec {w}})_{i}\right)\right)}$

und

${\frac {\partial {\hat {R}}}{\partial w_{l}}}={\frac {1}{N}}\sum _{i=1}^{N}{\frac {a(-1)^{y_{i}}{\underline {X}}'_{il}}{1+\mathrm {exp} (-a(-1)^{y_{i}}({\underline {X}}'{\vec {w}})_{i})}}$

an.

Feature Engineering

Wie auch bei linearen Regressionen lassen sich Klassifikationsprobleme weiterhin durch lineare Zusammenhänge lösen, wenn ein Feature Engineering durchgeführt wird. Dazu kann folgendes Beispiel betrachtet werden. Im zweidimensionalen Raum $X=\mathbb {R} ^{2}$ sollen Punkte in zwei Kategorien $Y=\{0,1\}$ klassifiziert werden. Durch Augenmaß ist bereits zu erkennen, dass die Separation durch einen Kreis mit Radius $1$ erfolgen könnte. Ein solcher wird durch

$x_{1}^{2}+x_{2}^{2}=1\quad \Leftrightarrow \quad 1\cdot x_{1}^{2}+1\cdot x_{2}^{2}-1=0$

beschrieben. Dies stellt aber einen linearen Zusammenhang in $x_{1}^{2}$ und $x_{2}^{2}$ dar. Wird insgesamt der Grad $g$ betrachtet, müssen wesentlich mehr Terme berücksichtigt werden. So würde sich für eine Feature Map mit dem Grad $g=2$ die Form

$\phi :\mathbb {R} ^{2}\to \mathbb {R} ^{5},\,\,{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}\mapsto {\begin{pmatrix}x_{1}\\x_{2}\\x_{1}^{2}\\x_{1}x_{2}\\x_{2}^{2}\end{pmatrix}}$

ergeben. Typischerweise wird eine Feature Map die Form

$\phi :\mathbb {R} ^{d}\to \mathbb {R} ^{m}$

mit $m\gg d$ haben. Aus $\phi ({\vec {x}})$ wird dann die erweiterten Datenmatrix ${\underline {X}}'$ für das oben beschriebene Gradientenabstiegsverfahren erstellt.