Computational Intelligence, SS08
2 VO 442.070 + 1 RU 708.070 last updated:
General
Course Notes (Skriptum)
Online Tutorials
Practical Course Slides
Homework
Exams
Animated Algorithms
Interactive Tests
Key Definitions
Downloads
Literature and Links
News
mailto:webmaster

Key Definitions for the Course Computational Intelligence

Prof. G. Kubin and Prof. W. Maass

 

These key definitions are also available as printable PDF-file.

Here we define some basic mathematical notations and definitions used throughout the course. For a better understanding they are written in german.

Kreuzprodukt
Für beliebige Mengen $ A,B$ ist das Kreuzprodukt $ A \times B$ die Menge aller geordneten Paare (=arrays) $ \langle a,b \rangle $ mit $ a \in A$ und $ b \in B$. Beachte: $ \langle a,b \rangle = \langle a', b' \rangle \Leftrightarrow (a=a'$     und $ b=b')$.

Für beliebige Mengen $ A_1,\ldots,A_d$ ist das Kreuzprodukt $ A_1 \times \ldots \times A_d$ die Menge aller arrays $ \langle a_1,\ldots,a_d\rangle $ mit $ a_i \in A_i$ für $ i=1,\ldots,d$.

Funktion
Für beliebige Mengen $ M,N$ ist eine Menge $ F \subseteq M \times N$ eine Funktion von $ M$ nach $ N$ falls gilt,
  1. für alle $ m \in M$ gibt es ein $ n \in N$ mit $ \langle m,n\rangle \in F$
  2. es gibt keine Paare $ \langle m,n\rangle \in F$ und $ \langle m,n'\rangle \in F$ mit $ n \neq n'$ (d.h. $ F$ ist eine ``rechtseindeutige'' Relation).

Für eine Funktion $ F \subseteq M \times N$ schreibt man in der Regel $ F(m) =n$ anstatt $ \langle m,n\rangle \in F$.

