
Die Musterlösungen sind teilweise ausführlicher, als es von den
Studentinnen erwartet wird.

Aufgabe 1)
a)
I) log-lineares Modell

II) Textklassifikation
y = Klasse
x = zu klassifizierender Text
N = Normalisierungskonstanten
w = Gewichtsvektor
m = Merkmalsfunktionen
k = Merkmalsindex

III+IV) p(Wissen|SarsCov2, verursacht, Covid19) = 1/Z(SarsCov2, verursacht, Covid19) * e^(w(SarsCov2,Wissen) + w(verursacht,Wissen) + w(Covid19,Wissen))
wobei die Normalisierungskonstante N(SarsCov2, verursacht, Covid19) den
Ausdruck e^(w(SarsCov2,C) + w(verursacht,C) + w(Covid19,C)) über alle
Klassen C summiert.

b)
I) Markowmodell i-ter Ordnung

II) wortbasierte Sprachmodellierung
x = Wortfolge
m = Länger der Wortfolge
i = Ordnung des Markmowmodelles
k = Wortposition

III+IV) für i=1: p(SarsCov2, verursacht, Covid19) = p(SarsCov2|<s>) p(verursacht|SarsCov2) p(Covid19|verursacht) p(<s>|Covid19)

c)
I) Naive Bayes Modell

II) Textklassifikation
y = Textklasse
x = Wortfolge
m = Länger der Wortfolge
k = Wortposition

III+IV) p(Wissen, SarsCov2 verursacht, Covid19) = p(Wissen) p(SarsCov2|Wissen) p(verursacht|Wissen) p(Covid19|Wissen)

d) 
I) Hidden-Markov-Modell 2. Ordnung

II) Wortart-Tagging
x = Wortfolge
y = Tagfolge
m = Länge der Wortfolge
k = Wortposition

III+IV) p(SarsCov2, verursacht, Covid19, NE, VVFIN, NE) = p(NE|<s>,<s>) * p(SarsCov2|NE)
                                                      p(VVFIN|<s>,NE) * p(verursacht|VVFIN)
                                                      p(NE|NE,VVFIN) * p(Covid19|NE)
                                                      p(<s>|VVFIN,NE)

e)
I) Probabilistische kontextfreie Grammatik

II) syntaktische Desambiguierung
B = Parsebaum
pi_1,...,pi_m = Linksableitung (Folge von kontextfreien Regeln pi_i)
m = Länge der Linksableitung

III+IV) p( (S(NP(NE SarsCov2))(VP(VVFIN verursacht)(NP(NE Covid19)))) ) =
        p( S --> NP VP, NP --> NE, NE --> SarsCov2, VP -->  VVFIN NP, VVFIN --> verursacht,
	   NP --> NE, NE --> Covid19) = 
        p(S --> NP VP) p(NP --> NE) p(NE --> SarsCov2) p(VP -->  VVFIN NP) 
	p(VVFIN --> verursacht) p(NP --> NE) p(NE --> Covid19)

Aufgabe 2)
Regel Häufigkeit Wahrscheinlichkeit
-----------------------------------
S --> NP VP  3    1

VP --> V     1	  1/3
VP --> V NP  1	  1/3
VP --> V PP  1	  1/3

NP --> DT N  2	  2/5
NP --> N     1	  1/5
NP --> NNP   2	  2/5

PP --> P NP  1	  1

DT --> a     1	  1/2
DT --> the   1	  1/2

N --> lady   1	  1/3
N --> park   1	  1/3
N --> pizza  1	  1/3

NNP --> Mary 1	  1/2
NNP --> Peter 1	  1/2

P --> in     1	  1

V --> likes  1	  1/3
V --> reads  1	  1/3
V --> walks  1	  1/3

Aufgabe 3)

Zunächst wird p(Haus|N) mit dem Bayes'schen Theorem durch
p(N|Haus)p(Haus)/p(N) ersetzt.  Da wir nur an dem wahrscheinlichsten
Parsebaum interessiert sind, können wir die Konstante p(Haus), die
nicht von der Baumstruktur abhängt, bei der argmax-Operation
ignorieren. p(N) kann einfach mit relativen Häufigkeiten geschätzt werden.
p(N|Haus) kann durch interpolierte Backoff-Glättung geschätzt werden:
p(N|Haus) = r(N|Haus) + alpha(Haus) *
            (r(N|ausG) + alpha(ausG) *
            (r(N|usG) + alpha(usG) *
            (r(N|sG) + alpha(sG) *
            (r(N|G) * p(N)))))
