\documentclass{article}
\usepackage{fullpage}
\usepackage{graphicx}
\usepackage[usenames]{color}
\providecommand{\blankanswer}[1]{\vspace{1.5in}}
\providecommand{\answer}[1]{{\color{white}#1 \vspace{0.1in}}}
\renewcommand{\theenumi}{\roman{enumi}.}
\renewcommand{\labelenumi}{\roman{enumi}.}
\def\indep{\perp\!\!\!\perp}
\title{ Written Assignment 3: Probabilistic Models}
\begin{document}
% \maketitle
\begin{center}
{\huge CS188: Artificial Intelligence, Spring 2009}\\
~\\
{\huge Written Assignment 3: Probabilistic Models}\\
~\\
Due: April 16 (extended!)\\
You can work on this in groups, but everyone should turn in his/her own work.\\
Don't forget your \textbf{name and login}.
~\\
~\\
\end{center}
\begin{flushleft}
{\small
{\bf Name:} \\
~\\
{\bf Login:} \\
~\\
{\bf GSI:} \\
~\\
{\bf Section Time:}
}
\end{flushleft}
\thispagestyle{empty}
\section{Question 1: Bayes Net Inference}
Dr. A. Gent, an armchair climatologist, wants to predict whether or not it's going to (R)ain. When it's (C)loudy, it tends to (R)ain unless it's (W)indy. From her armchair, Dr. Gent can observe the clouds (C) but not the wind. However, if it's (W)indy, then the tree outside tends to (S)way, which she can observed. Sometimes the tree (S)ways even when it's not windy. Squirrels, perhaps?
\begin{center}
\includegraphics{q1.pdf}
\end{center}
\begin{center}
\begin{tabular} [t]{|c|c|}
\hline \multicolumn{2}{|c|}{$P(C)$} \\ \hline $C$ & $P(C)$ \\ \hline $c$
& $0.4$ \\ \hline
\end{tabular}
\space
\space
\begin{tabular} [t]{|c|c|}
\hline
\multicolumn{2}{|c|}{$P(W)$} \\ \hline
$W$ & $P(W)$ \\ \hline
$w$ & $0.6$ \\ \hline
\end{tabular}
\space
\space
\begin{tabular} [t]{|c|c|c|c|}
\hline
\multicolumn{4}{|c|}{$P(R|C,W)$} \\ \hline
$C$ & $W$ & $R$ & $P(R=r|C,W)$ \\ \hline
$c$ & $w$ & $r$ &0.40 \\ \hline
$c$ & $\neg w$ & $r$ & 0.80 \\ \hline
$\neg c$ & $w$ & $r$ & 0.10 \\ \hline
$\neg c$ & $\neg w$ & $r$ & 0.20 \\ \hline
\end{tabular}
\space
\space
\begin{tabular} [t]{|c|c|c|}
\hline
\multicolumn{3}{|c|}{$P(S|W)$} \\ \hline
$W$ & $S$ & $P(S=s|W)$ \\ \hline
$w$ & $s$ & $0.9$ \\ \hline
$\neg w$ & $s$ & $0.3$ \\ \hline
\end{tabular}
\end{center}
\emph{Note: the tables above are abbreviated, but fully specified, e.g., $P(\lnot r | c, w) = 1 - P(r | c, w) = 0.6$.}
\paragraph{a)} What is the probability of perfect weather, $P(\lnot c, \lnot r, \lnot w)$?
\vfill
\newpage
\begin{center}
\begin{tabular} [t]{|c|c|}
\hline \multicolumn{2}{|c|}{$P(C)$} \\ \hline $C$ & $P(C)$ \\ \hline $c$
& $0.4$ \\ \hline
\end{tabular}
\space
\space
\begin{tabular} [t]{|c|c|}
\hline
\multicolumn{2}{|c|}{$P(W)$} \\ \hline
$W$ & $P(W)$ \\ \hline
$w$ & $0.6$ \\ \hline
\end{tabular}
\space
\space
\begin{tabular} [t]{|c|c|c|c|}
\hline
\multicolumn{4}{|c|}{$P(R|C,W)$} \\ \hline
$C$ & $W$ & $R$ & $P(R=r|C,W)$ \\ \hline
$c$ & $w$ & $r$ &0.40 \\ \hline
$c$ & $\neg w$ & $r$ & 0.80 \\ \hline
$\neg c$ & $w$ & $r$ & 0.10 \\ \hline
$\neg c$ & $\neg w$ & $r$ & 0.20 \\ \hline
\end{tabular}
\space
\space
\begin{tabular} [t]{|c|c|c|}
\hline
\multicolumn{3}{|c|}{$P(S|W)$} \\ \hline
$W$ & $S$ & $P(S=s|W)$ \\ \hline
$w$ & $s$ & $0.9$ \\ \hline
$\neg w$ & $s$ & $0.3$ \\ \hline
\end{tabular}
\emph{Conditional probability tables (CPTs) are repeated for convenience.}
\end{center}
\paragraph{b)} A \emph{dangling} node is a leaf node that is \emph{unobserved} in a query. When computing $P(C,R,W)$, $S$ is dangling. Show that the probabilities in the CPT for $P(S|W)$ cannot affect $P(C,R,W)$ for this network, regardless of the values in the CPTs above.
\vfill
\paragraph{c)} Can the CPT of a dangling leaf node for a query ever affect the outcome of that query? If so, when? If not, what preprocessing step does this fact suggest for variable elimination?
\vfill
\paragraph{d)} Compute P(R) using the variable elimination algorithm, perhaps modified by your answer to (c). Write down the intermediate factors after summing out each hidden variable. \emph{Hint: you can answer this question with one intermediate factor, in addition to $P(R)$.}
\vfill
\vfill
\paragraph{e)} Now, approximate $P(R | C=\neg c, S=\neg s)$ using each of the two sets of samples below.
Prior samples (rejection sampling):
\begin{tabular}{cccc}
$c,\neg w, s, r$ & $\neg c, w, s, \neg r$ & $c, w, s, \neg r$
& $\neg c, \neg w, \neg s, \neg r$ \\
$\neg c, w, s, \neg r$ & $\neg c, w, \neg s, \neg r$
& $c, \neg w, \neg s, \neg r$
& $c, w, s, r$ \\
$\neg c, w, s, r$ & $c, \neg w, \neg s, r$ & $\neg c, w, s, \neg r$
& $\neg c, w, s, \neg r$ \\
$\neg c, \neg w, \neg s, \neg r$ & $\neg c, w, s, \neg r$
& $c, w, s, \neg r$
& $\neg c, \neg w, s, r$ \\
\end{tabular}
$P(R =r | C=\neg c, S=\neg s) \approx$
\newline
Weighted samples (likelihood weighting):
\begin{tabular}{cc}
$\neg c, w, \neg s, \neg r$
& $\neg c, w, \neg s, r$ \\
$\neg c, \neg w, \neg s, \neg r$
& $\neg c, w, \neg s, \neg r$
\end{tabular}
$P(R = r| C=\neg c, S=\neg s) \approx$
\newpage
\section{Question 2: Conditional Independence Review}
Consider the following Bayes' nets.
\begin{center}
\includegraphics[width=6in]{q2.pdf}
\end{center}
For each of the following conditional independence properties, circle the number of each network for which the statement is guaranteed to be true.
\vfill
$F \indep R $ \hfill (i) \hfill (ii) \hfill (iii) \hfill (iv) \hfill \hfill
\vfill
$F \indep A $ \hfill (i) \hfill (ii) \hfill (iii) \hfill (iv) \hfill \hfill
\vfill
$V \indep A \ | \ F $ \hfill (i) \hfill (ii) \hfill (iii) \hfill (iv) \hfill \hfill
\vfill
$V \indep A \ | \ R $ \hfill (i) \hfill (ii) \hfill (iii) \hfill (iv) \hfill \hfill
\vfill
$F \indep R \ | \ S $ \hfill (i) \hfill (ii) \hfill (iii) \hfill (iv) \hfill \hfill
\vfill
$A \indep R \ | \ V$ \hfill (i) \hfill (ii) \hfill (iii) \hfill (iv) \hfill \hfill
\newpage
\section{Question 3: The Captain's Treasure}
You are searching for the treasure of Captain Long Beard, lost for fifty years. You've narrowed down the search to four sites on the corners of Dinghy Island. Here is what you know:
\begin{enumerate}
\item The treasure is in one of four locations: the North-East, North-West, South-East, or South-West. You assign equal probability to each. Let $L \in \{ne, nw, se, sw\}$ be the (unknown) location of the treasure.
\item You can only dig in one of the four locations. Let $A \in \{ne, nw, se, sw\}$ indicate where you dig.
\item The North of the island is rocky, and the South sandy. If the treasure is in the North and you dig in the correct location, you retrieve the treasure with probability 0.5, whilst if the treasure is in the South and you dig in the correct place, you retrieve it with probability 0.9. Let $T \in \{t,f\}$ be the variable recording whether you retrieve the treasure.
\item The town's guard claims to have seen whether Long Beard took the road to the North or to the South of the island when burying his treasure. The guard is willing to (honestly) tell you what he remembers, but his memory is shaky and biases Northward. If the Captain went North, the guard would remember. If the Captain went South, the guard has a $\frac{1}{4}$ chance of remembering North anyway. Let $G \in \{n,s\}$ be the variable indicating whether the guard remembers the Captain burying the treasure in the North or the South of the island.
\item Your utility $U$ is measured in dollars. The treasure chest is filled with gold, worth \$1000. The East of the island is reachable only by river, so if you dig there you must buy a raft for \$40.
\end{enumerate}
\paragraph{a)} Draw the decision network for this problem and fill in the conditional probability tables for each variable and the utility function table.
\vfill
\begin{center}
\begin{tabular} [t]{|c|c|}
\hline $L$ & $P(L)$ \\
\hline $ne$ & \rule{0pt}{4ex} \\
\hline $nw$ & \rule{0pt}{4ex} \\
\hline $se$ & \rule{0pt}{4ex} \\
\hline $sw$ & \rule{0pt}{4ex} \\
\hline
\end{tabular}
\space
\space
\begin{tabular} [t]{|c|c|c|c|}
\hline $L$ & $A$ & $T$ & $P(T|L,A)$ \\
\hline $ne$ & $ne$ & $t$ & \rule{0pt}{4ex} \\
\hline $nw$ & $nw$ & $t$ & \rule{0pt}{4ex} \\
\hline $se$ & $se$ & $t$ & \rule{0pt}{4ex} \\
\hline $sw$ & $sw$ & $t$ & \rule{0pt}{4ex} \\
\hline \multicolumn{2}{|c|}{$L \neq A$} & $t$ & \rule{0pt}{4ex} \\
\hline
\end{tabular}
\space
\space
\begin{tabular} [t]{|c|c|c|}
\hline $L$ & $G$ & $P(G|L)$ \\
\hline $ne$ & $n$ & \rule{0pt}{4ex} \\
\hline $nw$ & $n$ & \rule{0pt}{4ex} \\
\hline $se$ & $n$ & \rule{0pt}{4ex} \\
\hline $sw$ & $n$ & \rule{0pt}{4ex} \\
\hline
\end{tabular}
\space
\space
\begin{tabular} [t]{|c|c|c|}
\hline $A$ & $T$ & $U(A,T)$ \\
\hline $ne$ & $t$ & \rule{0pt}{4ex} \\
\hline $ne$ & $f$ & \rule{0pt}{4ex} \\
\hline $nw$ & $t$ & \rule{0pt}{4ex} \\
\hline $nw$ & $f$ & \rule{0pt}{4ex} \\
\hline $se$ & $t$ & \rule{0pt}{4ex} \\
\hline $se$ & $f$ & \rule{0pt}{4ex} \\
\hline $sw$ & $t$ & \rule{0pt}{4ex} \\
\hline $sw$ & $f$ & \rule{0pt}{4ex} \\
\hline
\end{tabular}
\end{center}
\newpage
\paragraph{b)} What is the best place to dig if you \emph{do not} know what the town guard remembers. What is the expected utility of this action?
\vfill
\paragraph{c)} Suppose the guard tells you that he remembers the Captain going North. Now what is the best place to dig, and what is the expected utility of this action? \emph{Hint: first compute the distribution $P(L\ |\ G=n)$.}
\vfill
\paragraph{d)} Now suppose the guard tells you that he remembers the Captain going South instead. What is the best place to dig based on this information, and what is the expected utility of this action?
\vfill
\paragraph{e)} What is the value of the guard telling you what he remembers (assuming you don't already know)?
\vfill
\vfill
\paragraph{f)} The guard will only tell you the information if you promise to dig in the East (his wife sells rafts). How much money do you expect to gain (or lose) by accepting his offer, versus digging without his information?
\vfill
\newpage
\section{Question 4: Playing Poker}
You are playing poker against a friend. Over the years, you've collected
data about her tendency to bluff (as opposed to playing her cards straight
up) and decide to model her habits with the following HMM.
\vspace{10pt}
\begin{tabular}{|cc|}
\hline
State & $P(X_1)$ \\
\hline
\it bluff & 0.2 \\
\it straight up & 0.8 \\
\hline
\end{tabular}
\vspace{10pt}
\begin{tabular}{|ccc|}
\hline
Previous State & Current State & $P(X_t|X_{t-1})$ \\
\hline
\it bluff & \it bluff & 0.2 \\
\it bluff & \it straight up & 0.8 \\
\it straight up & \it bluff & 0.6 \\
\it straight up & \it straight up & 0.4 \\
\hline
\end{tabular}
\vspace{10pt}
\begin{tabular}{|ccc|}
\hline
State & Observation & $P(O_t|X_t)$ \\
\hline
\it bluff & \it rolls eyes & 0.6 \\
\it bluff & \it scratches shoulder & 0.4 \\
\it straight up & \it rolls eyes & 0.3 \\
\it straight up & \it scratches shoulder & 0.7 \\
\hline
\end{tabular}
\paragraph{a)} On the first hand, your friend rolls her eyes. What is the posterior probability that she is bluffing on the first hand?
\vfill
\paragraph{b)} You observe two consecutive eye rolls on hands 1 and 2. What's the probability that she is bluffing on the second hand?
\vfill
\vfill
\paragraph{c)} You confirm that she was in fact bluffing on the first two hands. What is the probability that she will bluff again on the third hand?
\vfill
\paragraph{d)} Without any observations, what is the probability that she is bluffing on the $k^{th}$ hand as $k \rightarrow \infty$ ?
\vfill
\newpage
\noindent You now decide to track your friend's behavior via particle filtering. \textbf{You have only two particles, one initially assigned to {\it bluff} and the other to {\it straight up}}.
\paragraph{e)} You observe an eye roll on the first hand. What is the probability that your particles will still be {\it bluff} and {\it straight up} after resampling based on this evidence?
\vfill
\paragraph{f)} After resampling, what is the expected value of the error in your estimate of $P(X_1 = \textit{bluff}\ |\ O_1 = \textit{rolls eyes})$?
\vfill
\vfill
\paragraph{g)} After observing $O_1 =$ \emph{rolls eyes}, you have the option of calling her bluff. A correct call nets you \$3; an incorrect call nets you -\$1. If you do not call her bluff, you net \$0. In dollars, how much more or less money should you expect to make if you use a particle filter with two particles (starting with one for each outcome) to estimate $P(X_1 |\ O_1 = \textit{rolls eyes})$ versus computing it with Bayes rule, assuming you maximize your expected utility given your (possibly approximate) beliefs?
\vfill
\vfill
\end{document}