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

\input{preamble}

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


\begin{document}
\maketitle

\begin{slide}{Classification: Text Categorization}


The Association for Computing Machinery (ACM) maintains a subject classification
scheme for computer science research papers. Part of the subject hierarchy (1998 
version):

\begin{center}
\scalebox{0.8}{
\parbox{80mm}{
\begin{tabbing}
  I. Comp\=uting Methodologies \\
\> I.2 Arti\=ficial Intelligence \\
\>\> I.2.6 \= Learning \\
\>\>\> - Analogies \\
\>\>\> - Concept learning \\
\>\>\> - Connectionism and neural nets \\
\>\>\> - Induction \\
\>\>\> - Knowledge acquisition \\
\>\>\> - Language acquisition \\
\>\>\> - Parameter learning 
\end{tabbing}
}}
\end{center}

Papers are manually classified by authors or editors. 
\vsp

{\bf Data:} collection of classified papers (full text or abstracts)\\

{\bf Task:} build a \emph{classifier} that automatically assigns a subject index to new, 
unclassified papers.
\vsp

\end{slide}





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% slide1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{slide}{Classification: Spam Filtering}

\Subheading{}
\vsp

Spam filtering in Mozilla: user trains the mail reader to recognize
spam by manually labeling incoming mails as spam/no spam. 
\vsp

{\bf Data:} collection of user-classified emails (full text).


{\bf Task:} build  a classifier that automatically categorizes an incoming email as
spam/no spam

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% slide1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{slide}{Classification: Character Recognition}

\begin{center}
  \includegraphics[scale=0.4]{\figpath/DATA-wo_grid.eps}
\end{center}
\vsp


{\bf Data:} collection of handwritten characters, correctly labeled.

{\bf Task:} build a classifier that identifies new handwritten characters.

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% slide1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{slide}{Classification: Credit Rating}

From existing customer data predict whether a person applying for a 
new loan will repay or default on the loan. 
\vsp

{\bf Data:} existing customer records with attributes like age, employment type, income, \ldots
and information on payback history.

{\bf Task:} build a classifier that 
predicts whether a new customer will repay the loan.


\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% slide1
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{slide}{Classification using Bayesian networks}
Consider the poker domain and assume that we want a classifier for
predicting \vn{BH} based on \vn{FC}, \vn{SC}, and \vn{MH}.
\begin{center}
\psfrag{|OH0}[c]{\vn{OH0}\/}
\psfrag{|OH1}[c]{\vn{OH1}\/}
\psfrag{|OH2}[c]{\vn{OH2}\/}
\psfrag{|FC}[c]{\vn{FC}\/}
\psfrag{|SC}[c]{\vn{SC}\/}
\psfrag{|BH}[c]{\vn{BH}\/}
\psfrag{|MH}[c]{\vn{MH}\/}
\includegraphics[scale=0.5]{\figpath/classifier-BN-poker.eps}
\end{center}
When learning the model from data (over \vn{FC}, \vn{SC}, \vn{MH},
\vn{BH}), we are likely to get:

\begin{center}
\psfrag{|OH0}[c]{\vn{OH0}\/}
\psfrag{|OH1}[c]{\vn{OH1}\/}
\psfrag{|OH2}[c]{\vn{OH2}\/}
\psfrag{|FC}[c]{\vn{FC}\/}
\psfrag{|SC}[c]{\vn{SC}\/}
\psfrag{|BH}[c]{\vn{BH}\/}
\psfrag{|MH}[c]{\vn{MH}\/}
\includegraphics[scale=0.5]{\figpath/classifier-learned-poker-model}
\end{center}

\centerline{\Red{This is not a compact model!}}

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{slide}{Naive Bayes}

