\include{AlgoLernen}
\MyBegin{1}
\psset{unit=1pt}
%\newgray{lightgray}{.75}
\begin{enumerate}[\bfseries{1.}1]
\item \textbf{Aufgabe:} Auf einer verstreuten Inselgruppe \( I:=\left\{ I_1,\ldots,I_n\right\} \)
  im Südpazifik leben eine ganze Reihe von Tieren. Eine besondere Laune der Natur bringt es mit
  sich, dass abgesehen von einigen auf allen Inseln vorkommenden Tieren \( t_1,\ldots,t_k \) auch
  jede Insel $I_x$ eine nichtleere Menge \( \left\{ u_{x,1},\ldots \right\} \) von ganz spezifischen
  Tieren aufweist, die nur dort vorkommen.

  Ein dort gestrandeter Theoretiker beschließt, sich die Zeit bis zur Rettung damit zu vertreiben,
  eine Insel an ihrer Fauna zu erkennen und dazu das Lernmodell eines passiven Lernens zu verwenden.
  Ihm ist dabei bekannt, welche Tiere auf den Inseln vorkommen. Als Konzept der Insel $I_x$ setzt er
  also
  \begin{displaymath}
    C_x := \left\{ t_1,\ldots,t_k\right\} \cup \left\{ u_{x,1},u_{x,2},\ldots \right\}
  \end{displaymath}
  Glücklicherweise ist eine der dort ansässigen Gottheiten bereit als Lehrer zu fungieren.
  allerdings verlangt er für jedes Gegenbeispiel die Opferung eines Räucherstäbchens.\Punkte{6}
  \begin{enumerate}[a.]
  \item Wieviele Räucherstäbchen muss der Theoretiker bei sich haben, wenn er als Hypothesenklasse
    $\mathcal{H}$ die Konzeptklasse $\mathcal{C}$ (also die Menge der Inseln) verwendet? Dabei ist
    davon auszugehen, dass die Gottheit möglichst viele Räucherstäbchen geopfert haben möchte.

    \textbf{Lösung}:\\
    Da die Tiere \( t_1,\ldots,t_k \) auf allen Inseln vorkommen, kann man sie in unserer Hypothese
    $h$ weglassen und sich nur auf die übriggebliebenen einzigartigen Tiere konzentrieren.
    Sei nun
    \begin{displaymath}
      \begin{split}
        h &\equiv t_1 \wedge t_2 \wedge \ldots t_k \;\wedge \\
        & \wedge u_{1,1} \wedge u_{1,2} \wedge \ldots u_{1,j_1}\\
        & \wedge u_{2,1} \wedge u_{2,2} \wedge \ldots u_{2,j_2}\\
        & \vdots \\
        & \wedge u_{n,1} \wedge u_{n,2} \wedge \ldots u_{n,j_n}
      \end{split}
    \end{displaymath}
    die Hypothese um das Konzept einer Insel zu erlernen. Wir wissen nämlich, welche Tiere auf
    welchen Inseln leben und können uns die negierten Literale sparen. Außerdem wissen wir ja auch
    somit, wieviele Tiere auf jeder Insel leben. Nun gibt uns die niedere Gottheit ein positives
    Gegenbeispiel. Das Beispiel mit den wenigsten Informationen, das sie uns geben kann, hat an einer
    Stelle ein \( \neg u_{x,j} \) -- in diesem Beispiel auf der zweiten Insel:
    \begin{displaymath}
      \begin{split}
        c &= t_1 \wedge t_2 \wedge \ldots t_k \;\wedge \\
        & \wedge u_{1,1} \wedge u_{1,2} \wedge      \ldots u_{1,j_1} \\
        & \wedge u_{2,1} \wedge \neg u_{2,2} \wedge \ldots u_{2,j_2} \\
        & \vdots \\
        & \wedge u_{n,1} \wedge u_{n,2} \wedge \ldots u_{n,j_n}
      \end{split}
    \end{displaymath}
    Nun wissen wir also, dass es Insel $2$ nicht sein kann. Denn wenn sie es wäre, müsste das
    Tier \( u_{2,2} \) ja vorhanden sein. Wenn das so fortgeführt wird -- was es ja muss, denn
    die niedere Gottheit darf nur positive Gegenbeispiele geben -- sind wir in $n$ Gegenbeispielen
    fertig.

    Da wir das für alle Konzepte machen (\( \mathcal{H}=\mathcal{C} \)) brauchen wir $n^2$
    Räucherstäbchen.
  \item Welche Aussage macht die VC-Dimension bei diesem Problem?
    \\\textbf{Lösung}:\\
    Da ein Monom in $\mathcal{C}$ folgendermaßen aussieht:
    \begin{displaymath}
      m = t_1\ldots t_k u_{x,1}u_{x,2}\ldots u_{x,j_x}
    \end{displaymath}
    ist
    \begin{displaymath}
      \mathsf{VC}(C)=k+j \qquad \text{mit }j=\left\{ \max_{j=1}^n j_x \right\}
    \end{displaymath}
  \item Kann eine Hypothesenklasse angegeben werden, die die Schärfe dieser Schranke belegt?
  \end{enumerate}
