
\slidehead{\large  Analytical Learning \red \ } \bk


\centerline{[Read Ch. 11]}
\centerline{[Suggested exercises: 11.1]}

\bi
\item Why use prior knowledge?
\item Explanation-based learning: Prolog-EBL
\ei


\slidehead{\large A Positive Example \red \ } \bk
% worked: -2, 5.5.   also -3, 6.5
\vspace*{-2.5in}
%\centerline{\hbox{\psfig{file=./bookps/chess.ps,width=8in}}}
\psfig{file=./bookps/chess.ps,width=5.75in}



\slidehead{\large Inductive Learning Problem Setting \red \ } \bk

{\bf Given:}
\bi
\item Instance space $X$
\item Hypothesis space $H$
\item Training examples $D$ of some target function $f$. 
\[ D = \{
\langle x_{1}, f(x_{1}) \rangle, \dots \langle x_{n}, f(x_{n}) \rangle
\} \]
\ei

{\bf Determine:}
\begin{itemize}
\item A hypothesis from $H$ consistent with training examples $D$.
\end{itemize}

\slidehead{\large Analytical Learning Problem Setting \red \ } \bk

{\bf Given:}
\bi
\item Instance space $X$
\item Hypothesis space $H$
\item Training examples $D$ of some target function $f$. 
\[ D = \{
\langle x_{1}, f(x_{1}) \rangle, \dots \langle x_{n}, f(x_{n}) \rangle
\} \]
\item {\em Domain theory $B$ for explaining training examples}
\ei

{\bf Determine:}
\begin{itemize}
\item A hypothesis from $H$ consistent with both the training examples $D$ and domain
theory $B$.
\end{itemize}


\vspace*{1in}
We say 
\bi
\item
$B$ ``explains'' $\langle x, f(x) \rangle$ if $x + B \entails f(x)$
\item
$B$ is ``consistent with'' $h$ if  $B \not \entails \neg h$
\ei


\newpage
%slidehead{\large {\em SafeToStack(x,y)} Learning Problem \red \ } \bk

{\bf Given:}
\begin{itemize}
\item Instances: pairs of physical objects


Hypotheses:  Sets of Horn clause rules, e.g.,

\vspace*{-.05in}\[ SafeToStack(x,y) \la Volume(x, vx) \tand Type(y,Box)
\]

\vspace*{-.15in}
\item Training Examples: typical example is
\begin{tabbing}
\vspace{-.25 in}
% following sets up tab stops
xxxx\=xxxxxxxxxxxxxxxxxxxxx\=xxxxxxxxxxxxxxxxxxxx\= \kill 
$SafeToStack(Obj{\it 1}, Obj{\it 2})$ \\
\>\hskip-20pt$On(Obj{\it 1},Obj{\it 2})$	\>$Owner(Obj{\it 1}, Fred)$ \\
\>\hskip-20pt$Type(Obj{\it 1},Box)$	\>$Owner(Obj{\it 2}, Louise)$ \\
\>\hskip-20pt$Type(Obj{\it 2},Endtable)$ \>$Density(Obj{\it 1},0.3)$ \\
\>\hskip-20pt$Color(Obj{\it 1},Red)$	\>$Material(Obj{\it 1}, Cardbd)$ \\
\>\hskip-20pt$\ldots$
\end{tabbing}

\vspace*{-.2in}\item 
Domain Theory:
\begin{tabbing}
xxxx\=xxxxxxxxxxxxxxxxxxxxxxxx\=xxxxxxxxxxxxxxxxxxxx\= \kill 
	\>\hskip-16pt$ SafeToStack(x,y) \la \neg Fragile(y)$ \\
	\>\hskip-16pt$SafeToStack(x,y) \la Lighter(x,y)$ \\
	\>\hskip-16pt$Lighter(x,y) \la Wt(x,wx)\tand Wt(y,wy)\tand Less(wx,wy)$ \\
	\>\hskip-16pt$\ldots$ \\
\end{tabbing}
\end{itemize}
\vspace{-.1in}
{\bf Determine:}
\begin{itemize}
\item A hypothesis from $H$ consistent with training examples and domain theory.
\end{itemize}

\newpage


\pgm{Prolog-EBG}($TargetConcept, Examples, DomainTheory$)

\bi
\item
$LearnedRules \la \{\}$
\item
$Pos \la$ the positive examples from $Examples$ 

