\documentclass{article}
\usepackage{scribe}
\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Lecture command takes 4 arguments:
% ordinal number of the lecture
% date of the lecture
% lecturer
% scribe---that is you.
%
% Fill out the next line with this information !!!!
\lecture{4}{September 19, 2005}{Adam Klivans}{Justin Brickell}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Your notes start here!
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% For theorems, lemmas, definitions, remarks, etc. use commands
% {\theorem{...}}, {\lemma{...}}, {\definition{...}}, etc.
% For proofs, use \begin{proof} ... \end{proof}
%
% For postscript figures (.ps) use the following block:
%
% \begin{figure}[h]
% \begin{center}
% \mbox{\psfig{figure=notes-nn-fig-mm.ps}}
% \caption{A very nice picture.}
% \label{fig:picture}
% \end{center}
% \end{figure}
%
% For encapsulated postscript figures (.eps) use the following block:
% (also change documentstyle line )
% \begin{figure}[h]
% \begin{center}
% \mbox{\epsfbox{notes-nn-fig-mm.eps}}
% \caption{A very nice picture.}
% \label{fig:picture}
% \end{center}
% \end{figure}
%
\section{Using Set-Cover Approximation to learn Conjunctions}
This material is covered in depth on pages 38-42 of Kearns and Vazirani, so we will
only give a brief outline here. Recall from the previous lecture that there is a greedy
algorithm to find a set over of size at most $O(opt(S)\log m)$ where $opt(S)$ denotes
the number of sets in a minimum cardinality cover and $m$ is the size of the universe from
which the set elements are drawn.
We relate the Set Cover Problem to the Conjunction Problem by noting that each literal
$z$ appearing in the hypothesis $h$ ``covers'' a subset $N_{z}\in S$ of the negative
examples in S. Specifically, a $z$ covers those examples that are made negative by its
inclusion. The Conjunction Problem is equivalent to finding the minimum number of
sets $N_{z}$ that cover the entire set of negative examples.
Applying the cardinality version of Occam's Razor (Theorem 2.2) to the Occam
algorithm based on the greedy set cover algorithm, we arrive at the
conclusion that the Conjunction Problem is PAC learnable provided that the sample size
is
\[
m\geq c_{1}\left(\frac{1}{\epsilon}\log\frac{1}{\delta}+\frac{
size(c)\log n(\log size(c)+\log\log n)}{\epsilon}\right).
\]
By modifying the algorithm to stop the greedy algorithm before its completion, we
are able to improve the sample size bound to
\[
m\geq c_{1}\left(\frac{1}{\epsilon}\log\frac{1}{\delta}+\frac{
size(c)\log(2/\epsilon)\log n}{\epsilon}\right).
\]
\section{The Vapnik-Chervonenkis Dimension}
The Vapnik-Chervonenkis (VC) Dimension is a measure that assigns to each concept
class $C$ a number that captures the complexity of $C$. It is given a thorough treatment
in chapter 3 of the text; rather than repeat the proofs given in the text we will just highlight
the important definitions and theorems presented in lecture.
\definition{For any concept class $C$ over $X$, and any $S\subseteq X$,
\[
\Pi_{C}(S)=\{c\cap S:c\in C\}.
\]}
\definition{If $\Pi_{C}(S)=\{0,1\}^{m}$ (where $m=|S|$), then we say that $S$ is
{\bf shattered} by $C$. Thus, $S$ is shattered by $C$ if $C$ realizes all possible
dichotomies of $S$.}
\definition{The {\bf Vapnick-Chervonekis (VC) dimension} of $C$, denoted as
$VCD(C)$, is the cardinality $d$ of the largest set $S$ shattered by $C$. If arbitrarily
large finite sets can be shattered by $C$, then $VCD(C)=\infty$}
\subsection{Examples of VC Dimension}
We derived the VC dimensions of several well-known concept classes.
\begin{itemize}
\item Intervals on the real line. $VCD=2$
\item Halfspaces on the plane. $VCD=3$
\item Halfspaces in $d$ dimensions. $VCD=d+1$
\item Axis aligned rectangles in the plane. $VCD=4$
\item Convex polygons in the plane with $d$ sides. $VCD=2d+1$
\item Monotone disjunctions on $k<