Lernumgebung
Im Maschinellen Lernen betrachtet man Wahrscheinlichkeitsmaße $ P$ auf einer Menge $ A \times B$ (oder nur auf $ A$ im Fall von unsupervised Lernen) als abstraktes Modell der Lernumgebung.
Targetwerte
$ B$ ist eine endliche Menge im Fall von Klassifikationsproblemen. Falls es nur zwei Klassen gibt, wählen wir in der Regel $ B=\{-1,1\}$. Bei Regressionsproblemen ist die Menge $ B$ nicht endlich, z.B. $ B =$   $ \mbox{${\Bbb{R}}$}$$ .$
Attribute
$ A$ kann eine Menge von Abtastwerten einer Zeitreihe (einer Folge, eines Signals) oder ein Vektor von Attributen (Merkmalen) sein. Im letzteren Fall schreiben wir $ A=A_1 \times \ldots \times A_d $, und die Elemente von $ A$ werden mit $ \langle a_1,\ldots,a_d\rangle $ bezeichnet. Die Dimension der Attributvektoren wird also mit $ d$ bezeichnet.
Wahrscheinlichkeitsmaß einer Menge
Für $ M \subseteq A\times B$ wird $ P(M)$ für die Wahrscheinlichkeit geschrieben, dass ein zufällig gezogenes Paar $ \langle a,b\rangle \in A \times B$ in der Menge $ M$ liegt. Wir setzen voraus, dass alle Mengen $ M$, die wir betrachten, messbar sind, sodass $ P(M)$ stets wohldefiniert ist.
Wahrscheinlichkeitsdichtefunktion
Entsprechend bezeichnet bei Regressionsproblemen $ p(a,b)$ die Wahrscheinlichkeitsdichtefunktion an der Stelle $ \langle a,b\rangle \in A \times B$, wobei wir voraussetzen, dass diese Dichtefunktion existiert.
Hypothesen
sind Funktionen $ H:A \rightarrow B$. Wir schreiben $ \cal{H}$ für die Menge aller Hypothesen, die bei einem konkreten Lernverfahren betrachtet werden.
Andere Begriffe für Hypothesen
Wir müssen den Begriff der Hypothese noch mit den Begriffen ``Regressionsfunktion'', ``Clusterrepräsentant'' (da ist ja die Funktion $ A \rightarrow A$), und ``gelernte Wahrscheinlichkeitsverteilung'' ergänzen. Im Prinzip wollen wir ja immer eine unbekannte Funktion lernen, nur ihre Interpretation ist jeweils verschieden und die eingeführte Terminologie auch.
error$ _P(H):=P(\{\langle a,b \rangle \in A \times B: H(a) \neq b\})$ ist der wahre Fehler einer Hypothese $ H$ im Falle eines Klassifikationsproblems.
Wahrer mittlerer quadratischer Fehler
MSE$ _p(H) := E((b-H(a))^2)$ ist der wahre mittlere quadratische Fehler einer Hypothese $ H$ im Falle eines Regressionsproblems. Dieser Fehler wird auch für Clustering-Probleme und Vektorquantisierung als Maß herangezogen.
Empirischer Fehler (Klassifikation)
Falls $ L$ eine Liste (array) oder Folge $ \langle \langle a_1,b_1\rangle ,\ldots,\langle a_l,b_l\rangle \rangle $ von Paaren $ \langle a_i,b_i \rangle \in A \times B$ ist, so schreiben wir
error$\displaystyle _L(H):=\frac{\char93 \{i\in\{1,\ldots,l\}:H(a_i)\neq b_i\}}{l}$
für den (empirischen) Fehler einer Hypothese $ H$ auf der Liste $ L$ von Beispielen (Klassifikationsproblem).
Empirischer Fehler (Regression)
Falls $ L$ eine Liste (array) oder Folge $ \langle \langle a_1,b_1\rangle ,\ldots,\langle a_l,b_l\rangle \rangle $ von Paaren $ \langle a_i,b_i \rangle \in A \times B$ ist, so schreiben wir
MSE$\displaystyle _L(H):=\frac{ \sum_{i=1}^l(b_i-H(a_i))^2}{l}$
für den (empirischen) Fehler einer Hypothese $ H$ auf der Liste $ L$ von Beispielen (Regressionsproblem).
Liste, Arrays, Mengen
Oft redet man auch recht ungenau anstatt von einer Liste von einer Menge von Beispielen $ \langle a_i,b_i\rangle $. Das kann aber zu Irrtümern führen, wenn ein Paar $ \langle a,b \rangle $ mehrmals in der Liste $ L$ vorkommt. Daher sollte man im Zweifelsfall immer von Listen von Beispielen reden.
Folge
In manchen Fällen spielt die Reihenfolge der Paare in einer Liste keine Rolle, so z.B. bei der Bestimmung des empirischen Fehlers. Bei Lernalgorithmen (siehe w.u.) spielt die Reihenfolge, in der der Algorithmus die Paare der Liste abarbeitet aber praktisch immer eine Rolle, so dass immer von einer geordneten Liste oder Folge auszugehen ist. Sollte für bestimmte Situationen (z.B. Verarbeitung einer Folge von i.i.d. Beobachtungen eines wiederholt ausgeführten Experiments, asymptotische Analyse) die Reihenfolge irrelevant sein, sollte das stets besonders begründet werden. In dem Fall kann ja durch eine gezielte Zufallspermutation der Listenindices eine willkürliche Reihenfolge erzeugt werden.
unendliche Folgen
Abschließende Bemerkung zur Liste vs. Folge: Eine Liste hat wohl immer einen Anfang und ist auch meistens endlich. Eine Folge wird vielfach einseitig oder zweiseitig unendlich sein. Für die online-Verarbeitung laufend gewonnener Boebachtungen brauchen wir zumindest den Begriff der einseitig unendlich langen Folge.
Trainings-, Validierungs- und Testmenge
Für die praktische Durchführung müssen wir die Liste vorhandener Paare in 3 Teile zerlegen: eine Trainingsmenge für die Bestimmung der besten Hypothese bei gewählter Hypothesenklasse, eine Validierungsmenge für die Bestimmung der besten Hypothesenklasse (Modellstruktur), eine von den beiden ersten Mengen komplett unabhängige Testmenge zur tatsächlichen Bewertung des zu erwartenden Generalisierungsfehlers.
Lernalgorithmus
Ein Lernalgorithmus (mit Hypothesenklasse $ \cal{H}$) ist eine Funktion, die jeder endlich langen Liste $ L$ von Beispielen aus $ A \times B$ eine Hypothese $ H(L)$ aus $ \cal{H}$ zuordnet. Dabei kann die Auswahl von Listen $ L$ auf einen Listenraum $ {\cal L}$ eingeschränkt sein. $ H(L)$ selbst ist eine Funktion von $ A$ nach $ B$.
Online Lernen
Beim online Lernen wird davon abweichend versucht, bei Vorliegen eines einzelnen neuen Beispielpaars sofort eine neue Hypothese zu berechnen, die je nach Algorithmus dann auch nur lokal gültig ist. Das ist speziell dann notwendig, wenn sich das Wahrscheinlichkeitsmaß $ P$ auf der Menge $ A \times B$ zeitlich ändert.
Konvergenz von Lernalgorithmen
Das Konvergenzverhalten eines Algorithmus wird untersucht, indem die Folge von Hypothesen $ H(L_i)$ untersucht wird, die dadurch entsteht, dass man dem Lernalgorithmus eine Folge von um je ein Paar erweiterten Listen $ L_i = \langle \langle a_1,b_1\rangle , \ldots, \langle a_i,b_i\rangle \rangle $ anbietet.