\documentclass[a4paper,twoside,12pt]{article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts,amstext}
\usepackage{amsmath}
\usepackage{german}
\usepackage{fullpage}

\newcommand{\ZETTELNUMMER}{10}
\newcommand{\ABGABEDATUM}{bis zum 9. Januar 2017, 12 Uhr, in den
Briefkasten neben Raum 111}

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[2]{\vspace{0.3cm}\item[Aufgabe~\arabic{AUFGNR}]\stepcounter{AUFGNR} #1\hfill\emph{#2}}


\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\newcommand{\eps}{\varepsilon}
\newcommand{\E}{\mathbf{E}}
\renewcommand{\Pr}{\mathbf{Pr}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\half}[1]{\frac{#1}{2}}



\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{(\roman{enumii})}


\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER. Aufgabenblatt zur Vorlesung

\smallskip
\noindent
\large
\textbf{Randomisierte Algorithmen}\hfill WiSe 2016/17 \\[0.5ex]
\normalsize
Wolfgang Mulzer, Paul Seiferth, Max Willert

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm

\begin{description}
\AUFGABE{Chans Optimierungstechnik}{10 Punkte}
\begin{enumerate}
\item Sei $P \subset \R^2$ eine Menge von $n$ Punkten. Entwickeln und 
Analysieren Sie einen 
Algorithmus der den kleinsten Umfang eines Dreiecks berechnet, welches von 
drei Punkten aus $P$ aufgespannt wird. Ihr Algorithmus soll Chans Optimierungstechnik
verwenden und in $O(n \log n)$ erwarteter Zeit laufen.

\item Funktioniert Ihr Ansatz auch um die kleinste Fl\"ache eines Dreiecks aus 
$P$ zu berechnen? Welche Schwierigkeiten treten auf?
\end{enumerate}

\AUFGABE{Die Splitter-Funktion}{10 Punkte}

Sei $A  = (X, \mathcal{R})$ ein Range Space, mit 
$X$ unendlich. Die \emph{Splitterfunktion} f\"ur $A$, 
$\pi_A : \N \rightarrow \N$
ist definiert als
\[
  \pi_A(n) = \max_{Y \subset X, |Y| = n} |\mathcal{R}_Y|.
\]
Beweisen Sie folgende Aussagen. 
\begin{enumerate}
  \item Wenn $A$ VC-Dimension $d$ hat, 
     dann ist $\pi_A(n) = O((en/d)^d)$.
  \item
     Falls ein $d \geq 0$ existiert, so dass
       $\pi_A(n) = O(n^d)$ ist, so hat $A$ die
       VC-Dimension $O(d \log d)$.
   \item
     Entweder existiert eine Konstante $d \geq 0$,
     so dass $\pi_A(n) = O(n^d)$ ist, oder es gilt
     $\pi_A(n) = 2^n$.
   \item
     Seien $A_1 = (X, \mathcal{R}_1)$ und
     $A_2 = (X, \mathcal{R}_2)$ Range Spaces.
     Wir definieren die Range Spaces $A_1 \cup A_2$,
     $A_1 \cap A_2$ und $A_1 \setminus A_2$ 
     mit Grundmenge $X$ und Ranges 
     $\{R_1 \cup R_2 \mid R_1 \in \mathcal{R}_1, R_2 \in \mathcal{R}_2\}$,
     $\{R_1 \cap R_2 \mid R_1 \in \mathcal{R}_1, R_2 \in \mathcal{R}_2\}$ 
     bzw.
     $\{R_1 \setminus R_2 \mid R_1 \in \mathcal{R}_1, R_2 \in 
     \mathcal{R}_2\}$. Zeigen Sie: Falls $A_1$ und $A_2$
     beschr\"ankte VC-Dimension haben, so auch $A_1 \cup A_2$,
     $A_1 \cap A_2$ und $A_1 \setminus A_2$.
\end{enumerate}

\AUFGABE{PAC-Lernen}{10 Punkte}

Sei $X$ eine Menge. Eine Menge $\mathcal{C} \subseteq \{0, 1\}^X$ von
Funktionen von $X$ nach $\{0,1\}$ hei\ss{}t \emph{Konzeptklasse}.
Eine Konzeptklasse hei\ss{}t \emph{PAC-lernbar}, falls 
ein \emph{Lernalgorithmus} $A$ mit folgenden Eigenschaften
existiert. Es existiert eine Funktion $k(\eps, \delta): (0,1]^2 
\rightarrow \N$,
so dass f\"ur alle $\eps, \delta \in (0,1]$ und f\"ur alle
Verteilungen $\mu$ auf $X$ gilt: Sei $f \in \mathcal{C}$
fest, aber unbekannt.
Ziehe $k = k(\eps, \delta)$ Samples $x_1, x_2, \dots, x_k \in X$
gem\"a\ss{} der Verteilung $\mu$. Bei Eingabe 
$(x_1, f(x_1)), (x_2, f(x_2)), \dots, (x_k, f(x_k))$
liefert $A$ eine Funktion 
$g \in \mathcal{C}$, so dass mit Wahrscheinlichkeit
mindestens $1-\delta$ \"uber die Wahl des Samples 
\[
  \Pr_{x \sim \mu} [f(x) \neq g(x)] \leq \eps
\]
ist.

\begin{enumerate}
\item Interpretieren Sie PAC-Lernbarkeit im Kontext des 
betreuten Lernens.
\item Geben Sie eine geeignete Definition von VC-Dimension f\"ur
  Konzeptklassen.
\item
  Zeigen Sie: Wenn eine Konzeptklasse beschr\"ankte VC-Dimension hat,
  dann ist sie PAC-lernbar.

  \emph{Hinweis}: Verwenden Sie das verallgemeinerte $\eps$-Netz
  Theorem und Aufgabe 2.
\item
  Zeigen Sie: Sei $\mathcal{C}$ eine Konzeptklasse mit VC-Dimension
  mindestens $2z$. Dann existiert f\"ur jeden festen Lernalgorithmus $A$
  eine Funktion $f \in \mathcal{C}$ und eine Verteilung $\mu$ auf
  $X$, so dass f\"ur mit Wahrscheinlichkeit mindestens
  $1/7$ f\"ur ein Sample $x_1, \dots, x_z \sim \mu$ aus $X$ 
  \[
    \Pr_{x \sim \mu} [f(x)  \neq g(x)] \geq 1/8
  \]
  ist, wobei $g$ die Ausgabe von $A$ ist.

  \emph{Hinweis}: Sei $Y \subseteq X$ eine zersplittere Teilmenge 
    der Gr\"o\ss{}e $2z$. W\"ahlen Sie $\mu$ als die Gleichverteilung
    auf $Y$. W\"ahlen Sie $f:Y \rightarrow \{0, 1\}$ als eine 
    zuf\"allige Funktion und zeigen Sie dann
  \[
    \E_{f, x_1, \dots, x_z \sim \mu} \left[\Pr_{x \sim \mu} 
    [f(x)  \neq g(x)]\right]
    \geq 1/4.
  \]

\item
  Zeigen Sie: PAC-Lernbarkeit und beschr\"anke VC-Dimension 
    f\"ur Konzeptklassen sind \"aquivalent.
\end{enumerate}
\end{description}
\end{document}
