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 $\overrightarrow{x}$ aus dem $X={ℝ}^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:{ℝ}^d\to \{0,1\}$

sind.

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

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

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

$h_{\overrightarrow{w}}(\overrightarrow{x})=\mathrm{\Theta }(\overrightarrow{w}\cdot \overrightarrow{x}+w_0)$

zu formulieren, wobei

$\mathrm{\Theta }(x)=\{\begin{array}{cc}1& x\ge 0\\ 0& x<0\end{array}$

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{s}\mathrm{i}\mathrm{g}:ℝ\to (0,1),x\mapsto \mathrm{s}\mathrm{i}\mathrm{g}(x)=\frac{1}{1+{\mathrm{e}}^{-x}}$

betrachtet werden. Sie verfügt über die Grenzwerte

$\lim {\mathrm{\backslash limits}}_{x\to -\mathrm{\infty }}\mathrm{s}\mathrm{i}\mathrm{g}(x)=0\lim {\mathrm{\backslash limits}}_{x\to +\mathrm{\infty }}\mathrm{s}\mathrm{i}\mathrm{g}(x)=1$

und ist mit der Ableitung

${\mathrm{s}\mathrm{i}\mathrm{g}}^{\prime }(x)=\mathrm{s}\mathrm{i}\mathrm{g}(x)(1-\mathrm{s}\mathrm{i}\mathrm{g}(x))$

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

$h_{\overrightarrow{w}}(\overrightarrow{x})=\mathrm{s}\mathrm{i}\mathrm{g}(\overrightarrow{w}\cdot \overrightarrow{x}+w_0)=\frac{1}{1+{\mathrm{e}}^{-(\overrightarrow{w}\cdot \overrightarrow{x}+w_0)}}$

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

${\hat{h}}_{\hat{\overrightarrow{w}}}(\overrightarrow{x})=\mathrm{\Theta }(\hat{\overrightarrow{w}}\cdot \overrightarrow{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_{\overrightarrow{w}}(\overrightarrow{x}),y)=\ln (1+\mathrm{e}\mathrm{x}\mathrm{p}((-1{)}^y(\overrightarrow{w}\cdot \overrightarrow{x}+w_0)))$

bestimmt werden.

Für das empirische Risiko

$\hat{R}=\frac{1}{N}\sum _{i=1}^{N}l(h_{\overrightarrow{w}}({\overrightarrow{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 (1+\mathrm{e}\mathrm{x}\mathrm{p}((-1{)}^{y_i}({\underset{\_}{X}}^{\prime }\overrightarrow{w}{)}_i))$

gefunden werden. Darin taucht die erweiterte Datenmatrix ${\underset{\_}{X}}^{\prime }$ in einem Matrixvektorprodukt mit $\overrightarrow{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}\underset{\_}{X}{\text{'}}_{il}}{1+\mathrm{e}\mathrm{x}\mathrm{p}(-(-1{)}^{y_i}({\underset{\_}{X}}^{\prime }\overrightarrow{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{s}\mathrm{i}\mathrm{g}(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 (1+\mathrm{e}\mathrm{x}\mathrm{p}(a(-1{)}^{y_i}({\underset{\_}{X}}^{\prime }\overrightarrow{w}{)}_i))$

und

$\frac{\partial \hat{R}}{\partial w_l}=\frac{1}{N}\sum _{i=1}^N\frac{a(-1{)}^{y_i}\underset{\_}{X}{\text{'}}_{il}}{1+\mathrm{e}\mathrm{x}\mathrm{p}(-a(-1{)}^{y_i}({\underset{\_}{X}}^{\prime }\overrightarrow{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={ℝ}^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\iff 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

$\varphi :{ℝ}^2\to {ℝ}^5,\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)\mapsto \left(\begin{array}{c}{x}_1\\ x_2\\ x_1^2\\ x_1{x}_2\\ x_2^2\end{array}\right)$

ergeben. Typischerweise wird eine Feature Map die Form

$\varphi :{ℝ}^d\to {ℝ}^m$

mit $m\gg d$ haben. Aus $\varphi (\overrightarrow{x})$ wird dann die erweiterten Datenmatrix ${\underset{\_}{X}}^{\prime }$ für das oben beschriebene Gradientenabstiegsverfahren erstellt.