Transcript
Kognitive Systeme Übung 5 Matthias Sperber
1
23.06.15
Übung 5 – Spracherkennung und Maschinelles Lernen
KIT, Interactive Systems Laboratories
Aufgabe 1: Neuronales Netz
a) XOR-Problem Aufgabe: neuronales Netz entwickeln, welches XOR-Problem löst. 1 versteckte Schicht 2 binäre Eingänge (0/1) 1 binärer Ausgang (0/1) Eingang 1 Eingang 2 Ausgang
2
23.06.15
0
0
0
0
1
1
1
0
1
1
1
0
Übung 5 – Spracherkennung und Maschinelles Lernen
KIT, Interactive Systems Laboratories
Aufgabe 1: Neuronales Netz
a) XOR-Problem Mögliche Lösungen:
3
23.06.15
Übung 5 – Spracherkennung und Maschinelles Lernen
KIT, Interactive Systems Laboratories
Aufgabe 1: Neuronales Netz
b) Online-Frage
Wieviele versteckte Neuronen sind mind. nötig (direkte Verbindungen nicht erlaubt?) Antwort: 2
4
23.06.15
Übung 5 – Spracherkennung und Maschinelles Lernen
KIT, Interactive Systems Laboratories
Aufgabe 2: HMM – Forward-/Viterbi-Algorithmus
HMMs in der automatischen Spracherkennung
5
23.06.15
Übung 5 – Spracherkennung und Maschinelles Lernen
KIT, Interactive Systems Laboratories
Aufgabe 2: HMM – Forward-/Viterbi-Algorithmus
a) Wahrscheinlichkeit
Pro Zustand Emissionswahrscheinlichkeiten summieren sich auf zu 1 Übergangswahrscheinlichkeiten summieren sich auf zu 1
6
23.06.15
Übung 5 – Spracherkennung und Maschinelles Lernen
KIT, Interactive Systems Laboratories
Aufgabe 2: HMM – Forward-/Viterbi-Algorithmus
a) Wahrscheinlichkeit Wahrscheinlichkeit für O 1= ABA ?
P (O∣λ)=∑ P (O , Q∣λ) ∀Q
→ Forward-Algorithmus
α0 ( j)=
1, wenn j = Startzustand 0, sonst N
αt ( j)={∑ αt−1 (i)⋅a ij }⋅b j (O t )
mit t > 0
i=0
7
23.06.15
Übung 5 – Spracherkennung und Maschinelles Lernen
KIT, Interactive Systems Laboratories
Aufgabe 2: HMM – Forward-/Viterbi-Algorithmus
a) Wahrscheinlichkeit Wahrscheinlichkeit für O 1= ABA ?
A
8
23.06.15
B
Übung 5 – Spracherkennung und Maschinelles Lernen
A
KIT, Interactive Systems Laboratories
Aufgabe 2: HMM – Forward-/Viterbi-Algorithmus
a) Wahrscheinlichkeit Wahrscheinlichkeit für O 1= ABA ?
A
9
23.06.15
B
Übung 5 – Spracherkennung und Maschinelles Lernen
A
KIT, Interactive Systems Laboratories
Aufgabe 2: HMM – Forward-/Viterbi-Algorithmus
a) Wahrscheinlichkeit Wahrscheinlichkeit für O 1= ABA ?
A
10
23.06.15
B
Übung 5 – Spracherkennung und Maschinelles Lernen
A
KIT, Interactive Systems Laboratories
Aufgabe 2: HMM – Forward-/Viterbi-Algorithmus
a) Wahrscheinlichkeit Wahrscheinlichkeit für O 1= ABA ?
A
11
23.06.15
B
Übung 5 – Spracherkennung und Maschinelles Lernen
A
KIT, Interactive Systems Laboratories
Aufgabe 2: HMM – Forward-/Viterbi-Algorithmus
a) Wahrscheinlichkeit Wahrscheinlichkeit für O 1= ABA ?
A
12
23.06.15
B
Übung 5 – Spracherkennung und Maschinelles Lernen
A
KIT, Interactive Systems Laboratories
Aufgabe 2: HMM – Forward-/Viterbi-Algorithmus
a) Wahrscheinlichkeit Wahrscheinlichkeit für O 1= ABA ?
A
13
23.06.15
B
Übung 5 – Spracherkennung und Maschinelles Lernen
A
KIT, Interactive Systems Laboratories
Aufgabe 2: HMM – Forward-/Viterbi-Algorithmus
a) Wahrscheinlichkeit Wahrscheinlichkeit für O 1= ABA ?
A
14
23.06.15
B
Übung 5 – Spracherkennung und Maschinelles Lernen
A
KIT, Interactive Systems Laboratories
Aufgabe 2: HMM – Forward-/Viterbi-Algorithmus
a) Wahrscheinlichkeit Wahrscheinlichkeit für O 1= ABA ?
A
15
23.06.15
B
Übung 5 – Spracherkennung und Maschinelles Lernen
A
KIT, Interactive Systems Laboratories
Aufgabe 2: HMM – Forward-/Viterbi-Algorithmus
a) Wahrscheinlichkeit Wahrscheinlichkeit für O 1= ABA ?
A
16
23.06.15
B
Übung 5 – Spracherkennung und Maschinelles Lernen
A
KIT, Interactive Systems Laboratories
Aufgabe 2: HMM – Forward-/Viterbi-Algorithmus
a) Wahrscheinlichkeit Wahrscheinlichkeit für O 1= ABA ?
A
17
23.06.15
B
Übung 5 – Spracherkennung und Maschinelles Lernen
A
KIT, Interactive Systems Laboratories
Aufgabe 2: HMM – Forward-/Viterbi-Algorithmus
a) Wahrscheinlichkeit Wahrscheinlichkeit für O 1= ABA ?
A
18
23.06.15
B
Übung 5 – Spracherkennung und Maschinelles Lernen
A
KIT, Interactive Systems Laboratories
Aufgabe 2: HMM – Forward-/Viterbi-Algorithmus
a) Wahrscheinlichkeit Wahrscheinlichkeit für O 1= ABA ?
A
19
23.06.15
B
Übung 5 – Spracherkennung und Maschinelles Lernen
A
KIT, Interactive Systems Laboratories
Aufgabe 2: HMM – Forward-/Viterbi-Algorithmus
a) Wahrscheinlichkeit Wahrscheinlichkeit für O 1= ABA ?
A
20
23.06.15
B
Übung 5 – Spracherkennung und Maschinelles Lernen
A
KIT, Interactive Systems Laboratories
Aufgabe 2: HMM – Forward-/Viterbi-Algorithmus
a) Wahrscheinlichkeit Wahrscheinlichkeit für O 1= ABA ?
A
21
23.06.15
B
Übung 5 – Spracherkennung und Maschinelles Lernen
A
KIT, Interactive Systems Laboratories
Aufgabe 2: HMM – Forward-/Viterbi-Algorithmus
a) Wahrscheinlichkeit Wahrscheinlichkeit für O 1= ABA ?
A
22
23.06.15
B
Übung 5 – Spracherkennung und Maschinelles Lernen
A
KIT, Interactive Systems Laboratories
Aufgabe 2: HMM – Forward-/Viterbi-Algorithmus
a) Wahrscheinlichkeit
Wahrscheinlichkeit für
23
23.06.15
O2=CAB ?
Übung 5 – Spracherkennung und Maschinelles Lernen
KIT, Interactive Systems Laboratories
Aufgabe 2: HMM – Forward-/Viterbi-Algorithmus
a) Wahrscheinlichkeit
Wahrscheinlichkeit für
C
24
23.06.15
O2=CAB ?
A
Übung 5 – Spracherkennung und Maschinelles Lernen
B
KIT, Interactive Systems Laboratories
Aufgabe 2: HMM – Forward-/Viterbi-Algorithmus
b) Zustandskette
Mit max. Wahrscheinlichkeit für
O1= ABA ?
V t (i)=max q …q P (O1 …O t , q t =i∣λ) 1
t−1
→ Viterbi-Algorithmus
V 0 ( j)=
1, wenn j = Startzustand 0, sonst
V t ( j)={max i=0… N V t (i)⋅aij }⋅b j (O t ) mit t > 0
25
23.06.15
Übung 5 – Spracherkennung und Maschinelles Lernen
KIT, Interactive Systems Laboratories
Aufgabe 2: HMM – Forward-/Viterbi-Algorithmus
b) Zustandskette
Mit max. Wahrscheinlichkeit für
A
26
23.06.15
O1= ABA ? B
Übung 5 – Spracherkennung und Maschinelles Lernen
A
KIT, Interactive Systems Laboratories
Aufgabe 2: HMM – Forward-/Viterbi-Algorithmus
b) Zustandskette
Mit max. Wahrscheinlichkeit für
A
27
23.06.15
O1= ABA ? B
Übung 5 – Spracherkennung und Maschinelles Lernen
A
KIT, Interactive Systems Laboratories
Aufgabe 2: HMM – Forward-/Viterbi-Algorithmus
b) Zustandskette
Mit max. Wahrscheinlichkeit für
A
28
23.06.15
O1= ABA ? B
Übung 5 – Spracherkennung und Maschinelles Lernen
A
KIT, Interactive Systems Laboratories
Aufgabe 2: HMM – Forward-/Viterbi-Algorithmus
b) Zustandskette
Mit max. Wahrscheinlichkeit für
A
29
23.06.15
O1= ABA ? B
Übung 5 – Spracherkennung und Maschinelles Lernen
A
KIT, Interactive Systems Laboratories
Aufgabe 2: HMM – Forward-/Viterbi-Algorithmus
b) Zustandskette
Mit max. Wahrscheinlichkeit für
A
30
23.06.15
O1= ABA ? B
Übung 5 – Spracherkennung und Maschinelles Lernen
A
KIT, Interactive Systems Laboratories
Aufgabe 2: HMM – Forward-/Viterbi-Algorithmus
b) Zustandskette
Mit max. Wahrscheinlichkeit für
A
31
23.06.15
O1= ABA ? B
Übung 5 – Spracherkennung und Maschinelles Lernen
A
KIT, Interactive Systems Laboratories
Aufgabe 2: HMM – Forward-/Viterbi-Algorithmus
b) Zustandskette
Mit max. Wahrscheinlichkeit für
A
32
23.06.15
O1= ABA ? B
Übung 5 – Spracherkennung und Maschinelles Lernen
A
KIT, Interactive Systems Laboratories
Aufgabe 2: HMM – Forward-/Viterbi-Algorithmus
b) Zustandskette
Mit max. Wahrscheinlichkeit für
A
33
23.06.15
O1= ABA ? B
Übung 5 – Spracherkennung und Maschinelles Lernen
A
KIT, Interactive Systems Laboratories
Aufgabe 2: HMM – Forward-/Viterbi-Algorithmus
b) Zustandskette
Mit max. Wahrscheinlichkeit für
A
34
23.06.15
O1= ABA ? B
Übung 5 – Spracherkennung und Maschinelles Lernen
A
KIT, Interactive Systems Laboratories
Aufgabe 2: HMM – Forward-/Viterbi-Algorithmus
b) Zustandskette
Mit max. Wahrscheinlichkeit für
A
35
23.06.15
O1= ABA ? B
Übung 5 – Spracherkennung und Maschinelles Lernen
A
KIT, Interactive Systems Laboratories
Aufgabe 2: HMM – Forward-/Viterbi-Algorithmus
b) Zustandskette
Mit max. Wahrscheinlichkeit für
A
36
23.06.15
O1= ABA ? B
Übung 5 – Spracherkennung und Maschinelles Lernen
A
KIT, Interactive Systems Laboratories
Aufgabe 2: HMM – Forward-/Viterbi-Algorithmus
b) Zustandskette
Mit max. Wahrscheinlichkeit für
A
37
23.06.15
O1= ABA ? B
Übung 5 – Spracherkennung und Maschinelles Lernen
A
KIT, Interactive Systems Laboratories
Aufgabe 2: HMM – Forward-/Viterbi-Algorithmus
b) Zustandskette
Mit max. Wahrscheinlichkeit für
A
38
23.06.15
O1= ABA ? B
Übung 5 – Spracherkennung und Maschinelles Lernen
A
KIT, Interactive Systems Laboratories
Aufgabe 2: HMM – Forward-/Viterbi-Algorithmus
b) Zustandskette
Mit max. Wahrscheinlichkeit für
A
39
23.06.15
O1= ABA ? B
Übung 5 – Spracherkennung und Maschinelles Lernen
A
KIT, Interactive Systems Laboratories
Aufgabe 2: HMM – Forward-/Viterbi-Algorithmus
c) Onlinefrage Nr. 1: Wahrsch. Folge? O1
O2
P (O 1, Q∣λ)=0.012222< P (O 2, Q∣λ )=0.03339 → O2
40
23.06.15
Übung 5 – Spracherkennung und Maschinelles Lernen
KIT, Interactive Systems Laboratories
Aufgabe 3: Sprachmodelle
Allgemein V ={abwarten ,und ,Tee ,trinken }
Laut Sprachmodell: P(“I go there”) > P(“I go their”)
41
23.06.15
Übung 5 – Spracherkennung und Maschinelles Lernen
KIT, Interactive Systems Laboratories
Aufgabe 3: Sprachmodelle
Allgemein 3-gram-LM mit V ={abwarten , und , Tee , trinken } : Satzanfang : Satzende
42
23.06.15
Übung 5 – Spracherkennung und Maschinelles Lernen
KIT, Interactive Systems Laboratories
Aufgabe 3: Sprachmodelle
a) „abwarten und Tee trinken“
Formel für die Berechnung der Wahrscheinlichkeit von 3-grammen:
P( abwarten und Tee trinken ) = P(abwarten | n/a ) * P(und | abwarten) * P(Tee | abwarten und) * P(trinken | und Tee) * P( | Tee trinken)
43
23.06.15
Übung 5 – Spracherkennung und Maschinelles Lernen
KIT, Interactive Systems Laboratories
Aufgabe 3: Sprachmodelle
a) „abwarten und Tee trinken“
Formel für die Berechnung der Wahrscheinlichkeit von 3-grammen:
P( abwarten und Tee trinken ) = P(abwarten | n/a ) * P(und | abwarten) * P(Tee | abwarten und) * P(trinken | und Tee) * P( | Tee trinken) = 0,5 * 0,8 * 0,5 * 0,6 * 0,2 = 0,024 44
23.06.15
Übung 5 – Spracherkennung und Maschinelles Lernen
KIT, Interactive Systems Laboratories
Aufgabe 3: Sprachmodelle
a) „abwarten und Tee trinken“
Umformung:
45
23.06.15
Übung 5 – Spracherkennung und Maschinelles Lernen
KIT, Interactive Systems Laboratories
Aufgabe 3: Sprachmodelle
a) „abwarten und Tee trinken“
P( abwarten und Tee trinken ) = 0,024 PPL( abwarten und Tee trinken ) = 0,024 ^ (-1/5) = 2,108
46
23.06.15
Übung 5 – Spracherkennung und Maschinelles Lernen
KIT, Interactive Systems Laboratories
Aufgabe 3: Sprachmodelle
Satz
WS
PPL
a) abwarten und Tee trinken
0,024
2,108
b) Tee trinken und abwarten
0,00012
6,083
c) abwarten und abwarten
0,0006
3,593
d) abwarten
0,025
6,325
Onlinefrage 3: Reihenfolge in aufsteigender Perplexität Lösung: c) acbd
47
23.06.15
Übung 5 – Spracherkennung und Maschinelles Lernen
KIT, Interactive Systems Laboratories
Aufgabe 4: Dynamische Programmierung
a) Programmieren
Minimale Editierdistanz
D0,0 =0 Di−1, j−1 +0,falls match Di , j =min
Di−1, j−1+1, falls sub Di−1, j +1,falls del Di , j−1 +1, falls ins
48
23.06.15
Übung 5 – Spracherkennung und Maschinelles Lernen
KIT, Interactive Systems Laboratories
Aufgabe 4: Dynamische Programmierung
a) Programmieren
Demo
49
23.06.15
Übung 5 – Spracherkennung und Maschinelles Lernen
KIT, Interactive Systems Laboratories
Aufgabe 4: Dynamische Programmierung
a) Programmieren def levenshtein(s1, s2): if len(s1) < len(s2): return levenshtein(s2, s1) if len(s2) == 0: return len(s1) previous_row = range(len(s2) + 1) for i, c1 in enumerate(s1): current_row = [i + 1] for j, c2 in enumerate(s2): insertions = previous_row[j + 1] + 1 deletions = current_row[j] + 1 substitutions = previous_row[j] + (c1 != c2) current_row.append(min(insertions, deletions, substitutions)) previous_row = current_row return previous_row[-1]
50
23.06.15
Übung 5 – Spracherkennung und Maschinelles Lernen
KIT, Interactive Systems Laboratories
Aufgabe 4: Dynamische Programmierung
a) Programmieren
Referenz: wenn es im Juni viel donnert kommt ein trüber Sommer Hypothese
Word edit distance
im Juni viel Sonne kommt einen trüberen Sommer
5
im Juni viel Donner bringt einen trüben Sommer
6
viel Donner im Juni einen trüben Sommer bringt
8
Juni Donner einen Sommer
8
wenns im Juno viel Donner gibts einen trüben Sommer 7
51
23.06.15
Übung 5 – Spracherkennung und Maschinelles Lernen
KIT, Interactive Systems Laboratories
Aufgabe 4: Dynamische Programmierung
b) Programmieren
Referenz: wenn es im Juni viel donnert kommt ein trüber Sommer Hypothese
52
Word edit distance
Character edit dist.
im Juni viel Sonne kommt einen trüberen Sommer
5
15
im Juni viel Donner bringt einen trüben Sommer
6
18
viel Donner im Juni einen trüben Sommer bringt
8
34
Juni Donner einen Sommer
8
31
wenns im Juno viel Donner gibts einen trüben Sommer
7
13
23.06.15
Übung 5 – Spracherkennung und Maschinelles Lernen
KIT, Interactive Systems Laboratories
Aufgabe 4: Dynamische Programmierung
c) Onlinefrage Nr. 4: Höchste Punktzahl
1) 1, 2 2) 2, 1 3) 1, 5 4) 3, 3 5) 5,1
53
23.06.15
Übung 5 – Spracherkennung und Maschinelles Lernen
KIT, Interactive Systems Laboratories
