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 | \]

Wenn die Fehler normalverteilt sind, ist der Squared Loss (oder Mean Squared Error - MSE) \[ \frac{1}{m} \sum_{(x,y) \in \mathcal{D}_\text{train}} ( h_w(x) - y )^2 \] die Varianz unserer Fehler $\color{red} e$.

Annahme: $e^{(i)} \sim \mathcal{N}(0, \sigma^2)$ mit $\sigma = \text{RMSE}$

• $68.27 \%$ der Daten $y$ sind nicht mehr als RMSE von $h_w(x)$ entfernt.
• $95.45\%$ nicht mehr als 2 RMSE
• $99.73\%$ nicht mehr als 3 RMSE

68 - 95 - 99.7 Regel

Meistens stimmt die Annahme über normalverteilte Fehler nur ungefähr.
Daher stimmt die Interpretation meist auch nur ungefähr.

RMSE ist meist ein guter Indikator ob unser Modell "gut genug" ist.

R2 Score
Coefficient of determination

Gibt an, wie viel besser wir sind, als einfach den Mittelwert vorherzusagen

• $\text{R2} = 1$: Alle Punkte perfekt getroffen.
• $\text{R2} > 0$: Besser als Durchschnitt vorhersagen.
• $\text{R2} = 0$: Könnten auch $h(x) = \bar y$ verwenden.
• $\text{R2} < 0$: Schlechter als Durchschnitt vorhersagen.

\[ \text{R2} = 1 - \frac{\color{blue} \text{SS}_\text{res}}{\color{red} \text{SS}_\text{tot}} \]

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

Es macht Sinn, immer mehrere Metriken zu tracken um potentielle Probleme zu finden.

• Mean Absolute Error: \[ \frac{1}{m} \sum_{(x,y) \in \mathcal{D}} |h(x) - y| \]
• Max Error: \[ \max_{(x,y) \in \mathcal{D}} |h(x) - y| \]