Machine-Learning-Grundlagen – Normen

Einführung

Lineare Algebra gehört zu den grundlegenden mathematischen Werkzeugen in der Data Science. Ein Verständnis dieser Konzepte vertieft dein Verständnis vieler Algorithmen. Sie ist eine hervorragende Basis für deinen Data-Science-/Machine-Learning-Weg.

Das Ziel dieses Tutorials ist, Mathematik für Data Science mit Python/Numpy praktisch zu erarbeiten. Gerade bei theoretischen Themen wie linearer Algebra sind praxisnahe Tutorials hilfreich, denn Code zu schreiben und zu lesen ist ein guter Weg, mathematische Konzepte wirklich zu begreifen. Und vor allem: Es macht Spaß!

Es gibt keine besonderen Voraussetzungen. Falls dir Matrizen oder das Skalarprodukt nichts sagen, eignen sich die ersten Beiträge (1 bis 4) aus meiner Serie zum Deep-Learning-Buch von Ian Goodfellow als Einstieg.

In diesem Tutorial nehmen wir uns ein zentrales Konzept für Machine Learning und Deep Learning vor: die Norm. Normen werden häufig eingesetzt, etwa um die Güte eines Modells zu bewerten. Am Ende dieses Tutorials hast du hoffentlich ein besseres Bauchgefühl für dieses Konzept und dafür, warum es im Machine Learning so wertvoll ist. Außerdem schauen wir uns an, wie die Ableitung der Norm zum Trainieren eines Machine-Learning-Algorithmus genutzt wird.

Grundlegendes Setup

Als Erstes richten wir die Bibliotheken ein, die wir verwenden:

import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns

Und fügen ein paar LaTeX-Kürzel hinzu: bs für fette Symbole und norm für das Normsymbol:

