\documentclass[12pt]{scrartcl}

\usepackage{german,pstricks,pst-node,epsf,url,pst-tree}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{times}

\parskip 1ex

\pagestyle{plain}
\addtolength{\textheight}{1cm}

\title{Musterl"osungen zum 4. "Ubungsblatt}
\author{Sebastian Padó}

\begin{document}
\maketitle

\subsection*{Aufgabe 1a}
Zwei Klassen (gut, schlecht)

\subsection*{Aufgabe 1b}
Drei Features (Ablaufdatum, Geschmacksrichtung, Grösse)

\subsection*{Aufgabe 1c}
\begin{itemize}
\item Ablaufdatum: 20.1., 22.1., 24.1.
\item Geschmack: Erdbeer, Himbeer, Kirsche
\item Groesse: 500ml, 150 ml. 
\end{itemize}
Groesse des Featureraumes: 3 * 3 * 2 = 18

\subsection*{Aufgabe 1d}
Wir haben 7 von 18 Instanzen gesehen, also etwa 38\%. Ein
Klassifikator, der alle Features verwendet, wird also vermutlich keine
gute Abdeckung haben: wenn neue Daten klassifiziert werden sollen, die
diese Features zufällig kombinieren, haben wir die Kombination mit
über 60\% Wahrscheinlichkeit nicht gesehen.


\subsection*{Aufgabe 1e}
Die Zellen enthalten die Wahrscheinlichkeiten:

\begin{tabular}{c|ccc}
Klasse & P(Klasse | 20.1.) & P(Klasse | 22.1.) & P(Klasse | 24.1.) \\ \hline
Gut & 1/4 &  3/3 = 1 &2/3 \\
Schlecht & 3/4 & 0/3 = 0 & 1/3
\end{tabular}

Für den 20.1. ist die wahrscheinlichste Klasse also \textsl{schlecht},
für die beiden anderen Daten \textsl{gut}. Wenn man jede Instanz mit
der wahrscheinlichsten Klasse für ihr Datum klassifiziert, macht man 2
Fehler auf 10 Datenpunkten, also ist die Akkuratheit des
Klassifikators 80\% auf den Trainingsdaten.


\subsection*{Aufgabe 1f}
\begin{tabular}{c|ccc}
Klasse & P(Klasse | Himbeer) & P(Klasse | Erdbeer) & P(Klasse | Kirsch) \\ \hline
Gut & 4/4 = 1&  2/4 = 1/2 & 0/2 = 0 \\
Schlecht & 0/4 = 0 & 2/4 = 1/2 & 2/2 = 1
\end{tabular}

Für Himbeer ist die wahrscheinlichste Klasse also \textsl{gut}, für
Kirsch \textsl{schlecht}, und für Erdbeer sind die beiden Klassen
gleich wahrscheinlich. Wenn man jede Instanz mit der
wahrscheinlichsten Klasse für ihren Geschmack klassifiziert, macht man
auch 2 Fehler auf 10 Datenpunkten, also ist die Akkuratheit des
Klassifikators ebenfalls 80\% auf den Trainingsdaten. (Egal, welche
Klasse man für Erdbeer wählt: die Klassifikation ist gleich gut).

\begin{tabular}{c|cc}
Klasse & P(Klasse | 150ml) & P(Klasse | 500ml) \\ \hline
Gut & 3/6 = 1/2 &  3/4 \\
Schlecht & 3/6 = 1/2 & 1/4
\end{tabular}

Für 150 ml sind beide Klassen gleich wahrscheinlich; für 500ml ist
\textsl{gut} wahrscheinlicher. Wenn man jede Instanz mit der
wahrscheinlichsten Klasse für ihre Grösse klassifiziert, macht man
auch 4 Fehler auf 10 Datenpunkten, also ist die Akkuratheit des
Klassifikators nur 60\% auf den Trainingsdaten.

