\documentstyle[12pt,eclepsf]{article}

\textheight 260mm
\topmargin -10mm
\textwidth 180mm
\oddsidemargin -7mm

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

\begin{document}
\begin{LARGE}

\begin{center}
\begin{Huge}
\noindent
{\bf Pattern Recognition\footnote{I pick up some of the topics 
           from the following book:
           \begin{itemize}
           \item S. Theodoridis, and K. Koutroumbas (1999)
                 {\it Pattern Recognition.} Academic Press.
            \end{itemize}
especially the chapters that explain ``{\it classifiers 
based on Bayes decision theory}.''
The book is available, for example, at http://www.amazon.com.
However, you do not need to buy since it's not
necessarily easy to understand as it is. I pick up some of the topics
and edited them in my way.}}
\end{Huge}

\vspace{1in}
Dokuz Eyl\"{u}l University \\
Computer Engineering Department \\
19 February 2001 -- 8 June 2001\\
\vspace{1in}
Akira Imada\\
imada@cs.deu.edu.tr
\end{center}


%---------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf Contents:}\\

\begin{itemize}
\item[ 1.] What is {\it Pattern Recognition?}
   \begin{itemize}
   \item[$\star$] Hand-written character recognition as an example.
   \item[$\star$] Feature extraction.
   \end{itemize}
\item[ 2.] {\it Principal Component Analysis (PCA):} 
   \begin{itemize}
   \item[] How many features are enough? 
   \end{itemize}
\item[ 3.] {\it Sammon Mapping:}
   \begin{itemize}
   \item[] What a high-D feature space look like?
   \end{itemize}
\item[ 4.] How can we observe multi-dimensional feature space?
\item[ 5.] To minimize classification error: 
   \begin{itemize}
   \item[] {\it Bayesian Classifier.}
   \end{itemize}
\item[ 6.] Feature Generation by {\it Linear Transforms.}
\end{itemize}

%---------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf What is Pattern Recognition?}\\

\noindent
A typical example:
\begin{itemize}
\item Character recognition:
   \begin{itemize}
   \item[] characters as an example of patterns.\\
   \end{itemize}
\end{itemize}

\noindent
How can we recognize them?

\begin{itemize}
\item By taking all pixels as inputs?
\item By some shape information?
   \begin{itemize}
   \item[]e.g.
      \begin{itemize}
      \item area within boundary;
      \item degree of how boundary curve.
      \end{itemize}
   \end{itemize}
\item[]These are called {\it features}.\\
\end{itemize}

\noindent
Feature space:
\begin{itemize}
\item $l$ features forms {\it feature vector} 
\item[] \hspace*{1in} $\mbox{\bf x} = (x_1, x_2, \cdots, x_l)$
\item[] for each object to be recognized.
\item straight line separates the classes
\item[] \hspace*{1in} $\Downarrow$ in more general
\item[] separation by {\it hyper-plane}\\
\end{itemize}

\noindent
In short:
\begin{itemize}
\item pattern recognition is a {\it classifier}
\end{itemize}

%---------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf Examples of feature to recognize characters:}\\

\begin{itemize}
\item Perimeter:
\end{itemize}
   \begin{equation}
      P = \sum_{i=1}^{N-1} 
            {\| {\mbox{\bf x}}_{i+1} - {\mbox{\bf x}}_{i} \|
            + \| {\mbox{\bf x}}_{N} - {\mbox{\bf x}}_{1} \|}. \\
   \end{equation}
\begin{itemize}
\item Area:
   \begin{itemize}
   \item[] Measure the area enclosed by a boundary 
           by counting the number of pixels. \\
   \end{itemize}
\end{itemize}

\begin{itemize}
\item Roundness ratio: $r=P^2/ 4 \pi A$.
\end{itemize}

\begin{itemize}
\item Number of holes
\end{itemize}

\begin{itemize}
\item Bending energy:
   \begin{itemize}
   \item defined at a point $n$ as
   \begin{equation}
   E(n) = \frac{1}{P} \sum_{i=0}^{n-1} {\vert k_i \vert ^2} \\
   \end{equation}
   \item[] where $k_i$ is  the {\it curvature of the boundary} defined as:
      \begin{equation}
      k_n = \theta_{n+1} - \theta{n}, \hspace{.2in}
      n = 0, 1, \cdots, N-1.
      \end{equation}
   \item[] and
      \begin{equation}
      \theta_n = \tan^{-1} \frac {y_{n+1} - y_{n}}{x_{n+1} - x_{n}}, 
      \hspace{.2in}
      n = 0, 1, \cdots, N-1.
      \end{equation}
   \item[] when we measure the length of the boundary at a point 
              by the number of pixels $n$ between this point and 
              the origin of the curve.
   \end{itemize}
\item Number of corners:
   \begin{itemize}
   \item[] the number of points where the curvature $k_i$ takes 
           large values (infinity in theory)
   \end{itemize}
\end{itemize}

%---------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf Principal Component Analysis (PCA)}
\begin{itemize}
\item[] $\cdots$ A method of dimension reduction.
   \begin{itemize}
   \item[]In the context of Pattern Recognition, a method to reduce
          the number of features without losing efficiency.\\
   \end{itemize}
\end{itemize} 

\noindent
$\bullet$ Two dimensional cases:\\

\noindent
Suppose we have $N$ data pairs:
\begin{equation}
(x_i, y_i) \hspace{.3in} i = 1, 2, \cdots, N
\end{equation}

\noindent
In the context of Pattern Recognition, we have $N$ data with two features.\\

\noindent
Our objective is to find $a$ and $b$ that maximize the variance
of the projections of these $N$ points on the line
\begin{equation}
a(x - \bar{x}) + b(y - \bar{y}) = 0
\end{equation}
\noindent
where $\bar{x}$ and $\bar{y}$ are the average of $x_i$ and $y_i$,
respectively.\\

\noindent
Then 
\begin{equation}
z_i = a x_i + b y_i
\end{equation}
is called {\it principal component} of $x_i$ and $y_i$.\footnote{Yet 
another interpretation of $z_i$ is a weighted sum of $x_i$ and $y_i$.
For example, $x_i$ and $y_i$ are point of homework assignment and 
final exam of student $i$ and $z_i$ is the evaluation.}\\

\noindent
In the context of Pattern Recognition, two features $x_i$ and $y_i$
are said to be reduced to one feature $z_i$.

%---------------------------------------------------------------------
\clearpage
\noindent
Such $(a, b)$ is known to be the {\it eigenvector}\footnote{If
the transform of a vector {\bf x} by a matrix $A$ changes just 
a length of {\bf x} by $\lambda$ then {\bf x} and $\lambda$ are
called {\it eigenvector} and {\it eigenvalue} of the matrix $A$.
} of the matrix:
\begin{eqnarray}
\left(
\begin{array}{ll}
s_{xx} & s_{xy} \\
s_{yx} & s_{yy} \\
\end{array}
\right)
\end{eqnarray}
where $s_{xx}$ and $s_{yy}$ are {\it variance} of $x$ and $y$ respectively
and $s_{xy}=s_{yx}$ are {\it covariance} of $x_i$ and 
$y_i$\footnote{Variance of $x_i$ and covariance of $x_i$ and $y_i$ are 
defined as 
\begin{equation}
\frac{\displaystyle \sum_{i=1}^{N} (x_i - \bar{x})^2}{N}
\hspace{.3in}\mbox{and}\hspace{.3in}
\frac{\displaystyle \sum_{i=1}^{N} (x_i - \bar{x})(y_i - \bar{y})}{N}
\end{equation}
respectively.
}.\\

\noindent
That is,
\begin{equation}
\lambda = \frac
          {s_{xx}+s_{xy}\pm \sqrt{s_{xx}^2+s_{xy}^2+s_{yy}^2-s_{xx}s_{yy}}}
          {2}
\end{equation}
and
\begin{equation}
(a,b) = (\frac
          {s_{xx}-s_{yy}\pm \sqrt{s_{xx}^2+s_{xy}^2+s_{yy}^2-s_{xx}s_{yy}}}
          {2s_{xy}}, 1)\\
\end{equation}

\hspace*{1in}\\
\noindent
$\bullet$ Generalization to $n$-dimensional cases:\\

%---------------------------------------------------------------------
%%%%%%%%%%
\clearpage
\noindent
$\Box$ {\bf Sammon Mapping} (J.\ W.\ Sammon, 1969)\\

