
\slidehead{Bayesian Learning \red } \bk

\centerline{[Read Ch. 6]}
\centerline{[Suggested exercises: 6.1, 6.2, 6.6]}

\bi
\item Bayes Theorem
\item MAP, ML hypotheses
\item MAP learners
\item Minimum description length principle
\item Bayes optimal classifier
\item Naive Bayes learner
\item Example: Learning over text data
\item Bayesian belief networks
\item Expectation Maximization algorithm
\ei

\slidehead{\large Two Roles for Bayesian Methods \red } \bk

Provides practical learning algorithms:
\bi
\item 
Naive Bayes learning

\item
Bayesian belief network learning

\item 
Combine prior knowledge (prior probabilities) with observed data

\item
Requires prior probabilities
\ei

\bigskip

Provides useful conceptual framework
\bi
\item Provides ``gold standard'' for evaluating other learning algorithms
\item Additional insight into Occam's razor
\ei

\slidehead{\large Bayes Theorem \red } \bk

\[ P(h|D) = \frac{P(D|h) P(h)}{P(D)} \]

\bi
\item $P(h)$ = prior probability of hypothesis $h$
\item $P(D)$ = prior probability of training data $D$
\item $P(h|D)$ = probability of $h$ given $D$
\item $P(D|h)$ = probability of $D$ given $h$
\ei

\slidehead{\large Choosing Hypotheses \red } \bk

\[ P(h|D) = \frac{P(D|h) P(h)}{P(D)} \]

Generally want the most probable hypothesis given the training data

{\em Maximum a posteriori} hypothesis $h_{MAP}$:
\begin{eqnarray}
& h_{MAP} & = \arg \max_{h \in H} P(h|D)\nonumber \\
& & = \arg \max_{h \in H} \frac{P(D|h) P(h)}{P(D)} \nonumber \\
& & = \arg \max_{h \in H}P(D|h) P(h) \nonumber
\end{eqnarray}

\bigskip

If assume $P(h_{i})=P(h_{j})$ then can further simplify, and choose the 
{\em Maximum likelihood} (ML) hypothesis


\[h_{ML} = \arg \max_{h_{i} \in H} P(D|h_{i}) \]


\slidehead{\large Bayes Theorem \red } \bk

Does patient have cancer or not?
\begin{quote}
A patient takes a lab test and the result comes back positive.  The test
returns a correct positive result in only $98\%$ of the cases in which the
disease is actually present, and a correct negative result in only $97\%$ of
the cases in which the disease is not present.  Furthermore, $.008$ of the
entire population have this cancer.
\end{quote}

\begin{eqnarray}
& P(cancer) = \ \ \ \ \ \ \ \ \ \  & P(\neg cancer) =  \ \ \ \ \ \ \ \ \ \ \nonumber \\
& P(+ | cancer) =  \ \ \ \ \ \ \ \ \ \   & P(- | cancer) =   \ \ \ \ \ \ \ \ \ \ \nonumber \\
& P(+ | \neg cancer) =   \ \ \ \ \ \ \ \ \ \  & P(- | \neg cancer) =  \ \ \ \ \ \ \ \ \ \ \nonumber 
\end{eqnarray}


\slidehead{\large Basic Formulas for Probabilities \red } \bk
\bi
\item
{\em Product Rule}: probability $P(A \tand B)$ of a conjunction of two events
A and B:
\[P(A \tand B) = P(A|B) P(B) = P(B|A) P(A) \]

\item
{\em Sum Rule}: probability of a disjunction of two events A and B:
\[P(A \tor B) = P(A) + P(B) - P(A \tand B) \]

\item
{\em Theorem of total probability}: if events $A_{1}, \ldots, A_{n}$ are mutually exclusive with $\sum_{i = 1}^{n} P(A_{i}) = 1$, then
\[P(B) = \sum_{i = 1}^{n} P(B|A_{i}) P(A_{i})\]
\ei

\slidehead{\large Brute Force MAP Hypothesis Learner \red } \bk

\be
\item
For each hypothesis $h$ in $H$, calculate the posterior probability
\[ P(h|D) = \frac{P(D|h) P(h)}{P(D)}\]
\item
Output the hypothesis $h_{MAP}$ with the highest posterior probability
\[h_{MAP} = \argmax_{h \in H} P(h|D)\]

