\input psadobe
\documentstyle[12pt,epsf]{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}

\parskip=2ex

\parindent=0ex

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

\input nofill.tex
\input texcom.tex

\begin{document}
\centerline{\bf \large 6.824 Artificial Intelligence, Fall 1993}
\centerline{\bf \large Final Exam}

{\bf name} \rule{6in}{2pt}

There are five problems.  Write your answeres in the space provided or on the back of the
sheets.  The point value of each problem is shown.
You have three hours.


{\bf Problem 1. (15 points)} This problem is very similar to problem 2 from problem
set 2. It is on a Bayesian approach to concept learning.
We consider an instance space where
each instance assigns Boolean values to $n$ attributes
$x_1$, $\ldots$, $x_n$.  We consider the space of all concepts
definable by Boolean expressions over these features.  For
example, $x_1 \wedge \neg x_2$ is the concept that is true of
all instances that assign $x_1$ the value $T$ and $x_2$ the value $F$.
Consider the following stochastic grammar for generating Boolean expressions
in conjunctive normal form.

\sidebyside{${C}\stackrel{\frac{1}{2}}{\rightarrow}{(D \wedge C)} \;\;\;\;\; {C}\stackrel{\frac{1}{2}}{\rightarrow}{D}$

${D}\stackrel{\frac{1}{2}}{\rightarrow}{(L \vee D)} \;\;\;\;\; {D}\stackrel{\frac{1}{2}}{\rightarrow}{L}$
}{
${L}\stackrel{\frac{1}{2}}{\rightarrow}{(\neg A)}\;\;\;\;\; {L}\stackrel{\frac{1}{2}}{\rightarrow}{A}$

${A}\stackrel{\frac{1}{n}}{\rightarrow}{x_1} \;\;\;\ldots\;\;\; {A}\stackrel{\frac{1}{n}}{\rightarrow}{x_n}$}

\medskip
Recall that a stochastic grammar determines a probability distribution over
expressions.

Suppose that we are trying to learn a target concept where the target
concept has been generated at random using the above
grammar.  After the target concept has been selected, instances
{\em on which the concept is true} are selected independently at random, giving each
instance on which the concept is true equal probability.  Let $\Psi_1$
be the formula $((x_1 \vee x_2) \wedge (x_3 \vee \neg x_4))$ and let
$\Psi_2$ be the formula $((x_1 \vee x_2) \wedge ((x_3 \vee \neg x_4) \wedge (x_5 \vee x_6)))$.

{\bf Part a. (5 points)}  What are the a-priori probabilities of the Boolean expressions
$\Psi_1$ and $\Psi_2$.

\vfill

\eject

{\bf Part b. (10 points)} Suppose that we are given a data sequence $D$
consisting of $k$ instances such that both $\Psi_1$ and $\Psi_2$ are
true of every instance in $D$.  For what values of $k$ and $n$ is
$P_r(\Psi_2|D)$ larger than $P_r(\Psi_1|D)$?  Justify your answer.

\vfill
\eject

{\bf Problem 2. (15 points)} This problem is on constraint satisfaction.  Consider the graph shown
below where each node is a variable and each arc is labeled with a number from 2 to 5.
Each node in this graph is a variable that can take on integer values from 1 to 10
(including 1 and 10).  Each arc represents a constraint that the two variables connected
by that arc must have the same value modulo the number on the arc.  For example the
arc labeled 3 conecting $w$ and $u$ would be satisfied if $w$ is 5 and $u$ is 8
because both of 5 and 8 are 2 mod 3.  Suppose that we know that $x$ is 2,
$y$ is 0, and $v$ is 0.  Give the variable values that would be infered by value propagation,
generalized forward checking, and arc consistency respectively for this graph
and these given values for $x$, $y$, and $v$.

\bigskip
\centerline{\epsffile{./chen2.ps}}

\vfill

\eject

{\bf Problem 3. (20 points)}  This problem is on higher order logic and natural language semantics.
Consider the determiner ``only'' as used in the sentences ((only nerds) (watch Star Trek))
or ((some animal in the zoo) (eats (only ants))).  The phrases (only nerds)
and (only ants) are noun phrases.  Give the semantic type for the word
only (only maps a noun to a noun phrase).  Give a lambda expression for the determiner
``only'' under which the above sentences have their intuitive meaning.

\vfill

\eject

{\bf Problem 4. (25 points)}  This problem is on the unification algorithm
used in lifting.  Consider the following inference rules for determining
the satisfiability of a set of equality and disequality constraints on expressions.
We consider only those expressions constructed from {\tt ONE}, {\tt ZERO}, and the function {\tt CONS}.

\vfill