\begin{itemize}
\item Assume $N$ points are given in the $n$-D space.\\
\item Calculate distance matrix $R$ ($N \times N$) whose $i$-$j$ element
          is the Euclidean distance between the $i$-th and $j$-th point.\\
\item Also think of a tentative $N$ points in the 2-D space that are
          located at random at the beginning.\\
\item The distance matrix $Q$ is calculated in the same way as $R$.\\
\item Then the error matrix $P=R-Q$ is defined.\\
\item Search for the locations of $N$ points in the 2-D space
          that minimizes the sum of element $P$.\\
\end{itemize}
\noindent
This is an optimization problem which we can solve by GA, that is,\\

\begin{itemize}
\item $N$ points in $n$-D space $\Rightarrow$ $N$ points in 2-D space 
   \begin{itemize}
   \item[]{\it with the distance relation being preserved 
               as much as possible;} or\\
   \end{itemize}
\item The $n$-D distances are approximated by 2-D distances 
   \begin{itemize}
   \item[] {\it with a minimal error.}
   \end{itemize}
\end{itemize}

%---------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf GA Implementation of Sammon Mapping}\\
\begin{figure}[htbp]
 \begin{center}
   \epsfile{file=summon.eps,width=18cm,height=12cm}
 \end{center}
\end{figure}

%---------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf Bayes Decision Theory}\\
\hspace*{2in}--- for the design of classifiers.\\

\begin{itemize}
\item[]Pattern Recognition is more or less statistical due to:
      \begin{itemize}
      \item statistic variation of patterns;
      \item statistic nature of feature selection;
      \item noise in employing sensors.\\
      \end{itemize}
\item[]So, the task is:
   \begin{itemize}
   \item to classify unknown patterns into the {\it most
           probable class.}\\
   \end{itemize}
\item[]Then
   \begin{itemize}
   \item what does ``the most probable'' means?\\
   \end{itemize}
\item[]To answer this question:
   \begin{itemize}
   \item we study here the Bayesian Statistical Theory.
   \end{itemize}
\end{itemize}

%---------------------------------------------------------------------
\clearpage
\begin{itemize}
\item When we classify an unknown pattern which is represented by a feature
vector {\bf x}, we consider $M$ conditional probabilities:
\begin{equation}
p(\omega_i \vert \mbox{\bf x}) \hspace{.2in} i=1, \cdots, M
\end{equation}
\item[]
\item Then we define ``the most probable class'' as the class $\omega_i$ 
      which has the highest $p(\omega_i \vert \mbox{\bf x})$.\\
\item We have the other possible statistical quantities:
   \begin{itemize}
   \item[] \begin{center}
           $p(\omega_i)$, \hspace{.1in}
           $p(\mbox{\bf x} \vert \omega_i )$, \hspace{.1in}
           $p(\mbox{\bf x})$\end{center}
   \end{itemize}
\item[]
\item The {\it Bayesian rule} gives a relationship of these quantities:
   \begin{equation}
   p(\omega_i \vert \mbox{\bf x}) = \frac
   {p(\mbox{\bf x} \vert \omega_i) p(\omega_i)}
   {\displaystyle \sum_{k=1}^M p(\mbox{\bf x} \vert \omega_k) p(\omega_k)}\\
   \end{equation}
\item[]where the denominator is:
   \begin{equation}
   \sum_{k=1}^M p(\mbox{\bf x} \vert \omega_k) p(\omega_k) 
       = p(\mbox{\bf x}).
   \end{equation}
\end{itemize}

%---------------------------------------------------------------------
\clearpage
\noindent
$\bullet$ Example -1:\\
\hspace*{.5in}
 --- to understand the Bayesian Rule
\begin{itemize}
\item[$\cdot$] We have two bags of no difference from its outlook.
\item[$\cdot$] One bag called R has 70 red balls and 30 blue balls.
\item[$\cdot$] The other bag called B has 30 red balls and 70 blue balls.
\item[$\cdot$] When we take one bag at random and pick up 12 balls,
               returning it to the bag at each time.
\item[$\cdot$] The result was 8 red balls and 4 blue one.
\item[$\cdot$] Then was the bag estimated to be R or B, and how probable
               the estimate is?\\
\end{itemize}
\begin{center} \underline{\hspace*{7in}} \\ \end{center}
Clearly,
\begin{displaymath}
p(R)=p(B)=1/2
\end{displaymath}
\begin{eqnarray}
\nonumber
p(D \vert R) &=& _{12}C_{8}(0.7)^8(0.3)^4\\
\nonumber
p(D \vert B) &=& _{12}C_{8}(0.3)^8(0.7)^4
\end{eqnarray}
So we obtain
\begin{displaymath}
p(R \vert D)=\frac{(0.7)^8(0.3)^4}{(0.7)^8(0.3)^4+(0.3)^8(0.7)^4}
\approx 0.97
\end{displaymath}
(How big it is compared to our intuitive estimation!)

\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 the fact 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 
about {\bf A}, since probability $p(A)=1/3$.\\

\noindent
Try to apply Bayesian rule, if you agree
   \begin{displaymath}
   p(A) = p(B) = p(C) = 1/3.
   \end{displaymath}
Then the conditional probabilities of the data, that is, 
``C will be executed'' under the condition that
A, B, and C will be free tomorrow, respectively, are
\begin{eqnarray}
p(D \vert A) &=& 1/2 \\
p(D \vert B) &=& 1   \\
p(D \vert C) &=& 0
\end{eqnarray}

\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}

%---------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf The Bayesian Classifier:}\\

\newtheorem{bayse}{Definition}
\begin{bayse}[The Bayesian Classifier]
classify {\bf x} to the class $\omega_i$ 
such that $p(\omega_i  \vert \mbox{\bf x})$ takes the maximum value.\\
\end{bayse}

\noindent
$\bullet $ Two-class case
\begin{equation}\label{eq:1st-bayes}
\star \hspace{.1in} \mbox{if} \hspace{.1in} 
p(\omega_1  \vert \mbox{\bf x}) > p(\omega_2  \vert \mbox{\bf x}),
\hspace{.2in} \mbox{then classify} \hspace{.1in} {\bf x} 
\hspace{.1in} to \hspace{.1in} \omega_1
\end{equation}
\begin{equation}
\star \hspace{.1in} \mbox{if} \hspace{.1in} 
p(\omega_1  \vert \mbox{\bf x}) < p(\omega_2  \vert \mbox{\bf x}),
\hspace{.2in} \mbox{then classify} \hspace{.1in} {\bf x} 
\hspace{.1in} to \hspace{.1in} \omega_2
\end{equation}

\begin{itemize}
\item[$\cdot$] An example:
   \begin{itemize}
   \item[]If we assume
          $p(\omega_1  \vert \mbox{\bf x})= N(0, 1/2)$,
          $p(\omega_2  \vert \mbox{\bf x})
          = N(1, 1/2)$\footnote{$\displaystyle
          N(\mu, \sigma^2)=\frac{1}{\sqrt{2\pi}\sigma}
          \exp{-\frac{(x-\mu)^2}{2\sigma^2}}$},
          and\hspace{.1in}
          $p(\omega_1) = p(\omega_2) = 1/2$, 
          then how is our classification like?
   \end{itemize}
\end{itemize}

\begin{center}
%%\hspace*{1in}\\
\underline{\hspace*{3in}} \\ 
%%\hspace*{1in}\\
\end{center}

\noindent
The region where 
$p(\omega_1  \vert \mbox{\bf x}) > p(\omega_2  \vert \mbox{\bf x})$
is the region where
\begin{equation}
   \frac{p(\mbox{\bf x} \vert \omega_1) p(\omega_1)}{p(\mbox{\bf x})} >
   \frac{p(\mbox{\bf x} \vert \omega_2) p(\omega_2)}{p(\mbox{\bf x})}
\end{equation}
Since $p(\mbox{\bf x})>0$ and $p(\omega_1)=p(\omega_2)$, the region
is where
\begin{equation}
p(\mbox{\bf x} \vert \omega_1) > p(\mbox{\bf x} \vert \omega_2) 
\end{equation}
holds. Now assume the two Gaussian distribution cross at $x = x_0$, 
we can conclude:
\begin{itemize}
\item[$\star$]if $x<x_0$ then classify {\bf x} to class $\omega_1$,\\
and vice versa. 
\end{itemize}

%---------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf Probability of Misclassification:}\\

\noindent
In the previous example:

\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=two-gaussian.eps,width=16cm,height=10cm}
 \end{center}
\end{figure}