A compact type of model is the naive Bayes model:
\begin{center}
\psfrag{|OH0}[c]{\vn{OH0}\/}
\psfrag{|OH1}[c]{\vn{OH1}\/}
\psfrag{|OH2}[c]{\vn{OH2}\/}
\psfrag{|FC}[c]{\vn{FC}\/}
\psfrag{|SC}[c]{\vn{SC}\/}
\psfrag{|BH}[c]{\vn{BH}\/}
\psfrag{|MH}[c]{\vn{MH}\/}
\includegraphics[scale=0.5]{\figpath/classifier-NB-poker-model}
\end{center}



\vspace{5mm}

Interpretation: Given the true class labels, the different attributes 
take their value independently.



\end{slide}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% slide1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}{Naive Bayes}

\Subheading{The naive Bayes assumption I}
\vspace{5mm}

\begin{center}
\includegraphics[scale=0.4]{\figpath/fiveones.eps}
\end{center}
\vsp

For example:
\begin{displaymath}
P(\emph{Cell-2}=b\given \emph{Cell-5}=b,\emph{Symbol}=1)>
P(\emph{Cell-2}=b\given \emph{Symbol}=1)
\end{displaymath}

{\darkred Attributes not independent given \emph{Symbol}=1!}


\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% slide1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}{Naive Bayes}
\Subheading{The naive Bayes assumption II}
\vspace{5mm}

For spam example e.g.:
\begin{displaymath}
\begin{array}{c}
P(\mbox{Body'nigeria'={\xfiggreeniii y}}\given \mbox{Body'confidential'={\xfiggreeniii y}},\mbox{Spam={\xfiggreeniii y}})\\
\gg \\
P(\mbox{Body'nigeria'={\xfiggreeniii y}}\given \mbox{Spam={\xfiggreeniii y}})
\end{array}
\end{displaymath}

{\darkred Attributes not independent given \emph{Spam}=yes!}
\vsp

$\leadsto$\ Naive Bayes assumption often not realistic. Nevertheless, Naive Bayes 
often successful. 


\end{slide}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% slide1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{slide}{Naive Bayes}
\Subheading{Learning a Naive Bayes Classifier}
\vsp

\begin{itemize}
\item Determine parameters $P(a_i\given c)$\ ($a_i\in\emph{States}(A_i),c\in \emph{States}(C)$) 
from empirical counts in the data.
\item Missing values are easily handled: instances for which $A_i$\ is missing are ignored 
for $P(a_i\given c)$.
\item Discrete and continuous attributes can be mixed.
\end{itemize}


\end{slide}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% slide1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\overlays{2}{
\begin{slide}{Naive Bayes}

\Subheading{The paradoxical success of Naive Bayes}
\vsp

One explanation for the surprisingly good performance of Naive Bayes in 
many domains: do not require exact distribution for 
classification, only the right decision boundaries

\psfrag{plr}[c]{${\red \oplus}$}
\psfrag{plnb}[c]{${\blue \oplus}$}
\psfrag{redleg}[l]{${\red \oplus}:\ P(C=\oplus\given a_1,\ldots,a_n )$\ (real)}
\psfrag{blueleg}[l]{${\blue \oplus}:\ P(C=\oplus\given a_1,\ldots,a_n )$\ (Naive Bayes)}
\psfrag{attrbs}[c]{$\emph{States}(A_1,\ldots,A_n)$}

\vspace{-5mm}

\begin{center}
\onlySlide*{1}{\includegraphics[scale=0.8]{\figpath/realnbdistr-0.eps}}%
\onlySlide*{2}{\includegraphics[scale=0.8]{\figpath/realnbdistr.eps}}%

\end{center}

\end{slide}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% slide1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}{Naive Bayes}

\Subheading{When Naive Bayes must fail}
\vsp

No Naive Bayes Classifier can  produce the following 
classification:

\begin{center}
\begin{tabular}{|cc|c|}
\hline
$A$ & $B$ & Class \\ \hline
{\xfiggreeniii yes} & {\xfiggreeniii yes} & ${\red \oplus}$\\
{\xfiggreeniii yes} & {\xfiggreeniii no} & ${\red \ominus}$\\
{\xfiggreeniii no} & {\xfiggreeniii yes} & ${\red \ominus}$\\
{\xfiggreeniii no} & {\xfiggreeniii no} & ${\red \oplus}$\\ \hline
\end{tabular}
\end{center}


