\documentclass[pdf,bndg,slideColor,colorBG]{prosper}

\input{preamble}

\title{Bayesian Networks and Decision Graphs}
\subtitle{}
\author{}
\email{}
\institution{Chapter 6}
\slideCaption{Chapter 6}


\begin{document}
\maketitle



%####################################################################################
%# Learning probabilities from a database
%####################################################################################

\begin{slide}{Learning probabilities from a database}
\begin{minipage}{\linewidth}
\Blue{\ul{We have:}}
\begin{dinglist}{228}
\item A Bayesian network structure.
\item A database of cases over (some of) the variables.
\end{dinglist}
\Blue{\ul{We want:}}
\begin{dinglist}{228}
\item A Bayesian network model (with probabilities) representing the
  database.
\end{dinglist}




\hspace*{-0.5cm}\scalebox{0.6}{
      \psfrag{|Pr}[c]{\Var{Pr}}
      \psfrag{|Ut}[c]{\Var{Ut}}
      \psfrag{|Bt}[c]{\Var{Bt}}
      \psfrag{Table}[c]{      
	\begin{tabular}{c|ccc}
	  Cases & \Var{Pr} & \Var{Bt} & \Var{Ut} \\ \hline
	  $1$. & \St{?} & \St{pos} & \St{pos} \\
	  $2$. & \St{yes} & \St{neg} & \St{pos} \\
	  $3$. & \St{yes} & \St{pos} & \St{?} \\
	  $4$. & \St{yes} & \St{pos} & \St{neg} \\
	  $5$. & \St{?} & \St{neg} & \St{?} 
      \end{tabular}}
      \psfrag{P1}[c]{P(\Var{Bt}\given \Var{Pr})}
      \psfrag{P2}[c]{P(\Var{Pr})}
      \psfrag{P3}[c]{P(\Var{Ut}\given \Var{Pr})}
      \includegraphics[scale=0.8]{parameter-learning.eps}
}


\end{minipage}
\end{slide}



%####################################################################################
%# Complete data: Maximum likelihood estimation
%####################################################################################

\overlays{4}{
\begin{slide}{Complete data: Maximum likelihood estimation}
\begin{minipage}{\linewidth}
\fromSlide*{1}{
We have tossed a thumb tack $100$ times. It has landed pin up $80$
times, and we now look for the \Red{model} that best fits the observations/data:

\begin{figure}[hbpt]
  \psfrag{|T1}[c]{$T$}
  \psfrag{|T2}[c]{$T$}
  \psfrag{|T3}[c]{$T$}
  \psfrag{|P1}[c]{\Blue{$0.1$}}
  \psfrag{|P2}[c]{\Blue{$0.2$}}
  \psfrag{|P3}[c]{\Blue{$0.3$}}
  \psfrag{|M1}[c]{\Red{$M_{0.1}$}}
  \psfrag{|M2}[c]{\Red{$M_{0.2}$}}
  \psfrag{|M3}[c]{\Red{$M_{0.3}$}}
  \psfrag{|Model}[c]{\Red{Model}}
  \psfrag{|Structure}[c]{Structure}
  \psfrag{|P(pin up)=}[c]{\Blue{Probability, $P(\StM{pin up})=$}}
  \begin{center}
    \includegraphics[scale=0.8]{thumb-tack.eps}
  \end{center}
\end{figure}
\ \\
\ \\

%\fbox{
%So all our possible \Red{models} agree on the structure, but differ w.r.t.\
%the \Blue{probability parameters}!
%}

}
\onlySlide*{2}{
We can measure how well a model fits the data using:
\[
\begin{split}
P(\calD|M_{\Blue{\theta}}) &= P(\StM{pin up}, \StM{pin up}, \StM{pin
  down},\ldots, \StM{pin up}|M_{\Blue{\theta}}) \\
&=  P(\StM{pin up}|M_{\Blue{\theta}})P(\StM{pin up}|M_{\Blue{\theta}})P(\StM{pin
  down}|M_{\Blue{\theta}})\cdot \ldots\cdot P(\StM{pin up}|M_{\Blue{\theta}})
\end{split}
\]

\centerline{
\fbox{
This is also called the \Blue{likelihood} of $M_{\Blue{\theta}}$ given $\calD$.
}
}
%By assuming that the observations/cases are independent given the
%model we have:
%\[
%P(\calD|M_{\Blue{\theta}})=\prod_{i=1}^{100}P(d_i|M_{\Blue{\theta}})
%\]
}

\onlySlide*{3}{
We select the \Blue{parameter $\hat{\theta}$} that maximizes:
\[
\begin{split}
\Blue{\hat{\theta}}=&\arg\max
_{\Blue{\theta}}P(\calD|M_{\Blue{\theta}})\\
=&\arg\max
_{\Blue{\theta}}\prod_{i=1}^{100}P(d_i|M_{\Blue{\theta}})\\
=& \arg\max
_{\Blue{\theta}} \mu\cdot \Blue{\theta}^{80}(1-\Blue{\theta})^{20}.
\end{split}
\]}


\onlySlide*{4}{
By setting:
\[
\frac{d}{d\Blue{\theta}}\mu\cdot
\Blue{\theta}^{80}(1-\Blue{\theta})^{20}= 0 
\]
we get the \ul{maximum likelihood estimate}:
\[
\Blue{\hat{\theta}}= 0.8.
\]
}
\end{minipage}
\end{slide}
}



%####################################################################################
%# Complete data: Maximum likelihood estimation
%####################################################################################

\overlays{4}{
\begin{slide}{Complete data: maximum likelihood estimation}
\begin{minipage}{\linewidth}
In general, you get a maximum likelihood estimate as the fraction of
counts over the total number of counts.
\ \\

\psset{unit=0.3cm}
\newpsobject{showgrid}{psgrid}{subgriddiv=1,griddots=10,gridlabels=6pt}
\begin{center}
\begin{pspicture}(0,6)(25,14)

\pnode(1,14){p1}
\pnode(1,10){p2}

\Fnode{3}{12}{b}{$B$}
\Fnode{8}{12}{c}{$C$}
\Fnode{5.5}{9}{a}{$A$}

\pnode(10,14){p3}
\pnode(10,10){p4}

\pnode(4,7){p5}
\pnode(7,7){p6}

\arc{b}{a}
\arc{c}{a}
\arc{p1}{b}
\arc{b}{p2}
\arc{p3}{c}
\arc{c}{p4}
\arc{a}{p5}
\arc{a}{p6}

\psline[linestyle=dotted,linecolor=black](1,10.5)(1,13.5)
\psline[linestyle=dotted,linecolor=black](10,10.5)(10,13.5)
\psline[linestyle=dotted,linecolor=black](4.5,7)(6.5,7)

\rput[l](12,12){\Green{We want} $P(A=a\given B=b, C=c)$!}

%\showgrid
\end{pspicture}
\end{center}

To find the maximum likelihood estimate $\hat{P}(A=a\given B=b, C=c)$ we simply calculate:

\begin{equation*}
\begin{split}
\fromSlide*{1}{\hat{P}(A=a\given B=b,C=c)  }& 
\onlySlide*{1}{=\phantom{\frac{\hat{P}(A=a,B=b,C=c)}{\hat{P}(B=b,C=c)}=\frac{\left
  [\frac{N(A=a,B=b,C=c)}{N}\right ]}{\left [\frac{N(B=b,C=c)}{N}\right%
  ]}}}\fromSlide*{2}{=\frac{\hat{P}(A=a,B=b,C=c)}{\hat{P}(B=b,C=c)}}\onlySlide*{2}{\phantom{=\frac{\left%
  [\frac{N(A=a,B=b,C=c)}{N}\right ]}{\left [\frac{N(B=b,C=c)}{N}\right%
  ]}}}\fromSlide*{3}{=\frac{\left
  [\frac{N(A=a,B=b,C=c)}{N}\right ]}{\left [\frac{N(B=b,C=c)}{N}\right%
  ]}}\\
\fromSlide*{4}{
  &=\frac{N(A=a,B=b,C=c)}{N(B=b,C=c)}.}
\end{split}
\end{equation*}

\fromSlide*{4}{\centerline{\Blue{So we have a simple counting problem!}}}

\end{minipage}
\end{slide}
}


%####################################################################################
%# Complete data: maximum likelihood estimation
%####################################################################################

\begin{slide}{Complete data: maximum likelihood estimation}
\begin{minipage}{\linewidth}
Unfortunately, maximum likelihood estimation has a drawback:

\begin{table}[htbp]
\begin{center}
\begin{tabular}{cc|cccccccc}
& & \multicolumn{8}{c}{Last three letters} \\
& & \St{aaa} & \St{aab} & \St{aba} & \St{abb} & \St{baa} & \St{bba} &
 \St{bab} & \St{bbb} \\ \hline
\multirow{4}{10mm}{\begin{minipage}{10mm}\begin{center}First two letters\end{center}\end{minipage}} & \St{aa} & $2$ & $2$ & $2$ & $2$ & $5$ & $7$ & $5$ & $7$ \\
 & \St{ab} & $3$ & $4$ & $4$ & $4$ & $1$ & $2$ & $0$ & $2$ \\
 & \St{ba} & $0$ & $1$ & $0$ & $0$ & $3$ & $5$ & $3$ & $5$ \\
 & \St{bb} & $5$ & $6$ & $6$ & $6$ & $2$ & $2$ & $2$ & $2$ 
\end{tabular}
\end{center}
\end{table}