\noindent
$\bullet$ The probability of misclassifying {\bf x} of $\omega_2$
to $\omega_1$ is
\begin{equation}
\displaystyle \int_{-\infty}^{x_0}p(\mbox{\bf x} \vert \omega_2) dx,
\end{equation}
\indent
and the probability of misclassifying {\bf x} of $\omega_1$
to $\omega_2$ is
\begin{equation}
\displaystyle \int_{x_0}^{\infty}p(\mbox{\bf x} \vert \omega_1) dx.
\end{equation}
\indent
Therefore the total error probability is
\begin{equation}\label{p-error}
\displaystyle \int_{-\infty}^{x_0}p(\mbox{\bf x} \vert \omega_2) dx
+ \int_{x_0}^{\infty}p(\mbox{\bf x} \vert \omega_1) dx.
\end{equation}

\hspace*{1in}\\
\noindent
$\bullet$ But usually feature space is multidimensional and so
\begin{equation}
\displaystyle \int_{R_1}p(\mbox{\bf x} \vert \omega_2) d{\bf x}
+ \int_{R_2} p(\mbox{\bf x} \vert \omega_1) d{\bf x}
\end{equation}
\indent
is a more general expression of the equation (\ref{p-error}).

\clearpage
\noindent
$\bullet $ A generalization to $M$-class problem.
\begin{itemize}
\item[--] Assume that
\begin{equation}
R_j: \hspace{.3in} j=1,2, \cdots M.
\end{equation}
\item[]is the region of the feature space assigned to class $\omega_j$.\\
\item[--] Then the probability that a feature vector {\bf x} 
that belongs to $\omega_k$ lies in $R_i \hspace{.1in} (i \ne k)$ 
(i.e., misclassify {\bf x} of $\omega_k$ to $\omega_i$) is:
\begin{equation}
p_e = \sum_{i=1}^M \int_{R_i}p(\mbox{\bf x} \vert \omega_k) d\mbox{\bf x}
\end{equation}
\item[--]But usually, some errors are not so important as others, and 
         $\lambda_{ki}$, importance of the error
where {\bf x} of $\omega_k$ to $\omega_i$ \footnote{In other words,
$\lambda_{ki}$ is a penalty term corresponding to a misclassification of 
{\bf x} that belongs to $\omega_k$ lies in $R_j$}, 
         is weighted as:
\begin{equation}
r_k = \sum_{i=1}^M \lambda_{ki} \cdot
\int_{R_i}p(\mbox{\bf x} \vert \omega_k) d\mbox{\bf x}
\hspace{.1in}\footnote{Here, 
$\int_{R_i}p(\mbox{\bf x} \vert \omega_k) d\mbox{\bf x}$ is the probability 
of a feature vector from $\omega_k$ being classified in $\omega_i$.}
\end{equation}
and the goal is to determine $R_j$ such that
\begin{eqnarray}
\nonumber
r &=& \sum_{i=1}^M r_k \cdot p(\omega_k) \\
  &=& \sum_{i=1}^M \int_{R_i} \sum_{k=1}^M \lambda_{ki} \cdot 
      p(\mbox{\bf x} \vert \omega_k) p(\omega_k) d\mbox{\bf x}
\end{eqnarray}
is minimized.\\
\item[--] This is achieved if each of the integrals is minimized.
\item[]\hfill (to continue)
\clearpage
\item[--] Hence the following formula holds and called 
{\it Likelihood Ratio Test}.\\
\end{itemize}

\newtheorem{liklihood-test}{Test}
\begin{liklihood-test}[The Likelihood Ratio Test]
Assign {\bf x} to $R_i$ if 
\begin{equation}
\sum_{k=1}^M \lambda_{ki} \cdot p(\mbox{\bf x} \vert \omega_k) p(\omega_k) 
<
\sum_{k=1}^M \lambda_{kj} \cdot p(\mbox{\bf x} \vert \omega_k) p(\omega_k) 
\end{equation}
for $\forall j \ne k$.
\end{liklihood-test}

\begin{itemize}
\item[]
\item[--] The two-class ($M=2$) case:
   \begin{itemize}
   \item[$\cdot$] Assign {\bf x} to $\omega_i$ if
\begin{eqnarray}
\nonumber
&&\lambda_{11}p(\mbox{\bf x} \vert \omega_1)p(\omega_1) +
\lambda_{21}p(\mbox{\bf x} \vert \omega_2)p(\omega_2) \\
&<& \lambda_{12}p(\mbox{\bf x} \vert \omega_1)p(\omega_1) +
\lambda_{22}p(\mbox{\bf x} \vert \omega_2)p(\omega_2)
\end{eqnarray}
   \end{itemize}
\item[]That is,
\begin{equation}
(\lambda_{21} - \lambda_{22}) p(\mbox{\bf x} \vert \omega_2)p(\omega_2) <
(\lambda_{11} - \lambda_{11}) p(\mbox{\bf x} \vert \omega_1)p(\omega_1)
\end{equation}
\item[]
\item[] If we assume $\lambda_{ij}>\lambda{ii}$,
   \begin{itemize}
   \item[$\cdot$] Assign {\bf x} to $\omega_i$ if
\begin{equation}
\frac{p(\mbox{\bf x} \vert \omega_1)}{p(\mbox{\bf x} \vert \omega_1)}>
\frac{p(\omega_2)}{p(\omega_1)} \cdot 
\frac{(\lambda_{21} - \lambda_{22})}
     {(\lambda_{12} - \lambda_{11})}
\end{equation}
   \end{itemize}
\item[]\hfill (to continue)
\clearpage
\item[] If two classes are equiprobable $p(\omega_1) = p(\omega_2)$ and
$\lambda_{11}=\lambda_{22}=0$, then 
   \begin{itemize}
   \item[]{\it Assign} {\bf x} {\it to} $\omega_1$ {\it if}
   \end{itemize}
\begin{equation}
p(\mbox{\bf x}\vert \omega_1) > p(\mbox{\bf x}\vert \omega_2)\cdot
\frac{\lambda_{21}}{\lambda_{12}}
\end{equation}
\item[]
\item[]Furthermore if the importance of two misclassification is 
          the same,
that is, $\lambda_{12}=\lambda_{21}=1$, then
\begin{equation}
p(\mbox{\bf x}\vert \omega_1) > p(\mbox{\bf x}\vert \omega_2)
\end{equation}
\item[]
\item[]This is equivalent of the equation (\ref{eq:1st-bayes}).
\end{itemize}

%---------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf Decision Surfaces and Discriminant Functions:}\\
\hspace*{.5in}
 --- to partition the feature space into $M$ regions.\\
\begin{itemize}
\item If regions $R_i$ and $R_j$ are contiguous
\begin{equation}
p(\omega_i \vert \mbox{\bf x}) - p(\omega_j \vert \mbox{\bf x}) = 0
\end{equation}
determines the surface that partition $R_i$ and $R_j$,\\
\item Or, if necessary, 
      using a monotonic function $f(x)$\footnote{e.g., $f(x)=\ln(x)$ for 
      the Gaussian distribution.}, we define:
      \begin{equation}\label{logarithm}
      g_i(x)= f(p(\omega_i \vert \mbox{\bf x}))
      \end{equation}
      and we can say 
      \begin{equation}
      \star \mbox{if}\hspace{.1in} g_i(x)>g_j(x) \hspace{.1in} 
      \mbox{for} \hspace{.1in} \forall j \ne i,
      \mbox{classify {\bf x} to} \hspace{.1in} \omega_i.
      \end{equation}
      Hence
      \begin{equation}
      g_{ij} \equiv g_i(\mbox{\bf x}) - g_j(\mbox{\bf x}) = 0
      \end{equation}
      determines the {\it decision surfaces} separating contiguous regions 
      and called {\it discriminant function.}
\end{itemize}

%---------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf Bayesian Classification for 2-d Gaussian pdf:}\\

