Am 1. Januar 1801 entdeckte der Astronom Giuseppe Piazzi den Zwergplanet Ceres. Er machte sehr detaillierte Notizen über Zeit und Position der Beobachtungen.

https://en.wikipedia.org/wiki/File:Costanzo_Angelini,_L%27astronomo_Piazzi_1825_ca.jpg

Wann kann man Ceres wieder beobachten?

https://en.wikipedia.org/wiki/File:Ceres-Beobachtung_von_Piazzi.png

Im September 1801 erstellte Carl F. Gauss ein Modell, welches die Sichtung von Ceres auf 0,5 Grad genau vorhersagte. Dazu verwendete er Linear Least-Squares Regression.

https://commons.wikimedia.org/wiki/File:Carl_Friedrich_Gauss_1840_by_Jensen.jpg

Beispiel

Wir wollen Grundstückspreise vorhersagen.

Datensatz von Kaggle.com

Welche Hypothesen $h$?

Lineare Funktionen \[ h(x) = w_0 + w_1 x_1 \]

z.B.: \[ h(x^{(1)}) = w_0 + w_1 \cdot 785\\ x^{(1)}_1 = 785 \]

Beispiel: $h(x) = 90 + 0.075 x$

Allgemeiner: \[ h_w(x) = w^{(0)} + \sum_{j=1}^n w^{(j)} x^{(j)} \]

Und noch allgemeiner: \[ h_w(x) = w \cdot \phi(x) \]

\[ \underbrace{ w = \left[ {\begin{array}{c} w^{(0)} \\ w^{(1)} \\ w^{(2)} \\ \vdots \end{array}} \right]}_\text{Gewichte / Parameter} \text{ und }\, \underbrace{ \phi(x) = \left[ {\begin{array}{c} 1 \\ x^{(1)} \\ x^{(2)} \\ \vdots \end{array}} \right]}_\text{Features} \]

$\phi$ nennen wir Feature Extractor.
Wir gehen erstmal immer von folgender Form aus: \[ \phi(x) = \left[ {\begin{array}{c} 1 \\ x^{(1)} \\ x^{(2)} \\ \vdots \end{array}} \right] \]

Wenn die Feature $x$ schon passend sind brauchen wir nicht notwendigerweise einen Feature Extractor.

Noch etwas Notation