By using this table to estimate e.g.\ $P(T_1=b,T_2=a,T_3=T_4=T_5=a)$
we get:
\[
\hat{P}(T_1=b,T_2=a,T_3=T_4=T_5=a) = \frac{N(T_1=b,T_2=a,T_3=T_4=T_5=a)}{N}=0
\]


\begin{center}
\fbox{$ $ \Blue{This is not reliable!}}
\end{center}

\end{minipage}
\end{slide}




%####################################################################################
%# Complete data: Bayesian estimation
%####################################################################################

%% \begin{slide}{Complete data: Bayesian estimation}
%% \begin{minipage}{\linewidth}
%% The Bayesian approach:
%% \vspace*{-1cm}
%% \pstexfignocap[0.5]{three-tosses}

%% Using some frequency function $f(\theta)$ and with $P(\StM{pin up}\given \theta)$ as $\theta$,
%% we look for:
%% \[
%% \begin{split}
%% f(\theta\given \StM{pin up}) &= \frac{P(\StM{pin up}\given
%%   \theta)f(\theta)}{P(\StM{pin up})} \\
%% &= \frac{P(\StM{pin up}\given
%%   \theta)}{P(\StM{pin up})}=\frac{\theta}{P(\StM{pin up})} \hspace*{1cm}[\Blue{f(\theta)=1}] \\
%% &= 2\theta \hspace*{4cm}[\Blue{P(\StM{pin up})=\int_0^1\theta d\theta=1/2}] \\
%% \end{split}
%% \]
%% A single best estimate could then be the mean value:
%% \[
%% \int _0^1\theta (2\theta)d \theta = 2/3
%% \]

%% \end{minipage}
%% \end{slide}




%####################################################################################
%# Complete data: maximum likelihood estimation
%####################################################################################

\begin{slide}{Complete data: maximum likelihood estimation}
\begin{minipage}{\linewidth}
An even prior distribution corresponds to adding a \Blue{virtual
  count} of $1$:
\begin{table}[htbp]
\begin{center}
\begin{tabular}{cc|cccccccc}
& & \multicolumn{8}{c}{Last three letters} \\
& & \St{aaa} & \St{aab} & \St{aba} & \St{abb} & \St{baa} & \St{bba} &
 \St{bab} & \St{bbb} \\ \hline
\multirow{4}{10mm}{\begin{minipage}{10mm}\begin{center}First two letters\end{center}\end{minipage}} & \St{aa} & $2$ & $2$ & $2$ & $2$ & $5$ & $7$ & $5$ & $7$ \\
 & \St{ab} & $3$ & $4$ & $4$ & $4$ & $1$ & $2$ & $0$ & $2$ \\
 & \St{ba} & $0$ & $1$ & $0$ & $0$ & $3$ & $5$ & $3$ & $5$ \\
 & \St{bb} & $5$ & $6$ & $6$ & $6$ & $2$ & $2$ & $2$ & $2$ 
\end{tabular}
\end{center}
\end{table}
From this table we get:


\begin{table}[htbp]
\hspace*{-0.5cm}
\begin{tabular}{ccccc}

\begin{tabular}{cc|cc}
& & \multicolumn{2}{c}{$T_1$}\\
& & $a$ & $b$ \\ \hline
\multirow{2}{0.2cm}{$T_2$} & $a$ & $32$ & $17$ \\
& $b$ & $20$ & $31$
\end{tabular}

&
$\Rightarrow $
&
\begin{tabular}{cc|cc}
& & \multicolumn{2}{c}{$T_1$}\\
& & $a$ & $b$ \\ \hline
\multirow{2}{0.2cm}{$T_2$} & $a$ & $32+\Blue{1}$ & $17+\Blue{1}$ \\
& $b$ & $20+\Blue{1}$ & $31+\Blue{1}$
\end{tabular} 

&
$\Rightarrow $
&

