Regression

Quelle: Coursera ML Course

Kategorie: Supervised learning (da es wahre Werte gibt)

Notation: $(x^{(i)}, y^{(i)})$ - i-tes Training Beispiel (i-te Zeile)

Hypothesis h: Funktion, die x zu y mappt.

$h_\theta(x) = \theta_0 + \theta_1 x$

$\theta_i$ Parameter

Cost function

$\text{minimize}_{\theta_0,\theta_1} \sum_{i=1}^m (h_\theta(x^{(i)})-y^{(i)})^2$

Vereinfachtes Problem:

$\text{minimize}_{\theta_0,\theta_1} \frac{1}{2*m} \sum_{i=1}^m (h_\theta(x^{(i)})-y^{(i)})^2$

$h_\theta(x^{(i)}) = \theta_0 +\theta_1x^{(i)}$

Cost function (Squared error cost function):

$J(\theta_0,\theta_1) = \frac{1}{2*m} \sum_{i=1}^m (h_\theta(x^{(i)})-y^{(i)})^2$

Goal: $\text{minimize}_{\theta_0,\theta_1} J(\theta_0,\theta_1)$

Functions (example with only $\theta_1$):

$h_\theta(x)$ (fixed $\theta_1$, function of $x$)

$J(\theta_1)$ (function of the parameter $\theta_1$)

Contour plots

Gradient descent

$\min_{\theta_0, \theta_1} J(\theta_0, \theta_1)$ (für n Parameter möglich)

Starten mit $\theta_0, \theta_1$.

Kann in verschiedenen lokalen Optima landen.

Algorithmus:

Batch Gradient Descent: Jeder Schritt des Verfahrens nutzt alle Trainingspunkte.

Wiederholen bis zur Konvergenz:

$\theta_j := \theta_j - alpha \frac{\partial}{\partial\theta_j} J(\theta_0, \theta_1)$

Gleichzeitiges Update (!):

$$ tmp0 := \theta_0 - alpha \frac{\partial}{\partial\theta_0} J(\theta_0, \theta_1)\\ tmp1 := \theta_1 - alpha \frac{\partial}{\partial\theta_1} J(\theta_0, \theta_1)\\ \theta_0 := tmp0\\ \theta_1 := tmp1 $$

Learning rate:
  • $\alpha$ zu klein: Gradient descent kann langsam sein
  • $\alpha$ zu groß: Minimum kann übergangen werden, konvergiert u.U. nicht.

Wenn man Minimum näher komt, werden die Schritte automatisch kleiner (da Steigung abnimmt). $\alpha$ muss nicht kleiner gewählt werden.

Partial derivates

$$j=0: \frac{\partial}{\partial\theta_0} J(\theta_0, \theta_1) = \frac{1}{m} \sum_{i=1}^m (h_{\theta}(x^{(i)})-y^{(i)})\\ j=1: \frac{\partial}{\partial\theta_1} J(\theta_0, \theta_1) = \frac{1}{m} \sum_{i=1}^m (h_{\theta}(x^{(i)})-y^{(i)}) * x^{(i)} $$

Funktion

Konvexe Funktion (lokales Optimum = globales Optimum)

Normal equation method

Vorteil: Kein Alpha nötig, kann evtl. schneller sein. Nachteil: Gradient descent besser für große Datenmengen.

Notation: $x^{(i)}_j$: i-tes Trainingbeispiel, Feature j

Hypothesis h: $h_\theta(x) = \theta_0 + \theta_1 x_1 + \theta_2 x_2 + \ldots + \theta_n x_n$

Vereinfacht: $x_0 = 1; (x_0^{(i)}=1)$ $h_\theta(x) = \theta_0 x_0 + \ldots + \theta_n x_n = \theta^T x$

Cost function

$J(\theta) = \frac{1}{2*m} \sum_{i=1}^m (h_\theta(x^{(i)})-y^{(i)})^2 = \frac{1}{2*m} \sum_{i=1}^m (\theta^T x^{(i)} - y^{(i)})^2 = \frac{1}{2*m} \sum_{i=1}^m ((\sum_{j=0}^n \theta_j x_j^{(i)}) - y^{(i)})^2$

Gradient Descent

$\theta_j := \theta_j - alpha \frac{\partial}{\partial\theta_j} J(\theta)$

Normalengleichungen

  • Feature-/Designmatrix X (Dim: m x (n+1))
  • Vector y (Dim: m)

$\theta = (X^TX)^{-1}X^Ty$

  • Feature scaling nicht notwendig.

Was wenn $X^TX$ singulär (nicht invertierbar)?

(pinv in Octave)

Gründe für Singularität:

  • Redundante Features (lineare Abhängigkeit)
  • Zu viele Features (z.B. $m \Leftarrow n$)
    • Lösung: Features weglassen oder regularisieren

Wann was benutzten?

  • m training tupel, n features
  • GD funktioniert bei großem n (> 1000) gut, Normalengleichung muss (n x n) Matrix invertieren, liegt ungefähr in $O(n^3)$.

Feature Scaling

  • Features auf ähnliches Skalenniveau bringen führt zu schnellerer Konvergenz
    • Bspw. wenn Contour Plots länglich werden ($x_1 \in [0,2000]$, $x_2 \in [0,5]$).
  • Vorschlag: Feature ungefähr zwischen $-1 \Leftarrow x_i \Leftarrow 1$ bringen.
    • Rule of thumb: -3 to 3 (nicht zu groß, nicht zu klein)

Mean normalization

$x_i - \mu_i$

$\frac{x_i - \mu_i}{s_i}$, wobei $s_i$ Range ($max-min$) oder Standardabweichung sein kann.

Learning rate $\alpha$

  • $J(\theta)$ sollte nach jeder Iteration kleiner werden(Plot J/#Iterations).
    • Alternativ: Konvergenz erklären, wenn Änderungen kleiner $\epsilon$.
  • Falls $J(\theta)$ ansteigt, überschreitet GD vermutlich Minimum, d.h. kleineres $\alpha$ verwenden.
  • Wenn $\alpha$ zu klein: Langsame Konvergenz
  • Wenn $\alpha$ zu groß: $J(\theta)$ sinkt nicht bei jeder Iteration und konvergiert evtl. nicht.
  • Schema: 0,001 → 0,003 → 0,01 → 0,03 → 0,1 → …

$\theta_0 + \theta_1 x + \theta_2 x^2 + \theta_3 x^3$

Durch entsprechende Features möglich: $x_3 = (size)^3$

Feature scaling wird dann wichtig (da groß und verschieden)

Oder Wurzelfkt.:

$\theta_0 + \theta_1 x + \theta_2 \sqrt{x}$