• $x$: Input
• $y$: Output oder Target
• $(x,y)$: Example
• $\mathcal{D}_\text{train} = [(x_1, y_1), (x_2, y_2), (x_3, y_3), \ldots, (x_m, y_m)$: Trainingsdaten
• $m$: Anzahl Trainingsdaten

Was ist unser Ziel?

$h_w(x)$ soll nah an $y$ liegen

\[ \operatorname{Loss}(x, y, w) = (h_w(x) - y)^2 \]

\[ \operatorname{TrainLoss}(w) = \frac{1}{m} \sum_{(x,y) \in \mathcal{D}_\text{train}} ( h_w(x) - y )^2 \] (Squared Loss)

Ziel: \[ \min_w \operatorname{TrainLoss}(w) \]

\[ = \min \frac{1}{m} \sum_{(x,y) \in \mathcal{D}_\text{train}} ( h_w(x) - y )^2 \]

Beispiel: \[ {\color{red}w} = \left[ {\color{red} \begin{array}{c} 100 \\ 0.075 \end{array}} \right] \]

Wie finden wir optimale $w$?

Idee: Starte mit irgendeinem $w$, zum Beispiel: \[ w = \vec{0} = \left[ {\begin{array}{c} 0 \\ 0 \\ \vdots \end{array}} \right] \]

Versuche $w$ zu verändern, so dass $\operatorname{TrainLoss}(w)$ sinkt.

Grundlagen: Gradienten

Wir starten mit einer Funktion $f: \mathbb{R}^3 \to \mathbb{R}$: \[ f(\left[ {\begin{array}{c} x_1 \\ x_2 \\ x_3 \end{array}} \right]) = x_1^2 + \frac{1}{x_2} + x_3 \]

Was ist die Ableitung von $f$?

Was wäre die Ableitung von
$f(x_1) = x_1^2 + \frac{1}{x_2} + x_3$
mit $x_2$ und $x_3$ konstant (z.B. $x_2 = 2$, $x_3= 4$)

\[ f'(x_1) = 2 x_1 \]

Partielle Ableitungen

$f(x_1, x_2, x_3) = x_1^2 + \frac{1}{x_2} + x_3$

• $\frac{\partial}{\partial x_1}f(x_1, x_2, x_3) = 2 x_1$
• $\frac{\partial}{\partial x_2}f(x_1, x_2, x_3) = - \frac{1}{x_2^2}$
• $\frac{\partial}{\partial x_3}f(x_1, x_2, x_3) = 1$

Wenn die Parameter "interagieren" ändert sich trotzdem nichts:

$f(x_1, x_2) = x_1 x_2^2$

• $\frac{\partial}{\partial x_1}f(x_1, x_2) = x_2^2$
• $\frac{\partial}{\partial x_2}f(x_1, x_2) = 2 x_1 x_2$

Die partielle Ableitung sagt uns, wie stark sich die Funktion in der Richtung ändert:

$f(x_1 + \epsilon, x_2) \approx f(x_1, x_2) + \epsilon \frac{\partial}{\partial x_1}f(x_1, x_2)$

$f(x_1, x_2 + \epsilon) \approx f(x_1, x_2) + \epsilon \frac{\partial}{\partial x_2}f(x_1, x_2)$

Beispiel: $f(x_1, x_2) = x_1 x_2^2$

$f(3, 2) = 12$

$\frac{\partial}{\partial x_1} f(x_1, x_2) = x_2^2$

$\frac{\partial}{\partial x_1} f(3, 2) = 2^2 = 4$

$f(3.1, 2) = 12.4$

$f(3,2) + 0.1 \frac{\partial}{\partial x_1} f(3, 2) = 12 + 0.1 \cdot 4 = 12.4$

Beispiel: $f(x_1, x_2) = x_1 x_2^2$

$f(3, 2) = 12$

$\frac{\partial}{\partial x_2} f(x_1, x_2) = 2 x_1 x_2$

$\frac{\partial}{\partial x_1} f(3, 2) = 2 \cdot 3 \cdot 2 = 12$

$f(3, 2.1) = 13.23$

$f(3,2) + 0.1 \frac{\partial}{\partial x_2} f(3, 2) = 12 + 0.1 \cdot 12 = 13.2$

Definition: Gradient

\[ \nabla f(x) = \left[ {\begin{array}{c} \frac{\partial}{\partial x_1} f(x) \\ \frac{\partial}{\partial x_2} f(x) \\ \frac{\partial}{\partial x_3} f(x) \\ \vdots \end{array}} \right] \] Der Gradient ist der Vektor mit allen partiellen Ableitungen

Beispiel: $f(x_1, x_2) = x_1 x_2^2$

\[ \nabla f(x_1, x_2) = \left[ {\begin{array}{c} x_2^2 \\ 2 x_1 x_2 \end{array}} \right] \]

\[ \nabla f(3, 2) = \left[ {\begin{array}{c} 4 \\ 12 \end{array}} \right] \]

Der Gradient ist die Richtung in der $f$ am meisten ansteigt

Auch bei noch wilderen Funktionen funktioniert alles analog:$f: \mathbb{R}^{2\times 2} \to \mathbb{R}$ \[ f(\left[ {\begin{array}{cc} x_{1,1} & x_{1,2} \\ x_{2,1} & x_{2,2} \end{array}} \right]) = x_{1,1}^3 x_{2,1} - 2 x_{1,2} x_{2,1}^2 + 5 x_{2,2} \]

\[ \nabla f(\left[ {\begin{array}{cc} x_{1,1} & x_{1,2} \\ x_{2,1} & x_{2,2} \end{array}} \right]) = \left[ {\begin{array}{cc} 3 x_{1,1}^2 x_{2,1} & -2 x_{2,1}^2 \\ x_{1,1}^3 - 4 x_{1,2} x_{2,1} & 5 \end{array}} \right] \]

Gradient Descent

$-\nabla \operatorname{TrainLoss}(w)$ ist die Richtung, in die der TrainingLoss am meisten sinkt.

$\eta$: Lernrate / step size

Abbruchkriterium

• Maximale Iterationszahl
• Gradient klein genug: $|| \nabla \operatorname{TrainLoss}(w_{t}) || < \epsilon$

\[ \operatorname{TrainLoss}(w) = \frac{1}{m} \sum_{(x,y)\in\mathcal{D}_\text{train}} (w \cdot \phi(x) - y)^2 \]

\[ \nabla \operatorname{TrainLoss}(w) = \frac{1}{m} \sum_{(x,y)\in\mathcal{D}_\text{train}} 2 ({\color{red} \underbrace{w \cdot \phi(x)}_\text{prediction}} - {\color{blue} \underbrace{y}_\text{target}}) \phi(x) \]

Konkret ist unser Update für die Lineare Regression: \[ w \gets w - \eta \frac{1}{m} \sum_{(x,y)\in\mathcal{D}_\text{train}} 2 (w \cdot \phi(x) - y) \phi(x) \]

Jupyter

Für lineare Funktionen wird Gradient Descent immer das globale Optimum finden (wenn die Lernrate klein genug ist).

\[ \nabla \operatorname{TrainLoss}(w) = \frac{1}{|\mathcal{D}_\text{train}|} \sum_{(x,y)\in\mathcal{D}_\text{train}} \nabla \operatorname{Loss}(x,y,w) \]

Gradient descent skaliert schlecht mit der Anzahl Beispielen.

Können wir auch schon Fortschritt machen, bevor wir alle Beispiele gesehen haben?

Nochmal konkret für die Lineare Regression: \[ w \gets w - \eta (w \cdot \phi(x) - y) \phi(x) \]

Jupyter

Hybride Optionen sind auch möglich: Mini Batch Gradient Descent

Wie wählen wir die Schrittgröße $\eta$?

Schnelle Konvergenz vs Stabilität

• Simple Strategien:
  • Konstante: $\eta = 0.01$
  • Mit der Zeit fallend: $\eta = \frac{1}{\sqrt{\text{\# updates}}}$
• Komplexere Strategien:
  • AdaGrad
  • Adam

Kernidee: Lieber viele kleine und ungenaue, als ein präzises Update

Quantität über Qualität

Für lineare Regression kann man die Gewichte auch direkt optimal berechnen: \[ w = (X^T X)^{-1} X^T Y \]

scikit-learn

Effiziente Library mit sehr vielen Funktionen für Machine Learning und Preprocessing von Daten.

https://scikit-learn.org

sklearn: LinearRegression

Pattern:

          model = LinearRegression()
          model.fit(features, targets)

          model.predict(features)
        

Jupyter

Andere Sichtweise auf Least Squares Loss

Annahme: \[ y_i = \hat{w} \cdot x_i + e_i \\ e_i \sim \mathcal{N}(0, \sigma^2) \]

$\mathcal{N}(\mu, \sigma^2)$: Normalverteilung (Gauß Verteilung)

$\frac{1}{\sigma \sqrt{2 \pi}} e^{-\frac{(x-\mu)^2}{2 \sigma^2}}$

https://en.wikipedia.org/wiki/File:Standard_deviation_diagram.svg

Wahrscheinlichkeitstheorie

• Zufallsvariablen $X$
• Werte von ZV $X=x$
• Wahrscheinlichkeiten $P(X=x)$
• Wahrscheinlichkeitsverteilung $P(X)$
• Erwartungswert $E(X) = \sum_x x P(X=x)$
• Varianz $\operatorname{Var}(X) = \sum_x E((X - E(X))^2)$
• Bedingte Wahrscheinlichkeit $P(X=x | Y=y)$

Central Limit Theorem (Zentraler Grenzwertsatz)

In etwa: Die Summe vieler unabhängiger Zufallsvariablen ist normalverteilt.

https://commons.wikimedia.org/wiki/File:Galton-Brett.svg

Wenn \[ y_i = w \cdot x_i + e_i \\ e_i \sim \mathcal{N}(0, \sigma^2) \]

dann \[ y_i \sim \mathcal{N}(w \cdot x_i, \sigma^2) \]

Die Likelihood, dass wir unsere Trainingsdaten beobachten, wenn die Gewichte $w$ sind ist: \[ \mathcal{L}(w) = \prod_{(x,y) \in \mathcal{D}_\text{train}} p(y | x; w) \]

\[ = \prod_{(x,y) \in \mathcal{D}_\text{train}} \frac{1}{\sigma \sqrt{2 \pi}} e^{-\frac{({\color{red} y - w \cdot x})^2}{2 \sigma^2}} \]

Was, wenn wir eine andere Verteilung haben?

Wir wollen das $w$ mit maximaler Likelihood haben: \[ \operatornamewithlimits{arg\,max}_w \mathcal{L}(w) \]

$\operatornamewithlimits{arg\,max}$ gibt uns den Parameter, der die folgende Gleichung maximiert.

\[ \max_x -(3-x)^2 = 0 \]

\[ \operatornamewithlimits{arg\,max}_x -(3-x)^2 = 3 \]

\[ \operatornamewithlimits{arg\,max}_w \mathcal{L}(w) = \operatornamewithlimits{arg\,max}_w \underbrace{\log(\mathcal{L}(w))}_{= l(w) \text{ Log-Likelihood}} \]

$\log(x)$

\[ l(w) = \log \prod_{(x,y) \in \mathcal{D}_\text{train}} \frac{1}{\sigma \sqrt{2 \pi}} e^{-\frac{(y - w \cdot x)^2}{2 \sigma^2}} \]

\[ = \sum_{(x,y) \in \mathcal{D}_\text{train}} \log(\frac{1}{\sigma \sqrt{2 \pi}}) -\frac{(y - w \cdot x)^2}{2 \sigma^2} \]

\[ = m \log(\frac{1}{\sigma \sqrt{2 \pi}}) - \sum_{(x,y) \in \mathcal{D}_\text{train}} \frac{(y - w \cdot x)^2}{2 \sigma^2} \]

\[ \operatornamewithlimits{arg\,max}_w\, l(w) = \\ \operatornamewithlimits{arg\,max}_w\, m \log(\frac{1}{\sigma \sqrt{2 \pi}}) - \sum_{(x,y) \in \mathcal{D}_\text{train}} \frac{(y - w \cdot x)^2}{2 \sigma^2} \]

\[ = \operatornamewithlimits{arg\,max}_w - \sum_{(x,y) \in \mathcal{D}_\text{train}} (y - w \cdot x)^2 \]

Das ist äquivalent zu unserem Squared Loss: \[ \operatornamewithlimits{arg\,min}_w \frac{1}{m} \sum_{(x,y) \in \mathcal{D}_\text{train}} ( h_w(x) - y )^2 \]

Was merken wir uns?

• Unter gewissen Annahmen ist unsere Regressionskurve die, die am "ehesten" die richtige ist.
• Unser Loss "entspricht" dem Logarithmus der Likelihood

Andere Loss Funktionen sind möglich, zum Beispiel \[ Loss_\text{Abs.}(x,y,w) = | h_w(x) - y | \]