\input{AlgoLernen}
\begin{mydocument}{5}
  \begin{enumerate}
  \item \textbf{Aufgabe}: In dieser Aufgabe entwickeln wir einen \textsf{PAC}-Algorithmus für
    \( \mathsf{Threshold}_n \):
    \begin{enumerate}
    \item Beweise, dass jedes Konzept \( c \in \mathsf{Threshold}_n \) ausgedrückt
      werden kann durch eine Threshold-funktion der Form
      \begin{displaymath}
        c(x) = 1 \Longleftrightarrow \sum_{i=1}^n a_i x_i \geq b
        \text{ und } c(x) = 0 \Longleftrightarrow \sum_{i=1}^n a_i x_i \leq b-1
      \end{displaymath}
      wobei \( x = (x_1,x_2,\ldots,x_n) \in \{0,1\}^n \) und
      \( a_1,a_2,\ldots,a_n,b \in \mathbbm{Z} \)
    \item Zeige, dass \( \mathsf{Threshold}_n \) einen \textsf{PAC}-Algorithmus besitzt,
      der polynomiell in \( n \), \( \frac{1}{\varepsilon} \) und \( \frac{1}{\delta} \) ist.
    \end{enumerate}
    \textbf{Hinweis}:\\
    Für ein lineares Ungleichungssystem der Form \( Ax \leq b \) kann eine Lösung $x_0$ mit
    \( Ax_0 \leq b \) in polynomieller Zeit bezüglich $n$, $m$ und $L$ mit Karmarkars Algorithmus
    bestimmt werden. $A$ ist eine \( m \times n \)-Matrix, $x$ ein Vektor der Länge $n$,
    $b$ ein Vektor der Länge $m$ und $L$ gibt die Länge der Binärkodierung von $A$ und $b$ an.
    Die obere Schranke
    \( s \leq \frac{1}{\varepsilon}\left(\mathsf{VC}(\mathcal{C})
      \ln\left(\frac{1}{\varepsilon}\right)
      + \ln\left(\frac{1}{\delta}\right)\right) \)
    für die Beispielanzahl darf ebenfalls benutzt werden.\Punkte[1]{6}
  \item \textbf{Aufgabe}: Konstruieren sie einen effizienten \textsf{PAC}-Algorithmus für die
    Konzeptklasse \( \mathsf{Sym}_n \) aller symmetrischen Funktionen $f$ über $n$ Variablen.
    Eine Funktion \( \{0,1\}^n \rightarrow \{0,1\} \) heißt symmetrisch, falls für jede
    Permutation $\pi$ gilt:
    \begin{displaymath}
      f(x_1,x_2,\ldots,x_n) = f(x_{\pi(1)},x_{\pi(2)},\ldots,x_{\pi(n)})
    \end{displaymath}
    Ein klassifiziertes Beispiel besteht aus einem Eingabevektor, einem Funktionswert und der
    Klassifizierung, die angibt, ob die zu lernende Funktion für diesen Eingabevektor diesen
    Funktionswert annimmt oder nicht.

    Ihr Algorithmus sollte möglichst wenige Gegenbeispiele anfordern.\Punkte{6}
    Zuerstmal sollten wir herausstellen, dass es gar nicht so viele mögliche Eingabefolgen gibt,
    die wir lernen müssen. Denn wenn bei jeder Permutation derselbe Funktionswert herauskommt,
    ist für die Funktion nur die Anzahl der Einsen und Nullen wichtig.

    Und da \( x_1,\ldots,x_n \in \{0,1\} \) gibt es nur \( 2^n \) mögliche Kombinationen.

    Doch nun zum Algorithmus
    \begin{itemize}
    \item fordere $s$ Beispiele an mit \( s = \Theta\left(\frac{n}{\varepsilon}+\frac{1}{\varepsilon}
        \cdot\ln\left(\frac{1}{\delta}\right)\right) \)
      \hfill{S. 51 Skript}
    \item initialisiere \( B(1,\ldots,n) = (0,\ldots,0) \)
    \item wiederhole für jedes Beispiel
      \begin{itemize}
      \item setze i = Anzahl der Einsen im Eingabevektor
      \item falls x ein pos. Beispiel, setze \( B[i]=B[i]+1 \)
      \item falls x ein neg. Beispiel, setze \( B[i]=B[i]-1 \)
      \end{itemize}
    \item konstruiere Hypothese \( h = x_1\vee x_2\vee\ldots\vee x_n \), wobei
      \( x_k = i \) für \( B[i] \geq 0 \)
    \end{itemize}
    Wenn wir nun Beispiele zum klassifizieren bekommen, schauen wir nach, ob \( h = i\)
    (wobei $i=$ Anzahl der Einsen) ist.
  \item \textbf{Aufgabe}: Wir betrachten den folgenden Occam-Algorithmus $L$ für konvexe Polygone
    in der Ebene:

    Gegeben: Eine Menge von $m$ zufällig gewählten Beispielen.
    \begin{enumerate}
    \item Finde eine Linie, die alle positiven Beispiele auf der einen Seite und möglichst viele
      negative auf der anderen hat.
    \item Entferne diese negativen Beispiele und wiederhole Schritt 1, solange negative Beispiele
      vorhanden sind.
    \item Das Ergebnis ist das aus diesen Linien bestehenden konvexe Polygon.
    \end{enumerate}
    Zeige, dass nur \( \mathcal{O}(e \log m) \) Iterationen notwendig sind, wobei $e$ die Eckenzahl
    des Zielkonzeptes sei.
    \\\textbf{Hinweis}:\\ Das allgemeine Set-Cover Problem besteht aus einem Mengensystem
    \( S = S_1, S_2, \ldots,S_s \) mit
    \begin{displaymath}
      \bigcup_{1\leq i \leq s} S_i=U
    \end{displaymath}
    Gesucht ist eine möglichst kleines Teilmengensystem \( I \subseteq \{1,\ldots,s\} \) mit
    \begin{displaymath}
      \bigcup_{i\in I} S_i=U
    \end{displaymath}
    Der \textsf{Greedy}-Algorithmus, der zu jedem Zeitpunkt die Menge zu $I$ hinzufügt, die die meisten noch
    nicht abgedeckten Elemente aus $U$ überdeckt, liefert eine Lösung \( I_\mathsf{greedy} \) , die der
    Ungleichung
    \begin{equation}
      \label{eq:greedy}
      | I_\mathsf{greedy} | \leq | I_\mathsf{opt} |\cdot\log(|U|)
    \end{equation}
    genügt.\Punkte{6}
    Da unser Problem eine abstrakte Variante hat (Set-Cover), zeigen wir, dass die
    Ungleichung~(\ref{eq:greedy}) für unseren Fall anwendbar ist.

    \( \log(|U|) = \log m \) ist trivial, denn bei jeder Iteration bekommen wir mindestens ein
    Beispiel zu unserer Menge hinzu. Also ist die Anzahl der Iterationen gleich der Anzahl der
    Elemente in $I$.

    Jetzt muss nur noch gezeigt werden, dass \( |I_\mathsf{opt}| = e \),
    also der Anzahl der Ecken ist. Dies ist aber auch klar, denn wir beschreiben mit unserem
    \textsf{Greedy}-Algorithmus ja die konvexe Hülle der positiven Beispiele (wobei wir den
    Einschluss von negativen Beispielen mit einem Fehler von $\varepsilon$ erlauben). Wenn wir
    jetzt annehmen, dass jedes positive Beispiel an einem Eckpunkt sitzt -- was ja im Worst-case
    durchaus der Fall ist -- haben wir $e$ Elemente in unserer Menge \( I_\mathsf{opt} \).

    Daraus folgt:
    \begin{eqnarray*}
      |I_L| &\leq& |I_\mathsf{opt}|\cdot\log|U| \\
      &=& \mathcal{O}(e\log m) \\
    \end{eqnarray*}
  \item \textbf{Aufgabe}: In dieser Aufgabe \ldots\Punkte{6}
    Mein Occam-Algorithmus:
    \begin{itemize}
    \item fordere $n$ Beispiele in Abhängigkeit von $\varepsilon$ und $\delta$ an
    \item sortiere die Beispiele (negative wie positive) nach Größe (kleinstes zuerst)
    \item setze \( h = \mathrm{code}(x) \) für das erste positive Beispiel $x$ und speichere Zuordnung
    \item oder: setze \( h = \mathrm{code}(1)\cdot\mathrm{code}(0) \) falls es keins gibt und
      überspringe den folgenden Schritt
    \item Wiederhole für jedes Beispiel
      \begin{itemize}
      \item falls $x$ ein positives Beispiel:
        \begin{itemize}
        \item wenn das vorherige Beispiel ein positives war, tue nichts
        \item falls es ein negatives war, setze \( h' = h\cdot\mathrm{code}(x) \) und speichere Zuordnung
        \end{itemize}
      \item falls $x$ ein negatives Beispiel:
        \begin{itemize}
        \item wenn das vorherige Beispiel ein negatives war, tue nichts
        \item falls es ein positives war, setze \( h' = h\cdot\mathrm{code}(x) \) und speichere Zuordnung
        \end{itemize}
      \item setze \( h = h' \)
      \end{itemize}
    \item gib $h$ aus.
    \end{itemize}
    Nachdem der Algorithmus fertig ist, liegen die Zahlen kodiert vor als
    \( \mathrm{code}(a_1)\cdot\mathrm{code}(b_1)\cdot\mathrm{code}(a_2)\cdot\mathrm{code}(b_2)
    \cdots\mathrm{code}(a_s)\cdot\mathrm{code}(b_s) \). Dabei haben wir höchstens $2n$ Elemente
    in unserer Hypothese gespeichert (das ist auch die \textsf{VC}-Dimension dieser Konzeptklasse)
    und somit Laufzeit \( \mathrm{poly}(n) \). Auch das überprüfen der Hypothese ist kein Problem,
    denn wir haben immer $2$ Zahlen gespeichert und durch ihre besondere Kodierung auch deren Länge.
  \end{enumerate}
\end{mydocument}
\ifx\main\undefined\end{document}\fi