{\scriptsize

\sidebyside{
input rules

\eqruleii{1}{\mbox{\tt (NOT (EQUAL ?X ?Y))}}
{\mbox{\tt (INPUT! ?X)}}

\eqruleii{2}{\mbox{\tt (NOT (EQUAL ?X ?Y))}}
{\mbox{\tt (INPUT! ?Y)}}

\eqruleii{3}{\mbox{\tt (EQUAL ?X ?Y)}}
{\mbox{\tt (INPUT! ?X)}}

\eqruleii{4}{\mbox{\tt (EQUAL ?X ?Y)}}
{\mbox{\tt (INPUT! ?Y)}}

\eqruleii{5}{\mbox{\tt (INPUT! (CONS ?X ?Y))}}
{\mbox{\tt (INPUT! ?X)}}

\eqruleii{6}{\mbox{\tt (INPUT! (CONS ?X ?Y))}}
{\mbox{\tt (INPUT! ?Y)}}

basic equality rules

\eqruleii{7}{\mbox{\tt (INPUT! ?X)}}
{\mbox{\tt (EQUAL ?X ?X)}}

\eqruleii{8}{\mbox{\tt (EQUAL ?X ?Y)}}
{\mbox{\tt (EQUAL ?Y ?X)}}

\eqruleiii{9}{\mbox{\tt (EQUAL ?X ?Y)}}
{\mbox{\tt (EQUAL ?Y ?Z)}} {\mbox{\tt (EQUAL ?X ?Z)}}

unification closure rules

\eqruleii{10}{\mbox{\tt (EQUAL (CONS ?X1 ?Y1) (CONS ?X2 ?Y2))}}
{\mbox{\tt (EQUAL ?X1 ?X2)}}

}{

\eqruleii{11}{\mbox{\tt (EQUAL (CONS ?X1 ?Y1) (CONS ?X2 ?Y2))}}
{\mbox{\tt (EQUAL ?Y1 ?Y2)}}

clash rules

\eqruleii{12}{\mbox{\tt (EQUAL ONE ZERO)}}
{\mbox{\tt (UNSATISFIABLE)}}

\eqruleii{13}{\mbox{\tt (EQUAL ZERO (CONS ?X ?Y))}}
{\mbox{\tt (UNSATISFIABLE)}}

\eqruleii{14}{\mbox{\tt (EQUAL ONE (CONS ?X ?Y))}}
{\mbox{\tt (UNSATISFIABLE)}}

congruence rule

\eqrulev{15}{\mbox{\tt (INPUT! (CONS ?X1 ?Y1))}}
{\mbox{\tt (INPUT! (CONS ?X2 ?Y2))}}
{\mbox{\tt (EQUAL ?X1 ?X2)}}
{\mbox{\tt (EQUAL ?Y1 ?Y2)}}
{\mbox{\tt (EQUAL (CONS ?X1 ?Y1) (CONS ?X2 ?Y2))}}

disequation violation rule

\eqruleiii{16}{\mbox{\tt (EQUAL ?X ?Y)}}{\mbox{\tt (NOT (EQUAL ?X ?Y))}}{\mbox{\tt (UNSATISFIABLE)}}

occurs-check rule

\eqruleiii{17}{\mbox{\tt (EQUAL ?X ?Y)}}
{\mbox{\tt (OCCURS-IN ?X ?Y)}}
{\mbox{\tt (UNSATISFIABLE)}}}
}

\vfill

\eject

{\bf Part a. (5 points)}  Notice that the above rules do not have any way of deriving formulas of
the form {\tt (OCCURS-IN $u$ $w$)}.  Give an example of an unsatisfiable set of equations
and disequations whose unsatisfiability can not be derived by the above rules.

\vspace{1.5in}

{\bf Part b. (8 points)}  Give inference rules for deriving formulas of the form {\tt (OCCURS-IN $u$ $w$)}
such that when your rules are added to the above the result is a correct decision procedure
for determining the satisfiability of a set of equality and disequality constraints on expressions,
i.e., the rules can derive the formula {\tt (UNSATISFIABLE)} if and only if the input
equalities and disequalities are unsatisfiable.  This can be done with four rules.
Your rules should have the property that forward chaining inference from a finite set of
premises can only generate a finite set of assertions.

\vfill
\eject

{\bf Part c. (7 points)} Let $n$ be the number of expressions in the input equations and disequations
(including all subexpressions).  Recall that the rules can be run to completion in time proportional
to the number of prefix firings of the rules.
Give the order of the number of prefix firings as a function of $n$ involved in running
the forward chaining unification
algorithm defined by the above rules plus the rules you gave in part b.  Identify the rule
or rules with the largest order of growth in number of prefix firings.

\vfill

{\bf Part d. (5 points)} Suppose that we remove rule 15 from the above rule set.  Give an example
of an unsatisfiable set of equations and disequations such that the above rules together with
your rules from part b, but minus rule 15, can not derive the unsatisfiability.

\vfill
\eject

{\bf Problem 5. (25 points)} This problem is on games.  Recall that in
$\alpha$-$\beta$ search we are only interested in values greater than
or equal to $\alpha$ and less than or equal to $\beta$.  Consider a
version of $\alpha$-$\beta$ search such that if the static value of a
node is at least $\beta + \Delta$ then the procedure terminates and
returns $\beta$, and if the static value is no greater than
$\alpha-\Delta$ then the procedure terminates and returns $\alpha$.
Of course the procedure also terminates if the appropriate depth bound
is reached.  Consider a game tree in which each max node $n$ has
$b_1$ children with the same static value as $n$ and $b_2$ children
whose static value is the static value of $n$ minus $\Delta$.  Dually,
a min node $m$ has $b_1$ children with the same static value as $m$
and $b_2$ children with static equal to the static value of $m$ plus
$\Delta$.  Now consider searching this tree to depth $d$ using the
version of $\alpha$-$\beta$ just described.  We assume that the
initial values of $\alpha$ and $\beta$ are $-\infty$ and $+\infty$
respectively and that the root node is a max node with static value 0.
We also assume optimal move ordering.

{\bf Part a. (5 points)}  Assume that $b_1 = 2$ and $b_2 = 0$.  In this
case all static values are 0.  In this case how many leaf nodes are
there in a four ply search tree under the conditions described above.
Explain your answer (do more than simply quote a formula).

\vfill

{\bf Part b. (7 points)} For $b_1 = b_2 = 2$
draw the four ply search tree explored by $\alpha$-$\beta$ search under
the conditions described above.

\vfill

{\bf Part c. (13 points)} Give the order
of the number of nodes searched as a function of the two branching
factors $b_1$ and $b_2$ and the depth $d$.  Do not try to compute
the exact value --- just give the order of growth.  Explain your answer.

\vfill

\end{document}