\noindent
$\bullet$ $l$-dimensional Gaussian distribution
\begin{equation}\label{l-d-gauss}
p(\mbox{\bf x}) = \frac{1}{(2 \pi)^{l/2} \vert \Sigma \vert ^{1/2}}
\exp(-\frac{1}{2} 
(\mbox{\bf x} - {\bf \mu})^T \Sigma ^{-1}(\mbox{\bf x} - {\bf \mu})
\end{equation}
\noindent
where
\begin{eqnarray}
\cdot \Sigma = \left(
\begin{array}{cccc}
\sigma_1^2    & \sigma_{12}   & \cdots & \sigma_{1l}  \\
\sigma_{21}   & \sigma_2^2    & \cdots & \sigma_{2l}  \\
\hspace{.1in} & \hspace{.1in} & \cdots & \hspace{.1in}\\
\sigma_{l1}   & \sigma_{l2}   & \cdots & \sigma_l^2
\end{array}
\right)
\end{eqnarray} 
\begin{itemize}
\item[$\cdot$] {\bf x} = $(x_1, x_2, \cdots, x_l)$;
\item[$\cdot$] $\mu$ is a $l$-dimensional vector whose $i$-th
                element $\mu_i$ is the mean value of $x_i$;
\item[$\cdot$] $\sigma_i^2$ is the variance of $x_i$;
\item[$\cdot$] $\sigma_{ij}$ is the covariance between $x_i$ and $x_j$;
\item[$\cdot$] $\vert \Sigma \vert$ is determinant of the matrix $\Sigma$;
\item[$\cdot$] $\Sigma^{-1}$ is inverse  matrix of $\Sigma$\footnote{If 
we assume
\begin{eqnarray}
A = \left(
\begin{array}{cc}
a & b \\
c & d
\end{array}
\right)
\end{eqnarray}
then
\begin{equation}
\vert A \vert = ad - bc
\end{equation}
and 
\begin{eqnarray}
A^{-1} = \frac{1}{ad - bc} \left(
\begin{array}{rr}
d  & -b \\
-c &  a
\end{array}
\right)
\end{eqnarray}
};
\item[$\cdot$] $\mbox{\bf x}^T$ is 
transverse of vector {\bf x}\footnote{That is, 
when {\bf x} = $(x_1, x_2)$
\begin{eqnarray}
\mbox{\bf x}^T =  \left(
\begin{array}{c}
x_1  \\
x_2
\end{array}
\right)
\end{eqnarray}
}.
\end{itemize}

\noindent
$\bullet$ 2-dimensional Gaussian\\
\hspace*{1in}\\
\noindent
We can calculate $l=2$ version from the equation (\ref{l-d-gauss}) as:\\

\begin{eqnarray}\label{2-d-gauss}
\nonumber
p(x_1&,& x_2) = \frac{1}{2 \pi \sigma_1 \sigma_2 \sqrt{1-\rho^2}}\cdot
     \exp \{(-\frac{1}{2(1-\rho^2)} \cdot\\
\nonumber
     && \Biggl((\frac{x_1 - \mu_1}{\sigma_1})^2
       - 2 \rho(\frac{x_1 - \mu_1}{\sigma_1})(\frac{x_2 - \mu_2}{\sigma_2})
+(\frac{x_2 - \mu_2}{\sigma_2})^2
\Biggr)\}\\
\end{eqnarray}

\noindent
where $\rho$ is correlation coefficient defined as:
\begin{equation}
\rho = \frac{\sigma_{12}}{\sigma_1 \sigma_2}
\end{equation}

\hspace*{1in}\\
\begin{center} \underline{\hspace*{7in}} \\ \end{center}
\hspace*{1in}\\

\begin{itemize}
\item[] {\bf Exercise 1:} 
   \begin{itemize}
   \item[1.] Derive the equation (\ref{2-d-gauss}) from 
             the equation (\ref{l-d-gauss}).
   \item[2.] By giving your own set of five parameters:\\
             \hspace*{1in}
             $\mu_1$, $\mu_2$, $\sigma_1$, $\sigma_2$, and $\sigma_{12}$\\
             Draw the Gaussian surface on $(x_1, x_2)$ coordinate. 
             Then explore a couple of configurations of these five 
             parameters.
   \end{itemize}
\end{itemize}

\begin{figure}[h]
 \begin{center}
   \epsfile{file=2-d-gaussian.eps,width=16cm,height=10cm}
 \end{center}
\end{figure}

%---------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf Examples of Decision Surface in 2D Feature Space:}\\

\noindent
The equation (\ref{2-d-gauss}) with taking the function {\it ln} 
as $f(\cdot)$ in the equation (\ref{logarithm}), we obtain our 
discriminating function $g_i$ as:

\begin{eqnarray}\label{eq:discriminant}
\nonumber
g_i(\mbox{\bf x}) 
 &=& \ln (p(\mbox{\bf x} \vert \omega_i)p(\omega_i))\\
\nonumber
 && \hspace*{1in}\\
\nonumber
 &=& \ln p(\mbox{\bf x} \vert \omega_i) + \ln p(\omega_i)\\
\nonumber
 && \hspace*{1in}\\
\nonumber
 &=& - \frac{1}{2} (\mbox{\bf x}-\mu_i)^T
            \Sigma_i^{-1}(\mbox{\bf x}-\mu_i) + \ln p(\omega_i) + c_i\\
\nonumber
 && \hspace*{1in}\\
\nonumber
 &=& -\frac{1}{2} \mbox{\bf x}^T \Sigma_i^{-1}\mbox{\bf x}
     +\frac{1}{2} \mbox{\bf x}^T \Sigma_i^{-1}\mu_i
     -\frac{1}{2} \mu_i^T \Sigma_i^{-1}\mu_i\\
\nonumber
  && \hspace{1in} +\frac{1}{2} \mu_i^T \Sigma_i^{-1}\mbox{\bf x}
     + \ln p(\omega_i) + c_i\\
\end{eqnarray}
\noindent
where
\begin{equation}
c_i = - (l/2)\ln (2\pi) - (1/2) \ln \vert \Sigma_i \vert
\end{equation}

\clearpage
\noindent
$\bullet$ {\bf Example 1}\\

\noindent
When
\begin{eqnarray}
\nonumber
\Sigma_i =
\left(
\begin{array}{cc}
\sigma_i^2 & 0          \\
0          & \sigma_i^2 \\
\end{array}
\right)
\end{eqnarray}

\begin{equation}
g_i = \frac{x_1^2+x_2^2}{-2\sigma_i^2}
+\frac{\mu_{i1}x_1+\mu_{i2}x_2}{\sigma_i^2}
-\frac{\mu_{i1}^2+\mu_{i2}^2}{-2\sigma_i^2}
+ \ln p(\omega_i) + c_i \\
\end{equation}

\hspace*{1in}\\
\begin{itemize}
\item[$\star$] Hence, under this kind of two distributions, 
               the decision surface is a {\it circle}. \\
\end{itemize}

\clearpage
\noindent
$\bullet$ {\bf Example 2}\\

\noindent
When
\begin{eqnarray}
\nonumber
\Sigma_i =
\left(
\begin{array}{cc}
\sigma_{i1}^2 & 0             \\
0             & \sigma_{i2}^2 \\
\end{array}
\right)
\end{eqnarray}

\begin{eqnarray}
\nonumber
g_i = \frac{\sigma_{i2}^2x_1^2+\sigma_{i1}^2x_2^2}
           {-2\sigma_{i1}^2\sigma_{i2}^2}
&+& \frac{\sigma_{i2}^2\mu_{i1}x_1+\sigma_{i1}^2\mu_{i2}x_2}
       {\sigma_{i1}^2\sigma_{i2}^2}\\
&-& \frac{\sigma_{i2}^2\mu_{i1}^2 + \sigma_{i1}^2\mu_{i2}^2}
       {-2\sigma_{i1}^2\sigma_{i2}^2}
+ \ln p(\omega_i) + c_i
\end{eqnarray}

\hspace*{1in}\\
\begin{itemize}
\item[$\star$] This kind of two distributions construct a {\it quadratic}
               decision surface.
\item[$\star$] If expanded to $l>2$ case, then it is called 
               {\it hyper-quadratic}. \\
\end{itemize}

\hspace*{1in}\\
\noindent
$\bullet$ {\bf Exercise 2:}\\

\noindent
When $p(\omega_1)=p(\omega_2)$, $\mu_1=(0, 0)$, and $\mu_2=(1, 0)$,
obtain decision surface in the following two cases.

\begin{eqnarray}
\nonumber
(1) \hspace{.2in}\Sigma_1 =
\left(
\begin{array}{cc}
0.10 & 0             \\
0    & 0.15
\end{array}
\right),
\hspace{.5in}\Sigma_2 =
\left(
\begin{array}{cc}
0.20 & 0             \\
0    & 0.25
\end{array}
\right)
\end{eqnarray}

\begin{eqnarray}
\nonumber
(2) \hspace{.2in}\Sigma_1 =
\left(
\begin{array}{cc}
0.10 & 0             \\
0    & 0.15
\end{array}
\right),
\hspace{.5in}\Sigma_2 =
\left(
\begin{array}{cc}
0.15 & 0             \\
0    & 0.10
\end{array}
\right)
\end{eqnarray}


%---------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf An expansion to $l$-D Feature space:}\\

