Formaler Rahmen

Zunächst wird die Schreibweise erläutert und die Definitionen angegeben, die bei den folgenden Untersuchungen benötigt werden.

Es wird eine endliche oder unendliche Objektmenge X betrachtet. Jedes Objekt in X gehört zu genau einer von zwei disjunkten Klassen. Jede Teilmenge von X wird als eine Hypothese bezeichnet. Damit gibt es 2^|X| extensionsverschiedene Hypothesen. Eine Hypothesenmenge HM ist eine Teilmenge aller Hypothesen über X. Die Elemente einer bestimmten Hypothese H_z, der sogenannten Zielhypothese werden positiv und die übrigen Elemente in Xnegativ klassifiziert. Als Erfahrungsdaten werden dem Lernenden mit einer Kennzeichnung versehene Objekte aus X präsentiert. Die Kennzeichnung zeigt an, ob das Objekt positiv oder negativ zu klassifizieren ist. Es wird angenommen, daß die Zielhypothese in der betrachteten Hypothesenmenge enthalten ist. Die Lernaufgabe sei für jedes Objekt in X die zugehörige Klasse richtig zu bestimmen. Damit besteht die Lernaufgabe darin, für jedes Objekt in X zu bestimmen, ob es ein Element der anfänglich unbekannten Zielhypothese ist.

Für jede formale Lerntheorie L gibt es dabei in folgendem Sinn genau eine Hypothesenmenge $HM_{L}\subseteq 2^{X}$.

a)

Für jede Hypothese H aus HM_L gibt es entsprechende Erfahrungsdaten, so daß L lernen wird, die Objekte aus X genau gemäß H zu klassifizieren.

b)

eine Lerntheorie L kann niemals eine Hypothese bestimmen, die nicht in der zugrundeliegenden Hypothesenmenge HM_L enthalten ist - gleich welche Erfahrungsdaten präsentiert werden.

Bei relevanten Anwendungen der Lerntheorie werden die jeweiligen Objektmengen sehr groß sein. Angenommen, die Objekte des Lernbereiches werden durch nur 30 unterschiedliche, einstellige Prädikate beschrieben. Dann lassen sich rein syntaktisch bereits $2^{30}\approx 1\ 000\ 000\ 000$ Objektbeschreibungen unterscheiden.

Valiant führte 1984 [Val84b,Val84a] den Begriff des wahrscheinlichen annähernd korrekten Lernens (probably approximately correct learning) ein. Dabei wird eine beliebige, unbekannte aber feste Wahrscheinlichkeitsverteilung D über der Objektmenge X angenommen. Jedes Objekt in X tritt mit einer festen aber unbekannten Wahrscheinlichkeit auf, die durch D bestimmt ist. Während der Sammlung von Erfahrungsdaten für einen Induktionsschluß werden die Objekte aus X mit einer entsprechenden Klassifikation registriert. Das Ziel eines Induktionsschlusses aus den gesammelten Erfahrungsdaten ist es dann, möglichst alle Objekte aus X richtig zu klassifizieren, die wiederum zufällig nach der gleichen unbekannten Wahrscheinlichkeitsverteilung D auftreten. Dabei ist allerdings - im Gegensatz zu der Situation vor dem Induktionsschluß - keine Klassifizierung der Objekte mehr vorgegeben. Das Ziel dabei ist es, die Wahrscheinlichkeit, daß ein zufällig nach D gewähltes Objekt falsch klassifiziert wird, zu minimieren. Die Wahrscheinlichkeit, daß der Induktionsschluß auf ein zufällig nach D ausgewähltes Objekt nicht zutrifft, wird im folgenden auch die Fehlklassifikationswahrscheinlichkeit des Induktionsschlusses genannt. Weiterhin soll mit möglichst großer Wahrscheinlichkeit der Induktionsschluß nur eine kleine Fehlklassifikationswahrscheinlichkeit aufweisen.