\item\label{item:textbf-einem-kreis} \textbf{Aufgabe:} Einem Kreis $K$ in der Ebene $\mathbbm{R}^2$ ordnen wir die Punktmenge
  \begin{displaymath}
    C_K := \left\{ (x,y)\in\mathbbm{R}^2 \,\big|\, (x,y) \text{ liegt in } K\right\}
  \end{displaymath}
  als Konzepte zu. Sei $\mathcal{C}$ die Klasse aller solcher Konzepte. Bestimmen Sie exakt die
  VC-Dimension dieser Konzeptklasse.\Punkte{6}
  \textbf{Lösung}:\\
  Wir müssen nur einen Fall finden, in dem eine Beispielmenge bestehend aus $n$ Literalen von
  einem Kreis zertrümmert wird, denn "Die \textsf{VC}-Dimension ist die Mächtigkeit der größten
  Menge $S$, die von $\mathcal{C}$ zertrümmert wird." (\emph{S. 14} Skript)\\
  \begin{minipage}{100pt}
    \begin{picture}(70,70)
      \pscircle[fillstyle=solid,fillcolor=lightgray](40,40){30}
      \put(40,40){\circle*{4}
        \put(2,2){\mbox{$m$}}}
      \put(22,22){\circle*{4}
        \put(1,1){\mbox{$x_1$}}}
      \put(60,10){\circle*{4}
        \put(1,1){\mbox{$x_2$}}}
      \put(65,45){\circle*{4}
        \put(1,1){\mbox{$x_3$}}}
      \psline{<->}(40,0)(40,20)
      \psline{<->}(40,30)(40,50)
      \psline{<->}(30,40)(50,40)
    \end{picture}
  \end{minipage}
  \begin{minipage}{0.7\textwidth}
    Bei einem Kreis in $\mathbbm{R}^2$ haben wir nur zwei frei wählbare Variablen, nämlich den Kreisradius
    $r$ und den Mittelpunkt $m$. Dabei können wir ohne weiteres einen oder zwei Punkte abgrenzen.

    Auch bei drei Punkten ist das möglich, denn wir werden immer einen Kreis finden, der keinen, einen, zwei
    oder alle drei Punkte enthält.
  \end{minipage}
  \begin{minipage}{0.7\textwidth}
    Bei vier Punkten ist das aber nicht mehr möglich, denn man wird nie einen Kreis finden, der
    durch $x_2$ und $x_4$ geht, aber nicht durch $x_1$ oder $x_3$. Allgemeiner gesagt gibt es
    keinen Kreis, der die längere Diagonale enthält und die kürzere nicht.

    Deswegen ist
    \begin{displaymath}
      \mathsf{VC}(\mathcal{C})=3
    \end{displaymath}
  \end{minipage}
  \begin{minipage}{100pt}
    \begin{picture}(70,70)
      \pscircle[fillstyle=solid,fillcolor=lightgray](40,40){30}
      \put(40,40){\circle*{4}
        \put(1,2){\mbox{$m$}}}
      \put(22,22){\circle*{4}
        \put(1,1){\mbox{$x_1$}}}
      \put(60,10){\circle*{4}
        \put(1,1){\mbox{$x_2$}}}
      \put(65,45){\circle*{4}
        \put(1,1){\mbox{$x_3$}}}
      \put(10,60){\circle*{4}
        \put(1,1){\mbox{$x_4$}}}
      \psline(22,22)(65,45)
      \psline(60,10)(10,60)
    \end{picture}
  \end{minipage}
