\chapter{Classification}	\label{sec:classification}
\thispagestyle{empty}

  
Classification is the last stage of a recognition system. Given a patch with -~ho\-pefully~- one centered object, a feature vector is extracted from
the image. In training, the system learns how to distinguish among features of images belonging to different categories. In test phase, according to the
test image feature, a decision is made. If the object in the image is considered a particle of interest, then its class is also identified, 
otherwise it is discarded because the measurement does not match any training model.

This chapter begins with the description of training and
test stage of a Bayesian classifier using Gaussian mixture models. This classifier gave the best performance with an error rate of 7.6\% on
urine database and 10.2\% on ``pure'' pollen database. \\
However, following sections present slightly different approaches. First, two ways of combining both kinds of features already presented in the previous chapter will be discussed. 
Second, a customized version of AdaBoost.M1, an algorithm to boost the performance of any
classifier, will be defined. 
Finally, a classifier based on support vector machines (SVM) will be introduced. 

This chapter will conclude with experiments to
optimize the system and some final experiments covering all the data set. 


\section{Mixture of Gaussians} \label{sec:mog}

This classifier is the simplest and the most powerful system we developed. With the only exception of the classifier using SVM, all the
other classifiers are based on it. 

We now describe its two main stages: training and test.

\subsection{Training}

In training phase, we can model the distribution of feature vectors belonging to a certain class with a mixture of Gaussians (MoG) \cite{libro:Bishop}. 
If the number of categories is $K$, then we have to estimate $K$ MoGs. The estimation is done applying expectation maximization (EM) algorithm 
\cite{libro:Bishop}. \\
Generally, our aim is to estimate the \emph{class-conditional distribution} $f({\xv} \mid C_k)$, that is the probability density function (pdf) 
of the data, given our knowledge that they belong to a certain class $C_k$. 
In order to simplify the notation we now make implicit the class
condition. However, it is a straightforward generalization to consider it.\\
The mixture model decomposes the pdf of the data $f({\xv})$ in a linear combination of $M$ component densities $f({\xv} \mid j)$ in the form

\begin{equation} \label{q:mog}
f({\xv}) = \sum_{j=1}^{M} f({\xv} \mid j) P(j)
\end{equation}

The mixing parameters $P(j)$, also called \emph{priors probabilities}, satisfy the constraints

\begin{eqnarray}
\sum_{j=1}^M P(j) = 1 \\ 
0 \leq P(j) \leq 1
\end{eqnarray}

moreover, the conditional probability density functions verify

\begin{equation}
\int  f({\xv} \mid j) d{\xv} = 1
\end{equation}

An important property of mixture models is that they can approximate any continuous pdf to arbitrary accuracy with a proper choice of number
of components and parameters of the model.\\
In our system, we use mixture of Gaussians. Thus, we have to choose the number of components and the structure of their covariance matrix.
The best choice of parameters is found experimentally. We make use of a package for MATLAB called NETLAB in which there are functions to
estimate the MoG by the application of EM algorithm. 

The goal of training is to build for each class a model of the distribution of the feature vectors belonging to the class images. 
This model is achieved using MoG and it describes the pdf of the class feature vectors. 

\subsection{Test}

Given a test image, we compute its feature
vector ${\fv}$.
Then, we apply the Bayes' rule.\\
We are interested on the probability of the class $C_k$ given the test data $P[ C_k \mid {\xv} ]$, because we want to apply the following
decision rule:

\begin{equation}
x \mapsto r(x) = argmax_k {P[C_k \mid {\xv}]}
\end{equation}

The extension of Bayes' rule to continuous conditions assure that 

\begin{equation} \label{eq:Bayes}
P[C_k \mid {\xv}] = \frac{f({\xv} \mid C_k) P[C_k]}{f({\xv})} = \frac{f({\xv} \mid C_k) P[C_k]}{\sum_{j=1}^M f({\xv} \mid C_j) P[C_j]}
\end{equation}

where $f$ is pdf and $P$ is probability. So, in hypothesis of equal distribution for the class probabilities, $P[C_k] = 1/K$ for
$k=1,\cdots,K$, we can simplify

\begin{equation} \label{eq:Bayes2}
 P[C_k \mid {\xv}] = \frac{f({\xv} \mid C_k)}{\sum_{j=1}^M f({\xv} \mid C_j)}
 \end{equation}
 
Moreover, we can observe that $\max P[C_k \mid {\xv}]$ is obtained  for the same $k$ of $\max f({\xv} \mid C_k)$ because the factor 
$\sum_{j=1}^M f({\xv} \mid C_j)$ is constant for all $j$. The term $f({\xv} \mid C_k)$ is called \emph{likelihood} because it is a conditional
probability density function with implicit dependence on the model parameters. Because our decision rule looks for
the maximum of this term, it is referred as \emph{maximum likelihood} decision rule.

We also add to this framework a test. When we train, we collect for each class its resolution mean and 
standard deviation, $m_{r_k}$ and
$\sigma_k$. Then in test, we compute the likelihood of the test data given the class $C_k$ only if the following condition holds:

\begin{equation}	\label{eq:testrisol}
r \in [m_{r_k} - N \sigma_k,m_{r_k} + N \sigma_k]
\end{equation}

where, $r$ is the resolution of the test image and $N$ is a parameter to be chosen; in our experiments we chose $N = 3$.\\
This test is mainly done to save time avoiding useless computation. If an image resolution is out of the range of every class, then it is not
classified and put in an \emph{unknown} class.


\section{Combination of features}  

We will show in the experimental part that the previous classifier using features based on principal component analysis and on local jets
gives good results with an error rate below 15\% on urine database. In this section, we present two methods to combine these features. \\
If you look at the confusion matrices of the classifier working with these features (see \figref{Jan02CMonFullDataSetLJ} and 
\figref{Jan02CMonFullDataSetIPCSPC}), you can notice a certain correlation among
misclassifications which suggests dependence between the two kinds of feature. 

However, we can simplify the problem of feature combination assuming \emph{independence} between the two sets. If we do not make any
hypothesis between these features we have to solve the more general problem of combination of experts' response.
  
\subsection{Independence hypothesis}

Given an image, we apply the two techniques described in the previous chapter to extract features based on principal component analysis 
${\xv}_1$ and on local jets ${\xv}_2$. 
In hypothesis of independence between these two vectors, we can write the class conditional density function as

\begin{equation} \label{eq:indip}
f({\xv}_1,{\xv}_2 \mid C_i) = f({\xv}_1 \mid C_i) f({\xv}_2 \mid C_i)
\end{equation}

Thus, as we did in the previous section, we look for the maximum likelihood of the test image feature to make a decision and thanks to
eq. (\ref{eq:indip}), we can write

\begin{equation}
P[C_i \mid {\xv}_1,{\xv}_2] \mbox{  is proportional to  } f({\xv}_1 \mid C_i) f({\xv}_2 \mid C_i)
\end{equation}

To summarizee, with reference to the classifier using MoG we make two separate trainings using the two set of features and two separate tests.
Then, we multiply the class conditional densities and we choose the class with highest value.


\subsection{Without hypothesis}