\begin{tabular}{cc|cc}
& & \multicolumn{2}{c}{$T_1$}\\
& & $a$ & $b$ \\ \hline
\multirow{2}{0.2cm}{$T_2$} & $a$ & $\left(\frac{33}{54}\right )$ & $\left(\frac{18}{50}\right )$ \\
& $b$ & $\left(\frac{21}{54}\right )$ & $\left(\frac{32}{50}\right )$
\end{tabular}\\
\vspace*{0.25cm} & & & & \\
$N(T_1,T_2)$ & &$N'(T_1,T_2)$ & & $P(T_2\given T_1)$=$\frac{N'(T_1,T_2)}{N'(T_1)}$
\end{tabular}


\end{table}




\end{minipage}
\end{slide}



%####################################################################################
%# Incomplete data
%####################################################################################

\PDForPS{
\overlays{2}{
\begin{slide}{Incomplete data}
\begin{minipage}{\linewidth}

\fromSlide*{1}{
How do we handle cases with missing values:
\begin{dinglist}{228}
\item Faulty sensor readings.
\item Values have been intentionally removed.
\item Some variables may be unobservable.
\end{dinglist}
\centerline{
\fbox{Why don't we just throw away the cases with missing values?}}
\ \\


}
\fromSlide*{2}{
\begin{tabular}{ccc}
\scalebox{1}{
\begin{tabular}{cc|cc}
$A$ & $B$ & $A$ & $B$ \\ \hline
$a_1$ & $b_1$ & $a_2$ & $b_1$\\
$a_1$ & $b_1$ & $a_2$ & $b_1$\\
$a_1$ & $b_1$ & $a_2$ & $b_1$\\
$a_1$ & $b_1$ & $a_2$ & $b_1$\\
$a_1$ & $b_1$ & $a_2$ & $b_1$\\
$a_1$ & $b_1$ & $a_2$ & $?$\\
$a_1$ & $b_1$ & $a_2$ & $?$\\
$a_1$ & $b_1$ & $a_2$ & $?$\\
$a_1$ & $b_1$ & $a_2$ & $?$\\
$a_1$ & $b_1$ & $a_2$ & $?$
\end{tabular}
}
& 
\scalebox{2}{
$\Rightarrow$
}
& 
\begin{minipage}{0.5\linewidth}
Using the entire database:
\[
\hat{P}(a_1) = \frac{N(a_1)}{N(a_1)+N(a_2)} = \frac{10}{10+10} = 0.5.
\]

Having removed the cases with missing values:
\[
\hat{P}'(a_1) = \frac{N'(a_1)}{N'(a_1)+N'(a_2)} = \frac{10}{10+5} = 2/3.
\]


\end{minipage}

\end{tabular}
}

\end{minipage}
\end{slide}}
}
{
\begin{slide}{Incomplete data}
\begin{minipage}{\linewidth}

How do we handle cases with missing values:
\begin{dinglist}{228}
\item Faulty sensor readings.
\item Values have been intentionally removed.
\item Some variables may be unobservable.
\end{dinglist}
\centerline{
\fbox{Why don't we just throw away the cases with missing values?}}
\ \\

\begin{tabular}{ccc}
\scalebox{1}{
\begin{tabular}{cc|cc}
$A$ & $B$ & $A$ & $B$ \\ \hline
$a_1$ & $b_1$ & $a_2$ & $b_1$\\
$a_1$ & $b_1$ & $a_2$ & $b_1$\\
$a_1$ & $b_1$ & $a_2$ & $b_1$\\
$a_1$ & $b_1$ & $a_2$ & $b_1$\\
$a_1$ & $b_1$ & $a_2$ & $b_1$\\
$a_1$ & $b_1$ & $a_2$ & $?$\\
$a_1$ & $b_1$ & $a_2$ & $?$\\
$a_1$ & $b_1$ & $a_2$ & $?$\\
$a_1$ & $b_1$ & $a_2$ & $?$\\
$a_1$ & $b_1$ & $a_2$ & $?$
\end{tabular}
}
& 
\scalebox{2}{
$\Rightarrow$
}
& 
\begin{minipage}{0.5\linewidth}
Using the entire database:
\[
\hat{P}(a_1) = \frac{N(a_1)}{N(a_1)+N(a_2)} = \frac{10}{10+10} = 0.5.
\]

Having removed the cases with missing values:
\[
\hat{P}'(a_1) = \frac{N'(a_1)}{N'(a_1)+N'(a_2)} = \frac{10}{10+5} = 2/3.
\]


\end{minipage}

\end{tabular}


\end{minipage}
\end{slide}
}

%####################################################################################
%# How is the data missing?
%####################################################################################

\begin{slide}{How is the data missing?}
\begin{minipage}{\linewidth}
We need to take into account \Blue{how} the data is missing:
\begin{description}
\item[\Red{Missing completely at random}] The probability that a value is missing is independent of both the
  observed and unobserved values.
\item[\Red{Missing at random}] The probability that a value is missing depends only on the
  observed values.
\item[\Red{Non-ignorable}] Neither MAR nor MCAR. 
\end{description}
\ \\

\hrule
\ \\

What is the type of missingness:
\begin{dinglist}{228}
\item In an exit poll, where an extreme right-wing party is running for
parlament?
\item In a database containing the results of two tests, where the second test has
  only performed (as a ``backup test'') when the result of the first test
  was negative?
\item In a monitoring system that is not completely stable and where
  some sensor values are not stored properly? 
\end{dinglist}

\end{minipage}
\end{slide}


%####################################################################################
%# The EM algorithm
%####################################################################################

\overlays{5}{
\begin{slide}{The EM algorithm}
\begin{minipage}{\linewidth}
\fromSlide*{1}{
  \begin{tabular}{cc}
\begin{minipage}{0.5\linewidth}
      \psfrag{|Pr}[c]{\Var{Pr}}
      \psfrag{|Ut}[c]{\Var{Ut}}
      \psfrag{|Bt}[c]{\Var{Bt}}
      \includegraphics[scale=0.8]{insemination.eps}
\end{minipage}
    &
\begin{minipage}{0.5\linewidth}
    \begin{tabular}{c|ccc}
      Cases & \Var{Pr} & \Var{Bt} & \Var{Ut} \\ \hline
      $1$. & \St{?} & \St{pos} & \St{pos} \\
      $2$. & \St{yes} & \St{neg} & \St{pos} \\
      $3$. & \St{yes} & \St{pos} & \St{?} \\
      $4$. & \St{yes} & \St{pos} & \St{neg} \\
      $5$. & \St{?} & \St{neg} & \St{?} 
    \end{tabular}
\end{minipage}
\end{tabular}
\ \\
}
\onlySlide*{1}{

\centerline{
\fbox{Estimate the required probability distributions for the network}
}
}

\onlySlide*{2}{
If the database was complete we would estimate the required
probabilities, $P(\VarM{Pr})$,  $P(\VarM{Ut}\given \VarM{Pr})$ and
$P(\VarM{Bt}\given \VarM{Pr})$ as:
\[
P(\VarM{Pr}=\StM{yes})=\frac{N(\VarM{Pr}=\StM{yes})}{N}
\]

\[
P(\VarM{Ut}=\StM{yes}\given
\VarM{Pr}=\StM{yes})=\frac{N(\VarM{Ut}=\StM{yes},\VarM{Pr}=\StM{yes})}{N(\VarM{Pr}=\StM{yes})} 
\]

\[
P(\VarM{Bt}=\StM{yes}\given
\VarM{Pr}=\StM{no})=\frac{N(\VarM{Bt}=\StM{yes},\VarM{Pr}=\StM{no})}{N(\VarM{Pr}=\StM{no})} 
\]

\centerline{
\fbox{So estimating the probabilities is basically a counting problem!}
}

}
\onlySlide*{3}{

Estimate $P(\VarM{Pr})$ from the database above:
\ \\

Case $2$, $3$ and $4$ contributes with a value $1$ to
$N(\VarM{Pr}=\StM{yes})$, but what is the contribution from case $1$ and $5$?

\begin{dinglist}{228}
\item Case 1 contributes with $P(\VarM{Pr}=\StM{yes}|\VarM{Bt}=\StM{pos},\VarM{Ut}=\StM{pos})$.
\item Case 5 contributes with $P(\VarM{Pr}=\StM{yes}|\VarM{Bt}=\StM{neg})$.
\end{dinglist}

To find these probabilities we assume some initial distributions, $P_0(\cdot)$, have
been assigned to the network. \ \\

\centerline{
\fbox{We are basically calculating the expectation for
  $N(\VarM{Pr}=\StM{yes})$, denoted $\Exp [N(\VarM{Pr}=\StM{yes})]$ }
}


}

\onlySlide*{4}{
Using $P_0(\VarM{Pr})=(0.5,0.5)$, $P_0(\VarM{Bt}\given
\VarM{Pr}=\StM{yes})=(0.5,0.5)$ etc., as starting distributions we
get:
 
\[
\begin{split}
\Exp [N(\VarM{Pr}=\StM{yes})] & = P_0(\VarM{Pr}=\StM{yes}\given
\VarM{Bt}=\VarM{Ut}=\StM{pos}) + 1 + 1 + 1 + P_0(\VarM{Pr}=\StM{yes}\given
\VarM{Bt}=\StM{neg})\\ 
& = 0.5 + 1 + 1 + 1 + 0.5 = 4\\
\Exp [N(\VarM{Pr}=\StM{no})] & = P_0(\VarM{Pr}=\StM{no}\given
\VarM{Bt}=\VarM{Ut}=\StM{pos}) + 0 + 0 + 0 + P_0(\VarM{Pr}=\StM{no}\given
\VarM{Bt}=\StM{neg})\\ 
& = 0.5 + 0 + 0 + 0 + 0.5 = 1
\end{split}
\]
\vspace*{-0.5cm}
So we e.g.\ get:
\[
\hat{P}_1(\VarM{Pr}=\StM{yes}) = \frac{\Exp [N(\VarM{Pr}=\StM{yes})]}{N} = \frac{4}{5}=0.8
\]

}


\onlySlide*{5}{
To estimate $\hat{P}_1(\VarM{Ut}\given \VarM{Pr}) =
\Exp[N(\VarM{Ut},\VarM{Pr})]/\Exp[N(\VarM{Pr})]$ we e.g.\ need: 
 
\[
\begin{split}
\Exp [N(\VarM{Ut}=\StM{p},\VarM{Pr}=\StM{y})]  =& P_0(\VarM{Ut}=\StM{p},\VarM{Pr}=\StM{y}\given
\VarM{Bt}=\VarM{Ut}=\StM{p}) + 1 + P_0(\VarM{Ut}=\StM{p},\VarM{Pr}=\StM{y}\given
\VarM{Bt}=\StM{p},\VarM{Pr}=\StM{y})\\
& + 0 + P_0(\VarM{Ut}=\StM{p},\VarM{Pr}=\StM{y}\given
\VarM{Bt}=\StM{n}) = 0.5 + 1 + 0.5 + 0 + 0.25 = 2.25\\
\Exp [N(\VarM{Pr}=\StM{yes})]  = &  P_0(\VarM{Pr}=\StM{yes}\given
\VarM{Bt}=\VarM{Ut}=\StM{pos}) + 1 + 1 + 1 + P_0(\VarM{Pr}=\StM{yes}\given
\VarM{Bt}=\StM{neg})\\
 =& 0.5 + 1 + 1 + 1 + 0.5 = 4
\end{split}
\]
\vspace*{-0.5cm}
So we e.g.\ get:
\[
\hat{P}_1(\VarM{Ut}=\StM{pos}\given \VarM{Pr}=\StM{yes}) = \frac{\Exp
  [N(\VarM{Ut}=\StM{p},\VarM{Pr}=\StM{y})]}{\Exp
  [N(\VarM{Pr}=\StM{yes})]} = \frac{2.25}{4} = 0.5625
\]

}




\end{minipage}
\end{slide}}



\PDForPS{
\overlays{5}{
\begin{slide}{The EM algorithm}

\onlySlide*{1}
{
\hspace*{-0.75cm}
\vspace*{-0cm}
\begin{minipage}{\linewidth}

  \psfrag{u}[c]{Until convergence}
  \psfrag{1}[c]{\Blue{E-step $1$}}
  \psfrag{2}[c]{\Red{M-step $2$}}
  \psfrag{3}[c]{\Blue{E-step $3$}}
  \psfrag{4}[c]{\Red{M-step $4$}}
  \psfrag{|Pr}[c]{\Var{Pr}}
  \psfrag{|Ut}[c]{\Var{Ut}}
  \psfrag{|Bt}[c]{\Var{Bt}}
  \psfrag{P1}[l]{
    \begin{minipage}{0.5\linewidth}
      $P_0(\Var{Pr})=(0.5,0.5)$\\
      $P_0(\Var{Ut}=\StM{pos}\given \Var{Pr})=(0.5,0.5)$\\
      $P_0(\Var{Bt}=\StM{pos}\given \Var{Pr})=(0.5,0.5)$
    \end{minipage}
  }    

  \includegraphics[scale=0.7]{insemination-em-0.eps}

\vspace*{5.25cm}

\end{minipage}
}
\onlySlide*{2}
{\vspace*{-0.5cm}
\hspace*{-0.75cm}
\begin{minipage}{\linewidth}

  \psfrag{u}[c]{Until convergence}
  \psfrag{1}[c]{\Blue{E-step $1$}}
  \psfrag{2}[c]{\Red{M-step $2$}}
  \psfrag{3}[c]{\Blue{E-step $3$}}
  \psfrag{4}[c]{\Red{M-step $4$}}
  \psfrag{|Pr}[c]{\Var{Pr}}
  \psfrag{|Ut}[c]{\Var{Ut}}
  \psfrag{|Bt}[c]{\Var{Bt}}
  \psfrag{P1}[l]{
    \begin{minipage}{0.5\linewidth}
      $P_0(\Var{Pr})=(0.5,0.5)$\\
      $P_0(\Var{Ut}=\StM{pos}\given \Var{Pr})=(0.5,0.5)$\\
      $P_0(\Var{Bt}=\StM{pos}\given \Var{Pr})=(0.5,0.5)$
    \end{minipage}
  }    
  \psfrag{E1}[l]{
    \begin{minipage}{0.6\linewidth}
      $\Exp_0[N(\Var{Pr})]=(4,1)$\\
      $\Exp_0[N(\Var{Ut}=\StM{pos},\Var{Pr})]=(2.25,$\\
      $\phantom{\Exp_0[N(\Var{Ut}=\StM{pos},\Var{Pr})]=(}0.5+0+0+0+0.25)$\\
      $\Exp_0[N(\Var{Bt}=\StM{pos},\Var{Pr})]=(0.5+0+1+1+0=2.5$\\
      $\phantom{\Exp_0[N(\Var{Bt}=\StM{pos},\Var{Pr})]=(},0.5+0+0+0+0=0.5)$
    \end{minipage}
  }    

      \includegraphics[scale=0.7]{insemination-em-1.eps}
\vspace*{5.25cm}
\end{minipage}
}
\onlySlide*{3}
{\vspace*{-0.5cm}
\hspace*{-0.75cm}
\begin{minipage}{\linewidth}

  \psfrag{u}[c]{Until convergence}
  \psfrag{1}[c]{\Blue{E-step $1$}}
  \psfrag{2}[c]{\Red{M-step $2$}}
  \psfrag{3}[c]{\Blue{E-step $3$}}
  \psfrag{4}[c]{\Red{M-step $4$}}
  \psfrag{|Pr}[c]{\Var{Pr}}
  \psfrag{|Ut}[c]{\Var{Ut}}
  \psfrag{|Bt}[c]{\Var{Bt}}
  \psfrag{P1}[l]{
    \begin{minipage}{0.5\linewidth}
      $P_0(\Var{Pr})=(0.5,0.5)$\\
      $P_0(\Var{Ut}=\StM{pos}\given \Var{Pr})=(0.5,0.5)$\\
      $P_0(\Var{Bt}=\StM{pos}\given \Var{Pr})=(0.5,0.5)$
    \end{minipage}
  }    
  \psfrag{P2}[l]{
    \begin{minipage}{0.5\linewidth}
      $P_1(\Var{Pr})=(\frac{4}{5},\frac{1}{5})$\\
      $P_1(\Var{Ut}=\StM{pos}\given \Var{Pr})=(\frac{2.25}{4},\frac{0.75}{1})$\\
      $P_1(\Var{Bt}=\StM{pos}\given \Var{Pr})=(\frac{2.5}{4},\frac{0.5}{1})$
    \end{minipage}
  }    
  \psfrag{E1}[l]{
    \begin{minipage}{0.6\linewidth}
      $\Exp_0[N(\Var{Pr})]=(4,1)$\\
      $\Exp_0[N(\Var{Ut}=\StM{pos},\Var{Pr})]=(2.25,$\\
      $\phantom{\Exp_0[N(\Var{Ut}=\StM{pos},\Var{Pr})]=(}0.5+0+0+0+0.25)$\\
      $\Exp_0[N(\Var{Bt}=\StM{pos},\Var{Pr})]=(0.5+0+1+1+0=2.5$\\
      $\phantom{\Exp_0[N(\Var{Bt}=\StM{pos},\Var{Pr})]=(},0.5+0+0+0+0=0.5)$
    \end{minipage}
  }    

      \includegraphics[scale=0.7]{insemination-em-2.eps}
\vspace*{3.5cm}
\end{minipage}
}

\onlySlide*{4}
{\vspace*{-0.5cm}
\hspace*{-0.75cm}
\begin{minipage}{\linewidth}

  \psfrag{u}[c]{Until convergence}
  \psfrag{1}[c]{\Blue{E-step $1$}}
  \psfrag{2}[c]{\Red{M-step $2$}}
  \psfrag{3}[c]{\Blue{E-step $3$}}
  \psfrag{4}[c]{\Red{M-step $4$}}
  \psfrag{|Pr}[c]{\Var{Pr}}
  \psfrag{|Ut}[c]{\Var{Ut}}
  \psfrag{|Bt}[c]{\Var{Bt}}
  \psfrag{P1}[l]{
    \begin{minipage}{0.5\linewidth}
      $P_0(\Var{Pr})=(0.5,0.5)$\\
      $P_0(\Var{Ut}=\StM{pos}\given \Var{Pr})=(0.5,0.5)$\\
      $P_0(\Var{Bt}=\StM{pos}\given \Var{Pr})=(0.5,0.5)$
    \end{minipage}
  }    
  \psfrag{P2}[l]{
    \begin{minipage}{0.5\linewidth}
      $P_1(\Var{Pr})=(\frac{4}{5},\frac{1}{5})$\\
      $P_1(\Var{Ut}=\StM{pos}\given \Var{Pr})=(\frac{2.25}{4},\frac{0.75}{1})$\\
      $P_1(\Var{Bt}=\StM{pos}\given \Var{Pr})=(\frac{2.5}{4},\frac{0.5}{1})$
    \end{minipage}
  }    
  \psfrag{E1}[l]{
    \begin{minipage}{0.6\linewidth}
      $\Exp_0[N(\Var{Pr})]=(4,1)$\\
      $\Exp_0[N(\Var{Ut}=\StM{pos},\Var{Pr})]=(2.25,$\\
      $\phantom{\Exp_0[N(\Var{Ut}=\StM{pos},\Var{Pr})]=(}0.5+0+0+0+0.25)$\\
      $\Exp_0[N(\Var{Bt}=\StM{pos},\Var{Pr})]=(0.5+0+1+1+0=2.5$\\
      $\phantom{\Exp_0[N(\Var{Bt}=\StM{pos},\Var{Pr})]=(},0.5+0+0+0+0=0.5)$
    \end{minipage}
  }    
  \psfrag{E2}[l]{
    \begin{minipage}{0.5\linewidth}
      $\Exp_1[N(\Var{Pr})]=(\hspace*{1cm},\hspace*{1cm})$\\
      $\Exp_1[N(\Var{Ut}=\StM{pos},\Var{Pr})]=(\hspace*{1cm},\hspace*{1cm})$\\
      $\Exp_1[N(\Var{Bt}=\StM{pos},\Var{Pr})]=(\hspace*{1cm},\hspace*{1cm})$
    \end{minipage}
  }    
      \includegraphics[scale=0.7]{insemination-em-3.eps}
\vspace*{2.2cm}

\end{minipage}

}
\onlySlide*{5}
{\vspace*{-0.5cm}
\hspace*{-0.75cm}
\begin{minipage}{\linewidth}

  \psfrag{u}[c]{Until convergence}
  \psfrag{1}[c]{\Blue{E-step $1$}}
  \psfrag{2}[c]{\Red{M-step $2$}}
  \psfrag{3}[c]{\Blue{E-step $3$}}
  \psfrag{4}[c]{\Red{M-step $4$}}
  \psfrag{|Pr}[c]{\Var{Pr}}
  \psfrag{|Ut}[c]{\Var{Ut}}
  \psfrag{|Bt}[c]{\Var{Bt}}
  \psfrag{P1}[l]{
    \begin{minipage}{0.5\linewidth}
      $P_0(\Var{Pr})=(0.5,0.5)$\\
      $P_0(\Var{Ut}=\StM{pos}\given \Var{Pr})=(0.5,0.5)$\\
      $P_0(\Var{Bt}=\StM{pos}\given \Var{Pr})=(0.5,0.5)$
    \end{minipage}
  }    
  \psfrag{P2}[l]{
    \begin{minipage}{0.5\linewidth}
      $P_1(\Var{Pr})=(\frac{4}{5},\frac{1}{5})$\\
      $P_1(\Var{Ut}=\StM{pos}\given \Var{Pr})=(\frac{2.25}{4},\frac{0.75}{1})$\\
      $P_1(\Var{Bt}=\StM{pos}\given \Var{Pr})=(\frac{2.5}{4},\frac{0.5}{1})$
    \end{minipage}
  }    
  \psfrag{P3}[l]{
    \begin{minipage}{0.5\linewidth}
      $P_2(\Var{Pr})=(\cdot,.\cdot)$\\
      $P_2(\Var{Ut}=\StM{pos}\given \Var{Pr})=(\cdot,.\cdot)$\\
      $P_2(\Var{Bt}=\StM{pos}\given \Var{Pr})=(\cdot,.\cdot)$
    \end{minipage}
  }    
  \psfrag{E1}[l]{
    \begin{minipage}{0.6\linewidth}
      $\Exp_0[N(\Var{Pr})]=(4,1)$\\
      $\Exp_0[N(\Var{Ut}=\StM{pos},\Var{Pr})]=(2.25,$\\
      $\phantom{\Exp_0[N(\Var{Ut}=\StM{pos},\Var{Pr})]=(}0.5+0+0+0+0.25)$\\
      $\Exp_0[N(\Var{Bt}=\StM{pos},\Var{Pr})]=(0.5+0+1+1+0=2.5$\\
      $\phantom{\Exp_0[N(\Var{Bt}=\StM{pos},\Var{Pr})]=(},0.5+0+0+0+0=0.5)$
    \end{minipage}
  }    
  \psfrag{E2}[l]{
    \begin{minipage}{0.5\linewidth}
      $\Exp_1[N(\Var{Pr})]=(\hspace*{1cm},\hspace*{1cm})$\\
      $\Exp_1[N(\Var{Ut}=\StM{pos},\Var{Pr})]=(\hspace*{1cm},\hspace*{1cm})$\\
      $\Exp_1[N(\Var{Bt}=\StM{pos},\Var{Pr})]=(\hspace*{1cm},\hspace*{1cm})$
    \end{minipage}
  }    
      \includegraphics[scale=0.7]{insemination-em-4.eps}

\end{minipage}

}

\fromSlide*{1}
{
\vspace*{-2.0cm}\hspace*{8cm}\scalebox{0.8}{
\begin{tabular}{c|ccc}
      Cases & \Var{Pr} & \Var{Bt} & \Var{Ut} \\ \hline
      $1$. & \St{?} & \St{pos} & \St{pos} \\
      $2$. & \St{yes} & \St{neg} & \St{pos} \\
      $3$. & \St{yes} & \St{pos} & \St{?} \\
      $4$. & \St{yes} & \St{pos} & \St{neg} \\
      $5$. & \St{?} & \St{neg} & \St{?} 
    \end{tabular}
}
}


\end{slide}
}
}
{
\begin{slide}{The EM algorithm: In general}
\vspace*{-0.5cm}
\hspace*{-0.75cm}
\begin{minipage}{\linewidth}

  \psfrag{u}[c]{Until convergence}
  \psfrag{1}[c]{\Blue{E-step $1$}}
  \psfrag{2}[c]{\Red{M-step $2$}}
  \psfrag{3}[c]{\Blue{E-step $3$}}
  \psfrag{4}[c]{\Red{M-step $4$}}
  \psfrag{|Pr}[c]{\Var{Pr}}
  \psfrag{|Ut}[c]{\Var{Ut}}
  \psfrag{|Bt}[c]{\Var{Bt}}
  \psfrag{P1}[l]{
    \begin{minipage}{0.5\linewidth}
      $P_0(\Var{Pr})=(0.5,0.5)$\\
      $P_0(\Var{Ut}=\StM{pos}\given \Var{Pr})=(0.5,0.5)$\\
      $P_0(\Var{Bt}=\StM{pos}\given \Var{Pr})=(0.5,0.5)$
    \end{minipage}
  }    
  \psfrag{P2}[l]{
    \begin{minipage}{0.5\linewidth}
      $P_1(\Var{Pr})=(\frac{4}{5},\frac{1}{5})$\\
      $P_1(\Var{Ut}=\StM{pos}\given \Var{Pr})=(\frac{2.25}{4},\frac{0.75}{1})$\\
      $P_1(\Var{Bt}=\StM{pos}\given \Var{Pr})=(\frac{2.5}{4},\frac{0.5}{1})$
    \end{minipage}
  }    
  \psfrag{P3}[l]{
    \begin{minipage}{0.5\linewidth}
      $P_2(\Var{Pr})=(\cdot,.\cdot)$\\
      $P_2(\Var{Ut}=\StM{pos}\given \Var{Pr})=(\cdot,.\cdot)$\\
      $P_2(\Var{Bt}=\StM{pos}\given \Var{Pr})=(\cdot,.\cdot)$
    \end{minipage}
  }    
  \psfrag{E1}[l]{
    \begin{minipage}{0.6\linewidth}
      $\Exp_0[N(\Var{Pr})]=(4,1)$\\
      $\Exp_0[N(\Var{Ut}=\StM{pos},\Var{Pr})]=(2.25,$\\
      $\phantom{\Exp_0[N(\Var{Ut}=\StM{pos},\Var{Pr})]=(}0.5+0+0+0+0.25)$\\
      $\Exp_0[N(\Var{Bt}=\StM{pos},\Var{Pr})]=(0.5+0+1+1+0=2.5$\\
      $\phantom{\Exp_0[N(\Var{Bt}=\StM{pos},\Var{Pr})]=(},0.5+0+0+0+0=0.5)$
    \end{minipage}
  }    
  \psfrag{E2}[l]{
    \begin{minipage}{0.5\linewidth}
      $\Exp_1[N(\Var{Pr})]=(\hspace*{1cm},\hspace*{1cm})$\\
      $\Exp_1[N(\Var{Ut}=\StM{pos},\Var{Pr})]=(\hspace*{1cm},\hspace*{1cm})$\\
      $\Exp_1[N(\Var{Bt}=\StM{pos},\Var{Pr})]=(\hspace*{1cm},\hspace*{1cm})$
    \end{minipage}
  }    
      \includegraphics[scale=0.7]{insemination-em.eps}

\end{minipage}

\vspace*{-2.0cm}\hspace*{8cm}\scalebox{0.8}{
\begin{tabular}{c|ccc}
      Cases & \Var{Pr} & \Var{Bt} & \Var{Ut} \\ \hline
      $1$. & \St{?} & \St{pos} & \St{pos} \\
      $2$. & \St{yes} & \St{neg} & \St{pos} \\
      $3$. & \St{yes} & \St{pos} & \St{?} \\
      $4$. & \St{yes} & \St{pos} & \St{neg} \\
      $5$. & \St{?} & \St{neg} & \St{?} 
    \end{tabular}
}
\end{slide}
}



\begin{slide}{The EM algorithm}
\begin{minipage}{\linewidth}

  \begin{tabular}{cc}
\begin{minipage}{0.5\linewidth}
      \psfrag{|Pr}[c]{\Var{Pr}}
      \psfrag{|Ut}[c]{\Var{Ut}}
      \psfrag{|Bt}[c]{\Var{Bt}}
      \includegraphics[scale=0.8]{insemination.eps}
\end{minipage}
    &
\begin{minipage}{0.5\linewidth}
    \begin{tabular}{c|ccc}
      Cases & \Var{Pr} & \Var{Bt} & \Var{Ut} \\ \hline
      $1$. & \St{?} & \St{pos} & \St{pos} \\
      $2$. & \St{yes} & \St{neg} & \St{pos} \\
      $3$. & \St{yes} & \St{pos} & \St{?} \\
      $4$. & \St{yes} & \St{pos} & \St{neg} \\
      $5$. & \St{?} & \St{neg} & \St{?} 
    \end{tabular}
\end{minipage}
\end{tabular}
\ \\

\begin{itemize}
\item[1.] Let
  $\bmtheta^0=\{\theta_{ijk}\}$ be some start estimates ($P(\Var{X_i}=j\given \pa{\Var{X_i}=k}=\theta_{ijk}$).
\item[4.] Repeat until convergence:
\begin{description}
\item[E-step:] For each variable $X_i$
  calculate the table of expected counts:
\[
\Exp_{\bmtheta^t}[N(X_i,\pa{X_i}\given\calD]=\sum_{\mbox{$\bmd\in
    \calD$}}P(X_i,\pa{X_i}\given\bmd,\bmtheta^t).
\] 
\item[M-step:] Use the expected counts as if they were actual
  counts:
\[
\hat{\theta}_{ijk} = \frac{\Exp_{\bmtheta^i}[N(X_i=k,\pa{X_i}=j\given\calD]}{\sum_{k=1}^{\sizeof{\sspace{X_i}}}\Exp_{\bmtheta^i}[N(X_i=k,\pa{X_i}=j\given\calD]}.
\]
\end{description}
\end{itemize}


\end{minipage}
\end{slide}



%####################################################################################
%# Adaptation
%####################################################################################

\PDForPS{
\overlays{2}{
\begin{slide}{Adaptation}
\onlySlide*{1}{
Adapt the tables to experience (cases):

\psset{unit=0.4cm}
\newpsobject{showgrid}{psgrid}{subgriddiv=1,griddots=10,gridlabels=6pt}
\begin{center}
\begin{pspicture}(0,0)(25,14)

\pnode(1,14){p1}
\pnode(1,10){p2}

\Fnode{3}{12}{b}{$B$}
\Fnode{8}{12}{c}{$C$}
\Fnode{5.5}{9}{a}{$A$}

\pnode(10,14){p3}
\pnode(10,10){p4}

\pnode(4,7){p5}
\pnode(7,7){p6}

\arc{b}{a}
\arc{c}{a}
\arc{p1}{b}
\arc{b}{p2}
\arc{p3}{c}
\arc{c}{p4}
\arc{a}{p5}
\arc{a}{p6}

\psline[linestyle=dotted,linecolor=black](1,10.5)(1,13.5)
\psline[linestyle=dotted,linecolor=black](10,10.5)(10,13.5)
\psline[linestyle=dotted,linecolor=black](4.5,7)(6.5,7)

\rput[l](12,12){Social env. (or expert) $t_1$:
$P_1(\Var{A}|\Var{B},\Var{C})$}
\rput[l](12,9){Social env. (or expert) $t_k$:
$P_k(\Var{A}|\Var{B},\Var{C})$}

\psline[linestyle=dotted,linecolor=black](14,11.5)(14,9.5)


%\showgrid
\end{pspicture}
\end{center}
}
\onlySlide*{2}{
Adapt the tables to experience (cases):
\psset{unit=0.4cm}
\newpsobject{showgrid}{psgrid}{subgriddiv=1,griddots=10,gridlabels=6pt}
\begin{center}
\begin{pspicture}(0,0)(25,14)

\pnode(1,14){p1}
\pnode(1,10){p2}

\Fnode{3}{12}{b}{$B$}
\Fnode{8}{12}{c}{$C$}
\Fnode{5.5}{9}{a}{$A$}

\pnode(10,14){p3}
\pnode(10,10){p4}

\pnode(4,7){p5}
\pnode(7,7){p6}

\arc{b}{a}
\arc{c}{a}
\arc{p1}{b}
\arc{b}{p2}
\arc{p3}{c}
\arc{c}{p4}
\arc{a}{p5}
\arc{a}{p6}

\psline[linestyle=dotted,linecolor=black](1,10.5)(1,13.5)
\psline[linestyle=dotted,linecolor=black](10,10.5)(10,13.5)
\psline[linestyle=dotted,linecolor=black](4.5,7)(6.5,7)

\rput[l](12,12){Social env. (or expert) $t_1$:
$P_1(\Var{A}|\Var{B},\Var{C})$}
\rput[l](12,9){Social env. (or expert) $t_k$:
$P_k(\Var{A}|\Var{B},\Var{C})$}

\psline[linestyle=dotted,linecolor=black](14,11.5)(14,9.5)


%--------------------

\pnode(0,7){p1}
\pnode(0,3){p2}

\Fnode{2}{5}{b}{$B$}
\Fnode{9}{5}{c}{$C$}
\Fnode{5.5}{2}{a}{$A$}
\Fnode{5.5}{5}{t}{$T$}


\pnode(11,7){p3}
\pnode(11,3){p4}

\pnode(4,0){p5}
\pnode(7,0){p6}

\arc{b}{a}
\arc{c}{a}
\arc{p1}{b}
\arc{b}{p2}
\arc{p3}{c}
\arc{c}{p4}
\arc{a}{p5}
\arc{a}{p6}
\arc{t}{a}

\psline[linestyle=dotted,linecolor=black](0,3.5)(0,6.5)
\psline[linestyle=dotted,linecolor=black](11,3.5)(11,6.5)
\psline[linestyle=dotted,linecolor=black](4.5,0)(6.5,0)

\rput[l](12,5){Variable $\Var{T}$: $\St{t_1}, \ldots ,\St{t_k}$}
\rput[l](12,4){$P(\Var{T})$ reflects the credibility of $t_1,\ldots ,
t_k$}
\rput[l](12,3){$P(\Var{A}|\Var{B},\Var{C},\Var{T}=\St{t_i})=P_i(\Var{A}|\Var{B},\Var{C})$}

%\showgrid
\end{pspicture}
\end{center}
Any case $\St{e}$ will yield a $P(\Var{T}|\St{e})$: \newline
\hspace*{0.5cm}This is used as
prior for the next case.



}
\end{slide}
}
}
{
\begin{slide}{Adaptation}
Adapt the tables to experience (cases):
\psset{unit=0.4cm}
\newpsobject{showgrid}{psgrid}{subgriddiv=1,griddots=10,gridlabels=6pt}
\begin{center}
\begin{pspicture}(0,0)(25,14)

\pnode(1,14){p1}
\pnode(1,10){p2}

\Fnode{3}{12}{b}{$B$}
\Fnode{8}{12}{c}{$C$}
\Fnode{5.5}{9}{a}{$A$}

\pnode(10,14){p3}
\pnode(10,10){p4}

\pnode(4,7){p5}
\pnode(7,7){p6}

\arc{b}{a}
\arc{c}{a}
\arc{p1}{b}
\arc{b}{p2}
\arc{p3}{c}
\arc{c}{p4}
\arc{a}{p5}
\arc{a}{p6}

\psline[linestyle=dotted,linecolor=black](1,10.5)(1,13.5)
\psline[linestyle=dotted,linecolor=black](10,10.5)(10,13.5)
\psline[linestyle=dotted,linecolor=black](4.5,7)(6.5,7)

\rput[l](12,12){Social env. (or expert) $t_1$:
$P_1(\Var{A}|\Var{B},\Var{C})$}
\rput[l](12,9){Social env. (or expert) $t_k$:
$P_k(\Var{A}|\Var{B},\Var{C})$}

\psline[linestyle=dotted,linecolor=black](14,11.5)(14,9.5)


%--------------------

\pnode(0,7){p1}
\pnode(0,3){p2}

\Fnode{2}{5}{b}{$B$}
\Fnode{9}{5}{c}{$C$}
\Fnode{5.5}{2}{a}{$A$}
\Fnode{5.5}{5}{t}{$T$}


\pnode(11,7){p3}
\pnode(11,3){p4}

\pnode(4,0){p5}
\pnode(7,0){p6}

\arc{b}{a}
\arc{c}{a}
\arc{p1}{b}
\arc{b}{p2}
\arc{p3}{c}
\arc{c}{p4}
\arc{a}{p5}
\arc{a}{p6}
\arc{t}{a}

\psline[linestyle=dotted,linecolor=black](0,3.5)(0,6.5)
\psline[linestyle=dotted,linecolor=black](11,3.5)(11,6.5)
\psline[linestyle=dotted,linecolor=black](4.5,0)(6.5,0)

\rput[l](12,5){Variable $\Var{T}$: $\St{t_1}, \ldots ,\St{t_k}$}
\rput[l](12,4){$P(\Var{T})$ reflects the credibility of $t_1,\ldots ,
t_k$}
\rput[l](12,3){$P(\Var{A}|\Var{B},\Var{C},\Var{T}=\St{t_i})=P_i(\Var{A}|\Var{B},\Var{C})$}

%\showgrid
\end{pspicture}
\end{center}
Any case $\St{e}$ will yield a $P(\Var{T}|\St{e})$: \newline
\hspace*{0.5cm}This is used as
prior for the next case.

\end{slide}
}


%####################################################################################
%# Fractional updating
%####################################################################################

\PDForPS{
\overlays{6}{
\begin{slide}{Fractional updating}
\fromSlide*{1}{
\psset{unit=0.4cm}
\newpsobject{showgrid}{psgrid}{subgriddiv=1,griddots=10,gridlabels=6pt}
\begin{center}
\begin{pspicture}(0,7)(25,14)

\pnode(1,14){p1}
\pnode(1,10){p2}

\Fnode{3}{12}{b}{$B$}
\Fnode{8}{12}{c}{$C$}
\Fnode{5.5}{9}{a}{$A$}

\pnode(10,14){p3}
\pnode(10,10){p4}

\pnode(4,7){p5}
\pnode(7,7){p6}

\arc{b}{a}
\arc{c}{a}
\arc{p1}{b}
\arc{b}{p2}
\arc{p3}{c}
\arc{c}{p4}
\arc{a}{p5}
\arc{a}{p6}

\psline[linestyle=dotted,linecolor=black](1,10.5)(1,13.5)
\psline[linestyle=dotted,linecolor=black](10,10.5)(10,13.5)
\psline[linestyle=dotted,linecolor=black](4.5,7)(6.5,7)

\rput[l](12,10){I am uncertain about $P(\Var{A}|\Var{B},\Var{C})$.}


%\showgrid
\end{pspicture}
\end{center}
\ul{\Green{Idea:}} I can represent my uncertainty by assuming that $P(\Var{A}|\St{b_i},\St{c_j})$ are frequencies from
a \newline 
\phantom{\ul{\Green{Idea:}}} virtual sample of $n$ cases. \newline\newline
\hspace*{0.75cm}$\blacktriangleright$The larger I put $n$, the more certain
I am, i.e.,$P(\Var{A}|\St{b_i},\St{c_j})=\left(\frac{n_1}{n},\frac{n_2}{n},\ldots,
\frac{n_m}{n}\right )$.
}
\onlySlide*{2}{
\ \\
\ \\

I update $P(\Var{A}|\St{b_i},\St{c_j})$ when a new case arrives:
\ \\
\ \\

$a$) \ul{\Purple{New case:}} $\Var{B}=\St{b_i}, \Var{C}=\St{c_j},
\Var{A}=\St{a_1}, \ldots $:
\[
P^*(\Var{A}|\St{b_i},\St{c_j}) = \left(\frac{n_1+1}{n+1},\frac{n_2}{n+1},\ldots,
\frac{n_m}{n+1}\right )
\] 

}
\onlySlide*{3}{
\ \\
\ \\

I update $P(\Var{A}|\St{b_i},\St{c_j})$ when a new case arrives:
\ \\
\ \\

$b$) \ul{\Purple{New case:}} $\Var{B}=\St{b_i}, \Var{C}=\St{c_j}, \ldots.$ and 
$P(\Var{A}|\St{case})=(x_1,\ldots, x_m)$:
\[
P^*(\Var{A}|\St{b_i},\St{c_j}) = \left(\frac{n_1+x_1}{n+1},\frac{n_2+x_2}{n+1},\ldots,
\frac{n_m+x_m}{n+1}\right )
\] 

}
\onlySlide*{4}{
\ \\
\ \\

I update $P(\Var{A}|\St{b_i},\St{c_j})$ when a new case arrives:
\ \\
\ \\

$c$) \ul{\Purple{New case:}} $\ldots, \Var{A}=\St{a_1}, \ldots.$ and 
$P(\St{b_i},\St{c_j}|\St{case})=x$:
\[
P^*(\Var{A}|\St{b_i},\St{c_j}) = \left(\frac{n_1+x}{n+x},\frac{n_2}{n+x},\ldots,
\frac{n_m}{n+x}\right )
\] 


}


\onlySlide*{5}{
\ \\


I update $P(\Var{A}|\St{b_i},\St{c_j})$ when a new case arrives:
\ \\
\ \\

$d$) \ul{\Purple{New (general) case:}} $\Red{\ldots}$ $\Rightarrow$
$P(\Var{A}|\St{case})=(x_1,\ldots , x_m)$ and 
$P(\St{b_i},\St{c_j}|\St{case})=x$:
\[
P^*(\Var{A}|\St{b_i},\St{c_j}) = \left(\frac{n_1+x\cdot x_1}{n+x},\frac{n_2+x\cdot x_2}{n+x},\ldots,
\frac{n_m+x\cdot x_m}{n+x}\right )
\] 


}


\onlySlide*{6}{
\ \\


I update $P(\Var{A}|\St{b_i},\St{c_j})$ when a new case arrives:
\ \\
\ \\

$e$) \ul{\Purple{New case:}} $\Var{B}=\St{b_i}, \Var{C}=\St{c_j}$ and this is all!!
\vspace*{-0.3cm}
\[
P^*(\Var{A}|\St{b_i},\St{c_j}) = \left(\frac{n_1+\left
(\frac{n_1}{n}\right )}{n+1},\frac{n_2+\left
(\frac{n_2}{n}\right )}{n+1},\ldots,
\frac{n_m+\left
(\frac{n_m}{n}\right )}{n+1}\right ) = \left ( \frac{n_1}{n},\ldots ,\frac{n_m}{n}\right )
\] 
Unjustified, we thereby confirm our belief in our present distribution.

}

\end{slide}}
}
{

\begin{slide}{Fractional updating I}

\psset{unit=0.4cm}
\newpsobject{showgrid}{psgrid}{subgriddiv=1,griddots=10,gridlabels=6pt}
\begin{center}
\begin{pspicture}(0,7)(25,14)

\pnode(1,14){p1}
\pnode(1,10){p2}

\Fnode{3}{12}{b}{$B$}
\Fnode{8}{12}{c}{$C$}
\Fnode{5.5}{9}{a}{$A$}

\pnode(10,14){p3}
\pnode(10,10){p4}

\pnode(4,7){p5}
\pnode(7,7){p6}

\arc{b}{a}
\arc{c}{a}
\arc{p1}{b}
\arc{b}{p2}
\arc{p3}{c}
\arc{c}{p4}
\arc{a}{p5}
\arc{a}{p6}

\psline[linestyle=dotted,linecolor=black](1,10.5)(1,13.5)
\psline[linestyle=dotted,linecolor=black](10,10.5)(10,13.5)
\psline[linestyle=dotted,linecolor=black](4.5,7)(6.5,7)

\rput[l](12,10){I am uncertain about $P(\Var{A}|\Var{B},\Var{C})$.}


%\showgrid
\end{pspicture}
\end{center}
\ul{\Green{Idea:}} I can represent my uncertainty by assuming that $P(\Var{A}|\St{b_i},\St{c_j})$ is frequencies from
a \newline 
\phantom{\ul{\Green{Idea:}}} virtual sample of $n$ cases. \newline\newline
\hspace*{0.75cm}$\blacktriangleright$The larger I put $n$, the more certain
I am, i.e.,$P(\Var{A}|\St{b_i},\St{c_j})=\left(\frac{n_1}{n},\frac{n_2}{n},\ldots,
\frac{n_m}{n}\right )$.
\ \\
\ \\

I update $P(\Var{A}|\St{b_i},\St{c_j})$ when a new case arrives:
\ \\
\ \\

$a$) \ul{\Purple{New case:}} $\Var{B}=\St{b_i}, \Var{C}=\St{c_j},
\Var{A}=\St{a_1}, \ldots $:
\[
P^*(\Var{A}|\St{b_i},\St{c_j}) = \left(\frac{n_1+1}{n+1},\frac{n_2}{n+1},\ldots,
\frac{n_m}{n+1}\right )
\] 
\end{slide}

\begin{slide}{Fractional updating II}

\psset{unit=0.4cm}
\newpsobject{showgrid}{psgrid}{subgriddiv=1,griddots=10,gridlabels=6pt}
\begin{center}
\begin{pspicture}(0,7)(25,14)

\pnode(1,14){p1}
\pnode(1,10){p2}

\Fnode{3}{12}{b}{$B$}
\Fnode{8}{12}{c}{$C$}
\Fnode{5.5}{9}{a}{$A$}

\pnode(10,14){p3}
\pnode(10,10){p4}

\pnode(4,7){p5}
\pnode(7,7){p6}

\arc{b}{a}
\arc{c}{a}
\arc{p1}{b}
\arc{b}{p2}
\arc{p3}{c}
\arc{c}{p4}
\arc{a}{p5}
\arc{a}{p6}

\psline[linestyle=dotted,linecolor=black](1,10.5)(1,13.5)
\psline[linestyle=dotted,linecolor=black](10,10.5)(10,13.5)
\psline[linestyle=dotted,linecolor=black](4.5,7)(6.5,7)

\rput[l](12,10){I am uncertain about $P(\Var{A}|\Var{B},\Var{C})$.}


%\showgrid
\end{pspicture}
\end{center}
\ul{\Green{Idea:}} I can represent my uncertainty by assuming that $P(\Var{A}|\St{b_i},\St{c_j})$ is frequencies from
a \newline 
\phantom{\ul{\Green{Idea:}}} virtual sample of $n$ cases. \newline\newline
\hspace*{0.75cm}$\blacktriangleright$The larger I put $n$, the more certain
I am, i.e.,$P(\Var{A}|\St{b_i},\St{c_j})=\left(\frac{n_1}{n},\frac{n_2}{n},\ldots,
\frac{n_m}{n}\right )$.
\ \\
\ \\

I update $P(\Var{A}|\St{b_i},\St{c_j})$ when a new case arrives:
\ \\
\ \\

$b$) \ul{\Purple{New case:}} $\Var{B}=\St{b_i}, \Var{C}=\St{c_j}, \ldots.$ and 
$P(\Var{A}|\St{case})=(x_1,\ldots, x_m)$:
\[
P^*(\Var{A}|\St{b_i},\St{c_j}) = \left(\frac{n_1+x_1}{n+1},\frac{n_2+x_2}{n+1},\ldots,
\frac{n_m+x_m}{n+1}\right )
\] 
\end{slide}

\begin{slide}{Fractional updating III}

\psset{unit=0.4cm}
\newpsobject{showgrid}{psgrid}{subgriddiv=1,griddots=10,gridlabels=6pt}
\begin{center}
\begin{pspicture}(0,7)(25,14)

\pnode(1,14){p1}
\pnode(1,10){p2}

\Fnode{3}{12}{b}{$B$}
\Fnode{8}{12}{c}{$C$}
\Fnode{5.5}{9}{a}{$A$}

\pnode(10,14){p3}
\pnode(10,10){p4}

\pnode(4,7){p5}
\pnode(7,7){p6}

\arc{b}{a}
\arc{c}{a}
\arc{p1}{b}
\arc{b}{p2}
\arc{p3}{c}
\arc{c}{p4}
\arc{a}{p5}
\arc{a}{p6}

\psline[linestyle=dotted,linecolor=black](1,10.5)(1,13.5)
\psline[linestyle=dotted,linecolor=black](10,10.5)(10,13.5)
\psline[linestyle=dotted,linecolor=black](4.5,7)(6.5,7)

\rput[l](12,10){I am uncertain about $P(\Var{A}|\Var{B},\Var{C})$.}


%\showgrid
\end{pspicture}
\end{center}
\ul{\Green{Idea:}} I can represent my uncertainty by assuming that $P(\Var{A}|\St{b_i},\St{c_j})$ is frequencies from
a \newline 
\phantom{\ul{\Green{Idea:}}} virtual sample of $n$ cases. \newline\newline
\hspace*{0.75cm}$\blacktriangleright$The larger I put $n$, the more certain
I am, i.e.,$P(\Var{A}|\St{b_i},\St{c_j})=\left(\frac{n_1}{n},\frac{n_2}{n},\ldots,
\frac{n_m}{n}\right )$.
\ \\
\ \\

I update $P(\Var{A}|\St{b_i},\St{c_j})$ when a new case arrives:
\ \\
\ \\

$c$) \ul{\Purple{New case:}} $\ldots, \Var{A}=\St{a_1}, \ldots.$ and 
$P(\St{b_i},\St{c_j}|\St{case})=x$:
\[
P^*(\Var{A}|\St{b_i},\St{c_j}) = \left(\frac{n_1+x}{n+x},\frac{n_2}{n+x},\ldots,
\frac{n_m}{n+x}\right )
\] 

\end{slide}


\begin{slide}{Fractional updating IV}

\psset{unit=0.4cm}
\newpsobject{showgrid}{psgrid}{subgriddiv=1,griddots=10,gridlabels=6pt}
\begin{center}
\begin{pspicture}(0,7)(25,14)

\pnode(1,14){p1}
\pnode(1,10){p2}

\Fnode{3}{12}{b}{$B$}
\Fnode{8}{12}{c}{$C$}
\Fnode{5.5}{9}{a}{$A$}

\pnode(10,14){p3}
\pnode(10,10){p4}

\pnode(4,7){p5}
\pnode(7,7){p6}

\arc{b}{a}
\arc{c}{a}
\arc{p1}{b}
\arc{b}{p2}
\arc{p3}{c}
\arc{c}{p4}
\arc{a}{p5}
\arc{a}{p6}

\psline[linestyle=dotted,linecolor=black](1,10.5)(1,13.5)
\psline[linestyle=dotted,linecolor=black](10,10.5)(10,13.5)
\psline[linestyle=dotted,linecolor=black](4.5,7)(6.5,7)

\rput[l](12,10){I am uncertain about $P(\Var{A}|\Var{B},\Var{C})$.}


%\showgrid
\end{pspicture}
\end{center}
\ul{\Green{Idea:}} I can represent my uncertainty by assuming that $P(\Var{A}|\St{b_i},\St{c_j})$ is frequencies from
a \newline 
\phantom{\ul{\Green{Idea:}}} virtual sample of $n$ cases. \newline\newline
\hspace*{0.75cm}$\blacktriangleright$The larger I put $n$, the more certain
I am, i.e.,$P(\Var{A}|\St{b_i},\St{c_j})=\left(\frac{n_1}{n},\frac{n_2}{n},\ldots,
\frac{n_m}{n}\right )$.
\ \\
\ \\

I update $P(\Var{A}|\St{b_i},\St{c_j})$ when a new case arrives:
\ \\
\ \\

$d$) \ul{\Purple{New (general) case:}} $\Red{\ldots}$ $\Rightarrow$
$P(\Var{A}|\St{case})=(x_1,\ldots , x_m)$ and 
$P(\St{b_i},\St{c_j}|\St{case})=x$:
\[
P^*(\Var{A}|\St{b_i},\St{c_j}) = \left(\frac{n_1+x\cdot x_1}{n+x},\frac{n_2+x\cdot x_2}{n+x},\ldots,
\frac{n_m+x\cdot x_m}{n+x}\right )
\] 
\end{slide}


\begin{slide}{Fractional updating V}

\psset{unit=0.4cm}
\newpsobject{showgrid}{psgrid}{subgriddiv=1,griddots=10,gridlabels=6pt}
\begin{center}
\begin{pspicture}(0,7)(25,14)

\pnode(1,14){p1}
\pnode(1,10){p2}

\Fnode{3}{12}{b}{$B$}
\Fnode{8}{12}{c}{$C$}
\Fnode{5.5}{9}{a}{$A$}

\pnode(10,14){p3}
\pnode(10,10){p4}

\pnode(4,7){p5}
\pnode(7,7){p6}

\arc{b}{a}
\arc{c}{a}
\arc{p1}{b}
\arc{b}{p2}
\arc{p3}{c}
\arc{c}{p4}
\arc{a}{p5}
\arc{a}{p6}

\psline[linestyle=dotted,linecolor=black](1,10.5)(1,13.5)
\psline[linestyle=dotted,linecolor=black](10,10.5)(10,13.5)
\psline[linestyle=dotted,linecolor=black](4.5,7)(6.5,7)

\rput[l](12,10){I am uncertain about $P(\Var{A}|\Var{B},\Var{C})$.}


%\showgrid
\end{pspicture}
\end{center}
\ul{\Green{Idea:}} I can represent my uncertainty by assuming that $P(\Var{A}|\St{b_i},\St{c_j})$ is frequencies from
a \newline 
\phantom{\ul{\Green{Idea:}}} virtual sample of $n$ cases. \newline\newline
\hspace*{0.75cm}$\blacktriangleright$The larger I put $n$, the more certain
I am, i.e.,$P(\Var{A}|\St{b_i},\St{c_j})=\left(\frac{n_1}{n},\frac{n_2}{n},\ldots,
\frac{n_m}{n}\right )$.
\ \\
\ \\

I update $P(\Var{A}|\St{b_i},\St{c_j})$ when a new case arrives:
\ \\
\ \\

$e$) \ul{\Purple{New case:}} $\Var{B}=\St{b_i}, \Var{C}=\St{c_j}$ and this is all!!
\vspace*{-0.3cm}
\[
P^*(\Var{A}|\St{b_i},\St{c_j}) = \left(\frac{n_1+\left
(\frac{n_1}{n}\right )}{n+1},\frac{n_2+\left
(\frac{n_2}{n}\right )}{n+1},\ldots,
\frac{n_m+\left
(\frac{n_m}{n}\right )}{n+1}\right ) = \left ( \frac{n_1}{n},\ldots ,\frac{n_m}{n}\right )
\] 
Unjustified, we thereby confirm our belief in our present distribution.


\end{slide}

}


%####################################################################################
%# Assumptions
%####################################################################################


\begin{slide}{Assumptions}

\ul{What is the situation?}
\begin{itemize}
\item We are uncertain about $P(\Var{A}|\Var{B},\Var{C})$.
\item We get a new case with $\Var{B}=\St{b_1}$ and $\Var{C}=\St{c_2}$. 
\end{itemize}
\ \\
\ \\

When updating we have that:
\begin{itemize}
\item $P(\Var{A}|\St{b_1},\St{c_2})$ is changed.
\item All other $P(\Var{A}|\St{b_i},\St{c_j})$ are unaffected.
\end{itemize}
\ \\
\ \\
\ \\

This involves the following two assumptions:\newline

\Green{Local independence:} The (second order) uncertainty on
$P(\Var{A}|\St{b_i},\St{c_j})$ is independent of the\newline
\phantom{Local independence: }(second order)
uncertainty on $P(\Var{A}|\St{b_i'},\St{c_j'})$.\newline
\Green{Global independence:} The (second order) uncertainty for the
various variables is \newline
\phantom{Global independence: }independent.



\end{slide}



%####################################################################################
%# Example: Spoofing
%####################################################################################


\begin{slide}{Example: Spoofing}

\ul{Estimate:} $P(\Var{\#\mbox{chosen}}|\Var{\#\mbox{in-hand}}=\St{2})=(0.2,0.6,0.2)$\newline
\phantom{\ul{Estimate:}} Virtual sample size $=20$ (corresponding to (4,12,4)). \newline\newline

\ul{New case:} $\#$\Var{chosen}$=\St{0}$\newline
\phantom{\ul{New case:}} $P(\Var{\#\mbox{chosen}}|\Var{\#\mbox{in-hand}}=\St{2})=(\frac{5}{21},\frac{12}{21},\frac{4}{21})$ \newline\newline


\ul{$23$ new cases:} $(7,8,8)$ \newline
\phantom{\ul{$23$ new cases:}} $P(\Var{\#\mbox{chosen}}|\Var{\#\mbox{in-hand}}=\St{2})=(\frac{12}{44},\frac{20}{44},\frac{12}{44})=(0.27,0.46,0.27)$ \newline\newline


\centerline{
\Purple{Apparently, she plays $(\frac{1}{3},\frac{1}{3},\frac{1}{3})$!!}}
\end{slide}



%####################################################################################
%# Do I have to take the (wrong) past with me?
%####################################################################################

\PDForPS{
\overlays{2}{
\begin{slide}{Do I have to take the (wrong) past with me?}
\fromSlide*{1}{
\ul{We have two situations:}
\begin{itemize}
\item The initial probabilities are wrong.
\item The probabilities change over time.
\end{itemize}
\ \\
\ \\

}
\onlySlide*{1}{
\ul{\Green{Fading:}} Multiply the old set of counts with a \Red{fading
factor $q<1$}.
\begin{equation}\nonumber
\left (\frac{n_1}{n},\frac{n_2}{n},\frac{n_3}{n}\right
)\bigoplus (x_1,x_2,x_3)
\end{equation}
 }


\fromSlide*{2}{
\ul{\Green{Fading:}} Multiply the old set of counts with a \Red{fading
factor $q<1$}.
\begin{equation}\nonumber
\left (\frac{n_1}{n},\frac{n_2}{n},\frac{n_3}{n}\right
)\bigoplus (x_1,x_2,x_3)\hspace{1cm}(\text{with }x=\sum _ix_i)
\end{equation}

\ul{\Green{Updating proceeds as follows:}}\newline
The counts:
\vspace*{-0.5cm}
\[
\begin{split}
&(n_1,n_2,n_3)\rightarrow (n_1\cdot \Red{q},n_2\cdot \Red{q},n_3\cdot
\Red{q}) \\  
&n\rightarrow n\cdot \Red{q}
\end{split}
\]
The probabilities:
\vspace*{-0.5cm}
\[P(\cdot)=\left ( \frac{n_1\cdot \Red{q}+x_1}{n\cdot
\Red{q}+x},\frac{n_2\cdot \Red{q}+x_2}{n\cdot \Red{q}+x},\frac{n_3\cdot \Red{q}+x_3}{n\cdot
\Red{q}+x} \right )\]
\ \\
\ \\
\ \\

\Purple{This technique is very efficient for implementing adaptive agents for
games with perfect recall.}


}



\end{slide}
}
}
{

\begin{slide}{Do I have to take the (wrong) past with me?}
\ul{We have two situations:}
\begin{itemize}
\item The initial probabilities are wrong.
\item The probabilities change over time.
\end{itemize}
\ \\
\ \\

\ul{\Green{Fading:}} Multiply the old set of counts with a \Red{fading
factor $q<1$}.
\begin{equation}\nonumber
\left (\frac{n_1}{n},\frac{n_2}{n},\frac{n_3}{n}\right
)\bigoplus (x_1,x_2,x_3)\hspace{1cm}(\text{with }x=\sum _ix_i)
\end{equation}

\ul{\Green{Updating proceeds as follows:}}\newline
The counts:
\vspace*{-0.5cm}
\[
\begin{split}
&(n_1,n_2,n_3)\rightarrow (n_1\cdot \Red{q},n_2\cdot \Red{q},n_3\cdot
\Red{q}) \\  
&n\rightarrow n\cdot \Red{q}
\end{split}
\]
The probabilities:
\vspace*{-0.5cm}
\[P(\cdot)=\left ( \frac{n_1\cdot \Red{q}+x_1}{n\cdot
\Red{q}+x},\frac{n_2\cdot \Red{q}+x_2}{n\cdot \Red{q}+x},\frac{n_3\cdot \Red{q}+x_3}{n\cdot
\Red{q}+x} \right )\]
\ \\
\ \\
\ \\

\Purple{This technique is very efficient for implementing adaptive agents for
games with perfect recall.}



\end{slide}


}


%####################################################################################
%# Interpreting the fading factor
%####################################################################################


\begin{slide}{Interpreting the fading factor}
With the fading factor we have:
\[
\begin{split}
&(n_1,n_2,n_3)\rightarrow (n_1\cdot \Red{q},n_2\cdot \Red{q},n_3\cdot
\Red{q}) \\  
&n\rightarrow n\cdot \Red{q}
\end{split}
\]
If all counts will be updated with the value $1$, then the past will
fade away exponentially and the limit (the \Red{effective sample
  size}) will be:
\[
\Red{n^*}=\frac{1}{1-q}
\]
If $n=\Red{n^*}$ and a new case arrives, we get:
\[
n:=\Red{n^*}\cdot q+1 =\frac{q}{1-q}+1 =  \frac{1}{1-q}= \Red{n^*}
\]
So instead of declaring a fading factor we can specify an
\Red{effective sample size}, and the fading factor is then:
\[
q=\frac{\Red{n^*}-1}{\Red{n^*}}
\]

\end{slide}

\end{document}





