\documentstyle[12pt,eclepsf]{article}

\textheight 230mm
\topmargin 5mm
\textwidth 160mm
\oddsidemargin -2mm

\pagestyle{myheadings}
\markright{(Pattern Recognition)}

\newtheorem{formula}{Formula}
\newtheorem{excersize}{Excersize}
\newtheorem{algorithm}{Algorithm}

\begin{document}
\thispagestyle{empty}

\title{{\bf Pattern Recognition} \\ 
        {\large for \\
        postgraduates \\
        (21 February -- June, 2007)}}
\author{Akira Imada \\
Brest State Technical University, Belarus \\
        \hspace*{1in}\\
        \hspace*{1in}\\
        (last modified on)}
\maketitle

\clearpage
\begin{center}{\bf INDEX} \end{center}
\begin{itemize}
\item[1.] Introduction
   \begin{itemize}
      \item What is Pattern Recognition?
      \item What for?
      \item Classificater by {\it features.}
      \item Train by examples.
      \item How we design classification system?
   \end{itemize}
\item[2.] Bayesian Classification
\item[3.] Classification by Fuzzy Logic
\end{itemize}

\clearpage
\section{Introduction}
\subsection{What is Pattern Recognition?}

\subsection{What for?}
\begin{itemize}
\item automated speech recognition
\item finger-print (iris) recognition
\item DNA sequence identification
\item coin for coke-machine recognition
\item defect non-defect detection
\item nomal abnormal 
\item (handwritten) character recognition
\end{itemize}

\noindent
What else?

%% \subsection{Train by examples}
%% \begin{itemize}
%% \item apple belongs to A
%% \item orrange belongs to B
%% \item banana to A
%% \item pine-apple to B
%% \item lemon to A
%% \end{itemize}

%% \noindent
%% Then qivi? 

\subsection{Classification by Features}
\noindent
Recognition of a photo by its binary-pixel? $\Rightarrow$ not ploausible
$\Rightarrow$ Let's use {\it features}.

%% one feature e.g. length of fish or frequencies of voice

%% histogram of each of two classes
%% good feature and not-so-good one

%% set a dicision boundary so as to minimize error

%% error of misclassify salmon as sea-bass and vice versa

%% two featurs
%% feature space

%% pattern not yet seen

%% generalization vs over-fitting

%% minimum-error-rate
%% or
%% minimum cost(risk)rate


%% here what features or how fetures are selected are not treated


%% \subsection{how we design?}
%% \begin{itemize}
%% \item data collection
%% \item feature choise
%% \item model choice
%% \item training
%% \item evaluation
%% \end{itemize}


