\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 Midterm Exam} {\bf name} \rule{6in}{2pt} There are four 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. (25 pojnts)} This problem is on PAC learning. Consider objects with $n$ linear attributes where each object assigns each attribute $x_i$ an integer value from 1 to $2^k$ ($k$ is the number of bits used to represent the integer $x_i$). We consider conjunctive concepts defined by conditions of the form $$x_1 \in [l_1,\;u_1] \wedge x_2 \in [l_2,\;u_2] \wedge \ldots \wedge x_n \in [l_n,\;u_n]$$ where each $l_i$ and $u_i$ is an integer in the range $[1,\;2^k]$ and $l_i \leq u_i$. {\bf part a. (8 points)} From the cardinality of this concept space give a number of examples that suffices to ensure PAC learning, i.e., such that with probability $1- \delta$ all concepts consistent with the examples have error rate no larger than $\epsilon$. Your answer should be given in terms of $n$, $k$, $\delta$ and $\epsilon$. \vfill {\bf part b. (8 points)} Derive a number of examples sufficient for PAC learning using the VC dimension of this concept space. Your answer should depend only on $n$, $\delta$, and $\epsilon$ (and not on $k$). \vfill {\bf part c. (9 points)} The answers to both parts a and b should be linear in $n$ (holding the other parameters fixed). Give a relationship between $k$ and $\epsilon$ which guarantees that the sample complexity from part $a$ is smaller than the sample complexity from part $b$ (Hint: you only need to look at the linear term containing $n$ in your answers to parts a and b). Assume $\epsilon$ is $\frac{1}{32}$ (or $2^{-5}$) and give an approximate value for $k$ such that if we use no more than $k$ bits per number then the bound from part a is no smaller than the bound from part b. \vfill \eject \noindent {\bf Problem 2. (25 points)} This problem is on the backpropagation learning procedure. Suppose that we represent a function as a mixture of Gaussians. $$f(x) = \sum_{1 \leq j \leq k} a_j e^{\frac{-(x-m_j)^2}{2\sigma_j^2}}$$ Assume that you are given the parameters $a_j$, $m_j$, and $\sigma_j$ that define the function $f$. Also suppose that you are given a set $\{\tuple{x_1,\;y_1},\;\ldots,\;\tuple{x_n,\;y_n}\}$ of desired input/output pairs. {\bf part a. (9 points)} Give gradiant descent equations for updating the parameters $a_j$, $m_j$, and $\sigma_j$ to reduce the error $\sum_i (y_i - f(x_i))^2$. \vspace{2.0in} {\bf part b. (6 points)} Suppose that the function we are trying to learn is actually a sine wave. The data points $\tuple{x_i, y_i}$ consist of 100 points where the values $x_i$ are evenly spaced from 0 to $4\pi$ and that $y_i = \sin x_i$. Also suppose that we are using three Gausians ($k = 3$). Draw graphs of two different functions $f_1$ and $f_2$ each of which are a sum of three Guasians and each of which are possible functions that the gradiant descent procedure could converge on given this data. \bigskip \epsfxsize 6.5in \centerline{\epsffile{./graphs.ps}} \vfill \eject {\bf part b. (9 points)} This form of gradiant descent is a special case of a least squares fit (we are trying to minimize the sum squared error). Is a least squares fit in general best viewed as a maximum likelihood (ML) technique or a maximum a-posteriori probability (MAP) technique. Explain your answer. \vspace{3.0in} % %{\bf Problem 3.} Consider the problem of recognizing a wrench on a table %using a camera looking down from the ceiling. We assume that the wrench is %lying flat. We use a corner detector on the image which recognizes corners. %Here we represent corners using only the coordinates of the vertex of the corner. %A corner $c$ is represented here by two numbers $\tuple{x_c,\;y_c}$. %We model the wrench %as a tuple of corners $\tuple{M_1,\;\ldots,\;M_m}$ where %each $M_i$ is a point $\tuple{x_{M_i},\;y_{M_i}}$. %The result of running the corner detector on the image %is a tuple $Y = \tuple{Y_1,\;\ldots,\;Y_n}$ where each $Y_i$ is a %corner $\tuple{x_{Y_i},\;y_{Y_i}}$ %represented by the coordinates of its vertex. %The problem is to find the wrench in the image by lining up the model %corners in the wrench with the corners discovered by the corner detector. % %We assume that the corner vector is generated by the wrench %position (the position is called the pose) plus ``noise''. %The noise can do one of three things. It can delete wrench corners so that %only some of the wrench corners show up as detected corners in the image. It can add %corners to image at random places. It can also move a wrench corner by %some amount. % %We can hypothesize a correspondence between the wrench corners %and the corners detected in the image. This corespondence hypothesis is a tuple %$\Gamma = \tuple{\Gamma_1,\;\ldots,\;\Gamma_n}$ where each $\Gamma$ %specifies whether detected corner $Y_i$ is from the wrench or from noise, and %if it is from the wrench, which wrench corner it is. %Each $\Gamma_i$ is either $\bot$, indicating that corner $Y_i$ %is to be interpreted as noise, or is a wrench corner $M_j$. % %In this problem we assume that the %orientation of the wrench on the table is the same as the orientation of %the wrenchWhich ever answer in the model. This implies that we only need consider %translations of the wrence. The pose will be taken to be a vector %$\beta = \tuple{x_\beta,\;y_\beta}$. The true position of the wrench %in the image is simply a translation of the wrench corners. %We let $P(M_i,\;\beta)$ be an expression for the position of the wrench corner $M_i$ %under pose $\beta$. %We assume that the probability distribution over detected corner %$Y_i$ given $\Gamma$ and $\beta$ is given by % %$$P_r(Y_i|\Gamma,\beta) = \left\{ \begin{array}{ll} % \frac{1}{W^2} & \mbox{if $\Gamma_i = \bot$} \\ % \frac{1}{\sigma\sqrt{2\pi}}e^{-\frac{|Y_i - P(\Gamma_i,\;\beta)|^2}{2\sigma^2}} & \mbox{otherwise} % \end{array} \right.$$ % %where $W$ is the linear dimension of the image and $|X-Y|^2$ represents the square of the length of the vector from $X$ to $Y$. % %{\bf part a.} Give an expression for $P(M_i,\;\beta)$. % %{\bf part b.} Assuming that the noise used in generating each individual %detected corner is indepenent of the noise for the other corners %give an expression for $P_r(Y|\Gamma,\;\beta)$. % %{\bf part c.} If we select the pair $\tuple{\Gamma,\;\beta}$ which maximizes %$P_r(Y|\;\Gamma,\;\beta)$ are we using maximum likelihood (ML) or maximum a-posteriori %probability (MAP). Explain your answer. % %{\bf part d.} Intuitively, there is a trade off between the number of detected corners %matched and the ``tightness'' of the match. For example, it may be possible to find %a pose $\beta_1$ and a correpondence $\Gamma_1$ such that $\Gamma_1$ assigns a model corner %to four of the detected corners and each of these assigned corners fits the detected corner %extremely well. On the other hand it might be possible to find a $\Gamma_2$ and a $\beta_2$ --- %corresponding to a different location of the wrench, where $\Gamma_2$ assigns ten (rather than four) %detected corners to model corners but (because there are more corners involved) the %best pose $\beta_2$ only gives an approximate alignment of the ten assigned corners and %their corresponding model corners. Suppose that the mismatch distances (the distances %of the form $|Y_i - P(\Gamma_i,\;\beta)|$) involved in $\tuple{\Gamma_1,\;\beta_1}$ %are smaller than the noise standard deviation $\sigma$ but the the mismatch distances in $\tuple{\Gamma_2,\;\beta_2}$ %are large compared to $\sigma$. In this case should we prefer $\tuple{\Gamma_1,\;\beta_1}$ %or $\tuple{\Gamma_2,\;\beta_2}$ under the preference criterion used in part c? %Explain your answer. % %{\bf part e.} Again consider $\tuple{\Gamma_1,\;\beta_1}$ and $\tuple{\Gamma_2,\;\beta_2}$ as in part d. %Suppose that we now increase $\sigma$ so that %the mismatch distances involved in both $\tuple{\Gamma_1,\;\beta_1}$ and $\tuple{\Gamma_2,\;\beta_2}$ %are small compared to $\sigma$ but $\sigma$ is still small compared the image dimension $W$. %In this case should we prefer $\tuple{\Gamma_1,\;\beta_1}$ %or $\tuple{\Gamma_2,\;\beta_2}$ under the preference criterion used in part c? %Explain your answer. \eject {\bf Problem 3. (25 points)} Consider a Bayesian network which is an $n$ level binary tree with arcs directed from parents to children and ending in the $2^n$ leaves of the tree. Each node in this tree is a Boolean variable where the probability that a node has the same value as its parent is $(1-\epsilon)$ with $0 < \epsilon < \frac{1}{2}$. The prior probability that the root node is true is $\frac{1}{2}$. We use $P_n$ to represent a node that is $n$ arcs above the leaf nodes. %{\bf part a.} Suppose that the tree is two levels deep (and hence has four leaf nodes). %In this case $P_2$ is the root of the tree. Give an expression for $P_r(P_2=T\;|\;O)$ %where $O$ is the observation that all the leaves are true. Your answer should be a %function of $\epsilon$. {\bf part a. (6 points)} Consider the execution of the tree network shown below. What is the probability of the given execution, i.e., what is the probability of this assignment of values to nodes. Your answer should be given as a function of $\epsilon$. \bigskip \centerline{\epsffile{./tree.ps}} \vfill {\bf part b. (9 points)} Consider the case where all leaf nodes are observed to have value $T$. Recall that $\beta_{P_n}(T)$ is the probability of the oservations below the node $P_n$ given that $P_n = T$. $\beta_{P_n}(F)$ is defined similarly. For each $n$ these numbers can be written as polynomials in $\epsilon$. Since $\epsilon$ is in the interval $(0,\;\frac{1}{2})$ we take the order of a polynomial in $\epsilon$ to be {\em smallest} exponent of $\epsilon$ in a nonzero term. For example, the order of $1+ \epsilon$ is 0 and the order of $3\epsilon^2 + \epsilon^3$ is 2. The polynomial 0, i.e., the function that is always 0, should be considered to have infinite order (note that $0 = \epsilon^{\infty}$). Give the orders of the polynomials for $\beta_{P_n}(T)$ and $\beta_{P_n}(F)$ as a function of $n$. (The answer is a very simple function.) \vfill \eject {\bf part c. (9 points)} Now consider a set of observations $O$ at the leaves of a tree with $n$ levels of arcs and root node $n$. We allow $O$ to be arbitrary (some of the observed values may be $F$). For the fixed observation set $O$ consider all the possible ways that the network can be executed starting with root value $P_n = T$ and ending in the observed values $O$. A given execution corresponds to a particular set of values for all the internal nodes of the tree. For a given execution we consider the number of ``changes'' in the execution, i.e., the number of nodes whose values are different from the value of its parent. Define $B_{P_n}(T)$ to be the minimum over all executions of the number of changes of that execution. Circle the true statement in the following list and explain your answer. \begin{itemize} \item The order of the polynomial for $\beta_{P_n}$ is always less than $B_{P_n}(T)$. \item The order of the polynomial for $\beta_{P_n}$ is always larger than $B_{P_n}(T)$. \item The order of the polynomial for $\beta_{P_n}$ is always equal to $B_{P_n}(T)$. \item For trees and data sets the order of the polynomial for $\beta_{P_n}$ is less than $B_{P_n}(T)$ but for other trees and data sets the order of the polynomial for $\beta_{P_n}$ is greater than $B_{P_n}(T)$. \end{itemize} Hint: $\beta_{P_n}(T)$ is the sum over all executions $E$, consistent with the oservations $O$, of $P_r(E\; |\; P_n=T)$. \vspace{.5in} \vfill \eject {\bf Problem 4. (25 points)} This problem is about using inference rules to reason about Bayesian networks. Suppose we are given a tree structured Bayesian network with observed values at all of the leaves. The tree may have nonuniform depth. We want to find the most likely execution of the network given that the root node has value $T$ and the leaf nodes have their observed values. We assume that the Bayesian network is a binary tree. Every node other than the leaves has exactly two children. We suppose that the Bayesian network and the observations $O$ are represented by assertions in a data base of the following forms. \begin{itemize} \item The assertion {\tt (LEFT-CHILD $n$ $m$)} means that $m$ is the left child of $n$. \item The assertion {\tt (RIGHT-CHILD $n$ $m$)} means that $m$ is the right child of $n$. \item The assertion {\tt (CONDITIONAL-COMPLEXITY $X$ $x$ $Y$ $y$ $w$)} means that $Y$ is a child node of the node $X$ and $w = - \log_2 P_r(Y=y\;|\;X=x)$. \item The assertion {\tt (OBSERVED $Z$ $z$)} means that $Z$ is a leaf node which has been observed to have value $z$. \end{itemize} To find the most likely execution given the data we let $E_X$ be the set of possible executions of the nodes at or below $X$, i.e., the set of all possible assignments of values to $X$ and the nodes below $X$. For a given node $X$ and possible value $x$ for $X$ we define $\delta_X(x)$ as follows. $$\delta_X(x) = \max_{e \in E_x} P_r(e \wedge O | X=x)$$ In English, $\delta_X(x)$ is the probability of the most likely execution $e$ of the nodes at or below $X$ such that $e$ is consistent with the observations $O$. If $Z$ is a leaf node observed to have value $z$ then $\delta_Z(z) = 1$. If $Z$ is a leaf node and $w$ is some possible value for $Z$ other than the observed value then $\delta_Z(w) = 0$. We define $C_X(x)$ to be $- \log_2 \delta_X(x)$. Note that if $w$ is a possible value for $Z$ other than the observed value for $z$ then $C_Z(w) = \infty$. In this case we can ignore the value $w$ for $Z$. If $z$ is the observed value for leaf $X$ then $C_Z(z) = 0$. We wish to infer assertions of the following form. \begin{itemize} \item The assertion {\tt ($\leq$ (C $X$ $x$) $w$)} means that $C_X(x) \leq w$ \end{itemize} \vfill \eject {\bf part a. (13 points)} Give two inference rules for infering bound assertions such as the above. The inference rules should be capable of infering an exact value for each complexity $C_X(x)$ in the network. \vfill {\bf part b. (12 points)} Assume that there are $n$ nodes in the network and that each node has $d$ possible values. Give the order of running time for executing the rules you gave in part a according to the ``Dijkstra tightest bounds'' algorithm. Your answer should be in terms of $n$ and $d$. \vfill \end{document}