Universelle Lerntheorien

Unter einer universellen Lerntheorie wird im folgenden eine formale Theorie verstanden, die es erlaubt, in beliebigen Anwendungsgebieten aus gegebenen Erfahrungsdaten generalisierende Schlüsse zu ziehen. Es wird auf einige generelle Schwierigkeiten bei einem solchen Unterfangen hingewiesen. Die Schwierigkeiten gelten sowohl für deskriptive Theorien des menschlichen Lernens als auch für präskriptive Lerntheorien. Für präskriptive Lerntheorien, die sich mit induktivem Schließen befassen, gibt es eine Reihe von Vorläufern. Beispielsweise versuchte Carnap in Logical Foundations of Probability 1950 [Car50] eine formale Induktionstheorie zu entwickeln, die sich an syntaktischen Merkmalen der betrachteten Sätze orientierte. Goodmans Paradoxon^7.20 ist wohl ein starker Hinweis darauf, daß eine rein syntaktische Betrachtung keineswegs ausreichen kann, um Induktionsschlüsse zu begründen, wie sich in der langen Diskussion herauskristallisierte.^7.21 Im folgenden wird zwar nicht Carnaps Ansatz weiterverfolgt, obgleich sich eine universelle formale Lerntheorie nur an syntaktischen Merkmalen orientieren kann. Goodmans Paradoxon betrifft epistemologische Probleme von Induktionstheorien. Im Gegensatz dazu werden im folgenden rein kombinatorische Probleme von sowohl präskriptiven als auch deskriptiven Lern- bzw. Induktionstheorien betrachtet. Zunächst werden noch einige Formalien vereinbart.

Sei n die Zahl der Objekte in X. Dann gibt es 2ⁿ verschiedene Teilmengen oder Hypothesen über X. Weiterhin gibt es 2²ⁿ verschiedene Hypothesenmengen über X.

Das heißt, um eine beliebige Hypothesenmenge beschreiben zu können, werden mindestens $\log_{2} 2^{2^{n}}=2^{n}$ Binärzeichen benötigt. Eine allgemeine Lerntheorie muß eine konstante und wird in der Regel eine verhältnismäßig geringe Komplexität (Länge) haben. Dabei soll sie auf beliebige Bereiche anwendbar sein.

Für die folgenden asymptotischen Betrachtungen wird weiter von den folgenden Vereinbarungen ausgegangen. Sei X eine abzählbare Menge. Sei $X_{N}=\{X_{i}\vert i\in {\bf N}\}$, eine unendliche Menge von Teilmengen von X, wobei gilt: $X_{i}\subset X_{j}$, wenn i < j. Sei $HM_{N}=\{HM_{i}\vert i\in {\bf N}\}$ eine unendliche Menge von Hypothesenmengen wobei gilt: $HM_{i}\subseteq 2^{X_{i}}$. Zum Beispiel könnte HM_N die Menge aller Mengen von aussagenlogischen Formeln mit höchstens 17 Disjunktionstermen in disjunktiver Normalform über 1, 2, 3, $\ldots$ Aussagenvariablen sein.

Das notwendige asymptotische Wachstum von Hypothesenmengen  

Im allgemeinen kann man wohl davon ausgehen, daß die zu lernenden Hypothesen bzw. Klassifikationsregeln bei zunehmendem Umfang des Anwendungsbereiches immer komplizierter werden. Die Klassifikationsregeln müssen in den umfangreicheren Bereichen mehr Randbedingungen explizit enthalten, unter denen sie gelten.

Der Zusammenhang aus Theorem 1 läßt sich für asymptotische Betrachtungen wie folgt formulieren:

Theorem 2   Sei HM_N eine Menge von Hypothesenmengen über X_N. Wenn K_max(HM_i) eine in i streng wachsende Funktion ist, dann gilt für alle i > i₀ für ein geeignetes i₀: Die Zahl der Hypothesen in HM_i ist mindestens

c(2^K_max(HM_i))

für ein geeignetes c>0.

Beweis siehe Hoffmann [Hof91a].

Obiges Theorem zeigt das Verhältnis von Hypothesenkomplexität zu Hypothesenzahl in einer Hypothesenmenge bei sehr großer Komplexität. das Verhältnis gilt ungeachtet des betrachteten Lernverfahrens. Es zeigt, daß die Zahl der Hypothesen exponentiell mit der Komplexität der kompliziertesten Hypothese ansteigt. Daraus resultiert das folgende Dilemma, bei dem Versuch eine allgemeine formale Lerntheorie aufzustellen, die auch in der Lage ist, auf komplexe Hypothesen zu schließen: Entweder muß diese Lerntheorie sehr lang sein, oder aber sie muß mit einer sehr großen Menge von Erfahrungsdaten versorgt werden, um eine entsprechend komplexe Hypothese zu gewinnen. Anders ausgedrückt bedeutet dies, wenn eine kurz zu beschreibende formale Lerntheorie in der Lage ist, komplexe Hypothesen zu bilden, dann muß die zugrunde liegende Hypothesenmenge auch noch eine Vielzahl anderer, ebenso komplexer Hypothesen enthalten. Dies impliziert, daß eine entsprechend große Menge an Erfahrungsdaten erforderlich ist, um die vielen Konkurrenzhypothesen der Zielhypothese ausschließen zu können.

Theorem 1 und 2 spiegeln einen fundamentalen Sachverhalt wider. Es zeigt den Zusammenhang auf, zwischen dem Informationsgehalt einer Lerntheorie, der Information in den Erfahrungsdaten und der Information, die in der resultierenden Hypothese enthalten ist. Im folgenden Abschnitt wird gezeigt, was dies für das induktive Schließen aus Beispielen im Rahmen des wahrscheinlich annähernd korrekten Lernens bedeutet.

Induktion aus Beispielen  

Es lassen sich verschiedene Arten unterscheiden, wie Erfahrungsdaten für Induktionsschlüsse gesammelt werden. Im folgenden werden die Konsequenzen des obigen Sachverhaltes für das induktive Schließen im Rahmen des wahrscheinlich annähernd korrekten Lernens untersucht. Dafür kann die folgende Untergrenze für die Zahl von erforderlichen Beispielen angegeben werden.

Theorem 3   Sei HM_N eine Menge von Hypothesenmengen über X_N. Sei ferner K_max(HM_i) streng wachsend in i. Dann wird für ein wahrscheinlich annähernd korrektes Lernen mit einer Fehlklassifikationswahrscheinlichkeit von $1-\varepsilon$und einer Konfidenzwahrscheinlichkeit von $1-\delta$mittels einer formalen Lerntheorie L für i>i₀ für ein geeignetes i₀, mindestens

$$c(\frac{K_{max}(HM_{i})}{\varepsilon\log \vert X_{i}\vert})$$

Beispiele benötigt, für ein geeignetes c>0 und $0<\delta<\frac{1}{100}$

Für einen Beweis siehe Hoffmann [Hof91a].

Die Zahl der benötigten Beispiele wächst also asymptotisch mindestens linear mit der Komplexität der kompliziertesten Hypothese in der betrachteten Hypothesenmenge. In der Praxis können Menschen im Gegensatz dazu häufig aus sehr viel weniger Beispielen verlässliche induktive Schlüsse ziehen.^7.22