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

\input{preamble}

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


\begin{document}
\maketitle



%####################################################################################
%# Learning the structure of a Bayesian network
%####################################################################################

\begin{slide}{Learning the structure of a Bayesian network}
\begin{minipage}{\linewidth}
\Blue{\ul{We have:}}
\begin{dinglist}{228}
\item A complete database of cases over a set of variables.
\end{dinglist}
\Blue{\ul{We want:}}
\begin{dinglist}{228}
\item A Bayesian network structure representing the independence
  properties in the  database.
\end{dinglist}



\begin{center}

\hspace*{0.75cm}\scalebox{0.7}{
      \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{yes} & \St{pos} & \St{pos} \\
	  $2$. & \St{yes} & \St{neg} & \St{pos} \\
	  $3$. & \St{yes} & \St{pos} & \St{neg} \\
	  $4$. & \St{yes} & \St{pos} & \St{neg} \\
	  $5$. & \St{no} & \St{neg} & \St{neg} 
      \end{tabular}}
      \includegraphics[scale=0.8]{structural-learning.eps}
}
\end{center}


\end{minipage}
\end{slide}





%####################################################################################
%# Bayesian networks from databases
%####################################################################################

\begin{slide}{Bayesian networks from databases I}
\begin{minipage}{\linewidth}
\Green{\ul{Example:} Transmission of symbol strings}, $P_{\Red{\calD}}(\calU)$:
\begin{center}
\begin{tabular}{cc|cccccccc}
& & \multicolumn{8}{c}{Last 3} \\
& &  $\St{aaa}$ & $\St{aab}$  & $\St{aba}$ & $\St{abb}$ & $\St{baa}$ &
$\St{bab}$ & $\St{bba}$ & $\St{bbb}$    \\ \hline
\multirow{4}{0cm}{\begin{rotate}{90}\hspace*{-0.3cm}First 2\end{rotate}} 
& $\St{aa}$ & $0.017$ & $0.021$ & $0.019$ & $0.019$ & $0.045$ & $0.068$ & $0.045$ & $0.068$  \\
& $\St{ab}$ & $0.033$ & $0.040$ & $0.037$ & $0.038$ & $0.011$ & $0.016$ & $0.010$ & $0.015$  \\
& $\St{ba}$ & $0.011$ & $0.014$ & $0.010$ & $0.010$ & $0.031$ & $0.046$ & $0.031$ & $0.045$  \\
& $\St{bb}$ & $0.050$ & $0.060$ & $0.057$ & $0.057$ & $0.016$ & $0.023$ & $0.015$ & $0.023$  \\
\end{tabular}
\end{center}
\ \\

Consider the model $\Green{N}$ as representing the database:
\begin{center}
  \psfrag{|T1}[c]{\Var{T1}}
  \psfrag{|T2}[c]{\Var{T2}}
  \psfrag{|T3}[c]{\Var{T3}}
  \psfrag{|T4}[c]{\Var{T4}}
  \psfrag{|T5}[c]{\Var{T5}}
   \includegraphics[scale=0.8]{m-simp.eps}
\end{center}

\begin{itemize}
\item Simpler than the database.
\item A representation of the database.
\end{itemize}
\Green{\ul{The chain rule}} (yields the joint probability which we
can compare to the actual database): 
\[
P_{\Green{N}}(\calU)=P(\Var{T_1},\Var{T_2},\Var{T_3},\Var{T_4},\Var{T_5}) = P(\Var{T_1})P(\Var{T_2}|\Var{T_1})P(\Var{T_3}|\Var{T_2})P(\Var{T_4}|\Var{T_3})P(\Var{T_5}|\Var{T_4}).
\]

\end{minipage}

\end{slide}