\ee




\slidehead{\large Relation to Concept Learning \red } \bk

Consider our usual concept learning task

\bi
\item instance space $X$, hypothesis space $H$, training examples $D$

\item consider the \pgm{FindS} learning algorithm (outputs most specific
hypothesis from the version space $VS_{H,D}$)
\ei

\bigskip

What would Bayes rule produce as the MAP hypothesis?

\bigskip

Does $FindS$ output a MAP hypothesis??

\slidehead{\large Relation to Concept Learning \red } \bk

Assume fixed set of instances $\langle x_{1}, \ldots, x_{m}\rangle$

Assume $D$ is the set of classifications $D = \langle c(x_{1}),
\ldots, c(x_{m})\rangle$ 

\bigskip
Choose $P(D|h)$:

\slidehead{\large Relation to Concept Learning \red } \bk

Assume fixed set of instances $\langle x_{1}, \ldots, x_{m}\rangle$

Assume $D$ is the set of classifications $D = \langle c(x_{1}),
\ldots, c(x_{m})\rangle$ 

Choose $P(D|h)$
\bi
\item $P(D|h)=1$ if $h$ consistent with $D$
\item $P(D|h)=0$ otherwise
\ei

Choose $P(h)$ to be {\em uniform} distribution
\bi
\item $P(h) = \frac{1}{|H|}$ for all $h$ in $H$
\ei

Then,

