Aufgabe 2: HMM – Forward-/Viterbi-Algorithmus a

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 }
<S>: Satzanfang
</S>: 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(<S> abwarten und Tee trinken </S>)
= P(abwarten | n/a <S>)
* P(und | <S> abwarten)
* P(Tee | abwarten und)
* P(trinken | und Tee)
* P(</S> | 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(<S> abwarten und Tee trinken </S>)
= P(abwarten | n/a <S>)
* P(und | <S> abwarten)
* P(Tee | abwarten und)
* P(trinken | und Tee)
* P(</S> | 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(<S> abwarten und Tee trinken </S>)
= 0,024
PPL(<S> abwarten und Tee trinken </S>)
= 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

Download Report