\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{\noindent 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}
which is available, for example, at http://www.amazon.com.}}
\end{Huge}

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

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

\begin{itemize}
\item A typical example:
   \begin{itemize}
   \item Hand-written character recognition:
      \begin{itemize}
      \item[] with inputs being pixel values.\\
      \end{itemize}
   \end{itemize}
\item What else?
   \begin{itemize}
   \item Face recognition;
   \item Speech recognition;
   \item Robot's eye/ear.
   \end{itemize}

\clearpage
\item Can we recognize them with fewer information?\\
   \begin{itemize}
   \item Yes! 
   \item To recognize hand-written characters, e.g.,
      \begin{itemize}
      \item Perimeter of the boundary: 
         \begin{equation}
            P_i=\sum_{i=1}^{N-1}\|x_{i-1} - x_{i}\| + \|x_{0} - x_{1}\|.
         \end{equation}
      \item Area inside the boundary: $A$.
      \item Roundness ratio:
         \begin{equation}
            r = p^2/4 \pi A.
         \end{equation}
      \item Bending energy (defined at a point $n$):
         \begin{equation}
             E(n) = \frac{1}{P} \sum_{i=0}^{n-1} {\vert k_i \vert ^2} \\
         \end{equation}
      \item[] where $k_i$ {\it (curvature of boundary}) is:
         \begin{equation}
            k_n = \theta_{n+1} - \theta{n}, \hspace{.1in}
            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{.1in}
         n = 0, 1, \cdots, N-1.
         \end{equation}
      \item Number of halls.
      \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}
   \item They are called {\it features}.
   \item Then, how many features are enough?\\
         (Minimize the number of features.)\\
   \end{itemize}
\end{itemize}

\noindent
In short:
\begin{itemize}
\item pattern recognition is a {\it classifier}.
   \begin{itemize}
   \item Especially usfull for classification in high-dimensional
         {\it feature space}.
   \end{itemize}
\item Application:
   \begin{itemize}
   \item diagnosis.
   \item what else?
   \end{itemize}
\end{itemize}

%---------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf Statistical Classification: \\
\hspace*{2in}Bayes Decision Theory}\\
\hspace*{3in} --- 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 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}

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

\hspace*{1in}\\
\noindent
$\bullet $ Two-class case:
\begin{displaymath}\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{displaymath}
\begin{displaymath}
\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{displaymath}

\noindent
The region where 
$p(\omega_1  \vert \mbox{\bf x}) > p(\omega_2  \vert \mbox{\bf x})$
is the region where
\begin{equation}\label{eq:1-d-gaussian-1}
   \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}\label{eq:1-d-gaussian-2}
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}

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

\newtheorem{excersise}{Excersise}
\begin{excersise}
If we assume that
          $p(\omega_1  \vert \mbox{\bf x}) = 
           N(0, 1/2)$\footnote{$\displaystyle
           N(\mu, \sigma^2)=\frac{1}{\sqrt{2\pi}\sigma}
          \exp{-\frac{(x-\mu)^2}{2\sigma^2}}$},\hspace{.1in}
          $p(\omega_2  \vert \mbox{\bf x})
          = N(1, 1/2)$
          and\hspace{.1in}
          $p(\omega_1) = p(\omega_2) = 1/2$, 
          then how is our classification like?
\end{excersise}

%---------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf $l$-dimensional Gaussian distribution:}\\
\begin{itemize}
\item What does it mean by Gaussian distribution of a vector {\bf x}?
\begin{displaymath}
\mbox{\bf x} = (x_1, x_2, \cdots, x_l)
\end{displaymath}
\item[]Assume we have $p$ samples each of $x_i$ has a value $x_{ik}$
$(k = 1,2, \cdots, p)$ such as:

\begin{table}[hbtp]
\begin{center}
\begin{tabular}{c c c c c} \hline \hline
\hspace*{.1in} & $x_{1k}$ & $x_{2k}$ & $\cdots$ & $x_{lk}$ \\ \hline
$k=1$          & 3.2      & 7.4      &          & 9.4      \\
$k=2$          & 2.3      & 8.1      &          & 8.7      \\
               &          &          & $\cdots$ &          \\ 
$k=p$          & 2.9      & 9.2      &          & 7.9      \\ \hline
$\mu_i$    &&&& \\
$\sigma_i^2$ &&&& \\ \hline \hline
\end{tabular} 
\end{center}
\end{table}
\item[] You may fill the blancs for $\mu_i$ and $\sigma_i$.
\item[] Then you define the pdf as:
\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
\item[]where
\begin{displaymath}
\mu = (\mu_1, \mu_2, \cdots, \mu_l)
\end{displaymath}
\item[]and
\begin{eqnarray}
\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}

\clearpage
In summary,
   \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$, i.e.,
\begin{displaymath}
\mu_i = \frac{\displaystyle \sum_{k=1}^p x_{ik}}{p}
\end{displaymath}
   \item[$\cdot$] $\sigma_i^2$ is the variance of $x_i$, i.e.,
\begin{displaymath}
\sigma_i^2 = \frac{\displaystyle \sum_{k=1}^p (x_{ik} - \mu_i)^2}{p}
\end{displaymath}
   \item[$\cdot$] $\sigma_{ij}$ is the covariance between $x_i$ and $x_j$, 
                  i.e.,
\begin{displaymath}
\sigma_{ij} = \frac{\displaystyle \sum_{k=1}^p 
              (x_{ik} - \mu_i)(x_{jk} - \mu_j)}{p}
\end{displaymath}
   \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}
\end{itemize}

\clearpage
\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}{\sqrt{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{excersise}
Try the following two problems.
   \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{excersise}

\begin{figure}[h]
 \begin{center}
   \epsfile{file=two-d-gaussian.eps,width=20cm,height=24cm}
 \end{center}
\end{figure}

%---------------------------------------------------------------------
\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}\label{eq:boundary}
p(\omega_i \vert \mbox{\bf x}) - p(\omega_j \vert \mbox{\bf x}) = 0
\end{equation}
\hspace*{1in}\\
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}
\hspace*{1in}\\
      and we can say \\
      \begin{equation}
      \mbox{if}\hspace{.1in} g_i(x)>g_j(x) \hspace{.1in}
      \mbox{classify {\bf x} to} \hspace{.1in} \omega_i. 
      \end{equation}
\hspace*{1in}\\
      Hence \\
      \begin{equation}
      g_{ij} \equiv g_i(\mbox{\bf x}) - g_j(\mbox{\bf x}) = 0 
      \end{equation}
\hspace*{1in}\\
      determines the {\it decision surfaces} separating contiguous regions 
      and called {\it discriminant function.}
\end{itemize}

%---------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf Examples of Decision Surface:}\\

\noindent
$\bullet$ 1-D Gaussian case.\\

