The Art of Memory Loss

and the Art of Memory Loss and [...]

by Dominic Zimmer

“Die Kunst des Gedächtnisverlustes beschäftigt sich damit, trotz großer Vergesslichkeit auf lange Sicht stets die Richtigen Antworten zu wissen.”

— Irgendjemand, Saarbrücken 2023

Frösche, Wetter und Wetterfrösche

Frösche

• ein Frosch sitzt auf einer von zwei Seerosen $S = \{l, r\}$
• mit $p$ hüpft er von $l$ nach $r$
• mit $q$ hüpft er von $r$ nach $l$
• mit $1-p$ bzw $1-q$ bleibt er sitzen
• er beginnt auf $s_0 = l$

Wie oft ist der Frosch im Schnitt in $l$, wie oft in $r$?

Frösche Simulieren

import numpy as np
uniform = np.random.random # Zufall in [0, 1]
# Kein numpy? -> from random import random as uniform

p = 0.6 # von l nach r
q = 0.2 # von r nach l
N = 1_000_000 # Simulationen

# Los geht's!

visits = [0, 0]
cur = 0
for i in range(N):
    if cur == 0:
        if uniform() < p:
            cur = 1
            visits[1] += 1
        else:
            visits[0] += 1
    elif cur == 1:
        if uniform() < q:
            cur = 0
            visits[0] += 1
        else:
            visits[1] += 1
n = sum(visits)
print(f"{n}/{N}")
print(f"  {visits[0]/n:.4f} of the time at 0 ({visits[0]} total)")
print(f"  {visits[1]/n:.4f} of the time at 1 ({visits[1]} total)")

1000000/1000000
  0.2501 of the time at 0 (250098 total)
  0.7499 of the time at 1 (749902 total)

Warum ist der Frosch im Schnitt 25% in $l$ und 75% in $r$?

Frösche Analysieren

Die Wahrscheinlichkeiten für Wechsel sind $P(l \to r) = p$ und $P(r \to l) = q$

Wie können wir $P(\text{Frosch links})$ für große $t$ vorraussagen?

$t$	$P(\text{ Frosch links zu }t)$	$P(\text{ Frosch rechts zu }t)$
$0$	$1$	$0$
$1$	$1-p$	$p$
$2$	$(1-p)^2 + pq$	$p(1-p) + p(1-q)$

Frösche Analysieren

Unser Experiment zeigt für große $t$: $$ P_{t-2}(\text{Frosch links}) \approx P_{t-1}(\text{Frosch links}) \approx P_{t}(\text{Frosch links}) \approx \dots L $$

$$ \begin{align*} L &= L \cdot P(l \to l) + R \cdot P(r \to l)\\ R &= R \cdot P(r \to r) + L \cdot P(l \to r)\\ 1 &= L + R \end{align*} $$

$$ \begin{align*} L &= \frac{q}{p+q} = 25\% \\ R &= \frac{p}{p+q} = 75\% \end{align*} $$

Mathematik und Gedächtnisverlust

Definition (Gedächtnislosigkeit)

Ein Prozess ist gedächtnislos, wenn zu jedem Zeitpunkt seine Entscheidung nur vom aktuellen Zustand abhängt, nicht aber von dem Weg, wie der aktuelle Zustand erreicht wurde.

Beobachtung

Das Verhalten der Frösche ist gedächtnislos. Die Aktionen des Frosches und deren Wahrscheinlichkeiten $p$ und $1-p$ (bzw $q$ und $1-q$) hängen nur von der aktuellen Seerose ab.

Frösche — Formell

Der Frosch kann auf der linken oder rechten Seerose sitzen.

Wir modellieren die beiden Seerosen als die zwei Zustände $S = \{L, R\}$.

Zufällig hüpft er zwischen den Seerosen hin und her

Die Zufallsvariable $X_t$ beschreibt wo der Frosch zum Zeitpunkt $t$ ist.

Wir könnten zum Beispiel beobachten, dass

$$ \dots \quad X_3 = L \quad X_4 = L \quad X_5 = R \quad X_6 = L \quad \dots $$

Am Anfang sitzt der Frosch auf der linken Seerose.

Die Wahrscheinlichkeit $P(X_0 = L) = 1$.

Analog ergibt sich $P(X_0 = R) = 0$.

Der Frosch hüpft mit Wahrscheinlichkeit $p$ von links nach rechts

Die Übergangswahrscheinlichkeit, dass der Frosch zum Zeitpunkt $t-1$ in $L$, und zum Zeitpunkt $t$ in $R$ ist, ist $p$.

$$ \begin{align*} &\phantom{==}\color{gray}{P(X_t = R \mid X_{t-1} = L, X_{t-2} = L)}\\ &=\color{gray}{P(X_t = R \mid X_{t-1} = L, X_{t-2} = R)}\\ &= P(X_t = R \mid X_{t-1} = L) \\&= p \end{align*} $$