This approach was suggested by the good performance achieved modeling data with MoG. We now do not make any assumption on features.\\
We divide the training set into two sets. The first one is used to train separately the classifier using the two different kinds of features
and so to get $f({\xv}_i \mid C_j, \theta_n)$, where ${\xv}$ is a feature vector and $\theta_n$ is the model used. We refer to model as the
technique for feature extraction, namely the method based on PCA or local jets. Then, for each image of the second training set we compute the vector

\begin{equation} \label{eq:vettprob}
(P[C_1 \mid data, \theta_{pca}],\cdots ,P[C_1 \mid data, \theta_{lj}],\cdots)
\end{equation}

and we model with a MoG these probability vectors of all the images belonging to each class. 

In test, given an image we compute the two feature vectors and the vector of probabilities of eq. (\ref{eq:vettprob}). Then, we make a decision
by computing the maximum likelihood of this vector in the last training model. 

In this way, we take into account the performance of each classifier and implicitly we give more weight to the ``expert's'' response 
with better performance in the given class (even if in test we do not know the true class to which the particle belongs).

The drawback of this method, is that it requires a lot of training data because it needs to build MoG models. Because our data set is quite 
small, the parameter estimation cannot be very precise and thus, the performance is not improved (see the experimental section). 


\section{Boosting}

We studied the multi-class extension of AdaBoost called ``AdaBoost.M1'', \cite{paper:AdaBoost} \cite{paper:AdaBoostM1}.\\
Given a weak learner, let be $X$ the set of input data and $Y$ the set of the possible labels for the samples in $X$. The learner receives
examples $(x_i,y_i)$, with $x_i\in X$ and $y_i\in Y$. These examples are chosen randomly according to some fixed but unknown distribution 
$P$ on $X \times Y$. The goal is to learn to predict the label $y$ given an istance $x$. We assume that the sequence of $N$ training 
examples is $(x_1,y_1),...,(x_N,y_N)$. 
At each iteration or round, the weak learner generates hypothesis which assigns to each istance one of the $K$
possible labels. At the end, the boosting algorithm presents an output hypothesis $h_f : X \rightarrow Y$ with lower error rate. 
It is required that each weak hypothesis has prediction error less than 1/2\footnote{The error-correcting output 
code technique \cite{paper:AdaBoostECOC} has not this constraint but it is slightly more difficult. Our classifier has an error rate below
15\% and so, this constraint is not a problem.}.\\
We define for any predicate $p$, $\vdash p \dashv$ to be 1 if $p$ holds and 0 otherwise.\\
We summarize the general algorithm in pseudo-code in \figref{AdaBoostM1orig}. 

\begin{figure}[htbp]
\centering
\input{./figure/AdaBoostM1orig.tex}
\caption{Pseudocode of algorithm AdaBoost.M1.}
\label{figure:AdaBoostM1orig}
\end{figure}


Let's try to boost the performance of the classifier described in par. \ref{sec:mog} with reference to the previous algorithm.\\  
We have to decide how to provide our classifier with the distribution ${\pv}$ at each round. 
We could go inside EM algorithm and modify the weights
of the sum in the log-likelihood computation. 
However, it seems simpler to extract from each class set a number of images proportional to the
class weight. Note that in this way, ${\pv}$ becomes a distribution over the classes and not any more over the single training images. 
This method has also another drawback because the MoG estimation needs a lot of examples to find convergence. So, we have to reduce the
number of training images belonging the best classified categories and on the other hand, to keep a sufficient number for the MoG
estimate.
Thus, our implementation  of AdaBoost.M1 is a slightly different version. 

We choose the weights in a way that allows to the worst classified class to train on all the maximum number of images while the best
classified class has available a minor number of images; however this number is sufficient for the estimate of parameters in the MoG. In
particular, at each round the minimum weight is decreased if the class is still the best classified, while the maximum weight is always equal
to the maximum if the class is still the worst classified. We show the pseudo-code of this customized version of AdaBoost.M1 in
\figref{AdaBoostM1cust}.

\begin{figure}[htbp]
\centering
\input{./figure/AdaBoostM1cust.tex}
\caption{Pseudocode of modified version of algorithm AdaBoost.M1.}
\label{figure:AdaBoostM1cust}
\end{figure}


In the experimental section, we will show that this method is able to achieve a slightly better performance than the one of the basic
classifier.

\section{Support Vector Machines} \label{sec:svm}

The support vector machine (SVM) approach does not attempt to model the distribution of features but it works directly on them. \\
Let us start considering the simplest case of a \emph{linear machine} trained on \emph{separable data}, \cite{book:SVM} \cite{paper:SVM}. 
The training input data are a set of labeled features $\{ {\xv}_i,y_i \}$, $i=1,\cdots,l$, $y_i \in \{ -1,1 \}$, ${\xv}_i \in \Bbb{R}^d$. 
Suppose we have some hyperplane which separates the positive from the negative examples. The points ${\xv}$ which lie on the hyperplane satisfy
${\wv} \cdot {\xv} + b = 0$, where ${\wv}$ is the normal to the hyperplane. Let be $d_+$ and $d_-$ the shortest distance from the separating
hyperplane to the closest positive and negative example respectively. For the linearly separable case, the support vector algorithm looks for
the separating hyperplane with the largest \emph{margin}, defined as $d_+ + d_-$. Thus we can write that each training point satisfy:

\begin{eqnarray}
{\xv}_i \cdot {\wv} + b \geq +1, \hspace{.5cm} \mbox{  for  } y_i = +1 \nonumber \\
{\xv}_i \cdot {\wv} + b \leq +1, \hspace{.5cm} \mbox{  for  } y_i = -1 
\end{eqnarray}

that is,

\begin{equation} \label{eq:planesvm}
y_i({\xv}_i \cdot {\wv} + b) - 1 \geq 0 \mbox{    } \forall i
\end{equation}

Choosing a proper scale for ${\wv}$ and $b$, we can have points for which the equality in eq. (\ref{eq:planesvm}) holds and $d_+,d_- = 1/
\|{\wv}\|$; these points are called \emph{support vectors}. Their removal would change the solution and they live in the hyperplanes $H_1: 
{\xv}_i \cdot {\wv} + b = +1, H_2: {\xv}_i \cdot {\wv} + b = -1$. No training point falls between them.\\
It can be shown that in order to find ${\wv}$ and $b$, we have to solve a quadratic optimization problem. Once these parameters are found,
given a test point ${\xv}$, we simply determine on which side of the decision boundary ${\xv}$ lies and assign the corresponding class label.\\

If the training data are not separable, we have to introduce positive \emph{slack} variables $\xi_i$, $i=1,\cdots,l$ in the previous
equations which become:

\begin{flushleft}
\begin{eqnarray}
{\xv}_i \cdot {\wv} + b \geq +1 - \xi_i, \hspace{.5cm} \mbox{  for  } y_i = +1 \nonumber \\
{\xv}_i \cdot {\wv} + b \leq +1 + \xi_i, \hspace{.5cm} \mbox{  for  } y_i = -1  \nonumber \\
\xi_i \geq 0 \forall i
\end{eqnarray}
\end{flushleft}