\item
for each $PositiveExample$ in $Pos$ that is not covered by $LearnedRules$, do
\bi
\item[]\hspace*{-.18in}\hskip-12pt{\em 1. Explain:}
\item $Explanation \la $ an explanation (proof) in terms of {\em
DomainTheory} that {\em PositiveExample} satisfies {\em TargetConcept}

\item[]\hspace*{-.18in}\hskip-12pt{\em 2. Analyze:}
\item 
$SufficientConditions \la $ the most general set of features of {\em
PositiveExample} that satisfy {\em TargetConcept} according to $Explanation$.

\item[]\hspace*{-.18in}\hskip-12pt{\em 3. Refine:}
\item
$LearnedRules \la LearnedRules \ + \ NewHornClause$, where {\em
NewHornClause} is of the form
\[TargetConcept \la  SufficientConditions \]
\ei

\item
Return $LearnedRules$
\ei




\slidehead{\large An Explanation \red \ } \bk


\centerline{\hbox{\psfig{file=./bookps/ebg-safetostack1.epsf,width=7in}}}


\slidehead{\large Computing Weakest Preimage of $SafeToStack(Obj1, Obj2)$  \red \ } \bk



\centerline{\hbox{\psfig{file=./bookps/ebg-safetostack3.epsf,width=7in}}}


\newpage
%\hbox{\psfig{file=./bookps/ebg-regression.epsf,width=4in}}
\pgm{Regress}({\em Frontier, Rule, Literal, $\theta_{hi}$})

\bi
\item[] {\em Frontier:  literals to be regressed}
\item[] {\em Rule: A Horn clause}
\item[] {\em Literal: A literal in Frontier inferred by
Rule in the explanation}
\item[] $\theta_{hi}${\em : The substitution that unifies the head of Rule to the
corresponding literal in the explanation}
\item[] {\em Returns the set of literals forming the weakest preimage of
Frontier with respect to Rule}

\bi
\item $head \la head$ of {\em Rule}
\item $body \la body$ of {\em Rule}
\item $\theta_{hl} \la$ the most general unifier of $head$ with {\em Literal} such
that there exists a substitution $\theta_{li}$ for which
\[ \theta_{li}(\theta_{hl}(head)) = \theta_{hi}(head) \]
\item Return $\theta_{hl} ( Frontier - head + body)$
\ei
\ei

\slidehead{\large Regressing Literals: An Example \red \ } \bk


Example (the bottommost regression step in Figure 11.3):
\vskip4pt
\pgm{Regress}({\em Frontier, Rule, Literal, $\theta_{hi}$}) where
\bi
\item[]{\em Frontier} $= \{ Volume(x,vs), Density(x,dx), Eq(wx,
times(vx,$$dx)),$ $LessThan($$wx,$$wy)$, $Weight(y,$$wy) \}$
\item[]{\em Rule} $= Weight(z,5) \la Type(z,Endtable)$
\item[]{\em Literal} $= Weight(y,wy)$
\item[]$\theta_{hi} = \{z / Obj2 \}$
\bi
\item $head \la Weight(z,5)$
\item $body \la  Type(z,Endtable)$
\item $\theta_{hl} \la \{z / y, wy / 5 \}$, where $\theta_{li} = \{y / Obj2 \}$
\item Return $\{ Volume(x,vs), Density(x,dx), Eq(wx, times(vx,dx)),$ $LessThan(wx,5),$ $Type(y,Endtable) \}$
\ei
\ei

\slidehead{\large Lessons from $SafeToStack$ Example \red \ } \bk


\bi
\item Justified generalization from single positive example
\item Explanation determines  attribute {\em relevance}
\item Regression determines sufficient constraints on attributes
\item Generality of output hypothesis depends on domain theory
\item Still requires multiple examples (covering algorithm)
\ei

\slidehead{\large Perspectives on Prolog-EBG \red \ } \bk

\bi
\item Theory-guided generalization from examples
\item Example-guided compilation of domain theory
\item ``Just'' restating what learner already ``knows''
\ei

But is it learning?
\bi
\item Are you learning when you improve at playing chess?
\bi \item Even though optimal play follows from rules of game... \ei
\item Are you learning when you sit in math class?
\bi \item Even though those theorems follow from the axioms you've already learned...
\ei