Da die Übergangswahrscheinlichkeiten von Zeitpunkt $t$ zu Zeitpunkt $t+1$ nur von $X_t$ abhängen, schreiben wir kurzerhand

$$ P(X_{t+1} = R | X_{t} = L) = P(L \to R) = m_{L R} $$

Wir können alle Übergangswahrscheinlichkeiten $P(s \to s')$ als Matrix $M$ notieren:

$$ M = \begin{pmatrix} m_{LL} & m_{LR} \\ m_{RL} & m_{RR} \end{pmatrix} = \begin{pmatrix} 1 - p & p \\ q & 1-q \end{pmatrix} $$

Wir schreiben die Wahrscheinlichkeiten, dass der Frosch zum Zeitpunkt $t$ in $L$ oder $R$ ist, als Vektoren.

$$ X_0 = \begin{pmatrix}1 & 0\end{pmatrix} $$

Ein Zeitschritt $t=0 \to t=1$ verändert die Verteilung gemäß $M$:

$$ X_0 = \begin{pmatrix}1 & 0\end{pmatrix} \to \begin{pmatrix}1-p & p \end{pmatrix} = X_1 $$

Aus einem gegebenen

$$ X_0 = \begin{pmatrix}1 & 0 \end{pmatrix} $$

können wir das Vektor-Matrix-Produkt

$$ \begin{align*} X_1 &= X_0 \cdot M \\ &= \begin{pmatrix} 1 & 0 \end{pmatrix}\cdot{}\begin{pmatrix}1-p & p \\q & 1-q\end{pmatrix} = \begin{pmatrix}1-p & p \end{pmatrix} \end{align*} $$

ausrechnen.

Matrixmultiplikation rechnet "Zeile mal Spalte"

$$ \begin{align*} & X_0 \cdot M \\ &= \begin{pmatrix} 1 & 0 \end{pmatrix} \cdot{} \begin{pmatrix} \color{green}{1 - p} & \color{orange}{p} \\ \color{green}{q} & \color{orange}{1-q} \end{pmatrix} \\ &= \begin{pmatrix} \begin{pmatrix} 1 & 0 \end{pmatrix}\bullet{}\begin{pmatrix} \color{green}{1 - p} \\ \color{green}{q}\end{pmatrix} & \begin{pmatrix} 1 & 0 \end{pmatrix}\bullet{}\begin{pmatrix} \color{orange}{p} \\ \color{orange}{1-q} \end{pmatrix} \end{pmatrix}\\ &= \begin{pmatrix} \color{green}{1 - p}& \color{orange}{p} \end{pmatrix} \end{align*} $$

Die Einträge von $X_1 = X_0 \cdot M$ errechnen sich genau so, wie die Folgezustände $L'$ und $R'$ aus $L$ und $R$.

Wetterfrösche

In Froschland ändert sich das Wetter jeden Tag. Es gibt Sonnenschein, Regen und bewölkte Tage.

Je nach heutigem Wetter variiert die Wahrscheinlichkeit für das morgige Wetter:

• 30% der Tage verschlechtert sich das Wetter $S \to B \to R$
• 30% der Tage bleibt es nach wolkigen Tagen wolkig
• 10% der Tage schwingt das Wetter extrem um
• 40% der Tage regnet es nach Regen weiter

1. Zeichne den Graphen und stelle die Übergangsmatrix $M$ auf
2. Implementiere das Froschwetter in python
3. Was ist das erwartete Wetter 14 Tage nach Regen, Wolken oder Sonne?

Die Übergangsmatrix des Froschwetters

$$ \begin{align*} M = \frac{1}{10} \begin{pmatrix}6 & 3 & 1 \\ 4 & 3 & 3 \\ 1 & 5 & 4 \end{pmatrix} = \begin{pmatrix}0.6 & 0.3 & 0.1 \\ 0.4 & 0.3 & 0.3 \\ 0.1 & 0.5 & 0.4 \end{pmatrix} \end{align*} $$

Wenn heute die Sonne scheint $X_0 = \begin{pmatrix}1 & 0 & 0 \end{pmatrix}$, ist die Wettervorschau für morgen $X_0 \cdot M$, bzw für in zwei Wochen $X_{14} = X_0 \cdot M \cdot \dots M = X_0 \cdot M^{14}$.

Matrixmultiplikation

$$ \begin{align*} X_1 &= \begin{pmatrix}1 & 0 & 0\end{pmatrix} \cdot \begin{pmatrix}0.6 & 0.3 & 0.1 \\ 0.4 & 0.3 & 0.3 \\ 0.1 & 0.5 & 0.4 \end{pmatrix} \\ &= \begin{pmatrix} \begin{pmatrix}1 & 0 & 0\end{pmatrix}\bullet \begin{pmatrix} 0.6 \\ 0.4 \\ 0.1 \end{pmatrix} & \begin{pmatrix}1 & 0 & 0\end{pmatrix}\bullet \begin{pmatrix} 0.3 \\ 0.3 \\ 0.5 \end{pmatrix} & \begin{pmatrix}1 & 0 & 0\end{pmatrix}\bullet \begin{pmatrix} 0.1 \\ 0.3 \\ 0.4 \end{pmatrix} \end{pmatrix} \end{align*} $$

Wir können also $X_{t+1} = X_t \cdot{} M$ ausrechnen. Allerdings könnten wir auch $M^{14}$ ausrechnen und einmal $X_0 \cdot M^{14}$ berechnen.

Wir rechnen $v \cdot M$ als

Zeile mal Spalte, für alle Spalten von $M$

Ein Matrixprodukt $M_1 \cdot M_2$ berechnet sich als

für jede Zeile von $M_1$: Zeile mal Spalte, für alle Spalten von $M_2$

$$ \begin{align*} M^2 &= \begin{pmatrix}0.6 & 0.3 & 0.1 \\ 0.4 & 0.3 & 0.3 \\ 0.1 & 0.5 & 0.4 \end{pmatrix} \cdot \begin{pmatrix}0.6 & 0.3 & 0.1 \\ 0.4 & 0.3 & 0.3 \\ 0.1 & 0.5 & 0.4 \end{pmatrix} \\ &= \begin{pmatrix} \begin{pmatrix}0.6 & 0.3 & 0.1 \end{pmatrix}\bullet \begin{pmatrix} 0.6 \\ 0.4 \\ 0.1 \end{pmatrix} & \begin{pmatrix}0.6 & 0.3 & 0.1\end{pmatrix}\bullet \begin{pmatrix} 0.3 \\ 0.3 \\ 0.5 \end{pmatrix} & \begin{pmatrix}0.6 & 0.3 & 0.1\end{pmatrix}\bullet \begin{pmatrix} 0.1 \\ 0.3 \\ 0.4 \end{pmatrix}\\ \begin{pmatrix}0.4 & 0.3 & 0.3 \end{pmatrix}\bullet \begin{pmatrix} 0.6 \\ 0.4 \\ 0.1 \end{pmatrix} & \begin{pmatrix}0.4 & 0.3 & 0.3\end{pmatrix}\bullet \begin{pmatrix} 0.3 \\ 0.3 \\ 0.5 \end{pmatrix} & \begin{pmatrix}0.4 & 0.3 & 0.3\end{pmatrix}\bullet \begin{pmatrix} 0.1 \\ 0.3 \\ 0.4 \end{pmatrix}\\ \begin{pmatrix}0.1 & 0.5 & 0.4\end{pmatrix}\bullet \begin{pmatrix} 0.6 \\ 0.4 \\ 0.1 \end{pmatrix} & \begin{pmatrix}0.1 & 0.5 & 0.4 \end{pmatrix}\bullet \begin{pmatrix} 0.3 \\ 0.3 \\ 0.5 \end{pmatrix} & \begin{pmatrix}0.1 & 0.5 & 0.4 \end{pmatrix}\bullet \begin{pmatrix} 0.1 \\ 0.3 \\ 0.4 \end{pmatrix} \end{pmatrix} \end{align*} $$

Um $X_{14}$ auszurechnen könnten wir 14 Vektor-Matrix multiplikationen rechnen $$ X_{14} = X_0 \cdot M \cdot \dots \cdot M $$

Oder stattdessen $M^{14}$ berechnen und mit einer Vektor-Matrix multiplikation $$ X_{14} = X_0 \cdot M^{14} $$ ausrechnen.

Matrix-Matrix multiplikationen sind schlimmer als Vektor-Matrix multiplikationen.

Können wir $M^{14}$ irgendwie effizienter ausrechnen als $M \cdot M \cdot \dots \cdot M = M^{14}$

$$ M^{14} = {(M^7)}^2 = {(M \cdot M^6)}^2 = {(M \cdot {(M^3)}^2)}^2 = {(M \cdot {(M \cdot M \cdot M)}^2)}^2 $$

$\leadsto$ Insgesamt fünf M-M Multiplikationen und eine V-M Multiplikation.

from numpy import array

M = array([
    [0.6, 0.3, 0.1], 
    [0.4, 0.3, 0.3], 
    [0.1, 0.5, 0.4]]
)

x0 = [1, 0, 0]
x0

[1, 0, 0]

from numpy import linalg
x0 = [0, 0, 1]
x0 @ linalg.matrix_power(M, 14) # schnelles Exponenzieren

array([0.40908903, 0.34848547, 0.2424255 ])

Mehr als die halbe Wahrheit

Sehr brave Markovketten konvergieren mit $t \to \infty$ gegen eine eindeutige stationäre Verteilung $X^*$. Mathematisch lässt sich diese Verteilung durch

$$ X^* \cdot M \overset{!}{=} X^* $$

ausdrücken und explizit als Lösung des Gleichungssystems (denn Matrizen stellen mehrere Gleichungen dar) ausrechnen. Um eine stochastische Verteilung zu erhalten, brauchen wir die zusätzliche Gleichung

$$ 1 = \sum_{i} X^*_i. $$

Allgemein drückt man Lösungen der oberen Gleichung durch die Form

$$ v^* M = \lambda v^* $$

aus. Hierbei ist $\lambda != 0$ eine Zahl, die man auch Eigenwert nennt. Eine Lösung für die Eigenwertgleichung ist also ein Vektor $v^*$, der sich nach Matrixmultiplikation mit $M$ um den Faktor $\lambda$ streckt, allerdings seine Richtung beibehält. Da in der obigen Gleichung der Streckfaktor $\lambda = 1$ ist, nennen wir $X^*$ Eigenvektor von $M$ zum Eigenwert $1$.

In python können wir die Eigenwerte und -Vektoren berechnen lassen:

# linalg.eig berechnet Rechts-Eigenvektoren von Matrizen, wir suchen allerdings Links-Eigenvektoren
# Um zum richtigen Ergebnis zu kommen, müssen wir M also spiegeln (M.transpose())
ews, evs = linalg.eig(M.transpose()) # berechnet Eigenwerte und Eigenvektoren

# Wir sehen, dass ews[0] der Eigenwert 1 ist
print(ews[0])

# Folglich ist die 0-te Spalte von evs der dazugehörige Eigenvektor
v = evs[:,0]

# Wir müssen v auf Länge 1 skalieren, dass v ein stochastischer Vektor ist
v /= sum(v)

# Wir sehen, dass v und v@M der gleiche Vektor sind.
print(v)
print(v @ M)

Frösche brauchen Zufall

Viele Leute werfen faire Münzen in den Teich der Frösche. Wir sollen einen Frosch aussuchen, der der neue Schatzmeister werden soll. Wie können wir aus den 7 Fröschen fair einen auswählen?

Bedingungen:

• Jeder Frosch wird mit $\frac{1}{7}$ ausgewählt
• Zufall nur durch die Münzen

from numpy import array

M = array([
[ 0.0 , 0.5 , 0.5 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0], 
[ 0.0 , 0.0 , 0.0 , 0.5 , 0.5 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0], 
[ 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.5 , 0.5 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0], 
[ 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.5 , 0.5 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0], 
[ 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.5 , 0.5 , 0.0 , 0.0 , 0.0], 
[ 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.5 , 0.5 , 0.0], 
[ 0.5 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.5], 
[ 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 1.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0], 
[ 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 1.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0], 
[ 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 1.0 , 0.0 , 0.0 , 0.0 , 0.0], 
[ 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 1.0 , 0.0 , 0.0 , 0.0], 
[ 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 1.0 , 0.0 , 0.0], 
[ 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 1.0 , 0.0], 
[ 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 0.0 , 1.0]
])
v = array([1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ])
v @ linalg.matrix_power(M, 3*100)

array([4.90909347e-91, 0.00000000e+00, 0.00000000e+00, 0.00000000e+00,
       0.00000000e+00, 0.00000000e+00, 0.00000000e+00, 1.42857143e-01,
       1.42857143e-01, 1.42857143e-01, 1.42857143e-01, 1.42857143e-01,
       1.42857143e-01, 1.42857143e-01])

Markovketten

Die Prozesse, die wir bisher gesehen haben lassen sich als Markovketten verstehen. Die Ketten, die wir betrachten teilen die folgenden Eigenschaften:

• Zeit vergeht für unsere Prozesse $X_0, X_1, X_2, \dots$ diskret
• Wir können die Übergangswahrscheinlichkeiten in einer $n \times n$ Matrix $M$ auflisten
• Markovketten sind gedächtnislos

Außerdem ist $M$ eine stochastische Matrix und erfüllt

• jeder Eintrag $m_{ij}$ ist eine Zahl von 0 bis 1
• jede Zeile summiert sich zu $1$

A: A simple Language Model

Mit dem hp.txt, generiere Harry Potter fanfiction! Ein brandneues Universum an Unsinn erwartet dich!

https://dominic.leafbla.de/hp_parsed.txt https://dominic.leafbla.de/forschungstage

Code Beispiele

https://dominic.leafbla.de/crawler.py (Crawlt Wiki) https://dominic.leafbla.de/markov.py (Rechnet mit den Daten davon)

B: Monopoly

Wo sollte ich in Monopoly versuchen meine Häuser zu bauen?

C: Pagerank

Crawle eine kleine Wiki, analysiere ihre Links und finde die relevantesten Seiten!