\noindent
The Equation (\ref{eq:boundary}) in 1-D Caussian cases leads:
\begin{equation}
p(\omega_1  \vert \mbox{\bf x}) = p(\omega_2  \vert \mbox{\bf x})
\end{equation}
That is,
\begin{equation}
\frac{1}{\sqrt{2\pi}\sigma_1}\exp\{{-\frac{(x-\mu_1)^2}{2{\sigma_1}^2}}\} =
\frac{1}{\sqrt{2\pi}\sigma_2}\exp\{{-\frac{(x-\mu_2)^2}{2{\sigma_2}^2}}\}.
\end{equation}
Solving this equation w.r.t. $x$ you can obtain decision surface,
actually a point in this case, $x_0$. \footnote{See also the Eqations
(\ref{eq:1-d-gaussian-1}) and (\ref{eq:1-d-gaussian-2}).}

\begin{excersise}
Obtain the decision boundary $x_0$ when the two classes follow the Gaussian
distributions with $N(1, \frac{1}{2})$ and $N(3, \frac{1}{2})$ 
respectively.
\end{excersise}

\hspace*{1in}\\
\hspace*{1in}\\
\noindent
$\bullet$ General Gaussian case.\\

\noindent
The Equation (\ref{l-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}
\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}\\
 &=& - \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}\mbox{\bf x}\\
%%\nonumber
%%  && \hspace{1in} +\frac{1}{2} \mu_i^T \Sigma_i^{-1}\mu_i
%%     - \ln p(\omega_i) + c_i\\
\end{eqnarray}
\noindent
where
\begin{equation}\label{eq:discriminant}
c_i = - (l/2)\ln (2\pi) - (1/2) \ln \vert \Sigma_i \vert
\end{equation}

%---------------------------------------------------------------------
\clearpage
\noindent
$\bullet$ 2-D Gaussian case.\\

\noindent
Our discriminat function (\ref{eq:discriminant}) for 2-D Gaussian pdf is
\begin{eqnarray}\label{eq:2-d-gaussian}
g_i(\mbox{\bf x}) 
 &=& - \frac{1}{2} (\mbox{\bf x}-\mu_i)^T
            \Sigma_i^{-1}(\mbox{\bf x}-\mu_i) + \ln p(\omega_i) + c_i
\end{eqnarray}
\noindent
where
\begin{equation}\label{eq:2-d-const}
c_i = - (1/2)\ln (2\pi) - (1/2) \ln \vert \Sigma_i \vert.
\end{equation}

\hspace*{1in}\\
\noindent
This is simplified\\

\begin{itemize}
\item[$\star$] if

\begin{eqnarray}
\nonumber
\Sigma_i =
\left(
\begin{array}{cc}
\sigma_1^2 & 0          \\
0          & \sigma_2^2 \\
\end{array}
\right)
\end{eqnarray}
\item[]then

\begin{equation}
g_i = \frac{(x_1-\mu_1)^2}{-2\sigma_1^2}
    + \frac{(x_2-\mu_2)^2}{-2\sigma_2^2}
    -\frac{1}{2}\ln(\sigma_1^2\sigma_2^2)
+ \ln p(\omega_i) - \frac{1}{2}\ln(2\pi) \\
\end{equation}
\end{itemize}

\hspace*{1in}\\
Note that the last two terms in the right hand side of 
               the above equation will be cancelled when obtaining 
               the border $g_i-g_j=0$.


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

\item[-] If $\sigma_1 = \sigma_2$ holds in both $\Sigma_i$ and 
         $\Sigma_j$ then the decision surface is a {\it circle}.
\item[-] Furthermore, if $\Sigma_i = \Sigma_j$ holds then 
         the decision surface is a {\it straight line.}
\end{itemize}

\clearpage
\begin{excersise}\label{excersise:border}
When $p(\omega_1)=p(\omega_2)$, $\mu_1=(0, 0)$ and $\mu_2=(1, 1)$
obtain decision surface in the following four cases.
\begin{small}
\begin{eqnarray}
\nonumber
(1) \hspace{.2in}\Sigma_1 =
\left(
\begin{array}{cc}
0.10 & 0             \\
0    & 0.10
\end{array}
\right),
\hspace{.5in}\Sigma_2 =
\left(
\begin{array}{cc}
0.10 & 0             \\
0    & 0.10
\end{array}
\right)
\end{eqnarray}

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

\begin{eqnarray}
\nonumber
(3) \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
(4) \hspace{.2in}\Sigma_1 =
\left(
\begin{array}{cc}
0.20 & 0             \\
0    & 0.10
\end{array}
\right),
\hspace{.5in}\Sigma_2 =
\left(
\begin{array}{cc}
0.30 & 0             \\
0    & 0.10
\end{array}
\right)
\end{eqnarray}

\begin{eqnarray}
\nonumber
(5) \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}
\end{small}
\end{excersise}

\hspace*{1in}\\
\begin{excersise}\label{excersise:border-2}
When $p(\omega_1)=p(\omega_2)$ again, but $\mu_1=\mu_2 = (0, 0)$
this time, obtain decision surface.
\begin{small}
\begin{eqnarray}
\nonumber
(6) \hspace{.2in}\Sigma_1 =
\left(
\begin{array}{cc}
0.30 & 0             \\
0    & 0.30
\end{array}
\right),
\hspace{.5in}\Sigma_2 =
\left(
\begin{array}{cc}
0.10 & 0             \\
0    & 0.90
\end{array}
\right)
\end{eqnarray}
\end{small}
\end{excersise}

\hspace*{1in}\\
\begin{excersise}
When $p(\omega_1)=p(\omega_2)$, what condition is needed for the border of 
two classes to be the following decision surface?
\begin{itemize}
\item[] (1) ellipse;
\item[] (2) parabola;
\item[] (3) hyperbola;
\item[] (4) two straight lines.
\end{itemize}
\end{excersise}
%---------------------------------------------------------------------
\clearpage
\noindent
\begin{small}
$\bullet$ Examples of border --- from Excersise \ref{excersise:border}
and \ref{excersise:border-2}.

\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=border-1.eps,width=6.0cm,height=5.0cm}
   \epsfile{file=border-2.eps,width=6.0cm,height=5.0cm}
   \epsfile{file=border-3.eps,width=6.0cm,height=5.0cm}
   \epsfile{file=border-4.eps,width=6.0cm,height=5.0cm}
   \epsfile{file=border-5.eps,width=6.0cm,height=5.0cm}
   \epsfile{file=border-6.eps,width=6.0cm,height=5.0cm}
 \end{center}
\end{figure}

\noindent
The equations of the above borders are:\\