$$
\\newcommand\\bs[1]{\\boldsymbol{#1}}
\\newcommand\\norm[1]{\\left\\lVert#1\\right\\rVert}
$$

$$ \\newcommand\\bs[1]{\\boldsymbol{#1}} \\newcommand\\norm[1]{\\left\\lVert#1\\right\\rVert} $$

Zum Schluss konfigurieren wir noch das Aussehen der Grafiken, die wir erstellen:

# Plot parameters
sns.set()
%pylab inline
pylab.rcParams['figure.figsize'] = (4, 4)
plt.rcParams['xtick.major.size'] = 0
plt.rcParams['ytick.major.size'] = 0

Populating the interactive namespace from numpy and matplotlib

Ein praktisches Beispiel

Starten wir mit einem einfachen Beispiel. Stell dir vor, du hast einen Datensatz mit Songs und verschiedenen Merkmalen. Du möchtest nun ein Modell bauen, das die Dauer eines Songs anhand anderer Features wie Genre, Instrumentierung usw. vorhersagt. Du hast ein Modell trainiert und willst nun prüfen, wie gut es die Dauer eines neuen Songs prognostiziert. Dazu nimmst du neue Daten und sagst mit deinem Modell die Songdauern voraus. Da du für diese Beobachtungen die echte Dauer kennst, kannst du für jede Beobachtung echte und vorhergesagte Dauer vergleichen. Für 7 Beobachtungen ergeben sich in Sekunden folgende Werte:

errorModel1 = [22, -4, 2, 7, 6, -3, 12]

Diese Differenzen kannst du als Fehler des Modells verstehen. Ein perfektes Modell hätte nur 0en, ein sehr schlechtes Modell hätte große positive oder negative Werte.

Nehmen wir an, du probierst ein weiteres Modell aus und erhältst die folgenden Differenzen zwischen vorhergesagter und tatsächlicher Dauer:

errorModel2 = [14, 9, -13, 19, 8, -21, 4]

Wie findest du nun das beste Modell? Eine naheliegende Methode ist, die Summe der absoluten Fehler zu bilden. Die Beträge verwenden wir, weil ein negativer Fehler (tatsächliche Dauer kleiner als vorhergesagte) genauso ein Fehler ist. Je kleiner der Gesamtfehler eines Modells ist, desto besser:

totalErrorModel1 = np.sum(np.abs(errorModel1))
totalErrorModel1

56

totalErrorModel2 = np.sum(np.abs(errorModel2))
totalErrorModel2

88

Offenbar ist Modell 1 deutlich besser als Modell 2.

Glückwunsch! Du hast gerade die Norm des Fehlervektors für jedes Modell berechnet!

Intuition

Du kannst dir die Norm als die Länge eines Vektors vorstellen. Zur Veranschaulichung greifen wir unser Beispiel wieder auf. Die Fehlervektoren sind mehrdimensional: Pro Beobachtung gibt es eine Dimension. Im letzten Beispiel führten 7 Beobachtungen zu 7 Dimensionen. Sieben Dimensionen zu zeichnen ist schwierig, daher vereinfachen wir auf 2 Beobachtungen:

errorModel1 = [22, -4]
errorModel2 = [14, 9]

Jetzt können wir diese Vektoren darstellen, indem wir das erste Element als x- und das zweite als y-Koordinate interpretieren. Wir schreiben zunächst eine Funktion, mit der sich Vektoren leicht plotten lassen.

Vektoren mit Python und Matplotlib plotten

Wir möchten eine Funktion, die uns beim Plotten der Vektoren hilft. So wollen wir sie verwenden: Wir übergeben eine Liste von Arrays mit den Vektorkoordinaten und erhalten einen Plot dieser Vektoren. Zusätzlich können wir ein Farben-Array angeben, um die Vektoren im Plot zu unterscheiden. Kurz gesagt, wir möchten die Funktion so aufrufen:

plotVectors([vector1, vector2], ['red', 'blue'])

Schreiben wir die Funktion:

def plotVectors(vecs, cols, alpha=1):
    \"\"\"
    Plot set of vectors.

    Parameters
    ----------
    vecs : array-like
        Coordinates of the vectors to plot. Each vector is in an array. For
        instance: [[1, 3], [2, 2]] can be used to plot 2 vectors.
    cols : array-like
        Colors of the vectors. For instance: ['red', 'blue'] will display the
        first vector in red and the second in blue.
    alpha : float
        Opacity of vectors

    Returns:

    fig : instance of matplotlib.figure.Figure
        The figure of the vectors
    \"\"\"
    plt.axvline(x=0, color='#A9A9A9', zorder=0)
    plt.axhline(y=0, color='#A9A9A9', zorder=0)

    for i in range(len(vecs)):
        if (isinstance(alpha, list)):
            alpha_i = alpha[i]
        else:
            alpha_i = alpha
        if (len(vecs[i])==2):
            x = np.concatenate([[0,0],vecs[i]])
        elif (len(vecs[i])==4):
            x = vecs[i]
        plt.quiver([x[0]],
                   [x[1]],
                   [x[2]],
                   [x[3]],
                   angles='xy', scale_units='xy', scale=1, color=cols[i],
                  alpha=alpha_i)

Die Funktion nimmt ein Array zu plottender Vektoren (vecs) und ihre Farben (cols) entgegen. Sind im Vektor nur 2 Dimensionen angegeben, startet er bei (0, 0). Intern iterieren wir über die Vektoren und verwenden plt.quiver() für den Plot.

Nutzen wir die neue Funktion, um die Fehler der Modelle 1 und 2 zu plotten:

plotVectors([errorModel1, errorModel2], [sns.color_palette()[0], sns.color_palette()[1]])

plt.xlim(-1, 25)
plt.ylim(-5, 10)
plt.show()

Hinweis: Wir haben plt.show() nicht in die Funktion aufgenommen, um wie hier zusätzliche Plot-Parameter (z. B. Achsengrenzen) setzen zu können.

Hinweis 2: Die Farben stammen direkt aus seaborn via sns.color_palette().

Wir haben also je einen Fehlervektor pro Modell. Das bessere Modell ist das mit dem kürzeren Vektor. Eine Möglichkeit, die Länge zu berechnen, ist der Satz des Pythagoras: $\\sqrt{x^2+y^2}$. Wir berechnen die Längen beider Vektoren:

# Länge des Vektors errorModel1
np.sqrt(errorModel1[0]**2+errorModel1[1]**2)

22.360679774997898

# Länge des Vektors errorModel2
np.sqrt(errorModel2[0]**2+errorModel2[1]**2)

16.643316977093239

Glückwunsch! Du hast damit eine andere Norm der Fehlervektoren berechnet. Die Länge des Fehlervektors des ersten Modells beträgt $22{,}36$, die des zweiten rund $16{,}64$. In diesem Fall ist also das zweite Modell besser – beachte aber, dass wir hier nur die ersten zwei Werte genutzt haben.

Wir haben zuerst die Summe der Fehler berechnet, können aber auch mit dem Satz des Pythagoras die Norm eines Vektors bestimmen. Das sind zwei verschiedene Normen – es gibt also mehrere Wege, Normen zu berechnen.

Normfunktionen: Definitionen

Die Norm eines Vektors ist eine Funktion, die einen Vektor auf einen positiven Wert abbildet. Es gibt verschiedene Funktionen dafür – ein paar Beispiele sehen wir gleich. Diese Funktionen dürfen sich Norm nennen, wenn sie die folgenden Eigenschaften erfüllen:

• Normen sind nichtnegativ. Denkst du an Normen als Länge, ist klar, warum sie nicht negativ sein können.

• Normen sind genau dann $0$, wenn der Vektor der Nullvektor ist.

• Normen erfüllen die Dreiecksungleichung. Siehe unten.

• $\\norm{k\\cdot \\bs{u}}=\\norm{k}\\cdot\\norm{\\bs{u}}$. Dabei ist $k$ ein Skalar und $\\bs{u}$ ein Vektor. Die Norm eines mit einem Skalar multiplizierten Vektors ist gleich dem Betrag dieses Skalars mal der Norm des Vektors.

Üblicherweise schreibt man sie mit zwei senkrechten Strichen: $\\norm{\\bs{x}}$

Die Dreiecksungleichung

Eine Bedingung für eine Norm ist die Dreiecksungleichung. Sie besagt: Die Norm der Summe von Vektoren ist höchstens so groß wie die Summe ihrer Normen:

Beispiel 1.

Zur Veranschaulichung nehmen wir zwei Vektoren mit je zwei Elementen (praktisch als x- und y-Koordinaten darstellbar). Unsere Vektoren sind:

u = np.array([1, 6])
u

array([1, 6])

und

v = np.array([4, 2])
v

array([4, 2])

Wir vergleichen:

und:

Wir betrachten später verschiedene Normtypen, verwenden hier aber die klassische euklidische Norm ($L^2$). Die $L^2$-Norm lässt sich mit np.linalg.norm() berechnen (siehe Dokumentation).

Wir sehen später im Detail, was $L^1$- und $L^2$-Norm sind.

np.linalg.norm(u+v)

9.4339811320566032

und

np.linalg.norm(u)+np.linalg.norm(v)

10.554898485297798

Die Dreiecksungleichung ist also erfüllt, denn:

Grafische Erklärung

Die grafische Darstellung macht den Satz besonders eingängig. Wir plotten die Vektoren $\\bs{u}$, $\\bs{v}$ und $\\bs{u}+\\bs{v}$ mit unserer Funktion plotVectors und fügen Labels hinzu:

u = np.array([0,0,1,6])
v = np.array([0,0,4,2])
w = u+v

u_bis = [u[2], u[3], v[2], v[3]]

plotVectors([u, u_bis, w],
            [sns.color_palette()[0],
            sns.color_palette()[1],
            sns.color_palette()[2]])

plt.xlim(-2, 6)
plt.ylim(-2, 9)

plt.text(-1, 3.5, r'$||\\vec{u}||$', color=sns.color_palette()[0], size=20)
plt.text(2.5, 7.5, r'$||\\vec{v}||$', color=sns.color_palette()[1], size=20)
plt.text(2, 2, r'$||\\vec{u}+\\vec{v}||$', color=sns.color_palette()[2], size=20)

plt.show()
plt.close()

Die Länge von $\\bs{u}$ plus die Länge von $\\bs{v}$ ist größer als die Länge von $\\bs{u}+\\bs{v}$. Geometrisch bedeutet das schlicht: Der kürzeste Weg zwischen zwei Punkten ist die Gerade!

p‑Normen: Allgemeine Regeln

Wir haben die Bedingungen gesehen, die eine Funktion zur Norm machen. Es gibt also mehrere Funktionen, die als Normen dienen können. Die Vor- und Nachteile schauen wir uns später an. Als $p$‑Normen bezeichnen wir die folgende Funktionsfamilie, die von $p$ abhängt:

Gehen wir die Gleichung Schritt für Schritt durch. Es gibt eine Summe über die Elemente, wir iterieren also über die $i$ Elemente:

1. $\\vert\\bs{x}_i\\vert$ Den Betrag des $i$‑ten Elements bilden
2. $\\vert\\bs{x}_i\\vert^p$ Auf die Potenz $p$ heben
3. $\\sum_i\\vert\\bs{x}_i\\vert^p$ Alle potenzierten Beträge aufsummieren
4. $(\\sum_i\\vert\\bs{x}_i\\vert^p)^{1/p}$ Davon die $\\frac{1}{p}$‑te Potenz nehmen

Mit Beispielen wird das sofort klarer – und diese $p$‑Normen sind weit verbreitet.

Die $L^0$‑Norm

Für $p=0$ wird die Formel zu:

Was bedeutet das? Der Betrag hoch $0$ ergibt für jedes von $0$ verschiedene Element eine $1$ und für $0$ eine $0$.

Diese \"Norm\" entspricht also der Anzahl der von Null verschiedenen Elemente im Vektor. Streng genommen ist es keine Norm, denn multiplizierst du den Vektor mit $\\alpha$, bleibt diese Zahl gleich (Verstoß gegen Regel 4 oben).

Die $L^1$‑Norm

Für $p=1$ ergibt sich schlicht die Summe der Beträge. Genau das haben wir eingangs intuitiv verwendet:

Die $L^2$‑Norm (Euklidische Norm)

Die euklidische Norm ist die $p$‑Norm mit $p=2$. Sie ist – zusammen mit der quadrierten $L^2$‑Norm (siehe unten) – vermutlich die meistgenutzte Norm.

Den Betrag brauchen wir hier nicht mehr, da quadriert wird. Genau das haben wir oben mit dem Satz des Pythagoras getan.

Ein weiteres Beispiel:

Beispiel 2.

Grafisch entspricht die euklidische Norm der Länge des Vektors vom Ursprung zu dem durch die Koordinaten bestimmten Punkt (Satz des Pythagoras). Wir betrachten 2 Dimensionen: Der Vektor $\\bs{u}$ hat zwei Werte für x‑ und y‑Koordinate. Zeichnest du den Punkt und vom Ursprung dorthin einen Vektor, ist die $L^2$‑Norm die Länge dieses Vektors.

Zum Beispiel:

Berechnen wir die Norm per Formel:

Die $L^2$‑Norm ist also $5$.

Zur Erinnerung: Die $L^2$‑Norm kannst du auch mit linalg.norm() aus Numpy berechnen:

np.linalg.norm([3, 4])

5.0

Hier die grafische Darstellung des Vektors:

u = np.array([3, 4])

plt.ylim(-1, 5)
plt.xlim(-1, 5)
plotVectors([u], [sns.color_palette()[0]])

Der Vektor verläuft vom Ursprung (0, 0) nach (3, 4), seine Länge beträgt 5.

Das gilt analog in höheren Dimensionen.

Die quadrierte euklidische Norm (quadrierte $L^2$‑Norm)

Die quadrierte $L^2$‑Norm ist praktisch, weil die Wurzel entfällt und schlicht die Summe der quadrierten Werte bleibt.

In Machine Learning ist sie weit verbreitet, unter anderem weil sie sich als Vektoroperation $\\bs{x}^\\text{T}\\bs{x}$ berechnen lässt. Durch Optimierungen kann das performanter sein. Siehe hier und hier für Details.

Beispiel 3.

Wir sehen jetzt, wie sich die quadrierte euklidische Norm vektorisiert berechnen lässt. Beginnen wir mit einem Vektor $\\bs{x}$:

Wie gewohnt prüfen wir den Ablauf mit Code. Zuerst erstellen wir den Numpy‑Vektor $\\bs{x}$:

x = np.array([[2], [5], [3], [3]])
x

array([[2],
       [5],
       [3],
       [3]])

Nun transponieren wir den Vektor. Dadurch wird aus dem Spalten‑ ein Zeilenvektor:

Die Transposition erhalten wir mit der Methode T von Numpy‑Objekten:

x.T

array([[2, 5, 3, 3]])

Das Skalarprodukt von $\\bs{x}$ und $\\bs{x}^\\text{T}$ (siehe hier zur Auffrischung) entspricht der Summe der Element‑Quadrate:

Genau das ist die Definition der quadrierten euklidischen Norm!

Prüfen wir das mit Numpy. Denk daran (und probier es aus): Die Reihenfolge beim Skalarprodukt spielt eine Rolle:

euclideanNorm = x.T.dot(x)
euclideanNorm

array([[47]])

Das sollte unsere quadrierte euklidische Norm sein! Berechnen wir zur Kontrolle die $L^2$‑Norm und quadrieren sie:

np.linalg.norm(x)**2

47.0

Passt! Die Möglichkeit zur vektorisierten Berechnung ist ein großer Vorteil gegenüber anderen Normen.

Ableitung der quadrierten $L^2$‑Norm

Wir haben gesehen, dass Normen zur Modellbewertung dienen, indem sie Fehlervektoren zusammenfassen.

Nun gehen wir einen Schritt weiter: Wie ändern wir die Modellparameter, um den Gesamtfehler zu verringern? Dazu verwenden wir eine Kostenfunktion, die den Fehler des Modells in Abhängigkeit von den Parametern angibt. Mit Gradientenabstieg lässt sich das Minimum dieser Funktion finden. Dabei berechnen wir die Ableitungen nach jedem Parameter (partielle Ableitungen = Gradienten). Daher ist es entscheidend, die Ableitung effizient bestimmen zu können.

Ein großer Vorteil der quadrierten $L^2$‑Norm ist, dass sich ihre partiellen Ableitungen leicht berechnen lassen. Gegeben sei der Vektor:

Seine quadrierte $L^2$‑Norm lautet:

Für die partiellen Ableitungen betrachten wir alle anderen Variablen als konstant. Beispielsweise ist die partielle Ableitung nach $u_1$ die Ableitung von $u_1^2+a$ ($a$ steht für den konstanten Anteil der übrigen Variablen). Daraus folgen die partiellen Ableitungen:

Schön an den Gradienten der quadrierten $L^2$‑Norm ist, dass jede Ableitung unabhängig von den übrigen Variablen ist. Bei der $L^2$‑Norm ist das nicht so.

Ableitung der $L^2$‑Norm

Bei der $L^2$‑Norm ist die Ableitung komplizierter und hängt von allen Elementen des Vektors ab. Für den Vektor $\\bs{u}$ gilt:

Berechnen wir die Ableitung nach $u_1$:

Wir sehen: Die partielle Ableitung nach $u_1$ enthält weiterhin $u_2...u_n$. Die anderen Gradienten haben analogen Aufbau:

Weitere Überlegungen

Die quadrierte $L^2$‑Norm ist großartig, hat aber einen Haken: Sie unterscheidet schwach zwischen 0 und kleinen Werten, weil die Funktion nahe 0 nur langsam ansteigt.

Das sehen wir im Vergleich der quadrierten $L^2$‑Norm mit der $L^2$‑Norm. Die z‑Achse zeigt den Normwert, x‑ und y‑Achse stehen für zwei Parameter. Dasselbe gilt in mehr als 2 Dimensionen, nur ist es dann schwer zu visualisieren.

$L^2$‑Norm:

Quadrierte $L^2$‑Norm:

Zum Vergleich die $L^1$‑Norm:

Diese Plots sind mit Hilfe dieser Website entstanden. Probiere die Normen dort selbst aus, um ein Gefühl für ihre Form zu bekommen.

Die Max‑Norm

Das ist die $L^\\infty$‑Norm und entspricht dem Betrag des größten Elements im Vektor.

Matrixnormen: Die Frobenius‑Norm

Das entspricht der $L^2$‑Norm der Matrix nach dem Flattening.

Dieselbe Numpy‑Funktion kann verwendet werden:

A = np.array([[1, 2], [6, 4], [3, 2]])
A

array([[1, 2],
       [6, 4],
       [3, 2]])

np.linalg.norm(A)

8.3666002653407556

Skalarprodukt in Normen ausgedrückt

Das Skalarprodukt der Vektoren $\\bs{x}$ und $\\bs{y}$ lässt sich über ihre $L^2$‑Normen ausdrücken. $\\theta$ ist der Winkel zwischen den beiden Vektoren.

Beispiel 4.

Nehmen wir zwei Vektoren in 2 Dimensionen:

und

Die folgende Grafik zeigt die Darstellung:

x = [0,0,0,2]
y = [0,0,2,2]

plotVectors([x, y], [sns.color_palette()[0], sns.color_palette()[1]])

plt.xlim(-1, 3)
plt.ylim(-1, 3)

plt.text(-0.5, 1, r'$\\vec{x}$', size=18, color=sns.color_palette()[0])
plt.text(1.5, 0.5, r'$\\vec{y}$', size=18, color=sns.color_palette()[1])

<matplotlib.text.Text at 0x10a33b950>

Wir haben dieses Beispiel wegen seiner Einfachheit gewählt. Wie man sieht, beträgt der Winkel $\\theta$ 45°.

Zuerst berechnen wir das Skalarprodukt der Vektoren:

x = np.array([0, 2])
y = np.array([2, 2])

x.dot(y)

4

Und jetzt ihre Normen:

und

Mit der obigen Formel ergibt sich:

Das entspricht dem Ergebnis des Skalarprodukts. Hier die Rechnung mit numpy. Beachte: Wir nutzen deg2rad aus Numpy, weil np.cos den Winkel im Bogenmaß erwartet und wir daher umrechnen müssen.

# Note: np.cos take the angle in radian
np.cos(np.deg2rad(45))*2*np.sqrt(8)

4.0000000000000009

Fazit

Die $L^2$‑Norm (bzw. die Frobenius‑Norm bei Matrizen) und die quadrierte $L^2$‑Norm sind im Machine Learning, Deep Learning und in der Data Science allgemein weit verbreitet. Normen können zum Beispiel als Kostenfunktionen dienen. Willst du etwa eine Gerade an einen Punktsatz anpassen, kannst du mit zufälligen Parametern starten und iterativ die Kostenfunktion minimieren. Die Kostenfunktion misst den Fehler deines Modells – dieser soll möglichst klein sein. Normen sind hier hilfreich, weil sie den Fehlervektor auf einen Skalar abbilden. Die Kostenfunktion ist dieser Skalar für einen gegebenen Parametersatz.

Wir haben gesehen: Eine Norm ist nichts anderes als die Reduktion eines Arrays auf einen Skalar. Es gibt verschiedene Varianten, je nach zugrunde liegender Funktion. Welche Norm du wählst, hängt stark vom Problem ab – jede hat Vor- und Nachteile. Die $L^1$‑Norm ist zum Beispiel robuster als die $L^2$‑Norm, denn die $L^2$‑Norm reagiert empfindlicher auf Ausreißer: Große Fehlerwerte führen zu sehr großen quadrierten Fehlern.

Dieses Tutorial basiert auf diesem Artikel aus meiner Serie zum Kapitel Lineare Algebra im Deep Learning Book von Goodfellow et al.

Referenzen

https://www.quora.com/Why-is-L1-regularization-better-than-L2-regularization-provided-that-all-Norms-are-equivalent

http://www.deeplearningbook.org/contents/linear_algebra.html

https://docs.scipy.org/doc/numpy-1.14.0/reference/generated/numpy.linalg.norm.html

https://hadrienj.github.io/deep-learning-book-series-home/

http://christopher5106.github.io/deep/learning/2016/09/16/about-loss-functions-multinomial-logistic-logarithm-cross-entropy-square-errors-euclidian-absolute-frobenius-hinge.html

https://datascience.stackexchange.com/questions/10188/why-do-cost-functions-use-the-square-error