Lernen auf der Wissensebene - Angewandte Informatik / Kognitive

Lernen auf der Wissensebene
Learning on the Knowledge Level
Ute Schmid
Cognitive Systems
Fakultät Wirtschaftsinformatik und Angewandte Informatik
Otto-Friedrich Universität Bamberg
20. Juni 2013
U. Schmid (Uni BA)
Lernen auf der Wissensebene
20. Juni 2013
1 / 31
U. Schmid (Uni BA)
Lernen auf der Wissensebene
20. Juni 2013
2 / 31
Wissen
Wissen ist . . .
dem Bewusstsein zugänglich
symbolisch repräsentiert, deklarativ
inspizierbar
verbalisierbar, kommunizierbar
natürlich in regelbasierte Systeme integrierbar
Routen: können anderen beschrieben werden
Grammatikregeln: können von den meisten Muttersprachlern korrekt
angewendet werden; können von Sprachwissenschaftlern als
symbolische Regeln formuliert werden
Problemlösungen: können anderen beschrieben werden
Problemlösestrategien: werden eher unbewusst angewendet
Diagnosen: basieren häufig auf teilweise unbewussten Eindrücken
(an expert does not think, he knows)
U. Schmid (Uni BA)
Lernen auf der Wissensebene
20. Juni 2013
3 / 31
Newell’s Knowledge Level
Allen Newell (1981): Definition des knowledge level zur Beschreibung
und Vorhersage des Verhaltens von Computer-Systemen auf der
Ebene von Zielen, Wissen und Aktionen
Schwerpunkt: Repräsentation, ausgeklammert: Aquisition (Lernen)
Viele Kognitive Architekturen addressieren Lernen nicht,
oder nicht auf der Wissensebene (Parameter-Tuning)
Maschinelles Lernen: meist statistisch – black box learning
How can a cognitive system process environmental input and stored
knowledge so as to benefit from experience?
(Holland, Holyoak, Nisbett & Thagard, 1986, Induction – Processes of Inference, Learning, and
Discovery)
Lernen findet auf vielen Ebenen statt: Basale Lernprozesse (auf
Sensordaten) — Symbolbasierte Ansätze (auf der Wissensebene)
Im Folgenden: Induktives Lernen auf der Wissensebene
U. Schmid (Uni BA)
Lernen auf der Wissensebene
20. Juni 2013
4 / 31
Überblick
1
Induktiver Wissenserwerb
2
Induktives Programmieren
3
Analoges Lernen – Generalisierung
4
Anwendung: Incident Mining
5
Anwendung: Schmerzmimik
6
Anwendung: Diagnose von Pflanzen
7
Zusammenfassung
U. Schmid (Uni BA)
Lernen auf der Wissensebene
20. Juni 2013
5 / 31
Lernen produktiver Regelmengen
Generalisierung über erlebte Regularitäten
I
I
I
Rekursive Prädikate: odd/even, Vorfahr
Syntaktische Struktur von Sätzen
Lösungsprozedur für den Turm von Hanoi
Produktiv (im Sinne von Chomsky): endliche Regelmenge zur
Erzeugung von potentiell unendlich vielen Instanzen verschiedener
Komplexität
Generalisierung aus wenigen positiven Beispielen
(cf. Marcus, The Algebraic Mind, 2001)
Anwendung eines Verfahrens zur analytischen induktiven
Programmierung
(Igor, Kitzelmann & Schmid, JMLR 2006; Schmid & Kitzelmann, CSR 2012;
IK’13 Special Course)
U. Schmid (Uni BA)
Lernen auf der Wissensebene
20. Juni 2013
6 / 31
Induktives Programmieren
Anwendung von maschinellem Lernen auf das Problem der
Programmsynthese
Automatische Erzeugung (rekursiver) Programme aus
Eingabe-/Ausgabe-Beispielen (unvollständigen Spezifikationen)
Ansätze:
I
I
analytisch, daten-getrieben: Thesys, Golem, Igor (ILP und induktive
funktionale Ansätze)
generate-and-test: FFoil (ILP), Adate (evolutionär), MagicHaskeller
(systematische Aufzählung)
E/A Beispiele:
last [a]
last [a,b]
last[a,b,c]
last[a,b,c,d]
=
=
=
=
U. Schmid (Uni BA)
a
b
c
d
Induziertes Programm:
last[x]
= x
last(x:xs) = last(xs)
Lernen auf der Wissensebene
20. Juni 2013
7 / 31
Igor2
Analytischer Ansatz zum Lernen funktionaler Programme (Maude,
Haskell)
Effiziente Induktion rekursiver Regelmengen aus wenigen positiven Beispielen
Lernt lineare, Baum-, und wechselseitig rekursive Regelmengen
Automatische Induktion von Hilfsfunktionen (necessary function invention)
Kann Hintergrundwissen berücksichtigen (analog zum ILP-System Golem)
Restriction Bias: funktionale rekursive Programme, bei denen die äußere
Funktion entweder nicht-rekursiv oder aus dem Hintergrundwissen ist
Nicht-rekursive Programme zur Klassifikation als Spezialfall (z.B.
playTennis, Mitchell, 1997)
Präferenz-Bias: Weniger Fallunterscheidungen, spezifischere Patterns,
weniger rekursive Aufrufe
U. Schmid (Uni BA)
Lernen auf der Wissensebene
20. Juni 2013
8 / 31
odd/even
mult/add
allodds
—
×
8.1⊥
—
⊙
—
214.87
×
0.1⊥
0.016⊥
⊙
×
multlast
shiftr
weave
reverse
78.0
80.0
18.81
—
134.24⊥ 448.55⊥
—
0.4⊥ < 0.1⊥
—
0.66⊥
0.298
0.103
0.200
0.127
0.08
⊙
157.32
member
70.0
×
×
0.714
0.105
0.01
lasts
A DATE
F LIP
F FOIL
G OLEM
I GOR II
M AG H.
last
isort
Empirische Ergebnisse
A DATE 822.0
0.2
2.0
—
4.3
F LIP
×
0.020 17.868
0.130 448.90⊥
F FOIL
0.7⊥
0.1
0.1⊥ < 0.1⊥ < 0.1
G OLEM
1.062 < 0.001
0.033
—
< 0.001
I GOR II
5.695
0.007
0.152
0.019
0.023
M AG H. 19.43
0.01
⊙
—
0.30
— not tested × stack overflow ⊙ timeout ⊥ wrong
all runtimes in seconds
U. Schmid (Uni BA)
Lernen auf der Wissensebene
20. Juni 2013
9 / 31
Igor2 als Cognitive Rule Acquisition Device
Analytische induktive Programmierung bietet einen allgemeinen
Mechanismus um generalisierte Regelmengen aus Beispielen für ein
gewünschtes Verhalten zu extrahieren
Typische Bereiche, in denen aus positiven Beispielen gelernt wird
I
I
I
Semantische Relationen (Ist-Ein, Vorfahr)
Sprache (regelmäßige Beugungen, grammatische Strukturen)
Problemlösen (Turm von Hanoi)
U. Schmid (Uni BA)
Lernen auf der Wissensebene
20. Juni 2013
10 / 31
Beispiel: Blockswelt
Ziel: Baue einen Turm aus Blöcken in einer gegebenen Reihenfolge
Gegeben: beliebiger Anfangszustand, beliebig viele Blöcke
Strategie: Räume denjenigen Block frei, der ganz unten liegen soll
und stelle ihn auf den Tisch, stelle dann immer den nächst-benötigten
Block auf den Teilturm und sorge dafür, dass dieser Block frei ist.
(Nicht-optimale Strategie: Lege erst alle Blöcke auf den Tisch und
baue dann den Turm mit gewünschter Reihenfolge der Blöcke auf.)
Tower (9 examples of towers with up to four blocks, 1.2 sec)
(10 corresponding examples for Clear and IsTower as BK)
Tower(O, S) = S
if IsTower(O, S)
Tower(O, S) = put(O, Sub1(O, S),
Clear(O, Clear(Sub1(O, S),
Tower(Sub1(O, S), S))))
if not(IsTower(O, S))
Sub1(s(O), S) = O .
U. Schmid (Uni BA)
Lernen auf der Wissensebene
20. Juni 2013
11 / 31
Lernen aus Problemlöseerfahrung
Generierung von optimalen Plänen für kleine“ Probleme, z.B. mit
”
einem PDDL-Planer:
I
I
I
Tower: Türme mit bis zu vier Blöcken
Turm von Hanoi: ein bis drei Scheiben
Rocket: ein bis drei Kisten
Igor2 liefert generalisierte Problemlösestrategie
Ergebnis: Problemlösen durch Suche wird unnötig
Plötzliches Gefühl, ein Problem verstanden zu haben (Aha-Effekt):
Regularitäten wurden zu einem (Problemlöse-) Schema generalisiert
(Schmid, Wysotzki, AIPS 2000; Schmid et al., AGI 2009; Schmid & Kitzelmann, CSR 2012)
U. Schmid (Uni BA)
Lernen auf der Wissensebene
20. Juni 2013
12 / 31
Beispielanwendungen
Tower, Hanoi, Car Parking, Phrase-Structure Grammar, isa
(Schmid & Kitzelmann, 2012, CSR)
Lernen von odd/even durch einen simulierten Agenten in einer
Kreiswelt“(mit Mark Wernsdorfer)
”
Induktion von Zahlenreihen (mit Jacqueline Hofmann, Jose
Hernandez-Orello)
Ragni & Klein, KI’11 Examples (ANN)
By ANN and Igor: 7,10,9,12,11 f (n − 1) + 3, f (n − 1) − 1
By Igor but not by ANN: 3,7,15,31,63 2 ∗ f (n − 1) + 1
By ANN but not by Igor: 6,9,18,21,42 f (n − 1) + 3, f (n − 1) ∗ 2
Not by ANN and not by Igor: 2,5,9,19,37 f (n − 1) ∗ 2 + 1, f (n − 1) ∗ 2 − 1
U. Schmid (Uni BA)
Lernen auf der Wissensebene
20. Juni 2013
13 / 31
Vergleich mit anderen Ansätzen
Generalisierung über vorhandene Problemlöseerfahrung statt
suchbasiertes Erzeugen möglicher Strategien!
Automatische Induktion generalisierter Handlungsregeln
In kognitiven Architekturen (ACT-R, SOAR) stattdessen nur:
I
I
Veränderung von Stärkewerten
Chunking von Regeln zu komplexeren Einheiten
,→ Kein Erwerb neuer Regeln!
U. Schmid (Uni BA)
Lernen auf der Wissensebene
20. Juni 2013
14 / 31
Lernen beim Analogen Problemlösen
Analoges Problemlösen als Anfängerstrategie:
Lösung eines Problems (Ziel) durch Anpassung einer bekannten
Lösung eines ähnlichen Problems (Basis)
Wenn ein Problemlöser bereits über allgemeine Regeln oder Schemata
verfügt, können diese direkt angewendet werden
Analoges Problemlösen als Auslöser zum Generalisierungslernen
Analogy via Abstraction (AvA)
(Schmid et al. 2003, Weller & Schmid, KI 2006,
ICCM 2006, Wiese et. al, CogSci 2008)
U. Schmid (Uni BA)
Lernen auf der Wissensebene
20. Juni 2013
15 / 31
Analogy via Abstraction
Statt direktem Mapping von Wissensstruktur (Problemspezifikation
und Lösung) des Basisproblems und partieller Wissensstruktur des
Zielproblems (Problemspezifikation): Generalisierung der
gemeinsamen Struktur via Anti-Unifikation
Substitutionen/Mappings der Problemspezifikation werden auf die
Problemlösung angewendet und damit die Lösung des Zielproblems
erzeugt
Wissenserwerb: Aufbau allgemeiner Lösungsschemata
AvA Anwendungen
Proportionalanalogien (Letterstring-Domäne)
Physik
Programmieren
U. Schmid (Uni BA)
Lernen auf der Wissensebene
20. Juni 2013
16 / 31
Soviel wie möglich vs. soviel wie nötig
AvA generalisiert und überträgt so viel wie möglich
(vgl. Systematizitätsprinzip bei SME)
Empirische Frage: Generalisieren Problemlöser ebenfalls so viel wie
möglich oder nur so viel wie nötig?
Anwendung Physik: Wasserfluss/Stromfluss
U. Schmid (Uni BA)
Lernen auf der Wissensebene
20. Juni 2013
17 / 31
Experiment
Problemstellungen
Typ-1 Probleme: Stromstärke (I) und Spannung (V)
Typ-2 Probleme: Stromstärke (I) und Widerstand (R)
Hypothese
Wenn soviel wie möglich generalisiert und übertragen wird, dann sollte
analoges Problemlösen für Typ-1 Probleme die Bearbeitung nachfolgender
Typ-2 Probleme erleichtern und umgekehrt.
Tutorial type
Testing time 1
Testing time 2
U. Schmid (Uni BA)
Experimental
E1
E2
Water Circuit
type-1 type-2
type-2 type-1
Control
C1
C2
Electric Circuit
type-1 type-2
type-2 type-1
Lernen auf der Wissensebene
20. Juni 2013
18 / 31
Ergebnis
70 Teilnehmer
Abhängige Variable: Lösungszeit
Kein speed-accuracy trade-off
Auswertung mit ALM, Dummy-Kodierung für Probanden (nur korrekt
gelöste Probleme)
Signifikanter Interaktionseffekt zwischen Testzeitpunkt und
Tutorienart (p = 0.041) bestätigt die so viel wie möglich“ Hypothese
”
(Wiese, Konerding, Schmid, CogSci’08)
U. Schmid (Uni BA)
Lernen auf der Wissensebene
20. Juni 2013
19 / 31
Erwerb generalisierter Strukturen
AvA: Mapping via kleinster gemeinsamer Generalisierung
Automatische Identifikation von Rollen
attracts(sun, planet-i) und attracts (nucleus, electron-i) generalisiert
zu attracts(central-body, orbiter)
Generalisierte Strukturen entsprechen Schemata
Schemaerwerb ist mehr als Variabilisierung von Slot-Inhalten!
G−Spec
σ
σ’
σ
σ’
B−Spec
B−Sol
T−Spec
T−Sol
G−Sol
U. Schmid (Uni BA)
Lernen auf der Wissensebene
20. Juni 2013
20 / 31
Anwendung Symbolischer Lernverfahren
Symbolische Lernverfahren
Entscheidungsbäume
Inductive Logic Programming
Grammar Inference
Lernen symbolischer Repräsentationen
Klassifikationsregeln
Produktive Regeln
Schemata
Prototypen
Inspizierbar, kommunizierbar, in Regelsysteme integrierbar
U. Schmid (Uni BA)
Lernen auf der Wissensebene
20. Juni 2013
21 / 31
Anwendung: Incident Mining
Zusammenarbeit mit SAP: Incident-Mining als Vorbereitung auf
Business ByDesign
Support ist häufig über viele Personen und Orte verteilt
hoher Kostenfaktor, kann ausschlaggebend für Kundenzufriedenheit
sein
Problem: Kenntnis der Support-Ingenieure über bereits vorhandene
Lösungen
Intelligente Software-Unterstützung für Support-Ingenieure:
I
I
Automatischer Support bei Standard-Problemen
Zugang zu existierenden Lösungen für bereits aufgetretene und
behobene Probleme
(Schmid et al., IEA-AIE 2010)
U. Schmid (Uni BA)
Lernen auf der Wissensebene
20. Juni 2013
22 / 31
Structural Incident Mining
Typische Ansätze im data mining sind merkmalsbasiert
Incident reports liegen als XML-Bäume – basierend auf einem
Incident Modell – vor
,→ Transformation von Strukturen in Merkmale führen immer zu
einem Informationsverlust
Unser Ansatz: Extraktion struktureller Prototypen
I
I
I
Anti-unification (AU): Schnittmenge von Bäumen
Structure dominance generalisation (SDTG): Vereinigung von Bäumen
SDTG-AU: moderate Generalisierung; Generalisierung über Knoten mit
verschiedenen Labeln, Berücksichtigung von Auftretenshäufigkeiten von
Labeln
U. Schmid (Uni BA)
Lernen auf der Wissensebene
20. Juni 2013
23 / 31
Ergebnisse
Leave-one-out
Method
FOIL
AU
SDTG
SDTG-AU
Hits
11
29
22
31
Errors
8, 141
4
11
2
Av. Size
Hits
0
4
52
56
Errors
0, 571
53
5
1
Av. Size
173
387
264
Generation (sec.)
0,109
0,485
0,456
0,419
Retrieval (sec.)
0,409
0,044
0,049
0,047
Generation (sec.)
0,020
0,202
0,227
0,188
Retrieval (sec.)
7,378
0,051
0,102
0,069
Noisy Data
Method
FOIL
AU
SDTG
SDTG-AU
1
66
619
410
first value: classification error, second value: ambiguous result
(Retrieval for AU based on subsumption, retrieval for SDTG/SDTG-AU on Manhatten distance)
U. Schmid (Uni BA)
Lernen auf der Wissensebene
20. Juni 2013
24 / 31
Anwendung: Schmerzmimik
Klassifikation von Schmerz aus Mimikdaten
Zusammenarbeit mit der Biopsychologie, Uni BA (Lautenbacher &
Kunz)
Empirische Belege, dass Mimik ein guter Prädiktor für Schmerz ist
(in Abwesenheit der Möglichkeit von Selbstauskünften)
Anwendungsszenarien: Post-operativ, Personen mit dementiellen
Syndromen (Altzheimer)
Typisches Vorgehen in der Psychologie: Identifikation von action units
(AUs, Facial Action Coding System, FACS, Ekman & Friesen)
Häufigstes Vorgehen bei maschinellen Verfahren zur Facial Expression
Classification: Black-Box aus extrahierten Merkmalen aus
Bildern/Videos
U. Schmid (Uni BA)
Lernen auf der Wissensebene
20. Juni 2013
25 / 31
Gibt es eine Grammatik“ des Schmerzes?
”
Ansätze in Psychologie wie Facial Expression Analysis betrachten
bisher das Auftreten von Merkmalen/AUs in einem Zeitfenster als bag
of words
Liefert die Sequenz von AUs relevante Information?
Anwendungen
I
I
Grundlage für psychologische Theoriebildung
Realistische Animation von Avataren, Robotern
Grammatiklernen über FACS-kodierte Daten aus einem
Schmerzexperiment mit 86 Probanden
U. Schmid (Uni BA)
Lernen auf der Wissensebene
20. Juni 2013
26 / 31
Action Units für Schmerz
AUs with a critical occurence of more than 5% in denominated pain segments in
healthy controls and demented patients (abbreviated from Table 1 in Kunz et al.
2007).
AU
AU1, AU2
AU6, AU7
AU17
AU45
Description
brow raiser
orbit tightening
chin raise
eye blink
U. Schmid (Uni BA)
AU
AU4
AU9, AU10
AU25, AU26, AU27
Lernen auf der Wissensebene
Description
brow lower
levator contraction
mouth opening
20. Juni 2013
27 / 31
Schmerzsequenzen: Erste Ergebnisse
Induktion einer Schmerzgrammatik mit ABL: 5-fold cross validation,
mittlere coverage 0.651 (Schmid et al., ICGI’12)
Avatar-Experiment (Bachelor-Arbeit)
U. Schmid (Uni BA)
Lernen auf der Wissensebene
20. Juni 2013
28 / 31
Schmerzsequenzen: Erste Ergebnisse
U. Schmid (Uni BA)
Lernen auf der Wissensebene
20. Juni 2013
29 / 31
Anwendung: Diagnose von Pflanzen
Zusammenarbeit mit Fraunhofer IIS, Erlangen (Franz Uhrmann,
Oliver Scholz, Christoph Stocker)
Tabakpflanzen in Afrika zur Herstellung von Impfstoffen
Automatische Identifikation von Stress (um geschädigte Pflanzen zu
eliminieren)
Woran sieht ein Biologe frühzeitig, dass eine Pflanze gestresst ist?
Vorgehen: Entscheidungsbaum-Lernen aus Merkmalen, Klassen sind
vom Experten gegeben
U. Schmid (Uni BA)
Lernen auf der Wissensebene
20. Juni 2013
30 / 31
Zusammenfassung
Lernen auf der Wissensebene
Ansatz zur Modellierung kognitiver Lernprozesse
I
I
Beispiel 1: Lernen produktiver Regeln mit Igor
Beispiel 2: Analogy via Abstraction
Ansatz zur Identifikation von symbolischen Mustern und Regeln
I
I
I
Beispiel 1: Lernen struktureller Prototypen für das Incident Mining
Beispiel 2: Lernen von Schmerzgrammatiken zur realistischen
Animation
Beispiel 3: Lernen von Expertenregeln zur Bewertung von
Pflanzen-Stress
U. Schmid (Uni BA)
Lernen auf der Wissensebene
20. Juni 2013
31 / 31