\documentstyle[11pt,fullpage,epic,eepic]{article}

\input{inc}
\newcommand{\flip}{{\mbox{\rm flip}}}

\begin{document}
\lecture{1}{19.10.1999}{Introducing the Exact Learning Model}{Amos Beimel}{Amos Beimel}

\section{Motivation}

The ability of a computer to learn by interacting with the environment
is fascinating. There are many scenarios and circumstances in which this
learning process can take place.
Computational learning gives formal models of the learning process and the
type of interaction with the environment. Furthermore, it tries to
characterize when efficient learning is possible by both designing
efficient algorithms and proving impossibility results.

The exact learning model represents situations in which an
unsupervised learner actively collects information. Specifically, the
learner who tries to learn some target 
function $f$ is allowed to make two kinds of queries regarding $f$: 
\begin{description}
\item[Membership Query.]
The learner asks for the value $f(y)$ on points $y$ of its choice. 
\item[Equivalence Query.]
It suggests a hypothesis $h$ to which it either gets an answer
``hypothesis is equivalent to $f$'' or gets a counterexample --
a point $y$ where $f(x)\neq h(x)$.  
\end{description}
The goal of the algorithm is to exactly learn $f$ -- find a hypothesis
$h$ such that $f(x)=h(x)$ for every $x$.

The exact learning model was introduced by Angluin in 1988, and since
then many interesting algorithms were presented in this model for
various classes of 
functions. In this seminar we will focus on three topics: learning
automata, learning sub-classes of DNF, and learning geometric objects.

\section{Examples of Learning}

I start with an informal example, which motivates the following more formal
examples.

\begin{example}{\bf (Weather Forecast Algorithm)}
Consider the following scenario.
In the beginning of each day, an algorithm gets the weather
conditions -- e.g., temperature, humidity, 
winds -- and predicts if it will rain tomorrow. At the end of the 
day the program is notified if its forecast was correct.
The goal of this algorithm is to predict correctly and make few errors.

After this process continues for some time, one can expect the algorithm
to improve as 
the algorithm has more information -- the conditions of previous days
and whether the algorithm was right or wrong in each day. One
possibility to use 
this information is the ``nearest neighbor'' algorithm: given the 
weather conditions,  the algorithm looks for a previous day with similar
conditions and predicts that it will rain if it rained in that day.
\end{example}

\begin{example}{\bf (Learning a Singleton)}
There are $n$ variables $x_1,x_2,\dots,x_n$.
The learning algorithm knows that the target function can be represented as 
$x_i$ for some $i$
(that is, for $y_1,\dots,y_n\in \nbit$ the value of $f(y_1,\dots,y_n)=1$
if and only if $y_i=1$). I emphasize that the algorithm does not know
$i$ (i.e., the target function); it only knows that $f$ has this form,
and it tries to learn $i$. 

There is a trivial algorithm for this problem; the algorithm  makes an
equivalence query for each candidates for $f$, and outputs the
candidate which gets the answer ``yes.'' Since there are only $n$
candidates, this is an efficient algorithm (but not the most
efficient one).
\end{example}

\begin{example}{\bf (Learning a Monotone Term)}
Again, there are $n$ variables $x_1,x_2,\dots,x_n$.
This time, the learning algorithm knows that the function can be
represented as a monotone term -- a conjunction of variables.
That is, there exists a  set $B \subseteq \nset$ such that
$f= \AND_{ i \in B} x_i$.

For this example, checking all possible
candidates is possible, however it is highly inefficient. 
I present, in Figure~\ref{prot-elim},
an efficient algorithm for learning this class, called the elimination
algorithm. 
\protocol{Elimination Algorithm}{The elimination algorithm, which
learns a monotone term with equivalence queries.}{prot-elim}{
\begin{enumerate}
\item
Initialization: $A \gets \nset$.
\item
\label{loop}
Define the hypothesis $h(x_1,\dots,x_n) = \AND_{i \in A} x_i$,
and make an equivalence query with $h$.
\item
If the answer of the equivalence query is ``yes'' then output $h$ and
halt.
\item
Otherwise, let $y_1,\dots,y_n$ be the counterexample, set
$A \gets A \setminus \set{i:y_i=0}$, and goto Step~\ref{loop}.
\end{enumerate}
} %%% end protocol

