\documentstyle[fancyheadings,12pt]{article}

\pagestyle{fancy}

\addtolength{\headheight}{5pt}

\setlength{\headrulewidth}{1pt}


\setlength{\topmargin}{-0.6in}		%for dvi-imagen
\setlength{\oddsidemargin}{0.0in}   	%prev:-0.1 for dvi-imagen, -ve needed.
\setlength{\headheight}{.3in}
\setlength{\headsep}{.3in}
\setlength{\textheight}{8.8in}
\setlength{\textwidth}{6.5in} 
\setlength{\marginparwidth}{0in}
\setlength{\marginparsep}{0in}
\setlength{\marginparpush}{0in}

\lhead{Comp.Exam. Answers}

\chead{Artificial Intelligence}

\rhead{Fall 1995}

\cfoot{}



\setcounter{secnumdepth}{3}	%to get numbers on subsubsection in text
				%default is 2.
\setcounter{tocdepth}{3}	%to get numbers on subsubsection in toc
				%default is 2.
\setlength{\unitlength}{1mm}
\renewcommand{\baselinestretch}{1.2}  % for kind of double spacing
%\setlength{\parskip}{.3in}
\setlength{\baselineskip}{0.5cm} %JUST CHANGED FROM 0.5
\setlength{\parindent}{0.3in} %JUST CHANGED FROM 0.2
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%55

\newcommand{\ria}{\rightarrow}
\newcommand{\Ria}{\Rightarrow}
\newcommand{\ul}{\underline}
\newcommand{\ol}{\overline}
\newcommand{\xsp}{\hspace{0.5em}}
\newcommand{\ysp}{\vspace{1.1ex}}
\newcommand{\appr}{\sqsubseteq}
\newcommand{\trr}{\triangleright}
\newcommand{\lf}{\tt} %%%%%%%%%%%%%%%%%%%%%%%%%%%% LISP FONT, MAYBE CHANGE LATER
\newcommand{\etal}{{\em et al.}} 
\newcommand{\etc}{{\em et cetera}} 
\newcommand{\eto}{ evaluates to }
\newcommand{\col}{ Common Lisp}

\def\heading#1{ \begin{center} {\bf \ul{#1}} \end{center}}

\newcommand{\asmtabs}
	{mmmmm\=mmmmmmmm\=mmmmmmmm\=mmmmmmmmmmmmmmm\=  \kill}
\newtheorem{thm}{Theorem}
\newtheorem{propn}[thm]{Proposition}
\newtheorem{defn}{Definition}
\newtheorem{examp}{Example}
\newtheorem{exercises}{Exercises}
\newtheorem{program}{Program}

\def\correct#1{\relax \ifmmode \expandafter #1 \else
$\expandafter #1$\fi}            % forces mathmode

\def\db#1{\correct{[\![ #1 ]\!]}}
\def\exer#1{\begin{exercises} \rm
{ #1 }
\end{exercises}}
\def\th#1{\begin{thm} \rm
{ #1 }
\end{thm}}
\def\exam#1{\begin{examp} \rm
{ #1 }
\end{examp}}
\def\lem#1{\begin{lemma} \rm
{ #1 }
\end{lemma}}
\def\prog#1{\begin{program} \rm
{ #1 }
\end{program}}
\def\verba#1{\begin{verbatim}
{ #1 }
\end{verbatim}}

\begin{document}
\setlength{\itemsep}{\parskip} 

{\bf Answer one of the first two questions, and all the remaining questions.}
\normalsize
%%%%%%%%%%%%%%%%%%%%%%
\begin{enumerate}
\item
Two astronomers make measurements $M_1$ and $M_2$
 of the number of stars $N$ in some small region of the sky,
 using their telescopes.
Each telescope can be out of focus (events $F_1$ and $F_2$),
 leading to errors in counting.
A final conclusion about $N'$, the number of stars, needs to be made
 based on the astronomers' measurements.

Construct a belief network or probabilistic
 inference network relating $M_1, M_2, N, N', F_1$ and $F_2$.
A priori, $P(N=1)= P(N=2) = 2*P(N=0) = 2*P(N=3)$.
The probability that a telescope is out of focus is 0.2.
If a telescope is out of focus, the resulting measurement may be 0,1,2 or 3
 with equal probability.
If a telescope is not out of focus, we can expect the resulting measurement
 to be accurate.

If $M_1 =1$ and $M_2 = 3$, what is the most likely number of stars ($N$)?
 Give clear reasons for your answer.
State all simplifying assumptions.

{\bf ANSWER:}
$$F_1 \ria M_1$$
$$F_2 \ria M_2$$
$$N \ria M_1$$
$$N \ria M_2$$
$$M_1 \ria N'$$
$$M_2 \ria N'$$

$$P(N = 0) = P(N=3) = 1/6; ~~~~ P(N=1)=P(N=2) = 1/3$$

$$P(M_1 =0 ~ | ~ N=1 ) =
P(M_1 =2 ~ | ~ N=1 ) =
P(M_1 =3 ~ | ~ N=1 ) = 0.05$$

$$P(M_1 =1 ~ | ~ N=1 ) = 0.85$$

$$P(M_2 =0 ~ | ~ N=3 ) =
P(M_2 =1 ~ | ~ N=3 ) =
P(M_2 =2 ~ | ~ N=3 ) = 0.05$$

$$P(M_2 =3 ~ | ~ N=3 ) = 0.85$$

Assume independence of $F_1, F_2$.