\noindent
(1)
\begin{displaymath}
x_1 + x_2 = 1.
\end{displaymath}
(2)
\begin{displaymath}
(x_1 + 1)^2 + (x_2 + 1)^2 = 4 - 0.2 \ln (1/4).
\end{displaymath}
(3)
\begin{displaymath}
15 (x_1 + 1)^2 + 8(x_2 + 3/2)^2 = 93/2 - 6 \ln (3/10).
\end{displaymath}
(4)
\begin{displaymath}
x_1^2 + 4 x_1 + 12 x_2 - 8 + 0.6 ln(2/3) = 0.
\end{displaymath}
(5)
\begin{displaymath}
(x_1 + 1)^2 - (x_2 - 3/2)^2 = 3/2.
\end{displaymath}
(6)
\begin{displaymath}
(\sqrt{3}x_1 + \sqrt{5})(\sqrt{3}x_1 - \sqrt{5}) = 0.
\end{displaymath}
\end{small}


%---------------------------------------------------------------------
\clearpage
\begin{itemize}
\item[$\star$] An example of more general case:
   \begin{itemize}
   \item[]That is, our $\Sigma$ is no more of the form
\begin{eqnarray}
\nonumber
\left(
\begin{array}{cc}
\sigma_1^2 & 0          \\
0          & \sigma_2^2 \\
\end{array}
\right)
\end{eqnarray}
   \item[]but, instead,  of the more general form
\begin{eqnarray}
\nonumber
\left(
\begin{array}{cc}
\sigma_1^2 & \sigma_{12}\\
\sigma_{21}& \sigma_2^2 \\
\end{array}
\right).
\end{eqnarray}
   \item[] Then the Equation (\ref{eq:2-d-gaussian}) leads 
           an equation of the form
\begin{displaymath}
c_1 x_1^2 + c_2 x_2 ^2 + c_3 x_1 x_2 + c_4 x_1 + c_5 x_5 + c_6 = 0.
\end{displaymath}
   \end{itemize}
\end{itemize}

\hspace*{1in}\\
\begin{excersise}\label{excersise:border-non-diagonal}
When $p(\omega_1)=p(\omega_2)$, $\mu_1=(0, 0)$ and $\mu_2=(1, 1)$ 
still holds, obtain decision surface in the following case.
\begin{small}
\begin{eqnarray}
\nonumber
\hspace{.2in}\Sigma_1 =
\left(
\begin{array}{cc}
0.3 & 0.1             \\
0.1 & 0.4
\end{array}
\right),
\hspace{.5in}\Sigma_2 =
\left(
\begin{array}{cc}
0.5 & 0.3             \\
0.3 & 0.2
\end{array}
\right)
\end{eqnarray}
\end{small}
\end{excersise}

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

\noindent
The border of the Excersise \ref{excersise:border-non-diagonal} will be
\begin{displaymath}
18x_1^2-67x_1 x_2 -52 x_2^2 = (11/10) \ln 11.
\end{displaymath}

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

\begin{excersise}
But how can we draw the graph of this equation?
\end{excersise}


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

\noindent
Recalling that we classify {\bf x} to $\omega_i$ such that $g_i$ 
is maximized, the Equation (\ref{eq:discriminant}) implies
we minimize:

\begin{equation}
(\mbox{\bf x} - \mu_i)^T \Sigma^{-1}(\mbox{\bf x} - \mu_i)
\end{equation}
that is,

\begin{itemize}
\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}

\hspace*{1in}\\
\hspace*{1in}\\
\hspace*{1in}\\
\begin{excersise}\label{excersise:two-d}
About a two-class, two dimensional Bayesian classifier where 
\begin{displaymath}
p(\omega_1)=p(\omega_2),\hspace{.2in} \mu_1=(0, 0), 
\hspace{.2in}\mu_2=(1, 0)
\end{displaymath}
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}
answer the following questions.
\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$.\\
\end{itemize}
\end{excersise}

%---------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf Diagonalization of Variance Matrix:}\\
\hspace*{2in} --- to learn the shape of the ellipses\\

\noindent
Definition 
\begin{itemize}
\item {\it Eigenvalue} of $\Sigma$ are $\lambda$'s that satisfy 
   \begin{equation}
   \vert \Sigma - \lambda I \vert = 0
   \end{equation}
\item {\it Eigenvector} of $Sigma$ are {\bf x}'s that satisfy 
   \begin{equation}
   \Sigma  \mbox{\bf x} =  \lambda {\bf x}
   \end{equation}
\end{itemize}
\hspace*{1in}\\
Then we have the following relation:
   \begin{equation}
   \Sigma = \Phi \Lambda \Phi^T 
   \end{equation}
where $\Lambda$ is the diagonal matrix whose elements are 
the eigenvalues of $\Sigma$, $\Phi$ is a matrix whose columns 
are corresponing eignevectors of $\Sigma$, and due to its symmetry
$\Phi^{T} = \Phi^{-1}$.\\

\hspace*{1in}\\
\noindent
Hence, our ellipse $d_{M} = c^2$ becomes:
   \begin{equation}
   (\mbox{\bf x} - \mu)^T \Phi \Lambda \Phi^T (\mbox{\bf x} - \mu) = c^2.
   \end{equation}
\hspace*{1in}\\
This is interpreted as:
   \begin{equation}
   (\mbox{\bf X} - \mu)^T \Lambda (\mbox{\bf X} - \mu) = c^2
   \end{equation}
on the (rotated) new coordinate:
   \begin{eqnarray}
   \left(
   \begin{array}{c}
   X_1   \\
   X_2
   \end{array}
   \right) = \mbox{\bf X} = \Phi^T \mbox{\bf x}
   \end{eqnarray}
\hspace*{1in}\\
where the ellipse has the equation of the form:
   \begin{displaymath}
   a_1 X_1^2 + a_2 X_2^2 = c
   \end{displaymath}
\hspace*{1in}\\
instead of the form:
   \begin{displaymath}
   a_1 x_1^2 + a_2 x_2^2 +a_3 x_1 x_2 = c
   \end{displaymath}

\clearpage
\begin{excersise}\label{excersise:rotate-ellipse}
When
\begin{eqnarray}
\nonumber
\Sigma =
\left(
\begin{array}{cc}
1.1 & 0.3             \\
0.3 & 1.9
\end{array}
\right)
\end{eqnarray}
answer the following questions.
\begin{itemize}
\item[(1)] Obtain Eigenvalues of $\Sigma$.
\item[(2)] Obtain Eigenvectors of $\Sigma$.
\item[(3)] Solve the equation w.r.t. $x_1$ and $x_2$.
\begin{displaymath}
\mbox{\bf x}^T\Sigma^{-1}\mbox{\bf x} = 1.
\end{displaymath}
           
\item[(4)] Obtain $\Phi$ and $\Lambda$, and ascertain the relation: 
\begin{displaymath}
           \Sigma = \Phi^{-1}\Lambda \Phi.\\