Thus, for an error to occur, the corresponding $\xi_i$ must exceed unity, so $\sum_i \xi_i$ is an upper bound on the number of training
errors. It can be shown \cite{paper:SVM} that the quadratic programming problem can be solved introducing a new user defined parameter 
$C$ in order to assign the desired penalty to errors. An interpretation of C and support vectors is that only support vectors exert a force
on the decision sheet and $C$ is an upper bound on this force.

Because a support vector machine only realizes a linear classifier, non-separable data are projected in a very high dimensional feature space in which
the data become separable, and this means that in the original feature space the classifier becomes highly non-linear.\\
The only way in which training data appear in the optimization problem is in the form of dot products, ${\xv}_i \cdot {\xv}_j$. Then, we can
map the data in another (generally higher dimensional space) $H$ using the function $\Phi$:

\begin{equation}
\Phi: \Bbb{R}^d \mapsto H
\end{equation}

Now, the training depends only on the data through dot products in $H$, i.e. on $\Phi({\xv}_i) \cdot \Phi({\xv}_j)$. Moreover, we are
interested to find a \emph{kernel function} $K$ such that $K({\xv}_i,{\xv}_j) = \Phi({\xv}_i) \cdot \Phi({\xv}_j)$ in order to use only a
function. \\
The most powerful and simple kernels are:

\begin{itemize}
\item {\bfseries linear}: $K( {\xv}_i,{\xv}_j ) = {\xv}_i \cdot {\xv}_j$
\item {\bfseries polynomial} of order p: $K( {\xv}_i,{\xv}_j ) = ( {\xv}_i \cdot {\xv}_j + 1 )^p$
\item {\bfseries Gaussian radial basis function} (RBF) of parameter $\sigma$: $ K( {\xv}_i,{\xv}_j ) = e^{-\| {\xv}_i - {\xv}_j \| ^2 / {2 \sigma^2}
}$
\end{itemize}

In \figref{esempioSVM}, you find a simple example of binary classification using these kernels for different values of their parameters. 


\begin{figure}[htbp]
\centering
\includegraphics[width=0.9\textwidth]{./figure/esempioSVM.eps}
\caption{Example of classification using SVM for separable and non-separable synthetic data with different choices of kernel. Support vectors are
drawn in red. The decision boundary is more shattered for high values of degree of polynomial kernel, low values of $\sigma$ in RBF kernel, high values of C. A balance between generalization and performance in training set has to be found.}
\label{figure:esempioSVM}
\end{figure}

Finally, we have to discuss how to use this algorithm to solve a multiclass classification problem \cite{paper:svmECOC}\footnote{We could
apply this method also to AdaBoost algorithm.}: we use \emph{error-correcting output codes} technique. \\
Each class is assigned a unique binary string of length $n$ called \emph{codeword}. Then, $n$ binary functions are learned, one for each bit
position in these binary strings. During training for an example of class $i$, the desired outputs of these $n$ binary functions are
specified by the codeword for class $i$. New values ${\xv}$ are classified by evaluating each of the $n$ binary functions to generate an $n$-bit
string $s$. This string is then compared to each of the $k$ codewords, and ${\xv}$ is assigned to the class whose codeword is
closest\footnote{In our experiments, we use Hamming distance.} to the generated string $s$. 

The error-correcting code should satisfy the two properties:
\begin{itemize}
\item each codeword should be well-separated in Hamming distance from each of the other codewords
\item each bit-position function should be uncorrelated with the functions to be learned for the other bit positions
\end{itemize}

For our experiments we derived the error-correcting code by  T. Dietterich's collection of code matrices \cite{sito:ecoc}, see \figref{ecoc}.  
 
\begin{figure}[htbp]
\centering
\input{./figure/ecoc.tex}
\caption{Error-correction codes used in SVM experiments to solve the multiclass classification problem: 12 classes, codewords with 47 bits.}
\label{figure:ecoc}
\end{figure}

We did not implement SVM algorithm but we downloaded \cite{sito:svm} a software in Matlab written by Anton Schwaighofer
(2002). Its main features are:
\begin{itemize}
\item
 Except for the QP solver, all parts are written in plain Matlab.
\item
 Extension to multi-class problems via error correcting output codes is
  included.
\end{itemize}


\section{Experiments}

We divide this last section into two parts. First, we describe the method to tune the parameters 
and then, we show the final results.

\subsection{Tuning}	\label{sec:classexp}

We describe which parameters must be optimized and the optimization method. We will refer to the urine database because the reasoning is the
same for the pollen database.

\subsubsection{MoG}

The classifier using MoG, no matter the kind of feature used, needs to be optimized with respect to the choice of:
\begin{enumerate}
\item dimension of the feature space after application of Fisher's Linear Discriminants
\item number of components in each mixture
\item structure of the covariance matrix of each component
\item initial condition for EM algorithm used to estimate the mixture
\end{enumerate}


In order to achieve the best reliable (and hopefully also the best) result, we procede with a systematic method. 
The urine database has available twelve classes and nearly one thousand images for each category. 
Mucus class has only 546 images, Nhyal 860 and NSE 999. 
We want to work during this optimization with the same number of images in test and training for each class. 
Then, we divide the total number of available images in all classes in two set: 
the first 500 will be used for only training purposes while the complementary set for only test. 
From the former set, we extract randomly 30 images in order to build a validation set. 
All training models will be shown in the following pages, are done on the rest 470 images of training set and the 
evaluation of the performance is done on the validation set. 
Then, when optimal parameters are found, a final test is done on 30 randomly chosen images of the test set.

As you can see from the curves of error rate (see \figref{ERvsParamLJ} and following ones), the performance is strongly 
dependent not only on the number of parameters used in the MoG (see
\tabref{nrparamMoG}) but also on the kind of parameters. 
For example, in previous simulations we found that even if you keep constant the number of parameters, 
the error rate sometimes increases if you choose to increase the dimension of the space instead of increasing
the number of Gaussians 
in the mixture. For this reason, we run a lot of simulations for different values of the feature space dimension. 
While this value is maintained constant, several numbers of components are tried for different structures of covariance matrix 
(spherical, diagonal and full).

In order to estimate a parameter we need at least 3 points. 
In training we use 470 images and so we should stop our search when we reach a number of 150 parameters. 
On the other hand, our analysis wants to be exhaustive and so we try to perform simulations up to 300 parameters. 
However, when we run simulations with spherical covariance matrix, there are usually more then ten Gaussians (the maximum value was 25). 
Unfortunately, EM sometimes does not find convergence for a so high number of Gaussians even if the number of parameters is acceptable. 
Indeed, we checked the starting number of points assigned to each Gaussian by ``k-means'' algorithm and not surprisingly we found 
that some Gaussian has only few points (less than ten) and it is likely that these functions easily collapse in a single point 
or they can give rise to local minima in the error function which may give poor representations of the true distribution. 
Our assessment is strengthened by some warning (probability of data given the model nearly zero) of EM program and by 
the results of our test on the validation set. \\
As you can see, for example, in \figref{ERvsParamLJ} there are some irregularities in the trend of spherical covariance matrix 
because for a high number of Gaussians EM doesn't find a model for one or two classes 
(giving an acceptable global error rate but for those categories the error rate is 100\%!).

