\documentstyle[12pt]{report}
\newcommand{\bigcenter}[1]{\begin{center} {\Large\bf #1} \end{center}}
\setlength{\oddsidemargin}{.25in}       
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}          
\setlength{\textheight}{8.5in}

\newenvironment{proof}{\noindent{\bf Proof:}}{\qed\bigskip}
\newenvironment{proof_sketch}{\noindent{\bf Sketch of Proof}\hspace*{1em}}{\qed\bigskip}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}
\newtheorem{lemma}{Lemma}
\newtheorem{claim}{Claim}
\newtheorem{fact}{Fact}
\newtheorem{definition}{Definition}
\newtheorem{assumption}{Assumption}
\newtheorem{observation}{Observation}
\newtheorem{example}{Example}
\newcommand{\qed}{\rule{7pt}{7pt}}

\parskip=2ex

\parindent=0ex

\newcommand{\necpos}[1]{[\langle #1 \rangle]}

\def\eqruleii#1#2#3{{\footnotesize
\begin{tabbing}
#1 \hspace{.2in} \= #2 \\
		 \> \parbox{1.5in}{\noindent \hrule \mbox{}} \\
		 \> #3
\end{tabbing}}}


\def\eqruleiiii#1#2#3#4#5{{\footnotesize
\begin{tabbing}
#1 \hspace{.2in} \= #2 \\
                 \> #3 \\
                 \> #4 \\
		 \> \parbox{1.5in}{\noindent \hrule \mbox{}} \\
		 \> #5
\end{tabbing}}}

\begin{document}

\centerline{\bf \large 6.824 Artificial Intelligence, Fall 1993}
\centerline{\bf \large Problem Set 1 Solutions}
\medskip
\medskip

\centerline{Ruth Bergman}


%% check confusion over attributes, attributes, f's, x's.

\noindent
{\bf Problem 1} 

Consider an instance space where each instance is
an object with $n$ attributes $x_1, x_2, \ldots x_n$ where each $x_i$
takes on real number values in the closed interval $[0,1]$.
Consider conjunctive concepts, i.e., concepts
defined by conjunctions of pure atoms for linear attributes where
a pure atom is a formula of the form $r_1 \leq x_i \leq r_2$
or of the form $r_1 < x_i < r_2$ where $r_1$ and $r_2$ are rational numbers.

{\bf (a)} Mitchell's algorithm for this concept space is

\begin{tabbing}
\hspace{.25in}\=\hspace{.25in}\=\hspace{.25in}\=\hspace{.25in}\=\hspace{.25in}\= \kill
$S$ = \{$1 \leq x_1 \leq 0 \wedge 1 \leq x_2 \leq 0 \wedge \cdots \wedge 1 \leq x_n \leq 0$\}\\
;;; a universally false concept ($S$ contains exactly one concept)\\
$G$ = \{$0 \leq x_1 \leq 1 \wedge 0 \leq x_2 \leq 1 \wedge \cdots \wedge 0 \leq x_n \leq 1$\}\\
\\
Repeat until $|S| = |G| = 1$ and $G$ contains $S$\\
\>get example $y$\\
\\
\>if $y$ is a positive example then\\
\>\>remove any concept in $G$ that does not contain $y$\\
\>\>;;; update $S$ to include $y$\\
\>\>replace each atom $l_i \leq x_i \leq g_i$ in the concept in $S$ with\\ 
\>\>\>$\min(l_i, y_i) \leq x_i \leq \max(g_i, y_i)$\\
\\
\>if $y$ is a negative example then\\
\>\>remove from $S$ any concept that contains $y$\\
\>\>for each concept $C$ in $G$ s.t. $C$ contains $y$\\
\>\>\>for each attribute  $x_i$\\
\>\>\>\>construct two new concepts where \\
\>\>\>\>all attributes except $x_i$ have the values in C\\
\>\>\>\>and $x_i$ has value $l_i \leq x_i < y_i$ in one and $y_i < x_i \leq g_i$ in the other\\
\>\>\>\>add to $G$ each such newly generated concept that contains all\\
\>\>\>\>previous positive examples\\
\>\>\>;;;similarly for $l_i < x_i < g_i$ etc.\\
\>\>\>remove $C$ from $G$\\
\\
\>if $G$ or $S$ empty then no consistent concept.
\end{tabbing}

{\bf (b)} Consider the following negative examples\\
(1/2 1/2 $\ldots$ 1/2)\\
(1/3 1/3 $\ldots$ 1/3)\\
(1/4 1/4 $\ldots$ 1/4)\\
$\ldots$\\
(1/n 1/n $\ldots$ 1/n)\\

Starting with the most general concept above.  After the first negative example
we have $2n$ concepts in $G$.  The next negative example is contained in $n$ of
these concepts and splits each of those to $2n$, so we have $2n^2+n$ concepts.
The third example is contained in $n^2$ of the concepts and splits each of them
to $2n$ concepts, getting ${\cal O}(n^3)$ and so on.  After the $n$ examples
above we get ${\cal O}(n^n)$ concepts in $G$.

\vskip .5in
\noindent
{\bf Problem 2}