\end{displaymath}
\item[(5)] Obtain the equation of the projected ellipse w.r.t. 
$X_1$ and $X_2$
\begin{displaymath}
\mbox{\bf x}^T (\Phi \Lambda^{-1} \Phi^T) \mbox{\bf x} = 1
\end{displaymath}
that is,
\begin{displaymath}
\mbox{\bf X}^T \Lambda^{-1} \mbox{\bf X} = 1.
\end{displaymath}
\end{itemize}
\end{excersise}

%---------------------------------------------------------------------
\clearpage
\noindent
\begin{small}
$\bullet$ Examples of border --- 
from Excersise \ref{excersise:rotate-ellipse}\\

\noindent
Since now our $\Sigma$ is
\begin{eqnarray}
\nonumber
\Sigma =
\left(
\begin{array}{cc}
1.1 & 0.3             \\
0.3 & 1.9
\end{array}
\right)
\end{eqnarray}

\begin{eqnarray}
\nonumber
\mbox{\bf x}^T \Sigma \mbox{\bf x} =
(x_1 \hspace{.1in} x_2) \left(
\begin{array}{cc}
 0.95 & -0.15             \\
-0.15 &  0.55
\end{array}
\right) \left(
\begin{array}{c}
x_1            \\
x_2
\end{array}
\right) = \cdots = 0.95 x_1^2 - 0.30 x_1 x_2 + 0.55 x_2.
\end{eqnarray}
So our ellipse is, e.g.,
\begin{displaymath}
0.95 x_1^2 - 0.30 x_1 x_2 + 0.55 x_2 = 1.
\end{displaymath}
In order to learn the shape of the ellipse we transform it with
$\Sigma = \Phi \Lambda \Phi^T$ where
\begin{eqnarray}
\nonumber
\Phi =
\frac{1}{\sqrt{10}}\left(
\begin{array}{cc}
 3 & 1             \\
-1 & 3
\end{array}
\right)
\end{eqnarray}
and
\begin{eqnarray}
\nonumber
\Lambda =
\left(
\begin{array}{cc}
 1 & 0             \\
 0 & 2
\end{array}
\right)
\end{eqnarray}
That is, our ellipse $\mbox{\bf x}^T \Sigma^{-1} \mbox{\bf x} = 1$ is 
expressed as $\mbox{\bf x}^T \Phi \Lambda^{-1} \Phi^T  \mbox{\bf x} = 1$ 
where
\begin{eqnarray}
\nonumber
\mbox{\bf x}^T \Phi =
(x_1 \hspace{.1in} x_2) \left(
\begin{array}{rr}
 3 & -1             \\
 1 &  3 
\end{array}
\right)/\sqrt{10} = (3x_1-x_2 \hspace{.1in} x_1 + 3 x_2) /\sqrt{10}
\end{eqnarray}
and
\begin{eqnarray}
\nonumber
\Phi^T \mbox{\bf x} = \left(
\begin{array}{rr}
 3 & -1             \\
 1 &  3
\end{array}
\right) \left(
\begin{array}{r}
 x_1          \\
 x_2
\end{array}
\right) /\sqrt{10}
= (3x_1-x_2 \hspace{.1in} x_1 + 3 x_2)/\sqrt{10}
\end{eqnarray}
Hence, if we use the new coordinate:
\begin{displaymath}
(X_1 \hspace{.1in} X_2) = (3x_1-x_2 \hspace{.1in} x_1 + 3 x_2)/\sqrt{10}
\end{displaymath}
our ellipse is
\begin{eqnarray}
\nonumber
(X_1 \hspace{.1in} X_2) \left(
\begin{array}{rr}
 1 &  0             \\
 0 &  2
\end{array}
\right) \left( 
\begin{array}{r}
 X_1         \\
 X_2
\end{array}
\right)  = 1
\end{eqnarray}
That is
\begin{displaymath}
X_1^2 + 2 X_2 ^2 = 1
\end{displaymath}

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

\clearpage
$\bullet$ From Excersise \ref{excersise:two-d}
and \ref{excersise:rotate-ellipse}.

\begin{itemize}
\item[$\cdot$] Points whose Mahalanobis distance is identical from center 
(mean) of the two classes respectively.
\end{itemize}

\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=border-7.eps,width=18cm,height=14cm}
 \end{center}
\end{figure}
\end{small}

%---------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf Pattern Classification by Neural Network}\\

\begin{itemize}
\item We can use {\it Neural Networks} to classify
      for any number of features to any number of classes.
\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=black-box-nn.eps,width=10cm,height=8cm}
 \end{center}
\end{figure}
\item What is {\it Neural Networks}?
   \begin{itemize}
      \item Neuron
      \item Synaps
      \item Synaptic weight and Transfer function
      \item Learning
   \end{itemize}
\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=layered-nn.eps,width=10cm,height=6cm}
 \end{center}
\end{figure}
\clearpage
\item Definition of variables:
   \begin{itemize}
   \item $L$ layers of neurons.
   \item $k_r$ neurons in the $r$-$th$ layer.\hspace{.2in} 
         $r = 1,2, \cdots, L.$
   \item $M$ input neurons ($k_1 = M$) and $N$ output neurons ($k_L = N$).
   \item $w_{ij}^r$: weight from the $j$-$th$ neuron in the $r$-$th$ layer 
                     to the $i$-$th$ neuron in the $r$-$th$ layer.
   \item $p$ training pairs: $(\mbox{\bf x}(\mu),\mbox{\bf z}(\mu))$, 
         \hspace{.2in} $i = 1, 2, \cdots, p$.
   \item $y_i^{r}(\mu)$: the output of the $i$-$th$ neuron in the $r$-$th$
                        layer when the $\mu$-$th$ training sample is given.
   \item fan-in's to $j$-$th$ neuron in the $r$-$th$
                        layer when the $\mu$-$th$ training sample is given.
\begin{equation}\label{eq:fan-in}
\displaystyle 
              h_j^r(\mu) \equiv 
              \sum_{k=1}^{k_{r-1}}w_{jk}^r y_k^{r-1}(i) + w_{j0}^r =
              \sum_{k=0}^{k_{r-1}}w_{jk}^r y_k^{r-1}(i),
\end{equation}
   \item[] where
\begin{displaymath}
y_0^{r-1} = 1
\end{displaymath}
      \item[] and 
\begin{displaymath}
(y_1^1(\mu), \cdots,  y_M^1(\mu)) = 
               (x_1(\mu),   \cdots,    x_M(\mu)) = \mbox{\bf x}(\mu).
\end{displaymath}
   \item Each output neuron's error:
\begin{equation}\label{eq:error}
e_i(\mu) \equiv y_i(\mu)- z_i(\mu), \hspace{.1in}
i = 1,2, \cdots, N.
\end{equation}
   \item[] where $(z_1(\mu), \cdots, z_N(\mu)) 
                   = \mbox{\bf z}(\mu)$
   \item Error function to be minimized:
