\input format


\begin{document}


\thispagestyle{empty}

Physik Department \hfill SoSe 2006 \\
TU München \hfill Übungsblatt 6 \\
Theoretische Physik \hfill 7.7.2006 \\

\vskip 1 truecm                                                  
\centerline{\bf Übung zur theoretischen Physik neuronaler Informationsverarbeitung}
\centerline{(Prof.\ J.\ L.\ van Hemmen)}
\vskip 1 truecm




\begin{Aufgabe}{Hopfield-Modell}
  Gegeben seinen $N$ Neuronen mit Zuständen $S_i(t) \in \{+1,-1\}$ zur
  Zeit $t$ und $q$ Muster $\xi_i^\mu \in \{+1,-1\}$, wobei $1 \le i
  \le N$ und $1 \le \mu \le q$. Die Muster $\vec{\xi}^\mu =
  (\xi_1^\mu, \dots, \xi_N^\mu)$ bestehen aus unabhängigen, identisch
  verteilten Zufallszahlen mit Mittelwert 0. Das lokale Potential
  $h_i(t)$ an Neuron $i$ ist
  \begin{equation}
    h_i(t) = \sum_{j=1}^N J_{ij} S_j(t) \,.
  \end{equation}
  Der Zustand $\vec{S}$ zu Zeitschritt $t+\Delta t$ ergibt sich aus
  dem Zustand zur Zeit $t$ entsprechend der deterministischen Dynamik
  \begin{equation}
    S_i(t+\Delta t) = \sgn( h_i(t) ) \,.
    \label{eq:dyn}
  \end{equation}
  Die $q$ Muster seien zuvor bereits durch die Hebb'sche Regel
  \begin{equation}
    J_{ij} = \left\{ \begin{array}{ll} 
      \frac{1}{N} \sum_{\mu=1}^q \xi_i^\mu \xi_j^\mu & \mbox{für $i \neq j$} \\
      0 & \mbox{für $i=j$}
    \end{array}
    \right.
    \label{eq:J}
  \end{equation}
  gelernt worden. Ein derartiges Netzwerk stellt einen assoziativen
  Speicher dar, dessen Attraktoren den gespeicherten Mustern
  entsprechen.
  \begin{enumerate}
  \item Der Anfangszustand des Netzes sei ein beliebiges Muster (z.B.
    $\vec{S}(t_0)=\vec{\xi}^\nu)$. Berechnen Sie die maximal
    speicherbare Zahl der Muster $q_\mathrm{max}$ für $N \to \infty$,
    wenn zur Zeit $t_0+\Delta t$
    \begin{enumerate}
    \item die Wahrscheinlichkeit, dass ein beliebiges Neuron instabil
      ist, näherungsweise kleiner als $1\,\%$ sein soll.
    \item alle Spins mit $99\,\%$-iger Wahrscheinlichkeit richtig sein
      müssen.  \\
      Hinweis: Verwenden Sie für das Gauß'sche Fehlerintegral
      \begin{equation}
        \erf(x) = \frac{2}{\sqrt{\pi}} \int_0^x e^{-t^2} \,\mathrm{d}t
      \end{equation}
      die Abschätzung
      \begin{equation}
        \frac{2}{\sqrt{\pi}} \frac{e^{-x^2}}{x+\sqrt{x^2+2}} <
        1-\erf(x)
        \le \frac{2}{\sqrt{\pi}} \frac{e^{-x^2}}{x+\sqrt{x^2+\frac{4}{\pi}}} \,.
      \end{equation}
    \end{enumerate}
\rule[.5mm]{\textwidth}{0.1mm}\\
{\footnotesize Bitte wenden.}
\newpage 
  \item 
    \begin{enumerate}
    \item Zeigen Sie, dass
      \begin{equation}
        H(t) = - \sum_{i=1}^N |h_i(t)|
      \end{equation}
      eine Lyapunovfunktion bezüglich der oben angegebenen Dynamik mit
      beliebigen $J_{ij}$ ist.
    \item Zeigen Sie, dass bei zufällig gewählten Synapsenstärken
      $J_{ij}$ (z.B. gleichverteilt aus $[-1,1]$) die Dynamik mit
      Wahrscheinlichkeit 1 entweder zu einem Fixpunkt konvergiert oder
      zu einem $2 \Delta t$-periodischen Grenzzyklus.
    \end{enumerate}
\end{enumerate}
  
\end{Aufgabe}


\begin{Aufgabe}{Simulation eines Hopfield-Netzes}
  Berechnen Sie die zeitliche Entwicklung eines Hopfield-Netzes aus
  $N=100$ Neuronen im Computer. 
  
  Bestimmen Sie dazu zunächst $q$ Muster $\vec{\xi}^\mu$, $1 \le \mu
  \le q$, wobei die $\xi_i^\mu$ mit jeweils Wahrscheinlichkeit $1/2$
  auf $+1$ oder $-1$ gesetzt werden. Berechnen Sie dann nach
  \eqref{eq:J} die synaptischen Gewichte $J_{ij}$.
  
  Lassen Sie das Netzwerk mit allen Mustern als Anfangszustand, also
  \begin{equation}
    S_i(t_0) = \xi_i^\mu \,,
  \end{equation}
  für $\mu=1,\dots,q$, laufen. 
  
  Wieviele Muster werden korrekt "`erinnert"', sind also Fixpunkte
  unter der Dynamik \eqref{eq:dyn}?
  
  Berechnen Sie mit Ihrem Programm, welcher Prozentsatz an Mustern
  korrekt erinnert wird für $q=1, \dots, 100$.

  Steigern Sie auf $N=1000$ Neuronen und $q=10,20,30,\dots,200$!
\end{Aufgabe}


\vspace{2\parsep}

\hrulefill

\vspace{1.5\parsep}

\footnotesize Besprechung der Übungen am Freitag, den 21.7.2006 um
9.15 Uhr im Raum PH 2271 (Garching).

\vspace{1.5\parsep}

Übungsleitung: \\
Moritz Franosch, mail@Franosch.org, http://www.physik.tu-muenchen.de/lehrstuehle/T35/.

\end{document}