When we run experiments for the combination of classifiers we avoid these situations stopping the program at a lower number of 
Gaussians in the spherical case because we are looking for a stable system and we need a reasonable estimate of 
$ P[ C_j \mid data, mod_i ] $.

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.9\textwidth]{./figure/ERvsParamLJ.eps}
\caption{Classifier using MoG and feature based on local jets: 
ER as a function of the parameter number for different choices of feature space dimensions and structure of
covariance matrix.}
\label{figure:ERvsParamLJ}
\end{center}
\end{figure}

The classifier using features based on PCA needs to work with dimensions of space multiple of six because each IPCs is splitted in three 
parts and we require to get the same number of dimensions coming from image and spectrum principal
analysis\footnote{A justification for this choice is given at the end of par. \ref{sec:ipcspc}.}. 
For this reason, the following experiments are done for a number of dimensions equal to 12, 18 and 24.\\
The same argument is applied to the combination of classifiers. \\ 

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.7\textwidth]{./figure/ERvsParam_IPCSPCNL.eps}
\caption{Classifier using MoG and feature based on image and spectrum principal components: 
ER as a function of the parameter number for different choices of feature space dimensions and structure of
covariance matrix.}
\label{figure:ERvsParam_IPCSPCNL}
\end{center}
\end{figure}

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.7\textwidth]{./figure/ERvsParam_combfeat.eps}
\caption{Classifier using MoG and combination of feature in independence hypothesis: 
ER as a function of the parameter number for different choices of feature space dimensions and structure of
covariance matrix.}
\label{figure:ERvsParam_combfeat}
\end{center}
\end{figure}

The combination of classifiers modeling their outcomes needs a special care. Here, we have two trainings. In
previous studies we found that a good MoG for the second training (dummy test to model outcomes) has two
spherical Gaussians in each MoG. 
We use this model to optimize the first training and then with these good values we run another simulation to find good parameters for the second training. This new analysis confirms the previous results.\\
We chose to run the first training on 470 images per class (the full data training set) and then to select from this set 170 images to perform the second training. 

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.7\textwidth]{./figure/ERvsParamTR1_combclass.eps}
\caption{Classifier using MoG and making a combination of experts' response, first training: 
ER as a function of the parameter number for different choices of feature space dimensions and structure of
covariance matrix.}
\label{figure:ERvsParamTR1_combclass}
\end{center}
\end{figure}
  

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.8\textwidth,height=0.4\textwidth]{./figure/ERvsParamTR2_combclass.eps}
\caption{Classifier using MoG and making a combination of experts' response, second training (or modeling of results in dummy test): 
ER as a function of the parameter number for different choices of feature space dimensions and structure of
covariance matrix.}
\label{figure:ERvsParamTR2_combclass}
\end{center}
\end{figure}


\begin{table}[htbp]
\begin{center}
\begin{tabular}{||p{5cm}||*{2}{c|}|}

\hline
features	& gauss.	& dimens.	\\
\hline
\hline
\bfseries local jets & 4 full	& 12 \\
\hline
\bfseries PCA & 3 full & 12 \\
\hline
\bfseries comb. feat. (indep.) & 6 diag. & 18 \\
\hline
\bfseries experts' combination & 2 full & 18 \\
\hline
\hline
\end{tabular}
\end{center}
\caption{Best parameters found for MoG in urine database.}
\label{tab:bestparamclass}
\end{table}


The last set of experiments has the goal to find the optimal initial conditions for EM. 
Our program calls some functions of NETLAB package to estimate the MoG; we use ``gmm'', ``gmminit'' and ``gmmem''. 
The first routine uses the Matlab function ``randn'' (generator of normally distributed random numbers), 
the second one calls ``randn'' and ``rand'' (generator of uniformly distributed random numbers). 
The initial state of these two functions is a vector with two components for ``randn'' and with 35 components for ``rand''. 
So, for each mixture (that is for each class model) we have to find three vectors. 
We run one hundred experiments for each classifier leaving initial conditions free. 
At each iteration, we stored these vectors and the performance on the validation set. At the end, we force the initial state to that 
value which gave the lowest ER on the validation set.\\
Obviously, the number of Gaussians, kind of covariance matrix and number of space dimensions are the ones found in the previous 
simulations.  \\
We show the results of these experiments in the form of scatter plots. 
At each iteration in which a different initial condition was chosen, a training model was estimated and the test was done on 30 images 
per class randomly extracted from the training set, test set and validation set. 
You can note the generally stronger correlation between the test and validation error rate versus test and training error rate.
 
In the classifier which combines the experts' outcomes, 
as you can see in \figref{ScatterPlotsInitCondcombclass} (a similar situation happens also in \figref{ScatterPlotsInitCondIPCSPC}), 
there is no dependence of the performance on the initial conditions of the random number generator. 
We should not be surprised about it since we chose the maximum number of iteration of EM equal to one thousand 
and in this classifier we have to estimate the parameters of only two spherical Gaussians. 
For the classifier using feature based on image and spectrum principal components, three states are possible.

\newpage

\begin{figure}[!htbp]
\begin{center}
\includegraphics[width=0.7\textwidth,height=0.28\textwidth]{./figure/ScatterPlotsInitCondLJ.eps}
\caption{Classifier using MoG and feature based on local jets: 
each point in each scatter plot shows the error rate; 100 experiments were run with different initial conditions of random number generator.}
\label{figure:ScatterPlotsInitCondLJ}
\end{center}
\end{figure}
 
 
\begin{figure}[!htbp]
\begin{center}
\includegraphics[width=0.7\textwidth,height=0.25\textwidth]{./figure/ScatterPlotsInitCondIPCSPC.eps}
\caption{Classifier using MoG and feature based on image and spectrum principal components:
 each point in each scatter plot shows the error rate; 100 experiments were run with different initial conditions of random number
 generator (a lot of points are overlapped). }
\label{figure:ScatterPlotsInitCondIPCSPC}
\end{center}
\end{figure}

  
\begin{figure}[!htbp]
\begin{center}
\includegraphics[width=0.7\textwidth,height=0.25\textwidth]{./figure/ScatterPlotsInitCondcombclass.eps}
\caption{Classifier using MoG and making a combination of experts' response: 
each point in each scatter plot shows the error rate; 100 experiments were run with different initial conditions of random number 
generator (all points are overlapped). }
\label{figure:ScatterPlotsInitCondcombclass}
\end{center}
\end{figure}

\newpage

\subsubsection{AdaBoost}

We considered 500 images from each class and extracted randomly 20 of them for validation. The complementary set is used for the final test.
In \figref{findHypAdaBoost}, the training, validation and test error rates are shown at each round. 
Then, we combined the 10 hypothesis in the final one as suggested in the pseudocode of \figref{AdaBoostM1cust}.

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.8\textwidth,height=0.4\textwidth]{./figure/findHypAdaBoost.eps}
\caption{AdaBoost.M1: test, validation and training error rate as a function of the number of rounds. 
Training done on 480 images, each test on 20 images (randomly chosen).}
\label{figure:findHypAdaBoost}
\end{center}
\end{figure}


\subsubsection{SVM}

The parameters we aim to find are:
\begin{enumerate}
\item kernel type
\item number of dimensions of feature space after reduction with Fisher's Linear Discriminants
\item parameter $C$
\item parameter of kernel, i.e. degree of polynomial kernel or width of Gaussian radial basis function
\end{enumerate}