Consider an instance space where each instance is a structure with $n$
attributes $x_1, x_2, \ldots x_n$ and where the value set $V_i$ for
feature $x_i$ is the two element set $\{T,F\}$.  A concept is a
Boolean formula built from the attributes and connectives.

{\bf (a)} There are $2^n$ instances in the instance space
defined by $n$ Boolean attributes, since each attribute can
have 2 values.

{\bf (b)} Ignoring the representation of concepts as boolean formulas,
concepts are simply a division of the instance space into instances
in the concept and instances not in the concept.  The number of such
divisions is the number of subsets of the instances, which is
$2^{number-of-instances} = 2^{2^n}$.

{\bf (c)} The bound given in the Haussler paper can be used to show
that PAC learning is guaranteed provided we collect a number of samples
$m$ satisfying
$$m \geq \frac{1}{\epsilon}(\ln{\frac{1}{\delta}} + 2^n \ln{2})$$
With no inductive bias we need to look at a number of samples
that is proportional to the total number of instances.

\vskip .5in
\noindent
{\bf Problem 3}

Consider the instance space defined by $n$ Boolean attributes.
Concepts are Boolean combinations of literal that involve at most $k$
binary Boolean connectives each of which is either $\vee$ or $\wedge$.

{\bf (a)} Here's a different way of approaching this problem.  We can view
a boolean concept as a string.  A character in the string can be one of
the $n$ attributes, or one of the boolean connectives $\vee$, $\wedge$, or
$\neg$.  A total of $n+3$ possible values.  The length of the string
is at most $k$ for connectives plus $2(k+1)$ for possibly negated attributes.
This gives a maximum length of $3k+2$.  So a rough upper bound on the number
of concepts we can have is $(n+3)^{3k+2}$.

and the sample complexity for PAC-learning is\\
$$m \geq \frac{1}{\epsilon}(\ln{\frac{1}{\delta}} + (3k+2) \ln{(n+3)})$$

{\bf (b)} The solution to part {\bf a} does not imply that this concept
space is efficiently PAC-learnable because we haven't given an algorithm
that given a set of examples finds a concept from the concept space that
is consistent with the examples, and works in time polynomial in
$1/ \epsilon$, $1/ \delta$, $n$ and $k$.\\


%%
\vskip .5in
\noindent
{\bf Problem 4}

Consider an instance space in which each instance is an integer between
1 and $n$.  Consider a concept space in which each concept is a
disjunction of pure literals, i.e., a formula of the form
$p_1 \leq i \leq q_1 \vee p_2 \leq i \leq q_2 \vee \ldots \vee p_k \leq i \leq q_k$
where $i$ ranges over instances (integers from 1 to $n$) and each
$p_i$ and $q_i$ are integers.

{\bf (a)} We need only get an upper bound on the number of concepts for
this problem.\\
There are $2k$ $p_i$ and $q_i$, which can be one of $n$ values.  So
there are at most $n^{2k}$ concepts in this concept space.\\
Thus 
$$m \geq \frac{1}{\epsilon}(\ln{\frac{1}{\delta}} + 2k \ln{n})$$
examples are sufficient for PAC-learning.

{\bf (b)}  The following algorithm finds a concept from the concept space
that is consistent with all the examples.  (It is a batch algorithm.)

\begin{enumerate}
\item get $m$ examples from the example oracle
\item sort the examples in increasing order
\item repeat until no more examples\\
find the next positive example $u$\\
find the next negative example $v$, if no negative example found then $v = n+1$\\
make the interval $u \leq i \leq v-1$
\item if the number of intervals created is greater than $k$ output $fail$,
otherwise output the conjunction of the intervals.
\end{enumerate}

{\bf Correctness}  The algorithm above outputs a concept from the hypothesis
space.  From the construction, all the positive examples are included in
some interval, and all the negative examples are excluded.  So the concept
it outputs is consistent with the examples.

{\bf Complexity}
Sorting the examples in step 2 takes ${\cal O}(m \ln{m})$ time.  Step 3 scans
the list of examples so it takes ${\cal O}(m)$ time.  Step 4 takes ${\cal O}(k)$
time.  Since $m$ is polynomial in $n$, 1/$\epsilon$, 1/$\delta$, and k,
the algorithm works in polynomial time.

(Note: many people tried to implement Michell's algorithm to solve this
problem.  It is not necessary to implement this specific algorithm, any
algorithm that finds a consistent concept is fine.  The above algorithm is
much more efficient in this case.)

{\bf (c)}  The VC-dimension for this concept space is $2k$.

Any set of $2k$ instances is shattered by $k$ intervals, i.e., any
classification of the instances into positive and negative examples
corresponds to a concept.  The concept can be found by running the
algorithm from part b --- note that we can have at most $k$ strings of
positive examples from any labeling of $2k$ points, so the algorithm
will find a concept for any labeling.

But, consider any set of $2k+1$ or more instances.  Such a set is not shattered
because the labeling that makes the smllest instance a positive example and
then alternates negative and positive examples will have at least $k+1$ positive
strings of examples and hence does not correspond to a $k$-interval concept.

Thus 
$$m \geq \frac{1}{\epsilon}(4\ln{\frac{2}{\delta}} + 16k \log{\frac{13}{\epsilon}})$$
examples are sufficient for PAC-learning.

\end{document}