mit r(N|a_1...a_k) = (f(N,a_1...a_k) - delta_k) / f(a_1...a_k)
wobei hier die maximale Suffixlänge 3 ist und "G" Großschreibung des Wortes anzeigt.

Aufgabe 4)

Für das Training des Berkeley-Parsers von Petrov und Klein werden
zunächst alle Parsebaumregeln extrahiert. Die Regeln A --> B_1 B_2 ... B_n
mit rechten Seiten der Länge n>2 werden binarisiert, indem sie durch neue
Regeln A --> B_1 A', A' --> B_2 A', ..., A' --> B_n-1 B_n ersetzt werden.
Dann werden die Regelhäufigkeiten bestimmt. Anschließend wird die Grammatik
verfeinert, indem jedes Nichtterminal X durch zwei neue Nichtterminale X/0
und X/1 ersetzt wird. Grammatikregeln,die n Nichtterminale enthalten, werden
durch 2^n neue Grammatikregeln ersetzt. Die Häufigkeit der ursprünglichen Regel
wird annähernd gleichförmig auf die neuen Regeln aufgeteilt. Die Verteilung darf
nicht exakt gleichförmig sein, um die Symmetrie zu brechen.
Die verfeinerte Grammatik wird mit dem EM-Algorithmus für einige Iterationen
trainiert. Im E-Schritt wird für jeden Parsebaum der Baumbank ein Parsewald
gemäß der verfeinertern Grammatik erstellt und mit dem Inside-Outside-Algorithmus
werden erwartete Häufigkeiten berechnet. Die erwarteten Häufigkeiten werden über
die ganze Baumbank summiert. Im M-Schritt werden aus den erwarteten Häufigkeiten 
Wahrscheinlichkeiten (ohne Glättung) geschätzt.
Nach dem EM-Algorithmus werden alle Aufspaltungen der Nichtterminale 
danach sortiert, wieviel sie zur Erhöhung der Likelihood der Trainingsdaten
beitragen. Die schlechtesten 50% der Aufspaltungen werden rückgängig gemacht.
Dann werden erneut alle Nichtterminal aufgespalten und die Grammatik wird wieder
mit dem EM-Algorithmus trainiert. Die Verfeinerung der Grammatik wird fortgesetzt
bis bspw. die Parsinggenauigkeit der PCFG auf Development-Daten sinkt.

Das Schaubild zeigt, wie sich durch rekursive Aufspaltung der Kategorie DT 
und anschließendes EM-Training Unterklassen der Determiner-Kategorie
bilden, die sich in ihrem syntaktischen Verhalten unterscheiden.
Beispielsweise werden bei der ersten Aufspalten Demonstrativa und Quantoren 
von der Hauptklasse der Determiner abgespalten.

Aufgabe 5)

d_<s>(0) = 1
d_A(1) = d_<s>(0) * p(A|<s>) p(a|A) = 1 * 0.5 * 0.5 = 0.25
psi_A(1) = <s>
d_B(1) = 0 da B kein erlaubtes Tag des Tokens a ist.
d_A(2) = d_A(1) * p(A|A) p(a|A) = 0.25 * 0.5 * 0.5 = 0.0625
psi_A(2) = A
d_B(2) = 0 da B kein erlaubtes Tag des Tokens a ist.
d_A(3) = d_A(2) * p(A|A) p(x|A) = 0.0625 * 0.5 * 0.5 = 0.015625
psi_A(3) = A
d_B(3) = d_A(2) * p(B|A) p(x|B) = 0.0625 * 0 * 0.5 = 0
d_<s>(4) = max(d_A(3) * p(<s>|A) p(epsilon|<s>,
               d_B(3) * p(<s>|B) p(epsilon|<s>)
	 = max(0.015625 * 0.5 * 1, 0 * 0.5 * 1) = 0.0078125
psi_<s>(4) = A

t_3 = psi_<s>(4) = A
t_2 = psi_A(3) = A
t_1 = psi_A(2) = A
Tagfolge = A A A

Aufgabe 6)

alpha(NP5) = p(NP --> NP PP) alpha(NP6) alpha(PP7) + p(NP --> NP PP) alpha(NP8) alpha(PP9)
alpha(NP8) = p(NP --> D N) alpha(D11) alpha(N12)

beta(NP5) = beta(VP3) p(VP -> V NP) alpha(V4)
beta(NP8) = beta(NP6) p(NP -> NP PP) alpha(PP10) + beta(NP5) p(NP -> NP PP) alpha(PP9)