\begin{equation}\label{eq:error-function}
\displaystyle D= 
              \frac{1}{2} \sum_{\mu=1}^{p} \sum_{i=1}^{N} e_i(\mu)^2
\end{equation}
   \end{itemize}
\end{itemize}

\clearpage
\noindent
$\bullet$ An example of the notations \\
\begin{itemize}
\item[-] $L=3$,\hspace{.1in} $M=k_1 = 4$, \hspace{.1in} $N = k_3 = 3$ 
\hspace{.1in} and \hspace{.1in}$k_2 = 2$.
\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=backprop.eps,width=12cm,height=10cm}
 \end{center}
\end{figure}
\item[-] e.g.
   \begin{itemize}
   \item[$\star$]
           $h_2^2(\mu) = w_{21}^1 \cdot x_1(\mu) + w_{22}^1 \cdot x_2(\mu)
                       + w_{23}^3 \cdot x_3(\mu) + w_{24}^1 \cdot x_4(\mu).$
   \item[$\star$]
           $h_2^3(\mu) = w_{21}^2 \cdot y_1^2(\mu) 
                       + w_{22}^2 \cdot y_2^2(\mu).$
   \end{itemize}
\end{itemize}


%---------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf Back Propagation}\\
\hspace*{1in} --- Learning for multi-layered analog neural networks.\\

\noindent
$\bullet$ The algorithm:
\begin{itemize}
\item[1.] {\it Initialization:} 
   \begin{itemize}
   \item[$\cdot$]Initialize all the weights with small random values.
   \end{itemize}
\item[2.] {\it Forward computations:} 
   \begin{itemize}
   \item[$\cdot$] For each of the training vectors
      \begin{displaymath}
   \mbox{\bf x}(i), \hspace{.2in} \mu = 1, 2, \cdots, p
   \end{displaymath}
   \item[] compute all the 
\begin{equation}\label{eq:local-output}
y_j^r(\mu) = f (h_j^r(\mu))
\end{equation}
\item[] for \hspace{.1in}$j = 1, 2, \cdots, k_r $ 
\hspace{.1in} and \hspace{.1in}$ r = 1, 2, \cdots, L$.
   \end{itemize}
\item[3.] {\it Backward computations:} 
   \begin{itemize}
   \item[$\cdot$] For each \hspace{.1in} $\mu = 1, 2, \cdots, p$
          \hspace{.1in} and \hspace{.1in} $j = 1, 2, \cdots, N$ 
          \hspace{.1in} compute
\begin{equation}\label{eq:delta}
\delta_j^L(\mu) = e_j(\mu)f^{\prime}(h_j^L(\mu)).
\end{equation}
   \item[$\cdot$] Then compute
\begin{equation}\label{eq:next-delta}
\delta_j^{r-1}(\mu) = e_j^{r-1}(\mu)f^{\prime}(h_j^{r-1}(\mu))
\end{equation}
   \item[]for \hspace{.1in} $ r = L, L-1, \cdots ,2$ \hspace{.1in} and 
\hspace{.1in} $j = 1, 2, \cdots, k_r$ \hspace{.1in} where
\begin{equation}\label{eq:error-propagated}
\displaystyle e_j^{r-1}(\mu) = 
             \sum_{k=1}^{k_r} \delta_k^r(\mu)w_{kj}^{r-1}.
\end{equation}
   \end{itemize}
\item[4.] Update the weights for \hspace{.1in} $r=1,2, \cdots, L$ 
\hspace{.1in} and \hspace{.1in} $j = 1, 2, \cdots, k_r$
\begin{equation}\label{eq:modify-weights}
w_{jk}^{r} \left[ \mbox{new} \right]= 
            w_{jk}^{r} \left[ \mbox{old} \right] + 
            \triangle w_{jk}^r
\end{equation}
\item[]where
\begin{equation}\label{eq:resulted-weights}
\displaystyle \triangle w_{jk}^r = 
          - \epsilon 
            \delta_j^r(\mu)y_k^{r}(\mu).
\end{equation}
\item[] until no change occurs during the training cycle of 
\hspace{.1in}$\mu = 1,2, \cdots, p$.
\end{itemize}

\clearpage
\begin{center}
($\star$ Forward calculation in our previous toy example: 
From the bottom to top.) \\
\hspace*{1in}\\
\begin{small}
\hspace{.1in}\\
$y_1^1(\mu) = x_1(\mu)$, \hspace{.1in} $y_2^1(\mu) = x_2(\mu)$, 
\hspace{.1in}
$y_3^1(\mu) = x_3(\mu)$, \hspace{.1in} $y_4^1(\mu) = x_4(\mu)$.\\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\
$h_1^2(\mu)=w_{11}^1\cdot y_1^1+w_{12}^1\cdot y_2^1+w_{13}^1\cdot y_3^1
           +w_{14}^1\cdot y_4^1$ 
\hspace{.2in} from (\ref{eq:fan-in})\\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\
similarly $h_2^2(\mu)$.\\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\
$y_1^2 = f(h_1^2(\mu))$
\hspace{.2in} from (\ref{eq:local-output})\\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\
similarly $y_2^2(\mu)$. \\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\
$h_1^3(\mu) = w_{11}^2 \cdot y_1^2 + w_{12}^2 \cdot y_2^2$
\hspace{.2in} from (\ref{eq:fan-in}) again\\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\
similarly $h_2^3(\mu)$ \hspace{.2in}and\hspace{.2in} $h_3^3(\mu)$.\\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\
$y_1^3 = f(h_1^3(\mu))$
\hspace{.2in} from (\ref{eq:local-output}) again \\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\
similarly $y_2^3(\mu)$ \hspace{.2in}and\hspace{.2in} $y_3^3(\mu)$.\\
\end{small}
\clearpage
($\star$ Backward calculation in our previous toy example:
From the top to bottom.)\\
\hspace*{1in}\\
\begin{small}
\hspace*{1in}\\
$e_1^{(3)} = y_1^3 - z_1(\mu)$
\hspace{.2in} from (\ref{eq:error})\\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\
similarly $e_2^{(3)}(\mu)$ \hspace{.2in}and\hspace{.2in} $e_3^{(3)}(\mu)$. \\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\
$\delta_1^3(\mu) = e_1^{(3)} \cdot f^{\prime} (h_1^3(\mu))$
\hspace{.2in} from (\ref{eq:delta})\\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\
similarly $\delta_2^3(\mu)$  \hspace{.2in}and\hspace{.2in} 
$\delta_3^3(\mu)$.\\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\
$e_1^2({\mu}) = \delta _1^3 (\mu) \cdot w_{11}^2
              + \delta _2^3 (\mu) \cdot w_{21}^2
              + \delta _3^3 (\mu) \cdot w_{31}^2$ \\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\ 