\noindent
Our discriminant function now is 
the equation (\ref{eq:discriminant}), i.e.,\\
\begin{eqnarray}
\nonumber
g_i
 &=& -\frac{1}{2} \mbox{\bf x}^T \Sigma_i^{-1}\mbox{\bf x}
     +\frac{1}{2} \mbox{\bf x}^T \Sigma_i^{-1}\mu_i
     -\frac{1}{2} \mu_i^T \Sigma_i^{-1}\mu_i\\
\nonumber
  && \hspace{2in} +\frac{1}{2} \mu_i^T \Sigma_i^{-1}\mbox{\bf x}
     + \ln p(\omega_i) + c_i \\
\end{eqnarray}

\hspace*{1in}\\
\noindent
We have discussed that this  gives a {\it quadratic} decision surface.\\

\hspace*{1in}\\
\noindent
But if we assume here:\\

\begin{equation}
\forall \Sigma_i = \Sigma \\
\end{equation}

\hspace*{1in}\\
\noindent
That is, all the variance matrices are identical, then the first 
and the last term do not contribute to $g_i-g_j$, 
and we can re-define $g_i$ as: \\

\begin{equation}\label{eq:new-decision-function}
g_i =  \frac{1}{2} \mbox{\bf x}^T \Sigma_i^{-1}\mu_i
      +\frac{1}{2} \mu_i^T \Sigma_i^{-1}\mbox{\bf x}
      -\frac{1}{2} \mu_i^T \Sigma_i^{-1}\mu_i\\
      +\ln p(\omega_i)
\end{equation}

\clearpage
\hspace*{1in}\\
\noindent
And we can simplify the equation (\ref{eq:new-decision-function}) 
as:\footnote{Since $w_i^T=\Sigma^{-1}\mu_i$ and $\Sigma$ is symmetric,  
we obtain 
$w_i^T = \mu_i^T(\Sigma^{-1})^T = \mu_i^T(\Sigma^T)^{-1} 
       = \mu_i^T \Sigma^{-1}$.
And we conclude:
\begin{displaymath}
\frac{1}{2}\mbox{\bf x}^Tw_i + \frac{1}{2}w_i^T \mbox{\bf x} 
= w_i^T \mbox{\bf x}.
\end{displaymath}
Note that $\mbox{\bf x}^T$ is a raw vector and $w_i$  is a column vector.
Hence, $\mbox{\bf x}^T w_i = w_i^T\mbox{\bf x}$ holds.
}\\

\begin{equation}
g_i = w_i^T {\mbox{\bf x}} + w_{i0} \\
\end{equation}

\hspace*{1in}\\
\noindent
by putting\\

\begin{equation}
w_i = \Sigma^{-1}\mu_i  \\
\end{equation}

\noindent
and \\

\begin{equation}
w_{i0} = \ln p(\omega_i) - \frac{1}{2}\mu_i^T \Sigma_i^{-1}\mu_i\\
\end{equation}

\hspace*{1in}\\
\noindent
Hence our new $g_i$ is a linear function of {\bf x} and the decision
surfaces determined by $g_i - g_j = 0$ are {\it hyper-planes} instead
of the previous {\it quadratic} surfaces.    

%---------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf Further two assumptions for simplification:}\\

$\bullet$ When $\Sigma = \sigma^2 I$:

\begin{eqnarray}
\nonumber
g_i - g_j  &=&  (\frac{1}{\sigma^2}\mu_i^T \mbox{\bf x} + w_{i0})
              - (\frac{1}{\sigma^2}\mu_j^T \mbox{\bf x} + w_{j0}) \\
\nonumber
           & &   \hspace*{1in}\\
           &=&   \frac{1}{\sigma^2}(\mu_i^T - \mu_j^T)\mbox{\bf x} 
              + w_{i0} - w_{j0} \\
\nonumber
\end{eqnarray}

Here, we put\\

\begin{equation}
w^T = \mu_i^T - \mu_i^T \\
\end{equation}

Then,\\

\begin{eqnarray}\label{eq:new-new-discriminate}
\nonumber
\sigma^2 (g_i - g_j) &=& w^T \mbox{\bf x} + \sigma^2 (w_{i0} - w_{j0}) \\
\nonumber
                     &=& \cdots \mbox{\large (see next page!)} \\
                     &=& w^T (\mbox{\bf x} - {\mbox{\bf x}}_0) \\
\nonumber
\end{eqnarray}

where\\

\begin{equation}
x_0 = - \frac{1}{2}(\mu_i + \mu_j) - \sigma^2 \cdot
        \ln \{ \frac{p(\omega_i)}{p(\omega_i)} \} \cdot
        \frac{\mu_i - \mu_j}{\|\mu_i - \mu_j \|^2}
\end{equation}

\clearpage
\hspace*{1in}\\
\begin{large}
In equation (\ref{eq:new-new-discriminate})
\begin{eqnarray}
\nonumber
\sigma^2(w_{i0} - w_{i0})
&=&   \sigma^2 \Biggr( \ln p(\omega_i) - \frac{1}{2}\frac{1}{\sigma^2}
      \mu_i^T \mu_i \Biggr)
    - \sigma^2 \Biggr( \ln p(\omega_j) - \frac{1}{2}\frac{1}{\sigma^2}
      \mu_j^T \mu_j \Biggr)\\
\nonumber
&=&   \sigma^2 \Biggr( (\ln p(\omega_i) - \ln p(\omega_j)) 
    - \frac{1}{2} (\mu_i^T \mu_i - \mu_j^T \mu_j) \Biggl) \\
\nonumber
&=&   \sigma^2 \ln \frac{p(\omega_i)}{p(\omega_j)} 
    - \frac{1}{2}(\| \mu_i \|^2 - \|\mu_j \|^2) \\
\nonumber
&=&   (\mu_i - \mu_j)^T 
    - \sigma^2 \cdot \ln \frac{p(\omega_i)}{p(\omega_j)} \cdot 
      \frac{(\mu_i - \mu_j)^T (\mu_i - \mu_j)}
           {(\mu_i - \mu_j)^T (\mu_i - \mu_j)} \\
\nonumber
&=&   (\mu_i - \mu_j)^T \Biggl(-\frac{1}{2}(\mu_i + \mu_j)
    - \sigma^2 \cdot \ln \frac{p(\omega_i)}{p(\omega_j)} \cdot 
      \frac{\mu_i - \mu_j}{ \| \mu_i - \mu_j \| ^2 } \Biggr) \\
&\equiv& w^T {\mbox{\bf x}}_0 \\
\nonumber
\end{eqnarray}

Hence, from \\
\begin{equation}
\sigma^2(g_i - g_j) = w^T (\mbox{\bf x} - {\mbox{\bf x}}_0)  = 0\\
\end{equation}

\hspace*{1in}\\
\indent
we can conclude:\\

\begin{equation}
\sigma^2 (\mu_i - \mu_j)^T (\mbox{\bf x} - {\mbox{\bf x}}_0)  = 0
\end{equation}
\end{large}

\begin{center} \underline{\hspace*{7in}} \\ \end{center}

\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=hyper-plane.eps,width=6cm,height=6cm}
 \end{center}
\end{figure}

\hspace*{1in}\\
\begin{itemize}
\item[-] The point $\mbox{\bf x}_0$ is on the vector $(\mu_i - \mu_j)$ and 
         the location depends on $\sigma^2$ and 
         $p(\omega_i)/p(\omega_j)$, that is,\\
   \begin{itemize}
   \item[$\cdot$] If $p(\omega_i) > p(\omega_j)$, then the hyper-plane 
                  is located closer to $\mu_i$.\\
   \item[$\cdot$] If $\sigma^2$ is small w.r.t. $\|\mu_i - \mu_j \|$, then
                  the location of the hyper-plane is insensitive.
   \end{itemize}
\end{itemize}

\clearpage
\hspace*{1in}\\
$\bullet$ Non-diagonal Covariance Matrix $\Sigma$ \\