The correctness of the algorithm follows from the fact that
for every possible counterexample $h(y)=0$ and $f(y)=1$,
thus $y_i=0$ implies that $x_i$ is not in the target term.
As this introduction lecture is not formal, I will not formally prove the
correctness of the algorithm; I will rather show an example, which,
hopefully, will convince  that the algorithm is correct.
Let $n=6$, and consider the target function $f=x_1\AND x_2\AND x_6$.
The first hypothesis that the algorithm proposes is
$h=x_1 \AND x_2 \AND x_3 \AND x_4 \AND x_5 \AND x_6$.
The response to this equivalence query is a counterexample
$111011$, for which $h(111011)=0$ and $f(111011)=1$. 
From this counterexample, the algorithm can deduce that $x_4$ is not
in the term, thus it proposes the hypothesis
$h=x_1 \AND x_2 \AND x_3 \AND x_5 \AND x_6$.
This time, the response is a counterexample $110101$, and the
algorithm proposes the hypothesis $h=x_1 \AND x_2 \AND x_6$. There are
no further counterexamples, and the algorithm halts successfully.
\end{example}

\begin{example}{\bf (Learning a Monotone Term with Membership
Queries)}
In Figure~\ref{prot-find_min} I present Algorithm Find-Min for learning
monotone terms, this time 
the algorithm uses membership queries instead of equivalence queries.
In Algorithm Find-Min $\flip(w,i)$ is an operator that gets an $n$ bits
string $w$ and an index $i$ and returns an $n$ bit
string equal to $w$ except for the  $i$th bit which is set to $0$.
The idea of this algorithm is that we start with a point $w$ such that
$f(w)=1$ and flip the $i$ bit of $w$ if $f(\flip(w,i))$ remains $1$
(which means that $x_i$ is not in the conjunction). We continue this
process until we get to a minimal point.
\protocol{Algorithm Find-Min}{An algorithm for learning a monotone
term with membership queries.}{prot-find_min}{
\begin{tabbing}
Let $w=1^n$. \\
For \= $i=1$ to $n$ do: \\
\> Let $a=\MQ{\flip(w,i)}$ \\
\> If  $a =1$ then let $w \gets \flip(w,i)$. \\
EndFor. \\
Output $h=\BIGAND_{\,i\,:\, w_i =1} x_i$.
\end{tabbing}
} %%%% end protocol

In the next lecture I will formally prove the correctness of this
algorithm, and use it to learn a broader class of functions --
monotone DNF.
In this lecture I only describe how this algorithm works on the example
$f=x_1\AND x_2\AND x_6$. The algorithm starts with $w=111111$, and the
execution is summarized in the table below.
\begin{figure}[h]
$$
\begin{array}{|c|c|c|}
\hline
\mbox{ Query } & \mbox{ Answer } &  \mbox{Modified } w \\
\hline
 \ 011111 \    &       0       &         -           \\
\hline
 \ 101111 \    &       0       &         -           \\
\hline
 \ 110111 \    &       1       &       110111        \\
\hline
 \ 110011 \    &       1       &       110011        \\
\hline
 \ 110001 \    &       1       &       110001        \\
\hline
 \ 110000 \    &       0       &         -           \\
\hline
\end{array}
$$
\label{fig-exec}
\caption{The execution of Algorithm Find-Min on the example $111111$.}
\end{figure}
\end{example}

%%%\section{Characteristics of Learning Models}

\section{Overview of the Course}

In this section I survey the results that we will cover in this
course.

\subsection{Learning Automata}

\paragraph{Learning deterministic automata.}
Deterministic automata are a convenient way to model natural
processes. To recall the notion of deterministic automata, I describe
in Figure~\ref{fig-automaton} a simple example of
a deterministic automaton accepting 
the language of words with an odd number of zeros.
We will show an algorithm for learning regular languages in polynomial
time in the the number of states of the minimum deterministic
automaton for the language. 
%%%\fig{A simple example of a deterministic automaton.}{fig-automaton}{automaton.eepic} 

\paragraph{Learning deterministic automata without reset.}
Imagine a robot wandering around an unknown environment modeled by a
deterministic automaton. At each state the robot sees only if the
state is an accepting state or not.
The robot can actively decide
to move from its current state to a neighboring state, but it cannot 
jump to the start state (i.e., reset the automaton). In other words,
it cannot ask membership queries
(which correspond to a tour from the start state), but rather ask a
membership from its current state, and by making this query he moves
to a new state. We will show how the robot can learn the environment
by simulating a ``weak reset.''


\paragraph{Learning multiplicity  automata.}
Multiplicity automata are a generalization of deterministic automata.
In this lecture I will only define a special case of these automata:
multiplicity automata over GF$(2)$.
Before I define  multiplicity automata, I recall that 
in a non-deterministic automaton there can be any number of transitions
from a state with the same letter (zero or more transitions).
A non-deterministic automaton accepts a word if there exists at least
one path from the start state to an accepting state.
It is not known how to efficiently learn  non-deterministic automata. 

A multiplicity automaton (over GF$(2)$) accepts a word if the number of
accepting paths is odd. For example, in the automaton described in
Figure~\ref{fig-nd}, the word $11$ is accepted since it has exactly one
accepting path, and the word $01$ is rejected since it has 
two accepting paths.
%%%\fig{A simple example of a multiplicity automaton.}{fig-nd}{non-deterministic.eepic}
We will show how to learn multiplicity automata efficiently, and use
these, somewhat artificial, automata to learn natural classes  of
functions (e.g., polynomials).