because assume it did, then: 


  \begin{eqnarray*}
    1.\hspace{4mm}
    P(A={\xfiggreeniii y}\given {\red \oplus})P(B={\xfiggreeniii y}\given {\red \oplus})
    P({\red \oplus})
    & > &
    P(A={\xfiggreeniii y}\given {\red \ominus})P(B={\xfiggreeniii y}\given {\red \ominus})
    P({\red \ominus})\\
    2.\hspace{4mm}
    P(A={\xfiggreeniii y}\given {\red \ominus})P(B={\xfiggreeniii n}\given {\red \ominus})
    P({\red \ominus})
    & > &
    P(A={\xfiggreeniii y}\given {\red \oplus})P(B={\xfiggreeniii n}\given {\red \oplus})
    P({\red \oplus})\\
    3.\hspace{4mm}
    P(A={\xfiggreeniii n}\given {\red \ominus})P(B={\xfiggreeniii y}\given {\red \ominus})
    P({\red \ominus})
    & > &
    P(A={\xfiggreeniii n}\given {\red \oplus})P(B={\xfiggreeniii y}\given {\red \oplus})
    P({\red \oplus})\\
    4.\hspace{4mm}
    P(A={\xfiggreeniii n}\given {\red \oplus})P(B={\xfiggreeniii n}\given {\red \oplus})
    P({\red \oplus})
    & > &
    P(A={\xfiggreeniii n}\given {\red \ominus})P(B={\xfiggreeniii n}\given {\red \ominus})
    P({\red \ominus})
  \end{eqnarray*}

\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% slide1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}{Naive Bayes}

Multiplying the four left sides and the four right sides of these inequalities:
\begin{displaymath}
  \prod_{i=1}^4(\emph{left side of } i.) > \prod_{i=1}^4(\emph{right side of } i.)
\end{displaymath}
But this is false, because both products are actually equal.


\end{slide}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% slide1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}{Tree Augmented Naive Bayes}


\psfrag{|OH0}[c]{\vn{OH0}\/}
\psfrag{|OH1}[c]{\vn{OH1}\/}
\psfrag{|OH2}[c]{\vn{OH2}\/}
\psfrag{|FC}[c]{\vn{FC}\/}
\psfrag{|SC}[c]{\vn{SC}\/}
\psfrag{|BH}[c]{\vn{BH}\/}
\psfrag{|MH}[c]{\vn{MH}\/}

\raisebox{10mm}{
\begin{minipage}[b]{50mm}
Model: all Bayesian network structures where 
\begin{itemize}
\item [-] The class node is a parent of each attribute node
\item [-] The substructure on the attribute nodes is a tree
\end{itemize}
\end{minipage}
}
\hspace{3mm}
\includegraphics[scale=0.5]{\figpath/classifier-TAN-poker-model}
%tan.eps}
\vsp

Learning TAN classifier: learning the tree structure and parameters.
Optimal tree structure can be found efficiently.



\end{slide}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% slide1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}{Tree Augmented Naive Bayes}


\psfrag{cptC}[r]{
$
  \begin{array}{l|cc}
    & {\red \oplus} & {\red \ominus} \\ \hline
    & 0.5 & 0.5
  \end{array}
$
}