From our first experiments, it turns out that RBF kernels is able to achieve a lower error rate than polynomial kernel. So, we will refer
only to the results of RBF kernel.

We summarize the results in \tabref{resultSVM1} and following. The experiments are done taking 500 images for each class and extracting (only once) 30 images
for validation purpose.

\begin{table}[htbp]
\begin{center}
\begin{tabular}{||p{2.5cm}||*{7}{c|}|}

\hline
$\sigma$	& D 10	& D 12	& D 14 	& D 16	& D 18	& D 20	& D 22	\\
\hline
\hline
0.25	& 10.83  &  11.67  &  12.78 &   15.00  &  16.94  &  19.17  &  20.28 \\
\hline
0.5	& 9.17  &  \bfseries{8.89}  &  9.17  &  9.44  &  10.56  &  10.00  &  10.83 \\
\hline
1	& 10.83 &   10.83  &  10.00  &  10.56  &  11.67  &  10.56  &  11.11 \\
\hline
1.5	& 11.39  &  11.11  &  11.39  &  12.22  &  12.78  &  11.94  &  12.22  \\
\hline
2	& 11.94  &  12.22  &  12.50  &  13.06  &  13.06  &  13.33  &  13.89 \\
\hline
3	& 14.17  &  13.61  &  13.61  &  14.44  &  14.17 &   15.00  &  14.44 \\
\hline
4	& 15.28  &  14.72  &  15.28  &  15.00  &  15.83  &  15.83  &  14.72 \\
\hline
5	&  16.11  &  15.56  &  15.56  &  16.11  &  16.39  &  16.11  &  17.22 \\
\hline
10	& 18.33  &  16.94  &  18.61  &  18.61  &  18.33  &  18.89  &  18.33 \\
\hline
15	& 20.28  &  18.33 &   18.33  &  18.89  &  19.44  &  19.44  &  20.28 \\ 
\hline
20	& 22.50  &  19.44  &  20.00  &  20.56  &  20.83  &  21.11  &  21.94 \\
\hline
50 	& 26.11  &  23.06 &  24.44  &  25.28  &  27.22  &  28.33  &  28.89 \\
\hline
\hline
\end{tabular}
\end{center}
\caption{SVM with RBF kernel and penalty of errors $C=1$: error rate as a function of the width $\sigma$ and dimension D of feature space. The best performance is highlighted in thick black letters.}
\label{tab:resultSVM1}
\end{table}



\begin{table}[htbp]
\begin{center}
\begin{tabular}{||p{2.5cm}||*{7}{c|}|}
\hline
$\sigma$	& D 10	& D 12	& D 14 	& D 16	& D 18	& D 20	& D 22	\\
\hline
\hline
0.25	& 12.50  &  12.78  &  12.50  &  15.28  &  16.39  &  18.33  &  19.44 \\
\hline
0.5	&  10.83  &  10.00  &  \bfseries{8.61}  &  9.44  &  9.44  &  8.89  &  10.28\\
\hline
1	&  10.00  &  10.56  &  9.72  &  9.72  &  9.44  &  \bfseries{8.61}  &  9.17\\
\hline
1.5	&  11.39  &  10.83  &  11.39  &  10.56  &  11.67  &  10.00  &  9.72 \\
\hline
2	&  11.39  &  11.67  &  11.39  &  11.39  &  12.22  &  10.83  &  10.83\\
\hline
3	&  11.67  &  11.39  &  11.94  &  11.94  &  12.22  &  11.67  &  11.94\\
\hline
4	& 11.94  &  11.94  &  12.22  &  13.33  &  12.78  &  12.22  &  12.22\\
\hline
5	&  11.94  &  10.28  &  9.44  &  10.28  &  11.39  &  11.11  &  10.56 \\
\hline
10	&  12.78  &  11.39  &  11.67  &  11.94  &  12.78  &  12.78  &  13.06\\
\hline
15	&  13.33  &  13.06  &  12.78  &  13.89  &  14.17  &  13.89  &  14.72\\ 
\hline
20	&  14.44  &  14.44  &  14.72  &  14.72  &  14.72  &  14.44  &  15.28\\
\hline
50 	&  20.56  &  18.06  &  18.89  &  18.89  &  19.44  &  20.00  &  20.56\\
\hline
\hline
\end{tabular}
\end{center}
\caption{SVM with RBF kernel and penalty of errors $C=5$: error rate as a function of the width $\sigma$ and dimension D of feature space. The best performance is highlighted in thick black letters.}
\label{tab:resultSVM2}
\end{table}

\begin{table}[htbp]
\begin{center}
\begin{tabular}{||p{2.5cm}||*{7}{c|}|}
\hline
$\sigma$	& D 10	& D 12	& D 14 	& D 16	& D 18	& D 20	& D 22	\\
\hline
\hline
0.25	&   10.56  &  11.39  &  11.94  &  11.67  &  13.61  &  13.33  &  16.11\\
\hline
0.5	&   13.33  &  10.28  &  10.00  &  10.56  &  12.78  &  11.11  &  11.39\\
\hline
1	&   10.83  &  10.28  &  11.39  &  9.44  &  8.89  &  9.72  &  9.17\\
\hline
1.5	&    10.00  &  9.72  &  9.44  &  9.44  &  10.83  &  8.89  &  9.17\\
\hline
2	&   10.28  &  8.89  &  10.00  &  10.28  &  10.56  &  \bfseries{8.61}  &  9.72 \\
\hline
3	&   10.28  &  10.00  &  11.11  &  11.67  &  10.28  &  10.56  &  9.72\\
\hline
4	&  11.11  &  10.83  &  12.22  &  13.06  &  11.11  &  10.83  &  10.83\\
\hline
5	&    11.67  &  11.39  &  11.94  &  12.50  &  11.67  &  11.94   & 11.94\\
\hline
10	&   12.22  &  12.50  &  11.39  &  12.50  &  12.78  &  13.61  &  13.06\\
\hline
15	&   13.89  &  13.06  &  13.33  &  12.78  &  14.17  &  14.44  &  15.00\\ 
\hline
20	&  15.00  &  14.72  &  13.33  &  12.50  &  14.44  &  14.44  &  15.00\\
\hline
50 	&   15.83  &  16.67  &  17.78  &  18.33 &   18.89   &  18.89  &  19.00\\
\hline
\hline
\end{tabular}
\end{center}
\caption{SVM with RBF kernel and penalty of errors $C=20$: error rate as a function of the width $\sigma$ and dimension D of feature space. The best performance is highlighted in thick black letters.}
\label{tab:resultSVM3}
\end{table}