$P(N=1 | ~~ M_1 =1 ~ \& ~ M_2 =3)$ is  twice
$P(N=3 | ~~ M_1 =1 ~ \& ~ M_2 =3)$,
the same proportion as the prior probabilities $P(N=1), P(N=3)$,
and  much  larger than 
$P(N=0 | ~~ M_1 =1 ~ \& ~ M_2 =3)$ and
$P(N=2 | ~~ M_1 =1 ~ \& ~ M_2 =3)$,
which assume that both telescopes are faulty (for which the probability 
 is 0.04).

Therefore the conclusion is that there is only one star in the region.

\item
Regions in a bitmap image are painted using the three patterns below:

\begin{tabular}{cccc}
010 &~~~~ 111 &~~~~ 101 \\
010 &~~~~ 111 &~~~~ 010 \\
010 &~~~~ 111 &~~~~ 101 
\end{tabular}

The first pattern consists of a single vertical line of 1's,
the second pattern is filled with 1's,
and third consists of alternating 1's and 0's.

The size of a region painted with a pattern may be arbitrarily large.
The following is an example of such an image containing each of these four patterns:\\
\begin{verbatim}
000000000111
000000000111
000000000111
101000000111
010000010000
101000010000
000000010000
000000010000
000000010000
\end{verbatim}

Design a neural network to identify the presence of such patterns in an image.

{\bf ANSWER:}
Many answers are possible.
One solution is to define a feature-detecting module for each pattern,
and apply a copy of  each module to each small $3 \times 3 $
region of the input, and (for each module)
take an OR of the outputs of copies of the module.

\item
\begin{quote} \sf
Animals can outrun any animals that they eat.
Carnivores eat other animals.
Outrunning is transitive.
Outrunning is antisymmetric.
Lions eat zebras.
Zebras outrun dogs.
Dogs are carnivores.
Dogs eat zebras. \rm
\end{quote}

Translate the above statements into first order logic,
 and use resolution to show that {\sf zebras eat lions}.
A formal proof is expected.

{\bf ANSWER:}
First you must define the predicates and constants used.
For clarity, I will use uppercase letters for predicates and constants:
 $E(x,y)$ to stand for ``$x$ EATS $y$,''
$O(x,y)$ for ``$x$ outruns $y$,''
 $C(x)$ for ``$x$ is a carnivore,''
 and constants $L,Z,D$ for ``lions, zebras, dogs'' respectively.

All premises and the goal must be represented using first order logic,
 and the goal must be negated.
All free variables in formulas below are assumed to be universally quantified.

$$E(x,y) \ria O(x,y)$$

$$C(x) \ria \exists y. E(x,y) $$

$$E(L,Z)$$

$$O(Z,D)$$

$$C(D)$$

$$E(D,Z)$$

$$(O(x,y) \& O(y,z)) \ria O(x,z)$$

$$O(x,y) \ria \neg O(y,x)$$

Negation of goal: $\neg E(Z,L)$

Formulas must then be skolemized and translated into clause form:

$$\neg E(x,y) \vee O(x,y)$$

$$\neg C(x) \vee E(x,A)$$

$$E(L,Z)$$

$$O(Z,D)$$

$$C(D)$$

$$E(D,Z)$$

$$\neg O(x,y) \vee \neg O(y,z)) \vee O(x,z)$$

$$\neg O(x,y) \vee \neg O(y,x)$$

$\neg E(Z,L)$

We can then apply the resolution principle, taking care to rename variables:

From $E(D,Z)$ and 
$\neg E(x,y) \vee O(x,y)$,
conclude $O(D,Z)$.

From $O(Z,D)$ and 
$\neg O(x,y) \vee \neg O(y,x)$,
conclude $\neg O(D,Z)$.

From  $O(D,Z)$ and  $\neg O(D,Z)$, a contradiction follows.
Hence the negation of the goal is proved.

\item
Construct an augmented transition network 
for a library information retrieval system
in which users ask (in English)
for information about books on various subjects,
by various authors, and with various titles.
Each user query may contain a subject phrase, title,
 and/or author names.

{\bf ANSWER:}
Consider user queries such as ``Search for books on Automated Learning by Chang
 and Lee.''
The network constructed must have a start node,
 from which arcs are activated by phrases such as 
 ``Search for books'' (and other such phrases),
 and for each possible descriptive word (e.g., ``on, by, titled'')
 branch to a different node corresponding to an author-name node,
 title node, or subject node.
The network must allow multiple specifications, using either 
 backward arcs or multiple forks from these nodes.
Terminal nodes are activated by a punctuation mark such as a period.

\item
What is the Hough transform?
Where is it useful?
Describe an algorithm that uses the Hough transform.

{\bf ANSWER:} Clearly described in reference books.


\item
\begin{enumerate}
\item
How does search in A.I. differ from non-A.I. search techniques?
\item
How may  planning be viewed as a state-space search problem?
Identify the state space,
 initial and final goal states, move set, and 
 ``intelligent'' search methodology.

\end{enumerate}

{\bf ANSWER:}
\begin{enumerate}
\item
 A.I. uses ``heuristic'' search using guesswork and 
 partial/incomplete information to search along more promising paths.
\item
 State space: sequences of actions.

 Initial state: null sequence.

 Goal state: sequence of actions that leads to desired state of the world
 (e.g., red block on blue block on white block).

 Moves: Add to sequence, change symbol in sequence.

 Methodology: Macro-operators, hierarchical planning, formulation of 
 intermediate goals.

\end{enumerate}

\item
Describe the version space approach to concept learning.
What is the scope of applicability of this approach?

{\bf ANSWER:}
Approach described in reference book.
Limited to conjunctive formulas.

\end{enumerate}

\end{document}