similarly $e_2^2({\mu})$\hspace{.2in} from (\ref{eq:error-propagated}).\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\
$\delta_1^2(\mu) = e_1^2 (\mu) \cdot f^{\prime} (h_1^2(\mu))$
\hspace{.2in} from (\ref{eq:next-delta})\\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\
similarly $\delta_2^2(\mu)$.\\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\
$e_1^1({\mu}) = \delta _1^2 (\mu) \cdot w_{11}^1
              + \delta _2^2 (\mu) \cdot w_{21}^1$ \\
$e_2^1({\mu}) = \delta _1^2 (\mu) \cdot w_{12}^1
              + \delta _2^2 (\mu) \cdot w_{22}^1$ \\
$e_3^1({\mu}) = \delta _1^2 (\mu) \cdot w_{13}^1
              + \delta _2^2 (\mu) \cdot w_{23}^1$ \\
$e_4^1({\mu}) = \delta _1^2 (\mu) \cdot w_{14}^1
              + \delta _2^2 (\mu) \cdot w_{24}^1$ \\
\hspace{.2in} from (\ref{eq:error-propagated}) again\\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\
$\delta_1^1(\mu) = e_1^1 (\mu) \cdot f^{\prime} (h_1^1(\mu))$
\hspace{.2in} from (\ref{eq:next-delta}) again\\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\
similarly $\delta_2^1(\mu)$, \hspace{.1in}$\delta_3^1(\mu)$, \hspace{.1in}
$\delta_4^1(\mu)$. \\
\end{small}
\end{center}

%---------------------------------------------------------------------
\clearpage
\noindent
$\bullet$ Rationale\\

\noindent
$\star$ Thought Experiment: 1-D weight
\begin{figure}[bhtp]
 \begin{center}
   \epsfile{file=function.eps,width=18cm,height=12cm}
 \end{center}
\end{figure}

\noindent
Modification:
\begin{equation}
w^{\mbox{\small{new}}} = w^{\mbox{\small{old}}} + \triangle w
\end{equation}
where
\begin{equation}
\triangle w = - \epsilon \cdot 
                    \frac{dD}{dw} \vert _{w = w^{\mbox{\tiny{old}}}}
\end{equation}

\noindent
means that starting from $w_0$, $w$ gradually approaches the point 
where $D$ takes a minimum value with $\delta w$ being decreased. 

\clearpage
\noindent
$\star$ An example: XOR (revisited)\\

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

\noindent
In this example, 
\begin{eqnarray}
\nonumber
D  &=& \frac{1}{2} \{{e_1^{(3)}}\}^2 \\
\nonumber
   &=& \frac{1}{2} \{ y_i^{(3)} - z_i\}^2\\