\subsection*{Aufgabe 1g}
Offenbar sind der Geschmack und das Ablaufdatum gute, aber nicht
perfekte Features, um vorherzusagen, ob ein Joghurt nocht geniessbar
ist. Die Groesse der Packung scheint nur eine geringe Vorhersagekraft
zu besitzen.

\subsection*{Aufgabe 1h}
\begin{tabular}{c|cccc}
Klasse & P(Kl | 20,Erd) & P(Kl | 20,Him) & P(Kl | 20,Him) & P(Kl | 22,Erd) \\ \hline
Gut & 0/2 = 0      & 1/1 = 1 & 0/1 = 0 & n.d. \\ 
Schlecht & 2/2 = 1 & 0/1 = 0 & 1/1 = 1 & n.d. 
\end{tabular}

\begin{tabular}{c|ccccc}
& P(Kl | 22,Him) & P(Kl | 20,Kir) & P(Kl | 24,Erd) & P(Kl |
24,Him) & P(Kl | 24,Kir) \\ \hline
Gut & 3/3 = 1      & n.d. & 2/2 = 1 & n.d. & 0/1 = 0\\
Schlecht & 0/3 = 0 & n.d. & 0/2 = 0 & n.d. & 1/1 = 1
\end{tabular}

Wenn man wieder jede Instanz mit der Klasse klassifiziert, die am
wahrscheinlichsten für ihre Datum-Geschmack-Kombination ist, werden
alle Instanzen richtig klassifiziert.

\subsection*{Aufgabe 1i}
Das Modell ist nicht besonders robust: Viele Feature-Kombinationen
wurden gar nicht oder nur ein Mal gesehen. Für die einmal gesehenen
Feature-Kombinationen ist sich der Klassifikator sehr sicher (1 von 1
Instanzen = 100\% Sicherheit), aber die Hinzufügung auch nur einer
einzigen Instanz kann die Wahrscheinlichkeit von 100\% auf 50\%
(Gleichstand!) drücken und damit die Klassifikation ändern. Dies
beleuchtet ein grundlegendes Problem der Statistik: je mehr Features
man verwendet, desto besser ist die theoretische Vorhersagekraft des
Modells; andererseits sinken bei einer konstanten Trainingsmenge die
Frequenzen der einzelnen Featurekombinationen, weil es mehr solche
gibt, womit das Model anfälliger wird.


\subsection*{Aufgabe 1j}
Die einfachen Modelle, dir nur je ein Feature verwenden, werden nicht
besonders gut sein, aber dafür eine ziemlich gute Abdeckung haben: sie
werden zumindst irgendwelche Voraussagen machen können. Das komplette
Modell hat nur eine Abdeckung von 38\% (siehe 1d), wird also für die
meisten Datenpunkte überhaupt nichts aussagen können. 

Da das Modell $P(Klasse|Datum,Geschmack)$ ziemlich gut ist, bietet es
sich an, dieses Modell zu verwenden, wenn es die zu klassifizierende
Feature-Kombination schon einmal gesehen hat, und ansonsten auf die
Modelle $P(Klasse|Datum)$ und $P(Klasse|Geschmack)$ zurückzugreifen
(back-off)!
 