\psfrag{cptA}[l]{
$
  \begin{array}{l|cc}
    C & \mbox{{\xfiggreenii yes}} & \mbox{{\xfiggreenii no}} \\ \hline
    {\red \oplus} & 0.5 & 0.5\\
    {\red \ominus} & 0.5 & 0.5
  \end{array}
$
}
\psfrag{cptB}[l]{
$
  \begin{array}{cc|cc}
    C & A & \mbox{{\xfiggreenii yes}} & \mbox{{\xfiggreenii no}} \\ \hline
    {\red \oplus} & \mbox{{\xfiggreenii yes}} & 1.0 & 0.0\\
    {\red \oplus} & \mbox{{\xfiggreenii no}} & 0.0 & 1.0\\
    {\red \ominus} & \mbox{{\xfiggreenii yes}} & 0.0 & 1.0\\
    {\red \ominus} & \mbox{{\xfiggreenii no}} & 1.0 & 0.0
  \end{array}
$
}

TAN classifier for 
\scalebox{0.7}{
\begin{tabular}{|cc|c|}
\hline
$A$ & $B$ & Class \\ \hline
{\xfiggreeniii yes} & {\xfiggreeniii yes} & ${\red \oplus}$\\
{\xfiggreeniii yes} & {\xfiggreeniii no} & ${\red \ominus}$\\
{\xfiggreeniii no} & {\xfiggreeniii yes} & ${\red \ominus}$\\
{\xfiggreeniii no} & {\xfiggreeniii no} & ${\red \oplus}$\\ \hline
\end{tabular}
}:

  \begin{center}
    \includegraphics[scale=0.5]{\figpath/tanforbool.eps}
  \end{center}

\end{slide}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% slide1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}{Evaluating Classifiers}

\Subheading{Validation}
\vsp



Evaluation: estimate of the performance of a classifier on
future data.
Estimate obtained by measuring performance on \emph{validation set}
(distinct from test set used for parameter tuning!); or by
cross-validation.

\vsp

\Subheading{Classification Error}
\vsp

Classifier ${\cal C}$ is used to classify
instances $\bma_1,\ldots,\bma_N$\ with
true class labels $c_1,\ldots,c_N$. Class labels assigned by
 ${\cal C}:\ c'_1,\ldots,c'_N$.
Classification error:
\begin{displaymath}
|\{i\in 1,\ldots,N\mid c_i\neq c'_i\}|/N
\end{displaymath}


\end{slide}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% slide1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{slide}{Evaluating Classifiers}

\Subheading{Expected Loss}
\vsp

A more detailed picture is provided by the \emph{confusion matrix} and
a \emph{cost function}:


\begin{center}
\begin{tabular}{cc|rrr}
& & \multicolumn{3}{c}{\vn{Pred}}\\
 & & me & draw & op \\ \hline
\multirow{3}{0.5cm}{True} 
 & me   & $0.25$ & $0.05$ & $0.1$ \\
 & draw & $0.05$ & $0.1$  & $0.05$ \\
 & op  & $0.05$ & $0.1$  & $0.25$\\\hline 
\multicolumn{5}{c}{}\\
\multicolumn{5}{c}{{\bf Confusion matrix}}
\end{tabular}
\hspace{5mm}
\begin{tabular}{cc|rrr}
 & & \multicolumn{3}{c}{\vn{Pred}}\\
 & & me & draw & op \\ \hline
\multirow{3}{0.5cm}{True} 
 & me   & $0$ & $0$ & $-1$ \\
 & draw & $0$ & $0$  & $-1$ \\
 & op  & $-3$ & $-1$  & $0$ \\\hline
\multicolumn{5}{c}{}\\
\multicolumn{5}{c}{{\bf Loss matrix}}\\
\end{tabular}
\end{center}
\vsp

Expected Loss:
\begin{displaymath}
  \sum_{\rm{True},\rm{Pred.}
}
\emph{Confusion}(\vn{True},\vn{Pred})\cdot\emph{Loss}(\vn{True},\vn{Pred})=-0.4.
\end{displaymath}

When cost function given, try to minimize expected loss (minimizing classification error is
special case for \emph{0-1 loss}: $\emph{Loss}(x,x)=0$\ and $\emph{Loss}(x,y)=1$\ for
$x\neq y$)!
\vspace*{\fill}

\end{slide}


\end{document}