\begin{slide}{Bayesian networks from databases II}
\begin{minipage}{\linewidth}
\Green{\ul{Example:} Transmission of symbol strings}, $P_{\Red{\calD}}(\calU)$:
\begin{center}
\begin{tabular}{cc|cccccccc}
& & \multicolumn{8}{c}{Last 3} \\
& &  $\St{aaa}$ & $\St{aab}$  & $\St{aba}$ & $\St{abb}$ & $\St{baa}$ &
$\St{bab}$ & $\St{bba}$ & $\St{bbb}$    \\ \hline
\multirow{4}{0cm}{\begin{rotate}{90}\hspace*{-0.3cm}First 2\end{rotate}} 
& $\St{aa}$ & $0.017$ & $0.021$ & $0.019$ & $0.019$ & $0.045$ & $0.068$ & $0.045$ & $0.068$  \\
& $\St{ab}$ & $0.033$ & $0.040$ & $0.037$ & $0.038$ & $0.011$ & $0.016$ & $0.010$ & $0.015$  \\
& $\St{ba}$ & $0.011$ & $0.014$ & $0.010$ & $0.010$ & $0.031$ & $0.046$ & $0.031$ & $0.045$  \\
& $\St{bb}$ & $0.050$ & $0.060$ & $0.057$ & $0.057$ & $0.016$ & $0.023$ & $0.015$ & $0.023$  \\
\end{tabular}
\end{center}
\ \\

Consider the model $\Green{N}$ as representing the database:
\begin{center}
  \psfrag{|T1}[c]{\Var{T1}}
  \psfrag{|T2}[c]{\Var{T2}}
  \psfrag{|T3}[c]{\Var{T3}}
  \psfrag{|T4}[c]{\Var{T4}}
  \psfrag{|T5}[c]{\Var{T5}}
   \includegraphics[scale=0.8]{m-simp.eps}
\end{center}



\begin{center}
\begin{tabular}{cc|cccccccc}
& & \multicolumn{8}{c}{Last 3} \\
& &  $\St{aaa}$ & $\St{aab}$  & $\St{aba}$ & $\St{abb}$ & $\St{baa}$ &
$\St{bab}$ & $\St{bba}$ & $\St{bbb}$    \\ \hline
\multirow{4}{0cm}{\begin{rotate}{90}\hspace*{-0.3cm}First 2\end{rotate}} 
& $\St{aa}$ & $0.016$ & $0.023$ & $0.018$ & $0.021$ & $0.044$ & $0.067$ & $0.050$ & $0.061$  \\
& $\St{ab}$ & $0.030$ & $0.044$ & $0.033$ & $0.041$ & $0.011$ & $0.015$ & $0.012$ & $0.014$  \\
& $\St{ba}$ & $0.010$ & $0.016$ & $0.012$ & $0.014$ & $0.029$ & $0.045$ & $0.033$ & $0.041$  \\
& $\St{bb}$ & $0.044$ & $0.067$ & $0.059$ & $0.061$ & $0.016$ & $0.023$ & $0.017$ & $0.021$  \\
\end{tabular}
\end{center}
\centerline{
Are $P_{\Green{N}}(\calU)$ and $P_{\Red{\calD}}(\calU)$ sufficiently identical?}
\end{minipage}

\end{slide}



%####################################################################################
%# A way to look at it
%####################################################################################