\begin{table}[htbp]
\begin{center}
\begin{tabular}{||p{2.5cm}||*{7}{c|}|}
\hline
$\sigma$	& D 10	& D 12	& D 14 	& D 16	& D 18	& D 20	& D 22	\\
\hline
\hline
0.25	&  12.78  &  12.22  &  12.50  &  14.17  &  15.56  &  18.61  &  19.17\\
\hline
0.5	&  12.22  &  10.28  &  9.44  &  10.83  &  10.28  &  10.83  &  10.28\\
\hline
1	&  10.28  &  10.00  &  9.72  &  9.72  &  10.56  &  9.17  &  \bfseries{8.61}\\
\hline
1.5	&   10.28  &  10.28 &  10.83  &  9.17  &  10.56  &  9.17  &  9.72\\
\hline
2	& 10.56  &  10.00  &  9.72  &  10.00  &  9.44  &  9.72   & 9.72\\
\hline
3	&  9.72  &  10.28  &  11.39  &  9.72  &  10.83  &  9.44  &  10.00\\
\hline
4	& 10.83  &  10.83  &  11.94  &  10.28  &  10.56  &  10.28  &  10.28\\
\hline
5	&  11.39  &  10.83  &  11.39  &  11.67  &  11.94  &  10.00  &  11.39\\
\hline
10	&  12.22  &  12.22  &  12.50 &   11.94  &  12.78  &  12.50  &  12.78\\
\hline
15	&  13.33  &  12.50  &  12.78  &  13.61  &  12.78  &  13.89  &  13.89\\ 
\hline
20	&  14.17  &  13.89  &  14.72  &  15.00  &  13.89  &  15.00  &  14.44\\
\hline
50 	&  16.94  &  16.11  &  16.39  &  16.39  &  17.22  &  18.61  &  18.89\\
\hline
\hline
\end{tabular}
\end{center}
\caption{SVM with RBF kernel and penalty of errors $C=50$: error rate as a function of the width $\sigma$ and dimension D of feature space. The best performance is highlighted in thick black letters.}
\label{tab:resultSVM4}
\end{table}


\begin{table}[htbp]
\begin{center}
\begin{tabular}{||p{2.5cm}||*{7}{c|}|}
\hline
$\sigma$	& D 10	& D 12	& D 14 	& D 16	& D 18	& D 20	& D 22	\\
\hline
\hline
0.25	&  11.67  &  11.67  &  14.17  &  15.00  &  16.11  &  18.89  &  18.89\\
\hline
0.5	&  8.89  &  8.89  &  10.28  &  10.28  &  11.11  &  11.11  &  11.67\\
\hline
1	& 8.06  &  8.33  &  7.50  &  7.50  &  8.33  &  8.89  &  8.89\\
\hline
1.5	&   7.50  &  7.78  &  7.50  &  \bfseries{5.83}  &  8.06  &  6.67  &  8.61\\
\hline
2	& 6.94  &  7.50  &  7.78  &  6.94  &  6.67  &  6.39  &  7.78\\
\hline
3	&  7.50  &  8.61  &  7.50  &  8.06  &  7.22  &  7.50  &  7.50\\
\hline
4	& 8.61  &  8.06  &  7.78  &  8.06  &  8.06  &  7.22  &  7.50\\
\hline
\hline
\end{tabular}
\end{center}
\caption{SVM with RBF kernel and penalty of errors $C=100$: error rate as a function of the width $\sigma$ and dimension D of feature space. The best performance is highlighted in thick black letters.}
\label{tab:resultSVM5}
\end{table}






\subsection{Final experiments}	\label{sec:classFinExp}

We show the final results for urine and pollen database. In order to assess the performance, a confusion matrix is built. Each row is the class to
which the test images belong, the columns are the classes to which the classifier assigns the test images. Thus, in the intersection between
the $j$-th row and the $i$-th column we find the following estimate:

\begin{equation}
P[outcome \in C_i \mid image \in C_j ] = \frac{ \mbox{nr. of items of $C_j$ classified as belonging to $C_i$} }{ \mbox{total nr. of tested
images belonging to $C_j$} }
\end{equation} 
  
In order to evaluate the overall performance we compute the error rate defined as,

\begin{equation}
ER = \frac{\mbox{nr. of not correctly classified test images}}{\mbox{total nr. of test images}}
\end{equation}

Because not all the categories in our databases have the same number of images, we train and test on a uneven number of images for class.
Then, we define a new error rate which is the normalized sum of single class error rates 

\begin{equation}
ERp = \frac{1}{K} \sum_{j=1}^K \frac{\mbox{nr. of misclassified test images belonging to $C_j$} }{\mbox{total nr. of test images belonging 
to $C_j$}}
\end{equation}

For example, when we consider the whole system for pollen recognition we will see that the classifier has to analyze also particles of junk.
The ratio between pollen and junk particles is 1 out of 10. If we test 100 pollen patches and 1000 junk patches it is possible that the
classifier has an ER = 10\% which can be considered quite good. However, it is possible that most of junk particles are classified as junk and
most of pollen particles are misclassified, the ER simply can not say if the less numerous classes are well classified. Instead when you
consider also the ERp you can check if the error is evenly or proportionally distributed among the categories.

\subsubsection{Urine database}

First, we consider the classifier using mixture of Gaussians with the different kinds of features studied.\\
During the tuning of parameters, we focused on data belonging to the training and validation set. 
Now, we show some results of experiments done in the following way:

\begin{enumerate}
\item training and test using the full data set available and with different number of images per class; 
we pay attention to put in the training set all the images belonging to the previous training and validation set 
and we choose randomly (from the complementary set) 10\% of the total amount of images for test; the result will be the average of 10
experiments
\item we run 100 experiments on the full data set available; at each iteration we randomly extract about 10\% of images for test purpose. 
\end{enumerate}

In \figref{Jan02CMonFullDataSetIPCSPC}, \figref{Jan02CMonFullDataSetLJ}, \figref{CMonFullDataSetcombfeat} and 
\figref{CMonFullDataSetcase3combclass} we show the graphical representation of confusion matrix using the first method for the four different
kinds of classifiers based on MoG modeling. \\
Note that the numbers in the plot are in percentage with respect to the total number of images tested for a certain class. Moreover, we show
the average result on 10 experiments.\\  
The experiments with the classifier that combines the experts' outcomes, need a comment. 
We have to choose the subdivision of the training set for the first and second training. 
When we used 7/9 of the training set for the first training and 4/9 for the second one 
(so, there is a partial overlap of 2/9) we got an ER equal to 9.8\%; 
a second time we took all the images of the training set for the first training and we extracted randomly from this set 
half of them for the second training and we got an ER equal to 8\%. 
The trend was confirmed by the last experiment, shown in \figref{CMonFullDataSetcase3combclass}, 
when  we used for both trainings all the images available in the training set; 
in this way we got an ER of 7.7\%. 
Even if the second training models the training outcomes (or the training errors), the general performance is improved.\\
The best result is achieved with the classifier using features based on local jets, its error rate is equal to 6.8\% (the proportional error
rate is 6.5\% ).\\


\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.8\textwidth,height=0.5\textwidth]{./figure/CMLJ10ESPnooverlap.eps}
\caption{Classifier using MoG and feature based on local jets: averaged confusion matrix for experiments in which 90\% of images in the 
full data set is used for training and 10\% is randomly extracted for test; there is no overlapping between the test
items and previous trained images.}
\label{figure:Jan02CMonFullDataSetLJ}
\end{center}
\end{figure}


\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.8\textwidth,height=0.5\textwidth]{./figure/CMIPCSPC10ESP.eps}
\caption{Classifier using MoG and feature based on image and spectrum principal components: averaged confusion matrix 
for experiments in which 90\% of images in the full data set is used for training and 10\% is randomly extracted for
test; there is no overlapping between the test items and previous trained images.}
\label{figure:Jan02CMonFullDataSetIPCSPC}
\end{center}
\end{figure}


