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

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

Vereinfachtes Problem:

$\displaystyle\min_{\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$:

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

Goal: $\displaystyle\min_{\theta_0,\theta_1} J(\theta_0,\theta_1)$

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

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

Contour plots

$\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.

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 $$

• $\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.

$$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)} $$

Konvexe Funktion (lokales Optimum = globales Optimum)

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 + ... + \theta_n x_n$

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

$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$

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

• 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 <= 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)$.

• 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 <= x_i <= 1$ bringen.
  • Rule of thumb: -3 to 3 (nicht zu groß, nicht zu klein)

$x_i - \mu_i$

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

• $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}$