\subsection{Learning Sub-classes of DNF}

Disjunctive Normal Form (DNF) formulae is another natural
representation of functions. For example, psychological experiments
show that people tend to use DNF as a representation of knowledge.


I recall the definition of a DNF formulae. Given $n$ variables,
$x_1,x_2,\dots,x_n$, a literal is a variable $x_i$ or its negation
$\overline{x}_i$. A term is a conjunction of literals, e.g.,
$x_2 \AND \overline{x}_7 \AND x_{13}$.  A DNF formula is a disjunction
of terms, e.g., $(x_2 \AND \overline{x}_7  \AND x_{13} \AND
\overline{x}_{41}) \OR  (\overline{x}_{12} \AND 
{x}_{13} \AND \overline{x}_{51})$.


Learning DNF formulae in polynomial time in the number of variables
and number of terms is one of the most important open problems in
computational learning.\footnote{It is not clear if it is possible,
as it is known that a generalization of DNF formulae -- constant-depth
formulae -- cannot be learned efficiently (under some cryptographic
assumptions).} In this seminar we will show how to learn some
sub-classes of DNF:

\paragraph{Learning monotone DNF.}

A DNF formula is monotone if it does not contain any negations.
In the next lecture I will describe an algorithm for learning monotone
DNF using the membership algorithm for learning a monotone term
described in this lecture. 

\paragraph{Learning decision trees.}
Decision trees are used in practical implementations in machine
learning, e.g., the C4.5 algorithm of Quinlan. A simple decision tree
is described in Figure~\ref{fig-dt}. In this course we will see two
algorithms for learning decision trees.
%%%\fig{A simple example of a decision tree.}{fig-dt}{dt.eepic}


\paragraph{Learning disjoint DNF.}
A DNF formula is disjoint if every assignment satisfies at most one
term in the formula, e.g., the formula $(x_1 \AND x_2) \OR
(\overline{x}_1 \AND x_3)$. Every decision tree can be represented by a
disjoint DNF formula with the same size. We will see that every
disjoint formula can be represented by multiplicity automaton,
thus the learnability of multiplicity automata implies the learnability
of disjoint DNF, which, in turn, implies the learnability of decision
trees. 

\paragraph{Learning $\log n$-term DNF.} A DNF formula is a $\log n$-term
formula if the number of terms in the formula is at most $\log n$. We
will see three or four algorithms for learning this class,
one of them uses deterministic automata.

\paragraph{Learning read-once formulae.} A DNF formula is read-$k$
if every variable appears at most $k$ times. We will show how to learn
read-once formulae, and how to learn read-twice DNF formulae.
I note that if one can learn read-$3$ DNF then it would imply the
learnability of general DNF.

\paragraph{Learning conjunctions of Horn clauses.}
%%%% Horn clause  $x_1 \AND x_2 \AND x_7 ==> y$
We will show how to learn DNF formulae where each term contains only
one negated variable.

\subsection{Learning geometric objects}

Learning geometric objects attracted a lot of attention, as they are
natural objects. For example, in Figure~\ref{fig-geo} we describe a
simple geometric object -- the
union of three rectangles in two dimensions.
%%%\fig{A simple example of a geometric object.}{fig-geo}{boxes.eepic}

\paragraph{Learning $(1)$-dimensional objects.}
We will show how to learn fairly complicated objects in a constant
number of dimensions  using only equivalence queries.

\paragraph{Learning unions of high-dimensional boxes.}
The number of dimensions is not always constant, as described
in the following example: Consider all the people whose weight is
between 60kg and 80kg, their height is between 1.7m and 1.9m, their
age is between 40 and 45, and their shoe size is  between 40 and 45.
This set of people is $5$-dimensional cube. Thus, high-dimensional
geometric objects represent natural functions. We will show how to
learn some sub-classes of unions of high-dimensional boxes.

\paragraph{Attribute-efficient learning.}
Finally, we will talk about attribute-efficient algorithms, that is
algorithms in which the number of queries 
is polynomial only in the number of relevant
variables.
For example, assume that the there are a million variables, but the
target function is $x_3 \OR x_{999,993}$. We do not want the number
of queries of an algorithm learning this function to be polynomial in the
number of variables.

We will present the winnow algorithm that learns $n$-dimensional half
spaces with $k$ relevant variables (i.e., functions of the form
$\sum_{i=1}^n w_i x_i > 0$ with only $k$ non-zero weights $w_i$).
This algorithm does not use any membership queries, and the number of
equivalence queries it uses is polynomial in $k$ and $\log n$.
\end{document}   