\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.8\textwidth,height=0.5\textwidth]{./figure/CMCombFeat10EspNooverlap.eps}
\caption{Classifier using MoG and feature combination in indep. hyp.: averaged confusion matrix for experiments in which 90\% 
of images in the full data set is used for training and 10\% is randomly extracted for test; there is no overlapping
between the test items and previous trained images.}
\label{figure:CMonFullDataSetcombfeat}
\end{center}
\end{figure}

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.8\textwidth,height=0.5\textwidth]{./figure/CMCombClass10EspNooverlap.eps}
\caption{Classifier using MoG and making a combination of experts' response: averaged confusion matrix for experiments in which 90\%
 of images in the full data set is used for training and 10\% is randomly extracted for test; there is no overlapping
 between the test items and previous trained images.}
\label{figure:CMonFullDataSetcase3combclass}
\end{center}
\end{figure}



Finally, we show the average results of 100 experiments on the full data set taking randomly 10\% of images for test, see \figref{AvCMonFullDataSetLJ}, 
\figref{AvCMonFullDataSetcombfeat}, \figref{AvTestCMonFullDataSetcombclass}. 

Why did we choose to perform 100 experiments? Because we want a reliable estimate of the average ER with a low standard deviation. 
Now, we give a brief overview of the theoretic study for the choice of the experiment number. \\
If $ x $ is a stochastic binary variable with alphabet $ A_x = \{0,1\} $ and $P[x=1] = p(1) = p$ it is easy to find that the mean 
of $x$ is $m_x = p$ and its variance $\sigma_x^2 = p(1-p)$. 
We can interpret this variable as the outcome of the following event: ``the classifier takes the right decision on the test image''.\\
If you consider $n$ stochastic binary variables and all these variables have the same parameter p and are independent, 
we can define the sum variable $ y = \sum_{i=1}^n x_i$ which is a binomial one with parameters $n$ and $p$; 
its mean and variance are: $m_y=np=nm_x$, $\sigma_y^2=np(1-p)=n\sigma_x^2$. \\
Let be $z=y/n$, then $m_z=m_y/n=p=m_x$, and $\sigma_z^2 = \sigma_y^2/n^2=\sigma_x^2/n$. 
We can think that $y$ describes the statistic of $n$ decisions of the classifier on $n$ test images, and $z$ the performance 
when considering $n$ test images. You can note that increasing $n$ you can decrease $\sigma_z^2$.\\
In order to have a reliable result for the performance of our classifier we could average the results on many experiments. 
Given the (estimated) performance if we choose properly the number of images to test and the number of experiments, 
we can control the variability of the error rate.\\
Let be $m$ the number of experiments we want to run and $w=\frac{1}{m}\sum_{i=1}^m z_i$, then it can be shown that $m_w=m_z=m_x$ 
and $\sigma_w^2 = \frac{1}{m}\sigma_z^2 = \frac{1}{mn}\sigma_x^2$.\\
Finally, we can approximately estimate the standard deviation of the ER in our experiment doing the following hypothesis: 
if the probability to misclassify an image is nearly $p=0.1$ (even if it depends on the belonging class), 
$m$ is equal to 100 and $n$ is about 100*12 (in practice it is less), then

$$
\sigma_w=\frac{\sigma_x}{\sqrt{mn}} \simeq \frac{\sqrt{9\cdot10^{-2}}}{\sqrt{12\cdot10^4}} \simeq 7\cdot10^{-3}
$$

With this choice of parameters, we can be confident to find an ER with a standard deviation of about 0.7\% (below 1\%).\\
These result is confirmed by our experiments as you can check in  \figref{AvCMonFullDataSetLJ}, 
\figref{AvCMonFullDataSetcombfeat}, \figref{AvTestCMonFullDataSetcombclass}.  

 
As you can see for example in \figref{AvCMonFullDataSetLJ} and expect, the confusion matrix has an high symmetry with respect 
to the diagonal. For example, 2.5\% of Hyal are classified as Nhyal and vice versa, 4\% of NSE are classified as white cell clumps 
and 3.9\% of these particles are classified as belonging to NSE class. 

The best performance is again achieved using the classifier with features based on local jets, the error rate is equal to 7.6\%. 
If you look at \figref{AvCMonFullDataSetLJ}, 
the best classified class is mucus with an ER equal to 2\%; 
the worst classified particle is NSE. Most of errors are done between white cell clumps and NSE, 
white cell clumps and squame epithelius, hyal and nhyal.\\

  
\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.9\textwidth,height=0.55\textwidth]{./figure/AvCMonFullDataSetLJ.eps}
\caption{Classifier using MoG and feature based on local jets: averaged confusion matrix of test errors for 100 
experiments in which 90\% 
of images in the full data set is used for training and 10\% is randomly extracted for test.}
\label{figure:AvCMonFullDataSetLJ}
\end{center}
\end{figure}
 
\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.9\textwidth,height=0.55\textwidth]{./figure/AvCMonFullDataSetcombfeat.eps}
\caption{Classifier using MoG and feature combination in indep. hyp.: averaged confusion matrix of test errors for 100 
experiments in which 90\%
 of images in the full data set is used for training and 10\% is randomly extracted for test.}
\label{figure:AvCMonFullDataSetcombfeat}
\end{center}
\end{figure}
 
\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.9\textwidth,height=0.5\textwidth]{./figure/AvTestCMonFullDataSetcombclass.eps}
\caption{Classifier using MoG and making a combination of experts' response: averaged confusion matrix of test errors
for 100 experiments in which 90\%
 of images in the full data set is used for training and 10\% is randomly extracted for test.}
\label{figure:AvTestCMonFullDataSetcombclass}
\end{center}
\end{figure}
 
\newpage

We now show the results of AdaBoost inspired algorithm. With the hypothesis found during the experiments of \figref{findHypAdaBoost},
we run a test on 10\% of images in the data set (not belonging to previous training or validation set). In 
\figref{CMstandardclassifierTr480} and \figref{CMAdaBoost}, the averaged performance on 10 experiments is shown for the standard classifier
(that is taking only the first hypothesis) and for the boosted one. As you can notice there is an improvement of 0.5\% in the error rate.\\




\begin{figure}[!htbp]
\begin{center}
\includegraphics[width=1\textwidth,height=1\textwidth]{./figure/CMstandardclassifierTr480.eps}
\caption{Test and training confusion matrices for the original classifier using MoG and local jet based features. 
The training is performed on 480 images and the test on 10\% of full data set. The result is averaged on 10 experiments. In this figure and in
the following ones, the classes are identified with numbers in accordance to \tabref{urineDB}. The numbers in the diagonals are the percentages of correct classification in each class.}
\label{figure:CMstandardclassifierTr480}
\end{center}
\end{figure}



\begin{figure}[!htbp]
\begin{center}
\includegraphics[width=1\textwidth,height=1\textwidth]{./figure/CMAdaBoost.eps}
\caption{AdaBoost.M1: test and training confusion matrices. 
The training is performed on 480 images and the test on 10\% of full data set. The result is averaged on 10 experiments.}
\label{figure:CMAdaBoost}
\end{center}
\end{figure}