Definition 1   Sei HM eine Hypothesenmenge und $H_{z}\in HM$ die Zielhypothese. Dann sagen wir, daß eine Lerntheorie L genau dann eine Hypothesenmenge HM wahrscheinlich annähernd korrekt lernt, wenn

$$(\forall H_{z}\in HM)(\forall D)(\forall \varepsilon >0)(\forall \delta >0)$$

die von L bestimmte Hypothese $H\in HM$ ein zufällig nach D ausgewähltes Objekt $x\in X$ höchstens mit einer Wahrscheinlichkeit von $\varepsilon$fehlklassifiziert. Dieses Ereignis muß dabei mit einer (Konfidenz-) Wahrscheinlichkeit von mindestens $1-\delta$ auftreten.

Ohne Verlust der Allgemeinheit können noch die folgenden Vereinbarungen getroffen werden. Zunächst wird eine Repräsentation z(H) einer Hypothese H über X definiert.

Definition 2  

Sei jedes Objekt in X durch eine binäre Zahl von 0 bis |X|-1 bezeichnet. Dann heißt die im folgenden beschriebene binäre Zeichenkette z(H) die binäre Darstellung von H. z(H) hat die Länge |X|. Zu jeder Position in z(H) korrespondiert ein entsprechend nummeriertes Objekt in X. Eine `1' an der Position für das Objekt $x\in X$ bedeutet $x\in H$, während eine `0' anzeigt, daß $x\not\in H$.

Beispiel: Sei X die Menge $\{1,2,3,4,5,6,7,8,9\}$ und $HM=\{H_{1},H_{2}\}$, wobei

$H_{1}=\{1,4,8,9\}$ und $H_{2}=\{1,3,5,8,9\}$ gelte.

Dann ist z(H₁)=`100100011' und z(H<sub>2</sub>)=`101010011'.

Damit läßt sich von der Kolmogoroffkomplexität K(z(H)) einer jeden Hypothese $H\in HM$sprechen.

Es folgt die Definition eines Komplexitätsmasses K_max(HM) einer Hypothesenmenge HM, welches der Komplexität der komplexesten Hypothese in HM enstpricht:

Definition 3   Sei K_max eine Funktion $2^{2^{X}} \rightarrow {\bf N}$und

$$K_{max}(HM)=\max_{H\in HM}\ K(z(H))$$

Dann heißt K_max(HM) die Komplexität der Hypothesenmenge HM.

Hypothesenmengen, die komplexe Hypothesen enthalten  

Wie weiter oben erwähnt, läßt sich jeder formalen Lerntheorie genau eine Menge von Hypothesen zuordnen. Im folgenden wird die Zahl der Hypothesen betrachtet, die in einer Hypothesenmenge notwendigerweise enthalten sein muß, wenn eine Lerntheorie in der Lage sein soll, auch komplexe Hypothesen zu lernen. Die Zahl der Hypothesen in HM ist interessant, da sie einen Indikator dafür ist, wieviele Erfahrungsdaten benötigt werden, um eine akzeptable Hypothese (geringe Fehlklassifikationswahrscheinlichkeit) aus HM zu bestimmen. Die Erfahrungsdaten dienen dabei dazu, Konkurrenzhypothesen auszuschließen, falls sie inkonsistent mit den Erfahrungsdaten sind.

Theorem 1   Sei L ein Lernalgorithmus, der binär für eine universelle Turingmaschine U codiert ist. Sei HM_Ldie Hypothesenmenge, die L zugrunde liegt.

Für $K_{max}(C) > \vert L\vert+{\rm const}$gibt es mindestens

$$2^{K_{max}(HM_{L})-\vert L\vert-{\rm const}}$$

Hypothesen in HM_L, wobei const eine kleine konstante natürliche Zahl ist, die nur von der konkret gewählten universellen Turingmaschine U abhängt.

Beweis siehe Hoffmann [Hof90a].