\documentstyle[art12,program,6034]{article}

\def\picture #1 by #2 (#3){
  \vbox to #2{
    \hrule width #1 height 0pt depth 0pt
    \vfill
    \special{picture #3} % this is the low-level interface
    }
  }

\def\scaledpicture #1 by #2 (#3 scaled #4){{
  \dimen0=#1 \dimen1=#2
  \divide\dimen0 by 1000 \multiply\dimen0 by #4
  \divide\dimen1 by 1000 \multiply\dimen1 by #4
  \picture \dimen0 by \dimen1 (#3 scaled #4)}
  }

\begin{document}
\solutions 7 18

\problem{Computing conditional probabilities (5 pts)}

$$P(e=\mbox{\tt {\#}t}|b=\mbox{\tt {\#}f})$$
\begin{program}

(define (cp net target given)
  (/ (infer net (append target given))
     (infer net given)))
     
(infer mcbn1 '((e #t)) '((b #f)))
$$P(d=\mbox{\tt {\#}t},e=\mbox{\tt {\#}t}|a=\mbox{\tt {\#}f},b=\mbox{\tt {\#}f})$$
$$P(a=\mbox{\tt {\#}t}|d=\mbox{\tt {\#}f},e=\mbox{\tt {\#}f})$$

\problem{Modeling complex probabilistic dependence}

Here is a summary of an extended example used by Judea Pearl to introduce Bayes
networks in his classic book, {\em Probabilistic Reasoning in Intelligent
Systems: Networks of Plausible Inference}, Morgan Kaufmann, 1986:
\begin{quotation}
Holmes is worried that his house will be burgled.  For the time period of
interest, there is a $10^{-4}$ {\em a priori} chance of this happening, and
Holmes has installed a burglar alarm to try to forestall this event.  The
alarm is 95\% reliable in sounding when a burglary happens, but also has a
false positive rate of 1\%.  Holmes' neighbor, Watson, is sure (well, say 90\%
sure) to call Holmes at his office if the alarm sounds, but he is also a bit of
a practical joker, and knowing Holmes' concern, might (30\%) call even if the
alarm is silent.  Holmes' other neighbor, Mrs. Gibbons, is a well-known lush
and often befuddled, but Holmes believes that she is four times more likely to
call him if there is an alarm than if not.
\end{quotation}

\subproblem{Building the model (4 pts)}
Draw a Bayes network that describes the above dependencies.  Now define a
Bayes net, {\tt Holmes}, that models this.  Think carefully about the
probabilistic dependencies and exactly what they mean.  Turn in a listing of
the call to {\tt define-bnet} that defines your network.

You will have noticed that the story above does not tell the actual conditional
probability that Gibbons will call if the alarm sounds or that she will call if
the alarm is silent.  Indeed, these probabilities would be quite difficult for
Holmes to estimate.  Fortunately, it is only the likelihood ratio between
these conditions that matters.  You can verify that your choice or particular
numbers to use for the conditional probabilities leading to Gibbons' call are
immaterial so long as their ratio is $4$. 

\subproblem{Calculations (2 pts)}
Within a few minutes of each other, Holmes is phoned by both Watson and Gibbons.
Use your network to calculate the probability that Holmes has suffered a
burglary.

\subproblem{Explaining away (3 pts)}
Realizing that Holmes lives in Los Angeles, it occurs to us that there might be
another explanation for the (probable) alarm at Holmes' house.  If a
sufficiently large earthquake occurs, it may set off the burglar alarm even
without there being a burglary.  Define a new Bayes net, {\tt quake}, based on
the same facts that you used for {\tt holmes}, but with the following
additional story:
\begin{quotation}
Holmes, always the anxious type, listens to KNX, ``News Radio,'' while at work,
which will report, with 95\% reliability, the occurrence of a sufficiently
large quake.  Holmes thinks that a burglary and an earthquake can each set off
his burglar alarm in independent ways that make {\em noisy-or} a good model. 
From his original belief about the probabilistic connection between burglary
and alarm, Holmes can compute a causal probability from burglary to alarm and a
leak probability for an alarm occurring in the absence of a burglary.  He
estimates the probability of a quake causing an alarm as 60\%.  The incidence
of quakes in Los Angeles is equal to the incidence of burglaries.
\end{quotation}
Use the {\tt quake} network to calculate the probability of Holmes' house
having been burgled if he receives calls from Watson and Gibbons, but also
hears the report of a quake on KNX.

\subproblem{Multiple connections (3 pts)}
\begin{quotation}
Holmes realizes that his daughter was planning to visit his house this day, and
would surely (98\%) call if she heard the alarm, unless she was convinced that
it was really the earthquake that had set it off.
\end{quotation}
Build another variation of the {\tt quake} network, {\tt daughter}, in which you
model the daughter's calling or not calling.  Describe and justify the
modeling assumptions that you make, and the numbers you choose.  ({\em Hint:}
There is no single right answer here; choose a reasonable model of this part of
the story and justify it.)

If she does {\em not} call, what is the probability that Holmes' house has in
fact been burgled.  Explain how this relates to the answer from the {\tt quake}
network.

\problem{Probabilistic diagnosis}

Consider the diagnostic domain {\tt dom3} of Problem Set 6, reproduced
and shown graphically in Figure \ref{bpg}.
\begin{figure}[tb]
\begin{center}
\parbox[t]{3in}{
%\begin{tabular}{cc}
{\tt
\begin{tabular}[b]{l}
(define dom3\\
\ \ (make-domain\\
\ \ \ '((a s1 s2 s5)\\
\ \ \ \ \ (b s1 s2 s4)\\
\ \ \ \ \ (c s1 s3 s4 s5)\\
\ \ \ \ \ (d s1 s5)\\
\ \ \ \ \ (e s2 s3 s4)\\
\ \ \ \ \ (f s5)\\
\ \ \ \ \ (g s3 s4)\\
\ \ \ \ \ (h s3 s5)\\
\ \ \ \ \ )))
\end{tabular}
}}\hfil
\parbox[b]{3in}{\begin{tabular}[t]{c}
\scaledpicture {3.71in} by {4.47in} (bpg scaled 750)
\end{tabular}}
%\end{tabular}
\end{center}

\caption{A bipartite graph for a diagnostic problem corresponding to domain
{\tt dom3} of Problem Set 6.  Disorders are letters, symptoms are $s_i$, and
numbers on arcs between diseases and symptoms are the causal probabilities.  We
assume independent causation (i.e., noisy-or) combination of causal influences
at each symptom, with a uniform leak probability of 0.05.} 
\label{bpg}
\end{figure}

\subproblem{Defining a bipartite graph Bayesian problem (3 pts)}

Use {\tt define-bnet} (much as it is used in defining {\tt mcbn2} in {\tt
examples.scm}) to define the network corresponding to the diagnostic domain
{\tt dom3} with the additional probabilistic information shown in Figure
\ref{bpg}.  Turn in a listing of the expression you use to define this net.

\subproblem{Exploring absent symptoms (2 pts)}

Use the program you wrote for computing conditional probabilities to compute the
probability of disease {\tt a} given that symptoms {\tt s1}, {\tt s2} and {\tt
s3} are present.

Now compute the probability of {\tt a} given that those symptoms are present
but that {\tt s4} and {\tt s5} are absent.  If the answer differs from the
previous one, why?  Contrast this behavior with the treatment that set-cover
diagnosis gives to {\em absent} symptoms.

\subproblem{Joint probabilities of multiple diseases (2 pts)}

Calculate, as above, the probability of disease {\tt e} assuming only that
symptoms {\tt s1}, {\tt s2} and {\tt s3} are present.

Calculate, similarly, the probability of disease {\tt h} under the same
condition.

Ben Bitdiddle (remember {\em him}?) suggests that the probability that
{\tt a}, {\tt e} and {\tt h} are present together is just the
product of the probabilities that each is present by itself (as you've just
computed).  Check his suggestion by computing the joint probability of these
three diseases given that symptoms {\tt s1}, {\tt s2} and {\tt s3} are
present.  Comment on the sagacity of Ben's advice.

\subproblem{Use for diagnosis (3 pts)}

Assuming that {\tt s1}, {\tt s2} and {\tt s3} are present and {\tt s4} and
{\tt s5} are absent, find the most likely set of diseases.  You should not need
to explore the $2^8$ possibilities, if you think about which sets seem like
promising candidates, and if you are willing to take a slight risk of missing
the very best.  {\em Hint:} We do not expect you to write a program to do this,
but just to explore ``by hand'' the most likely sets of diseases.

\problem{Grand Synthesis}

\subproblem{Design (3 pts)}

Describe a general solution to the previous subproblem (finding
the most likely set of diseases to explain the presence/absence of a set of
symptoms).  You should find the set-cover algorithm and our code here to be
very useful.

\subproblem{Implementation (Extra Credit of 5 pts)}

Implement the design you sketched in the preceding subproblem.  You probably need
to build both a domain (in the lingo of ps6) and a Bayes net for the same
disease-symptom relationships, unless you redefine {\tt causes} and {\tt
consequences} to work off the Bayes net data structures directly.  Debugging
your code will be difficult because of the circular data structures and the
consequent problems of printing out.  Note the useful procedures in {\tt
debug.scm} to help ameliorate, but not solve, this problem.

Show your program and demonstrate it on the above example.  Does it get the
same solution that you did?  Why, or why not?

\end{document}