kurse:efcomputergrafik:kw10 [https://fginfo.ksbg.ch Fachgruppe Informatik der KSBG]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
==== KW10 Ziele =====

  * Jede/r kann eine multivariate Regression mit und ohne SciKit durchführen
  * <del>Jede/r kennt eine Strategie, wie das beste Modell ausgewählt werden kann und kennt die  Begriff Trainings, Validierungs- und Testdatensatz.</del>
  * Jede/r kennt die Idee des <<gradient descent>> Algorithmus und kann für eine Funktion mit dem <<gradient descent>> das Minimum bestimmen.

Abzugeben sind die Komma-getrennten Vorhersagen der letzten Woche sowie die Vorhersage des besten Modells dieser Woche auf der  [[kurse:efcomputergrafik:forecastcompetition|Forecasts-Seite]]
==== Theorie ==== 
=== Notation ===
Wie letztes Mal erwähnt, halten wir uns an folgenden Abmachungen:
  * Grossbuchstaben $X$, $Y$ sind Zufallsvariablen
  * Kleinbuchstaben mit Index sind Datenpunkte $x_i$. $x_i$ kann dabei eine Zahl oder ein Vektor sein. $y_i$ ist immer die abhängige Grösse
  * Fehler im Model werden mit $\varepsilon_i$ bezeichnet, es ist $y_i=\alpha+\beta \cdot x_i+\varepsilon_i$
  * Modellvorhersagen werden mit einem Dach $\hat{}$ versehen. Kennt man $\alpha$ und $\beta$ ist $\hat y_i=\alpha+\beta\cdot x_i$ also $y_i-\hat y_i = \varepsilon_i$ (( $\beta$ kann dabei entweder eine Zahl oder ein Vektor sein. Die Multiplikation ist dann entweder die normale Multiplikation oder das Skalarprodukt.))

=== Theorie multivariate lineare Regression ===

Wie bereits in der ersten Woche erläutert, ist das Modell $y_i=\alpha+\beta x_i+\epsilon_i$ häufig zu einfach. Man möchte mehrere Variablen verwenden, um Vorhersagen über den möglichen Wert $\hat y_i$ zu machen: Das Modell wird dann zu 
\[
Y=\alpha+\beta_1X_1+\beta_2X_2+\cdots +\beta_pX_p.
\]
Um die Parameter (resp. das Modell) zu bestimmen, betrachtet man wiederum die Summe der quadrierten Abstände und sucht $\alpha,\beta_1,\ldots,\beta_p$, so dass eben die Summe der quadrierten Abstände minimal ist.

Von der Überlegung her, suchen wir also wieder $\alpha,\beta_1,\ldots,\beta_p$ so, dass 
\[
\sum_{i=1}^n (y_i-\alpha-\beta_1 x_i^1-\cdots-\beta_px_i^p)^2
\]
minimal ist. Dies kann -- theoretisch -- wieder via Ableiten und Nullsetzen passieren. ((Die Summe oben kann als Funktion von $\alpha,\beta_1,\ldots,\beta_p$ aufgefasst werden, deren Minimum wir suchen, i.e.
\[
g(\alpha,\beta_1,\ldots,\beta_p)=\sum_{i=1}^n (y_i-\alpha-\beta_1 x_i^1-\cdots-\beta_px_i^p)^2.
\]))

Praktisch wird es aber häufig über Matrizenmultiplikation gelöst (orthogonale Projektion).

Für unsere Zwecke genügen die Resultate dieser Herleitung: Es ist
\[
\mathbf{\beta} = \begin{bmatrix}
\alpha \\
\beta_1 \\
\beta_2 \\
\vdots\\
\beta_p
  \end{bmatrix} = (\mathbf{X}'\mathbf{X} )^{-1}\mathbf {X}' \mathbf y
\]
wobei
\[
X= \begin{bmatrix}
1& x_{1}^1 & x_{1}^2 & \cdots & x_{1}^j & \cdots & x_{1}^p\\
1& x_{2}^1 & x_{2}^2 & \cdots & x_{2}^j & \cdots & x_{2}^p\\
\vdots & \vdots & \ddots & \vdots & \ddots & \vdots\\
1&x_{i1} & x_{i}^2 & \cdots & x_{i}^j & \cdots & x_{i}^p\\
\vdots & \vdots & \ddots & \vdots & \ddots & \vdots\\
1& x_{n}^1 & x_{n}^2 & \cdots & x_{n}^j & \cdots & x_{n}^p
\end{bmatrix} 
\text{ und } y =
  \begin{bmatrix}
    y_1 \\
    y_2 \\
    \vdots \\
    y_i \\
    \vdots \\
    y_n
  \end{bmatrix}
\]
mit $X$ einer $(n \times (p+1))$ Matrix, $y$ ein $n\times 1$ Vektor (Matrix).
Mit SciKit können mehrere Features (z.B. Alter und Kilometer) ebenfalls verwendet werden 
<code python | scikit_regression.py>

#relevante spalten auswählen
x = np.asarray([data[:,6],data[:,8]]).transpose()
y = data[:,7]
reg = LinearRegression(fit_intercept=True).fit(x, y)
</code>

==== Aufgaben ==== 
  - Führe mindestens zwei Regressionen (mit SciKit oder von Hand) aus, bei der du mindestens zwei Variablen verwendest, um den Preis vorherzusagen.
  - Finde eine Möglichkeit, zu entscheiden, welches das bessere Model ist. 
  - Wähle dein besseres Modell und verwende dieses um wiederum auf dem Testdatensatz Vorhersagen zu machen, welches wohl der Preis des Fahrzeugs ist.
  - Können alle Variablen gleich mit ins Modell einbezogen werden? Was ist mit mit <<Diesel>> oder <<Modell>>?
  - Wie könnten die Koeffizienten interpretiert werden?

==== Gradient Descent ====

Im Fall der linearen Regression lassen sich die Koeffizienten explizit berechnen. Dies ist allerdings nicht immer der Fall: Gelingt es nicht, das Maximum oder Minimum einer Funktion analytisch zu bestimmen, kann man immer versuchen, dieses numerisch zu bestimmen. Dazu verwendet man den sogenannten Gradienten.

Der Gradient einer Funktion, ist die der Vektor, welche die Ableitung in jede Richtung als Komponenten enthält. Ist $f:\mathbb{R}^p\rightarrow \mathbb{R}$, dann ist
\[
\nabla f= [\frac{\partial f}{\partial x_1},\;\frac{\partial f}{\partial x_2},\cdots, \frac{\partial f}{\partial x_p}]'.
\]
Der Gradient von $f$ hat die wichtige Eigenschaft, dass er immer die Richtung des grössten Zuwachses angibt. Diese Eigenschaft wird ausgenutzt, um dann eben die Richtung der Stärksten Abnahme, $-\nabla f$ zu bestimmen und in diese Richtung ein Minimum zu suchen.((Die Erklärung dafür findet sich eigentlich an der Uni im ca. 2 Semester. Einen Überblick kann sich auch auf der [[https://www.khanacademy.org/math/multivariable-calculus/multivariable-derivatives/gradient-and-directional-derivatives/v/why-the-gradient-is-the-direction-of-steepest-ascent|Khan-Academy]] verschafft werden. Wir verwenden einfach die Eigenschaft, dass der Gradient die Richtung des stärksten Zuwachses angibt))


=== Beispiel ===
Ist $f(x,y)=(x-2)^2+(y+1)^2$ so ist $\nabla f =[2x-4,\;2y+2]'$. Damit ist z.B. die Richtung der stärksten Zunahme an der Stelle $[3,-3]'$ 
$[2\cdot 3-4,\;2\cdot(-3)+2]'=[2,-4]'$.

Möchte man jetzt das Minimum numerisch finden, kann man vom Startpunkt $[3,-3]'$ aus ein Vielfaches $\gamma$ des negativen Gradienten dazuzählen, um dem Minimum näher zu kommen:
  - Wähle einen Startpunkt $v_0$, z.B. $v_0=[3,-3]'$
  - $v_{t+1}=v_t-\gamma \cdot \nabla f$, z.B. mit $\gamma=\frac 14$ und $v_1=v_0-\frac{1}{4}\cdot [2,-4]=[1.5,-3]$

Die Schlaufe kann fortgesetzt werden, bis sich der Wert von $f$ an der aktuellen Stelle nicht mehr zu stark ändert.

==== Aufgaben ====
Nimm für die folgenden Aufgaben die Funktion $f(x,y)=2\cdot(x-3)^2+(y+2)^2$. Du kannst auch diese {{kurse:efcomputergrafik:efcg_contourplot.ggb|Geogebra-Datei als Hilfestellung}} verwenden.
  - Zeichne einen <<contour plot>> für $f$. Wähle mindestens drei verschiedene Niveaus für die Niveaulininien
    - Contourplot können mit Geogebra (''Folge(f(x, y) = m, m, 1, 20, 2)'') erstellt werden.
    - Berechne einen Gradienten in einem Punkt, welcher auf einer gezeichneten Niveaulinie liegt. Zeichne den Gradienten als Vektor angehängt in diesem Punkt ein. Wähle einen anderen Punkt und mache dasselbe? Was fällt auf?
  - Berechne zwei Schritte des <<gradient descent>>-Verfahren von Hand und trage diese im <<contour plot>> oben ein.
  - Implementiere den Gradient <<gradient descent>> für die Funktion $f(x,y)=(x-2)^2+(y+1)^2$ in Python.
  - Wähle ein Funktion mit mehr als einem Minimum und lasse den <<gradient descent>> Algorithmus das Minimum findet. Was passiert?
  - Bestimme $\alpha$ und $\beta$ mit dem <<gradient descent>> Algorithmus. Wähle dabei ein Beispiel mit einer Variable $Y=\beta\cdot X+\alpha+\varepsilon$. 
    - Standardisiere((Standardisieren heisst, dass jede Beobachtung $x_i$ durch $\frac{x_i-\mu}{\sigma}$ ersetzt wird. Es ist dabei $\mu=\frac{1}{n}\sum_{i=1}^n x_i$ und $\sigma=\sqrt{\sum_{i=1}^n (x_i-\mu)^2}$.)) die Beobachtungen zuerst, sonst kommt es zu numerischen Problemen. 
    - Verwende für das Beispiel zuerst nur z.B. 50 Datensätze und vergleiche die Lösung mit der scikit Lösung.
    - Führe die Rechnung mit allen Datensätzen durch und vergleiche wiederum die Lösung mit der scikit Lösung.
  - Wie könnten ein bestes Model ausgewählt werden? Überlege dir Strategie, welche du verwenden könntest, um ein bestes Modell zu indentifizieren. Nota bene: Das Modell soll am besten auf neuen, ungesehen, Daten sein.