\[ P(h|D) = \left\{ \begin{array}{cl}
  \frac{1}{|VS_{H,D}|} & \mbox{if $h$ is consistent with $D$} \\
\\
  0  & \mbox{otherwise} 
\end{array} \right.
\]

\slidehead{\large Evolution of Posterior Probabilities \red } \bk

\hbox{\psfig{file=./bookps/bayes-vs.ps,width=5.5in}}


\slidehead{\large Characterizing Learning Algorithms by Equivalent MAP 
Learners \red } \bk

\hbox{\psfig{file=./bookps/vs-map-equivalent.ps,width=5.5in}}



\slidehead{\large Learning A Real Valued Function \red } \bk

\centerline{\hbox{\psfig{file=./bookps/bayes-linear.epsf,width=2.5in}}}

Consider any real-valued target function $f$

Training examples $\langle x_{i}, d_{i} \rangle$, where $d_{i}$ is noisy
training value
\bi \item $d_{i} = f(x_{i}) + e_{i}$ 
\item $e_{i}$ is random variable (noise) drawn independently for each $x_{i}$ 
according to some Gaussian distribution with mean=0
\ei

Then the maximum likelihood hypothesis $h_{ML}$ is the one that minimizes
the sum of squared errors:

\[ h_{ML} = \arg \min_{h \in H} \sum_{i=1}^{m} \left(d_{i} -
h(x_{i})\right)^{2} \]


\slidehead{\large Learning A Real Valued Function \red } \bk

\begin{eqnarray}
h_{ML} &= &\argmax_{h \in H} p(D|h) \nonumber \\
 &= &\argmax_{h \in H} \prod_{i=1}^{m} p(d_{i}|h) \nonumber \\
&= &\argmax_{h \in H} \prod_{i=1}^{m} \frac{1}{\sqrt{2 \pi \sigma^{2}}}
e^{-\frac{1}{2}(\frac{d_{i} - h(x_{i})}{\sigma})^{2}} \nonumber
\end{eqnarray}

Maximize natural log of this instead...

\begin{eqnarray}
h_{ML}  &= &\argmax_{h \in H}
\sum_{i=1}^{m} \ln \frac{1}{\sqrt{2 \pi \sigma^{2}}} -
\frac{1}{2}\left(\frac{d_{i} - h(x_{i})}{\sigma}\right)^{2} \nonumber \\
  &= &\argmax_{h \in H} \sum_{i=1}^{m} -
\frac{1}{2}\left(\frac{d_{i} - h(x_{i})}{\sigma}\right)^{2} \nonumber \\
 &= &\argmax_{h \in H} \sum_{i=1}^{m} - \left(d_{i} - h(x_{i})\right)^{2}
 \nonumber \\
 &= &\argmin_{h \in H} \sum_{i=1}^{m} \left(d_{i} - h(x_{i})\right)^{2}  \nonumber
\end{eqnarray}

\slidehead{\large Learning to Predict Probabilities \red } \bk

Consider predicting survival probability from patient data

\bigskip

Training examples $\langle x_{i}, d_{i} \rangle$, where $d_{i}$ is 1 or 0

\bigskip

Want to train neural network to output a {\em probability} given $x_i$ (not a
0 or 1)

\vspace*{.5in}

In this case can show

\[ h_{ML} = \argmax_{h \in H} \sum_{i=1}^{m} d_{i} \ln h(x_{i}) + (1-d_{i})
\ln (1 - h(x_{i})) \]


\bigskip

Weight update rule for a sigmoid unit:
\[ w_{jk} \leftarrow w_{jk} +  \Delta w_{jk}\]
where
\[ \Delta w_{jk} = \eta \sum_{i=1}^{m} (d_{i} - h(x_{i})) \  x_{ijk} \]


\slidehead{\large Minimum Description Length Principle \red } \bk

Occam's razor: prefer the shortest hypothesis

\vspace*{.5in}

MDL: prefer the hypothesis $h$ that minimizes
\[h_{MDL} = \argmin_{h \in H} L_{C_{1}}(h) + L_{C_{2}}(D|h) \]
where $L_{C}(x)$ is the description length of $x$ under encoding $C$

\vspace*{.4in}
\rule{\textwidth}{.2mm}\vskip -3mm

\vspace*{.15in}
Example: $H$ =  decision trees, $D$ = training data labels
\bi
\item $L_{C_{1}}(h)$ is \# bits to describe tree $h$
\item $L_{C_{2}}(D|h)$ is \# bits to describe $D$ given $h$
\bi
\item Note $L_{C_{2}}(D|h)=0$ if examples classified perfectly by $h$. Need
only describe exceptions
\ei
\item Hence $h_{MDL}$ trades off tree size for training errors
\ei

\slidehead{\large Minimum Description Length Principle \red } \bk
\begin{eqnarray}
h_{MAP} &= &\arg \max_{h \in H}P(D|h) P(h) \nonumber \\
&= &\arg \max_{h \in H} \log_{2} P(D|h) + \log_{2} P(h)  \nonumber \\
&= &\arg \min_{h \in H} - \log_{2} P(D|h) - \log_{2} P(h) 
\end{eqnarray}

Interesting fact from information theory:
\begin{quote}
The optimal (shortest expected coding length) code for an event with
probability $p$ is $- \log_{2} p$ bits.
\end{quote}

So interpret (1):
\bi
\item $- \log_{2} P(h)$ is length of $h$ under optimal code
\item $- \log_{2} P(D|h)$ is length of $D$ given $h$ under optimal code
\ei

$\rightarrow$ prefer the hypothesis that minimizes
\[ length(h) + length(misclassifications) \]

\slidehead{\normalsize Most Probable Classification of New Instances \red } \bk


So far we've sought the most probable {\em hypothesis} given the data $D$
(i.e., $h_{MAP}$)

\bigskip

Given new instance $x$, what is its most probable {\em classification}?
\bi
% true or false? \item $h_{MAP}(x)$ called the {\em Naive Bayes} classification
\item $h_{MAP}(x)$ is not the most probable classification!
\ei

\bigskip

Consider:
\bi
\item Three possible hypotheses: 
\bi \item[] $P(h_{1}|D)=.4, \  P(h_{2}|D)=.3, \  P(h_{3}|D)=.3$ \ei
\item Given new instance $x$, 
\bi \item[] $h_{1}(x)=+, \ h_{2}(x)=-, \ h_{3}(x)=-$ \ei
\item What's most probable classification of $x$?
\ei


\slidehead{\large Bayes Optimal Classifier \red } \bk

{\bf Bayes optimal classification: }

\[ \arg \max_{v_{j} \in V} \sum_{h_{i} \in H} P(v_{j}|h_{i}) P(h_{i}|D)\]

Example:

\begin{eqnarray}
P(h_{1}|D)=.4, & P(-|h_{1})=0, & P(+|h_{1})=1 \nonumber \\
P(h_{2}|D)=.3, & P(-|h_{2})=1, & P(+|h_{2})=0 \nonumber \\
P(h_{3}|D)=.3, & P(-|h_{3})=1, & P(+|h_{3})=0 \nonumber 
\end{eqnarray}
therefore
\begin{eqnarray}
\sum_{h_{i} \in H} P(+|h_{i}) P(h_{i}|D) & = & .4 \nonumber \\
\sum_{h_{i} \in H} P(-|h_{i}) P(h_{i}|D) & = & .6 \nonumber
\end{eqnarray}
and
\begin{eqnarray}
\arg \max_{v_{j} \in V} \sum_{h_{i} \in H} P(v_{j}|h_{i}) P(h_{i}|D) & = & -
\nonumber 
\end{eqnarray}

\slidehead{\large Gibbs Classifier \red } \bk

Bayes optimal classifier provides best result, but can be expensive if many
hypotheses.

Gibbs algorithm:
\be
\item Choose one hypothesis at random, according to $P(h|D)$
\item Use this to classify new instance 
\ee

Surprising fact: Assume target concepts are drawn at random from $H$ 
according to priors on $H$.  Then:

\[ E[error_{Gibbs}] \leq 2 E[error_{Bayes Optimal}] \]


Suppose correct, uniform prior distribution over $H$, then 
\bi
\item Pick any hypothesis from VS, with uniform probability
\item Its expected error no worse than twice Bayes optimal
\ei



\slidehead{\large Naive Bayes Classifier \red } \bk

Along with decision trees, neural networks, nearest nbr, one of the most
practical learning methods.

\bigskip

When to use
\bi
\item Moderate or large training set available
\item Attributes that describe instances are conditionally independent given
classification 
\ei

Successful applications:
\bi
\item Diagnosis
\item Classifying text documents
\ei


\slidehead{\large Naive Bayes Classifier \red } \bk

Assume target function $f: X \ra V$, where each instance $x$ described by
attributes $\langle a_{1}, a_{2} \ldots a_{n} \rangle$.  

Most probable value of $f(x)$ is:
\begin{eqnarray}
v_{MAP} &= &\argmax_{v_{j} \in V} P(v_{j} | a_{1}, a_{2} \ldots a_{n})  \nonumber \\ 
v_{MAP} &= &\argmax_{v_{j} \in V} \frac{P(a_{1}, a_{2} \ldots a_{n}|v_{j})
P(v_{j})}{P(a_{1}, a_{2} \ldots a_{n})} \nonumber \\ 
&= &\argmax_{v_{j} \in V} P(a_{1}, a_{2} \ldots a_{n}|v_{j}) P(v_{j}) \nonumber
\end{eqnarray}

\bigskip

Naive Bayes assumption:
\[ P(a_{1}, a_{2} \ldots a_{n}|v_{j}) = \prod_{i} P(a_{i} | v_{j}) \]

which gives 

\[\mbox{\bf Naive Bayes classifier: } v_{NB} = \argmax_{v_{j} \in V} P(v_{j})
\prod_{i} P(a_{i} | v_{j}) \]

\slidehead{ Naive Bayes Algorithm \red } \bk

Naive\_Bayes\_Learn($examples$)
\bi 
\item[]
For each target value $v_j$
\bi
\item[]
$\hat{P}(v_j) \la$ estimate $P(v_j)$
\item[] For each attribute value $a_i$ of each attribute $a$
\bi \item[] $\hat{P}(a_i|v_j) \la$ estimate $P(a_i|v_j)$ \ei
\ei
\ei

\vspace*{.8in}
Classify\_New\_Instance($x$)
\[ v_{NB} = \argmax_{v_{j} \in V} \hat{P}(v_{j}) \prod_{a_i \in x} \hat{P}(a_{i} | v_{j}) \]

%\normalsize
\slidehead{ Naive Bayes: Example \red } \bk

Consider {\em PlayTennis} again, and new instance 

 \[\langle Outlk=sun, Temp=cool, Humid=high, Wind=strong \rangle \]

\bigskip

Want to compute:
\[ v_{NB} = \argmax_{v_{j} \in V} P(v_{j}) \prod_{i} P(a_{i} | v_{j}) \]

\bigskip

\[P(y)\ P(sun|y)\ P(cool|y)\ P(high|y)\ P(strong|y) = .005 \]
\[P(n)\ P(sun|n)\ P(cool|n)\ P(high|n)\ P(strong|n) = .021 \]

\bigskip

\[ \ra v_{NB} = n \]

\slidehead{ Naive Bayes: Subtleties \red } \bk


\be
\item Conditional independence assumption is often violated
\[ P(a_{1}, a_{2} \ldots a_{n}|v_{j}) = \prod_{i} P(a_{i} | v_{j}) \]

\bi
\item ...but it works surprisingly well anyway.  Note don't need estimated
posteriors $\hat{P}(v_j|x)$ to be correct; need only that \ei
\[\argmax_{v_{j} \in V} \hat{P}(v_{j}) \prod_{i} \hat{P}(a_{i} | v_{j}) =
\argmax_{v_{j} \in V}  P(v_{j}) P(a_{1} \ldots, a_n | v_{j}) \]

\bigskip

\bi
\item see [Domingos \& Pazzani, 1996] for analysis
\item Naive Bayes posteriors often unrealistically close to 1 or 0
\ei
\ee

\slidehead{ Naive Bayes: Subtleties \red } \bk


\be
\item[2.]
what if none of the training instances with target value $v_j$ have attribute
value $a_i$?  Then
\[ \hat{P}(a_i|v_j) = 0 \mbox{, and...}\]
\[ \hat{P}(v_{j}) \prod_{i} \hat{P}(a_{i} | v_{j}) = 0 \]
\ee

Typical solution is Bayesian estimate for $\hat{P}(a_{i} | v_{j})$
\[  \hat{P}(a_{i} | v_{j}) \la \frac{n_{c} + mp}{n + m} \]
where 
\bi
\item
$n$ is number of training examples for which $v=v_j$, 
\item $n_c$ number of examples for which $v=v_j$ and $a=a_i$
\item $p$ is prior estimate for $\hat{P}(a_{i} | v_{j})$
\item $m$ is weight given to prior (i.e. number of ``virtual'' examples)
\ei

\slidehead{Learning to Classify Text \red } \bk

Why?
\bi
\item Learn which news articles are of interest
\item Learn to classify web pages by topic
\ei

\bigskip

Naive Bayes is among most effective algorithms

\bigskip
What attributes shall we use to represent text documents??


\slidehead{Learning to Classify Text \red } \bk

Target concept $Interesting? : Document \ra \{+,-\}$

\be
\item Represent each document by vector of words
\bi
\item one attribute per word position in document
\ei
\item Learning: Use training examples to estimate
\bi
\item $P(+)$
\item $P(-)$
\item $P(doc|+)$
\item $P(doc|-)$
\ei
\ee
Naive Bayes conditional independence assumption

\[ P(doc|v_j) = \prod_{i=1}^{length(doc)} P(a_i=w_k | v_j) \]

where $P(a_i=w_k| v_j)$ is probability that word in position $i$ is $w_k$,
given $v_j$

\bigskip
one more assumption: $P(a_i=w_k|v_j) = P(a_m=w_k|v_j), \forall i,m$


\newpage
\pgm{Learn\_naive\_Bayes\_text}($Examples, V$)

\bi

\item[]\hspace*{-.18in}
{\em 1. collect all words and other tokens that occur in
$Examples$}

\item
$Vocabulary \la$ all distinct words and other tokens in $Examples$

\item[]\hspace*{-.18in}
{\em 2. calculate the required $P(v_{j})$ and $P(w_{k}|v_{j})$ probability
terms}

\item
For each target value $v_{j}$ in $V$ do
\bi
\item
$docs_{j} \la $ subset of $Examples$ for which the target value is $v_{j}$

\item
$P(v_{j}) \la \frac{|docs_{j}|}{|Examples|}$

\item
$Text_{j} \la $ a single document created by concatenating all members of $docs_{j}$

\item
$n \la$ total number of words in $Text_{j}$ (counting duplicate words multiple
times)

\item
for each word $w_{k}$ in $Vocabulary$
\bi
\item
$n_{k} \la$ number of times word $w_{k}$ occurs in $Text_{j}$

\item
$P(w_{k}|v_{j}) \la \frac{n_{k} + 1}{n + |Vocabulary|}$
\ei
\ei
\ei

\newpage

\pgm{Classify\_naive\_Bayes\_text}($Doc$)

\bi
\item
$positions \la$ all word positions in $Doc$ that contain tokens found in
$Vocabulary$

\item
Return $v_{NB}$, where
\[v_{NB} = \argmax_{v_{j} \in V} P(v_{j}) \prod_{i \in positions}P(a_{i}|v_{j}) \]
\ei

\slidehead{Twenty NewsGroups \red } \bk

Given 1000 training documents from each group

Learn to classify new documents according to which newsgroup it came from

\bigskip
\begin{center}
\begin{tabular}{cc}
comp.graphics & misc.forsale\\
comp.os.ms-windows.misc & rec.autos \\
comp.sys.ibm.pc.hardware & rec.motorcycles \\
comp.sys.mac.hardware & rec.sport.baseball \\
comp.windows.x & rec.sport.hockey \\
\ & \ \\
alt.atheism & sci.space \\
soc.religion.christian  & sci.crypt\\
talk.religion.misc & sci.electronics\\
talk.politics.mideast & sci.med \\
talk.politics.misc & \ \\
talk.politics.guns & \ \\
\end{tabular}
\end{center}

\bigskip


Naive Bayes: 89\% classification accuracy


\slidehead{Article from rec.sport.hockey \red } \bk

\begin{verbatim}
Path: cantaloupe.srv.cs.cmu.edu!das-news.harvard.edu!ogicse!uwm.edu
From: xxx@yyy.zzz.edu (John Doe)
Subject: Re: This year's biggest and worst (opinion)...
Date: 5 Apr 93 09:53:39 GMT

I can only comment on the Kings, but the most 
obvious candidate for pleasant surprise is Alex
Zhitnik. He came highly touted as a defensive 
defenseman, but he's clearly much more than that. 
Great skater and hard shot (though wish he were 
more accurate). In fact, he pretty much allowed 
the Kings to trade away that huge defensive 
liability Paul Coffey. Kelly Hrudey is only the 
biggest disappointment if you thought he was any 
good to begin with. But, at best, he's only a 
mediocre goaltender. A better choice would be 
Tomas Sandstrom, though not through any fault of 
his own, but because some thugs in Toronto decided 
\end{verbatim}


\slidehead{Learning Curve for 20 Newsgroups \red } \bk

\centerline{\hbox{\psfig{file=./bookps/bayes-text-results.ps,width=6in}}}

\centerline{Accuracy vs. Training set size (1/3 withheld for test)}

\slidehead{Bayesian Belief Networks \red } \bk

Interesting because:
\bi
\item Naive Bayes assumption of conditional independence too restrictive
\item But it's intractable without some such assumptions...
\item Bayesian Belief networks describe conditional independence among {\em
subsets} of variables
\item[$\ra$] allows combining prior knowledge about (in)dependencies among
variables with observed training data
\ei
\bigskip
(also called Bayes Nets)

\slidehead{Conditional Independence \red } \bk

\begin{quote}
{\bf Definition:} $X$ is {\em conditionally independent} of $Y$ given $Z$ if
the probability distribution governing $X$ is independent of the value of $Y$
given the value of $Z$; that is, if
\[  (\forall x_i,y_j,z_k) \ P(X = x_i | Y = y_j, Z = z_k) =   P(X = x_i | Z
= z_k) \]
more compactly, we write
\[  P(X | Y,Z) = P(X | Z) \]
\end{quote}

\vspace*{.3in}
Example: $Thunder$ is conditionally independent of $Rain$, given $Lightning$
\[  P(Thunder | Rain, Lightning) = P(Thunder | Lightning) \]

\bigskip

\bigskip

Naive Bayes uses cond. indep. to justify
\begin{eqnarray}
P(X,Y|Z) &= &P(X|Y,Z) P(Y|Z)  \nonumber \\
 &= &P(X|Z) P(Y|Z)  \nonumber
\end{eqnarray}

\slidehead{Bayesian Belief Network \red } \bk

\centerline{\hbox{\psfig{file=./bookps/bayesnet.ps,width=7in}}}

Network represents a set of conditional independence assertions:

\bi
\item Each node is asserted to be conditionally independent of its nondescendants, given its
immediate predecessors.
\item Directed acyclic graph
\ei

\slidehead{Bayesian Belief Network \red } \bk

\centerline{\hbox{\psfig{file=./bookps/bayesnet.ps,width=7in}}}

Represents joint probability distribution over all variables
\bi
\item e.g., $P(Storm, BusTourGroup, \ldots, ForestFire)$
\item in general, 
\[P(y_1, \ldots, y_n) = \prod_{i=1}^{n} P(y_i | Parents(Y_i)) \]
where $Parents(Y_i)$ denotes immediate predecessors of $Y_i$ in graph
\item so, joint distribution is fully defined by graph, plus the $P(y_i | Parents(Y_i))$
\ei


\slidehead{Inference in Bayesian Networks \red } \bk

How can one infer the (probabilities of) values of one or more network
variables, given observed values of others?

\bi
\item
Bayes net contains all information needed for this inference
\item
If only one variable with unknown value, easy to infer it
\item
In general case, problem is NP hard
\ei

In practice,  can succeed in many cases
\bi
\item
Exact inference methods work well for some network structures
\item
Monte Carlo methods ``simulate'' the network randomly to calculate approximate
solutions
\ei

\slidehead{Learning of Bayesian Networks \red } \bk

Several variants of this learning task

\bi
\item 
Network structure might be {\em known} or {\em unknown}
\item 
Training examples might provide values of {\em all} network variables, or just
{\em some}
\ei

If structure known and observe all variables
\bi \item Then it's easy as training a Naive Bayes classifier \ei


\slidehead{Learning Bayes Nets \red } \bk

Suppose structure known, variables partially observable

\bigskip

e.g., observe {\em ForestFire, Storm, BusTourGroup, Thunder}, but not {\em
Lightning, Campfire}...

\bi
\item Similar to training neural network with hidden units
\item In fact, can learn network conditional probability tables using gradient
ascent! 
\item Converge to network $h$ that (locally) maximizes $P(D|h)$
\ei


\slidehead{Gradient Ascent for Bayes Nets \red } \bk

Let $w_{ijk}$ denote one entry in the conditional probability table for
variable $Y_i$ in the network
\[ w_{ijk} = P(Y_i=y_{ij} | Parents(Y_i) = \mbox{the list $u_{ik}$ of values)} \]
e.g., if $Y_i = Campfire$, then $u_{ik}$ might be $\langle Storm=T, BusTourGroup=F \rangle$
 
\bigskip

Perform gradient ascent by repeatedly
\be
\item update all $w_{ijk}$ using training data $D$
\[w_{ijk} \la w_{ijk} + \eta \sum_{d \in D} \frac{P_h(y_{ij}, u_{ik} |
d)}{w_{ijk}} \]
\item then, renormalize the $w_{ijk}$ to assure
\bi
\item $\sum_{j} w_{ijk} = 1$
\item $0 \leq w_{ijk} \leq 1$
\ei
\ee

\slidehead{More on Learning Bayes Nets \red } \bk

EM algorithm can also be used. Repeatedly:
\be
\item Calculate probabilities of unobserved variables, assuming $h$
\item Calculate new $w_{ijk}$ to maximize $E[\ln P(D|h)]$ where $D$ now includes
both observed and (calculated probabilities of) unobserved variables
\ee

\bigskip

\bigskip

When structure unknown...
\bi
\item Algorithms use greedy search to add/substract edges and nodes
\item Active research topic
\ei


\slidehead{Summary: Bayesian Belief Networks \red } \bk

\bi
\item Combine prior knowledge with observed data
\item Impact of prior knowledge (when correct!) is to lower the sample complexity
\item Active research area
\bi
\item Extend from boolean to real-valued variables
\item Parameterized distributions instead of tables
\item Extend to first-order instead of propositional systems
\item More effective inference methods
\item ...
\ei
\ei


\slidehead{Expectation Maximization (EM) \red } \bk

When to use:
\bi
\item Data is only partially observable
\item Unsupervised clustering (target value unobservable)
\item Supervised learning (some instance attributes unobservable)
\ei

\bigskip

Some uses:
\bi
\item Train Bayesian Belief Networks
\item Unsupervised clustering (AUTOCLASS)
\item Learning Hidden Markov Models
\ei




\slidehead{Generating Data from Mixture of $k$ Gaussians \red } \bk

\centerline{\hbox{\psfig{file=./bookps/two-gaussians.eps,width=6.5in}}}

\bigskip
Each instance $x$ generated by
\be
\item Choosing one of the $k$ Gaussians with uniform probability
\item Generating an instance at random according to that Gaussian
\ee

\slidehead{EM for Estimating $k$ Means \red } \bk

Given:
\bi
\item Instances from $X$ generated by mixture of $k$ Gaussian distributions
\item Unknown means $\langle \mu_1, \ldots, \mu_k \rangle$ of the $k$
Gaussians
\item Don't know which instance $x_i$ was generated by which Gaussian
\ei

Determine:
\bi
\item Maximum likelihood estimates of  $\langle \mu_1, \ldots, \mu_k \rangle$
\ei

\vspace*{.3in}

Think of full description of each instance as $y_i = \langle x_i, z_{i1}, z_{i2}
\rangle$, where
\bi
\item $z_{ij}$ is 1 if $x_i$ generated by $j$th Gaussian
\item $x_i$ observable
\item $z_{ij}$ unobservable
\ei

\slidehead{EM for Estimating $k$ Means \red } \bk

EM Algorithm: Pick random initial $h = \langle \mu_1, \mu_2 \rangle$, then
iterate
\be
\item[E step:]
Calculate the expected value $E[z_{ij}]$ of each hidden variable $z_{ij}$,
assuming the current hypothesis $h = \langle \mu_1, \mu_2 \rangle$ holds.
\begin{eqnarray}
E[z_{ij}] & = & \frac{p(x=x_i | \mu = \mu_j)}{\sum_{n=1}^{2} p(x = x_i |
 \mu=\mu_n)} \nonumber \\
 & = & \frac{e^{-\frac{1}{2 \sigma^2} (x_i -
 \mu_j)^2}}{\sum_{n=1}^{2} e^{-\frac{1}{2 \sigma^2} (x_i - \mu_n)^2}} \nonumber
\end{eqnarray}

\item[M step:]
Calculate a new maximum likelihood hypothesis $h' = \langle \mu_1', \mu_2'
\rangle$, assuming the value taken on by each hidden variable $z_{ij}$ is 
its expected value $E[z_{ij}]$ calculated above.   Replace $h =
\langle \mu_1, \mu_2 \rangle$ by $h' = \langle \mu_1', \mu_2' \rangle$.
\[ \mu_j \la \frac{\sum_{i=1}^m E[z_{ij}] \ \  x_i}{\sum_{i=1}^m E[z_{ij}]} \]

\ee

\slidehead{EM Algorithm \red } \bk

Converges to local maximum likelihood $h$

and provides estimates of hidden variables $z_{ij}$


\bigskip
In fact, local maximum in $E[\ln P(Y|h)]$

\bi 

\item $Y$ is complete (observable plus unobservable variables) data 

\item Expected value is taken over possible values
of unobserved variables in $Y$ 
\ei

\slidehead{General  EM Problem \red } \bk

Given:
\bi
\item Observed data $X=\{x_1, \ldots, x_m\}$
\item Unobserved data $Z=\{z_1, \dots, z_m\}$
\item Parameterized probability distribution $P(Y|h)$, where
\bi 
\item $Y=\{y_1, \dots, y_m\}$ is the
full data $y_i = x_i \union z_i$
\item $h$ are the parameters
\ei
\ei

Determine:
\bi
\item $h$ that (locally) maximizes $E[\ln P(Y|h)]$
\ei
\vspace*{.2in}
Many uses:
\bi
\item Train Bayesian belief networks
\item Unsupervised clustering (e.g., $k$ means)
\item Hidden Markov Models
\ei

\slidehead{General EM Method \red } \bk

Define likelihood function $Q(h' | h)$ which calculates $Y = X \union Z$ using
observed $X$ and current parameters $h$ to estimate $Z$

\[ Q(h' | h) \la E[ \ln P(Y | h') | h, X ] \]

\bigskip
EM Algorithm:

\bi
\item[]
{\em Estimation (E) step:} Calculate $Q(h'|h)$ using the current hypothesis
$h$ and the observed data $X$ to estimate the probability distribution over
$Y$.
\[ Q(h' | h) \la E[ \ln P(Y | h') | h, X ] \]

\item[]
{\em Maximization (M) step:} Replace hypothesis $h$ by the hypothesis $h'$
that maximizes this $Q$ function.
\[ h \la \argmax_{h'}  Q(h' | h) \]
\ei

