DAS PRINZIP DER GESCHICHTSKOMPRESSION

Man betrachte einen deterministischen Prediktor (nicht notwendigerweise ein KNN), dessen Zustand zur Zeit $t$ der Sequenz $p$ durch einen reellen Eingabevektor $x^p(t)$ aus der Umgebung, einen internen Zustandsvektor $h^p(t)$, und einen Ausgabevektor $z^p(t)$ gegeben ist.

Die Eingaben aus der Umgebung selbst dürfen nichtdeterministisch sein. Zum Zeitpunkt $0$ beginnt der Prediktor mit $x^p(0)$ und einem internen Initialisierungszustand $h^p(0)$. Zum Zeitpunkt $t \geq 0$ berechnet er

$$z^p(t)= f ( x^p(t), h^p(t)).$$ (7.1)

Weiterhin berechnet der Prediktor zur Zeit $t >0$

$$h^p(t) = g ( x^p(t-1), h^p(t-1)).$$ (7.2)

Es ist nun entscheidend, einzusehen, daß die gesamte Information über die Eingabe zu jedem beliebigen Zeitpunkt $t_x$ in

$$t_x, f, g, x^p(0), h^p(0), \{ (t_s, x^p(t_s)) ~~mit~~ 0 < t_s \leq t_x, z^p(t_s - 1) \neq x^p(t_s) \}$$ (7.3)

enthalten ist [102]. Denn falls zum Zeitpunkt $t~~$ $z^p(t)=x^p(t+1)$ gilt, kann der Prediktor die neue Eingabe aus den alten Eingaben vorhersagen. Die neue Eingabe ist aus den alten mittels $f$ und $g$ deduzierbar und trägt damit lediglich redundante Information. Die gesamte Eingabesequenz kann aus der reduzierten Beschreibung (7.4) rekonstruiert werden [113].

Dabei spielt es keine Rolle, ob die Eingabesequenz durch einen deterministischen oder durch einen nicht-deterministischen Prozeß generiert wurde. Es geht nur um die Kompression der Beschreibung einer bereits beobachteten Sequenz - auf welche Weise die Sequenz entstanden ist, ist egal. Beispiel: Ein trivialer Prediktor, der bei einer Sequenz von Münzwürfen stets `Wappen' prophezeiht, wird in etwa der Hälfte der Fälle recht behalten - damit läßt sich die Zahl der zur Beschreibung der beobachteten Sequenz benötigten Eingaben um etwa die Hälfte reduzieren^7.1.

Die Information über eine beobachtete Eingabesequenz läßt sich i.a. jedoch noch weiter komprimieren: Es genügt vollständig, wenn wir uns in (7.4) ausschließlich diejenigen Komponenten der Vektoren $x^p(t_s)$ merken, die nicht korrekt vorhergesagt wurden. Ich nenne dies das Prinzip der Geschichtskompression.

Typischerweise wollen wir beobachtete Sequenzen gar nicht vollständig rekonstruieren, sondern nur korrekt klassifizieren. Aus dem Prinzip der Geschichtskompression folgt, daß wir zwei oder mehr Sequenzen schon dann voneinander unterscheiden können, wenn wir nichts über die Sequenzen wissen außer den falsch vorhergesagten Eingaben samt den Zeitschritten, zu denen sie auftraten. Durch das Ignorieren erwarteter Eingaben geht keine Information verloren. Zur Sequenzklassifikation müssen wir nicht einmal $f$ und $g$ kennen - es genügt, zu wissen, daß sowohl $f$ als auch $g$ deterministisch sind.

Vom theoretischen Standpunkt aus ist es wirklich notwendig, den Zeitschritt zu kennen, zu dem eine unerwartete Eingabe auftrat. Ohne solches Wissen eröffnet sich Raum für Ambiguitäten: Zwei verschieden Eingabesequenzen können zur selben kürzeren Sequenz falsch prophezeihter Eingaben führen. Bei vielen praktischen Aufgaben ist es jedoch nicht unbedingt erforderlich, die `kritischen' Zeitschritte zu kennen (siehe Abschnitt 7.4.1).

Related links in English: Recurrent networks - Fast weights - Subgoal learning - Reinforcement learning and POMDPs - Unsupervised learning and ICA - Metalearning and learning to learn
Deutsche Heimseite