\subsection*{Aufgabe 2}
Der 71 Jahre alte Narasimha Rao hat eine Führungsposition inne (Rolle
\textsc{Leader} eines \textsc{Leadership}-Frames), und zwar regiert er
über Indien (\textsc{Jurisdiction}). Diese Rolle (\textsc{Role}) hat
er aber erst seit kurzem (\textsc{New Leader} eines
\textsc{Change\_of\_leadership}-Frames). Ausserdem war sich ``kaum
jemand'' (\textsc{Cognizer}) sicher (Frame \textsc{Certainty}, was folgendes
angeht (\textsc{Content}): nämlich, dass er (\textsc{Item}) einen
\textsc{Standard} übertreffen würde (Frame \textsc{Surpassing}). Der
Standard war gesetzt durch die Einschätzung (\textsc{Categorisation})
von ihm (\textsc{Item}) durch jemanden, nämlich diejenigen
(\textsc{Role}, die die Congress-Partei (\textsc{Jurisdiction}
anführten (Frame \textsc{Leadership}).

\pagebreak
\subsection*{Aufgabe 3a}
Lesart 1: Die Verfolgung findet mit der Sonnenbrille statt.
\begin{center}
  \psset{levelsep=2.5\baselineskip,nodesep=2pt}
  \pstree{\TR{S}}{
    \pstree{\TR{S}}{
      \pstree{\TR{NP}}{
        \pstree{\TR{Det}}{\TR{Der}}
        \pstree{\TR{N}}{\TR{Detektiv}}}
      \pstree{\TR{VP}}{
        \pstree{\TR{V}}{\TR{verfolgte}}
        \pstree{\TR{NP}}{
          \pstree{\TR{Det}}{\TR{den}}
          \pstree{\TR{N}}{\TR{Gangster}} }}}
      \pstree{\TR{PP}}{
        \pstree{\TR{Prp}}{\TR{mit}}
        \pstree{\TR{NP}}{        
          \pstree{\TR{Det}}{\TR{der}}
          \pstree{\TR{N}}{\TR{Sonnenbrille}}} }}
\end{center}

\vspace{1cm}
Lesart 2: Der Gangster besitzt die Sonnenbrille.
\begin{center}
  \psset{levelsep=2.5\baselineskip,nodesep=2pt}
  \pstree{\TR{S}}{
    \pstree{\TR{NP}}{
      \pstree{\TR{Det}}{\TR{Der}}
      \pstree{\TR{N}}{\TR{Detektiv}}}
    \pstree{\TR{VP}}{
      \pstree{\TR{V}}{\TR{verfolgte}}
      \pstree{\TR{NP}}{
        \pstree{\TR{Det}}{\TR{den}}
        \pstree{\TR{N}}{\TR{Gangster}}
      \pstree{\TR{PP}}{
        \pstree{\TR{Prp}}{\TR{mit}}
        \pstree{\TR{NP}}{        
          \pstree{\TR{Det}}{\TR{der}}
          \pstree{\TR{N}}{\TR{Sonnenbrille}}}} } } }
\end{center}



\subsection*{Aufgabe 3b}
Drei wichtige Mechanismen des Deutschen, die beachtet werden müssen,
um wohlgeformte Sätze zu erzeugen, sind Subkategorisierung, Kongruenz
und Kasuszuweisung (Rektion). Alle können von der Grammatik verletzt
werden:
\begin{itemize}
\item ``Den Motorrad schläft''. Der Satz verletzt die
  \textsl{Kongruenz in der Nominalphrase}: Artikel und Kopfnomen
  müssen dieselben Kasus/Genus/Numerus haben. Weil die vorliegende
  Grammatik nur Nomina in der 3. Person Singular kennt, kann sie die
  \textsl{Subjekt-Verb-Kongruenz} nicht verletzen: Subjekt und Verb
  müssen in Kasus und Numerus übereinstimmen (nicht \textsl{du
  schläft}). 
\item ``Der Gangster verfolgte''. Dieser Satz verletzt die
  Subkategorisierung des Verbs: verfolgte ist transitiv, muss also ein
  direktes Objekt haben.
\item ``mit die Sonnenbrille'': \textsl{mit} ``regiert'' den Dativ
  (d.h. die NP in einer \textsl{mit}-PP muss im Dativ stehen) -- diese
  Fallzuweisung wird von der Grammatik nicht erzwungen. Entsprechend
  erzwingt sie nicht, dass das Subjekt eines Satzes im Nominativ
  stehen muss, sondern erlaubt Sätze wie ``den Gangster schläft''.
\end{itemize}

\end{document}
%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