\item \textbf{Aufgabe:} Einem Dreieck $D$ in der Ebene $\mathbbm{R}^2$ ordnen wir die Punktmenge
  \begin{displaymath}
    C_D := \left\{ (x,y)\in\mathbbm{R}^2 \,\big|\, (x,y) \text{ liegt in } D\right\}
  \end{displaymath}
  als Konzepte zu. Sei $\mathcal{C}$ die Klasse aller solcher Konzepte. Bestimmen Sie exakt die
  VC-Dimension dieser Konzeptklasse.\Punkte{6}
  \textbf{Lösung}:\\
  Die Lösung ist ähnlich zu Aufgabe \textbf{1.\ref{item:textbf-einem-kreis}}, jedoch werden wir diesmal
  die Punkte auf einem Kreis anordnen.\\
  \begin{minipage}{100pt}
    \begin{picture}(80,80)
      \pscircle(40,40){30}
      \put(10,40){\circle*{4}
        \put(1,1){\mbox{$x_1$}}}
      \put(40,10){\circle*{4}
        \put(1,1){\mbox{$x_2$}}}
      \put(60.28,18.28){\circle*{4}
        \put(2,2){\mbox{$x_3$}}}
      \put(70,40){\circle*{4}
        \put(2,2){\mbox{$x_4$}}}
      \put(40,70){\circle*{4}
        \put(1,1){\mbox{$x_5$}}}
      \pspolygon[fillstyle=solid,fillcolor=lightgray](10,40)(40,10)(70,40)
    \end{picture}
  \end{minipage}
  \begin{minipage}{0.7\textwidth}
    Hier können wir wunderbar die Menge der keinen, einen, zwei, drei oder vier Punkte zertrümmern.
    Wenn wir z.B. auch noch $x_3$ in das Dreieck bekommen möchte, verlängern wir einfach
    $\overrightarrow{x_1x_2}$ und $\overrightarrow{x_1x_4}$ und $x_3$ ist drin.
    Wir können das fortsetzen, bis zu 7 Punkten; bei 8 ist jedoch Schluss.
  \end{minipage}
  \begin{minipage}{0.7\textwidth}
    Wenn man bei 8 Punkten die Punkte $x_2$, $x_4$, $x_6$ und $x_8$ in ein Dreieck bekommen möchte,
    ist das nicht mehr möglich. Im Beispiel wäre das zertrümmern kein Problem, wenn das $x_5$ nicht
    da wäre. Jedoch findet man kein Dreieck, das die Anforderungen erfüllt. Deshalb:
    \begin{displaymath}
      \mathsf{VC}(D)=7
    \end{displaymath}
  \end{minipage}
  \begin{minipage}{100pt}
    \begin{picture}(80,80)(-10,0)
      \pscustom[fillstyle=solid,fillcolor=lightgray]{
        \psline(80,62)(14,68)(14,11)(80,17)
        }
      \pscircle(40,40){30}
      \put(10,40){\circle*{4}
        \put(1,1){\mbox{$x_1$}}}
      \put(19.28,18.28){\circle*{4}
        \put(1,1){\mbox{$x_2$}}}
      \put(40,10){\circle*{4}
        \put(1,1){\mbox{$x_3$}}}
      \put(60.28,18.28){\circle*{4}
        \put(2,2){\mbox{$x_4$}}}
      \put(70,40){\circle*{4}
        \put(2,2){\mbox{$x_5$}}}
      \put(60.28,60.28){\circle*{4}
        \put(2,2){\mbox{$x_6$}}}
      \put(40,70){\circle*{4}
        \put(1,1){\mbox{$x_7$}}}
      \put(19.28,60.28){\circle*{4}
        \put(2,2){\mbox{$x_8$}}}
    \end{picture}
  \end{minipage}
\item \textbf{Aufgabe:} In der Vorlesung wurde gezeigt, dass \textsf{Winnow} stets mit
  \( \mathcal{O}(\cdot\log(n)) \) Gegenbeispielen auskommt. In dieser Aufgabe bewerten wir diese
  Aussage an den Rändern.
  \begin{enumerate}[a.]
  \item Kann man \textsf{Winnow} für \( k=n \) zu \( \Omega(n\cdot\log(n)) \) Gegenbeispielen
    gezwungen werden? Welche untere Schranke liefert die \textsf{VC}-Dimension?
  \item Welche untere Schranke liefert die \textsf{VC}-Dimension für den Fall $k=2$?
  \end{enumerate}
\end{enumerate}
\MyEnd