\begin{itemize}
\item[-] As in the previous assumption we obtain:\\
\begin{equation}
g_i - g_j = w^T (\mbox{\bf x} - {\mbox{\bf x}}_0) \\
\end{equation}
\item[]
\item[]where \\
\begin{equation}
w^T = \mu_i^T - \mu_i^T \\
\end{equation}
\item[]
\item[]and \\
\begin{equation}
x_0 = - \frac{1}{2}(\mu_i + \mu_j) - \sigma^2 \cdot
        \ln \{ \frac{p(\omega_i)}{p(\omega_i)} \} \cdot
        \frac{\mu_i - \mu_j}{\|\mu_i - \mu_j \|^2 _{\Sigma^{-1}}}\\
\end{equation}
\item[]
\item[-] Here, we refer
$
\|\mbox{\bf x} \|_{\Sigma^{-1}} \equiv 
(\mbox{\bf x}^T \Sigma^{-1}\mbox{\bf x})
$
to $\Sigma^{-1}$ {\it norm} of {\bf x}. 
\item[]
\item[-] The decision hyper-plane is no longer orthogonal to 
         $\mu_i - \mu_j$ but to its linear transformation
         $\Sigma^{-1}(\mu_i - \mu_j)$.\\



\item[$\cdot$]Under {\it non-diagonal} $\Sigma$, the $\Sigma^{-1}$ norm
\end{itemize}

%---------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf Classification by the distance from the mean:}\\

\noindent
Recall that we classify {\bf x} to $\omega_i$ such that $g_i$ 
is maximized, \\

\begin{itemize}
\item[]\hspace*{.5in}$\Downarrow$ then it implies\\
\item for diagonal $\Sigma = \sigma^2 I$, minimize
\begin{equation}
d_E \equiv \| \mbox{\bf x} - \mu_i \| 
\end{equation}
\item for no-diagonal $\Sigma$, minimize
\begin{equation}\label{eq:mahalanobis}
d_M \equiv  (\mbox{\bf x} - \mu_i)^T \Sigma^{-1}(\mbox{\bf x} - \mu_i)
\end{equation}
\item[] which is called {\it Mahalanobis distance.}
\end{itemize}

\begin{center} \underline{\hspace*{7in}} \\ \end{center}

Note that: 
\begin{itemize}
\item $d_E={\large const.}$ $\Rightarrow$ {\it hyper-sphere}
\item $d_M={\large const.}$ $\Rightarrow$ {\it hyper-ellipse}
\end{itemize}

%---------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf Diagonalization of Variance Matrix:}\\

\hspace*{1in}
--- to learn the shape of the ellipses\\

\noindent
$\Sigma$ can be diagonalized by a {\it unitary transform} $\Phi$ as:\\

\begin{equation}\label{eq:diagonal}
\Sigma = \Phi^{-1} \Lambda \Phi.
\end{equation}

\hspace*{1in}\\
\noindent
where $\Phi^T = \Phi^{-1}$ because $\Phi$ is unitary, and $\Lambda$
is the diagonal matrix whose elements are the eigenvalues of $\Sigma$.
$\Phi$ has eigenvectors of $\Sigma$ as its column, that is,

\begin{equation}
\Phi = (\nu_1 \nu_2 \cdots \nu_l).
\end{equation}

\hspace*{1in}\\
\noindent
From (\ref{eq:mahalanobis}) and (\ref{eq:diagonal}), 
our hyper-ellipse becomes

\begin{equation}\label{eq:our-ellipse}
(\mbox{\bf x}-\mu_i)^T \Phi^{-1}\Lambda \Phi (\mbox{\bf x}-\mu_i) = 
{\large const.}
\end{equation}

\hspace*{1in}\\
\noindent
If we define $\mbox{\bf x}^{\prime} = \Phi \mbox{\bf x}$ here, 

\begin{equation}
\mbox{\bf x}^{\prime} = \nu_k^T \mbox{\bf x}
\end{equation}

\hspace*{1in}\\
\noindent
implies the {\it projections} of {\bf x} onto each eigenvector, and 
(\ref{eq:our-ellipse}) becomes our familiar hyper-ellipse formula:

\begin{equation}
\frac{(x_1^{\prime}-\mu^{\prime}_{i1})}{\lambda_1}+
\frac{(x_2^{\prime}-\mu^{\prime}_{i2})}{\lambda_2}+ \cdots +
\frac{(x_l^{\prime}-\mu^{\prime}_{il})}{\lambda_l} = \mbox{\large const.}
\end{equation}

\clearpage
\hspace*{1in}\\
\noindent
Thus, all points having the same Mahalanobis distance from 
a specific point are located on an ellipse.

\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=ellipse.eps,width=6cm,height=6cm}
 \end{center}
\end{figure}


\clearpage
\hspace*{1in}\\
\noindent
$\bullet$ {\bf Exercise 3:}\\

\noindent
About a two-class, two dimensional Bayesian classifier where 
$p(\omega_1)=p(\omega_2)$, $\mu_1=(0, 0)$, $\mu_2=(1, 0)$, and
\begin{eqnarray}
\nonumber
\Sigma_1 = \Sigma_2 = \Sigma =
\left(
\begin{array}{cc}
1.1 & 0.3             \\
0.3 & 1.9
\end{array}
\right)
\end{eqnarray}
calculate the followings.

\begin{itemize}
\item[(1)] Obtain $d_M$ of $\mbox{\bf x}=(1.0, 2.2)$ from 
           $\mu_1$ and $\mu_2$, respectively.\\
\item[(2)] Should {\bf x} classified to $\omega_1$ or $\omega_2$? \\
           (Compare the result when we use $d_E$ instead of $d_M$.\\
\item[(3)] Obtain the ellipse when we suppose {\it const.}~= 1.\\
\begin{displaymath}
(\mbox{\bf x}-\mu_i)^T\Sigma^{-1}(\mbox{\bf x}-\mu_i) = 1,
\hspace{.2in} i=1, 2.\\
\end{displaymath}
\item[(4)] Calculate eigenvalues $\lambda_1$ and $\lambda_2$,
           and eigenvectors $\nu_1$ and $\nu_2$ of $\Sigma$.\\
\item[(5)] Obtain $\Phi$ and $\Lambda$ and ascertain 
           $\Sigma = \Phi^{-1}\Lambda \Phi$.\\
\item[(6)] Obtain the projected ellipse
\begin{displaymath}
(\mbox{\bf x}-\mu_i)^T\Phi^{-1} \Lambda \Phi (\mbox{\bf x}-\mu_i) = 1,
\hspace{.2in} i=1, 2.
\end{displaymath}
\end{itemize}

%---------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf What to do with unknow pdf?}\\

\noindent
So far we have studied known pdf $p(\mbox{\bf x}\vert \omega_i)$
with its known parameter which is not of usual case.\\

\noindent
Usually,
\begin{itemize}
\item[$\cdot$]Pdf is known but some parameters are unknown; or
\item[$\cdot$]underlying pdf should be estimated from the available data.
\end{itemize}

%---------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf Non-parametric pdf Estimation}\\
\hspace*{.5in}
 --- Histogram approximation of unknown pdf.\\
\begin{itemize}
\item 2-D case:
   \begin{itemize}
   \item[(1)]x-axis is divided into successive {\it bins} of length $h$.
   \item[(2)]If $N$ is the total number of samples and $k_N$ of them are
             located inside a bin then pdf is approximated by
\begin{equation}
p(x) \equiv p(\hat{x}) \approx \frac{1}{h}\frac{k_N}{N}
\end{equation}  
   \item[]for
\begin{equation}
\vert x - \hat{x} \vert \le \frac{h}{2}
\end{equation}
   \end{itemize}
\item[]
\item $l$-D case:
   \item[]In the same way as 2-D case, $l$-dimensional space is divided 
          into hypercubes with length of side $h$ whose volume is $h^l$.
   \begin{itemize}
   \item[-] Assume we have $N$ feature vectors:
\begin{equation}
\mbox{\bf x}_i = (x_{i1}, x_{i2}, \cdots, x_{il}), \hspace{.2in}
i = 1, 2, \cdots, N.
\end{equation}
   \item[] and a function $\phi(\mbox{\bf x}_i)$:
