Grundlagen des Maschinellen Lernens
Kap 3: Lernverfahren in anderen Domänen
Automatensynthese
1.
2.
Motivation
Lernmodelle – Teil I
2.1. Lernen im Limes
2.2. Fallstudie: Lernen von0101110101000101011011101011100
Patternsprachen
0100011
3. Lernverfahren in anderen Domänen
3.1. Automatensynthese
3.2. Entscheidungsbäume
3.3. Entscheidungsbäume über regulären Patterns
4. Lernmodelle – Teil II
4.1. Online-Lernen
01011101010001010110111010111000100011
4.2. PAC-Lernen
5. Spezielle Lernverfahren
5.1. unüberwachtes Lernen
5.2 überwachtes Lernen
5/1
Grundlagen des Maschinellen Lernens
Kap 3: Lernverfahren in anderen Domänen
Automatensynthese
Fahrplan
•
•
•
•
motivierendes Beispiel
0101110101000101011011101011100
Präzisierung des zu lösenden
Lernproblems
0100011
zugrunde liegende Begriffe (nur Wiederholung(!?))
Lernverfahren für endliche Automaten mit Ein- und Ausgabe
01011101010001010110111010111000100011
5/2
Grundlagen des Maschinellen Lernens
Kap 3: Lernverfahren in anderen Domänen
Automatensynthese
Problemstellung: Kaffeeautomat
ein wohlwollender Sponsor hat in D14 einen Kaffeeautomat zu freien
0101110101000101011011101011100
Benutzung aufgestellt
0100011
–
–
man kann sich Kaffee umsonst verschaffen ☺
es gibt leider keine Bedienungsanleitung
A
01011101010001010110111010111000100011
B
C
5/3
Grundlagen des Maschinellen Lernens
Kap 3: Lernverfahren in anderen Domänen
Automatensynthese
kurzfristiges Ziel
Wir wollen einen Becher mit Kaffee aus dem Automaten erhalten.
0101110101000101011011101011100
0100011
langfristiges Ziel
Wir wollen verstehen, wie der Automat funktioniert, um planmäßig (und
beliebig oft) aus dem Automaten einen Becher mit Kaffee erhalten zu
können.
01011101010001010110111010111000100011
Kann man die Funktionsweise des Automaten erlernen?
5/4
Grundlagen des Maschinellen Lernens
Kap 3: Lernverfahren in anderen Domänen
Automatensynthese
vom Kaffeeautomaten ist “bekannt” ...
Er hat 3 Knöpfe: A, B und C.
0101110101000101011011101011100
0100011
A
Es sind 4 verschiedene Ausgaben möglich:
B
C
Ertönen einer Glocke
Gl
Becher
Be
Zucker
Zu
01011101010001010110111010111000100011
Kaffee
Ka
5/5
Grundlagen des Maschinellen Lernens
Kap 3: Lernverfahren in anderen Domänen
Automatensynthese
A/Zu
B/Ka
2
A/Zu
0101110101000101011011101011100
C/Gl
start
0100011
A/Zu
B/Zu
01011101010001010110111010111000100011
C/Be
1
C/Gl
B/Gl
5/6
Grundlagen des Maschinellen Lernens
Kap 3: Lernverfahren in anderen Domänen
Automatensynthese
Präzisierung des zu lösenden Lernproblems
Klasse zu lernender Objekte
0101110101000101011011101011100
endlich deterministische Automaten A0100011
(mit Ausgabe)
Informationen
über das Verhalten eines unbekannten Automaten A werden
Interaktionsfolgen vorgelegt
01011101010001010110111010111000100011
Lernziel
es soll ein Automat B gelernt werden, der sich genauso wie A verhält
5/7
Grundlagen des Maschinellen Lernens
Kap 3: Lernverfahren in anderen Domänen
Automatensynthese
endliche Automaten ohne Ausgabe (zur Erinnerung)
A = [ X, Z, δ, {z0}, F ]
0101110101000101011011101011100
0100011
•
Eingabealphabet X
•
Zustandsmenge Z
•
Zustandsüberführungsfunktion δ: Z x X
Z
•
Anfangzustand z0 ∈ Z
01011101010001010110111010111000100011
•
Endzustände F ⊆ Z
5/8
Grundlagen des Maschinellen Lernens
Kap 3: Lernverfahren in anderen Domänen
Automatensynthese
b
a
1
2
a, b
3
b
4
a, b
5
0101110101000101011011101011100
0100011
a
b
a
•
X = { a, b }
•
Z = { 1, 2, 3, 4, 5 }
01011101010001010110111010111000100011
•
z0 = 1
•
F={5}
δ
a
b
1
2
1
2
3
3
3
3
4
4
5
5
5
5
2
5/9
Grundlagen des Maschinellen Lernens
Kap 3: Lernverfahren in anderen Domänen
Automatensynthese
endliche Automaten mit Ausgabe
A = [ X,Y,Z, δ, λ,{z0} ]
0101110101000101011011101011100
•
0100011
Eingabe-/Ausgabealphabet
X, Y
•
Zustandsmenge Z
•
Zustandsüberführungsfunktion δ: Z x X
•
Ausgabefunktion λ: Z x X
Z
Y
01011101010001010110111010111000100011
•
Anfangzustand z0 ∈ Z
5/10
Grundlagen des Maschinellen Lernens
Kap 3: Lernverfahren in anderen Domänen
Automatensynthese
b/0
a/0
1
2
a/0
b/0
3
b/0
4
a/1
5
b/0
0101110101000101011011101011100
0100011
b/0
a/1
a/0
•
X = { a, b }
•
Y = { 0, 1 }
01011101010001010110111010111000100011
•
Z = { 1, 2, 3, 4, 5 }
•
z0 = 1
δ/ λ
a
b
1
2/0
1/0
2
3/0
3/0
3
3/0
4/0
4
5/1
5/0
5
5/1
2/0
5/11
Hinweis: beschreibt dasselbe Akzeptierungsverhalten; letztes Bit der Ausgabe ist relevant
Grundlagen des Maschinellen Lernens
Kap 3: Lernverfahren in anderen Domänen
Automatensynthese
endliche Automaten mit Ausgabe
A = [ X,Y,Z, δ, λ, {z0} ]
0101110101000101011011101011100
•
0100011
Eingabe-/Ausgabealphabet
X, Y
•
Zustandsmenge Z
•
Zustandsüberführungsfunktion δ: Z x X
•
Ausgabefunktion λ: Z x X
Z
Y
01011101010001010110111010111000100011
•
Anfangzustand z0 ∈ Z
Verhalten von A: V(A) = { (w, λ*(z0,w)) | w ∈ X+ }
5/12
Grundlagen des Maschinellen Lernens
Kap 3: Lernverfahren in anderen Domänen
Automatensynthese
Fortsetzung der Ausgabe- und der Zustandsüberführungsfunktion
sei A = [ X,Y,Z, δ, λ,{z0} ]
0101110101000101011011101011100
0100011
λ*(z0,x) = λ(z0,x), falls x ∈ X
λ*(z0,wx) = λ*(z0,w) λ(δ*(z0,w),x), falls w ∈ X+, x ∈ X
δ*(z0,x) = δ(z0,x), falls x ∈ X
01011101010001010110111010111000100011
δ*(z0,wx) = δ(δ*(z0,w),x), falls
w ∈ X+, x ∈ X
5/13
Grundlagen des Maschinellen Lernens
Kap 3: Lernverfahren in anderen Domänen
Automatensynthese
Interaktionsfolgen (Eingabe für das Lernverfahren)
0101110101000101011011101011100
unendliche Folge {Vi} endlicher Mengen,
so daß für alle i gilt:
0100011
Vi ⊆ V(A)
Vi ist anfangsstückvollständig (/* d.h. falls (u,λ*(u)) ∈ Vi,
so (u‘,λ*(u‘)) ∈ Vi für alle Anfangsstücke u‘ von u */)
•
Vi ⊆ Vi+1
•
V1 ∪ V2 ∪ … = V(A)
01011101010001010110111010111000100011
•
•
5/14
Grundlagen des Maschinellen Lernens
Kap 3: Lernverfahren in anderen Domänen
Automatensynthese
Gundlagen
Es sei A ein endl. det. Automat.0101110101000101011011101011100
Dann gibt es einen (/* bis auf
0100011
Isomorphie */) eindeutig bestimmten minimalen endl. det.
Automaten A’ mit V(A’) = V(A).
Es gibt einen effizienten Algorithmus zur Bestimmung von A’.
•
•
01011101010001010110111010111000100011
5/15
Grundlagen des Maschinellen Lernens
Kap 3: Lernverfahren in anderen Domänen
Automatensynthese
Ist folgender endl. det. Automat A minimal?
a/1
0101110101000101011011101011100
0100011
minimal, falls gilt:
a/1
a/1
1
3
2
b/1
b/1
b/1
es gibt keinen äquivalenten
endl. det. Automat B mit
weniger Zuständen
b/0
01011101010001010110111010111000100011
4
a/1
b/1
5
a/1
5/16
Grundlagen des Maschinellen Lernens
Kap 3: Lernverfahren in anderen Domänen
Automatensynthese
es sei A = [ X,Y,Z, δ, λ,{z0} ]
•
•
zwei Zustände z, z’ heißen äquivalent,
falls für alle w ∈ X+
0101110101000101011011101011100
0100011
gilt: λ*(z,w) = λ*(z’,w)
zwei Zustände z, z’ heißen k-äquivalent, falls für alle w ∈ X+
mit |w| = k gilt: λ*(z,w) = λ*(z’,w)
Beobachtung:
01011101010001010110111010111000100011
Es seien z, z’ zwei k+1-äquivalente Zustände.
Dann gilt für alle x ∈ X:
•
•
λ(z,x) = λ(z’,x)
die Zustände δ(z,x) und δ(z’,x) sind k-äquivalent
5/17
Grundlagen des Maschinellen Lernens
Kap 3: Lernverfahren in anderen Domänen
Automatensynthese
Minimierungsalgorithmus (bekannt (!?))
a/1
1-äquivalent: { 1 } { 2, 3, 4, 5}
0101110101000101011011101011100
0100011
a/1
2-äquivalent: { 1 } { 2, 4, 5 } { 3 }
a/1
1
b/1
3-äquivalent:
{ 1 } { 2 } { 4, 5 } { 3 }
01011101010001010110111010111000100011
b/0
4
4-äquivalent: { 1 } { 2 } { 4, 5 } { 3 }
3
2
a/1
b/1
b/1
b/1
5
a/1
5/18
Grundlagen des Maschinellen Lernens
Kap 3: Lernverfahren in anderen Domänen
Automatensynthese
gegebener Automat A
zugehöriger minimaler Automat A/~
a/1
a/1
0101110101000101011011101011100
0100011
a/1
a/1
a/1
1
3
2
b/1
b/1
b/1
a/1
b/1
{2}
b/1
b/001011101010001010110111010111000100011
4
a/1
{1}
{3}
b/1
b/0
5
{ 4, 5 }
a/1
b/1
a/1
5/19
Grundlagen des Maschinellen Lernens
Kap 3: Lernverfahren in anderen Domänen
Automatensynthese
Ansatz für ein Lernverfahren
wir betrachten V(A) als Automaten 0101110101000101011011101011100
(/* V(A) ist äquivalent zu A */)
0100011
Ansatz: Wir minimieren V(A).
Beobachtung:
01011101010001010110111010111000100011
Das Ergebnis ist ein Automat B mit den Eigenschaften:
•
B ist äquivalent zu V(A) (und damit auch zu A).
•
B ist minimal.
5/20
Grundlagen des Maschinellen Lernens
Kap 3: Lernverfahren in anderen Domänen
Automatensynthese
Wir betrachten V(A) als Automaten.0101110101000101011011101011100
0100011
V(A) = [X,Y,X*,δ∞,λ∞,{ ε }] mit:
•
δ∞(z,x) = zx
•
λ∞(z,x) = y, falls y ∈ Y und (zx,vy) ∈ V(A) für ein v ∈ Y*
01011101010001010110111010111000100011
5/21
Grundlagen des Maschinellen Lernens
Kap 3: Lernverfahren in anderen Domänen
Automatensynthese
zugehöriger Automat V(A)
gegebener Automat A
a/1
a/1
0101110101000101011011101011100
ε
0100011 a/1
a/1
1
2
a/1
3
b/1
01011101010001010110111010111000100011
b/1
a/1
b/0
4
a/1
b/1
5
a/1
aaa
...
aa
a
b/1
b/1
a/1
b/0
b
b/1
ab
ba
bb
...
...
...
aab
...
5/22
Grundlagen des Maschinellen Lernens
Kap 3: Lernverfahren in anderen Domänen
Automatensynthese
zugehöriger Automat V(A)
gegebener Automat A
a/1
a/1
a/1
1
b/0
0101110101000101011011101011100
ε
1
0100011
1
3
2
b/1
01011101010001010110111010111000100011
b/1
1
4
5
a/1
b/1
a/1
a
aa
aaa
1
0
b
1
1
1
ab
ba
bb
...
...
...
aab
...
...
5/23
Hinweis: einfachere, „äquivalente“ Darstellung von V(A)
Grundlagen des Maschinellen Lernens
Kap 3: Lernverfahren in anderen Domänen
Automatensynthese
Wir betrachten V(A) = [X,Y,X*,δ∞,λ∞,{ε}].
0101110101000101011011101011100
~ bezeichnet die Zustandsäquivalenz
auf X*.
0100011
V(A)/~ bezeichnet den nach ~ „faktorisierten“ Automaten
Beobachtung:
01011101010001010110111010111000100011
Es gibt eine endliche Teilmenge V von V(A), so daß gilt: V(A)/~ = V/~.
Außerdem gilt für alle V‘ mit V‘ ⊇ V: V‘/~ = V/~.
5/24
Grundlagen des Maschinellen Lernens
Kap 3: Lernverfahren in anderen Domänen
Automatensynthese
„Rahmen“ für ein Lernverfahren
betrachten V(A) = [X,Y,X*,δ∞,λ∞,{ ε }]
und V1 ⊆ V2 ⊆ V3 ⊆ V4 ⊆ V5 ⊆ ...
0101110101000101011011101011100
⊆0100011
V(A).
Schritt 1:
Input:
V1
Output:
Bilde V1/~. Gib h1 = V1/~ aus.
Schritt
n
+
1:
01011101010001010110111010111000100011
Input:
Vn+1; hn
Output:
Teste, ob der Automat hn mit den vorliegenden
Informationen verträglich ist, d.h. teste, ob
Vn+1 ⊆ V(hn) gilt.
Falls ja, gib hn+1 = hn aus.
Sonst bestimme Vn+1/~ und gib hn+1 = Vn+1/~ aus.
5/25
Grundlagen des Maschinellen Lernens
Kap 3: Lernverfahren in anderen Domänen
Automatensynthese
Bestimmung von Vi/~:
0101110101000101011011101011100
0100011
und versucht, Vi zu
Man betrachtet Vi als (partiellen) Automaten
minimieren, d.h. Vi/~ zu konstruieren.
... aber aufgrund fehlender Information ist noch zu klären, wie man
die Relation ~ bzw. eine Approximation davon berechnet …
01011101010001010110111010111000100011
5/26
Grundlagen des Maschinellen Lernens
Kap 3: Lernverfahren in anderen Domänen
Automatensynthese
1-äquivalent:
{ ε } { a, b, aa }
ε
1
0
0101110101000101011011101011100
0100011
2-äquivalent:
1
a
1
1
ab
ba
b
1
{ε } {a, ??? }
1
aa
01011101010001010110111010111000100011
aaa
Idee:
1
bb
aab
Zustände gelten als äquivalent, solange nichts dagegen spricht
5/27
Grundlagen des Maschinellen Lernens
Kap 3: Lernverfahren in anderen Domänen
Automatensynthese
Beispiel 1
zugehöriger minimaler Automat V1/~
Input V1
1
a
0101110101000101011011101011100
0100011
ε
{ ε, b }
0
1
b
a/1
b/0
0
01011101010001010110111010111000100011
ba
bb
5/28
Grundlagen des Maschinellen Lernens
Kap 3: Lernverfahren in anderen Domänen
Automatensynthese
Beispiel 2
zugehöriger minimaler Automat V2/~
Input V2
0101110101000101011011101011100
0100011
ε
1
{ ε, b }
0
a/1
b/0
1
a
1
1
b
0
{a}
01011101010001010110111010111000100011
aa
ab
ba
a/1
b/1
bb
5/29
Grundlagen des Maschinellen Lernens
Kap 3: Lernverfahren in anderen Domänen
Automatensynthese
Beispiel 3
zugehöriger minimaler Automat V3/~
Input V3
0101110101000101011011101011100
0100011
ε
1
{ ε, b, aa }
0
b/0
1
a
1
1
b
0
a/1
a/1
{a}
01011101010001010110111010111000100011
aa
0
ab
ba
bb
b/1
aab
5/30
Grundlagen des Maschinellen Lernens
Kap 3: Lernverfahren in anderen Domänen
Automatensynthese
Bestimmung von Vi/~:
0101110101000101011011101011100
0100011
es gibt offenbar verschiedene Möglichkeiten,
die Zustände von Vi
zusammenzufassen und nicht definierte Werte im hypothetischen
Automaten Vi/~ festzulegen (/* Heuristiken, ... */)
Festlegungen führen zu unterschiedlichen Lernverfahren
01011101010001010110111010111000100011
... Grundkonzept: nachweisbare Inäquivalenz
... technische Voraussetzung: lexikographische Ordnung
5/31
Grundlagen des Maschinellen Lernens
Kap 3: Lernverfahren in anderen Domänen
Automatensynthese
Bestimmung von Vi/~:
Bezeichnung:
0101110101000101011011101011100
0100011
„u1 ∇ u2“, falls aus dem mit Vi verfügbaren Wissen folgt, daß die mit
u1 und u2 bezeichneten Zustände nicht äquivalent sein können
01011101010001010110111010111000100011
d.h., die in u1 und u2 beginnenden Teilbäume unterscheiden
sich „merkbar“, wenn man sie „übereinander legt“
5/32
Grundlagen des Maschinellen Lernens
Kap 3: Lernverfahren in anderen Domänen
Automatensynthese
Bestimmung von Vi/~ (/* Bestimmung der Zustandsmenge */)
sei Vi gegeben; es sei Ri := { u | es gibt x ∈ X, v ∈ Y+: (ux,v) ∈ Vi }
0101110101000101011011101011100
0100011
k = 1;
while ( Ri != ∅ ) {
zk = ∅ ;
rk = min { r | r ∈ Ri }; Ri =
01011101010001010110111010111000100011
Ri \ { rk }; zk = zk ∪ { rk } ;
while ( es gibt ein u ∈ Ri, so daß für alle r ∈ zk gilt: not ( u ∇ r ) )
Ri = Ri \ { u }; zk = zk ∪ { u };
k = k+1;
}
5/33
Grundlagen des Maschinellen Lernens
Kap 3: Lernverfahren in anderen Domänen
Automatensynthese
Bestimmung von Vi/~ (/* Bestimmung von δ und λ */)
sei Vi gegeben, sei z1,…,zn die bestimmte Zustandsmenge
0101110101000101011011101011100
0100011
-
δ(zr,x) = zk, falls es ein u ∈ zr mit δ∞(u,x) ∈ zk gibt
-
δ(zr,x) = zr, sonst
-
λ(zr,x) = y, falls es ein u ∈ zr gibt mit λ∞(u,x) = y
01011101010001010110111010111000100011
-
λ(zr,x) = y’, sonst
Bemerkung:
zi ist Anfangszustand gdw. ε ∈ zi
y‘ ist ausgezeichnetes Zeichen in Y
5/34
Grundlagen des Maschinellen Lernens
Kap 3: Lernverfahren in anderen Domänen
Automatensynthese
Vi = {
(a,1), (b,0),
(aa,10), (ba,01), (bb,00),
(aaa,100), (bba,001) }
1
0
ε
a
0
b
1
0101110101000101011011101011100
0100011
aa
0
ba
0
bb
1
aaa
bba
01011101010001010110111010111000100011
a, b, aa, bb }
Ri = { ε,
z1
z1 = { ε, b, bb }
z2 = { a, aa }
Anmerkung:
y‘ = 0
b/0
a/1
z2
a/0
b/0
5/35
© Copyright 2024 ExpyDoc