\begin{slide}{A (na\"{\i}ve) way to look at it}
\begin{minipage}{\linewidth}

Some agent produces samples $\Red{\calD}$ of cases from a Bayesian network
$M$ over the universe $\calU$. 
\begin{dinglist}{228}
\item These cases are handed over to you, and
you should now reconstruct $M$ from the cases. 
\end{dinglist}
\ \\

\Blue{\ul{Assumptions:}}
\begin{dinglist}{228}
\item The sample is fair ($P_{\Red{\calD}}(\calU)$ reflects the distribution determined by $M$).
\item All links in $M$ are essential.
\end{dinglist}
\ \\

\Blue{\ul{A na\"{\i}ve procedure:}}
\begin{itemize}
\item For each Bayesian network structure $\Green{N}$:
\begin{itemize}
\item Calculate the distance between $P_{\Green{N}}(\calU)$ and $P_{\Red{\calD}}(\calU)$.
\end{itemize}
\item Return the network $\Green{N}$ that minimizes the distance, and
  where all links are essential.
\end{itemize}
\ \\
\ \\

\centerline{
\Red{But this is hardly feasible!}
}


\end{minipage}
\end{slide}




%####################################################################################
%# The space of network structures is huge!
%####################################################################################

\begin{slide}{The space of network structures is huge!}
\begin{minipage}{\linewidth}

The number of DAG structures (as a function of the number of nodes):
\begin{equation}\nonumber
f(n)=\sum_{i=1}^n(-1)^{i+1}\frac{n!}{(n-i)!i!}2^{i(n-i)}f(n-i).
\end{equation}  

\Blue{\ul{Some example calculations:}}

\begin{center}
\scalebox{0.95}{
\begin{tabular}{|cc|cc|}
\hline
Nodes & Number of DAGs & Nodes & Number of DAGs \\ \hline
$1$ & $1$ & $13$ & $1.9\cdot 10^{31}$ \\
$2$ & $3$& $14$ & $1.4\cdot 10^{36}$\\
$3$ & $25$ & $15$ & $2.4\cdot 10^{41}$\\
$4$ & $543$ & $16$ & $8.4\cdot 10^{46}$\\
$5$ & $29281$ & $17$ & $6.3\cdot 10^{52}$\\
$6$ & $3.8\cdot 10^{6}$ & $18$ & $9.9\cdot 10^{58}$\\
$7$ & $1.1\cdot 10^{9}$ & $19$ & $3.3\cdot 10^{65}$\\
$8$ & $7.8\cdot 10^{11}$ & $20$ & $2.35\cdot 10^{72}$\\
$9$ & $1.2\cdot 10^{15}$ & $21$ & $3.5\cdot 10^{79}$\\
$10$ & $4.2\cdot 10^{18}$ & $22$ & $1.1\cdot 10^{87}$\\
$11$ & $3.2\cdot 10^{22}$ & $23$ & $7.0\cdot 10^{94}$\\
$12$ & $5.2\cdot 10^{26}$ & $24$ & $9.4\cdot 10^{102}$ \\ \hline
\end{tabular}
}
\end{center}

\end{minipage}
\end{slide}





%####################################################################################
%# Two approaches to structural learning 
%####################################################################################

\begin{slide}{Two approaches to structural learning }
\begin{minipage}{\linewidth}

\Blue{\ul{Score based learning:}}
\begin{dinglist}{228}
\item Produces a series of candidate structures.
\item Returns the structure with highest score.
\end{dinglist}
\ \\


\Blue{\ul{Constraint based learning:}}
\begin{dinglist}{228}
\item Establishes a set of conditional independence statements for the
  data.
\item Builds a structure with d-separation properties corresponding to the
  independence statements found.
\end{dinglist}


\end{minipage}
\end{slide}



%####################################################################################
%# Constraint based learning
%####################################################################################

\begin{slide}{Constraint based learning}
\begin{minipage}{\linewidth}
\Blue{\ul{Some notation:}}
\begin{dinglist}{228}
\item To denote that $A$ is conditionally independent of $B$ given $\calX$ in
the database we shall use
\[
I(A,B,\calX).
\]
\end{dinglist}
\vspace*{-0.5cm}

\Blue{\ul{Some assumptions:}}
\begin{dinglist}{228}
\item The database is a \Red{faithful} sample from a Bayesian network
  $M$: $A$ and $B$ are d-separated given $\calX$ in $M$ if and only if
  $I(A,B,\calX)$.
\item We have an oracle that correctly answers questions of the type:\\
\centerline{``Is $I(A,B,\calX)$?''}
\end{dinglist}
\ \\

\Blue{\ul{The algorithm:}} Use the oracle's answers to first establish a \Red{skeleton} of a
Bayesian network:
\begin{dinglist}{228}
\item The skeleton is the undirected graph
  obtained by removing directions on the arcs.
\end{dinglist}
\vspace*{-0.2cm}
\pstexfignocap[0.6]{ABS}
\vspace*{-0.2cm}
Next, when the skeleton is found we then start looking for the directions on
the arcs.

\end{minipage}
\end{slide}




%####################################################################################
%# Finding the skeleton
%####################################################################################

\begin{slide}{Finding the skeleton I}
\begin{minipage}{\linewidth}
\Blue{The idea:} if there is a link between $A$ and $B$ in $M$ then they cannot be
d-separated, and as the data is faithful it can be checked by asking
questions to the oracle:
\begin{dinglist}{228}
\item The link $A-B$ is part of the skeleton if and only if $\neg
  I(A,B,\calX)$, for all $\calX$.
\end{dinglist}

Assume that the only conditional independence found is $I(A,B)$:

\pstexfignocap[0.65]{ABC-skeleton2}


Assume that the conditional independences found are $I(A,B,D)$ and
$I(C,D,\{A,B\})$:

\pstexfignocap[0.65]{ABCD-skeleton-no-arc}

\end{minipage}
\end{slide}



%####################################################################################
%# Finding the skeleton
%####################################################################################

\begin{slide}{Finding the skeleton II}
\begin{minipage}{\linewidth}
\Blue{The idea:} if there is a link between $A$ and $B$ in $M$ then they cannot be
d-separated, and as the data is faithful it can be checked by asking
questions to the oracle:
\begin{dinglist}{228}
\item The link $A-B$ is part of the skeleton if and only if $\neg
  I(A,B,\calX)$, for all $\calX$.
\end{dinglist}

Assume that the only conditional independence found is $I(A,B)$:

\pstexfignocap[0.65]{ABC-skeleton2}


Assume that the conditional independences found are $I(A,B,D)$ and
$I(C,D,\{A,B\})$:

\pstexfignocap[0.65]{ABCD-skeleton}

\end{minipage}
\end{slide}




%####################################################################################
%# Setting directions on the links
%####################################################################################

\begin{slide}{Setting the directions on the links I}
\begin{minipage}{\linewidth}

\Red{\ul{Rule 1:}} If you have three nodes,
$A, B, C$ such that $A-C$ and $B-C$, but not $A-B$, then introduce the
v-structure $A \rightarrow C \leftarrow B$ if there exists an $\calX$
(possibly empty) such
that $I(A, B, \calX)$ and $C \not\in \calX$.

\pstexfignocap[0.65]{ABS2}

\Blue{\ul{Example:}} Assume that we get the independences 
$I(A,B)$, $I(B,C)$, $I(A,B,C)$, $I(B,C,A)$, $I(C,D,A)$,
$I(B,C,\{D,A\})$, $I(C,D,\{A,B\})$, $I(B,E,\{C,D\})$,
$I(A,E,\{C,D\})$, $I(B,C,\{A,D,E\})$, $I(A,E,\{B,C,$ $D\})$,
$I(B,E,\{A,C,D\})$.
% $I(A, B)$, $I(A, B, D)$, $I(A, D)$, $I(A, D, B)$,
% $I(A, D, \{B, C\})$, $I(A, D,\{B,C, E\})$, $ I(C, D, B)$, $I(C, D,$ $
% \{A, B\})$, $I(B,$ $E, \{C, D\})$, $I(B, E, \{C, D, A \})$, $I(A, E,
% \{C, D\})$ and $I(A, E, \{C, D, B\})$.


\begin{center}
\scalebox{0.6}{\input{\figpath/ABCDE-skeleton.pstex_t}} 
\end{center}

\end{minipage}
\end{slide}



%####################################################################################
%# Setting directions on the links
%####################################################################################

\begin{slide}{Setting the directions on the links I}
\begin{minipage}{\linewidth}

\Red{\ul{Rule 1:}} If you have three nodes,
$A, B, C$ such that $A-C$ and $B-C$, but not $A-B$, then introduce the
v-structure $A \rightarrow C \leftarrow B$ if there exists an $\calX$
(possibly empty) such
that $I(A, B, \calX)$ and $C \not\in \calX$.

\pstexfignocap[0.65]{ABS2}

\Blue{\ul{Example:}} Assume that we get the independences $I(A,B)$, $I(B,C)$, $I(A,B,C)$, $I(B,C,A)$, $I(C,D,A)$,
$I(B,C,\{D,A\})$, $I(C,D,$ $\{A,B\})$, $I(B,E,\{C,D\})$,
$I(A,E,\{C,D\})$, $I(B,C,\{A,D,E\})$, $I(A,E,\{B,C,$ $D\})$,
$I(B,E,\{A,C,D\})$.
%  $I(A, B)$, $I(A, B, D)$, $I(A, D)$, $I(A, D, B)$,
% $I(A, D, \{B, C\})$, $I(A, D,\{B,C, E\})$, $ I(C, D, B)$, $I(C, D,$ $
% \{A, B\})$, $I(B,$ $E, \{C, D\})$, $I(B, E, \{C, D, A \})$, $I(A, E,
% \{C, D\})$ and $I(A, E, \{C, D, B\})$.

\begin{center}
\begin{tabular}{cc}
\scalebox{0.6}{\input{\figpath/ABCDE-skeleton.pstex_t}} &
\scalebox{0.6}{\input{\figpath/ABCDE-v-structures.pstex_t}} 
\end{tabular}
\end{center}

\end{minipage}
\end{slide}





%####################################################################################
%# Setting directions on the links
%####################################################################################

\begin{slide}{Setting the directions on the links II}
\begin{minipage}{\linewidth}

\Red{\ul{Rule 2 [Avoid new v-structures]:}} When Rule 1 has been
exhausted, and you have $A \rightarrow C-B$ (and no link between $A$
and $B$), then direct $C \rightarrow B$.
\ \\ 
\ \\

\Red{\ul{Rule 3 [Avoid cycles]:}} If $A \rightarrow B$ introduces a
directed cycle in the graph, then do $A \leftarrow B$
\ \\
\ \\

\Red{\ul{Rule 4 [Choose randomly]:}} If none of the rules 1-3 can be
applied anywhere in the graph, choose an undirected link and give it
an arbitrary direction.
\ \\
\ \\


\Blue{\ul{Example:}}

\begin{center}
\begin{tabular}{ccc}
\scalebox{0.6}{\input{\figpath/ABCDE-skeleton.pstex_t}} &
\scalebox{0.6}{\input{\figpath/ABCDE-v-structures.pstex_t}} &
\scalebox{0.6}{\input{\figpath/ABCDE-directed.pstex_t}} \\
Skeleton & Rule 1 & Rule 4
\end{tabular}
\end{center}

\end{minipage}
\end{slide}

%####################################################################################
%# The rules: an overview
%####################################################################################

\begin{slide}{The rules: an overview}
\begin{minipage}{\linewidth}
\Red{\ul{Rule 1 [Find v-structures]:}} If you have three nodes,
$A, B, C$ such that $A-C$ and $B-C$, but not $A-B$, then introduce the
v-structure $A \rightarrow C \leftarrow B$ if there exists an $\calX$
(possibly empty) such
that $I(A, B, \calX)$ and $C \not\in \calX$. 
\ \\
\ \\ 

\hrule

\ \\
\ \\

\Red{\ul{Rule 2 [Avoid new v-structures]:}} When Rule 1 has been
exhausted, and you have $A \rightarrow C-B$ (and no link between $A$
and $B$), then direct $C \rightarrow B$.
\ \\ 
\ \\

\Red{\ul{Rule 3 [Avoid cycles]:}} If $A \rightarrow B$ introduces a
directed cycle in the graph, then do $A \leftarrow B$
\ \\
\ \\

\Red{\ul{Rule 4 [Choose randomly]:}} If none of the rules 1-3 can be
applied anywhere in the graph, choose an undirected link and give it
an arbitrary direction.

\end{minipage}
\end{slide}




%####################################################################################
%# Another example
%####################################################################################

\begin{slide}{Another example}
\begin{minipage}{\linewidth}
Consider the graph:

\begin{center}
\scalebox{0.6}{\input{\figpath/independence-test-a.pstex_t}} 
\end{center}

\centerline{
\Red{Apply the four rules to learn a Bayesian network structure}}

\end{minipage}
\end{slide}



%####################################################################################
%# Another example
%####################################################################################

\PDForPS{
\overlays{6}{
\begin{slide}{Another example I}
\begin{minipage}{\linewidth}



\begin{tabular}{ccc}
\fromSlide*{1}\scalebox{0.6}{\input{\figpath/independence-test-a.pstex_t}} &
\fromSlide*{2}{\scalebox{0.6}{\input{\figpath/independence-test-b.pstex_t}}} &
\fromSlide*{3}{\scalebox{0.6}{\input{\figpath/independence-test-c.pstex_t}}} \\
\fromSlide*{1}{Step 1: \Blue{Rule 1}} & \fromSlide*{2}{Step 2: \Blue{Rule 2}} & \fromSlide*{3}{Step 3: \Blue{Rule 4}} \\
&  & \\
\fromSlide*{4}{\scalebox{0.6}{\input{\figpath/independence-test-d.pstex_t}}} &
\fromSlide*{5}{\scalebox{0.6}{\input{\figpath/independence-test-e.pstex_t}}} &
\fromSlide*{6}{\scalebox{0.6}{\input{\figpath/independence-test-f.pstex_t}}} \\
\fromSlide*{4}{Step 4:  \Blue{Rule 2}} & \fromSlide*{5}{Step 5: \Blue{Rule 2}} & \fromSlide*{6}{Step 6: \Blue{Rule 4}}
\end{tabular}


\fromSlide*{6}{
\centerline{However, we are not guaranteed a unique solution!}


}
\end{minipage}
\end{slide}}
}
{
\begin{slide}{Another example I}
\begin{minipage}{\linewidth}

\begin{center}

\begin{tabular}{ccc}
\scalebox{0.6}{\input{\figpath/independence-test-a.pstex_t}} &
\scalebox{0.6}{\input{\figpath/independence-test-b.pstex_t}} &
\scalebox{0.6}{\input{\figpath/independence-test-c.pstex_t}} \\
Step 1: \Blue{Rule 1} & Step 2: \Blue{Rule 2} & Step 3: \Blue{Rule 4} \\
&  & \\
\scalebox{0.6}{\input{\figpath/independence-test-d.pstex_t}} &
\scalebox{0.6}{\input{\figpath/independence-test-e.pstex_t}} &
\scalebox{0.6}{\input{\figpath/independence-test-f.pstex_t}} \\
Step 4:  \Blue{Rule 2} & Step 5: \Blue{Rule 2} & Step 6: \Blue{Rule 4}
\end{tabular}
\end{center}

\centerline{However, we are not guaranteed a unique solution!}
\end{minipage}
\end{slide}
}

%####################################################################################
%# Another example
%####################################################################################

\PDForPS{
\overlays{5}{
\begin{slide}{Another example II}
\begin{minipage}{\linewidth}



\begin{tabular}{ccc}
\fromSlide*{1}{\scalebox{0.6}{\input{\figpath/independence-test-a.pstex_t}}} &
\fromSlide*{1}{\scalebox{0.6}{\input{\figpath/independence-test-b.pstex_t}}} &
\fromSlide*{2}{\scalebox{0.6}{\input{\figpath/independence-test-g.pstex_t}}} \\
\fromSlide*{1}{Step 1:  \Blue{Rule 1}} & \fromSlide*{1}{Step 2: \Blue{Rule 2}} & \fromSlide*{2}{Step 3: \Blue{Rule 4}} \\
&  & \\
\fromSlide*{3}{\scalebox{0.6}{\input{\figpath/independence-test-h.pstex_t}}} &
\fromSlide*{4}{\scalebox{0.6}{\input{\figpath/independence-test-i.pstex_t}}} &
\fromSlide*{5}{\scalebox{0.6}{\input{\figpath/independence-test-j.pstex_t}}} \\
\fromSlide*{3}{Step 4: \Blue{Rule 4}} & \fromSlide*{4}{Step 5: \Blue{Rule 2}} & \fromSlide*{5}{Step 6: \Blue{Rule 2+3}}
\end{tabular}

\fromSlide*{5}{
Although the solution is not necessarily unique, all solutions have
the same d-separation properties!


}
\end{minipage}
\end{slide}}
}
{
\begin{slide}{Another example II}
\begin{minipage}{\linewidth}



\begin{tabular}{ccc}
\scalebox{0.6}{\input{\figpath/independence-test-a.pstex_t}} &
\scalebox{0.6}{\input{\figpath/independence-test-b.pstex_t}} &
\scalebox{0.6}{\input{\figpath/independence-test-g.pstex_t}} \\
Step 1:  \Blue{Rule 1} & Step 2: \Blue{Rule 2} & Step 3: \Blue{Rule 4} \\
&  & \\
\scalebox{0.6}{\input{\figpath/independence-test-h.pstex_t}} &
\scalebox{0.6}{\input{\figpath/independence-test-i.pstex_t}} &
\scalebox{0.6}{\input{\figpath/independence-test-j.pstex_t}} \\
Step 4: \Blue{Rule 4} & Step 5: \Blue{Rule 2} & Step 6: \Blue{Rule 2+3}
\end{tabular}


Although the solution is not necessarily unique, all solutions have
the same d-separation properties!

\end{minipage}
\end{slide}
}




%####################################################################################
%# From independence tests to skeleton
%####################################################################################

\begin{slide}{From independence tests to skeleton}
\begin{minipage}{\linewidth}

Until now, we have assumed that all questions of the form ``Is
$I(A,B,\calX)$?'' can be answered (allowing us to establish the
skeleton). However, questions come at a price, and we would there like
to ask as few questions as possible.
\ \\

To reduce the number of questions we exploit the following property:
\ \\

\Blue{\ul{Theorem:}} The nodes $A$ and $B$ are not linked if and only
if $I(A,B,\pa{A})$ or $I(A,B,\pa{B})$.
\ \\
\ \\

\centerline{\Red{It is sufficient to ask questions $I(A,B,\calX)$,
    where $\calX$ is a subset of $A$'s or $B$'s neighbors.}}
\vsp
\vsp

\begin{tabular}{cc}
  \psfrag{|A}[c]{$A$}
 \psfrag{|B}[c]{$B$}
 \psfrag{|C}[c]{$C$}
 \psfrag{|D}[c]{$D$}
 \psfrag{|E}[c]{$E$}
 \psfrag{|F}[c]{$F$}
 \psfrag{|G}[c]{$G$}
 \psfrag{|H}[c]{$H$}
\includegraphics[scale=0.6]{\figpath/necessary-independence-test.eps}
&
An active path from $A$ to $B$ must go through a parent of $B$.
\end{tabular}

\end{minipage}
\end{slide}



%####################################################################################
%# The PC algorithm
%####################################################################################

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

\Blue{\ul{The PC algorithm:}}
\begin{enumerate}
\item Start with the complete graph;

\item $i:= 0$;

\item {\bf while} a node has at least $i+1$ neighbors

\begin{itemize}

\item[-] {\bf for all} nodes $A$ with at least $i+1$ neighbors \\
\begin{itemize}
\item[-] {\bf for all} neighbors $B$ of $A$ \\
\begin{itemize}
\item[-] {\bf for all} neighbor sets $\calX$ such that $\sizeof{\calX} = i$ and $\calX
\subseteq (\nb{A} \setminus \{B\})$ \\
\begin{itemize}
\item[-] {\bf if} $I(A, B, \calX)$ {\bf then} remove the link $A-B$ and store
"$I(A, B, \calX)$"
\end{itemize}
\end{itemize}

\end{itemize}

\item[-] $i := i+1$

\end{itemize}

\end{enumerate}

\end{minipage}
\end{slide}


%####################################################################################
%# Example
%####################################################################################

\begin{slide}{Example}
\begin{minipage}{\linewidth}
We start with the complete graph and ask the questions $I(A, B)$?,
$I(A, C)$?, $I(A, D)$?, $I(A, E)$?, $I(B, C)$?, $I(B, D)$?, $I(B,
E)$?, $I(C, D)$?, $I(C, E)$?, $I(D, E)$?
% $I(A, B)$?,
% $I(A, C)$?, $I(A, D)$?, $I(A, E)$?, $I(B, C)$?, $I(B, D)$?, $I(B,
% E)$?, $I(C, D)$?, $I(C, E)$?, $I(D, E)$?.


\begin{center}
\begin{tabular}{cc}
\scalebox{0.8}{\input{\figpath/independence-question-a.pstex_t}} &
\scalebox{0.8}{\input{\figpath/independence-question-b.pstex_t}} \\
The original model & The complete graph
\end{tabular}
\end{center}


\end{minipage}
\end{slide}



%####################################################################################
%# Example
%####################################################################################

\begin{slide}{Example}
\begin{minipage}{\linewidth}
We start with the complete graph and ask the questions $I(A, B)$?,
$I(A, C)$?, $I(A, D)$?, $I(A, E)$?, $I(B, C)$?, $I(B, D)$?, $I(B,
E)$?, $I(C, D)$?, $I(C, E)$?, $I(D, E)$?.


\begin{center}
\begin{tabular}{cc}
\scalebox{0.8}{\input{\figpath/independence-question-a.pstex_t}} &
\scalebox{0.8}{\input{\figpath/independence-question-b.pstex_t}} \\
The original model & The complete graph
\end{tabular}
\end{center}
\ \\
\ \\

We get a ``yes'' for $I(A,B)$? and $I(B,C)$?:
\begin{dinglist}{228}
\item the links $A-B$ and
$B-C$ are therefore removed.
\end{dinglist}

\end{minipage}
\end{slide}



%####################################################################################
%# Example
%####################################################################################

\begin{slide}{Example}
\begin{minipage}{\linewidth}
We now condition on one variable and ask the questions $I(A, C, E)?$, $I(A, E, C)?$, $I(B, C, D)?$, $I(B, C, E)?$, $I(B, D, C)?$,
$I(B, D, E)?$, $I(B, E, C)?$, $I(B, E, D)?$, $I(C, B, A)?$, \ldots ,$I(C, D,
A)?$, $I(C, D, B)?$. 

\begin{center}
\begin{tabular}{cc}
\scalebox{0.8}{\input{\figpath/independence-question-a.pstex_t}} &
\scalebox{0.8}{\input{\figpath/independence-final-a.pstex_t}} \\
The original model & After one iteration
\end{tabular}
\end{center}


\end{minipage}
\end{slide}


%####################################################################################
%# Example
%####################################################################################

\begin{slide}{Example}
\begin{minipage}{\linewidth}
We now condition on one variable and ask the questions $I(A, C, E)?$, $I(A, E, C)?$, $I(B, C, D)?$, $I(B, C, E)?$, $I(B, D, C)?$,
$I(B, D, E)?$, $I(B, E, C)?$, $I(B, E, D)?$, $I(C, B, A)?$, \ldots ,$I(C, D,
A)?$, $I(C, D, B)?$. 

\begin{center}
\begin{tabular}{cc}
\scalebox{0.8}{\input{\figpath/independence-question-a.pstex_t}} &
\scalebox{0.8}{\input{\figpath/independence-final-a.pstex_t}} \\
The original model & After one iteration
\end{tabular}
\end{center}
\ \\
\ \\

The question $I(C, D, A)?$ has the answer "yes":
\begin{dinglist}{228}
\item we therefore remove
the link $C-D$.
\end{dinglist}

\end{minipage}
\end{slide}


%####################################################################################
%# Example
%####################################################################################

\begin{slide}{Example}
\begin{minipage}{\linewidth}
We now condition on two variable and ask questions like $I(B, C, \{D,
E\})?$.

\begin{center}
\begin{tabular}{cc}
\scalebox{0.8}{\input{\figpath/independence-question-a.pstex_t}} &
\scalebox{0.8}{\input{\figpath/independence-final-b.pstex_t}} \\
The original model & After two iterations
\end{tabular}
\end{center}
\ \\
\ \\

The questions $I(B, E, \{C, D \})?$ and $I(E, A, \{D, C
\})?$ have the answer ``yes'': 

\begin{dinglist}{228}
\item we therefore remove
the links $B-E$ and $A-E$.
\end{dinglist}

\end{minipage}
\end{slide}


%####################################################################################
%# Example
%####################################################################################

\begin{slide}{Example}
\begin{minipage}{\linewidth}
We now condition on three variables, but since no nodes have four
neighbors we are finished.

\begin{center}
\begin{tabular}{cc}
\scalebox{0.8}{\input{\figpath/independence-question-a.pstex_t}} &
\scalebox{0.8}{\input{\figpath/independence-final-c.pstex_t}} \\
The original model & After three iterations
\end{tabular}
\end{center}
\ \\
\ \\

The identified set of independence statements are then  $I(A, B)$, $I(B, C)$,
$I(C, D, A)$, $I(A, E, \{C, D\})$, and $I(B, E, \{C, D \})$. They are
sufficient for applying rules 1-4.

\end{minipage}
\end{slide}


%####################################################################################
%# Real world data
%####################################################################################

\begin{slide}{Real world data}
\begin{minipage}{\linewidth}

The oracle is a statistical test, e.g.\ \Blue{conditional mutual information}:

\[ CE(A, B| X) = \sum_{X} P(X) \sum_{A, B} P(A, B| X) \log \frac {P(A, B| X)}{P(A| X)P(B| X)}.   \]

\[ I(A, B, X) \Leftrightarrow CE(A, B| X) = 0. \]

However, all tests have false positives and false negatives, which may
provide false results/causal relations! 
\ \\

Similarly, false results may also be caused to
\Green{hidden variables}: 

\pstexfignocap[0.7]{hidden-variable}

\end{minipage}
\end{slide}




%####################################################################################
%# Properties
%####################################################################################

\begin{slide}{Properties}
\begin{minipage}{\linewidth}

\begin{dinglist}{228}
\item If the database is a faithful sample from a Bayesian network and
  the oracle is reliable, then a solution exists.
\item You can only infer causal relations if no hidden variables
  exists.
\end{dinglist}

\end{minipage}
\end{slide}

\end{document}





