lehrkraefte:ks:efcomputergrafik2022 [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.

===== 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 Residuen (residuals), residual sum of squares, feature space.
  * Jede/r kennt die Begriffe Training- und Testdaten wie auch Evaluationsdaten (training set, evaluation set, test set)f]
  * Jede/r kann eine Vorhersage auf Grund von Testdaten machen unter Verwendung von Trainings- und Evaluationsdaten.
  * Jede/r kann $k$-nearest neighbour erklären und implementieren.
    * Selbst implementieren oder mit ''sklearn'' implementieren
    * Das optimale $k$ feststellen.

===== KW 21 =====

Bitte keine **gif**s zu GitHub hinzufügen: Dazu eine Datei ''.gitignore'' (Achtung:  Mit Punkt vor Dateinamen) erstellen mit der Zeile ''*.gif''
===== KW 20 =====
Neuronale Netze: Woher, wohin. {{lehrkraefte:ks:storyslides_2022_ef_inf.pdf|Slides}}

===== KW 19 =====

Weiterarbeit am Projekt, siehe auch [[lehrkraefte:ks:efcomputergrafik2022|Ziele]]. 

Bitte Mails lesen.

Zusätzliche Fragestunde: Donnerstag, 12. Mai, 12:15 im H23.

===== KW 18 =====
  * Slides: {{lehrkraefte:ks:efcomputergrafik2022:intro_2022.pdf|Geschichte Machine Learning / AI}}.
  * Padlet mit Fragen (A) und was als nächstes ansteht (B) [[https://padlet.com/simon_knaus1/qw0imwgi44rcgy65|Bitte hier]]


===== KW 17 =====
=== Ziel ===
Jede:r startet sein eigenes Projekt.

=== Auftrag === 
  - Lies den Beschrieb des Projekts durch
  - Wähle aus, was du machen möchtest. Bei Interesse können auch weitere resp. andere Daten gewählt werden.
  - Strukturiere dein Projekt in Teilziele
  - Versuche die Struktur deines Projekts auch im Code abzubilden, das heisst, defiere Zwischenschritte, Funktionen, o.ä. welche deinen Code lesbar und übersichtlich machen. 
    * Definere bereits Funktionen ohne diese bereits Zeile für Zeile definier zu haben, das heisst, definiere, welche Argumente sie hat und was die Rückgabewerte sind
    * Definiere wie du Zwischenschritte überprüfen kannst.
  - Besprich die Punkte 3 und 4 mit Ks

==== Projekt =====

Jede:r <<führt>> eine Klassifikationproblem <<durch>>. Dabei sollen folgende Punkte berücksichtigt werden:
  * Trainingsdaten und Evaluationsdaten werden verwendet.
  * Auf den Evaluationsdaten wird die Güte der Klassifikation wie auch die Konfusionsmatrix ausgewiesen.
  * Hat der Klassifikationsalgorithmus einen **Hyperparameter** (oder **Tuningparameter**, wie Baumtiefe oder Anzahl Nachbarn) wird der optimale Hyperparameter ebenfalls auf dem Evaluationsset  bestimmt.
  * Es können bekannte Algorithmen ($k$ nearest neighbor, trees) oder eigene Algorithmen (<<averaging>>) verwendet werden. 
  * Es können die Daten der BU, die Bilddateien des Unterrichts o.ä. verwendet werden.

Abzugeben ist ein Markdown-Dokument mit
  * kurzem Beschrieb, welches Problem gelöst worden ist.
  * den wichtigsten Code-Zeilen in Markdown mit ggf. Erklärungen.
  * einem sinnvollen Bild als Illustration.
  * der Antwort auf die Frage <<Was wäre ich froh gewesen, hätte ich schon vorm Projektende gewusst>> (<<I wish I had known before>>).
Das ganze ist in einer mit Code und Daten als lauffähiges Programm in [[https://github.com/monsieurknos/efmachinelearning]] in einem Ordner mit Bezeichnung ''Nachname'' abzulegen.

Relevant für die Bewertung sind:
  * Eigenleistung (eigene Implementation wird höher bewertet)
  * Korrektheit des Codes
  * Kommentare und Struktur des Codes
  * Saubere Darstellung im Markdown-Dokument.

===== KW14 =====
Jede:r implementiert $k$-nearest neighbors für ein $p$-dimensionales Problem. Die $p$ Dimensionen können 
  * die Features der Buchstaben aus der BU sein oder
  * die Pixelfarben in Graufstufen des MNIST-Datensatzes
sein. 
{{ :lehrkraefte:ks:img_20220405_151107541.jpg?400 |}}
Für beide Probleme ist es **zentral**, dass alle Features normiert werden, dass heisst, die Werte der Features werden so skaliert und verschoben, dass sie auf das Intervall $[-1,1]$ zu liegen kommen.

=== Hinweise Features BU ===
Der Datensatz kann aus der BU von git [[https://github.com/ivo-bloechliger/kaien/tree/main/data|übernommen]] werden.

=== Hinweise MNIST Datensatz ===
Der MNIST-Ziffern-Datensatz ist ein <<Standarddatensatz>> in der Machinelearning-Community. Wir arbeiten deswegen auch mit diesem. Standardmässig sind die Ziffern als Bilddateien verfügbar.
{{ :lehrkraefte:ks:efcomputergrafik2022:illustraiton.png?100 |}}
Zwischenschritte: 
  * ZIP-Code Problematik verstehen: ZIP-Code -> Ziffer -> 16x16 Bild -> Liste mit 256 Graustufen-Werten -> kNN in $\mathbb{R}^{256}$.
  * Die Idee sollte sein, das Problem resp. Programm in zwei Teile zu strukturieren
    * Einlesen der Bilddateien und generieren der Liste resp. CSV-Datei
    * Verwenden von $k$ nearest neighbors wie gehabt auf Grund einer erstellten Liste resp. CSV-Datei.
  * Einzelne Ziffern als {{lehrkraefte:ks:efcomputergrafik2022:knn_rk_trainingsdaten.zip|Bilddateien als ZIP}} einlesen und als 256 Zahlwerte pro Bild als Liste speichern:
    * Eine Funktion schreiben, die als Argument einen Dateinamen hat und als Rückgabewert eine Liste mit 256 Elementen.
    * Diese Funktion auf alle Dateien anwenden (siehe unten) und die Ziffer aus dem Dateinamen in eine Liste von Liste mit 256+1 (Farbwerte+Ziffer) Elementen speichern.

== Code Hinweise ==
  * **Konvertierung der Bild-Dateien zu Zahlwerten**
    * Bilder können in mit ''skimage'' mit [[https://scikit-image.org/docs/dev/api/skimage.io#skimage.io.imread|imread]] eingelesen werden. Stelle sicher, dass du die Funktion resp. Dokumentation der Funktion verstehst.
    * Verzeichnisse können mit os.listdir() durchlaufen werden: <file python listdir.py>import os
for filename in os.listdir("C:/temp/"):
    print(filename)

</file>
    * Mit ''filename.split('_', 3)'' kann der String "filename" aufgeteilt ([[https://www.programiz.com/python-programming/methods/string/split|"gesplitted"]]) werden, die 3 steht dabei für das Dritte Element nach dem Split in der Liste und entspricht der Ziffer.
    * Die Graustufenwerte von 0 bis 255 sollten auf Werte zwischen -1 und 1 "umgelegt" werden.    
    * Ziel ist eine Liste mit 256 + 1 Einträgen pro Bilddatei. Diese Liste könnte dann wieder als [[https://de.wikipedia.org/wiki/CSV_(Dateiformat)|CSV]] Datei gespeichert werden. 
    * Speicherung als CSV passiert am einfachsten über CSV schreiben: <file python writecsv.py>import csv
    *  outcsv = open("C:/temp/outfile.csv", 'a'); 

# CSV-writer konfigurieren.
writer = csv.writer(outcsv, delimiter=',', lineterminator='\n')

for item in datalist:
    #Jeden Eintrag der Datalist als Zeile ausgeben
    writer.writerow([item[0], item[1], item[2]])

# Wrtier schliessen
outcsv.close()
 </file>
=== Lösungen ===
<hidden Liste von Bilddateien>
<code python pixelist_from_directory.py>

import os  #um Verzeichnisse zu listen
import skimage.io #um Bilder einzulesen           

# Pfad zu den Bilddateien
digitsdirectory = 'C:/temp/knn_rk_trainingsdaten/'


def getPixeListFromFilePath(filepath):
    img = skimage.io.imread(fname=filepath)
    w = img.shape[0]
    h = img.shape[1]
    pixellist = []
    for y in range(h):
        for x in range(w):

            # color is ein Objekt mit verschiedenen Attributen, u.a. red, green, blue.
            # bei grau sind rot=gruen=blau, d.h., eine Farbe auslesen reicht.
            # siehe auch https://docs.oracle.com/javase/7/docs/api/java/awt/Color.html
            color = img[y][x]
            # umlegen auf das Intervall [-1,1] zwecks Normalisierung
            value = (color/255) * 2 - 1
            # an liste anhaengen
            pixellist.append(value)
            
    return pixellist

def getDigitFromFileName(filename):
    return int(filename.split('_', 3)[2])


# leere Liste fuer alle Trainingsdaten der Form [-0.93,0.331,....,0.99,3]

trainingset = []

# durch alle files im Ziffernverzeichnis loopen
for filename in [filename for filename in os.listdir(digitsdirectory) if filename.endswith("gif")]:

    # Ziffer auslesen
    currdigit = getDigitFromFileName(filename)

    # Pixelliste von Datei auslesen
    currpixellist = getPixeListFromFilePath(digitsdirectory + filename)

    # Der Pixelliste die Ziffer anhaengen
    currpixellist.append(currdigit)

    # Gesamte Liste dem trainingsset anhaengen.
    trainingset.append(currpixellist)

# Das Trainingsset kann jetzt verwendet werden
# print(trainingset)


</code>
</hidden>


===== KW13 =====
=== Aufträge ===
Jede:r implementiert $k$-nearest neighbors für ein zwei-dimensionales Problem (s.u.) und dokumentiert den Algorithmus in Markdown mit diesen {{lehrkraefte:ks:pointdata.zip|Daten}}.

=== Markdown ===
  * {{lehrkraefte:ks:efcomputergrafik2022:markdown-cheat-sheet.zip|Beispieldokument}}: Achtung, zuerst entzippen. ''.md'' ist die Markdown-Datei.
  * [[https://pandoc.org/|Pandoc]] (GPL Licence) 
  * [[https://dillinger.io/|Dillinger]] (MIT Licence)

=== $k$-nearest neighbours ===
Bei $k$ nearest neighbours (kNN) geht es darum, einem dazukommenden Punkt diese Klasse zuzuweisen, welche die nächsten $k$-Punkte mehrheitlich haben. 
Der Trainingsdatensatz sind damit alle Punkte, von welchem man die Klasse und Koordinaten kennt. Auf Grund dieser Klassen und Koordinaten wird einem neuen Datenpunkt einzig auf Grund der Koordinaten eine Klasse zugeordnet.
{{ :lehrkraefte:ks:sctructure.png?400 |}}

=== Ziel ===
Den $k$-nearest-neighbour Algorithmus in $\mathbb{R}^2$ implementieren.

=== Wichtige Zutaten: Basic Python ===
  * [[https://tobiaskohn.ch/files/PythonCheatSheet.pdf|Cheat Sheet]]
  * Liste mit Klassen und Distanzen, i.e. ''%%[[1,0.033131],[0,0.123131],[1,0.123124141],[0,1.2123141]]%%''
  * Sortieren dieser Liste um die $k$ nächsten Nachbarn resp. deren Klasse zu bestimmen:
    * Sortieren von Listen kann mit Python mit [[https://www.programiz.com/python-programming/methods/built-in/sorted|sorted]] gelöst werden. Speziell für unseren Fall ist "Example 3" spannend.
    * Auf Grund der sortierted Liste kann die Mehrheitsmeinung der $k$ nächsten Nachbarn bestimmt werden

Empfehlung: Mindestens zwei Funktionen definieren. Eine zur Berechnugn der Distanz-Klassen-Liste, eine zur Zuweisung der Klasse (0 oder 1).

=== Wichtige Zutaten: Numpy ===
Mit ''numpy'' kann das ganze sehr effizient gelöst werden (siehe z.B. auch CheatSheet für <<slicing>>, oben rechts: [[https://assets.datacamp.com/blog_assets/Numpy_Python_Cheat_Sheet.pdf|CheatSheet]])
  * Sind ''a'' und ''b'' numpy-Vektoren, kann die Distanz (elementweise) als ''%%((a-x)**2+(b-y)**2)**0.5%% '' berechnet werden.
  * [[https://numpy.org/doc/stable/reference/generated/numpy.argsort.html|argsort]]
  * [[https://numpy.org/doc/stable/reference/generated/numpy.bincount.html|bincount]]
Einen zweidimensionalen Array mit ''numpy'' erstellen: Die Distanzen können vektoriell berechnet werden. Dann mit [[https://numpy.org/doc/stable/reference/generated/numpy.argsort.html|argsort]] den Array umbauen, um dann mit [[https://numpy.org/doc/stable/reference/generated/numpy.bincount.html|bincount]] die Mehrheitsmeinung festzustellen.


<hidden Lösung>
<file python knn_numpy_frei.py>
import csv  # um Text-Dateien im CSV-Format zu lesen
 
# CSV-File oefffnen
 
csvfile = open('C:/temp/data.csv', 'r')
 
# CSV-File einlesen.
 
reader = csv.reader(csvfile, delimiter=',',
                    quoting=csv.QUOTE_NONNUMERIC)
 
# CSV-File in Liste umwandeln
 
data = list(reader)
</file>

<file python knn.py>
import random
import numpy as np
import matplotlib.pyplot as plt
from math import sqrt
# CSV-File oefffnen

csvfile = '../data/pointdata.csv'

# CSV-File einlesen.

data = np.loadtxt(csvfile, delimiter=',')

plt.scatter(data[data[:,2]==1,0], data[data[:,2]==1,1], s=10)
plt.scatter(data[data[:,2]==0,0], data[data[:,2]==0,1], s=10,c="#ff33ff")
</file>
</hidden>


===== KW 10 =====
==== 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}]^T.
\]
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]^T$. Damit ist z.B. die Richtung der stärksten Zunahme an der Stelle $[3,-3]^T$ 
$[2\cdot 3-4,\;2\cdot(-3)+2]^T=[2,-4]^T$.

Möchte man jetzt das Minimum numerisch finden, kann man vom Startpunkt $[3,-3]^T$ 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]^T$
  - $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 Gradient Descent ====
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}} oder als [[https://www.geogebra.org/m/bmdgxbnz|Link]] 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.

===== KW 8 =====
==== Ziele ====
  * Jede:r hat funktionierenden Code für das einfache Regressionsproblem (<<welches ist die beste Variable um den Preis vorherzusagen?>>)
  * Jede:r bearbeitet ein weiteres Problemfeld von Regressionsproblem: Optimierung (<<gradient descent>>) oder multivariate lineare Regression.
==== Aufräge ====
  * Eigenen, bisherigen, Code abschliessen.
  * Theorie zu multivariater Regression oder Gradient Descent durcharbeiten und 

==== 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}^{T}\mathbf{X} )^{-1}\mathbf {X}^{T} \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).
== Manuell ==
In NumPy können //transpose// und //inverse// verwendet werden: [[https://numpy.org/doc/stable/reference/generated/numpy.transpose.html|Transpose]] und [[https://numpy.org/doc/stable/reference/generated/numpy.linalg.inv.html?highlight=inverse|Inverse]]. Matrizenmultiplikation erfolgt mit [[https://numpy.org/doc/stable/reference/generated/numpy.matmul.html|Matmul]]. 

== SciKit ==
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 multivariate Regression ====
  * Finde ein Modell mit drei oder mehr vorhersagenden Variablen, welche den Preis von diesen Autos am besten vorhersagen. Gehe dabei wie folgt vor:
    * Suche eine Variable, welche den Preis am besten erklärt (bereits gemacht)
    * Finde eine nächste Variable, welche zusammen mit der gefundenen Variable den Preis am besten erklärt.
Diese Method nennt man auch //forward selection// um eine optimale Teilmenge (//best subset//) zu finden. 


==== KW 7 ====
=== Ziele ===
Das Ziel dieser Sitzung ist es, ein eigenes Modell zu <<trainieren>>. In diesem Kontext heisst trainieren, das richtige Feature ($x$; Prädiktor) resp. die richtigen Features auszuwählen, um eine Vorhersage für den Preis zu machen.
  * Einen Datensatz in Trainings- und Evaluationsdaten zu unterteilen mit ''numpy''
  * Die Modelvorhersagen zu berechnen wie auch die Vorhersagen aus dem sklearn ''regression''-Objekt zu erhalten um dann die mittlere RSS zu berechnen.


Die abschliessende Vorhersage passiert auf den {{lehrkraefte:ks:efcomputergrafik2022:cardata_test.zip|Testdaten}}, das heisst, Daten ohne das Attribut <<Preis>>. Die Schritte dazu sind in den nachfolgenden Aufträgen festgehalten:
=== Aufträge ===
  * Schreibe deinen Code so, dass du ein <<evalaution set>> und ein <<training set>> hast. Wähle die Daten als Teil deiner ursprünglichhen Daten, siehe Beispiel unten.
    * Für ''numpy''-Neulinge: Arbeite den Code unten durch und erkläre deinem/deiner Nachbar:in, was die Code-Zeilen bewirken. Lies dir das [[https://assets.datacamp.com/blog_assets/Numpy_Python_Cheat_Sheet.pdf|CheatSheet]] durch.
    * Die Variable ''data'' sind die Daten vom letzten Mal. Mit den unterschiedlichen Spalten, hast du unterschiedliche //features//, mit den unterschiedlichen Zeilen unterschiedliche //Beobachtungen//; eine Teilmenge der Beobachtungen bildet das //trainings set//, die verbleibenden Beobachtungen bilden das //evaluation set//.

  * Vergleiche die mittleren Quadratische-Abweichungen deiner Modelle ($\frac 1n \sum_{i=1}^n (y_i-\hat y_i)^2)$. Verwende dazu das //evaluation set//. 
    * Bis jetzt sind deine Vorhersagen manuell auf Grund von $y=mx+q$ enstanden. Versuche die Methoden ''predict'' des Regression-Objekts von ''sklearn'' zu verwenden und vergleiche deine Forecasts $y=mx+q$ mit den Regression-Forecasts.
  * Wähle dann dein bestes Modell (mit einem oder mehreren Prädiktoren aus dem feature space) und mache die Vorhersagen für die {{lehrkraefte:ks:efcomputergrafik2022:cardata_test.zip|Testdaten}}.

=== Code Bits ===
<hidden numpy starter> <code Python  |  numpy_starter.py>
import numpy as np
olist = [x for x in range(5)]
nlist = [ [x+5*y for x in range(5)] for y in range(7)]
data = np.asarray(nlist)
print(data)
print(data[0,2])
print(data[:,3])
print(data[1:2,:])
print(data[1:3,:])
# Zufällig Daten auswählen (mit Zurücklegen)
indices = np.random.randint(0,7,3)
print(indices)
newdata = data[indices,2]
print(newdata)

# Zufällig Daten auswählen (ohne Zurücklegen)
indices = np.random.choice([x for x in range(7)],3,False)
print(indices)
newdata = data[indices,2]
print(newdata)
</code></hidden>

<hidden Trainings und Evaluationsdaten>
<code Python | setdiff.py>
# a und b sind dann indices; a alle Beobachtungen, b das Evaluation set
a = np.array([1, 2, 3, 2, 4, 1])
b = np.array([3, 5, 6])
print(np.setdiff1d(a, b))
</code></hidden>

<hidden Forecasts manuell und aus sklearn>
<code Python | forecasts.py>
reg = LinearRegression(fit_intercept=True).fit(xb, y)
# alpha und beta ausgeben
q = reg.intercept_
m = reg.coef_
y1 = reg.predict(xb)
y2 = m*x+q
print(y1)
print(y2)
sum((y1-y)**2)
sum((y2-y)**2)
</code>
=== Lösung ===

<code python | kw7.py>
import numpy as np
from sklearn.linear_model import LinearRegression
from math import floor
import matplotlib.pyplot as plt

#daten laden
path = "C:/temp/cardata.csv"

data =  np.loadtxt(fname = path, delimiter = ',')
rows, cols = data.shape

allindices = np.asarray([x for x in range(rows)])
# training / evaluation 
training = np.random.choice(rows,floor(0.25*rows))
evaluation = np.setdiff1d(allindices,training)

# trainingsdaten
# data[training,:]



def getSquaredError(xtrain,ytrain,xeval,yeval):
    reg = LinearRegression(fit_intercept=True).fit(xtrain, ytrain)
    ypred = reg.predict(xeval) # äquivalent zu a*x+b
    # von Hand
    # ypred2 = reg.coef_*xeval+reg.intercept_
    # ypred und ypred2 sind identisch; a*x+b; a=reg.coef_, b=reg.intercept_
    RSS = sum((ypred-yeval)**2)
    return (RSS/ypred.size)

## example
print(getSquaredError(data[training,8:9],data[training,7:8],data[evaluation,8:9],data[evaluation,7:8]))

results = [0]*cols

for i in range(cols):
    if i==7:
       results[i]  = float('inf')
       continue
    results[i] = float(getSquaredError(data[training,i:(i+1)],data[training,7:8],data[evaluation,i:(i+1)],data[evaluation,7:8]))

# Vergleiche Resultate
print(results)
# Vergleiche Resultate as log
print(np.log(results))

minval = results[0]
minindex = 0
for i in range(1, len(results)):
    if(results[i] < minval):
        minindex = i
        minval = results[i]

print(minval)
print(minindex) 
#automaisch      
print(np.amin(np.array(results,dtype=object)))       
</code>

==== KW 6 ====

=== Aufgaben ===
  * Aufgaben vom letzten Mal abschliessen, insbesondere 'scikit-learn' in Anaconda installieren und Aufgabe 3 erarbeiten
  * Merkmal auswählen, welches die Preise am besten vorhersagt, dazu
    * eine Funktion schreiben, welche auf Grund von zwei Listen die Summe der quadrierten Residuen berechnet
    * die verschiedenen Merkmale auf den Evaluationsdaten austesten und dann auswählen
  * Einen Forecast mit den Testdaten machen und diesen bereithalten.

=== Theorie ===
Auf der Suche nach einem optimalem $f$ müssen verschiedene Dinge berücksichtigt werden, so muss z.B. $f$ schnell und gut zu berechnen sein und es sollte auch auf //ungesehenen Daten// gut funktionieren. Würde dieses letzte Kriterium wegfallen, könnte man ja einfach jedem Vektor $x$ den bekannten $y$ Wert zuordnen. 

Die //ultimative// Überprüfung einer Funktion $f$ erfolgt mit einem sogenannten Testdaten, das heisst, Daten, welchen die bekannte Grösse $y$ entfernt wurde und erst zu einem späteren Zeitpunkt zur Verfügung gestellt werden. Damit wird sichergestellt, dass kein sogenanntes //data snooping// betrieben wird. 

Wird die Funktion $f$ auf eine Weise erstellt, welche noch zusätzliche Entscheidungen oder Anpassungen erfordert, kannes auch vorkommen, dass man sich selbst, die Trainingsdaten aufteilt, bei einem Teil der Daten die abhängige Grösse zwischenzeitlich entfernt um dann diese als fiktive Testdaten zu verwenden.


**Reminder:** In unserem Kontext ist eine Funktion irgendeine Zuordnung, welch einem Element aus $X$ ein Element aus $Y$ zuordnet. In extremis könnte das auch eine sehr lange Liste sein, welche jedem Element aus $X$ ein Element aus $Y$ zuordnet. Die Funktion muss nicht zwingend als mathematischer Audruck (<<Funktionsgleichung>>) daherkommen.
{{ :lehrkraefte:ks:theorie2.jpg?nolink&400 |}}

=== Packages installieren ===
Zusätzliche Packgages werden am besten mit ''pip'' (**p**ackage **i**nstaller for **p**ython) installiert. Dazu im Prompt 
  * ''pip install sklearn'' für scikit-learn
  * ''pip install numpy'' für numpy, welches einen effizienten Umgang mit strukturierten Daten ermöglicht
eingeben.

{{ :lehrkraefte:ks:efcomputergrafik2022:first.jpg?400 |}}

{{ :lehrkraefte:ks:efcomputergrafik2022:second.jpg?400 |}}


==== KW 5 ====
=== Einführung ===
  * Vorstellung
  * Kenntniserhebung
    * Python
    * Pythonumgebung
    * Mathematik: Stochastik, Erwartungswert, Regression
  * Einstieg
    * Clearview
      * [[https://www.youtube.com/watch?v=-JkBM8n8ixI| Interview and Demo w/ ClearView CEO]]
      * [[https://www.heise.de/news/Gesichtserkennung-Clearview-soll-Datenbrille-fuers-US-Militaer-entwickeln-6351132.html| heise online News zu ClearView]] und in der [[https://www.derbund.ch/zuercher-stadtpolizist-testete-clearview-nach-einer-ausbildung-696840503794|Schweiz]] bei der StaPo Zürich.
      * [[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
  * $k$-nearest-neighbours als erste echte nicht-lineare Variante
  * Neuronale Netze  (evtl.)

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_i^1,x_i^2,\ldots,x_i^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_i^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$.
{{ :lehrkraefte:ks:efcomputergrafik2022:tafeln:tafel_20220208.jpg?600 |{{ :lehrkraefte:ks:efcomputergrafik2022:tafeln:tafel_20220208.jpg?nolink&400 |}}
=== 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 {{lehrkraefte:ks:efcomputergrafik2022: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 {{lehrkraefte:ks:efcomputergrafik2022:cardata_test.zip|diesem Datensatz}}. Speichere deine Forecasts im Wiki [[lehrkraefte:ks:efcomputergrafik2022|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.

==== Ressourcen ====
  * [[https://numpy.org/doc/stable/reference/|NumPy-Dokumentation]]
  * [[https://scikit-learn.org/stable/modules/generated/sklearn.linear_model.LinearRegression.html#sklearn.linear_model.LinearRegression|SciKit Lineare Regression]]
  * [[https://scikit-learn.org/stable|SciKit]]