Taking the best achieved performance on validation  set, we run experiments using SVM following the methodology above-mentioned for AdaBoost.
Unfortunately, we achieved an error rate of 12.2\% in test and below 2\% in training. This is caused by training data overfitting.
 We have
to choose parameters for SVM to find a sort of balance between accuracy attained on a particular training set, and the capacity of the
machine to learn the general properties of our data. With this choice of parameters, the system seems to have a little generalization.  
For this reason, we tried other ``good'' but sub-optimal values for the parameters and the best performance is reported in 
\figref{CMSVM10EspC5p1D20}. There is still a big gap between the performance on training and test set however there is an improvement of
0.5\% and 1\% in the absolute and proportional error rate with respect to the classifier using MoG.

\begin{figure}[!htbp]
\begin{center}
\includegraphics[width=1\textwidth,height=1\textwidth]{./figure/CMSVM10EspC5p1D20.eps}
\caption{SVM with rbf kernel $C=5$, $\sigma=1$ in a 20 dimensional feature space: test and training confusion matrices. 
The training is performed on 500 images and the test on 10\% of full data set. The result is averaged on 10 experiments.}
\label{figure:CMSVM10EspC5p1D20}
\end{center}
\end{figure}

\clearpage

\subsubsection{Pollen database}


We show the performance of classifier using MoG with feature based on local jets. The database we are considering is the ``pure'' 
pollen database and the six most numerous categories. These classes have more than 1000 images. It turns out from the tuning stage that the
best modeling is achieved taking 2 full covariance matrix in each mixture and considering a 20 dimensional feature space. 
The tuning was done on 500 training images per class from which 30 images were extracted to build a validation set. 
Then, we run 100 experiments taking
from each class the 10\% of available images for test and the rest for training, see \tabref{pollenDB}. We paid attention to avoid that images belonging to previous training and
validation sets are selected in the current test set. The averaged test error rate is 10.2\%, see \figref{CM100EspCl6}.

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.95\textwidth,height=0.8\textwidth]{./figure/CM100EspCl6Pollen.eps}
\caption{Test and training confusion matrix for the six most numerous categories of ``pure'' pollen. The result is averaged on 100 experiments (no overlapping between test set
and current or previous training sets).}
\label{figure:CM100EspCl6}
\end{center}
\end{figure}

Analogously, we made an experiment taking the 13 most numerous classes in the ``pure'' pollen database (see \tabref{pollenDB}), that is all the categories with more
than 100 images and we got a proportional averaged test error rate around 19\%, see \figref{CMPollenCl13}.

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.95\textwidth,height=0.6\textwidth]{./figure/CMPollenCl13.eps}
\caption{Test confusion matrix for the 13 most numerous categories of ``pure'' pollen. The result is averaged on 100 experiments (no overlapping between test set
and current or previous training sets).}
\label{figure:CMPollenCl13}
\end{center}
\end{figure}


Is useful to test the classifier on ``pure'' pollen database? How should we read these results? \\
In order to answer to these questions, we describe an analysis of pollen database which will give a deep insight on how the ``pure'' pollen
database is related to the air sampled pollen database.

We consider the classes of air sampled pollen database with more than 60 items. These categories are: ash, chinese elm and oak. In the
``pure'' pollen database these species have more than 1000 images, see \tabref{nrpollenexp} and \tabref{pollenDB}. We make a test on a number of images that is the 10\% of air
sampled pollen database. The experiments done with the classifier using Mog and local jet based features are:

\begin{enumerate}
\item train and test on pollen grains captured by air sampler machine
\item train and test on ``pure'' pollen grains with a number of images equal to case 1
\item train on ``pure'' pollen grains and test on air sampler pollen grains using the same number of images of case 1
\item train and test on ``pure'' pollen grains using for training all the remaining part of images in the ``pure'' pollen database
\item train on the same ``pure'' pollen images of case 4 and test on the air sampled pollen grains of case 3
\end{enumerate}

\begin{table}[htbp]
\begin{center}
\begin{tabular}{||p{3cm}||*{3}{c|}|}
\hline
Class	& training on few samples	& training on many samples & test	\\
\hline
\hline
\bfseries ash & 68 & 1275 & 7\\
\hline
\bfseries chin. elm & 112 & 1904 & 12 \\
\hline
\bfseries oak & 60 & 1473 & 6 \\
\hline
\hline
\end{tabular}
\end{center}
\caption{Number of samples used in experiments for pollen database assessment.}
\label{tab:nrpollenexp}
\end{table}

For experiments with few training data, each mixture has two diagonal Gaussians while for experiments with more than 1000 images per
class we chose to model the distribution of the data with a mixture of seven diagonal Gaussians. \\
The results are shown in \figref{CMTrainFewTestFewsamples} and \figref{CMTrainManyTestFewsamples}. 
 
 
\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.9\textwidth,height=0.75\textwidth]{./figure/CMtrainfewTestfewPollen.eps}
\caption{Pollen database: confusion matrix when training is done on few samples; the result is an average of 100 experiments}
\label{figure:CMTrainFewTestFewsamples}
\end{center}
\end{figure}



\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.9\textwidth,height=0.5\textwidth]{./figure/CMtrainmanyTestfewPollen.eps}
\caption{Pollen database: confusion matrix when training is done on many images (more than 1000); the result is an average on 100 experiments}
\label{figure:CMTrainManyTestFewsamples}
\end{center}
\end{figure}



The aim of these experiments is also to find an estimate of the error rate for the same classifier when the training and test are done on air
sampled pollen grains and the training has available 1000 images for each class. Since our database of air 
sampled pollen particles does not have such a
quantity of data (see  \tabref{pollenDB}), we linearly interpolate this error rate from the error rates found in the previous experiments; 
the promising result of 15\% is found as shown in \figref{estimatedERTrainTestAir}.
 
 
\begin{figure}[htbp]
\begin{center}
\includegraphics[width=1\textwidth,height=0.85\textwidth]{./figure/estimatedERTrainTestAir.eps}
\caption{Pollen database: graphical estimate of error rate when the training is done using many (more than
1000) images of pollen grains captured
by volumetric spore trap.}
\label{figure:estimatedERTrainTestAir}
\end{center}
\end{figure}

Thanks to this analysis, we can claim that there is inconsistency between ``pure'' pollen and air sampled pollen database. It is not worth
to train with the ``pure'' pollen images and then to test the air sampled pollen images because the former ones are without junk in the
background, less variable in shape, texture and color. \\
However, training and test done on ``pure'' pollen database will allow to find a lower bound for the
error rate of the classifier using only pollen captured by spore trap.

The system must be evaluated using air sampled pollen particles in order to have a realistic estimate of the
performance of a measurement instrument. However, ``pure'' pollen images can give an idea of which kind of particles are most difficult to
classify. 

Moreover, we should observe how much the performance improves with the number of training images; as you can see in 
\figref{CMTrainFewTestFewsamples} and \figref{CMTrainManyTestFewsamples}, 
the error rate decreases from 18\% to 6\% if more images for training are taken when using ``pure'' pollen images. This fact is also
highlighted by the great gap between training and test error rate when few images are taken for training.
  
\clearemptydoublepage

