% -*- Mode: TeX -*-
\documentstyle[12pt]{article}

\input nofill.tex
\input texcom.tex

\parskip=2ex

\begin{document}

\centerline{\bf \huge ??. Concept Learning}

\section{Problems}


{\bf Problem 1.}  Consider an instance space where each instance is
a structure with $n$ features $f_1, f_2, \ldots f_n$ and where the
value set $V_i$ for feature $f_i$ is the two element set $\{T,F\}$.
Each instance can be viewed as a truth assignment to the features
--- each instance $x$ assignes the feature $f_i$ either the value
$T$ or the value $F$.

For this instance space a concept can be defined by a Boolean formula
$\Phi$ built from the features.  For example, the formula $f_1
\wedge \neg f_2$ is true of an instance $x$ if and only if $x$
assigns the feature $f_1$ the value $T$ and the feature $f_2$ the
value $F$.  I will define a {\em term} to be a conjunction
$\Psi_1 \wedge \Psi_2 \wedge \ldots \Psi_k$ where each $\Psi$
is a literal, i.e., a formula of the form $f_i$ or of the form
$\neg f_i$ (a term is the dual of a clause).
The empty conjunction is also considered to be a term
and is, by convention, the universally true formula.

Now consider a concept space that includes all formulas of the form
$\Phi_1 \vee \Phi_2$ where $\Phi_1$ and $\Phi_2$ are terms in the
above sense.  This concept class is called the class of 2-term DNF
(disjunctive normal form) concepts.

Show that, for this concept space, the set of most specific versions
maintained by Mitchel's algorithm (i.e., the lower fringe of the version
space) can grow exponentially in the number of examples.  More
specifically, give a set of positive examples such that the
number of different minimal concepts that cover those examples is
exponential in the number of examples.

\eject
{\bf Problem 2.}  Consider the instance space from
the previous problem, i.e., the set of structures where each structure
has $d$ features where each feature $f_i$ is associated with the value
set $\{T, F\}$.  Concepts for this instance space can be defined by
Boolean formulas as in the previous problem.
Suppose that we are trying to learn some fixed
target concept.  Further suppose that instances are selected at
random (according to some fixed distribution on instances)
and each selected instance is classified according to the fixed
target rule.  Derive a lower bound
on the number of instances that must be examined in this way
before, with probability at least 1-$\delta$, the actual error rate
of all rules consistent with the data is less than $\epsilon$.
Your answer should be an expression in terms of $\delta$,
$\epsilon$, and the number $d$ of features and should be polynomial
in $d$, $\frac{1}{\epsilon}$ and $\frac{1}{\delta}$.

{\bf Problem 3.} A concept is called $k$-DNF if it can be expressed by
a disjunctive normal form formula (a disjunction of conjunctions of
literals) where each conjunction has at most $k$ literals.  This
is a fairly rich and important concept class. (The dual class, the
class of $k$-CNF concepts, is also important).  Repeat problem 2 for
$k$-DNF concepts.  For fixed $k$ your lower bound on the number of samples
needed should be polynomial in $d$, $\frac{1}{\epsilon}$ and $\frac{1}{\delta}$.

{\bf Problem 4.} Repeat problem 2 but for the class of {\em all}
Boolean concepts.

{\bf Problem 5.} The correct answers to problem 3 above {\em does not} immediately
imply that, for conjunctive and $k$-DNF concepts,
one can quickly (in polynomial time in the number of features $d$)
find an acceptable rule (one that with probability $1-\delta$
has an error rate less than or equal to $\epsilon$).  Explain (in a couple
sentences) why the result from part d does not immediately give such
a procedure.

{\bf Problem 6.}
Consider a learning problem where objects are points on the plane
and concepts are subsets of points on the plane.  Suppose we restrict
the learning system so that it can only learn concepts which are
the interior plus the boundry of a convex polygon.  For example, the interior
plus the edges of a square form a convex polygon concept.
Give a proof that the VC dimension of the set of all convex polygons is
infinite.   Hint:  Consider a large number of points all on the circumference of a circle
and any classification of these points as positive or negative instances.  Consider
polygons whose vertices are selected from the given points.  Your proof should
demonstrate an understanding of the concept of VC dimension.


{\bf Problem 7.} Show that for $j > 3$ the VC dimension of polygons with $j$ edges
is $2j+1$.

{\bf Problem 8.} Consider two learning experiments.  In the first experiment
we only select points on the circumference of the unit circle for classification.
The points are selected independently and randomly according to a uniform distribution
over the set of points on the unit circle.  As each point is selected it is classified
as a positive or negative example.  The second learning experiment is identical to
the first except that the points to be classified are selected at random
according to a uniform distribution over the {\em interior} of the unit square.
In which of these two experiments can we use the VC dimension given in problem 7
to compute a lower bound on the number of data points that must be examined to
ensure that with probability $1-\delta$ any concept consistent with the data
has an error rate no larger than $\epsilon$?  Suppose we repeat the experiment but allowing abitrary convex
polygons as concepts.  In which experiment is the target concept PAC learnable, i.e.,
after some number of data points we have confidence $1-\delta$ that any concept consistent
with the data has error rate no larger than $\epsilon$.  Explain your answers.


{\bf Problem 1. (25 points)} This problem is on concept learning.  A finite state
automaton is a machine with a finite number of internal states.
The machine runs by reading symbols from an input tape
and making transitions between internal states.  At each step of
the process the machine reads a symbol and makes a state transition.
The behavior is specified by a table that specifies for each internal
state and each possible input symbol what the next state of the machine
will be.  There is a start state and a set of accept states.  We say
that the machine accepts a string of input symbols if, when the machine
starts in the start state and reads those symbols it ends in an accept
state.

{\bf Part a. (8 points) } Suppose that we wish to learn a concept whose instances
are finite strings of symbols (each concept classifies each finite
string as either $+$ or $-$).  Assume that the target concept is
defined by a finite state machine with $n$ states, and that there
are $a$ symbols in the alphabet used to construct symbol strings.
Also assume that finite strings are generated at random according to
some unknown but fixed probability distribution (i.e., that the assumptions
of PAC learning hold).  Give a number of examples such that with probability
$1-\delta$ any $n$ state finite state machine that agrees with the classification
of those examples will have an error rate less than $\epsilon$.  Your
answer should be stated in terms of $n$, $a$, $\epsilon$, and $\delta$.

\vspace{3in}

{\bf Part b. (8 points) } Explain why your answer to part a does not imply the
existence of an efficient PAC learning procedure for finite state
machines.

\vspace{3in}

{\bf Part c. (9 points)} Consider the set of concepts whose set of instances
can be written 
in the form $\{\tuple{x,\;y}: y \geq ax^2+bx+c\}$
where $a$, $b$, and $c$ are real numbers and $a$ is geater than or equal to
zero.  Each instance is a point on the plane and the positive instances
of a fixed concept consist of all the points above a fixed quadratic
polynomial.  What is the VC dimension of this concept class?  Explain
your answer.

\vspace{4in}

\bibliographystyle{named}

\bibliography{/home/c2/dam/biblio/master}

\end{document}