\documentclass[12pt]{article}
\setlength{\textwidth}{15.5 cm}
\setlength{\textheight}{22 cm}
\setlength{\oddsidemargin}{0 mm}
\setlength{\evensidemargin}{0 mm}
\setlength{\topmargin}{10 mm}
\setlength{\headsep}{0 mm}
\setlength{\headsep}{0 mm}
\usepackage{german}
\newcommand{\rmd}{{\rm d}}
\parindent 0 pt
\begin{document}


\centerline{{\it Physik auf dem Computer II}}
\bigskip
\centerline{\bf "UBUNG 10} 
\medskip
\centerline{\it Muster-Klassifizierung}
\bigskip

{\bf L"osungen.\ }\\ 
Bitte protokollieren Sie die L"osungen schriftlich und 
geben Sie das Protokoll wieder am Ende der "Ubung ab.

\thispagestyle{empty}
\bigskip

{\bf Einf"uhrung.} \\
Ein Modellneuron habe $N$ Eing"ange (Synapsen), deren Eingangswerte $\{ x_i
\}, \quad x_i \in \{0,1 \},\quad i=0,\dots, N-1$ als Repr"asentation
eines Musters aufgefa"st werden k"onnen. 
"Uber diese Eingangswerte wird eine gewichtete Summe gebildet
\begin{equation}
  \sigma = \sum_{i=0}^{N-1} w_i x_i.
\end{equation}
Falls $\sigma$ gr"o"ser ist als ein Schwellwert $s$ aus dem Intervall
$[0\dots 1],$ dann soll der Ausgangszustand $y$ 
des Perzeptrons den Wert $1$, sonst den Wert $0$ annehmen: 
\begin{equation}
  y = \theta (\sigma - s), 
\end{equation}
wobei wir mit $\theta(x)$ die Heaviside-Funktion gekennzeichnet haben.

\bigskip

{\bf Aufgabe 1: Lernregel.}

In \verb|COMPUTERPHYSIK/BLATT10/predict.cc|, finden Sie ein
vorbereitetes Programm, in dem Sie eine Lernregel als Methode einer
Klasse \verb|Neuron| implementieren k"onnen. Das Neuron soll auf eine
logische UND-Verkn"upfung trainiert werden. Anfangs seien alle
Gewichte $w_i$ des Neurons gleich $0$, der Schwellwert $s=1$.  Wenn
Sie den Zufallszahlengenerator benutzen m"ochten, empfiehlt sich die
"Ubersetzung mittels \verb|Makefile| und \verb|gmake|.

i) Programmieren Sie die Delta-Lernregel:\\
Gibt das Perzeptron als Antwort 0, wo eine 1 erwartet wurde, so
m"ussen die Gewichte f"ur die Stellen, an denen das Muster Einsen
aufweist, erh"oht werden. Die Positionen, an denen Nullen stehen,
sollen unver"andert bleiben. Ergibt sich als Antwort f"alschlich
1, dann erfolgt die Korrektur der Gewichte mit umgekehrtem 
Vorzeichen:
\begin{equation}
 w_i' = w_i + \epsilon ( y^{\rm soll} - y^{\rm ist} ) x_i, \quad i=0 \dots N-1.
\end{equation}
Der Wert $\epsilon$ sollte in der Regel nicht gr"o\ss{}er als $1/N$
gew"ahlt werden. Testen Sie Ihr Programm mit 2 Eing"angen und den
gegebenen Eingangsmustern.

ii) Trainieren Sie das Perzeptron durch geeignete Eingangsmuster nun auf
eine UND-Verkn"upfung mit 10 Eing"angen. Geben Sie Ihre
Musterwahl in Ihrer L"osung an. Wie lauten die Gewichte, die sich f"ur
die Realisierung der UND-Verkn"upfung ergeben? In welchen Grenzen
m"ussen die Gewichte bei gleichgewichteten Eing"angen liegen?

\bigskip

{\bf Aufgabe 2: Kaffeesatzlesen} 

Das Perzeptron soll nun Eingaben von der Tastatur vorhersagen.  Schreiben
Sie dazu eine Schleife, in der von der Tastatur fortlaufend Werte
$\xi_i= 0$ oder $1$ eingelesen werden. Vergleichen Sie die
Tastatureingabe mit der Vorhersage des Perzeptrons und registrieren Sie
die Anzahl der richtigen und falschen Vorhersagen. Als Eing"ange f"ur
seine Vorhersage verwendet das Perzeptron dabei die $N=7$ vorangegangenen
Tastatureingaben. F"uhren Sie anschliessend einen Lernschritt mit der
neuen Tastatureingabe als erwartetem Ausgangssignal durch, und gehen Sie
wieder zum Anfang der Schleife. Wie hoch ist etwa die
Trefferwahrscheinlichkeit der Vorhersagen?
 

\bigskip

{\bf Aufgabe 3: ``Fouriertransformation''}

Das Perzeptron soll nun trainiert werden, eine Funktion aus zwei
"uberlagerten Cosinusschwingungen unterschiedlicher Frequenz und
Amplitude als ``"uberwiegen hochfrequent'' oder ``"uberwiegend
niederfrequent'' zu charakterisieren. Pr"asentieren Sie dem Perzeptron
als Eingangssignale ca. $N=100$ Werte der Funktion
\begin{equation}
  x_i = \theta\left( 
          \alpha \cos(\frac{2\pi i}{N}) + 
          (1-\alpha) \cos(\frac{4\pi i}{N}) + 1) \right), \quad 0 \le \alpha
          \le 1.        
\end{equation}
F"ur $\alpha<0.5$ soll das Perzeptron eine $0$ (="uberwiegend
niederfrequent) f"ur $\alpha>0.5$ eine $1$ (="uberwiegend
hochfrequent) als Antwort liefern. Beschreiben Sie Ihr
Lernverfahren. Wieviel verschiedene Werte f"ur $\alpha$ waren f"ur
das Training erforderlich? Wieviele Lernschritte wurden ben"otigt?
 
\bigskip

{\bf Aufgabe 4: XOR}~~{\it (freiwillig)}\\
Das Problem der hier untersuchten Einzelneuronen ist, da\ss{}
die Muster ``linear separierbar'' sein m"ussen. Zeigen Sie mit dem 
Beispielprogramm, da\ss{} ein Einzelneuron die XOR-Funktion nicht
erfolgreich implementieren kann. 

Benutzen Sie die Wettbewerbsregel f"ur zwei Neuronen $r$ und $s$, 
\begin{equation}
 y_r = \left\{ \begin{array}{ll} 1,~& \mbox{falls}~ 
                \sum_i w_{ri} x_i > \sum_i w_{si} x_i, \\
                                0,~& \mbox{sonst.}     
                \end{array} \right.
\end{equation}
zusammen mit der Delta-Lernregel f"ur $r$ bzw $s$,
\begin{equation}
 w_{[r,s]i}' = w_{[r,s]i} + 
        \epsilon ( y_{[r,s]}^{\rm soll} - y_{[r,s]}^{\rm ist} ) x_i, 
        \quad i=0 \dots N-1.
\end{equation}
unter der ``Erwartung'', da\ss{} Neuron $r$ den Wahrheitwert der XOR
Funktion, Neuron $s$ dagegen immer $0$ ausgibt. 
Zeigen Sie, da\ss{} dieses System die gestellte Aufgabe l"osen kann. 


\end{document}