\begin{eqnarray}
\phi(\mbox{\bf x}_i) = \left\{
\begin{array}{ll}
1 & \hspace{.2in} \mbox{for} \hspace{.2in} \vert x_{ij} \vert \le 1/2 \\
0 & \hspace{.2in} \mbox{otherwise}.\\
\end{array}
\right.
\end{eqnarray}
   \item[] This is referred to as {\it Parzen Windows}
   \item[]\hfill (to continue)
\clearpage
   \item[]Then 
\begin{equation}
p(\mbox{\bf x}) \equiv p(\mbox{\bf x}_i) \approx \frac{1}{h^l} \Biggl(
\frac{1}{N} \sum_{i=1}^N 
\phi (\frac{\mbox{\bf x}_i - \mbox{\bf x}}{h}) \Biggr)
\end{equation}
   \item[] in which $\sum \phi(\cdot)$ implies the number of points 
           falling inside the hypercube with length of side $h$ 
           centered at $\mbox{\bf x}_i$, the point where the pdf
           is to be estimated, that is to say, $\sum \phi = k_N$.
           In short:
\begin{equation}
p(\mbox{\bf x}) \approx \frac{1}{h^l} \Biggl( \frac{k_N}{N} \Biggr)  
\end{equation}
   \item[-] How to determine $h$ and $N$.
      \begin{itemize}
      \item[$h$:] starting with a certain $h$, modify it iteratively to 
                  minimize misclassification error. (typically ranging from 
                  0.1 to 0.8)
      \item[$N$:] If $N$ is appropriate for the 2-D version, the $n$-D 
                  version needs $N^n$ samples.\\
      \end{itemize}
   \end{itemize}
\item The likelihood ratio test using the Parzen Windows:
   \begin{itemize}
   \item[]{\it Assign} {\bf x} {\it to} $\omega_1$ {\it if}
   \end{itemize}
\begin{equation}
\frac
{\frac{1}{N_1 h^l}\sum_{i=1}^{N_1}
\phi (\frac{\mbox{\bf x}_1 - \mbox{\bf x}}{h})}
{\frac{1}{N_2 h^l}\sum_{i=1}^{N_2}
\phi (\frac{\mbox{\bf x}_2 - \mbox{\bf x}}{h})}
> \frac{p(\omega_2)}{p(\omega_1)}\cdot 
  \frac{(\lambda_{21}-\lambda_{22})}{(\lambda_{12}-\lambda_{11})}
\end{equation}
\end{itemize}

%---------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf k Nearest Neighbor Density Estimation (kNN)}\\

\noindent
While in the Parzen windows $h$ is fixed, here in kNN it is $k_N$ 
that is fixed.

\begin{itemize}
\item k Nearest Neighbor pdf:
   \begin{itemize}
   \item[] When the volume of the hypercube\footnote{Instead of hypercube,
           we might compute its Euclidean distance from all the training 
           vectors of the different classes, that is, compute radius of the 
           hypersphere centered at {\bf x} that contains $k$ points from 
           $\omega_i$. Then $V(\mbox{\bf x})$ is the volume of the 
           hypersphere.} around the point {\bf x},
           which includes $k_N = k$ (fixed) out of a total of $N$ samples, 
           is $V(\mbox{\bf x})$ then the pdf is estimated as:
\begin{equation}
p(\mbox{\bf x}) = \frac{k}{N V(\mbox{\bf x})}
\end{equation}
   \item[] Note that the lower the density of samples the larger the
           volume $V$ , and vice versa.\\
   \end{itemize}
\item The likelihood ratio test:
   \begin{itemize}
   \item[]{\it Assign} {\bf x} {\it to} $\omega_1$ {\it if}
   \end{itemize}
\begin{equation}
\frac{N_2 V_2}{N_1 V_1}
> \frac{p(\omega_2)}{p(\omega_1)}\cdot 
  \frac{(\lambda_{21}-\lambda_{22})}{(\lambda_{12}-\lambda_{11})}
\end{equation}
\end{itemize}

%---------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf The Nearest Neighbor Density Estimation (k=1)}\\

\newtheorem{nearest-neighbor}{Algorithm}
\begin{nearest-neighbor}[The k Nearest Neighbor]
Given an unknown feature vector {\bf x} and a distance measure like 
Euclidean or Mahalanobis distance:
\begin{itemize}
\item[1.]Out of the $N$ training vectors, identify the $k$ 
         (an odd integer) nearest neighbors, irrespective of class.
\item[2.]Out of these $k$ samples, identify the number of vectors $k_i$ 
         that belong to class $\omega_i$ $i=1,2,\cdots M$. $(\sum k_i = k)$.
\item[3.]Assign {\bf x} to $\omega_i$ with the maximum $k_i$.
\end{itemize}
\end{nearest-neighbor}

\hspace*{1in}\\

\begin{itemize}
\item The simplest version is when $k=1$. This called Nearest Neighbor 
      Algorithm (NN). Then:
   \begin{itemize}
   \item[] {\bf x} {\it is assigned to its nearest neighbor class.}\\
   \end{itemize} 
\item kNN is no more the Bayesian classification but
\begin{equation}
P_B \le P_{NN} \le P_B(2 - \frac{M}{M-1} P_B) < 2 P_B
\end{equation}
\begin{equation}
P_B < P_{kNN} \le P_B + \sqrt{\frac{2P_{NN}}{k}}
\end{equation}
\item[]are known, where $P_B$ and $P_{kNN}$ is 
misclassification error probabilities
of Bayesian and kNN classifier, respectively.
\item[]\hfill (to continue)
\clearpage
\item[]And when $P_B \ll 1$, we obtain that
\begin{equation}
P_{NN} \approx 2 P_B
\end{equation}
\item[] and
\begin{equation}
P_{3NN} \approx P_B + 3 P_B^2
\end{equation}
\item[]
\item[]When $P_B = 0.01$, for example, 
\begin{equation}
P_{3NN} - P_B \approx  0.00003
\end{equation}
\item[] Further, as $k$ becomes large, 
kNN tends to the Bayesian classifier.
\end{itemize} 

\hspace*{1in}\\
\newtheorem{voronoi}{Definition}
\begin{voronoi}[Voronoi Tesselation]
When $k=1$, $N$ training vectors 
$\mbox{\bf x}_i \hspace{.2in} (i=1,2,\cdots, N$) 
define a partition of the $l$-D feature space into $N$ regions:
\begin{equation}
R_i = \{ \mbox{\bf x} \vert d(\mbox{\bf x}, \mbox{\bf x}_i)
< d(\mbox{\bf x}, \mbox{\bf x}_j) \} \hspace{.2in} i \ne j.
\end{equation}
$R_i$ contains all points that are closer to $\mbox{\bf x}_i$ than 
any other point.
\end{voronoi}

%---------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf Thought Experiments}\\

\begin{itemize}
\item You have (one dimensional) 100 positive valued training samples 
created following\footnote{This is the Rayleigh pdf defined as
\begin{equation}
p(x)= \frac{x}{\sigma^2} \exp (- \frac{x^2}{2 \sigma^2}.)
\end{equation}}:
\begin{equation}
p(\mbox{\bf x}\vert \omega_1) = x \exp (-x^2/2)
\end{equation}
and the other 100 following
\begin{equation}
p(\mbox{\bf x}\vert \omega_2) = 2x \exp (-x^2)
\end{equation}
but you don't know both of the function from which data are created.
   \begin{itemize}
   \item[(1)] Classify a feature vector {\bf x} produced at random.
   \item[(2)] For each set of 100 data, observe the histogram with
              various value of $h$. 
   \item[(3)] Observe the histograms by changing $N_1$ and $N_2$ from
              10 to 1000.\\
   \end{itemize}
\clearpage
\item For two sets of (2-dimensional) 100 data each drawn from
\begin{equation}
p(\mbox{\bf x}\vert \omega_1) = \frac{1}{2\pi}
\exp \Biggl( -(\mbox{\bf x} - \mu_1)^T(\mbox{\bf x} - \mu_1) \Biggr)
\end{equation}
\begin{equation}
p(\mbox{\bf x}\vert \omega_2) = \frac{1}{2\pi}
\exp \Biggl( -(\mbox{\bf x} - \mu_2)^T(\mbox{\bf x} - \mu_2) \Biggr)
\end{equation}
where $\mu_1 = (1,1)$ and $\mu_2 = (3,3)$.
   \begin{itemize}
   \item[(1)] Classify a randomly cleated feature vector {\bf x} using
              the Parzen windows.
   \item[(3)] Try 3NN Algorithm for
      \begin{itemize}
      \item[i)] hypercube of length $h$;
      \item[ii)] hypersphere of radius $r$
      \item[iii)] a hyper ellipsoid   
      \end{itemize}
   \item[(3)] Each of the above three cases, 
              try to use likelihood ratio test.\\
   \end{itemize}
\item Create 100 training data following 3-dimensional Gaussian
      distribution with
