====== 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.

===== Univariate linear regression =====

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

$\theta_i$ Parameter

==== Cost function ====
$\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)$

=== Functions (example with only $\theta_1$): ===

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

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

[[http://reference.wolfram.com/mathematica/ref/ContourPlot.html | 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.

===== Multiple linear regression =====

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$

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

===== Gradient Descent Improvements =====
==== 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 <= x_i <= 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 -> ...


===== Polynomial regression =====
$\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}$