Algorithmisches Lernen Algorithmic Learning Theorie des

Transcrição

Algorithmisches Lernen
Algorithmic Learning
01011101010001010110111
010111000100011
Theorie des Algorithmischen Lernens
0101110101000101011011101011100
0100011 0101110101000101011011101011100
0100011
Sommersemester 2006
01011101010001010110111010111000100011
Gunter Grieser
01011101010001010110111010111000100011
01011101010001010110111010111000100011
010111010100010101101110101110
00100011
Folienvorlage von K.P. Jantke
Motivation
01011101010001010110111
010111000100011
Was ist Lernen???
0101110101000101011011101011100
0100011 0101110101000101011011101011100
0100011
01011101010001010110111010111000100011
01011101010001010110111010111000100011
01011101010001010110111010111000100011
010111010100010101101110101110
00100011
Learning
01011101010001010110111
010111000100011
• Learning is any change in a system that allows
it to do better the second time on repetition of
the same task or another task drawn from the
same population.
01011101010001010110111010111000100011
0101110101000101011011101011100
0100011 0101110101000101011011101011100
0100011
01011101010001010110111010111000100011
01011101010001010110111010111000100011
Herbert Simon, 1983
010111010100010101101110101110
00100011
Learning
01011101010001010110111
010111000100011
0101110101000101011011101011100
0100011 0101110101000101011011101011100
0100011
• Learning is the organization of experience.
Dana Scott, 1983
01011101010001010110111010111000100011
01011101010001010110111010111000100011
01011101010001010110111010111000100011
010111010100010101101110101110
00100011
Learning
01011101010001010110111
010111000100011
0101110101000101011011101011100
0100011 0101110101000101011011101011100
0100011
• Learning is making useful changes in our
minds.
01011101010001010110111010111000100011
01011101010001010110111010111000100011
01011101010001010110111010111000100011
Marvin
Minsky,
1985
010111010100010101101110101110
00100011
Learning
01011101010001010110111
010111000100011
0101110101000101011011101011100
0100011 0101110101000101011011101011100
0100011
• Learning is constructing or modifying
representation of what is being
experienced.
01011101010001010110111010111000100011
01011101010001010110111010111000100011
01011101010001010110111010111000100011
010111010100010101101110101110
Ryszard
Michalski, 1986
00100011
Learning
01011101010001010110111
010111000100011
0101110101000101011011101011100
0100011 0101110101000101011011101011100
0100011
• We will not state what learning is.
Pieter
Adriaans & Dolf Zantinge, 1996… 1998
01011101010001010110111010111000100011
im Kapitel010111010100010101101110101110
2 ,,What is learning?’’
01011101010001010110111010111000100011
01011101010001010110111010111000100011
00100011
Learning
01011101010001010110111
010111000100011
Numerous
mathematical models
of learning have been
proposed during the last three decades. Nevertheless,
different models give 0101110101000101011011101011100
vastly different results
0100011 0101110101000101011011101011100
concerning the learnability and0100011
non-learnability of
objects one wants to learn. Hence, finding an
appropriate definition of learning which covers most
01011101010001010110111010111000100011
aspects
of learning is also part of the goals aimed at
01011101010001010110111010111000100011
in algorithmic learning theory.
010111010100010101101110101110
00100011
Michael M. Richter, Carl H. Smith, Rolf
Wiehagen, Thomas Zeugmann, 1998
01011101010001010110111010111000100011
The Scenario of Inductive Inference
01011101010001010110111
010111000100011
• Irgend etwas soll gelernt werden - aber was ?!
• … und woraus, d.h. aus was
für Information ?
0101110101000101011011101011100
0100011 0101110101000101011011101011100
• Soll aus jeglicher Information
gelernt
werden, oder
0100011
gibt es ‘’mehr oder weniger’’ sinnvolle ?
• Und falls man etwas gelernt hat, wie drückt man das
aus, mit welchen
Mitteln formuliert man das ?
01011101010001010110111010111000100011
01011101010001010110111010111000100011
• Wer
oder was lernt ?
• Was ist ein ‘’richtiges’’ Lernergebnis
…
010111010100010101101110101110
01011101010001010110111010111000100011
• … und welche Lernprozesse00100011
sind letztendlich
erfolgreich ?
Das Szenario der Induktiven Inferenz
01011101010001010110111
010111000100011
• Klasse zu lernender Objekte
0101110101000101011011101011100
• Informationsfolgen: (Gegen-)Beispiele
0100011 0101110101000101011011101011100
0100011
• korrekte (Limes-)Spezifikationen
• Lernverfahren
01011101010001010110111010111000100011
• Hypothesenraum
01011101010001010110111010111000100011
• Semantik
von Hypothesen
010111010100010101101110101110
• Erfolgskriterium
01011101010001010110111010111000100011
00100011
Essentials
01011101010001010110111
010111000100011
Wenn man Lernen im Sinne eines solchen Szenarios
ernst meint, dann hat man auch
unausweichlich mit
0101110101000101011011101011100
0101110101000101011011101011100
ein paar Phänomenen zu tun,0100011
wie zum
Beispiel:
0100011
• Es ist im allgemeinen nicht a priori abschätzbar, ob
man schon genug Information erhalten hat, ob also der
01011101010001010110111010111000100011
Lernprozeß schon
beendet werden kann oder nicht.
01011101010001010110111010111000100011
• Wenn man schon nichts über die “globale” Güte von
Hypothesen weiß, dann wird010111010100010101101110101110
deren “lokale” Güte um so
01011101010001010110111010111000100011
00100011
wichtiger.
Gliederung
01011101010001010110111
1. Motivation
und Einführung
010111000100011
•Einführende
Beispiele
•Szenario der Induktiven Inferenz
•Charakteristika natürlicher Lernverfahren
0101110101000101011011101011100
2. Lernen formaler Sprachen0100011
0101110101000101011011101011100
0100011
3. Lernen rekursiver Funktionen
4. Ausgewählte
Anwendungen
01011101010001010110111010111000100011
01011101010001010110111010111000100011
5. Zusammenfassung
01011101010001010110111010111000100011
010111010100010101101110101110
00100011
Example 1
01011101010001010110111
010111000100011
Angenommen, über eine unbekannte Funktion f
0101110101000101011011101011100
wird Information vorgelegt
wie z.B.
0100011 0101110101000101011011101011100
f(0) = 0 , f(1) = 10100011
, ...
Um welche Funktion handelt es sich?
01011101010001010110111010111000100011
f(2) = 2 , …
01011101010001010110111010111000100011
Und jetzt … ?
010111010100010101101110101110
f(3) = 720!
,…
01011101010001010110111010111000100011
00100011
Na, noch eine Idee … ?
Analysis 1.1
01011101010001010110111
010111000100011
Untersuchen wir das Beispiel
0101110101000101011011101011100
0101110101000101011011101011100
f(0) = 0 , f(1) = 1 , f(2)0100011
= 2 , f(3)
= 720! , …
0100011
mit dem Ziel, Regularitäten aufzudecken, also
“zu lernen’’.
01011101010001010110111010111000100011
Ein Ansatz
könnte wie folgt aussehen:
01011101010001010110111010111000100011
f(3) = 720! = (6!)! = ((3!)!)! = 3!!!
010111010100010101101110101110
Gehen wir weiter in’s Detail
...
01011101010001010110111010111000100011
00100011
Analysis 1.2
01011101010001010110111
010111000100011
Gegeben Information der Form
f(x) 0101110101000101011011101011100
=y,
0100011 0101110101000101011011101011100
0100011
kann man die Suche nach einer
Darstellung
f(3) = 720! = (6!)! = ((3!)!)! = 3!!!
01011101010001010110111010111000100011
auffassen
als “expressing y in terms of x’’
01011101010001010110111010111000100011
(SUMMERS, 1975 & 1977).
010111010100010101101110101110
sind dabei die verfügbaren
00100011
Hinweis: Entscheidend
bzw. zugelassenen Ausdrucksmittel.
01011101010001010110111010111000100011
Analysis 1.3
01011101010001010110111
010111000100011
Wie drückt man das durch Terme aus?!
Gegeben sind
0101110101000101011011101011100
0100011 0101110101000101011011101011100
0100011
f(x1) = y1 , … , f(xn) = yn .
Gesucht01011101010001010110111010111000100011
sind ein Term t(x) und Substitutionen
01011101010001010110111010111000100011
σ1 , … , σ n
mit der Eigenschaft (für010111010100010101101110101110
i=1,…,n):
01011101010001010110111010111000100011
σi t 00100011
= yi
Analysis 1.4
01011101010001010110111
010111000100011
Wenn man aus den Beispielen
f(x1) = y1 , …0101110101000101011011101011100
, f(x ) = yn .
0100011n 0101110101000101011011101011100
0100011
einen Term t(x) mit Substitutionen
σ1 , … , σ n
und der Bedingung σi t = yi
01011101010001010110111010111000100011
gefunden
hat, dann hat man t “gelernt”, …
01011101010001010110111010111000100011
010111010100010101101110101110
… was aber nur eine Hypothese
sein kann.
01011101010001010110111010111000100011
00100011
Analysis 1.5
01011101010001010110111
010111000100011
Ein - eventuell vorläufiges - Ergebnis besteht
0101110101000101011011101011100
darin zu sagen, man hätte
aus den Beispielen
0100011 0101110101000101011011101011100
0100011
f(0) = 0 , f(1) = 1 , f(2) = 2 , f(3)
= 720! , …
die Beschreibung
01011101010001010110111010111000100011
g(x,0)
= x
01011101010001010110111010111000100011
g(x,n+1) = g(x,n)!
f(x) =010111010100010101101110101110
g(x,x)
01011101010001010110111010111000100011
00100011
der Funktion f “gelernt”.
Beispiel 3.1
01011101010001010110111
010111000100011
Ein Beispieltext (Zeichenkette, Datensatz, … ):
0101110101000101011011101011100
0100011 0101110101000101011011101011100
0100011
@article
( Angluin/Smith83,
author =
{Angluin, Dana and Smith, Carl H.},
title =
{A Survey of Inductive Inference:
Theory and Methods},
01011101010001010110111010111000100011
journal =
{Computing Surveys},
01011101010001010110111010111000100011
year =
{1983},
volume =
{15},
010111010100010101101110101110
01011101010001010110111010111000100011
pages =
{237--269} )00100011
Beispiel 3.2
01011101010001010110111
010111000100011
… und ein weiteres Beispiel für dasselbe Konzept:
0101110101000101011011101011100
0100011 0101110101000101011011101011100
0100011
@article
( Klette/Wiehagen80,
author =
{Klette, Reinhard and Wiehagen, Rolf},
title =
{Research in the Theory of Inductive
Inference by {GDR} Mathematicians
01011101010001010110111010111000100011
- A Survey},
01011101010001010110111010111000100011
journal =
{Information Sciences},
year =
{1980},
010111010100010101101110101110
01011101010001010110111010111000100011
00100011
volume =
{22},
pages =
{149--169} )
Beispiel 3.3
01011101010001010110111
010111000100011
Was für ein Konzept soll gelernt werden ?!
0101110101000101011011101011100
0100011 0101110101000101011011101011100
0100011
• basierend auf Zeichenketten
eine CHOMSKY-Grammatik
Text-Muster
...
01011101010001010110111010111000100011
01011101010001010110111010111000100011
• basierend auf Relationen (relationalen DB)
010111010100010101101110101110
Datenabhängigkeiten
(welcher Art?)
01011101010001010110111010111000100011
00100011
...
Analysis 3.1
01011101010001010110111
010111000100011
Ein erster intuitiver (naiver …?!) Ansatz für ein Muster
0101110101000101011011101011100
(engl.: Pattern) p1:
0100011
0101110101000101011011101011100
0100011
@article
( x1/x2x3,
author =
{x1, x4 and x2, x5},
title
=
{x6},
01011101010001010110111010111000100011
journal =
{x7},
01011101010001010110111010111000100011
year =
{19x3},
volume =
{x8}, 010111010100010101101110101110
pages =
{x9--x00100011
01011101010001010110111010111000100011
10} )
Criticism of the Naïve Approach
01011101010001010110111
010111000100011
Die Wahl von p1 beruht auf einer Reihe von impliziten
Annahmen, sozusagen auf “Vorurteilen”.
Wieso?!
0101110101000101011011101011100
0100011
0101110101000101011011101011100
0100011
• Zum Beispiel ist “x1/x28x3” spezifischer als “x1/x2x3”.
• Sowohl
{x61 of Inductive Inference x62}
01011101010001010110111010111000100011
01011101010001010110111010111000100011
• als auch
• ist viel genauer als
01011101010001010110111010111000100011
{x61 Theory x62}
010111010100010101101110101110
{x00100011
6} .
Analysis 3.2
01011101010001010110111
010111000100011
Eine Hypothese, die weniger intuitiv, aber akurater
0101110101000101011011101011100
die Beispiele widerspiegelt, ist
p:
01000112
0101110101000101011011101011100
0100011
@article
( x1/x28x3,
author =
{x1, x4 and x2, x5},
title
=
{x6 of Inductive Inference x7},
01011101010001010110111010111000100011
journal =
{x8 x9},
01011101010001010110111010111000100011
year =
{198x3},
volume =
{x10},010111010100010101101110101110
pages =
{x11--x
01011101010001010110111010111000100011
1269} )
00100011
Analysis 3.3
01011101010001010110111
010111000100011
Eine konkurrierende Hypothese, unvergleichbar zu p2,
0101110101000101011011101011100
ist p3:
0100011
0101110101000101011011101011100
0100011
@article
( x1/x28x3,
author =
{x1, x4 and x2, x5},
title
=
{x6 Theory x7},
01011101010001010110111010111000100011
journal =
{x8 x9},
01011101010001010110111010111000100011
year =
{198x3},
volume =
{x10},010111010100010101101110101110
pages =
{x11--x
01011101010001010110111010111000100011
1269} )
00100011
Discussion
01011101010001010110111
010111000100011
Sowohl die Hypothese p1 als auch die Hypothese p2
charakterisiert die zwei Beispiele
nicht so gut wie
0101110101000101011011101011100
0100011 0101110101000101011011101011100
möglich.
0100011
• Zum Beispiel ist “journal = {x81ox82tix83 Sx91ex92s}”
spezifischer
als “journal = {x8 x9}”.
01011101010001010110111010111000100011
• Die Teilstruktur “title = {x61A Survey x62}”
ist sinnvoll, falls leere Substitutionen
zugelassen
010111010100010101101110101110
01011101010001010110111010111000100011
00100011
werden.
01011101010001010110111010111000100011
Short Digression
01011101010001010110111
010111000100011
Wie vernünftig sind “vernünftige” Ideen, d.h. konkret:
0101110101000101011011101011100
Um wieviel wächst die Ausdruckskraft
von Patterns,
0100011 0101110101000101011011101011100
wenn man leere Substitutionen zuläßt?!
0100011
Hat diese Verallgemeinerung des Ansatzes irgendeine Auswirkung auf die Problematik, solche Patterns
01011101010001010110111010111000100011
zu01011101010001010110111010111000100011
lernen?!
Allgemeiner: Wie weit reicht der “gesunde Menschen010111010100010101101110101110
01011101010001010110111010111000100011
verstand”, und von welcher Stelle
an wird Wissenschaft
00100011
unverzichtbar?
Postulates of Naturalness
01011101010001010110111
010111000100011
Übersicht:
In dieser Vorlesung können nur ein paar
0101110101000101011011101011100
Eine recht umfassende
Beispiele behandelt werden.
0100011 0101110101000101011011101011100
Darstellung findet man schon im Artikel
JANTKE/BEICK,
0100011
“Combining Postulates of Naturalness in Inductive Inference”.
Wir diskutieren:
01011101010001010110111010111000100011
01011101010001010110111010111000100011
• Consistency
• Conservative Mind Changes010111010100010101101110101110
01011101010001010110111010111000100011
00100011
• Finiteness
• Incremental Hypothesis Construction
• ...
Consistency
01011101010001010110111
010111000100011
0101110101000101011011101011100
Ein induktives Lernverfahren
arbeitet konsistent
_________
0100011 0101110101000101011011101011100
0100011
genau dann, wenn
jede durch
dieses Verfahren
generierte Hypothese die Eigenschaft hat, daß sie
die Information,
auf der sie basiert, korrekt
01011101010001010110111010111000100011
widerspiegelt.
01011101010001010110111010111000100011
01011101010001010110111010111000100011
010111010100010101101110101110
00100011
Ein Beispiel zur Illustration
Zu 01011101010001010110111
lernen sind Textpatterns (Strings aus
010111000100011
Terminalen
und Variablen).
Es werden Beispiele w1, w2, w3, ... vorgelegt.
0101110101000101011011101011100
0100011 0101110101000101011011101011100
Wir betrachten folgendes Lernverfahren:
0100011
M(w1) := w1
(1) M (hn,wn+1) := merge (hn, wn+1 ) , falls |wn+1| = | hn |
01011101010001010110111010111000100011
(2)01011101010001010110111010111000100011
M (hn, wn+1) := hn, ,falls |wn+1| > | hn |
(3) M (hn, wn+1) := wn+1 , falls |wn+1| < | hn|
01011101010001010110111010111000100011
010111010100010101101110101110
00100011
merge geht von links nach rechts durch die
Zeichenketten und setzt neue Variablen in der
Hypothese, falls nötig. (genaue Def. Später)
Ein Beispiel zur Illustration
aabab01011101010001010110111
Hypothese:
aabab
010111000100011
ababb
0101110101000101011011101011100
Hypothese: aXYXb
0100011 0101110101000101011011101011100
aaa
0100011
Hypothese: aaa
bbaa
01011101010001010110111010111000100011
Hypothese: aaa
01011101010001010110111010111000100011
bba
Hypothese: XXa
010111010100010101101110101110
01011101010001010110111010111000100011
00100011
aab
Hypothese: XXY
...
Discussing Details
01011101010001010110111
010111000100011
Eine Lehre
0101110101000101011011101011100
0100011 0101110101000101011011101011100
0100011
Wir neigen bei der Behandlung komplizierter Fragen
dazu, implizit bestimmte Annahmen zu machen, welche
uns das Nachdenken erleichtern oder “dem gesunden
01011101010001010110111010111000100011
Menschenverstand
entsprechen”,
01011101010001010110111010111000100011
die aber unzulässig sein können ...
01011101010001010110111010111000100011
010111010100010101101110101110
00100011
Conservativeness
01011101010001010110111
010111000100011
0101110101000101011011101011100
konservativ
__________
0100011 arbeitet
0101110101000101011011101011100
0100011
genau dann, wenn
jeder durch
dieses Verfahren
vollzogene Hypothesenwechsel dadurch motiviert
ist, daß die
neu vorgelegte Information mit der
01011101010001010110111010111000100011
bisherigen
Hypothese nicht konsistent war.
01011101010001010110111010111000100011
01011101010001010110111010111000100011
010111010100010101101110101110
00100011
Incremental Hypothesis Construction
01011101010001010110111
010111000100011
0101110101000101011011101011100
inkrementell
0100011arbeitet
0101110101000101011011101011100
genau dann, wenn
es nur das0100011
jeweils vorgelegte
Beispiel in die letzte Hypothese einarbeitet.
01011101010001010110111010111000100011
01011101010001010110111010111000100011
01011101010001010110111010111000100011
010111010100010101101110101110
00100011
Finiteness
01011101010001010110111
010111000100011
0101110101000101011011101011100
finit
____ genau
0100011 arbeitet
0101110101000101011011101011100
0100011
dann, wenn
es ein zugehöriges
Entscheidungsverfahren gibt, das zu jedem möglichen vorgelegten
Informationsangebot
feststellt, ob die generierte
01011101010001010110111010111000100011
Hypothese
bereits richtig ist und demzufolge end01011101010001010110111010111000100011
gültig beibehalten werden kann.
01011101010001010110111010111000100011
010111010100010101101110101110
00100011
Observation … Theorem
01011101010001010110111
Frage:
Wie ist das Verhältnis der Anforderungen
010111000100011
zueinander?
0101110101000101011011101011100
0100011 0101110101000101011011101011100
0100011
01011101010001010110111010111000100011
Beispielantwort:
01011101010001010110111010111000100011
Wenn
ein Lernverfahren finit arbeitet, dann kann es
in ein konsistentes Verfahren
transformiert werden.
010111010100010101101110101110
01011101010001010110111010111000100011
Die Umkehrung gilt nicht. 00100011

Algorithmisches Lernen Algorithmic Learning Theorie des

Transcrição

Documentos relacionados

Tätigkeit als Werkstudent/in bei Siemens AG

索引 ABC Index

Game Based Learning

5. scil Trendstudie 2015/2016

Neue Lernformen für die berufliche Bildung: Mobile Learning

Helen Doron - pVS Kritzendorf

COMPUTERBILD 13/2007 : "Sehr gut für Anfänger geeignet

Learning Layers

Una belezza senza fine- Roma

Rossa 2012 Effective Language Teaching