Differences

This shows you the differences between two versions of the page.

--- kurse:efcomputergrafik:kw09 [2020/02/27 06:31] – Simon Knaus
+++ kurse:efcomputergrafik:kw09 [2020/03/03 14:18] (current) – Simon Knaus
@@ Line 1: / Line 1: @@
+==== KW09 Ziele =====
+  * Jede/r kennt was ein Regressions-/Klassifikationsproblem ist
+  * Jede/r kann eine lineare Regression in Python und mit SciKit durchführen.
+  * Jede/r kennt die Begriffe Residuum, Residual Sum of Squares, feature space.
+==== Einführung ====
+  * Vorstellung
+  * Kenntniserhebung
+    * Python
+    * Pythonumgebung
+    * Mathematik: Stochastik, Erwartungswert, Regression
+  * Einstieg
+    * Clearview
+      * [[https://www.nytimes.com/2020/01/18/technology/clearview-privacy-facial-recognition.html| New York Times]] Artikel
+      * [[https://nzzas.nzz.ch/meinungen/kuenstliche-intelligenz-app-bietet-gesichtserkennung-an-ld.1536444|NZZ am Sontag]] Artikel oder {{kurse:efcomputergrafik:kuenstliche_intelligenz_eine_app_bietet_gesichtserkennung_an.pdf|PDF}}
+      * [[https://www.nzz.ch/digital/gesichtserkennung-grosse-fortschritte-wachsender-widerstand-ld.1538489|NZZ]] Artikel oder {{kurse:efcomputergrafik:gesichtserkennung_grosse_fortschritte_wachsender_widerstand.pdf|PDF}}
+    * [[http://www.youtube.com/watch_popup?v=9CO6M2HsoIA|Slaugherbots]]
+  * Aufgaben / Besprechung
+=== Informatik und Mathematik ===
+Die meisten Probleme der Thematik maschinelles lernen (<<machine learning>>) oder künstlicher Intelligenz (<<artificial intelligence>>) lassen sich auf entweder
+  * Klassifikationsprobleme, oder
+  * Regressionsprobleme
+zurückführen.
+Im EF Computergrafik sprechen wir mehrheitlich von <<machine learning>>. Dieser Begriff ist enger abgegrenzt und trifft genauer, was wir machen. <<machine learning>> ist eine Teildisziplin von <<artificial intelligence>>. Im Verlaufe des Kurses werden wir noch neuronale Netzwerke besprechen. Wir kommen dann noch darauf, was unter Deep Learning zu verstehen ist.
+Wer die Thematik weiterverfolgen möchte, kann sich an diesen drei  Büchern unten orientieren
+  * [[https://web.stanford.edu/~hastie/Papers/ESLII.pdf|Elements of Statistical Learning]]. Knappe und konzise Einführung ist die klassischen Maschinen-Lernen-Techniken.
+  * [[https://www.deeplearningbook.org/|Deep Learning]]. Vertiefung der Machinen-Lernen-Techniken vor allem für neuronale Netzwerke und <<deep learning>>.
+  * [[https://www.penguinrandomhouse.com/books/603982/rebooting-ai-by-gary-marcus-and-ernest-davis/|Rebooting AI]]. Weitere Sicht in einem breiteren gesellschaftlichen Rahmen auf Probleme und Herausforderungen aktueller AI Thematiken.
+=== Formalisierung ===
+Mathematisch kann die Problematik auf folgende Gleichung heruntergebrochen werden:
+\[
+f(X)=Y.
+\]
+$X\in\mathbb{R}^p$ ist ein Vektor. Die Menge $\mathbb{R}^p$ ist dabei der sogenannte <<feature space>>. Dieser Vektor enthält Werte, welchen diesen Datenpunkt $X$ beschreiben. Der feature space kann grundsätzlich beliebig gross sein und sich auf auch Teilmengen von $\mathbb{R}$, z.B. $\mathbb{N}$ beschränken. Die Menge, in welchem die Werte von $Y$ liegen, wird mit $\mathcal Y$ bezeichnet.
+Man unterscheidet dabei zwischen
+  * Regression: Ist $\mathcal Y\subset \mathbb R$, dann ist es **Regressions**problem.
+  * Klassifikation: Ist $\mathcal Y\subset \mathbb N$, dann ist es **Klassifikations**sproblem.
+Die Probleme dabei, lassen sich wie folgt zusammenfassen
+  - Wie finde ich ein <<gutes $f$>>?
+  - Was ist <<gut>> in diesem Zusammenhang?
+Die Antwort auf die erste Frage, sind verschiedene Methoden. Im EF werden wir voraussichtlich folgende Methoden vertieft kennenlernen:
+  * Regression (Uni- und multivariat) als Brückenschlag zur normalen Mathe
+  * Smoothing-Splines als Brückenschlag zu Teil II
+  * $k$-nearest-neighbours als erste echte nicht-lineare Variante
+  * Neuronale Netze
+Dass $X$ und $Y$ gross geschrieben werden, hat damit zu tun, dass beide als Zuvallsvektoren verstanden werden. Zufallsvektoren sind Vektoren, welche aus Zufallsvariablen (Zufallsgrössen) bestehen. So ist $X=[X_1,X_2,\ldots,X_p]'$ ein $p$-Dimensionaler Zufallsvektor.
+$Y$ ist üblicherweise $1$-dimensional.
+=== Gütekriterien ===
+Grundsätzlich ist immer die Idee, dass mein Modell $f$ möglichst genau den Wert der Variable $Y$ vorhersagt, wenn ich die zugehörigen Werte von $X$ kenne. Im Regressionskontext ist dies häufig, die mittlere quadratische Abweichung (residual sum of squares, RSS).
+Gehen wir davon aus, dass wir $n$ Beobachtungen ($=$ Datenpunkte $\neq$ Zufallsvariable) $x_i=[x^1,x^2,\ldots,x^p]$ und zugehörige Werte $y_i$ haben.((Die Kleinbuchstaben für die Variablen bezeichnen Datenpunkte; die **Super**skripte beim Vektor $x_i$ sind eigentlich **Sub**skripte: Ein Datenpunkt $x_i$ ist ein Vektor bestehend aus den Werte $x_1,\ldots, x_p$. Konvention ist aber, die Indizierung, $i$, tiefgesetzt zu schreiben.))
+Man definiert dann
+\[
+\text{RSS}(f)=\sum_{i=1}^n (f(x_i)-y_i)^2.
+\]
+Im einfachsten Fall suchen wir ein lineares $f$: Gehen wir von $x_i=[x^1]$ aus und einer linearen Funktion aus. Damit setzten wir voraus, dass $Y_i=\alpha+\beta X_i+\varepsilon_i$ ist. $\varepsilon_i$ ist dabei ein Fehlerterm, der die Ungenauigkeit des Modells <<auffängt>>. Man nennt entsprechend $y_i-(\alpha+\beta x_i)$ auch das **Residuum** eines Datenpaares $(x_i,y_i)$.
+Hat man die bekannten Grössen $x_i$ so kann man die Vorhersage $f(x_i)=\hat y_i$ berechnen (predicted value; prediction). Das Residuum ist dann einfach $\hat y_i-y_i$.
+==== Aufgaben ====
+=== Einstiegsfragen ===
+  - Welches sind Klassifizierungsaufgaben bei Clearview? Was ist der Feature Space? Was ist $|\mathcal{Y}|$?
+  - Welches sind Klassifzierungsaufgaben beim Slaugherbots? Wie viele Elemente hat die Menge $\mathcal Y$?
+=== Regression ===
+Verwende für die nachfolgenden Aufgaben den folgenden Datensatz {{kurse:efcomputergrafik:cardata.zip|Auto Daten}}. Schaue dir zuerst den Datensatz in einem Texteditor an, die Datei ''fields.txt'' enthält die Spaltennamen. Verwende für Aufgabe 1 als **abhängige** Variable $y$ die gefahrenen Kilometern, als **unabhängige** Grösse $X$ das Alter. Verwende für die multivariate Regression als **abhängige** Variable den Preis und wähle dir mehr als eine unabhängige Variablen.
+== Univariate Lineare Regression ==
+  - Setze ein Modell $y_i=f(x_i)=\beta x_i+\epsilon_i$ voraus, $y_i$ sind dabei die gefahrenen Kilometer und $x_i$ das Alter in Tagen. Bestimme $\beta$ so, dass $\sum_{i=1}^{n}(y_i-\beta x_i)^2=\text{RSS}(f)$ minimal ist, das heisst, leite eine Formel für $\beta$ her.
+  - Berechne $\beta$ in Python ohne Hilfsmittel, das heisst, lies die Daten ein und bestimme $\beta$.
+  - Verwende dann [[https://scikit-learn.org/stable/index.html|SciKit]] um ebenfalls $\beta$ zu bestimmen.
+    - Installiere zuerst scikit. Frage Ks oder eine/n der erfahrenen Programmierer/innen.
+    - Arbeite die Lösung unten Schritt für Schritt durch, falls du noch nicht klar kommst.
+  - Leite die Formel für $\alpha$ und $\beta$ im Modell $f(y_i)=\alpha+\beta x_i$ her: Das Prinzip ist dasselbe: Wir haben neu eine Funktion $f$, welche von $\alpha$ und $\beta$ abhängt, das heisst, um $\alpha$ und $\beta$ zu bestimmen, kann $f$ nach $\alpha$ und nach $\beta$ abgeleitet werden, beide gleich Null gesetzt werden und das Gleichungssystem aufgelöst werden.
+  - Berechne $\alpha$ und $\beta$ wiederum <<von Hand>> und dann in SciKit.
+  - Du hast nun ein Modell: $y=f(x)=\alpha+\beta x$. Berechne Forecasts auf {{kurse:efcomputergrafik:cardata_test_new.zip|diesem Datensatz}}. Speichere deine Forecasts im Wiki [[kurse:efcomputergrafik:forecastcompetition|Forecasts]]
+<hidden Lösung Afg.1 >
+Der Ausdruck $\sum_{i=1}^n (y_i-\beta x_i)^2$ ist eigentlich ein quadratisches Polynom in $\beta$. Die Werte $x_i$ und $y_i$ sind Zahlen und bekannt. Folglich kann man die Summe als Funktion von $\beta$ aufassen und ableiten. Leitet man dann also $f(\beta)=\sum_{i=1}^n (y_i-\beta x_i)^2$ ab, erhält man \[f'(\beta)=\sum _{i=1}^n \left(2 \beta  x_i^2-2 x_i y_i\right)=2\beta\sum_{i=1}^nx_i^2-2\sum_{i=1}^n x_iy_i.\] Die Extremalstellen dieser Funktion sind nun bei Nullstellen der Ableitung, das heisst, löst man $f'(\beta)=0$ nach $\beta$ auf, erhält man
+\[
+\beta = \frac{\sum_{i=1}^n x_iy_i}{\sum_{i=1}^nx_i^2}.
+\]
+Das ist die übliche Formel für die Regressionsgerade __ohne__ Achsenabschnitt.
+</hidden>
+<hidden Stub Afg. 2>
+<code python |  stubafg02.py>
+import csv
+path = "C:/pfad/zur/datei"
+#befehl um csv dateien zu lesen
+datalist = list(csv.reader(open(path, 'r'), delimiter=','))
+print(datalist[1])
+print(datalist[2][3])
+//schlaufe zum berechnen schreiben
+</code>
+</hidden>
+<hidden Lösung Afg. 3>
+<code python>
+import numpy as np
+from sklearn.linear_model import LinearRegression
+import matplotlib.pyplot as plt
+#daten laden
+path = "C:/pfad/zur/datei"
+data =  np.loadtxt(fname = path, delimiter = ',')
+#relevante spalten auswählen
+x = data[:,8]
+y = data[:,7]
+#zähler und nenner definieren
+num = 0.0
+den = 0.0
+for i in range(len(x)):
+    num += y[i]*x[i]
+    den +=  x[i]*x[i]
+beta=num/den
+print(beta)
+#etwas weniger händisch
+print(np.dot(x,y)/np.dot(x,x))
+# mit scikit tools
+#zuerst in einen echten mehrdimensionalen nx1-Array verwandenln
+xb = x.reshape(-1,1)
+#Ohne Achsenabschnitt
+reg = LinearRegression(fit_intercept=False).fit(xb, y)
+# alpha und beta ausgeben
+print(reg.intercept_)
+print(reg.coef_)
+#Mit Achsenabschnitt
+reg = LinearRegression(fit_intercept=True).fit(xb, y)
+# alpha und beta ausgeben
+print(reg.intercept_)
+print(reg.coef_)
+# Plot outputs
+plt.scatter(xb, y,  color='black')
+plt.plot(x, reg.predict(xb), color = "green")
+plt.xticks(())
+plt.yticks(())
+plt.show()
+</code>
+</hidden>
+<hidden Lösung Afg. 4>
+Genau wie bei der univariaten Regression, kann das Problem als Polynom in $\alpha$ und $\beta$ aufgefasst werden. Leite wir $f$ nach $\alpha$ und $\beta$ ab und setzen beides gleich $0$ und lösen nach $\alpha$ und $\beta$ auf, erhalten wir:
+\[
+\beta= \frac{\sum(x_i-\bar{x})(y_i-\bar{y})}{\sum(x_i-\bar{x})^2} \text{ und } \alpha=\bar{y}-{\beta}\bar{x}
+\]
+wobei $\bar{y}=\frac{1}{n}\sum_{i=1}^n y_i$ und $\bar{x}=\frac{1}{n}\sum_{i=1}^n x_i$ ist.
+</hidden>
+== Multivariate Lineare Regression ==
+Das Modell $y_i=\alpha+\beta x_i$ ist sehr simpel. Um gute Vorhersagen zu machen, müssen wir mehr als eine Variable haben, das heisst, wir hätten gerne ein Model $Y=\alpha+\beta_1X_1+\beta_2X_2+\cdots +\beta_pX_p$. Interpretiert man die Multiplikation $\cdot$ als Skalarprodukt, so kann dieses Modell einfach als $Y=\alpha +\beta\cdot X$ geschrieben werden. Dabei ist $\beta=[\beta_1,\ldots,\beta_p]$ und $X=[X_1,\ldots,X_p]$. Mit $\beta\cdot X=\langle \beta,X\rangle$ ist dann $Y=f(X)=\alpha +\beta\cdot X=\alpha+\beta_1X_1+\beta_2X_2+\cdots \beta_pX_p$. Genau gleich wie vorher suchen wir wieder $\alpha,\beta_1,\ldots,\beta_p$ so, dass $\text{RSS}(f)$ minimal ist, also
+\[
+\sum_{i=1}^n (y_i-\alpha-\beta_1 x_i^1-\cdots-\beta_px_i^p)^2
+\]
+soll minimal sein.
+Wenn also z.B. $p=2$ ist suchen wir also eine Ebene, welche die quadrierten Abstände der Datenpunkte von der Ebene minimiert.
+==== Tafeln ====
+{{ :kurse:efcomputergrafik:efcg_1.jpg?200 |}}
+==== Prüfung / OOP ====
+<code python | prA3.py>
+class Foo:
+    def __init__(self,a):
+        self.n = a
+    def mehr(self):
+        self.n+=1
+    def show(self):
+        print(self.n)
+a=Foo(3)
+b=Foo(5)
+a.mehr()
+b.show()
+print(b.n)
+b.mehr()
+b.show()
+print(b.n)
+a.show()
+print(a.n)
+#a.n ist analog zu reg.coef_ oder reg.intercept_
+</code>