\begin{eqnarray}
\Sigma = \left(
\begin{array}{lll}
0.3 &  0.1 &  0.1 \\
0.1 &  0.3 & -0.1 \\
0.1 & -0.1 &  0.3 \\
\end{array}
\right)
\end{eqnarray}
where $\mu_1 = (0,0,0)$ and $\mu_2 = (1/2,1/2,1/2)$.
   \begin{itemize}
   \item[(1)] Classify a randomly cleated feature vector {\bf x} using
      \begin{itemize}
      \item[i)] the Parzen windows; 
      \item[ii)] 3NN Algorithm
      \item[iii)] NN Algorithm              
      \end{itemize}
   \item[(2)] Try to use likelihood ratio test.\\
   \end{itemize}
\end{itemize}

%---------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf Parameter Estimation under Known pdf}\\

\begin{itemize}
\item[-]Assume that we have 100 data: 
\begin{equation}
3.2, 2,8, 5.4, 6.2 \cdots
\end{equation}
\item[]that are drawn from $p(\mbox{\bf x}\vert \omega_i)$, 
       a pdf for a class $i$.\\
\item[-]Sometimes
   \begin{itemize}
   \item[$\cdot$]We don't have no information as for pdf, which
                 we have studied in the previous section.
   \item[]or
   \item[$\cdot$]We know the function form but not parameters, which
                 we are going to study in this section.
   \end{itemize}
\end{itemize}

\hspace*{1in}\\
\noindent
$\bullet$ Maximum Likelihood Estimation:
\begin{itemize}
\item[-] For a data set 
\begin{displaymath}
\mbox{\bf x} = (x_1, x_2, \cdots, x_N),
\end{displaymath}
\item[] when likelihood that {\bf x} is drawn from the pdf with 
        parameter $\theta$ is expressed as $p(\mbox{\bf x}; \theta)$,
        we might say ``$p(\mbox{\bf x}; \theta_1)$ is more likely  than
        $p(\mbox{\bf x}; \theta_2)$.''\\
\item[-]Then which $\theta$ gives most likely $p(\mbox{\bf x}; \theta)$?
\item[]\hfill (to continue)
\clearpage
\item[-]Under an assumption of independence between the different sample,
\begin{equation}
p(\mbox{\bf x}; \theta) \equiv p(x_1, \cdots, x_N) = 
\prod_{k=1}^N p(\mbox{\bf x}; \theta)
\end{equation}
\item[-]To answer the question, likelihood function is defined as
\begin{equation}
l(\theta) = \prod_{k=1}^N p(\mbox{\bf x}_k; \theta)
\end{equation}
\item[-]The necessary condition of the most likely $\theta = \theta_{ML}$ is
\begin{equation}
\frac{\partial \prod_{k=1}^N p(\mbox{\bf x}_k; \theta)}{\partial \theta}=0
\end{equation}
\item[-]Or sometimes more conveniently taking logarithm
\begin{equation}
L(\theta) = \ln \prod_{k=1}^N p(\mbox{\bf x}_k; \theta)
\end{equation}
\item[]called {\it loglikelihood function}, \\
\item[-]and $\theta_{ML}$ is obtained from
\begin{equation}
\frac{\partial L}{\partial \theta} = 
\sum \frac{1}{p(\mbox{\bf x}_k; \theta)}\cdot 
\frac{\partial p(\mbox{\bf x}_k; \theta)}{\partial \theta}
\end{equation}
\end{itemize}
\clearpage
\begin{itemize}
\item[] {\bf Exercise} 
   \begin{itemize}
   \item[1.]  We now have 100 positive values 
\begin{displaymath}
2.4, 5.6, 3.2 \cdots
\end{displaymath}
and we know they are drawn from 
\begin{equation}
p(\mbox{\bf x}; \theta) = \theta^2 x \exp (- \theta x)
\end{equation}
             called {\it Erlang} pdf, but we don't know the value of 
             $\theta$. Then what $\theta$ is the most likely value for 
             the given 100 data? \\
   \item[2.]We have 100 data drawn from $N(\mu, 1)$. What is the most 
            likely estimate for $\mu$?
   \end{itemize}
\end{itemize}
\clearpage
\noindent
$\bullet$ Maximum a posteriori pdf estimation
\begin{itemize}
\item[-] For a data set $X = (\mbox{\bf x}_1, \cdots, \mbox{\bf x}_N)$
$\theta$, which is thought as a random variable here, is estimated 
its value on the condition that the data $\mbox{\bf X}$ has occurred.\\
\item[]Since\\
\begin{equation}
p(\theta \vert X) = \frac{p(\theta)p(X \vert \theta)}{p(X)}
\end{equation}
\item[]
\item[] $\theta_{\mbox{\small MAP}}$ is estimated from
\begin{equation}
\frac{\partial}{\partial \theta} \hspace{.1in} p(\theta \vert X) 
= \frac{\partial}{\partial \theta} \hspace{.1in} 
  p(\theta)p(\theta \vert X) = 0
\end{equation}
\item[]
\item[-] The difference between ML and MAP is that the latter
involves $p(\theta)$. Therefore if $p(\theta)$ is uniform distribution
or if $p(\theta)$ has a large variance, the Both are the same or almost
the same. But in general the two estimation yield a different results.
\item[]\hfill (to continue)
\clearpage
\item[]{\bf Example:} 
   \begin{itemize}
   \item[] Assume we have 100 data from Gaussian pdf with unknown $\mu$
           and we know $\mu$ is from Rayleigh pdf:
\begin{equation}
p(\mu) = \frac{\mu \exp (- \mu^2 / 2 \sigma_{\mu}^2)}
              {\sigma_{\mu}^2}
\end{equation}
   \item[]Estimate $\mu_{\mbox{\small MAP}}$.\footnote{The answer is
\begin{equation}
\mu_{\mbox{\tiny MAP}} = \frac{Z}{2R}(1+ \sqrt {1+ \frac{4R}{Z^2}}).
\end{equation}
where
\begin{equation}
Z=\frac{1}{\sigma^2}\sum_{k=1}^N x_k, \hspace{.2in}\mbox{and}\hspace{.2in}
R=\frac{N}{\sigma^2}+\frac{1}{\sigma_{\mu}^2}.
\end{equation}
}
      \end{itemize}
\item[]
\item[]{\bf Yet Another Example:} 
   \begin{itemize}
   \item[] Assume $x_1, x_2, \cdots, x_N$ are data from Gaussian pdf
           with known $\sigma$ and unknown $\mu$, that is,
\begin{equation}
p(x_k;\mu) = \frac{1}{\sqrt{2\pi}\sigma} 
\exp \{ - \frac{(x_k - \mu)^2}{2\sigma^2} \}
\end{equation}
\item[]and $\mu$ is known to be Gaussian distributed 
around the value $\mu_0$, that is,
\begin{equation}
p(\mu) = \frac{1}{\sqrt{2\pi}\sigma_{\mu}} 
\exp \{- \frac{(\mu - \mu_0)^2}{2\sigma_{\mu^2}}\}
\end{equation}
   \item[]Estimate $\mu_{\mbox{\small MAP}}$.\footnote{The answer is
\begin{equation}
\mu_{\mbox{\tiny MAP}} = 
\frac{\mu_0 + (\sigma_{\mu}^2/\sigma^2)\sum_{k=1}^N x_k}
     {1 + (\sigma_{\mu}^2/\sigma^2)N}
\end{equation}
which can be interpreted as $ \mu_{\mbox{\tiny MAP}} = \mu_0$ when
$\sigma_{\mu}^2/\sigma^2 \gg 1$. I thank Lalehan for pointing this out!
}
   \end{itemize}
\end{itemize}

%---------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf Unknown pdf shortly revisited}\\
\begin{itemize}
\item Maximum Entropy Estimation:
   \begin{itemize}
   \item[-] Determine $p(x)$ such that entropy
\begin{equation}
H = - \int_x p(x) \ln p(x)dx
\end{equation}
   \item[]is maximized.\\
   \end{itemize}
\item Estimation as a sum of known pdf:
   \begin{itemize}
   \item[-]Assuming each sample $x$ is drawn from any of the $J$ pdfs
           with the probability $p_j$.
\begin{equation}
p(x) = \sum_{j=1}^J p(x \vert j) p_j
\end{equation}
   \end{itemize}
\end{itemize}
\vfill
\begin{center}
--------------------------------------------------------------------------\\
\end{center}
$\star$ This concludes the course of this semister.\\
$\star$ Thank you very much for your interest and atendance. \\
$\star$ See you.

\end{LARGE}
\end{document}