\subsection{Occum's rasor}
We have a dilemma {\it Not so simple to poor to classify} vs.
{not so complex to be poor for new pattern}.

For example,
a practical limit of complexity
e.g. charracter recognition with10x10 binary pixel 

supervised
un-supervised -> clustering
reinforcement only say ok or ng


recognition for classification
\subsection{An example -- Female or male?}
Well the topic here is about sermon not human.
\section{Bayesian Desision Theory}

\noindent
Assume we should guess the class that will come next without being allowed to see it.

(1) If we only know the prior probability $P(\omega_1)$ and $P(\omega_2)$

   - guess 1 if $P(\omega_1) > P(\omega_2)$ otherwise 2 \\
   - but what if we think of guessing  consecutively    \\

(2) If we know $p(x \vert \omega_1)$ --- class conditional probability

$ p(x \vert \omega_j)$ --- likelihood \\
when we have an observation of  value of  and if $p(x \vert \omega_j)$ is larger than 
$p(x \vert \omega_i)$
$\omega_j$ is more likely to be true
 

$P(\omega \vert x)$ --- posterior probability

   - guess 1 if $P(\omega_1 \vert x) > P(\omega_1  \vert x)$ otherwise 2


excersize
giving $p(x \vert omega_j)$ as a specific table or function form, 
calculate $P(\omega vert x)$ \\

\subsection{Let's formalize more generally}

multiple fwatuers 1.. d
multiple class    1.. c

$\alpha$ actions instead of gussing which class 1..a

loss function $\lambda(\alpha_i \vert \omega_j)$

vector representation of Baysian eq


---
observe x then action $\alpha_i$ while true class is $\omega_j$

conditional Risk 
\begin{equation}
R(\alpha_i \vert x)= \sum_{j=1}^{c}{\lambda(alpha_i \vert \omega_j) p(\omega_j \vert x)}
\end{equation}

take action so as to minimize this risk

more generally
$\alpha(x)$ corresponds either of $alpha_i$ i=1..a to 
which action to take for every possible observation $\Rightarrow$ bayes desision theory



\clearpage
\noindent
$\bullet$ Example 2.\\
\begin{itemize}
\item[$\cdot$] Three prisoners ({\bf A}, {\bf B}, and {\bf C}) are 
               in a prison.
\item[$\cdot$] {\bf A} knows that the two out of the three are to 
               be executed tomorrow, and the rest becomes free.
\item[$\cdot$] {\bf A} thought either one of {\bf B} or {\bf C} is sure
               to be executed. 
\item[$\cdot$] Then, {\bf A} asked a guard ``even if you tell me
               which of {\bf B} and {\bf C} is executed, that will not give
               me any information as for me. So please tell it to me.'' 
\item[$\cdot$] The guard answers that {\bf C} will. $\Rightarrow$ data $D$
\item[$\cdot$] Now, {\bf A} knows one of {\bf A} or {\bf B} is sure to be
               free.
\end{itemize}

\begin{center} \underline{\hspace*{7in}} \end{center} 
%%\hspace*{1in}\\
\noindent
Do you guess probability $p(A \vert D) = 1/2$?\\
\hspace*{1in}\\
If this is correct, then the answer of the guard had given an information 
as for A, since probability $p(A)=1/3$.\\

\noindent
You agree that
   \begin{displaymath}
   p(A) = p(B) = p(C) = 1/3.
   \end{displaymath}
Then, try to apply Bayesian rule, i.e., obtain the conditional 
probability of the data ``C will be executed'' under the condition that 
``A will be free tomorrow'' And in the same way for B and C. They are:
\begin{eqnarray}
\nonumber
p(D \vert A) &=& 1/2. \\
\nonumber
p(D \vert B) &=& 1.   \\
\nonumber
p(D \vert C) &=& 0.
\end{eqnarray}
In conclusion:
\begin{displaymath}
p(A \vert D)=\frac{p(D \vert A)p(A)}
                  {p(D \vert A)p(A)+p(D \vert B)p(B)+p(D \vert C)p(C)}
=1/3.
\end{displaymath}
This shows probability did not change after the information!

\clearpage
\begin{itemize}
\item Now it's clear that
   \begin{itemize}
   \item $p(A)$ and so on are to be called 
      \begin{itemize} 
      \item[] $\star$ {\it a priori} probabilities;
      \end{itemize}
   \item and $p(A \vert D)$ and so on to be
      \begin{itemize} 
      \item[] $\star$ {\it a posteriori} probabilities.\\
      \end{itemize}
   \end{itemize}
\item In the same way,
   \begin{itemize}
   \item $p(\omega_i)$ is called 
      \begin{itemize} 
      \item[] $\star$ {\it a priori} probability\footnote{Usually given,
but if unknown, it can be estimated as $N_i/N$ where $N_i$
is the number of training samples which belong to class $\omega_i$, 
and $N$ is the total number of training samples};
      \end{itemize}
   \item $p(\omega_i  \vert \mbox{\bf x})$
      \begin{itemize} 
      \item[] $\star$ {\it a posteriori} probabilities.\\
      \end{itemize}
   \end{itemize}
\item[]Furthermore
   \begin{itemize}
   \item $p(\mbox{\bf x})$ is called
      \begin{itemize} 
      \item[] $\star$ p.d.f. of {\bf x}
      \end{itemize}
   \item $p(\mbox{\bf x} \vert \omega_i)$
      \begin{itemize} 
      \item[] $\star$ class-conditional p.d.f.\footnote{This is also
estimated from training data which will be explained later more in detail.}
         \begin{itemize}
         \item which describes the distribution of 
               the feature vectors {\bf x}
               in each of the classes $\omega_i$.
         \end{itemize}
      \end{itemize}
   \end{itemize}
\end{itemize}



%% $\mbox{\bf x}$
%% \mbox{\bf x}
\section{Bayesian decision theory}
Under continuous feature $\mbox{\bf x}$ we have observed,
assume
$c$ finite categories: ${\omega_1, \omega_2, ...\omega_c}$  and
$a$ finite possible actions ${\alpha_1, \alpha_2, ...\alpha_a}$.
Then
a loss function $\lambda(\alpha_i \vert \omega_j)$ is defiened as 
the loss caused by taking an action
$\alpha_i$ when $\omega_j$ is the situation.


\begin{equation}
P(\omega_j \vert \mbox{\bf x}) = \frac{p(\mbox{\bf x} \vert \omega_j)P(\omega_j)}
{p(\mbox{\bf x})}
\end{equation}
where
\begin{equation}
p(\mbox{\bf x}) = \sum_{j=1}^{c}{p(\mbox{\bf x} \vert \omega_j)P(\omega_j)}
\end{equation}
which is called {\it evidence}.

\noindent
Assume we take action $\alpha_i$ when we observe $\mbox{\bf x}$
while the tree situation is $\omega_j$ the loss function
$\lambda(\alpha_i \vert \omega_j)$ will be defiend.
Then expected loss will be 
\begin{equation}
R(\alpha_i \vert \mbox{\bf x}) = \sum_{j=1}^{c}{\lambda(\alpha_i \vert \omega_j)
P(\omega_j \vert \mbox{\bf x})}
\end{equation}
which called a {\it risk}.

\subsection{Two-category classification}
Let's simplify as $\lambda_{ij} = \lambda(\alpha_i \vert \omega_j)$
Then 
\begin{equation}
\nonumber
   R(\alpha_1 \vert \mbox{\bf x}) = \lambda_{11}P(\omega_1 \vert \mbox{\bf x})
      + \lambda_{12}P(\omega_2 \vert \mbox{\bf x})
\end{equation}
\begin{equation}
   R(\alpha_2 \vert \mbox{\bf x}) = \lambda_{21}P(\omega_1 \vert \mbox{\bf x})
      + \lambda_{22}P(\omega_2 \vert \mbox{\bf x})
\end{equation}
Then 
\begin{formula}[Rule for classification]
If $R(\alpha_1 \vert \mbox{\bf x}) < R(\alpha_1 \vert \mbox{\bf x})$
then classify $\mbox{\bf x} to $ $\omega_1$ otherwise to $\omega_2$.
\end{formula}

\subsubsection{likelihood ratio}
If we further assume that we have one feature $x$ instead of multiple $\mbox{\bf x}$,
the if part of the rule above will be
\begin{equation}
(\lambda_{21} - \lambda_{11})P(\omega_1 \vert x) > 
(\lambda_{12} - \lambda_{22})P(\omega_2 \vert x).
\end{equation}
And usually we can assume by definition that $\lambda_{21}>\lambda_{21}>$ and 
$\lambda_{21}>\lambda_{21}>$, the rule will be:
\begin{formula}[Rule for classification]
If the following holds 
\begin{equation}
\frac{p(x \vert \omega_1)}{p(x \vert \omega_2)}
> 
\frac{\lambda_{12} - \lambda_{22}}{\lambda_{21} - \lambda_{11}}\frac{P(\omega_2)}{P(\omega_1)}
\end{equation}
then classify $x$ to $\omega_1$ otherwise to $\omega_2$.
\end{formula}
Note that the left-hand side is a function of $x$ and is called a {\it likelihood ratio}
and the right-hand side is a quantity and is a {\it threshold} to discriminate two classes. 





\subsection{Discriminant function}






\end{document}
%%================================================================================================
