\documentstyle[12pt]{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 1992}
\centerline{\bf \large Problem Set 2}
\medskip
\medskip

\centerline{Due:  Beginning of class Wednesday, September 29}

\noindent
{\bf Problem 1} This problem is on the backpropagation learning procedure.
There are many kinds of parameterized ``networks''.
Consider a linear sum of $n$ inputs defined by

$$N(x_1,\;\ldots,\;x_n)  = \sum_{1 \leq i \leq n} a_i x_i$$

We now define another function $M$ of $n$ inputs by computing a polynomial
in $N$.  More specifically we define $M(\vec{x})$ as follows

$$M(\vec{x}) = b_0 + b_1[N(\vec{x}) + b_2[N(\vec{x})+ b_3N(\vec{x})]]$$

Assume that you are given the parameters $a_i$ and $b_j$ that define
the function $M$ and a single input output pair $\tuple{\vec{x},\;y}$.
Give a gradient descent procedure for computing a small change in the
network parameters $a_i$ and $b_j$ that reduces the
error on this input output pair.  Explain how your procedure can be used
as an ``on line'' method of training this network to simulate a desired
function.

{\bf Problem 2.} This problem is about the Bayesian inference
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$.

In this problem we will define a probability distribution over
concepts using a {\em stochastic context free grammar}.  A normal
(nonstochastic) context free grammar is defined by symbols that are divided
into terminal symbols and nonterminal symbols plus a set of {\em productions}
each of which has the form
$$X \rightarrow s_1 s_2 \ldots s_n$$
where $X$ is a nonterminal and each $s_i$ is a symbol, either terminal
or nonterminal.  The productions are rewrite rules for replacing nonterminal
symbols by other strings.  For example, consider the following grammar.
$$X \rightarrow aXb$$
$$X \rightarrow c$$
In the above grammar $X$ is a nonterminal symbol and $a$, $b$, and $c$ are
terminal symbols.  By selecting between the above two productions for
rewriting $X$, the symbol $X$ can be rewritten to $c$, or $acb$ or $aacbb$
or any string of the form $a^ncb^n$.  For any context free grammar and any
nonterminal symbol $X$ in that grammar, the set of strings of terminal
symbols that can be generated from $X$ using the productions of the
language is called the language generated by $X$.
The symbol $F$ in the following context free grammar generates all the Boolean concepts
over the attributes $x_1$, $\ldots$ $x_n$.

$$F \rightarrow (F \wedge F)$$
$$F \rightarrow (F \vee F)$$
$$F \rightarrow L$$
$$L \rightarrow (\neg A)$$
$$L \rightarrow A$$
$$A \rightarrow x_1$$
$$\vdots$$
$$A \rightarrow x_n$$

A stochastic context free grammar is a context free grammar in which
each production is associated with a real number in the interval $[0,1]$
and such that for each nonterminal symbol $X$ the sum of the weights of
the productions from $X$ is 1.  The above grammar can be converted
to a stochastic context free grammar by adding weights to the above
productions as follows.

$${F}\stackrel{\frac{1}{3}}{\rightarrow}{(F \wedge F)}$$
$${F}\stackrel{\frac{1}{3}}{\rightarrow}{(F \vee F)}$$
$${F}\stackrel{\frac{1}{3}}{\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}$$
$$\vdots$$
$${A}\stackrel{\frac{1}{n}}{\rightarrow}{x_n}$$

We can now define a random process for rewriting nonterminals in which
every time a nonterminal symbol is rewritten we select a production
for that nonterminal in such a way that the probability of selecting
a given production equals the given weight of that production.  In any
grammar where each nonterminal generates a nonempty language this
process determines a probability distribution over the strings in the
language generated by each nonterminal symbol (the sum of the probabilities
of all strings in the language equals 1).
The above grammar determines a probability distribution over Boolean
formulas.

Suppose that we are trying to learn a target concept where the target
concept has been generated independently at random using the above
grammar.  After the target concept has been selected, instances for
{\em on which the concept is true} are selected at random, giving each
instance on which the concept is true equal probability.  Let $\Psi_1$
be the formula $(f_1 \wedge f_2)$ and let $\Psi_2$ be the formula
$(f_1 \wedge (f_2 \wedge f_3))$.  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_1|D)$ larger than $P_r(\Psi_2|D)$?  Justify your answer.

{\bf Problem 3}.  This problem is on the maximum entropy assumption.
Consider a wheel such as those used on game shows.  This
wheel has three possible outcomes numbered 1, 2, and 3.
Suppose that we are told that the wheel is biased so that
the expected value on any spin is 1.5 (if all three numbers
where equally likely the expected value would be 2).
Give a numerical approximation to the maximum entropy probability distribution
over the three possible outcomes subject to the constraint that the expected value
is 1.5.

{\bf Problem 4.} This problem is also on the maximum entropy assumption.
Consider three propositions $P$, $Q$ and $R$.  In the maximum entropy
distribution on the truth assignments to these propositions, what
is the probability that $P$ is true?  Now suppose that we
are given the constraint that $P_r(R|P) = 0$.  What is the probability
that $P$ is assigned true in the maximum entropy distribution satisfying
this constraint?

\end{document}