\nonumber
   &=& \frac{1}{2} \{(f(h^3_i) - z_i\}^2\\
\nonumber
   &=& \frac{1}{2}\{ f (w^2_{11}\cdot y^2_1 + w^2_{12}\cdot y^2_2)
                             -z_1\}^2 \\
\nonumber
   &=& \frac{1}{2}\{ f (w^2_{11}\cdot f(h^2_1) + w^2_{12}\cdot f(h^2_2)
                             -z_1\}^2 \\
\nonumber
   &=& \frac{1}{2}\{ f (w^2_{11} \cdot 
                         f(w^1_{11}\cdot y^1_1 + w^1_{12}\cdot y^1_2) 
                      + w^2_{12}\cdot 
                         f(w^1_{21}\cdot y^1_1 + w^1_{22}\cdot y^1_2)
                             -z_1\}^2 \\
\nonumber
   &=& \frac{1}{2}\{ f (w^2_{11} \cdot 
                         f(w^1_{11}\cdot x_1 + w^1_{12}\cdot x_2) 
                      + w^2_{12}\cdot 
                         f(w^1_{21}\cdot x_1 + w^1_{22}\cdot x_2)
                             -z_1\}^2 \\
\nonumber
\end{eqnarray}
You can see that $D$ is a function of only all the weights
(6-D in this case).


\clearpage
\noindent
$\star$ Where are the definitions of $\delta^r_j$ and $e^{r-1}_j$
in (\ref{eq:next-delta}) and (\ref{eq:error-propagated}) from?\\

\noindent
We have studied that
\begin{eqnarray}
D  &=& \frac{1}{2} \sum_{i=1}^{N} {e_i}^2 \\
   &=& \frac{1}{2} \sum_{i=1}^{N} (y_i - z_i)^2\\
   &=& \frac{1}{2} \sum_{i=1}^{N} (f(h^L_i) - z_i)^2
\end{eqnarray}
where
\begin{equation}\label{eq:four}
h_i^{r+1} = \sum_{k=1}^{k_r} w_{ik}^r \cdot y_k^r
\end{equation}
So, $D$ is a function of all the $w_{ik}^r$ and 
\begin{equation}\label{eq:five}
\frac{\partial D}{\partial w_{jk}^r} = 
\frac{\partial D}{\partial h_j^{r+1}} \cdot
\frac{\partial h_j^{r+1}}{\partial w_{jk}^r}
\end{equation}
holds. From (\ref{eq:four})
\begin{equation}\label{eq:six}
\frac{\partial h_j^{r+1}}{\partial w_{jk}^r} = y^r_k
\end{equation}
and we put
\begin{equation}\label{eq:seven}
\delta^{r+1}_j \equiv \frac{\partial D}{\partial h_j^{r+1}}
\end{equation}
Since $D$ is a function of $h^L_i$ and
\begin{equation}\label{eq:eight}
h^{r+1}_i = \sum^{k_r}_{k=1} w^r_{ik}f(h^r_k),
\end{equation}
recursive use of this equation $D$ can be expressed as a function of
\begin{displaymath}
\sum^{k_r}_{k=1} w^r_{ik}f(h^r_k)
\end{displaymath}
for any $r$. So $\delta^{r-1}_i$ is defined as
\begin{equation}
\delta^{r-1}_i \equiv \frac{\partial D}{\partial h^{r-1}_i} 
   = \sum^{k_r}_{i=1}\frac{\partial D}{\partial h^{r-1}_k}\cdot
                       \frac{\partial h^{r}_k}{\partial h^{r-1}_k}
   = \sum^{k_r}_{i=1}\delta^r_k \cdot
                       \frac{\partial h^{r}_k}{\partial h^{r-1}_k}\\
\end{equation}
Here,
\begin{equation}
\frac{\partial h^{r}_k}{\partial h^{r-1}_k} 
   = \frac{\partial \Biggl({\displaystyle \sum^{k_{r-1}}_{m=1}}
                                     w^r_{km} \cdot f(h^{r-1}_m) \Biggl)}
            {\partial h^{r-1}_k} \\
   = w^r_{kj} \cdot f^{\prime}(h^{r-1}_j)
\end{equation}
Hence,
\begin{equation}
\delta^{r-1}_i = \sum^{k_r}_{k=1} \delta^r_k \cdot w^r_{kj} \cdot
                 f^{\prime}(h^{r-1}_j)
\end{equation}
In conclusion, if we define
\begin{equation}
e^{r-1}_j = \sum^{k_{r}}_{k=1} \delta^r_k \cdot w^r_{kj}
\end{equation}
we obtain
\begin{equation}
\delta^{r-1}_j = e^{r-1}_j \cdot f^{\prime}(h^{r-1}_j)
\end{equation}


%---------------------------------------------------------------------
\clearpage
\noindent
$\Box$ {\bf Linear Transformation}\\
\hspace*{2in}--- to reduce number of features.\\
\hspace*{1in}\\
$\bullet$ {\bf Discrete Fourier Transform (DFT)}\\
\begin{equation}
y(k)=\frac{1}{\sqrt{N}}\sum^{N-1}_{n=0}x(n)\exp(-j\frac{2\pi}{N}kn)
\end{equation}

\indent
$\cdot$ Inverse DFT
\begin{equation}
x(n)=\frac{1}{\sqrt{N}}\sum^{N-1}_{k=0}y(k)\exp(j\frac{2\pi}{N}kn)
\end{equation}

\hspace*{1in}\\
\hspace*{1in}\\

\begin{itemize}
\item[-] DFT transforms $x(0),x(1),\cdots, x(N-1)$ to 
                        $y(0),y(1),\cdots, y(N-1)$.
\item[-] For example, we can send transformed data {\bf y} instead of
         real data {\bf x}.
\item[-] The number of data is not reduced directly, but usually
         most of the energy lies in the low-frequency region.
\item[-] Matrix form of the transformation e.g. $N=4$
\begin{eqnarray}
\nonumber
\frac{1}{2} \left(
\begin{array}{rrrr}
1 &  1 &  1 &  1 \\
1 &  j & -1 & -j \\
1 & -1 &  1 & -1 \\
1 & -j & -1 &  j \\
\end{array}
\right)
\end{eqnarray}
\end{itemize}

\hspace*{1in}\\
\hspace*{1in}\\
\noindent
$\bullet$ {\bf Kalhunen-Loeve Transform (KL)}\\
\hspace*{1in}\\
K-L Transform is calculated  from the correlation matrix $R$ of the data,
so that the $n$-th raw is the eigen vector of $R$ corresponding to the
$n$-th largest eigen value.

\hspace*{1in}\\
\begin{excersise}
Obtain the K-L Transform for the correlation matrix:
\begin{eqnarray}
\nonumber
R = \left(
\begin{array}{rrr}
 0.3 &  0.1 &   0.1 \\
 0.1 &  0.3 &  -0.1 \\
 0.1 & -0.1 &  0.3 \\
\end{array}
\right)
\end{eqnarray}
\end{excersise}

\clearpage
\noindent
$\bullet$ {\bf Hadamar Transform:}
\begin{itemize}
\item[$\cdot$] For a $2^n$-dimensional vector $\mbox{\bf x}$ 
               ($2^n$ feature vector), the transform and its inverse 
               transform are:
\begin{equation}
\mbox{\bf y} = H_n \mbox{\bf x}, \hspace{.3in} 
\mbox{\bf x} = H_n \mbox{\bf y}
\end{equation}

\item[]where
\begin{equation}
H_n = H_1 \otimes H_{n-1}
\end{equation}
\item[]and
\begin{eqnarray}
H_1 = \frac{1}{\sqrt 2} \left(
\begin{array}{rr}
1 &  1 \\
1 & -1 \\
\end{array}
\right)
\end{eqnarray}

\item[]Here $\otimes$ denotes the Kronecker product 
       for two matrices:\footnote{\noindent for example, if
\begin{eqnarray}
A = \left(
\begin{array}{cc}
1 &  2 \\
3 &  4 \\
\end{array}
\right)
\end{eqnarray}
and
\begin{eqnarray}
B = \left(
\begin{array}{cc}
5 &  6 \\
7 &  8 \\
\end{array}
\right)
\end{eqnarray}
\item[]then we define
\begin{eqnarray}
A \otimes B = \left(
\begin{array}{cccc}
 5 &  6  & 10 & 12\\
 7 &  8  & 14 & 16\\
15 & 18  & 20 & 24\\
21 & 24  & 28 & 32\\
\end{array}
\right)
\end{eqnarray}
}
\begin{equation}
[A \otimes B]_{ij} = A_{ij}B
\end{equation}
\end{itemize}

\hspace*{1in}\\
\hspace*{1in}\\
\noindent
$\bullet$ {\bf Haar Transform:}
\begin{itemize}
\item[$\cdot$]For a $2^n$-dimensional vector $\mbox{\bf x}$:
\begin{itemize}
\item[(1)] Define Haar function $h_k(z)$, which is continuous and 
           are defined in $[0,1]$ as follows:
   \begin{itemize}
   \item[-] Decompose $k$ into two integers $p$ and $q$, such that
      \begin{equation}
         k=2^p+q-1, \hspace{.3in} k=0,1, \cdots, L-1
      \end{equation}
   \item[]which is unique when
      \begin{eqnarray}
         \left\{
         \begin{array}{ll}
         q=0 \hspace{.2in} \mbox{or} \hspace{.2in} 1        
                          & \hspace{.2in}\mbox{if}\hspace{.2in}p=0\\
         0 \le p \le n-1, \hspace{.2in} 0 < q \le 2^p    
                          & \hspace{.2in}\mbox{if}\hspace{.2in}p \ne 0\\
         \end{array}
         \right.
      \end{eqnarray}
   \item[-] then Haar functions are
      \begin{equation}
         h_0(z) \equiv h_{00}(z) = \frac{1}{\sqrt L}
      \end{equation}
           and
      \begin{eqnarray}
         h_k(z) \equiv h_{pq}(z) = \frac{1}{\sqrt L} \left\{ 
      \begin{array}{cl}
         2^{\frac{p}{2}} & 
         \mbox{if } \frac {q-1}{2^p}  \le z < \frac{q-\frac{1}{2}}{2^p}\\
                    - 2^{\frac{p}{2}} & 
         \mbox{if } \frac{q-\frac{1}{2}}{2^p} \le z < \frac{q}{2^p}   \\
                    0                 &
         \mbox{otherwise in } [0,1]
         \end{array}
         \right.
         \end{eqnarray}
\item[(2)] The $k$-th raw of the Haar transform matrix 
           of order $L=2^n$ is:
      \begin{displaymath}
         z=\frac{m}{L}, \hspace{.3in} m=0,1,2, \cdots L-1.
      \end{displaymath}
   \end{itemize}
\end{itemize}
\end{itemize}

\hspace*{1in}\\
\hspace*{1in}\\
\begin{excersise} 
Obtain the 8 $\times$ 8 transform matrix.
\end{excersise}
\begin{center} \underline{\hspace*{7in}} \\ \end{center}
\noindent
$\cdot$ An example of $n=3$, that is, $L=8$.
\begin{equation}
k=2^p+q-1, \hspace{.3in} k=0,1, \cdots, 7
\end{equation}

where
\begin{eqnarray}
\left\{
\begin{array}{ll}
q=0 \hspace{.2in} \mbox{or} \hspace{.2in} 1        
                          & \hspace{.2in}\mbox{if}\hspace{.2in}p=0\\
0 \le p \le 2, \hspace{.2in} 0 < q \le 2^p    
                          & \hspace{.2in}\mbox{if}\hspace{.2in}p \ne 0.\\
\end{array}
\right.
\end{eqnarray}

So,
\begin{table}[hbtp]
\begin{center}
\begin{tabular}{c c c} \hline \hline
p=0           & q=0         & k=0      \\
\hspace{.1in} & q=1         & k=1      \\ \hline
\hspace{.1in} & $(0<q\le2)$ & $(k=1+q)$\\
p=1           & q=1         & k=2      \\
\hspace{.1in} & q=2         & k=3      \\ \hline
\hspace{.1in} & $(0<q\le4)$ & $(k=3+q)$\\
p=2           & q=1         & k=4      \\
\hspace{.1in} & q=2         & k=5      \\
\hspace{.1in} & q=3         & k=6      \\
\hspace{.1in} & q=4         & k=7      \\ \hline \hline
\end{tabular} 
\end{center}
\end{table}

Hence,
\begin{table}[hbtp]
\begin{center}
\begin{tabular}{c c c c c c c c c}   \hline \hline
k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\
p & 0 & 0 & 1 & 1 & 2 & 2 & 2 & 2 \\
k & 0 & 1 & 1 & 2 & 1 & 2 & 3 & 4 \\ \hline \hline
\end{tabular} 
\end{center}
\end{table}

Then the Haar functions are:
\begin{eqnarray}
h_1(z) \equiv h_{01}(z) = \frac{1}{\sqrt 8} \left\{ 
\begin{array}{rlc}
 1 & \hspace{.2in}\mbox{if } & -1         \le z < \frac{1}{2}\\
-1 & \hspace{.2in}\mbox{if } & \frac{1}{2}\le z < 1          \\
\end{array}
\right.
\end{eqnarray}
\begin{eqnarray}
h_2(z) \equiv h_{11}(z) = \frac{1}{\sqrt 8} \left\{ 
\begin{array}{rlc}
 \sqrt 2 & \hspace{.2in}\mbox{if }
           \hspace{.2in} 0          \le z < \frac{1}{4}\\
-\sqrt 2 & \hspace{.2in}\mbox{if }
           \hspace{.2in} \frac{1}{4}\le z < \frac{1}{2}\\
       0 & \hspace{.2in}\mbox{otherwise in } [0,1]
\end{array}
\right.
\end{eqnarray}
\begin{eqnarray}
h_3(z) \equiv h_{12}(z) = \frac{1}{\sqrt 8} \left\{ 
\begin{array}{rlc}
 \sqrt 2 & \hspace{.2in}\mbox{if }
           \hspace{.2in} \frac{1}{2} \le z < \frac{3}{4}\\
-\sqrt 2 & \hspace{.2in}\mbox{if }
           \hspace{.2in} \frac{3}{4} \le z < 1          \\
       0 & \hspace{.2in}\mbox{otherwise in } [0,1]
\end{array}
\right.
\end{eqnarray}
\begin{center}{\Huge $\cdots\cdots$}\end{center}
\begin{eqnarray}
h_7(z) \equiv h_{24}(z) = \frac{1}{\sqrt 8} \left\{ 
\begin{array}{rlc}
 2 & \hspace{.2in}\mbox{if }
           \hspace{.2in} \frac{3}{4} \le z < \frac{7}{8}\\
-2 & \hspace{.2in}\mbox{if }
           \hspace{.2in} \frac{7}{8} \le z < 1          \\
 0 & \hspace{.2in}\mbox{otherwise in } [0,1]
\end{array}
\right.
\end{eqnarray}

and
\begin{table}[hbtp]
\begin{center}
\begin{tabular}{c c c c c c c c c}   \hline \hline
$h_0(z)$ & 1 & 1 & 1 & 1 &   1 &   1 &   1 &   1           \\
$h_1(z)$ & 1 & 1 & 1 & 1 & --1 & --1 & --1 & --1           \\
$h_2(z)$ & $\sqrt 2$ & $\sqrt 2$ & $-\sqrt 2$ & $-\sqrt 2$ 
         & 0         & 0         & 0          & 0          \\
$h_3(z)$ & 0         & 0         & 0          & 0 
         & $\sqrt 2$ & $\sqrt 2$ & $-\sqrt 2$ & $-\sqrt 2$ \\
$h_4(z)$ & 2 & --2 & 0 &   0 & 0 &   0  & 0 &   0          \\
$h_5(z)$ & 0 &   0 & 2 & --2 & 0 &   0  & 0 &   0          \\
$h_6(z)$ & 0 &   0 & 0 &   0 & 2 & --2  & 0 &   0          \\
$h_7(z)$ & 0 &   0 & 0 &   0 & 0 &   0  & 2 & --2          \\ \hline \hline
\end{tabular} 
\end{center}
\end{table}

Since
\begin{equation}
H_{ij}=\frac{1}{\sqrt L}h_j(\frac{j}{L}),
\end{equation}

we obtain
\begin{eqnarray}
H =
\left(
\begin{array}{cccccccc}
1 &   1 & 1 &   1 &  1 &  1 &  1 &  1     \\
1 &   1 & 1 &   1 & -1 & -1 & -1 & -1     \\
\sqrt 2 & \sqrt 2 & -\sqrt 2 & -\sqrt 2 & 
        & 0       & 0        & 0          \\
0       & 0       & 0        & 0        & 
\sqrt 2 & \sqrt 2 & -\sqrt 2 & -\sqrt 2    \\
2 & -2 & 0 &  0 & 0 &  0  & 0 &  0        \\
0 &  0 & 2 & -2 & 0 &  0  & 0 &  0        \\
0 &  0 & 0 &  0 & 2 & -2  & 0 &  0        \\
0 &  0 & 0 &  0 & 0 &  0  & 2 & -2        \\
\end{array}
\right)
\end{eqnarray}



\end{large}
\end{document}
