% revised version of the BV JMLR paper - October 2003
\documentclass[twoside,11pt]{article}

% Any additional packages needed should be included after jmlr2e.
% Note that jmlr2e.sty includes epsfig, amssymb, natbib and graphicx,
% and defines many common macros, such as 'proof' and 'example'.
%
% It also sets the bibliographystyle to plainnat; for more information on
% natbib citation styles, see the natbib documentation, a copy of which
% is archived at http://www.jmlr.org/format/natbib.pdf

\usepackage{jmlr2e}

% Definitions of handy macros can go here

\newcommand{\dataset}{{\cal D}}
\newcommand{\fracpartial}[2]{\frac{\partial #1}{\partial  #2}}
\newcommand{\vt}[1]{\mathbf{#1}}
\newcommand{\changed}{}
\newcommand{\changedEnd}{}

% Heading arguments are {volume}{year}{pages}{submitted}{published}{author-full-names}

\jmlrheading{5}{2004}{725--775}{1/03}{7/04}{Giorgio Valentini and Thomas Dietterich}

% Short headings should be running head and authors last names

\ShortHeadings{Bias-Variance Analysis of SVMs}{Valentini and Dietterich}
\firstpageno{725}

\begin{document}



\title{Bias-Variance Analysis of Support Vector Machines 
for the Development of SVM-Based Ensemble Methods}

\author{\name Giorgio Valentini \email valentini@dsi.unimi.it \\
       \addr DSI - Dipartimento di Scienze dell'Informazione\\
       Universit\`a degli Studi di Milano\\
       Via Comelico 39, Milano, Italy
       \AND
       \name Thomas G. Dietterich \email tgd@cs.orst.edu \\
       \addr Department of Computer Science\\
       Oregon State University\\
       Corvallis, OR 97331, USA}

\editor{Nello Cristianini}

\maketitle

\begin{abstract}
%The success of ensembles of classifiers have been explained in the framework 
%of the theory of large margin classifiers and  bias-variance decomposition of the error.
Bias-variance analysis provides a tool to study 
learning algorithms and  can be used 
to properly design ensemble methods well tuned to the properties of a
specific base learner.
Indeed the effectiveness of ensemble methods   critically depends on accuracy,
diversity and learning characteristics of base learners.
We present an extended experimental analysis of bias-variance decomposition of the error in 
Support Vector Machines (SVMs),
considering Gaussian, polynomial and dot product kernels.
A characterization of the error decomposition is provided, by means of the analysis of
the relationships between bias, variance, kernel type and its parameters, offering insights into the way
SVMs learn.
The results show that the expected trade-off between bias and variance is sometimes observed, 
but more complex relationships can be detected, especially in Gaussian and polynomial kernels.
We  show that the bias-variance decomposition offers a rationale to develop
ensemble methods using SVMs as base learners, and we outline two
directions for developing SVM ensembles, exploiting the SVM bias
characteristics and the bias-variance dependence on the kernel
parameters.
\end{abstract}

\begin{keywords}
  Bias-variance analysis, support vector machines, ensemble methods, multi-classifier systems.
\end{keywords}

\section{Introduction}
Ensembles of classifiers represent one of the main research directions in machine learning~\citep{Die00a}.
Empirical studies showed that both in classification and regression problems ensembles are often much more accurate than 
the individual base learner that make them up~\citep{Bau99,Die00b,Fre96}, and recently different theoretical explanations 
have been proposed to justify the effectiveness of some commonly used ensemble methods~\citep{Kit98b,Scha99,Klein00,All00}.

Two main theories are invoked to explain the success of ensemble methods. 
The first one considers the ensembles in the framework of large margin classifiers~\citep{Mason00}, showing that  
ensembles enlarge the margins, enhancing  the generalization capabilities of learning 
algorithms~\citep{Scha98,All00}.
The second is based on the classical bias-variance decomposition of the error~\citep{Gem92}, 
and it shows that  ensembles  can reduce  variance~\citep{Bre96b} and also  bias~\citep{Kon95}.

Recently Domingos proved that Schapire's notion of margins~\citep{Scha98} can be expressed in terms of bias and 
variance and vice versa~\citep{Dom00b}, and hence Schapire's bounds of ensemble's generalization error can be 
equivalently expressed in terms of the distribution of the margins or in terms of the bias-variance 
decomposition of the error, showing the equivalence of margin-based and bias-variance-based approaches.

The effectiveness of ensemble methods depends on the specific characteristics of the base learners;
in particular on  the relationship between diversity and accuracy of the base 
learners~\citep{Die00a,Kun01a,Kun03a}, on their stability~\citep{Bre96b,Bou02}, and on their general geometrical
properties~\citep{Cohen01}.

From this standpoint the analysis of the features and
properties of the base learners used in ensemble methods is crucial in
order to design ensemble methods well tuned to the characteristics of a specific base learner.
For instance, considering that the agglomeration of many classifiers into one classification rule reduces 
variance~\citep{Bre96}, we could  apply low-bias base learners to reduce both bias and variance using 
ensemble methods.
To this purpose in this paper we study Support Vector Machines (SVMs), that are ``strong'' dichotomic classifiers, 
well founded on Vapnik's statistical learning theory~\citep{Vap98}, in order to establish  if and how we can exploit 
their specific features in the context of ensemble methods.  
We analyze the learning properties of SVMs
using the bias-variance decomposition of the error as a tool to
understand the relationships between kernels, kernel parameters, and
learning processes in SVM.  

Historically, the bias-variance insight
was borrowed from the field of regression, using squared-loss as the
loss function~\citep{Gem92}.  For classification problems,
where the $0/1$ loss is the main criterion, several authors proposed
bias-variance decompositions related to $0/1$ loss.
\citet{Kon95} proposed a bias-variance decomposition in the context of ECOC ensembles~\citep{Die95},
but their analysis is extensible to arbitrary classifiers, even if they defined variance simply as a difference between 
loss and bias. 

In Breiman's decomposition~\citep{Bre96b} bias and variance are always non-negative (while Dietterich definition allows a
negative variance), but at any input the reducible error (i.e. the total error rate less noise) is assigned entirely to variance
if the classification is unbiased, and to bias if biased.
Moreover he forced the decomposition to be purely additive, while for the 0/1 loss this is not the case.
\citet{Kohavi96} approach leads to a biased estimation of bias and variance, assigning a non-zero bias to
a Bayes classifier, while \citet{Tib96} did not use directly the notion of variance, 
decomposing the $0/1$ loss in bias and an unrelated quantity he called ``aggregation effect'', which is similar to the James'
notion of {\em variance effect}~\citep{James03}.

\citet{Frie97} showed that bias and variance are not purely additive: in some cases
increasing variance increases the error, but in other cases can also reduce the error, especially when the prediction is
biased.

\citet{Hes98} proposed a bias-variance decomposition using as loss function the Kullback-Leibler divergence. 
By this approach the error between the target and the predicted classifier densities is measured; anyway when he 
tried to extend this approach to the zero-one function interpreted as the limit case of log-likelihood type error, 
the resulting decomposition produces a definition of bias that loses his natural interpretation as systematic error 
committed by the classifier.

As briefly outlined, these decompositions suffer of significant shortcomings: in particular they
lose the relationship to the original squared loss decomposition,
forcing in most cases bias and variance to be purely additive.

We consider classification problems and the $0/1$ loss function in the
Domingos' unified framework of bias-variance decomposition of the
error~\citep{Dom00b,Dom00c}. In this approach bias and variance are
defined for an arbitrary loss function, showing that the resulting
decomposition specializes to the standard one for squared loss, but it
holds also for the $0/1$ loss~\citep{Dom00b}.  

A similar approach has been proposed by \citet{James03}: he extended the notion of variance and bias for general loss
functions, distinguishing also between bias and variance, interpreted respectively as the systematic error and the
variability of an estimator, and the actual effect of bias and variance on the error. 

Using Domingos' theoretical
framework, we tried to answer two main questions:
\begin{enumerate}
\item Can we characterize bias and variance in SVMs with respect to the
kernel and its parameters?
\item Can the bias-variance decomposition offer guidance for developing
ensemble methods using SVMs as base learners?
\end{enumerate}
In order to answer these two questions, we planned and performed an
extensive series of experiments on synthetic and real data sets to
evaluate bias variance-decomposition of the error with different
kernels and different kernel parameters.

The paper is organized as follows.  In
Section~\ref{sec:BVdecomposition}, we summarize the main results of
Domingos' unified bias-variance decomposition of error.
Section~\ref{sec:measuringBV} outlines how to measure in practice bias and 
variance decomposition of the error with artificial or large benchmark data sets, 
or when only a small ``real'' data set is available. 
Section~\ref{sec:BV-SVM} outlines the main characteristics of the data
sets employed in our experiments and the main experimental tasks
performed.  Then we present the main results of our
experiments about bias-variance decomposition of the error in
SVMs, considering separately Gaussian, polynomial and and dot product SVMs, 
and comparing also the results between different kernels.
Section~\ref{sec:characterization} provides a characterization of bias-variance decomposition of the error for 
Gaussian, polynomial and and dot product SVMs, highlighting the common patterns for each different kernel.
 Section~\ref{sec:directions} exploits the knowledge achieved by the
bias-variance decomposition of the error to formulate hypotheses
about the effectiveness of SVMs as base learners in ensembles of
learning machines, and two directions for developing new ensemble
models of SVM are proposed.  An outline of ongoing and future developments of
this work concludes the paper.




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Bias-Variance Decomposition for the 0/1 Loss Function}
\label{sec:BVdecomposition}
The analysis of bias-variance decomposition of the error has been originally developed in the standard regression setting,
where the squared error is usually used as loss function.
Considering a prediction $y=f(x)$ of an unknown target $t$, provided by a learner $f$ on input $x$, 
with $\vt{x} \in \mathbb{R}^d$ and $y \in \mathbb{R}$, the classical
decomposition of the error in bias and variance for the squared error loss is~\citep{Gem92}
\begin{eqnarray*}
E_{y,t} [(y-t)^2] & = & E_t[(t - E[t])^2] + E_y[(y-E[y])^2] + (E[y]-E[t])^2 \\ \nonumber
                 & = & Noise(t) + Var(y) + Bias^2(y).
\end{eqnarray*}
In words, the expected loss of using $y$ to predict $t$ is the sum of the variances of $t$ (noise) and $y$ plus the squared
bias. $E_y[\cdot]$ indicates the expected value with respect to the distribution of the random variable $y$.

This decomposition cannot be automatically extended to the standard classification setting, as in this context the 0/1 loss
function is usually applied, and bias and variance are not purely additive. 
As we are mainly interested in  analyzing bias-variance  for classification problems, 
we introduce the bias-variance decomposition for the 0/1 loss function, 
according to the Domingos unified bias-variance decomposition of the error~\citep{Dom00c}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Expected Loss Depends on the Randomness of the Training Set and the Target}
\label{subsec:randomness}

%%% Set of data sets
Consider a (potentially infinite) population $U$ of labeled training
data points, where each point is a pair $(\vt{x}_j, t_j), \; t_j \in
\mathcal{C}, \; \vt{x}_j \in \mathbb{R}^d, \; d \in \mathbb{N}$, where
$\mathcal{C}$ is the set of the class labels. Let $P(\vt{x},t)$
be the joint distribution of the data points in $U$.  Let $D$ be a set
of $m$ points drawn identically and independently from $U$ according
to $P$.  We think of $D$ as being the training sample that we are
given for training a classifier.  We can view $D$ as a random
variable, and we will let $E_D[\cdot]$ indicate the expected value
with respect to the distribution of $D$.

%%% Model produced by a learner
Let $\mathcal{L}$ be a learning algorithm, and define $f_{D} =
\mathcal{L}(D)$ as the classifier produced by $\mathcal{L}$ applied to
a training set $D$. The model produces a prediction $f_{D}(\vt{x}) = y$.
%%% Loss function 
Let $L(t,y)$ be the $0/1$ loss function, that is $L(t,y) = 0$ if
$y=t$, and $L(t,y) = 1$ otherwise.

Suppose we consider a fixed point $\vt{x} \in \mathbb{R}^d$.  This point
may appear in many labeled training points in the population.  We can
view the corresponding labels as being distributed according to the
conditional distribution $P(t|\vt{x})$.  Recall that it is always possible
to factor the joint distribution as $P(\vt{x},t) = P(\vt{x}) P(t|\vt{x})$.  Let
$E_t[\cdot]$ indicate the expectation with respect to $t$ drawn
according to $P(t|\vt{x})$. 

Suppose we consider a {\it fixed} predicted class $y$ for a given $\vt{x}$.
This prediction will have an expected loss of $E_t[L(t,y)]$.  In
general, however, the prediction $y$ is not fixed.  Instead, it is
computed from a model $f_D$ which is in turn computed from a training
sample $D$.  

Hence, the expected loss $EL$ of learning algorithm
$\mathcal{L}$ at point $\vt{x}$ can be written by considering both the
randomness due to the choice of the training set $D$ and the
randomness in $t$ due to the choice of a particular test point $(\vt{x},
t)$:
\[EL(\mathcal{L}, \vt{x}) = E_D[ E_t[ L(t, f_D(\vt{x})) ] ],\]
where $f_D = \mathcal{L}(D)$ is the classifier learned by
$\mathcal{L}$ on training data $D$.  The purpose of the bias-variance
analysis is to decompose this expected loss into terms that separate
the bias and the variance. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Optimal and Main Prediction}
\label{subsec:0/1-loss}

%%% Def. optimal prediction
To derive this decomposition, we must define two things: the {\em optimal
prediction} and the {\em main prediction}: according to Domingos, bias and variance can be defined in terms
of these quantities. 

The {\em optimal prediction}
$y_*$ for point $\vt{x}$ minimizes $E_t[L(t,y)]:$
\begin{equation}
y_*(\vt{x}) = \arg \min_y E_t[L(t,y)].
\label{eq:optimalprediction}
\end{equation}
%%%%%  rev.2 comment 2  %%%%%%%%%%%%%%%%%%%
\changed
It is equal to the label $t$ that is observed more often in the universe $U$ of the data points, and corresponds to the prediction
provided by the Bayes classifier.
The {\em optimal model} $\hat{f}(\vt{x})=y_*, \; \forall \vt{x}$ makes the optimal
prediction at each point $\vt{x}$, and corresponds to the Bayes classifier; its error rate corresponds to the Bayes error rate.
\changedEnd
 
The noise $N(\vt{x})$, is defined in terms of the optimal prediction,
and represents the remaining loss that cannot be eliminated, even by the optimal prediction: 
\begin{displaymath}
N(\vt{x}) = E_t[L(t,y_*)].
\end{displaymath}
Note that in the deterministic case $y_* = t$ and $N(\vt{x}) = 0$.

%%%%%%% Def, main prediction
The {\em main prediction} $y_m$ at point $\vt{x}$ is defined as
\begin{equation}
y_m = \arg \min_{y'} E_D[L(f_D(\vt{x}), y')].
\label{eq:mainprediction}
\end{equation}
This is a value that would give the lowest expected loss if it were
the ``true label'' of $\vt{x}$.  It expresses the ``central tendency'' of a learner, that is its systematic
prediction, or, in other words, it is the label for $\vt{x}$ that the learning algorithm ``wishes'' were correct.
For 0/1 loss, the main prediction is the class predicted most often by the learning
algorithm $\mathcal{L}$ when applied to training sets $D$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Bias, Unbiased and Biased Variance.}
\label{subsec:bias}
%%%%%%%% Def Bias %%%%%%%%%
Given these definitions, the {\em bias} $B(\vt{x})$ (of a learning algorithm
$\mathcal{L}$ on training sets of size $m$) is the loss of the main
prediction relative to the optimal prediction: 
\begin{displaymath}
B(\vt{x}) = L(y_*,y_m). 
%\label{eq:bias}  
\end{displaymath}
For 0/1 loss, the bias is always 0 or 1.  We will say that
$\mathcal{L}$ is {\it biased at point $\vt{x}$}, if $B(\vt{x}) = 1$. 

%%%%%%%% Def Net-variance %%%%%%%%%
The {\em variance} $V(\vt{x})$ is the average loss of the
predictions relative to the main prediction: 
\begin{equation}
V(\vt{x}) = E_D[L(y_m,f_D(\vt{x}))].
\label{eq:net-variance}
\end{equation}
It captures the extent to which the various predictions $f_D(\vt{x})$
vary depending on $D$.  

In the case of the 0/1 loss we can also distinguish two opposite 
effects of  variance (and  noise) on the error: in the unbiased case  variance and  noise increase the
error, while in the biased case variance and noise decrease the error.

%%%%%%%% Unbiases and biased variance %%%%%%%%%
There are three components that determine whether $t = y$:
\begin{enumerate}   
  \item Noise: is $t = y_*$ ?   
  \item Bias:  is $y_* = y_m$ ?
  \item Variance: is $y_m = y$ ? 
\end{enumerate}   
Note that bias is either  0 or 1 because neither $y_*$ nor $y_m$ are random variables.
From this standpoint we can consider two different cases: the unbiased and the biased case.

In the unbiased case, $B(\vt{x}) = 0$ and hence $y_* = y_m$. In this case we suffer a loss if  
the  prediction $y$ differs from the main prediction $y_m$ (variance) and the optimal prediction $y_*$ is equal 
to the target $t$, or $y$ is equal to $y_m$, but $y_*$   is different from $t$ (noise).

In the biased case, $B(\vt{x}) = 1$ and hence $y_* \neq y_m$. In this case we suffer a loss if  
the  prediction $y$ is equal to the main prediction $y_m$  and the optimal prediction $y_*$ is equal 
to the target $t$, or if both $y$ is different from  $y_m$ (variance), and $y_*$   is different from $t$ (noise).
Figure~\ref{fig:case-analysis} summarizes the different conditions under which an error can arise, considering the
combined effect of bias, variance and noise on the learner prediction.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
\begin{figure}[t] 
\begin{center}  
%\hspace{-1cm}
\includegraphics  [width = 13cm] {ps/case-analysis.eps}         \\  %\vspace{0.6cm}      
%\vspace*{8pt}
\caption{Case analysis of error.}
\label{fig:case-analysis}
\end{center}    
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Considering the above case analysis of the error,
if we let $P(t \neq y_*) = N(\vt{x}) = \tau$ and   $P(y_m \neq y) = V(\vt{x}) = \sigma$,
in the unbiased case we have
\begin{eqnarray}
\label{eq:unbiased}
  L(t,y) & = & \tau (1 - \sigma ) + \sigma (1- \tau ) \\ \nonumber
         & = & \tau + \sigma - 2 \tau \sigma \\ \nonumber
         & = & N(\vt{x}) + V(\vt{x}) - 2 N(\vt{x}) V(\vt{x}),
\end{eqnarray}
while in the biased case 
\begin{eqnarray}
\label{eq:biased}
  L(t,y) & = & \tau  \sigma +  (1- \tau )  (1 - \sigma )   \\ \nonumber
         & = & 1 - ( \tau + \sigma - 2 \tau \sigma ) \\ \nonumber
         & = & B(\vt{x}) - ( N(\vt{x}) + V(\vt{x}) - 2 N(\vt{x}) V(\vt{x})).
\end{eqnarray}

Note that in the unbiased case (Equation~\ref{eq:unbiased}) the variance is an additive term of the loss function,
while in the biased case (Equation~\ref{eq:biased}) the variance is a subtractive term of the loss function.
Moreover the interaction terms will usually be small, because, for instance, 
if both noise and variance term will be both lower than $0.1$,  the
interaction term $2 N(\vt{x}) V(\vt{x}) $  will be reduced to less than $0.02$.

In order to distinguish between these two different effects of the variance on the loss function,  
Domingos defines the {\em unbiased variance}, $V_u(\vt{x})$, to be the variance when $B(\vt{x}) = 0$ and the {\em biased variance}, 
$V_b(\vt{x})$, to be the variance when $B(\vt{x}) = 1$. We can also define the  {\em net variance} $V_n(\vt{x})$ to take into
account the combined effect of the unbiased and biased variance:
\begin{displaymath}
  V_n(\vt{x}) = V_u(\vt{x}) - V_b(\vt{x}).
\end{displaymath}
Figure \ref{fig:biased_nonbiased_effects} summarizes in graphic form the opposite effects of biased and unbiased variance on the error.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[!t]
\begin{center}
\includegraphics[width=7cm]{ps/buvar.eps}
\caption{Effects of biased and unbiased variance on the error. The unbiased variance increments, while the
biased variance decrements the error.}
\label{fig:biased_nonbiased_effects}
\end{center}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


If we can disregard the noise, the  unbiased variance captures the extents to which the learner deviates from 
the correct prediction $y_m$ (in the unbiased case $y_m = y_*$), while the biased variance captures 
the extents to which the learner  deviates from the incorrect prediction $y_m$ 
(in the biased case $y_m \neq y_*$).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Domingos' Bias-Variance Decomposition}
\label{subsec:Domingos}
\citet{Dom00a} showed that for a  quite general loss function the expected loss is
\begin{equation}
EL(\mathcal{L}, \vt{x}) = c_1 N(\vt{x}) + B(\vt{x}) + c_2 V(\vt{x}).
\label{eq:DomingosBV}
\end{equation}
For the $0/1$ loss function $c_1$ is $2 P_D(f_D(\vt{x}) = y_*) - 1$ and $c_2$ is +1 if $B(\vt{x}) = 0$
and $-1$ if $B(\vt{x}) = 1$. Note that $c_2 V(\vt{x}) = V_u(\vt{x}) - V_b(\vt{x}) = V_n(\vt{x})$ (Equation~\ref{eq:net-variance}), 
and if we disregard the noise, Equation~\ref{eq:DomingosBV} can be simplified to
\begin{equation}
EL(\mathcal{L}, \vt{x}) = B(\vt{x}) + V_n(\vt{x}).
\label{eq:DomingosBV-no-noise}
\end{equation}

Summarizing, one of the most interesting aspects of Domingos' decomposition is that variance
hurts on unbiased points $\vt{x}$, but it helps on biased points.
Nonetheless, to obtain low overall expected loss, we want the bias to
be small, and hence, we see to reduce both the bias and the unbiased
variance. A good classifier will have low bias, in which case the expected loss 
will approximately equal the variance.
%%%%% Average bias, net-variance, biased and unbiased variance, average loss

This decomposition for a single point $\vt{x}$ can be generalized to the
entire population by defining $E_\vt{x}[\cdot]$ to be the expectation with
respect to $P(\vt{x})$.  Then we can define the {\em average bias} $E_\vt{x}[B(\vt{x})]$,
the {\em average unbiased variance} $E_\vt{x}[V_u(\vt{x})]$, and the {\em average
biased variance} $E_\vt{x}[V_b(\vt{x})]$.  In the noise-free case, the expected
loss over the entire population is
\begin{displaymath}
E_\vt{x}[ EL(\mathcal{L},\vt{x}) ]  =  E_\vt{x}[B(\vt{x})] + E_\vt{x}[V_u(\vt{x})] -  E_\vt{x}[V_b(\vt{x})].
%\label{eq:average-error}
\end{displaymath}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Measuring Bias and Variance}
\label{sec:measuringBV}
The procedures to measure bias and variance depend on the characteristics and on the cardinality of the data sets
used.

For synthetic data sets we can generate different sets of training data for each learner to be trained. Then a
large synthetic test set can be generated in order to estimate the bias-variance decomposition of the error for a
specific learner model.

Similarly, if a large data set is available, we can split it in a large learning set and in a large testing set.
Then we can randomly draw subsets of data from the large training set in order to train the learners;
bias-variance decomposition of the error is measured on the large independent test set.

However, in practice, for real data we dispose of only one and often small data set. 
In this case, we can use cross-validation techniques for estimating bias-variance decomposition, but we propose
to use out-of-bag~\citep{Bre01a} estimation procedures, as they are computationally less expensive.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Measuring with Artificial or Large Benchmark Data Sets}
\label{subsec:measuring-artificial}
%%% Set of data sets
\changed
Consider a set $\mathcal{D} = \{D_i\}_{i=1}^n$ of learning sets $D_i = \{ \vt{x}_k, t_k \}_{k=1}^m$.
The data sets $D_i$ can be generated according to some known probability distribution or can be drawn with replacement from a large data
set $\mathcal{D}$ according to an uniform probability distribution.
Here we consider only a two-class case, i.e.
$t_k \in \mathcal{C} = \{-1,1\}, \quad \vt{x}_k \in \vt{X}$, for instance $\vt{X} = \mathbb{R}^d, \quad d \in \mathbb{N}$,
but the extension to the multiclass case is straightforward.

%%% Model produced by a learner and estimate of BV
The estimates of the error, bias, unbiased and biased variance are performed on a test set $\mathcal{T}$ separated from the training set 
$\mathcal{D}$.
In particular these estimates with respect to a single example $(\vt{x}, t) \in \mathcal{T}$ are performed using the classifiers 
$f_{D_i} = \mathcal{L}(D_i)$ produced by a learner $\mathcal{L}$ using training sets $D_i$ drawn from $\mathcal{D}$.
These classifiers produce a prediction $y \in \mathcal{C}$, that is $f_{D_i}(\vt{x}) = y$.
The estimates are performed for all the $(\vt{x}, t) \in \mathcal{T}$, and the overall loss, bias and variance can be evaluated averaging
over the entire test  set $\mathcal{T}$.
\changedEnd

In presence of noise and with the 0/1 loss, the optimal prediction $y_*$
is equal to the label $t$ that is observed more often in the universe $U$ of data points:
\begin{displaymath}
y_*(\vt{x}) = \arg \max_{t \in \mathcal{C}} P(t|\vt{x}).
%\label{eq:optimalprediction-01-loss}
\end{displaymath}
The noise $N(\vt{x})$ for the 0/1 loss can be estimated if we can evaluate the probability of the targets for a given
example $\vt{x}$:
\begin{displaymath}
N(\vt{x}) = \sum_{t \in \mathcal{C}} L(t,y_*)P(t|\vt{x}) = \sum_{t \in \mathcal{C}} || t \neq y_* || P(t|\vt{x}),
\end{displaymath}
where $|| z || = 1$ if $z$ is true, $0$ otherwise. 
In practice it is difficult to estimate the noise for ``real world'' data sets, and to simplify the computation we consider the noise free
case. In this situation we have $y_* = t$. 

%%%%%%% Def, main prediction
The main prediction is a function of the $y = f_{D_i}(\vt{x})$.
Considering a $0/1$ loss, we have 
\begin{displaymath}
y_m = \arg \max (p_1, p_{-1}),
\end{displaymath}
where  $p_1 = P_D (y=1 |\vt{x})$ and $p_{-1} = P_D (y=-1 | \vt{x})$, i.e. the main prediction is
the mode.
To calculate $p_1$, having a test set $\mathcal{T} = \{ \vt{x}_j, t_j \}_{j=1}^r$, it is sufficient to count the number
of learners that predict class 1 on a given input $\vt{x}$:
\begin{displaymath}
p_1(\vt{x}_j) = \frac{\sum_{i=1}^n \Vert f_{D_i}(\vt{x}_j) = 1 \Vert} {n},
%\label{eq:p1} 
\end{displaymath}
where $\Vert z \Vert = 1$ if $z$ is true and $\Vert z \Vert = 0$ if $z$ is false

%%%%%%%% Def Bias %%%%%%%%%
The bias can be easily calculated after the evaluation of the main prediction:
\begin{equation}
B(\vt{x}) = \left\{ \begin{array}{ll}
              1 & \mbox{if $y_m \neq t$} \\
                                                        0 & \mbox{if $y_m = t$}
                                                        \end{array} \right.
                 = \left| \frac{y_m - t}{2} \right|,
\label{eq:bias01}
\end{equation}
or equivalently:
\begin{displaymath}
B(\vt{x}) = \left\{ \begin{array}{ll}
              1 & \mbox{if $p_{corr}(\vt{x}) \leq 0.5$} \\
                                                        0 & \mbox{otherwise},
                                                        \end{array} \right.
\end{displaymath}
where $p_{corr}$ is the probability that a prediction is correct, i.e.
$p_{corr}(\vt{x}) = P(y = t | \vt{x}) = P_D(f_D(\vt{x}) = t)$.

%%%%%%%% Def. Variance %%%%%%%%%
In order to measure the variance $V(\vt{x})$, if we define $ y_{D_i} = f_{D_i}(\vt{x})$,
we have
\begin{displaymath}
V(\vt{x}) = \frac{1}{n} \sum_{i=1}^n L(y_m, y_{D_i})
                 = \frac{1}{n} \sum_{i=1}^n || (y_m \neq y_{D_i}) ||
%\label{eq:net-variance01}
\end{displaymath}

%%%%%%%%%%%%% Unbiased and biased variance %%%%%%%%%%%%%%%%%%%%%%%
The {\em unbiased variance} $V_u(\vt{x})$ and the {\em biased variance} $V_b(\vt{x})$ can be calculated evaluating
if the prediction of each learner differs from the main prediction respectively in the unbiased and in the
biased case:
\begin{displaymath}
V_u(\vt{x}) = \frac{1}{n} \sum_{i=1}^n || (y_m = t) \; {\rm and} \; (y_m \neq y_{D_i}) ||,
                                                        %\label{eq:unb-variance-calc-finite}
\end{displaymath}
\begin{displaymath}
V_b(\vt{x}) = \frac{1}{n} \sum_{i=1}^n 
                          || (y_m \neq t) \; {\rm and} \; (y_m \neq y_{D_i}) ||.
%\label{eq:biased-variance-calc-finite}
\end{displaymath}

%%%% Average loss  on a sample x
In the noise-free case, the {\em average loss on the example $\vt{x}$ }  $E_D(\vt{x})$ is calculated by a simple 
algebraic sum of bias, unbiased and biased variance:
\begin{displaymath}
E_D(\vt{x}) = B(\vt{x}) + V_u(\vt{x}) - V_b(\vt{x}) = B(\vt{x}) + (1 - 2 B(\vt{x})) V(\vt{x}).
%\label{eq:expectederroronx}
\end{displaymath}

%%%%%%%%%%%%% BV decomposition on the entire data set %%%%%%%%%%%%%%%%%%
%%%%% Average bias
\changed
We can easily calculate the {\em average bias, variance, unbiased, biased and net variance},  
averaging over the entire set of the examples of the test set $\mathcal{T} = \{ (\vt{x}_j, t_j) \}_{j=1}^r$.
In the remaining part of this section the indices $j$ refer to the examples that belong to the test set $\mathcal{T}$, while the indices
$i$ refer to the training sets $D_i$, drawn with replacement from the separated training set $\mathcal{D}$, and used to train the
classifiers $f_{D_i}$.

The average quantities are
\changedEnd

\noindent
{\em Average bias}:
\begin{displaymath}
E_\vt{x}[B(\vt{x})] = \frac{1}{r} \sum_{j=1}^r B(\vt{x}_j) = \frac{1}{r} \sum_{j=1}^r  \left| \frac{y_m(\vt{x}_j) - t_j}{2} \right|,
%\label{eq:averagebias}
\end{displaymath}
%%%%%%%% Average variance
{\em Average variance}:
\begin{eqnarray*}
E_\vt{x}[V(\vt{x})] & = & \frac{1}{r} \sum_{j=1}^r V(\vt{x}_j) \\ \nonumber
& = & \frac{1}{nr} \sum_{j=1}^r \sum_{i=1}^n L(y_m(\vt{x}_j), f_{D_i}(\vt{x}_j)) \\ \nonumber
& = & \frac{1}{nr} \sum_{j=1}^r \sum_{i=1}^n || y_m(\vt{x}_j) \neq f_{D_i}(\vt{x}_j) ||,
%\label{eq:average-variance-calc}
\end{eqnarray*} 
%%%%%%%% Average unbiased-variance
{\em Average  unbiased variance}:
\begin{displaymath}
E_\vt{x}[V_u(\vt{x})] = \frac{1}{r} \sum_{j=1}^r V_u(\vt{x}_j) =
\frac{1}{nr} \sum_{j=1}^r  \sum_{i=1}^n 
       || (y_m(\vt{x}_j) = t_j) \; {\rm and} \; (y_m(\vt{x}_j) \neq f_{D_i}(\vt{x}_j)) ||,
%\label{eq:averageunbiasedvariance-calc}
\end{displaymath}
%%%%%%%% Average biased-variance
{\em Average  biased variance}:
\begin{displaymath}
E_\vt{x}[V_b(\vt{x})] = \frac{1}{r} \sum_{j=1}^r V_b(\vt{x}_j) =
\frac{1}{nr} \sum_{j=1}^r  \sum_{i=1}^n 
       || (y_m(\vt{x}_j) \neq t_j) \; {\rm and} \; (y_m(\vt{x}_j) \neq f_{D_i}(\vt{x}_j)) ||,
%\label{eq:averagebiasedvariance-calc}
\end{displaymath}
%%%%%%%% Average net-variance
and the {\em Average  net variance}:
\begin{displaymath}
E_\vt{x}[V_n(\vt{x})] =  \frac{1}{r} \sum_{j=1}^r V_n(\vt{x}_j) =
\frac{1}{r} \sum_{j=1}^r ( V_u(\vt{x}_j) - V_b(\vt{x}_j) ).
%\label{eq:averagenetvariance-calc}
\end{displaymath}

Finally, the average loss on all the examples (with no noise) is the algebraic sum of the average bias, unbiased
and biased variance.
\begin{displaymath}
E_{\vt{x}}[L(t,y)]  =  E_\vt{x}[B(\vt{x})] + E_\vt{x}[V_u(\vt{x})] -  E_\vt{x}[V_b(\vt{x})] 
%\label{eq:average-error-measure}
\end{displaymath} 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Measuring with Small Data Sets}
\label{subsec:measuring-small}
In practice (unlike in theory), we have only one and often small data set $\mathcal{S}$.   
We can simulate multiple training sets by bootstrap replicates   
$S_b  =  \{\vt{x} | \vt{x} $ is drawn at random with replacement from $ \mathcal{S}\}$.
In order to measure bias and variance we can use out-of-bag points, providing in such a way an unbiased estimate of
the error.
%%%%%%% bootstrap replicates %%%%%%%%%%%%%
At first we need to construct $B$ bootstrap replicates of $\mathcal{S}$ (e. g., $B = 200$): $S_1 , \ldots, S_B$. 
%%%%%%%%%% Training learner %%%%%%%%%%%%%%%
Then we apply a learning algorithm $\mathcal{L}$ to each replicate $S_b$ to obtain hypotheses 
$f_b = \mathcal{L}(S_b)$.

%%%%%%%% Predictions on out-of-bag points %%%%%%%%%%%%
Let $T_b = \mathcal{S} \backslash S_b$ be the data points that do not appear in $S_b$ (out of bag points).
We can use these data sets $T_b$ to evaluate the bias-variance decomposition of the error; that is
we compute the predicted values $f_b(\vt{x})$, $\forall \vt{x} {\rm \;
  s.t. \;} \vt{x} \in T_b$. For each data point $\vt{x}$, we  have now the observed corresponding value $t$ and several predictions 
$y_1, \ldots, y_K$, where 
$K = |\{T_b| \vt{x} \in T_b, 1 \leq b \leq B \}|$, $K \leq B$, and on the average $K \simeq B/3$,
because about $1/3$ of the predictors is not trained on a specific input $\vt{x}$. 
\changed
Note that the value of $K$ depends on the specific example $\vt{x}$ considered.
Moreover if $\vt{x} \in T_b$ then $\vt{x} \notin S_b$, hence  $f_b(\vt{x})$ makes a prediction on an unknown example $\vt{x}$.
\changedEnd

%%%%%%%%%%%%%%%%%% Main prediction %%%%%%%%%%%
In order to compute the main prediction, for a two-class classification problem,
we can define
\begin{displaymath}
p_1(\vt{x}) = \frac{1}{K} \sum_{b=1}^B || (\vt{x} \in T_b) {\rm \; and \;} (f_b(\vt{x}) = 1) ||,
\end{displaymath}
\begin{displaymath}
p_{-1}(\vt{x}) = \frac{1}{K} \sum_{b=1}^B || (\vt{x} \in T_b) {\rm \; and \;} (f_b(\vt{x}) = -1) ||.
\end{displaymath}
The main prediction $y_m(\vt{x})$ corresponds to the mode:
\begin{displaymath}
y_m = \arg \max (p_1, p_{-1}).
\end{displaymath}

%%%%%%%%% Bias %%%%%%%%%
The bias can be calculated as in Equation~\ref{eq:bias01}, and the variance $V(\vt{x})$ is
\begin{displaymath}
V(\vt{x}) = \frac{1}{K} \sum_{b=1}^B || (\vt{x} \in T_b) \; {\rm and } \; (y_m \neq f_b(\vt{x})) ||.
\end{displaymath}
%%%%%%%% Biased, unbiased and net variance %%%%%%%%%
Similarly easily computed are the unbiased, biased and net-variance:
\begin{displaymath}
V_u(\vt{x}) = \frac{1}{K} \sum_{b=1}^B 
                          ||  (\vt{x} \in T_b) \; {\rm and} \; (B(\vt{x}) = 0) \; {\rm and} \; (y_m \neq f_b(\vt{x})) ||,
%\label{eq:unb-variance-calc-finite}
\end{displaymath}
\begin{displaymath}
V_b(\vt{x}) = \frac{1}{K} \sum_{b=1}^B 
                          ||  (\vt{x} \in T_b) \; {\rm and} \; (B(\vt{x}) = 1) \; {\rm and} \; (y_m \neq f_b(\vt{x})) ||,
%\label{eq:biased-variance-calc-finite}
\end{displaymath}
\begin{displaymath}
V_n(\vt{x}) = V_u(\vt{x}) - V_b(\vt{x}).
%\label{eq:net-variance-calc-finite}
\end{displaymath}
%%%%%%%%%%% Average loss %%%%%%%%%%%%
Average bias, variance, unbiased, biased and net variance, can be easily calculated 
averaging over all the examples.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Bias-Variance Analysis in SVMs}
\label{sec:BV-SVM}
The bias-variance decomposition of the error represents a powerful tool
to analyze learning processes in learning machines.  
According to the procedures described in the previous section, we measured bias and variance in SVMs, in order to study the
relationships with different kernel types and their parameters.
To accomplish this task we computed bias-variance decomposition of the error on different synthetic and ``real'' data
sets.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[!htb]
\begin{center}
\includegraphics[width=12cm]{ps/P2.eps}
\caption{P2 data set, a bidimensional two class synthetic data set. 
Roman numbers label the regions belonging to the two classes.}
\label{fig:P2}
\end{center}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Experimental Setup}
\label{subsec:expsetup}
In the experiments we employed seven different data sets, both synthetic and ``real''. 
{\em P2} is a synthetic  bidimensional two-class data set;\footnote{The application {\tt gensimple}, 
that we developed to generate the data, is freely available on line at 
{\tt ftp://ftp.disi.unige.it/person/ValentiniG/BV/gensimple}.} 
each region is delimited by one or more of  four simple polynomial and trigonometric functions (Figure \ref{fig:P2}).
The synthetic data set {\em Waveform} is generated from a combination
of two of three ``base'' waves; we reduced the original three classes
of {\em Waveform} to  two, deleting all samples pertaining to class $0$.
The other data sets are all from the UCI repository~\citep{Mer98}. 
Table \ref{fig:features-data-set} summarizes the main features of the data sets used in the
experiments. 
%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{center}
\begin{table}[htb]
\label{fig:features-data-set}
\vspace{0.30cm}
{\centering \begin{tabular}{||l|rrrrr||}
\hline\hline 
Data set           & \# of   & \# of tr. & \# of tr. & \# base  & \# of         \\
                   & attr.   & samples   & sets     & tr. set  & test samples \\ \hline
{\em P2}           & 2          & 100              &  400           & synthetic    &  10000           \\ \hline
{\em Waveform}     & 21         & 100              &  200           & synthetic    &  10000           \\ \hline
{\em Grey-Landsat} & 36         & 100              &  200           & 4425         &  2000            \\ \hline
{\em Letter}       & 16         & 100              &  200           & 614          &  613             \\ \hline
{\em Letter w. noise} & 16      & 100              &  200           & 614          &  613             \\ \hline
{\em Spam}         & 57         & 100              &  200           & 2301         &  2300            \\ \hline
{\em Musk}         & 166        & 100              &  200           & 3299         &  3299            \\ \hline
\hline 
\end{tabular}\par}
\caption{Data sets used in the experiments.}
\end{table}
\end{center}
\normalsize
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In order to perform a reliable evaluation of bias and variance we used small training set and large test sets.
For synthetic data  we  generated the desired number of samples. For real data sets we
used bootstrapping to replicate the data.
In both cases we computed the main prediction, bias, unbiased and biased variance, net-variance according to the
procedures explained in Section~\ref{subsec:measuring-artificial}.
In our experiments, the computation of James' variance and systematic effect~\citep{James03} is reduced to the measurements 
of the net-variance and bias, and hence we did not explicitly compute these quantities (see Appendix {\em A} for details).

With synthetic data sets,
we generated small training sets of about $100$ examples and reasonably large test sets using computer programs.
In fact small samples show bias and variance more clearly than having larger samples. 
We produced $400$ different training sets for {\em P2~} and $200$ training sets for {\em Waveform}.
The test sets were chosen reasonably large ($10000$ examples) to obtain reliable estimates of bias and variance.

For real data sets we first divided the data into a training  $\mathcal{D}$ and a test  $\mathcal{T}$ sets.
If the data sets had a predefined training and test sets reasonably large, we used them (as in {\em
Grey-Landsat~} and {\em Spam}), otherwise we split them in a training and test set of equal size.
Then we drew from $\mathcal{D}$  bootstrap samples. We chose bootstrap samples much smaller than
$|\mathcal{T}|$ ($100$ examples). More precisely we drew $200$ data sets from $\mathcal{D}$, each one consisting of $100$
examples uniformly drawn with replacement.

Summarizing, both with synthetic and real data sets we generated  small training sets  for
each data set and a much larger test set.
Then all the data were normalized in such a way that for each attribute the mean was $0$ and the standard
deviation $1$.
%%%%%%% Software used in the experiments %%%%%%%%%%%%%%
In all our experiments we used  {\em
  NEURObjects}~\citep{Val02h},\footnote{This library may be downloaded
  from the web at {\tt
http://www.disi.unige.it/person/ValentiniG/NEURObjects}.} a C++ library for the development of neural networks and machine learning
applications, and {\em SVM-light}~\citep{Joa99}, a set of C applications for training and testing SVMs.

We developed and used the C++ application {\tt analyze\_BV},  to perform bias-variance decomposition of the 
error.\footnote{The source code is available at {\tt ftp://ftp.disi.unige.it/person/ValentiniG/BV}. Moreover 
C++ classes for bias-variance analysis have been developed as part of the {\em NEURObjects} library.}
 This application analyzes the output of a generic learning machine model and 
computes the main prediction, error, bias, net-variance, unbiased and biased variance using the $0/1$ loss
function.
Other C++ applications have been developed to process and analyze the results, using also
Cshell scripts to train, test and analyze bias-variance decomposition of all the SVM models for each 
specific data set.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[htb]
\begin{center}  
\begin{tabular}{cc}                                                                                                                                                     
%\hspace{-2.0cm} 
\multicolumn{2}{c} {\includegraphics  [width = 7.4cm] {ps/GREY-LANDSATrbf-avgerr.eps} } \\ \vspace{0.6cm} 
\hspace{7.0cm} {(a)}  & \\ 
\hspace{-0cm}
\includegraphics  [width = 7.4cm]{ps/GREY-LANDSATrbf-bias.eps}     &
\hspace{-0cm}
\includegraphics  [width = 7.4cm] {ps/GREY-LANDSATrbf-netvar.eps}         \\ \vspace{0.6cm}
\hspace{-0cm} (b) & \hspace{+0.0cm} (c)  \\
\hspace{-0cm}
\includegraphics  [width = 7.4cm] {ps/GREY-LANDSATrbf-unbvar.eps}         &
\hspace{-0cm}
\includegraphics  [width = 7.4cm] {ps/GREY-LANDSATrbf-biasedvar.eps}         \\ \vspace{0.6cm}
\hspace{-0cm} (d) & \hspace{+0.0cm} (e)  \\
\end{tabular}
\caption{Grey-Landsat data set. Error (a) and its decomposition in bias (b), net variance (c), unbiased
variance (d), and biased variance (e) in SVM RBF, varying both $C$ and $\sigma$.}
\label{fig:GREY-LANDSATrbf-3D}
\end{center}    
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\clearpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Experimental Tasks}
\label{subsec:exptasks}
To evaluate bias and variance in SVMs we conducted experiments with different kernels (Gaussian, polynomial and dot product) and
different kernel parameters.
For each kernel we considered the same set of values for the parameter $C$ that controls the trade-off 
between training error and margin, ranging from $C = 0.01$ to $C=1000$.
%\begin{displaymath}
%C       \in   \{0.01, 0.1, 1, 2, 5, 10, 20, 50, 100, 200, 500, 1000 \} 
%\end{displaymath}
\begin{enumerate}
\item {\bf Gaussian kernels}. We evaluated bias-variance decomposition varying the parameters $\sigma$ of the
kernel and the $C$ parameter.
In particular we analyzed:
  \begin{enumerate}
  \item The relationships between  average error, bias, net-variance, unbiased and biased variance, 
  the $\sigma$ parameter  of the kernel and the $C$ parameter.
        \item The relationships between  generalization error, training error, number of support vectors and capacity with
        respect to $\sigma$.
  \end{enumerate}
We  trained RBF-SVM with all the combinations of the parameters $\sigma$ and $C$, 
using the a set of values for $\sigma$ ranging from $\sigma = 0.01$ to $\sigma = 1000$.
%\begin{displaymath}
%     \sigma  \in  \{0.01, 0.02, 0.1, 0.2, 0.5, 1, 2, 5, 10, 20, 50, 100, 200, 300, 400, 500, 1000\}  \\
%\end{displaymath}
We evaluated about  $200$ different RBF-SVM models for each data set. 

\item {\bf Polynomial kernels}. We evaluated bias-variance decomposition varying the degree of the
kernel and the $C$ parameter. 
In particular we analyzed the relationships between  average error, bias, net-variance, unbiased and biased variance,
the degree of the kernel and the $C$ parameter.

We  trained polynomial-SVM with several combinations of the degree parameter of the kernel and $C$ values, using all the polynomial
degrees between 1 and 10, evaluating in such a way about $120$ different polynomial-SVM models for each data set.
Following the heuristic of Jakkola, the dot product of polynomial kernel was divided by the dimension of the 
input data, to ``normalize'' the dot product before to raise to the degree of the polynomial. 

\item {\bf Dot product kernels}. We evaluated bias-variance decomposition varying the $C$ parameter.
We analyzed the relationships between  average error, bias, net-variance, unbiased and biased variance
  and the parameter $C$ (the regularization factor) of the kernel.
We  trained dot-product-SVM considering different values for the $C$ parameter, evaluating in such a way 
$12$ different dot-product-SVM models for each data set.
\end{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%          
\begin{figure}[htb]
\begin{center}  
%\small
%\vspace{-0.7cm} 
\begin{tabular}{cc} 
\hspace{-0cm}
\includegraphics  [width = 7.4cm] {ps/WAVEFORMrbf.C10.eps}               &
\hspace{-0.0cm}
\includegraphics  [width = 7.4cm] {ps/GREY-LANDSATrbf.C10.eps}         \\  \vspace{0.6cm}
\hspace{-0cm} (a) & \hspace{+0.0cm} (b)  \\
\hspace{-0.0cm}
\includegraphics  [width = 7.4cm] {ps/LETTER-TWOrbf.C0.1.eps}            &
\hspace{-0.0cm}
\includegraphics  [width = 7.4cm] {ps/LETTER-TWOrbf.C1.eps}         \\  \vspace{0.6cm}
\hspace{-0cm} (c) & \hspace{+0.5cm} (d)  \\
\hspace{-0cm}
\includegraphics  [width = 7.4cm]{ps/NOISE-LETTER-TWOrbf.C10.eps}     &
\hspace{-0cm}
\includegraphics  [width = 7.4cm] {ps/SPAMrbf.C1.eps}         \\  \vspace{0.6cm}
\hspace{-0cm} (e) & \hspace{+0.0cm} (f)  \\
\end{tabular}
%\vspace*{8pt}
\caption{Bias-variance decomposition of error in bias, net variance, unbiased
and biased variance in SVM RBF, varying $\sigma$ and for fixed $C$ values:
(a) Waveform, (b) Grey-Landsat, (c) Letter-Two with $C=0.1$, (c) Letter-Two with $C = 1$,
 (e) Letter-Two with added noise and (f) Spam.}
\label{fig:rbf-sigma}
\end{center}    
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Each SVM model required the training of $200$ different SVMs, one for each synthesized or bootstrapped data
set, for a total of $(204+120+12) \times 200 = 67200$ trained SVM for each data set ($134400$ for the data set
{\em P2}, as for this data set we used $400$ data sets for each model). 
The experiments required the training of more than half million of SVMs, considering all the data
sets and of course the testing of all the SVM previously trained in order to evaluate the bias-variance
decomposition of the error of the different SVM models.
For each SVM model we computed the main prediction, bias, net-variance, biased and unbiased variance and the error on each 
example of the test set, and the corresponding average quantities on the overall test set.
%\clearpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Results}
\label{sec:results}
In this section we present the results of the experiments.
We analyzed bias-variance decomposition with respect to the kernel parameters considering separately Gaussian, polynomial
and dot product SVMs, comparing also the results among different kernels.
Here we present the main results. Full results, data and graphics are available by anonymous ftp at
{\tt ftp://ftp.disi.unige.it/person/ValentiniG/papers/bv-svm.ps.gz}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Gaussian Kernels}
\label{subsec:gaussian}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%          
\begin{figure}[htb]
\begin{center}  
%\small
%\vspace{-0.7cm}                                                                                                                                                                                                                                                                                                                        
\begin{tabular}{cc}                                                                                                                                                     
\hspace{-0.0cm}
\includegraphics  [width = 7.4cm] {ps/LETTER-TWOrbf-c.sigma0.01.eps}             &
\hspace{-0.4cm}
\includegraphics  [width = 7.4cm] {ps/LETTER-TWOrbf-c.sigma0.1.eps}         \\ \vspace{0.6cm}
\hspace{-0cm} (a) & \hspace{+0.0cm} (b)  \\  
\hspace{-0cm}
\includegraphics  [width = 7.4cm]{ps/LETTER-TWOrbf-c.sigma1.eps}     &
\hspace{-0.0cm}
\includegraphics  [width = 7.4cm] {ps/LETTER-TWOrbf-c.sigma5.eps}         \\ \vspace{0.6cm}
\hspace{-0cm} (c) & \hspace{+0.0cm} (d)  \\  
\hspace{-0.0cm}
\includegraphics  [width = 7.4cm] {ps/LETTER-TWOrbf-c.sigma20.eps}         &
\hspace{-0.0cm}
\includegraphics  [width = 7.4cm] {ps/LETTER-TWOrbf-c.sigma100.eps}         \\ \vspace{0.6cm}
\hspace{-0cm} (e) & \hspace{+0.0cm} (f)  \\  
\end{tabular}
\caption{Letter-Two data set. Bias-variance decomposition of the error in bias, net variance, unbiased
and biased variance in SVM RBF, while varying $C$ and for some fixed values of $\sigma$:
(a) $\sigma = 0.01$, (b) $\sigma = 0.1$, (c) $\sigma = 1$, (d) $\sigma = 5$, (e) $\sigma = 20$, 
(f) $\sigma = 100$.}
\label{fig:LETTER-TWOrbf-c}
\end{center}    
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Figure~\ref{fig:GREY-LANDSATrbf-3D} depicts the average loss, bias
net-variance, unbiased and biased variance varying the values of
$\sigma$ and the regularization parameter $C$ in {\em RBF-SVM} on the
{\em Grey-Landsat} data set.  We note that $\sigma$ is the most
important parameter: although for very low values of $C$ the SVM
cannot learn, independently of the values of $\sigma$,
(Figure~\ref{fig:GREY-LANDSATrbf-3D} a), the error, the bias, and the
net-variance depend mostly on the $\sigma$ parameter.  In particular
for low values of $\sigma$,  bias is very high (Figure~\ref{fig:GREY-LANDSATrbf-3D} b) and net-variance is
$0$, as biased and unbiased variance are about equal (Figure~\ref{fig:GREY-LANDSATrbf-3D}d and \ref{fig:GREY-LANDSATrbf-3D}e). 
Then the bias suddenly
drops (Figure~\ref{fig:GREY-LANDSATrbf-3D}b), lowering the average
loss (Figure~\ref{fig:GREY-LANDSATrbf-3D}a), and then stabilizes for
higher values of $\sigma$.
Interestingly enough, in this data set (but also in others, data not shown), we note an increment followed
by a decrement of the net-variance, resulting in a sort of ``wave shape'' of the net variance graph
(Figure~\ref{fig:GREY-LANDSATrbf-3D}c). 

Figure~\ref{fig:rbf-sigma} shows the bias-variance decomposition on
different data sets, varying $\sigma$, and for a fixed value of $C$, 
that is a sort of ``slice'' along the $\sigma$ axis of the
Figure~\ref{fig:GREY-LANDSATrbf-3D}.
The plots show that average loss, bias, and variance depend
significantly on $\sigma$ for all the considered data sets, confirming
the existence of a ``high biased region'' for low values of $\sigma$.
In this region, biased and unbiased variance are about equal
(net-variance $V_n = V_u - V_b$ is low).  Then unbiased variance
increases while biased variance decreases (Figure~\ref{fig:rbf-sigma}
a,b,c and d), and finally both stabilize for relatively high values of
$\sigma$.  Interestingly, the average loss and the bias do not
increase for high values of $\sigma$, especially if $C$ is high.

Bias and average loss
increases with $\sigma$ only for very small C values. Note that net-variance and bias show opposite trends
only for small values of C (Figure~\ref{fig:rbf-sigma} c). For larger C values the symmetric trend is
limited only to $\sigma \leq 1$ (Figure~\ref{fig:rbf-sigma} d), otherwise bias stabilizes and net-variance slowly decreases. 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[!htb]
\begin{center}  
%\small
%\vspace{-0.7cm}                                                                                                                                                                                                                                                                                                        
\hspace{-0cm}                                                                                                                                           
\includegraphics  [width = 13.2cm] {ps/s0.01c1.xyz-1.eps}               
\caption{The real valued function computed by the SVM on the P2 data set with  $\sigma = 0.01$, $C=1$.}
\label{fig:function0.01}
\end{center}    
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Figure~\ref{fig:LETTER-TWOrbf-c}  shows more in detail the effect of the C parameter on bias-variance decomposition. 
For $C \geq 1$ there are no variations of the average error, bias and variance for
a fixed value of $\sigma$. Note that for very low values of $\sigma$ (Figure~\ref{fig:LETTER-TWOrbf-c}a and b) 
there is no learning.
In the Letter-Two data set, as in other data sets (figures not shown), 
only for small $C$ values we have variations in bias and variance values
(Figure~\ref{fig:LETTER-TWOrbf-c}).

 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Discriminant Function Computed by the SVM-RBF Classifier}
\label{subsubsec:real-valued}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[!htb]
\begin{center}
%\small
%\vspace{-0.7cm}                                                                                                                                                                                                                                                                                                        
\hspace{-0cm}                                                                                                                                           
\includegraphics  [width = 13.2cm] {ps/s1c1.xyz-1.eps}                  
\caption{The real valued function computed by the SVM on the P2 data set, with $\sigma = 1$, $C=1$.}
\label{fig:function1}
\end{center}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
In order to get insights into the behaviour of the SVM learning algorithm with Gaussian kernels we plotted
the real-valued functions computed  without considering the discretization step performed through the sign 
function.
The real valued function computed by a Gaussian SVM is 
\begin{displaymath}
f(\mathbf{x}, \mathbf{\alpha}, b) = \sum_{i \in SV} y_i \alpha_i \exp(- \|\mathbf{x_i} - \mathbf{x}\|^2 / \sigma^2)+ b,
\end{displaymath}
where the $\alpha_i$ are the Lagrange multipliers found by the solution of the dual optimization problem,
the $\mathbf{x_i} \in SV$ are the support vectors, that is the points for which $\alpha_i > 0$.

We plotted the surface computed by the Gaussian SVM with the synthetic data set {\em P2}. Indeed it is the only surface
that can be easily visualized, as the data are bidimensional and the resulting real valued function can be easily
represented through a wireframe three-dimensional surface.
The SVMs are trained with exactly the same training set composed by 100 examples. The outputs are referred to
a test set of 10000 examples, selected in an uniform way through all the data domain. 
In particular we considered a grid of equi-spaced data at 0.1 interval in a two dimensional  $10 \times 10$ input 
space. 
If $f(\mathbf{x}, \mathbf{\alpha}, b) > 0$ then the SVM matches up the example $\vt{x}$ with class $1$,
otherwise with class $2$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%          
\begin{figure}[!b]
\begin{center}  
%\small
%\vspace{-0.7cm}                                                                                                                                                                                                                                                                                                                        
\begin{tabular}{cc}                                                                                                                                                     
\hspace{-0.0cm}
\includegraphics  [width = 7.4cm] {ps/s20c1.xyz-1.eps}                   &
\hspace{-0.4cm}
\includegraphics  [width = 7.4cm] {ps/s20c1000.xyz-1.eps}         \\ \vspace{0.6cm}
\hspace{-0cm} (a) & \hspace{+0.0cm} (b)  \\  
\hspace{-0cm}
\includegraphics  [width = 7.4cm]{ps/s500c1.xyz-1.eps}     &
\hspace{-0.0cm}
\includegraphics  [width = 7.4cm] {ps/s500c1000.xyz-1.eps}         \\ \vspace{0.6cm}
\hspace{-0cm} (c) & \hspace{+0.0cm} (d)  \\  
\end{tabular}
\caption{The real valued function computed by the SVM on the P2 data set. (a) $\sigma = 20$ $C=1$, (b) $\sigma = 20$ $C=1000$,
(c) $\sigma = 500$ $C=1$, (d) $\sigma = 500$ $C=1000$.}
\label{fig:function20}
\end{center}    
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

With small values of $\sigma$ we have ``spiky'' functions: the response is high around the support vectors, and is close
 to 0 in all the other regions of the input domain (Figure~\ref{fig:function0.01}).
In this case we have overfitting: a large error on the test set (about $46$ \% with $\sigma=0.01$ and  $42.5$ \% 
with $\sigma=0.02$ ), and a training error near to 0.

If we enlarge the values of $\sigma$ we obtain a wider response on the input domain and the error decreases 
(with $\sigma = 0.1$ the error is about $37$ \%).
With $\sigma = 1$ we have a smooth function that fits quite well the data (Figure~\ref{fig:function1}). 
In this case the error drops down to about $13$ \%.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%          
\begin{figure}[!tb]
\begin{center}
%\small
%\vspace{-0.7cm}                                                                                                                                                                                                                                                                                                                        
\begin{tabular}{cc}                                                                                                                                                     
\hspace{-0cm}
\includegraphics  [width = 7.4cm] {ps/GREY-LANDSATrbf-large-sigma.C0.1.eps}              &
\hspace{-0cm}
\includegraphics  [width = 7.4cm] {ps/GREY-LANDSATrbf-large-sigma.C1.eps}         \\  \vspace{0.6cm}
\hspace{-0cm} (a) & \hspace{+0cm} (b)  \\
\hspace{-0cm}
\includegraphics  [width = 7.4cm]{ps/GREY-LANDSATrbf-large-sigma.C10.eps}     &
\hspace{-0.0cm}
\includegraphics  [width = 7.4cm] {ps/GREY-LANDSATrbf-large-sigma.C100.eps}         \\  \vspace{0.6cm}
\hspace{-0cm} (c) & \hspace{+0cm} (d)  \\
\end{tabular}
\vspace{-0cm}
\caption{Grey-Landsat data set. Bias-variance decomposition of error in bias, net variance, unbiased
and biased variance in SVM RBF, while varying $\sigma$ and for some fixed values of $C$:
(a) $C = 0.1$, (b) $C = 1$, (c) $C = 10$, (d) $C = 100$.}
\label{fig:GREY-LANDSATrbf-large-sigma}
\end{center}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Enlarging too much  $\sigma$  we have a too smooth function (Figure~\ref{fig:function20} (a)), and the error 
increases to about $37$ \%: in this case the high bias is due to an excessive smoothing of the function. 
Increasing the values of the regularization parameter C (in order to better fit the data), we can diminish the 
error to about $15$ \%: the shape of the function now is less smooth (Figure~\ref{fig:function20} (b)).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%           
\begin{figure}[!tb]
\begin{center}
%\small
%\vspace{-0.7cm}                                                                                                                                                                                                                                                                                                                        
\begin{tabular}{cc}                                                                                                                                                     
\hspace{-0cm}
\includegraphics  [width = 7.4cm] {ps/P2rbf-large-sigma.C1.eps} &
\hspace{-0.0cm}
\includegraphics  [width = 7.4cm] {ps/P2rbf-large-sigma.C1000.eps}         \\  \vspace{0.6cm}
\hspace{-0cm} (a) & \hspace{+0.0cm} (b)  \\
\hspace{-0cm}
\includegraphics  [width = 7.4cm]{ps/MUSKrbf-large-sigma.C1.eps}     &
\hspace{-0.0cm}
\includegraphics  [width = 7.4cm] {ps/MUSKrbf-large-sigma.C1000.eps}         \\  \vspace{0.6cm}
\hspace{-0cm} (c) & \hspace{+0.0cm} (d)  \\
\end{tabular}
\vspace{-0cm}
\caption{Bias-variance decomposition of the error in bias, net variance, unbiased
and biased variance in SVM RBF, while varying $\sigma$ and for some fixed values of $C$:
(a) P2, with $C = 1$,  (b) P2, with  $C = 1000$, (c) Musk, with $C = 1$, (d) Musk, with  $C = 1000$.}
\label{fig:P2rbf-large-sigma}
\end{center}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\changed
As noted in~\citet{Scholk02}, using very large values of sigma, we have a very smooth discriminant function 
(in practice a plane), and increasing it even further does not change anything. 
Indeed, enlarging $\sigma$ to $500$ we obtain a plane (Fig~\ref{fig:function20} (c)), and a very
biased function (error about $45$ \%), and even if we increment C, 
we can obtain  better results, but always with a large error (about $35$ \%, Fig~\ref{fig:function20} (d)).
\changedEnd

%\clearpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Behavior of SVMs with Large $\sigma$ Values}
\label{subsubsec:large-sigma}

Fig~\ref{fig:GREY-LANDSATrbf-3D} and \ref{fig:rbf-sigma} show that $\sigma$ parameter plays  a sort of smoothing
effect, as the value of $\sigma$ increases. In particular with large values of $\sigma$ we did not observe any increment of
bias nor decrement of variance. In order to get insights into this counter-intuitive behaviour we tried to answer these two
questions:
\begin{enumerate}
\item Does the bias increase while variance decrease with large values of $\sigma$, and what is the combined effect 
of bias-variance on the error?
\item In this situation (large values for $\sigma$), what is the effect of the C parameter?
\end{enumerate}

In Figure~\ref{fig:rbf-sigma}  we do not observe an increment of bias with large values 
of $\sigma$, but we limited our experiments to values of $\sigma \leq 100$. Here we investigate the effect for larger values of
$\sigma$ (from 100 to 1000).

In most cases, also increasing the values of $\sigma$ right to 1000 we do not observe an increment of the 
bias and a substantial decrement of the variance. 
Only for low values of C, that is $C < 1$, the bias and the error increase with  large values of $\sigma$ 
(Figure~\ref{fig:GREY-LANDSATrbf-large-sigma}).
With the P2 data set the situation is different: in this case we  observe an increment of the bias and the error with large values of
$\sigma$, even if with large values of C the increment rate is lower (Figure~\ref{fig:P2rbf-large-sigma} a and b).

Also with the musk data set we note an increment of the error with very large values of $\sigma$, but surprisingly this is due to an
increment of the unbiased variance, while the bias is quite stable, at least for values of $C > 1$,
(Figure~\ref{fig:P2rbf-large-sigma} c and d).


Larger values of C counter-balance the bias introduced by large values of  $\sigma$. 
But with some distributions of the data  too large values of  $\sigma$ produce too smooth functions, and also
incrementing C it is very difficult to fit the data. Indeed, the discriminant function computed by the RBF-SVM with the P2
data set (that is the function computed without considering the sign function) is too smooth for large values of $\sigma$: for
$\sigma = 20$, the error is about 37\%, due almost entirely to the large bias, (Figure~\ref{fig:function20} a), 
and for $\sigma = 500$ the error is about 45 \% and also incrementing the $C$ value to 1000, we obtain a surface 
that fits the data better, but with an error that remains large (about 35\%). 
\changed
Indeed with very large values of $\sigma$ the Gaussian kernel becomes nearly linear~\citep{Scholk02} and if the data set is
very far from being linearly separable, as with the {\em P2} data set (Figure~\ref{fig:P2}), the error increases, especially in the bias
component (Figure~\ref{fig:P2rbf-large-sigma} (a) and (b)).
\changedEnd
Summarizing with large $\sigma$ values  bias can increment, while net-variance tends to stabilize, but this effect can be
counter-balanced by larger $C$ values.




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Relationships between Generalization Error, Training Error, Number of Support Vectors and Capacity}
\label{subsubsec:BV-relationships}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%          
\begin{figure}[!tb]
\begin{center}
%\small
%\vspace{-0.7cm}                                                                                                                                                                                                                                                                                                                        
\begin{tabular}{cc}                                                                                                                                                     
%\hspace{-1.5cm}
\includegraphics  [width = 7.4cm] {ps/LETTER-TWOrbf-rescaled-train-test.C1.eps}                  &
%\hspace{-0.4cm}
\includegraphics  [width = 7.4cm] {ps/LETTER-TWOrbf-rescaled-train-test.C10.eps}         \\  \vspace{0.6cm}
\hspace{-0cm} (a) & \hspace{-0.0cm} (b)  \\
%\hspace{-1.5cm}
\includegraphics  [width = 7.4cm]{ps/LETTER-TWOrbf-rescaled-train-test.C100.eps}     &
\hspace{-0.cm}
\includegraphics  [width = 7.4cm] {ps/LETTER-TWOrbf-rescaled-train-test.C1000.eps}         \\  \vspace{0.6cm}
\hspace{-0cm} (c) & \hspace{-0.0cm} (d)  \\
\end{tabular}
\caption{Letter-Two data set. Error, bias, training error, support vector rate, and estimated VC dimension in  SVM RBF, 
while varying the $\sigma$ parameter and for some fixed values of $C$:
(a) $C = 1$, (b) $C = 10$, (c) $C = 100$, and $C = 1000$.}
\label{fig:LETTERrbf-sigma-train-test1}
\end{center}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Looking at Figure~\ref{fig:GREY-LANDSATrbf-3D} and \ref{fig:rbf-sigma}, 
we see that SVMs do not learn for small values of $\sigma$.
Moreover the low error region is
relatively large with respect to $\sigma$ and $C$.

In this section we evaluate the relationships between the estimated generalization error, the bias, 
the training error, the number of support vectors and the estimated  Vapnik Chervonenkis dimension, in order to answer the
following questions:
\begin{enumerate}
\item Why SVMs do not learn for small values of $\sigma$?
\item Why we have a so large bias for small values of $\sigma$?
\item Can we use the variation of the number of support vectors to predict the ``low error'' region?
\item Is there any relationship between the bias, variance and VC dimension, 
and can we use this last one to individuate the ``low error'' region?
\end{enumerate}

The generalization error, bias, training error, number of support vectors and the  Vapnik Chervonenkis dimension
are estimated  averaging with respect to 400 SVMs ({\em P2} data set) or 200 SVMs (other data
sets) trained with different bootstrapped training sets composed by 100 examples each
one. The test error and the bias are estimated with respect to an independent and sufficiently large data set.

The {\em VC dimension} is estimated using the Vapnik's bound based on the radius $R$ of the sphere that contains all the 
data (in the feature space), approximated through the sphere centered in the origin, and on the norm of the weights 
in the feature space~\citep{Vap98}.
In this way the VC dimension is overestimated but it is easy to compute and we are interested mainly in the comparison
 of the VC dimension of different SVM models:
\begin{displaymath}
VC \leq  R^2 \cdot \| \mathbf{w} \|^2 + 1,
\end{displaymath}
where
\begin{displaymath}
\| \mathbf{w} \|^2 = \sum_{i \in SV} \sum_{j \in SV} \alpha_i \alpha_j K(\mathbf{x_i}, \mathbf{x_j}) y_i y_j
\end{displaymath}
and
\begin{displaymath}
R^2 = \max_{i} K(\mathbf{x_i}, \mathbf{x_i}).
\end{displaymath}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%          
\begin{figure}[!tb]
\begin{center}
%\small
%\vspace{-0.7cm}                                                                                                                                                                                                                                                                                                                        
\begin{tabular}{cc}                                                                                                                                                     
\hspace{-0cm}
\includegraphics  [width = 7.4cm] {ps/GREY-LANDSATrbf-rescaled-train-test.C1.eps}                &
\hspace{-0cm}
\includegraphics  [width = 7.4cm] {ps/GREY-LANDSATrbf-rescaled-train-test.C10.eps}         \\  \vspace{0.6cm}
\hspace{-0cm} (a) & \hspace{-0.0cm} (b)  \\
\hspace{-0cm}
\includegraphics  [width = 7.4cm]{ps/GREY-LANDSATrbf-rescaled-train-test.C100.eps}     &
\hspace{-0cm}
\includegraphics  [width = 7.4cm] {ps/GREY-LANDSATrbf-rescaled-train-test.C1000.eps}         \\  \vspace{0.6cm}
\hspace{-0cm} (c) & \hspace{-0.0cm} (d)  \\
\end{tabular}
\caption{Grey-Landsat data set. Error, bias, training error, support vector rate, and estimated VC dimension in  SVM RBF, 
while varying the $\sigma$ parameter and for some fixed values of $C$:
(a) $C = 1$, (b) $C = 10$, (c) $C = 100$, and $C = 1000$.}
\label{fig:GREYrbf-sigma-train-test1}
\end{center}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
The number of support vectors is expressed as the halved ratio of the number (\% $SV$) of support vectors with 
respect to the total number of training data:
\begin{displaymath}
\%SV = \frac{\#SV}{\#training data \cdot 2}.
\end{displaymath}
In the graphs shown in Figure~\ref{fig:LETTERrbf-sigma-train-test1} and Figure~\ref{fig:GREYrbf-sigma-train-test1}, 
on the left y axis is represented the error, training error and bias, and the halved ratio of support vectors. 
On the right y axis is reported the estimated Vapnik Chervonenkis dimension. 

For very small values of $\sigma$ the training error is very small (about 0), while the number of support vectors is 
very high, and high is also the error and the bias
(Figure\ref{fig:LETTERrbf-sigma-train-test1} and \ref{fig:GREYrbf-sigma-train-test1}).
These facts support the hypothesis of overfitting problems with small values of $\sigma$. 
Indeed the real-valued function computed by the SVM (that is the function computed without considering the sign function, 
see Section~\ref{subsubsec:real-valued}) is very spiky with small values of $\sigma$ (Figure~\ref{fig:function0.01}). 
The response of the SVM is high only in small areas around the support vectors, while in all the other areas 
``not covered'' by the support vectors the response is very low (about 0), that is the SVM is not able to get a decision, 
with a consequently very high bias. 
In the same region (small values for $\sigma$) the net variance is usually very small, for either one 
of these reasons: 1) biased and unbiased variance are almost equal because the SVM
performs a sort of random guessing for the most part of the unknown data; 2) both biased and unbiased variance are about 0, 
showing that all the SVMs tend to answer in the same  way independently of a particular instance of 
the training set (Figure~\ref{fig:rbf-sigma} a, b and f).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%            
\begin{figure}[!b]
\begin{center}
%\small
%\vspace{-0.7cm}                                                                                                                                                                                                                                                                                                                        
\begin{tabular}{cc}                                                                                                                                                     
\hspace{-0.0cm}
\includegraphics  [width = 7.4cm] {ps/WAVEFORMpoly.C0.1.eps}             &
\hspace{-0.4cm}
\includegraphics  [width = 7.4cm] {ps/WAVEFORMpoly.C50.eps}         \\  \vspace{0.6cm}
\hspace{-0cm} (a) & \hspace{+0.0cm} (b)  \\
\hspace{-0cm}
\includegraphics  [width = 7.4cm]{ps/LETTER-TWOpoly.C0.1.eps}     &
\hspace{-0.0cm}
\includegraphics  [width = 7.4cm] {ps/LETTER-TWOpoly.C50.eps}         \\  \vspace{0.6cm}
\hspace{-0.0cm} (c) & \hspace{+0.0cm} (d)  \\
\end{tabular}
\caption{Bias-variance decomposition of the error in bias, net variance, unbiased
and biased variance in polynomial SVM, while varying the degree and for some fixed values of $C$:
(a) Waveform, $C = 0.1$, (b) Waveform, $C = 50$, (c) Letter-Two, $C = 0.1$, (d) Letter-Two, $C = 50$.}
\label{fig:WAVEFORMpoly-degree-rid}
\end{center}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Enlarging $\sigma$ we obtain a wider response on the input domain:  the real-valued function computed by the SVM 
becomes smoother (Figure~\ref{fig:function1}), as the ``bumps'' around the support vectors become wider
and the SVM can decide also on unknown examples. At the same time the number of support vectors decreases 
(Figure~\ref{fig:LETTERrbf-sigma-train-test1} and \ref{fig:GREYrbf-sigma-train-test1}). 

Considering the variation of the ratio of the support vectors with $\sigma$,  in all data sets the trend of the
rate of support vectors follows the error, with a sigmoid shape that sometimes becomes an U shape for small 
values of C (Figure\ref{fig:LETTERrbf-sigma-train-test1} and \ref{fig:GREYrbf-sigma-train-test1}). 
This is not surprising because it is known that the support
vector ratio offers an approximation of the generalization error of the SVMs~\citep{Vap98}.
Moreover, on all the data sets the \%SV decreases in the ``stabilized'' region, while in the transition region remains high.
As a consequence the decrement in the number of support vectors shows that we are entering the ``low error'' region, and in 
principle we can use this information to detect this region.

\changed
In our experiments, an inspection of the support vectors relative to the {\em Grey-Landsat} and 
{\em Waveform} data sets found  that most of the
support vectors are shared in polynomial and Gaussian kernels with respectively the best degree and $\sigma$ parameters.
Even if these results confirmed the ones found by other authors (see e.g.~\cite{Vap98}), it is worth noting that we did not perform a
systematic study on this topic: we considered only two data sets and we compared only few hundreds of different SVMs.
\changedEnd


%%%%%%%%% VC dim %%%%%%%%%%%%
In order to analyze the role of the VC dimension on the generalization ability of learning machines, we know from statistical learning
theory that the form of the bounds of the generalization error $E$ of SVMs is 
\begin{equation}
E(f(\sigma,C)_n^k)) \leq E_{emp}(f(\sigma,C)_n^k)) + \Phi(\frac{h_k}{n}),
\label{eq:errbound}
\end{equation}
where $f(\sigma,C)_n^k$ represents the set of functions computed by an RBF-SVM trained with $n$ examples and with
parameters $(\sigma_k, C_k)$ taken from a set of parameters $S = \{(\sigma_i, C_i), i \in \mathbb{N} \}$, 
$E_{emp}$ represents the empirical error and $\Phi$  the confidence interval that depends on the cardinality $n$ of the data set and on the
VC dimension $h_k$ of the set of functions identified by the actual selection of the parameters $(\sigma_k, C_k)$.
In order to obtain good generalization capabilities we need to minimize both the empirical risk and the confidence interval.
According to Vapnik's bounds (Equation~\ref{eq:errbound}), in Figure~\ref{fig:LETTERrbf-sigma-train-test1} and 
\ref{fig:GREYrbf-sigma-train-test1}  the lowest
generalization error is obtained for a small empirical risk and a small estimated VC dimension.

But sometimes with relatively small values of $VC$ we may have a very large error, as the training error and 
the number of support vectors increase with very large values of $\sigma$ 
(Figure~\ref{fig:LETTERrbf-sigma-train-test1} a and \ref{fig:GREYrbf-sigma-train-test1} a).
Moreover with a very large estimate of the VC dimension and low empirical error (Figure~\ref{fig:LETTERrbf-sigma-train-test1} and
\ref{fig:GREYrbf-sigma-train-test1}) we may have a relatively low generalization error.
In conclusion it seems  very difficult to use in practice these estimate of the VC dimension to infer the generalization
abilities of the SVM. In particular it seems unreliable to use the VC dimension to infer the ``low error'' region of the RBF-SVM.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[!htb]
\begin{center}  
\begin{tabular}{cc}                                                                                                                                                     
%\hspace{-2.0cm} 
\multicolumn{2}{c} {\includegraphics  [width = 8.1cm] {ps/P2poly-avgerr.eps} } \\ \vspace{0.6cm} 
\hspace{7.0cm} {(a)}  & \\ 
\hspace{-0cm}
\includegraphics  [width = 8.1cm]{ps/P2poly-bias.eps}     &
\hspace{-0cm}
\includegraphics  [width = 8.1cm] {ps/P2poly-netvar.eps}         \\ \vspace{0.6cm}
\hspace{-0cm} (b) & \hspace{+0.0cm} (c)  \\
\end{tabular}
\caption{P2 data set. Error (a) and its decomposition in bias (b) and net variance (c), 
varying both $C$ and the polynomial degree.}
\label{fig:P2poly-3D-rid}
\end{center}    
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Polynomial and Dot Product Kernels}
\label{subsec:poly-dotprod}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%          
\begin{figure}[!htb]
\begin{center}
%\small
%\vspace{-0.7cm}                                                                                                                                                                                                                                                                                                                        
\begin{tabular}{cc}                                                                                                                                                     
\hspace{-0.0cm}
\includegraphics  [width = 7.4cm] {ps/LETTER-TWOpoly-c.degree2.eps}              &
\hspace{-0.0cm}
\includegraphics  [width = 7.4cm] {ps/LETTER-TWOpoly-c.degree3.eps}         \\ \vspace{0.6cm}
\hspace{-0.0cm} (a) & \hspace{+0.0cm} (b)  \\  
\hspace{-0.0cm}
\includegraphics  [width = 7.4cm]{ps/LETTER-TWOpoly-c.degree5.eps}     &
\hspace{-0.0cm}
\includegraphics  [width = 7.4cm] {ps/LETTER-TWOpoly-c.degree10.eps}         \\ \vspace{0.6cm}
\hspace{-0.0cm} (c) & \hspace{+0.0cm} (d)  \\   
\end{tabular}
\caption{Letter-Two data set. Bias-variance decomposition of error in bias, net variance, unbiased
and biased variance in polynomial SVM, while varying $C$ and for some polynomial degrees:
(a) $degree = 2$, (b) $degree = 3$, (c) $degree = 5$, (d) $degree = 10$}
\label{fig:LETTER-TWOpoly-c-rid}
\end{center}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
In this section we analyze the characteristics of bias-variance decomposition of the error in polynomial SVMs, 
varying the degree of the kernel and the regularization parameter C.

Error shows a U shape with respect to the degree. This shape depends on unbiased variance
(Figure~\ref{fig:WAVEFORMpoly-degree-rid} a and b), or both by bias and unbiased
variance (Figure~\ref{fig:WAVEFORMpoly-degree-rid} c and d).
The U shape of the error with respect to the degree tends to be more flat for increasing values of C,
and  net-variance and bias show often opposite trends (Figure~\ref{fig:P2poly-3D-rid}).


Average error and bias tends to be higher for low C and degree values,
but, incrementing the degree, the error is less sensitive to $C$ values
(Figure~\ref{fig:LETTER-TWOpoly-c-rid}). 

Bias is flat (Figure~\ref{fig:WAVEFORMpoly-3D-rid} a) or decreasing with respect 
to the degree (Figure~\ref{fig:P2poly-3D-rid} b), or it can be constant or decreasing, depending on
C (Figure~\ref{fig:WAVEFORMpoly-3D-rid} b).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[!htb]
\begin{center}  
\begin{tabular}{cc}                                                                                                                                                     
%\hspace{-2.0cm} 
\hspace{-0.0cm}
\includegraphics  [width = 8.1cm]{ps/WAVEFORMpoly-bias.eps}     &
\hspace{-0.0cm}
\includegraphics  [width = 8.1cm] {ps/SPAMpoly-bias.eps}         \\ \vspace{0.6cm}
\hspace{-0.0cm} (a) & \hspace{+0.0cm} (b)  \\
\end{tabular}
\caption{Bias  in polynomial SVMs with (a) Waveform and (b) Spam data sets, 
varying both $C$ and  polynomial degree.}
\label{fig:WAVEFORMpoly-3D-rid}
\end{center}    
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Unbiased variance shows an U shape (Figure~\ref{fig:WAVEFORMpoly-degree-rid} a and b) or it increases 
(Figure~\ref{fig:WAVEFORMpoly-degree-rid} c) with respect 
to the degree, and  the net-variance follows the shape of the unbiased variance.
Note that in the P2 data set (Figure~\ref{fig:P2poly-3D-rid}) bias and net-variance follow the classical opposite
trends with respect to the degree. This is not the case with other data sets (see, e.g. 
Figure~\ref{fig:WAVEFORMpoly-degree-rid}).

For large values of C bias and net-variance tend to converge, as a result of the bias reduction 
and net-variance increment (Figure~\ref{fig:P2SPAMpoly-c-rid}), or because 
both stabilize at similar values (Figure~\ref{fig:LETTER-TWOpoly-c-rid}).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%          
\begin{figure}[!htb]
\begin{center}
%\small
%\vspace{-0.7cm}                                                                                                                                                                                                                                                                                                                        
\begin{tabular}{cc}                                                                                                                                                     
\hspace{-0.0cm}
\includegraphics  [width = 7.4cm] {ps/P2poly-c.degree6.eps}              &
\hspace{-0.0cm}
\includegraphics  [width = 7.4cm] {ps/SPAMpoly-c.degree3.eps}         \\ \vspace{0.6cm}
\hspace{-0.0cm} (a) & \hspace{+0.0cm} (b)  \\  
\end{tabular}
\caption{Bias-variance decomposition of the error in bias, net variance, unbiased
and biased variance in polynomial SVM, varying $C$:
(a) P2 data set with $degree = 6$, (b)  Spam data set with $degree = 3$.}
\label{fig:P2SPAMpoly-c-rid}
\end{center}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In dot product SVMs bias and net-variance show opposite trends: bias decreases, while net-variance and unbiased
variance tend to increase with C (Figure~\ref{fig:dot-prod-all}). On the data set P2 this trend is not observed, as in
this task the bias is very high and the SVM does not perform better than random guessing
(Figure~\ref{fig:dot-prod-all}a). The minimum of the average loss for relatively low values of C is the result of the
decrement of the bias and the increment of the net-variance: it is achieved usually before the crossover of 
bias and net-variance curves and before the stabilization of the bias and the net-variance for large values of C.
The biased variance remains small independently of C.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%          
\begin{figure}[!htb]
\begin{center}
%\small                                                                                                                                                                                                                                                                                                         
\begin{tabular}{cc}                                                                                                                                                     
\hspace{-0.0cm}
\includegraphics  [width = 7.4cm] {ps/P2dotprod.eps}         & 
\hspace{-0.0cm}
\includegraphics  [width = 7.4cm] {ps/GREY-LANDSATdotprod.eps}         \\  \vspace{0.6cm} 
\hspace{-0.0cm} (a) & \hspace{+0.0cm} (b)  \\
\hspace{-0.0cm}
\includegraphics  [width = 7.4cm] {ps/LETTER-TWOdotprod.eps}             &
\hspace{-0.0cm}
\includegraphics  [width = 7.4cm] {ps/NOISE-LETTER-TWOdotprod.eps}         \\  \vspace{0.6cm}
\hspace{-0.0cm} (c) & \hspace{+0.0cm} (d)  \\
\hspace{-0cm}
\includegraphics  [width = 7.4cm] {ps/SPAMdotprod.eps}         & 
\hspace{-0cm}
\includegraphics  [width = 7.4cm] {ps/MUSKdotprod.eps}         \\  \vspace{0.6cm} 
\hspace{-0cm} (e) & \hspace{+0.0cm} (f)  \\
\end{tabular}
\caption{Bias-variance decomposition of error in bias, net variance, unbiased
and biased variance in dot product SVM,  varying $C$:
(a) P2, (b) Grey-Landsat, (c) Letter-Two, (d) Letter-Two with added noise, (e) Spam, (f) Musk.}
\label{fig:dot-prod-all}
\end{center}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\clearpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Comparing Kernels}
\label{subsec:comp-kernels}
In this section we compare the bias-variance decomposition of the error with respect to the C parameter, considering
Gaussian, polynomial and dot product kernels. For each kernel and for each data set the best results are selected.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{table}[!h]
\label{tab:BVdecomp-best-results}
\begin{center}
%%\vspace{-1cm}  
\small
{\centering \begin{tabular}{|l|l|l|l|l|l|l|} 
\hline  
\hspace{1cm} & $\mathbf{Parameters}$ & {\bf Avg. } & {\bf Bias} & {\bf Var. } & {\bf Var. } &  {\bf Net }\\  
             & $                   $ & {\bf Error} &            & {\bf unb. } & {\bf bias.} &  {\bf Var.}\\  
\hline   \hline 
\multicolumn{7}{|l|}{Data set {\em P2}}  \\ \cline{2-7}
RBF-SVM     &  $C=20, \quad \sigma = 2$   & 0.1516 &  0.0500  &   0.1221  & 0.0205  & 0.1016 \\  \cline{2-7}
Poly-SVM    &  $C=10, \quad degree = 5$   & 0.2108 &  0.1309  &   0.1261  & 0.0461  & 0.0799 \\  \cline{2-7}
D-prod SVM  &  $C=500 $                   & 0.4711 &  0.4504  &   0.1317  & 0.1109  & 0.0207 \\  \cline{1-7}
\multicolumn{7}{|l|}{Data set {\em Waveform}}  \\ \cline{2-7}
RBF-SVM     &  $C=1, \quad \sigma = 50$   & 0.0706 &  0.0508  &   0.0356  & 0.0157  & 0.0198 \\  \cline{2-7}
Poly-SVM    &  $C=1, \quad degree = 1 $   & 0.0760 &  0.0509  &   0.0417  & 0.0165  & 0.0251 \\  \cline{2-7}
D-prod SVM  &  $C=0.1 $                   & 0.0746 &  0.0512  &   0.0397  & 0.0163  & 0.0234 \\  \cline{1-7}
\multicolumn{7}{|l|}{Data set {\em Grey-Landsat}}  \\ \cline{2-7}
RBF-SVM     &  $C=2, \quad \sigma = 20$  & 0.0382 &  0.0315  &   0.0137  & 0.0069  & 0.0068 \\  \cline{2-7}
Poly-SVM    &  $C=0.1, \; degree = 5$     & 0.0402 &  0.0355  &   0.0116  & 0.0069  & 0.0047 \\  \cline{2-7}
D-prod SVM  &  $C=0.1 $                   & 0.0450 &  0.0415  &   0.0113  & 0.0078  & 0.0035 \\  \cline{1-7}
\multicolumn{7}{|l|}{Data set {\em Letter-Two}}  \\ \cline{2-7}
RBF-SVM     &  $C=5, \quad \sigma = 20$   & 0.0743 &  0.0359  &   0.0483  & 0.0098  & 0.0384 \\  \cline{2-7}
Poly-SVM    &  $C=2, \quad  degree = 2$   & 0.0745 &  0.0391  &   0.0465  & 0.0111  & 0.0353 \\  \cline{2-7}
D-prod SVM  &  $C=0.1 $                   & 0.0908 &  0.0767  &   0.0347  & 0.0205  & 0.0142 \\  \cline{1-7}
\multicolumn{7}{|l|}{Data set {\em Letter-Two with added noise}}   \\ \cline{2-7}
RBF-SVM     &  $C=10, \quad \sigma = 100$ & 0.3362 &  0.2799  &   0.0988  & 0.0425  & 0.0563 \\  \cline{2-7}
Poly-SVM    &  $C=1, \quad  degree = 2$   & 0.3432 &  0.2799  &   0.1094  & 0.0461  & 0.0633 \\  \cline{2-7}
D-prod SVM  &  $C=0.1 $                   & 0.3410 &  0.3109  &   0.0828  & 0.0527  & 0.0301 \\  \cline{1-7}
\multicolumn{7}{|l|}{Data set {\em Spam}}   \\ \cline{2-7}
RBF-SVM     &  $C=5, \quad \sigma = 100$  & 0.1263 &  0.0987  &   0.0488  & 0.0213  & 0.0275 \\  \cline{2-7}
Poly-SVM    &  $C=2, \quad degree = 2$    & 0.1292 &  0.0969  &   0.0510  & 0.0188  & 0.0323 \\  \cline{2-7}
D-prod SVM  &  $C=0.1 $                   & 0.1306 &  0.0965  &   0.0547  & 0.0205  & 0.0341 \\  \cline{1-7}
\multicolumn{7}{|l|}{Data set {\em Musk}}  \\ \cline{2-7}
RBF-SVM     &  $C=2, \quad \sigma = 100$  & 0.0884 &  0.0800  &   0.0217  & 0.0133  & 0.0084 \\  \cline{2-7}
Poly-SVM    &  $C=2, \quad degree = 2$    & 0.1163 &  0.0785  &   0.0553  & 0.0175  & 0.0378 \\  \cline{2-7}
D-prod SVM  &  $C=0.01 $                  & 0.1229 &  0.1118  &   0.0264  & 0.0154  & 0.0110 \\  \cline{1-7}
\hline 
\end{tabular}}
%\vspace{-1cm}  
\end{center}
\caption{Compared best results with different kernels and data sets. RBF-SVM stands for SVM with Gaussian kernel; Poly-SVM for
SVM with polynomial kernel and D-prod SVM for SVM with dot product kernel. Var unb. and Var. bias. stand for
unbiased and biased variance.}
\end{table}
\normalsize
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Table \ref{tab:BVdecomp-best-results} shows the best results achieved by the SVM,
considering each kernel and each data set used in the experiments. 
Interestingly enough in $3$ data sets (Waveform, Letter-Two with added noise and Spam) 
there are not significant differences in the error between the kernels, but there are differences in bias, net-variance, unbiased or biased
variance. In the other data sets Gaussian kernels outperform polynomial  and dot product kernels, lowering bias
or net-variance or both. Considering bias and net-variance, in some cases they are lower for polynomial or
dot product kernel, showing that  different kernels learn in different ways with different data.

Considering the data set {\em P2} (Figure \ref{fig:P2-comp-kernel} a, c, e), RBF-SVMs achieve the best results, 
as bias is lower. Unbiased variance is comparable between polynomial and Gaussian kernel, while
net-variance is lower, as biased variance is higher for polynomial-SVM. In this task the bias of 
dot product SVM is very high. Also in the data set {\em Musk} (Figure \ref{fig:P2-comp-kernel} b, d, f) RBF-SVM obtains
the best results, but in this case unbiased variance is responsible for this fact, while bias is similar.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%          
\begin{figure}[htb]
\begin{center}
%\small
%\vspace{2cm}                                                                                                                                                                                                                                                                                                                   
\begin{tabular}{cc}                                                                                                                                                     
\hspace{-0cm}
\includegraphics  [width = 7.4cm] {ps/P2rbf-c.sigma1-comp.eps}         & 
\hspace{-0cm}
\includegraphics  [width = 7.4cm] {ps/MUSKrbf-c.sigma100-comp.eps}         \\  \vspace{0.6cm} 
\hspace{-0cm} (a) & \hspace{+0.0cm} (b)  \\
\hspace{-0cm}
\includegraphics  [width = 7.4cm] {ps/P2poly-c.degree5-comp.eps}                 &
\hspace{-0cm}
\includegraphics  [width = 7.4cm] {ps/MUSKpoly-c.degree2.eps}         \\  \vspace{0.6cm}
\hspace{-0cm} (c) & \hspace{+0.0cm} (d)  \\
\hspace{-0cm}
\includegraphics  [width = 7.4cm] {ps/P2dotprod.eps}         & 
\hspace{-0cm}
\includegraphics  [width = 7.4cm] {ps/MUSKdotprod-comp.eps}         \\  \vspace{0.6cm} 
\hspace{-0cm} (e) & \hspace{+0.0cm} (f)  \\
\end{tabular}
\caption{Bias-variance decomposition of the error in bias, net variance, unbiased
and biased variance with respect to $C$, considering different kernels.
(a) P2, Gaussian; (b) Musk, Gaussian (c) P2, polynomial; (d) Musk, polynomial; (e) P2, dot product; 
(f) Musk, dot product.}
\label{fig:P2-comp-kernel}
\end{center}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
With the other data sets the bias is  similar between RBF-SVM and polynomial-SVM, but for dot product SVM
often the bias is higher (Figure~\ref{fig:WAVEFORM-comp-kernel} b, d, f). Interestingly enough RBF-SVM seems to be more
sensible to the $C$ value with respect to both polynomial and dot product SVM: 
for $C < 0.1$ in some data sets the
bias is much higher (Figure \ref{fig:WAVEFORM-comp-kernel} a, c, e).
With respect to $C$ bias and unbiased variance show sometimes opposite trends, independently of the kernel: 
bias decreases, while unbiased variance increases, but this does not occur in some data sets.
We outline also that the shape of the error, bias and variance curves is similar between different kernels in all
the considered data sets: that is, well tuned SVMs having different kernels tend to show similar 
trends of the bias and variance curves with respect to the $C$ parameter.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%          
\begin{figure}[htb]
\begin{center}
%\small
%\vspace{2cm}                                                                                                                                                                                                                                                                                                                   
\begin{tabular}{cc}                                                                                                                                                     
\hspace{-0cm}
\includegraphics  [width = 7.4cm] {ps/WAVEFORMrbf-c.sigma20-comp.eps}         & 
\hspace{-0.0cm}
\includegraphics  [width = 7.4cm] {ps/LETTER-TWOrbf-c.sigma20-comp.eps}         \\  \vspace{0.6cm} 
\hspace{-0cm} (a) & \hspace{+0.0cm} (b)  \\
\hspace{-0cm}
\includegraphics  [width = 7.4cm] {ps/WAVEFORMpoly-c.degree3.eps}                &
\hspace{-0.0cm}
\includegraphics  [width = 7.4cm] {ps/LETTER-TWOpoly-c.degree2-comp.eps}         \\  \vspace{0.6cm}
\hspace{-0cm} (c) & \hspace{+0.0cm} (d)  \\
\hspace{-0cm}
\includegraphics  [width = 7.4cm] {ps/WAVEFORMdotprod-comp.eps}         & 
\hspace{-0.0cm}
\includegraphics  [width = 7.4cm] {ps/LETTER-TWOdotprod-comp.eps}         \\  \vspace{0.6cm} 
\hspace{-0cm} (e) & \hspace{+0.0cm} (f)  \\
\end{tabular}
\caption{Bias-variance decomposition of the error in bias, net variance, unbiased
and biased variance with respect to $C$, considering different kernels.
(a) Waveform, Gaussian; (b) Letter-Two, Gaussian (c) Waveform, polynomial; (d) Letter-Two, polynomial; 
(e) Waveform, dot product; (f) Letter-Two, dot product.}
\label{fig:WAVEFORM-comp-kernel}
\end{center}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\clearpage
%%%%% rev.1 comment 2 %%%%%%%%%%%%%%%%%%
\changed
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{table}[!tb]
\label{tab:BVdecomp-variation}
\begin{center}
%%\vspace{-1cm}  
\small
{\centering \begin{tabular}{|l|l|l|l|l|l|} 
\hline  
Kernel &  {\bf Avg. } & {\bf Bias} & {\bf Var. } & {\bf Var. } &  {\bf Net }\\  
type   &  {\bf Error} &            & {\bf unb. } & {\bf bias.} &  {\bf Var.}\\  
\hline   \hline 
RBF    &   $0.0901 \pm 0.0087$& $0.0805 \pm 0.0126$ &  $0.0237 \pm 0.0039$ &$0.0141 \pm 0.0025$ &$0.0096 \pm 0.0019$\\  \cline{2-6}
Poly   &   $0.1158 \pm 0.0069$& $0.0782 \pm 0.0083$ &  $0.0585 \pm 0.0071$ &$0.0109 \pm 0.0018$ &$0.0376 \pm 0.0047$\\  \cline{2-6}
D-prod &   $0.1305 \pm 0.0133$& $0.1179 \pm 0.0140$ &  $0.0285 \pm 0.0084$ &$0.0159 \pm 0.0045$ &$0.0126 \pm 0.0035$\\  \cline{1-6}
\hline 
\end{tabular}}
%\vspace{-1cm}  
\end{center}
\caption{Evaluation of the variation of the estimated values of bias variance decomposition with the {\em Musk} 
data set. RBF-SVM stands for SVM with Gaussian kernel; Poly-SVM for
SVM with polynomial kernel and D-prod SVM for SVM with dot product kernel. 
Net Var. Var unb. and Var. bias. stand for net,
unbiased and biased variance. For each value is represented the mean value over $100$ replicated experiments and the corresponding value
of the standard deviation.}
\end{table}
\normalsize
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\changedEnd
\changed  
In our experiments we used relatively small training sets (100 examples), while the number of input variables ranged from $2$ ({\em P2}
data set) to $166$ ({\em Musk} data set).
Hence, even if for each SVM model (that is for each combination of SVM parameters) we used 200 training sets 
$D_i, 1 \leq i \leq 200$ in order to train 200 different classifiers $f_{D_i}$, you could wonder whether the estimated quantities (average
error, bias, net-variance, unbiased and biased variance) could be noisy.
An extensive evaluation of the sensitivity of the estimated quantities to the sampling procedure would be very expensive.
Indeed if we replicate only 10 times our experiments on all the data sets, we should train and test more than 5 millions of different
SVMs. 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%          
\begin{figure}[!tb]
%\small
%\vspace{-0.7cm}                                                                                                                                                                                                                                                                                                                        
\begin{tabular}{cc}                                                                                                                                                     
\hspace{-0.0cm}
\includegraphics  [width = 7.4cm] {ps/LETTER-TWOrbf-c.sigma5.eps}        &
\hspace{-0.0cm}
\includegraphics  [width = 7.4cm] {ps/NOISE-LETTER-TWOrbf-c.sigma5.eps}         \\ \vspace{0.6cm}
\hspace{-0cm} (a) & \hspace{+0cm} (b)  \\  
\hspace{-0.0cm}
\includegraphics  [width = 7.4cm] {ps/LETTER-TWOpoly-c.degree3.eps}              &
\hspace{-0.0cm}
\includegraphics  [width = 7.4cm] {ps/NOISE-LETTER-TWOpoly-c.degree3.eps}         \\ \vspace{0.6cm}
\hspace{-0cm} (c) & \hspace{+0cm} (d)  \\  
\end{tabular}
\caption{Effect of noise on bias and variance. The bias-variance decomposition of the error is shown
while varying the $C$ regularization parameter with polynomial and Gaussian kernels.
(a) Letter-Two: Gaussian kernel, $\sigma = 5$, 
(b) Letter-Two with added noise: Gaussian kernel, $\sigma = 5$, 
(c) Letter-Two: polynomial kernel, degree = 3, 
(d) Letter-Two with added noise: polynomial kernel, degree = 3.}
\label{fig:noisy}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Anyway, in order to get insights about this problem, we performed $100$ replicates of our experiments limited only to the 
{\em Musk} data set (that is the data set with the largest dimensionality in our experiments), for a subset of the parameters near the
optimal ones. We found that the standard deviation of the estimated values is not too large. For instance, considering the best model for
Gaussian, polynomial and dot product kernels we obtained the values shown in Table~\ref{tab:BVdecomp-variation}. It seems that the
computed quantities are not too noisy, even if we need more experiments to confirm this result.
\changedEnd

\changed
%%%%%%%%% rev.1 comment 1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Bias-Variance Decomposition with Noisy Data}
\label{sub:BV-noisy-data}
While the estimation of the noise is quite straightforward with synthetic data, it is a difficult task with ``real'' data~\cite{James03}.
For these reasons, and in order to simplify the computation and the overall analysis, 
in our experiments we did not explicitly consider noise. 

Anyway, noise can play a significant role in the bias-variance analysis.
Indeed, according to Domingos, with the $0/1$ loss the noise is linearly added to the error with a coefficient equal to 
$2 P_D(f_D(\vt{x}) = y_*) - 1$  (Equation~\ref{eq:DomingosBV}).
Hence, if the classifier is accurate, that is if \mbox{$P_D(f_D(\vt{x}) = y_*) \gg 0.5$}, then the noise $N(\vt{x})$, if present,
influences the expected loss.
In the opposite situation also, with very bad classifiers, that is when \mbox{$P_D(f_D(\vt{x}) = y_*) \ll 0.5$}, 
the noise influences the overall error in the opposite sense: it reduces the expected loss. 
If \mbox{$P_D(f_D(\vt{x}) = y_*) \approx 0.5$}, that is if the classifier performs a sort of random guessing, then 
\mbox{$2 P_D(f_D(\vt{x}) = y_*) - 1 \approx 0$} and the noise has no substantial impact on the error.

Hence if we know that the noise is small we can disregard it, but what about the effect of noise when it is present but not explicitly
considered in the bias-variance decomposition of the error?
The analysis of the results in the data set Letter-Two without and with $20$ \% added noise shows that the main effect of noise 
in this specific situation consists in incrementing the bias and consequently the average error.
Indeed, with Gaussian kernels (Figure \ref{fig:noisy} (a) and (b)) the bias
is raised to about 0.3, with an increment of about 0.25 with respect to the data set without noise, while the
net-variance is incremented only by about 0.02, as the increment of the unbiased variance is counter-balanced by
the increment of the biased variance.
A similar behavior is registered also with polynomial (Figure \ref{fig:noisy} (c) and (d)) and dot product kernels
(Figure \ref{fig:dot-prod-all} (c) and (d)).
\changedEnd


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Characterization of Bias-Variance Decomposition of the Error}
\label{sec:characterization}
Despite the differences observed in different data sets, common patterns of bias and variance can be detected for each of
the kernels considered in this study. Each kernel presents a specific characterization of bias and variance with respect to
its specific parameters, as explained in the following sections.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Gaussian Kernels}
\label{subsec:char-gaussian}

Error, bias, net-variance, unbiased and biased variance show a common
trend in the 7 data sets we used in the experiments. Some
differences, of course, arise in the different data sets, but we can
distinguish three different regions in the error analysis of {\em
RBF-SVM}, with respect to increasing values of $\sigma$
(Figure \ref{fig:3RBF-region}):
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
\begin{figure}[!tb] 
\begin{center}
%\hspace{-2cm}
\includegraphics  [width = 14cm] {ps/3RBF-region-GREY-LANDSATrbf.C100-trans.eps}        \\  %\vspace{0.6cm}      
\vspace*{4pt}
\caption{The 3 regions of the error in RBF-SVM with respect to $\sigma$.}
\label{fig:3RBF-region} 
\end{center}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{enumerate}
        \item {\bf High bias region}. 
        For low values of $\sigma$, error is high: it depends on high
        bias.  Net-variance is about $0$ as biased and unbiased
        variance are equivalent. In this region there are no
        remarkable fluctuations of bias and variance: both remain
        constant, with high values of bias and comparable values of
        unbiased and biased variance, leading to net-variance values
        near to $0$.  In some cases biased and unbiased variance are
        about equal, but different from $0$, in other cases they are
        equal, but near to $0$.

        \item {\bf Transition region}. 
        Suddenly, for a critical value of $\sigma$, the bias decreases
        rapidly. This critical value depends also on $C$: for
        very low values of $C$, we have no learning, then for higher
        values the bias drops.  Higher values of $C$ cause the
        critical value of $\sigma$ to decrease
        (Figure~\ref{fig:GREY-LANDSATrbf-3D} (b) and
        \ref{fig:rbf-sigma}).  In this region the increase in
        net-variance is lower than the decrease in bias: so the
        average error decreases.
        The boundary of this region can be determined at the point where the error stops decrementing. 
        This region is characterized also by a particular trend of the net-variance. We can distinguish two main
        behaviors:
        \begin{enumerate}
          \item {\bf Wave-shaped net-variance}. Net-variance first increases and then decreases, producing a
                wave-shaped curve with respect to $\sigma$. The initial increment of the net-variance is due to the
                simultaneous increment of the unbiased variance and decrement of the biased variance.           
                In the second part of the transition region, biased variance stabilizes and unbiased variance
                decreases, producing a parallel decrement of the net-variance.
                The rapid decrement of the error with $\sigma$ is due  to the rapid decrement of the bias, after which the
                bias stabilizes and the further decrement of the error with $\sigma$ is determined by the net-variance 
                reduction (Figure~\ref{fig:GREY-LANDSATrbf-3D}c, \ref{fig:rbf-sigma}).
                \item {\bf Semi-wave-shaped net-variance}. In other cases the net-variance curve with $\sigma$ is not so
                clearly wave-shaped: the descending part is very reduced (Figure~\ref{fig:rbf-sigma} e, f).
                In particular in the musk data set we have a continuous increment of the net-variance (due to the 
                continuous growing of the unbiased variance with $\sigma$), and no wave-shaped curve is observed 
                (at least for $C > 10$, Figure \ref{fig:P2rbf-large-sigma} d).
        \end{enumerate}
        In both cases the increment of net-variance is  slower than the increment in bias: as a result,
   the average error decreases. 

        \item {\bf Stabilized region}.
        This region is characterized by small or no variations in bias
        and net-variance. For high values of $\sigma$ both bias and
        net-variance stabilize and the average error is constant
        (Figure ~\ref{fig:GREY-LANDSATrbf-3D}, \ref{fig:rbf-sigma}). 
        In other data sets the error increases with $\sigma$, because of the increment of the
        bias (Figure~\ref{fig:P2rbf-large-sigma} a,b) or the unbiased variance (Figure~\ref{fig:P2rbf-large-sigma} c,d).
\end{enumerate}

In the first region, bias rules SVM behavior: in most cases the bias
is constant and close to $0.5$, showing that we have a sort of random
guessing, without effective learning.  It appears that the area of
influence of each support vector is too small (Figure~\ref{fig:function0.01}), and the learning
machine overfits the data.  This is confirmed by the fact that in this
region the training error is about $0$ and almost all the training
points are support vectors.

In the transition region, the SVM starts to learn, adapting itself to
the data characteristics.  Bias rapidly goes down (at the expenses of
a growing net-variance), but for higher values of $\sigma$ (in the
second part of the transition region), sometimes net-variance also
goes down, working to lower the error (Figure~\ref{fig:rbf-sigma}).

Even if the third region is characterized by no variations in bias and variance, 
sometimes  for low values of $C$, the error increases with
$\sigma$ (Figure~\ref{fig:GREY-LANDSATrbf-large-sigma} a, \ref{fig:LETTERrbf-sigma-train-test1} a), 
as a result of the bias increment; on the
whole RBF-SVMs are sensitive to low values of $C$: if $C$ is too low,
then bias can grow quickly.  High values of $C$ lower the bias(Figure~\ref{fig:LETTERrbf-sigma-train-test1} c, d).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Polynomial and Dot Product Kernels}
\label{subsec:char-poly-dotprod}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%          
\begin{figure}[!tb]
\begin{center}
%%\small
%\vspace{-0.7cm}                                                                                                                                                                                                                                                                                                                                                                                                                                                        
\hspace{-0.0cm}
\includegraphics  [width = 14cm]{ps/trend-LETTER-TWOpoly.C0.1.eps}     \\
\caption{Behaviour of polynomial SVM with respect of the bias-variance decomposition of the error.}
\label{fig:poly-trend}
\end{center}    
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
For polynomial and dot product SVMs, we have also characterized the
behavior of  SVMs in terms of average error, bias, net-variance,
unbiased and biased variance, 
even if we are not able to distinguish between  different regions clearly defined. 

However,  common patterns of the error curves with respect to the polynomial degree, considering bias, net-variance and 
unbiased and biased variance can be noticed.

The average loss curve shows in general a U shape with respect to the polynomial
degree, and this shape may depend  on both bias and unbiased variance or in some cases mostly on the
unbiased variance according to the characteristics of the data
set.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
\begin{figure}[!tb]
\begin{center}          
%%\small                                                                                                                                                        
\hspace{-0cm}
\includegraphics  [width = 14cm] {ps/trend-SPAMdotprod.eps}              
\caption{Behaviour of the dot product SVM with respect of the bias-variance decomposition of the error.}
\label{fig:dprod-trend}
\end{center}    
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
From these general observations we can schematically distinguish two main global pictures
of the behaviour of polynomial SVM with respect to the bias-variance decomposition of the error:
\begin{enumerate}
\item {\bf Error curve shape bias-variance dependent}. \\
In this case the shape of the error curve is dependent both on the unbiased variance and the bias.
The trend of bias and net-variance can be symmetric or they can also have non coincident paraboloid shape,
depending on C parameter values (Figure~\ref{fig:WAVEFORMpoly-degree-rid} c, d and \ref{fig:P2poly-3D-rid}). 
Note that bias and net variance show often opposite trends 
(Figure~\ref{fig:P2poly-3D-rid}).
\item {\bf Error curve shape unbiased variance dependent}.\\
In this case the shape of the error curve is mainly dependent on the unbiased variance. 
The bias (and the biased variance) tend to be degree independent, especially for high values of $C$
(Figure~\ref{fig:WAVEFORMpoly-degree-rid} a, b) .
\end{enumerate} 
Figure \ref{fig:poly-trend} schematically summarizes  the main characteristics of the bias-variance
decomposition of error in polynomial SVM.
Note however that the error curve depends for the most part on both variance and bias: the prevalence of the unbiased
variance (Figure~\ref{fig:WAVEFORMpoly-degree-rid} a, b) or the bias seems to depend mostly 
on the distribution of the data. 

The increment of the values of $C$ tends to flatten the U shape of the error curve: in particular
for large $C$ values  bias  becomes independent with respect to the degree
(Figure~\ref{fig:WAVEFORMpoly-3D-rid}). Moreover the  $C$ parameter plays also a regularization role
(Figure~\ref{fig:P2SPAMpoly-c-rid}) 


%%%%%%%%%%%%%% DOT PRODUCT %%%%%%%%%%%%%%%
Dot product SVM are characterized by opposite trends of bias and net-variance: bias decrements, 
while net-variance grows with respect to C; then, for higher values of C both stabilize.
The combined effect of these symmetric curves produces a minimum of the error for low values of C, as
the initial decrement of bias with C is larger than the initial increment of net-variance.
Then the error slightly increases and stabilizes with C (Figure \ref{fig:dot-prod-all}).
The shape of the net-variance curve is determined mainly by the unbiased variance: it increases and then
stabilizes with respect to C. On the other hand the biased variance curve is flat, remaining small for all
values of C. A schematic picture of this behaviour is given in Figure \ref{fig:dprod-trend}.




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Two Directions for Developing Ensembles of SVMs}
\label{sec:directions}
In addition to providing insights into the behavior of SVMs, the
analysis of the bias-variance decomposition of the error can identify
the situations in which ensemble methods might improve SVM
performance. 

\changed
On several real-world problems, SVM ensembles are reported to give improvements over single SVMs~\citep{Kim02,Val03a},
but few works showed also negative experimental results about ensembles of SVMs~\citep{Buciu01,Evg00}.
In particular~\citet{Evg00} experimentally found that leave-one-out error bounds for kernel machines ensembles are tighter that the
equivalent ones for single machines, but they showed that with accurate parameters tuning single SVMs and ensembles of SVMs perform
similarly.

In this section we propose to exploit bias-variance analysis in order to develop ensemble methods well tuned to the bias-variance
characteristics of the base learners. 
In particular we present two possible ways of applying bias-variance
analysis to develop SVM-based ensemble methods.
\changedEnd

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Bagged Ensemble of Selected Low-Bias SVMs}
\label{subsec:bag-low-SVM}
\changed
From a general standpoint, considering different kernels and different parameters of the kernel, we can
observe that the minimum of the error, bias and net-variance (and in particular unbiased variance) do not
match. For instance, considering RBF-SVM we see that we achieve the minimum of the error, bias and 
net-variance for different values of $\sigma$ (see, for instance, Figure \ref{fig:rbf-sigma}).
Similar considerations can also be applied to polynomial and dot product SVM.
Often, modifying parameters of the kernel, if we gain in bias we lose in variance and vice versa, even if
this is not a rule.
\changedEnd

Under the bootstrap assumption, bagging reduces only variance. From bias-variance decomposition we know
that unbiased variance reduces the error, while biased variance increases the error. 
Hence bagging should be applied to low-biased classifiers, because the biased variance will be small.

Summarizing, we can schematically consider the following observations:
\begin{itemize}
\item We know that bagging lowers net-variance (in particular
unbiased variance) but not bias~\citep{Bre96b}. 

\item SVMs are strong, low-biased learners, but this property depends on
the proper selection of the kernel and its parameters. 

\item If we can identify low-biased base learners with a relatively
high unbiased variance, bagging can lower the error.

\item Bias-variance analysis can identify SVMs with low bias.
\end{itemize}

Hence a basic high-level algorithm for a general {\em Bagged ensemble
of selected low-bias SVMs} is the following: 
\begin{enumerate}
\item Estimate bias-variance decomposition of the error for different SVM models
\item Select the SVM model with the lowest bias 
\item Perform bagging using as base learner the SVM with the estimated lowest bias.
\end{enumerate}

%(a) select the SVM model with the lowest bias using bias-variance decomposition of the error;
%(b) perform bagging using as base learner the SVM with the estimated lowest bias.  

This approach combines the low bias properties of SVMs
with the low unbiased variance properties of bagging and should
produce ensembles with low overall error. 
\changed
We named this approach {\em Lobag}, that stands for {\em Lo\/}w bias {\em bag\/}ging.
Using SVMs as base learners, 
\changedEnd
depending on the type of
kernel and parameters considered, and on the way the bias is estimated
for the different SVM models, different algorithmic variants can be provided:
%%% NEW PART INSERTED %%%%%%%%%%%%%%%%%
For instance, depending on the type of kernel and parameters considered, 
different implementations can be given:
\begin{enumerate}
\item Selecting the RBF-SVM with the lowest bias with respect to the $C$ and $\sigma$ parameters.
\item Selecting the polynomial-SVM with the lowest bias with respect to the $C$ and degree parameters.
\item Selecting the dot-prod-SVM with the lowest bias with respect to the $C$  parameter.
\item Selecting the SVM with the lowest bias with respect to the kernel.
\end{enumerate}

Another issue is how to implement the estimation of the bias-variance decomposition of the error for different SVM models.
We could use cross-validation in conjunction with bootstrap replicates, or out-of-bag estimates (especially if we have
small training sets), or hold-out techniques in conjunction with bootstrap replicates if we have sufficiently
large training sets.

\changed
A first implementation of this approach, using an out-of-bag estimate of the bias-variance decomposition of the error, has been
proposed, and quite encouraging results have been achieved~\citep{Val03b}.
\changedEnd

Another problem is the estimate of the noise in real data sets. A straightforward approach simply consists in disregarding
it, but in this way we could overestimate the bias (see Section~\ref{sub:BV-noisy-data}). 
Some heuristics are proposed in~\cite{James03}, but the problem remains substantially unresolved.

\changed
It is worth noting that this approach can be viewed as an alternative way for tuning SVM parameters, using an ensemble instead of a
single SVM.
From this standpoint recent works proposed to automatically choose multiple kernel parameters \citep{Chap02,Grand02}, 
setting, for instance different $\sigma$ values for each input dimension in Gaussian kernels, by applying a minimax procedure to
iteratively maximize the margin of the SVM and to minimize an estimate of the generalization error over the set of kernel parameters
\citep{Chap02}.
This promising approach could be in principle extended to minimize the bias, instead of the overall error.
To this purpose we need to solve non trivial problems such as providing an upper bound for the bias and the variance, or at least an
easy to compute their estimator having, if possible, an analytical expression.
This approach could represent a new interesting research line that could improve the performances and/or reduce the computational
burden of the Lobag method.
\changedEnd





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Heterogeneous Ensembles of  SVM}
\label{subsec:het-SVM}

The analysis of bias-variance decomposition of error in SVM shows
that the minimum of the overall error, bias, net-variance, unbiased
and biased variance occur often in different SVM models.  These
different behaviors of different SVM models could be in principle
exploited to produce diversity in ensembles of SVMs.  Although the
diversity of base learner itself does not assure the error of the
ensemble will be reduced \citep{Kun01a}, the combination of accuracy
and diversity in most cases does~\citep{Die00a}.  As a consequence, we
could select different SVM models as base learners by evaluating their
accuracy and diversity through the bias-variance decomposition of the
error. 

Our results show that the ``optimal region'' (low average loss region) is
quite large in RBF-SVMs (Figure~\ref{fig:GREY-LANDSATrbf-3D}).
This means that $C$ and $\sigma$ do not need
to be tuned extremely carefully.  From this point of view, we can
avoid time-consuming model selection by combining RBF-SVMs trained
with different $\sigma$ values all chosen from within the ``optimal
region.''  For instance, if we know that the error curve looks like
the one depicted in Figure~\ref{fig:3RBF-region}, we could try to fit a
sigmoid-like curve using only few values to estimate where the
stabilized region is located.  Then we could train an heterogeneous
ensemble of SVMs with different $\sigma$ parameters (located in the low
bias region) and average them according to their estimated
accuracy.  

A high-level algorithm for {\em Heterogeneous Ensembles of  SVMs} could
include the following steps:
\begin{enumerate}
\item Individuate the ``optimal region'' through bias-variance analysis of the error
\item Select the SVMs with parameters chosen from within the optimal region defined by bias-variance analysis.
\item Combine the selected SVMs by majority or weighted voting according to their estimated accuracy.
\end{enumerate}
We could use different methods or heuristics to find the ``optimal region'' (see Section~\ref{subsubsec:BV-relationships})
and we have to define also the criterion used to select the SVM models inside the ``optimal region'' (for
instance, improvement of the diversity).
The combination could be performed using also other approaches, such as 
minimum, maximum, average and OWA aggregating operators~\citep{Kit98b} or
Behavior-Knowledge space method~\citep{Hua95},
Fuzzy aggregation rules~\citep{Wang98}, Decision templates~\citep{Kun01}
or Meta-learning techniques~\citep{Prod99}. 
Bagging and boosting~\citep{Fre96} methods can also be combined with this
approach to further improve diversity and accuracy of the base
learners.

\changed
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Numerical Experiments with Low Bias Bagged SVMs}
\label{sec:lobag-exp}
In order to show that these research directions could be fruitful to follow further, we performed  numerical experiments 
on different data sets to test the Lobag ensemble method using SVMs as base learners.  
We compared the results with single SVMs and classical bagged SVM ensembles.
We report here some preliminary results.More detailed results are reported in~\citet{Val03b}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{table}[!htb]
\label{tab:comp-mcnemar}  
\begin{center}
%%\vspace{-1cm}  
\small  
{ \begin{tabular}{|l|l|l|l|l|l|l|} 
\hline  
$\mathbf{Kernel}$  & $\mathbf{E_{lobag}}$ & $\mathbf{E_{bag}}$ & $\mathbf{E_{single}}$  &   \multicolumn{3}{c|}{\bf Confidence level}  \\ \cline{5-7}  
$\mathbf{type}$    &                           &                          &                         & $\mathbf{L / B}$  &  $\mathbf{L / S}$  &  $\mathbf{B / S}$\\ 
\hline   \hline 
\multicolumn{1}{|l} {} &    \multicolumn{6}{l|}{Data set {\em P2}}  \\ \cline{2-7}
Polyn.   &  0.1735 &  0.2008  & 0.2097  &  0.001 & 0.001 & 0.001 \\  \cline{2-7}
Gauss.     &  0.1375 &  0.1530  & 0.1703  &  0.001 & 0.001 & 0.001 \\  \cline{1-7}
\multicolumn{1}{|l} {}   &    \multicolumn{6}{l|}{Data set {\em Waveform}}  \\ \cline{2-7}
Linear       &  0.0740 &  0.0726  & 0.0939  &  1     & 0.001 & 0.001  \\  \cline{2-7}
Polyn.   &  0.0693 &  0.0707  & 0.0724  &  1     & 0.1   & 0.1     \\  \cline{2-7}
Gauss.     &  0.0601 &  0.0652  & 0.0692  &  0.001 & 0.001 & 0.001   \\  \cline{1-7}
\multicolumn{1}{|l} {}   &    \multicolumn{6}{l|}{Data set {\em Grey-Landsat}}  \\ \cline{2-7}
Linear       &  0.0540 &  0.0540  & 0.0650  &  1     & 0.001 & 0.001    \\  \cline{2-7}
Polyn.   &  0.0400 &  0.0440  & 0.0480  &  1     & 0.1   & 1        \\  \cline{2-7}
Gauss.     &  0.0435 &  0.0470  & 0.0475  &  0.1   & 0.1   & 1        \\  \cline{1-7}
\multicolumn{1}{|l} {}   &    \multicolumn{6}{l|}{Data set {\em Letter-Two}}  \\ \cline{2-7}
Linear       &  0.0881 &  0.0929  & 0.1011  &  1     & 0.025 & 0.05  \\  \cline{2-7}
Polyn.   &  0.0701 &  0.0717  & 0.0831  &  1     & 0.05  & 0.1   \\  \cline{2-7}
Gauss.     &  0.0668 &  0.0717  & 0.0799  &  1     & 1     & 1     \\  \cline{1-7}
\multicolumn{1}{|l} {}   &    \multicolumn{6}{l|}{Data set {\em Letter-Two with added noise}}  \\ \cline{2-7}
Linear       &  0.3535 &  0.3518  & 0.3747  &  1     & 1     & 0.1   \\  \cline{2-7}
Polyn.   &  0.3404 &  0.3715  & 0.3993  &  1     & 0.05  & 0.1    \\  \cline{2-7}
Gauss.     &  0.3338 &  0.3764  & 0.3829  &  0.05  & 0.025 & 1     \\  \cline{1-7}
\multicolumn{1}{|l} {}   &    \multicolumn{6}{l|}{Data set {\em Spam}}  \\ \cline{2-7}
Linear       &  0.1408 &  0.1352  & 0.1760  &  0.05  & 0.001 & 0.001 \\  \cline{2-7}
Polyn.   &  0.0960 &  0.1034  & 0.1069  &  0.1   & 0.025 & 1     \\  \cline{2-7}
Gauss.     &  0.1130 &  0.1256  & 0.1282  &  0.005 & 0.001 & 1     \\  \cline{1-7}
\multicolumn{1}{|l} {}   &    \multicolumn{6}{l|}{Data set {\em Musk}}  \\ \cline{2-7}
Linear       &  0.1291 &  0.1291  & 0.1458  &  1     & 0.001 & 0.001  \\  \cline{2-7}
Polyn.   &  0.1018 &  0.1157  & 0.1154  &  0.001 & 0.001 & 1      \\  \cline{2-7}
Gauss.     &  0.0985 &  0.1036  & 0.0936  &  0.05  & 1     & 0.05   \\  \cline{1-7}
\hline 
\hline 
\end{tabular}}
%\vspace{-1cm}  
\end{center}
\caption{Results of the experiments using pairs of train $\mathcal{D}$ and test $\mathcal{T}$ sets. 
$E_{lobag}$, $E_{bag}$ and $E_{SVM}$ stand respectively for estimated error of lobag, 
bagged and single SVMs on the  test set $\mathcal{T}$. The three last columns show the confidence level according to the Mc Nemar test.
$\mathbf{L / B}$, $\mathbf{L / S}$  and  $\mathbf{B / S}$ stand respectively for the comparison Lobag/Bagging, Lobag/Single SVM and
Bagging/Single SVM. If the confidence level is equal to 1, no significant difference is registered.}
\end{table}
\normalsize
%\vspace{-2cm}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%% Exp. setup %%%%%%%%%%%%%%
We employed the $7$ different two-class data sets described in Section~\ref{subsec:expsetup},
using small $\mathcal{D}$ training sets and large test $\mathcal{T}$ sets in order
to obtain a reliable estimate of the generalization error: the number of examples for
$\mathcal{D}$ was set to $100$, while the size of $\mathcal{T}$ ranged from a few thousands
for the ``real'' data sets to ten thousands for synthetic data sets.  Then we applied
the Lobag algorithm  setting the number of samples
bootstrapped from $\mathcal{D}$ to $100$, and performing an out-of-bag estimate of the
bias-variance decomposition of the error.  The selected lobag, bagged and single SVMs
were finally tested on the separated test set $\mathcal{T}$.

%%%%%%%%%%%%% Results %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Table~\ref{tab:comp-mcnemar} shows the results of the experiments.
We measured 20 outcomes
for each method: 7 data sets, and 3 kernels (Gaussian, polynomial, and dot product)
applied to each data set except P2 for which we did not apply the dot product kernel
(because it was obviously inappropriate).  For each pair of methods, we applied the McNemar
test~\citep{Die98} to determine whether there was a significant difference in
predictive accuracy on the test set.

On nearly all the data sets, both bagging and Lobag outperform the single SVMs
independently of the kernel used.  The null hypothesis that Lobag has the same error rate
as a single SVM is rejected at or below the 0.1 significance level in 17 of the 20 cases,
while the null hypothesis that bagging has the same error rate as a single SVM is
rejected at or below the 0.1 level in 13 of the 20 cases.  
Most importantly, Lobag generally outperforms standard bagging.  Lobag is statistically
significantly better than bagging in 9 of the 20 cases, and significantly inferior only
once.  

These preliminary results show the feasibility of our approach, as shown also by similar
experiments presented in~\cite{Val03b}, but we need more experimental studies and applications to real
problems in order to better understand when and in which conditions this approach could be fruitful.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\changedEnd



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Conclusion and Future Works}
\label{sec:conclusion}
We applied bias-variance decomposition of the error as a tool to gain insights into SVM learning algorithm.
In particular we performed an analysis of  bias and variance of SVMs, considering
Gaussian, polynomial, and dot product kernels.  
The relationships between parameters of the kernel and bias, net-variance, unbiased and 
biased variance have been studied through an extensive  experimentation involving training, testing, and bias-variance
analysis of more than half million of SVMs.

We discovered regular
patterns in the behavior of the bias and variance, and we related
those patterns to the parameters and kernel functions of the SVMs.
The characterization of bias-variance decomposition of the error showed that in Gaussian kernels we can individuate at least
three different regions with respect to the $\sigma$ parameter, while in polynomial kernels the U shape of the error can be
determined by the combined effects of bias and unbiased variance.
The analysis revealed also that the expected trade-off between bias and variance holds systematically for dot product
kernels, while other kernels showed more complex relationships.

The information supplied by bias-variance analysis suggests two
promising approaches for designing ensembles of SVMs.  One approach is
to employ low-bias SVMs as base learners in a bagged ensemble.  The
other approach is to apply bias-variance analysis to construct a
heterogeneous, diverse set of accurate and low-bias classifiers.
We are designing and experimenting with both of these approaches.    
                
An outgoing development of this work  extends this analysis to bagged and  boosted ensemble of SVMs, 
in order to achieve more insights about the behavior of SVM ensembles based on resampling methods.

\changed
In our experiments we did not explicitly consider the noise: analyzing the role of the noise in the decomposition of the error 
(Section~\ref{sub:BV-noisy-data}) could help to develop ensemble methods specifically designed for noisy data.
\changedEnd

Moreover in our experiments we did not explicitly consider the characteristics of the data.
Nonetheless, such as we could expect and as our experiments suggested, different data characteristics 
influence bias-variance patterns in learning machines.
To this purpose we plan to explicitly analyze the relationships between bias-variance decomposition of the
error and data characteristics, using data complexity measures based on geometrical and topological
characteristics of the data~\citep{Li93,Ho02a}.

\acks{
We thanks the anonymous reviewers for their comments and suggestions.}

\appendix
\section{}
\label{app:bias-var-effects}
In this appendix we discuss the notions of systematic and variance effect introduced by~\citet{James03}, showing that these quantities
are reduced respectively to the bias and the net-variance when the $0/1$ loss is used and the noise is disregarded.

\citet{James03} provides definitions of bias and variance that are similar to those provided by~\citet{Dom00b}.
Indeed bias and variance definitions are based on quantities that he named the systematic part $sy$ of the prediction $y$  
and  the systematic part $st$ of the target $t$. These correspond respectively to the Domingos main prediction 
(Equation\ref{eq:mainprediction}) and optimal prediction (Equation\ref{eq:optimalprediction}).
Moreover James distinguishes between bias and variance and {\em systematic} and {\em variance effects}.
Bias and variance satisfy respectively the notion of the difference between the systematic parts of $y$ and $t$, and
the variability of the estimate $y$.
Systematic effect $SE$ represents the change in error of predicting $t$ when using $sy$ instead of $st$ and the
variance effect $VE$ the change in prediction error when using $y$ instead of $sy$ in order to predict $t$.
Using Domingos' notation ($y_m$ for $sy$, and $y_*$ for $st$) the variance effect is
\begin{displaymath}
VE(y,t) = E_{y,t}[L(y,t)] - E_t[L(t,y_m)],
%\label{eq:variance-effect}
\end{displaymath} 
while the systematic effect corresponds to
\begin{displaymath}
SE(y,t) = E_{t}[L(t,y_m)] - E_t[L(t,y_*)].
%\label{eq:systematic-effect}
\end{displaymath} 
In other words the systematic effect represents the change in prediction error caused by bias, while the variance
effect the change in prediction error caused by variance.

While for the squared loss the two sets of bias-variance definitions match, for general loss functions the
identity does not hold.
In  particular for the 0/1 loss James proposes the following definitions for noise, variance and bias with 0/1
loss:
\begin{eqnarray}
N(\vt{x}) & = & P(t \neq y_*), \nonumber \\ 
V(\vt{x}) & = & P(y \neq y_m), \nonumber \\ 
B(\vt{x}) & = & I(y_* \neq y_m),
\label{eq:averagenet-variance}
\end{eqnarray} 
where $I(z)$  is 1 if $z$ is true and 0 otherwise.

The variance effect for the 0/1 loss can be expressed as
\begin{eqnarray}
VE(y,t) = E_{y,t}[L(y,t) - L(t,y_m)] & =  & P_{y,t} (y \neq t) - P_t (t \neq y_m) =  \nonumber \\ 
= 1 - P_{y,t} (y = t) - ( 1 - P_t (t = y_m)) & = & P_t (t = y_m) - P_{y,t} (y = t),
\label{eq:variance-effect-01}
\end{eqnarray} 
while the systematic effect is
\begin{eqnarray}
SE(y,t) = E_{t}[L(t,y_m)] - E_t[L(t,y_*)] & =  & P_{t} (t \neq y_m) - P_t (t \neq y_*) = \nonumber \\ 
= 1 - P_{t} (t = y_m) - ( 1 - P_t (t = y_*)) & =  & P_t (t = y_*) - P_{t} (t = y_m).
\label{eq:systematic-effect-01}
\end{eqnarray} 
If we let $N(\vt{x}) = 0$, considering Equation~\ref{eq:DomingosBV-no-noise}, \ref{eq:averagenet-variance} and Equation~\ref{eq:variance-effect-01} the variance effect 
becomes
\begin{eqnarray}
VE(y,t) = P_t(t = y_m) - P_{y,t} (y = t) & = & P(y_* = y_m) - P_y (y = y_*) = \nonumber \\
= 1 - P(y_* \neq y_m) - (1 - P_y (y \neq y_*)) & = & 1 - B(\vt{x}) - (1 - EL(\mathcal{L}, \vt{x})) = \nonumber \\
EL(\mathcal{L}, \vt{x}) - B(\vt{x}) = V_n(\vt{x}), & &
\label{eq:VEequalVn}
\end{eqnarray}
while from Equation~\ref{eq:averagenet-variance} and Equation~\ref{eq:systematic-effect-01} the systematic effect becomes
\begin{eqnarray}
SE(y,t) = P_t (t = y_*) - P_{t} (t = y_m) & = &  1 - P_t (t \neq y_*) - (1 - P_{t} (t \neq y_m)) =  \nonumber \\
P (y* \neq y_m) = I(y* \neq y_m) = B(\vt{x}). 
 & &
\label{eq:SEequalBias}
\end{eqnarray}
Hence if $N(\vt{x}) = 0$, it follows that the variance effect is equal to the net-variance (Equation~\ref{eq:VEequalVn}),
and the systematic effect is equal to the bias (Equation~\ref{eq:SEequalBias}).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\changedEnd


%\bibliographystyle{natbib}
%\bibliography{../../../BIBLIO/biblio}
\begin{thebibliography}{47}
\expandafter\ifx\csname natexlab\endcsname\relax\def\natexlab#1{#1}\fi
\expandafter\ifx\csname url\endcsname\relax
  \def\url#1{{\tt #1}}\fi

\bibitem[Allwein et~al.(2000)Allwein, Schapire, and Singer]{All00}
E. L. Allwein, R. E. Schapire, and Y.~Singer.
\newblock Reducing multiclass to binary: a unifying approach for margin
  classifiers.
\newblock {\em Journal of Machine Learning Research}, 1:\penalty0 113--141,
  2000.

\bibitem[Bauer and Kohavi(1999)]{Bau99}
E.~Bauer and R.~Kohavi.
\newblock An empirical comparison of voting classification algorithms:
  {B}agging, boosting and variants.
\newblock {\em Machine Learning}, 36\penalty0 (1/2):\penalty0 525--536, 1999.

\bibitem[Bousquet and Elisseeff(2002)]{Bou02}
O.~Bousquet and A.~Elisseeff.
\newblock Stability and {G}eneralization.
\newblock {\em Journal of Machine Learning Research}, 2:\penalty0 499--526,
  2002.

\bibitem[Breiman(1996{\natexlab{a}})]{Bre96}
L.~Breiman.
\newblock Bagging predictors.
\newblock {\em Machine Learning}, 24\penalty0 (2):\penalty0 123--140,
  1996{\natexlab{a}}.

\bibitem[Breiman(1996{\natexlab{b}})]{Bre96b}
L.~Breiman.
\newblock Bias, variance and arcing classifiers.
\newblock Technical Report TR 460, Statistics Department, University of
  California, Berkeley, CA, 1996{\natexlab{b}}.

\bibitem[Breiman(2001)]{Bre01a}
L.~Breiman.
\newblock Random {F}orests.
\newblock {\em Machine Learning}, 45\penalty0 (1):\penalty0 5--32, 2001.

\bibitem[Buciu et~al.(2001)Buciu, Kotropoulos, and Pitas]{Buciu01}
I.~Buciu, C.~Kotropoulos, and I.~Pitas.
\newblock Combining {S}upport {V}ector {M}achines for {A}ccurate {F}ace
  {D}etection.
\newblock In {\em Proc. of ICIP'01}, volume~1, pages 1054--1057, 2001.

\bibitem[Chapelle et~al.(2002)Chapelle, Vapnik, Bousquet, and
  Mukherjee]{Chap02}
O. Chapelle, V. Vapnik, O. Bousquet, and S. Mukherjee.
\newblock Choosing multiple parameters for support vector machines.
\newblock {\em Machine Learning}, 46\penalty0 (1):\penalty0 131--159, 2002.

\bibitem[Cohen and Intrator(2001)]{Cohen01}
S.~Cohen and N.~Intrator.
\newblock {A}utomatic {M}odel {S}election in a {H}ybrid {P}erceptron/{R}adial
  {N}etwork.
\newblock In {\em Multiple Classifier Systems. Second International Workshop,
  MCS 2001, Cambridge, UK}, volume 2096 of {\em Lecture Notes in Computer
  Science}, pages 349--358. Springer-Verlag, 2001.

\bibitem[Dietterich(1998)]{Die98}
T. G. Dietterich.
\newblock Approximate statistical test for comparing supervised classification
  learning algorithms.
\newblock {\em Neural Computation}, \penalty0 (7):\penalty0 1895--1924, 1998.

\bibitem[Dietterich(2000{\natexlab{a}})]{Die00a}
T. G. Dietterich.
\newblock Ensemble methods in machine learning.
\newblock In J.~Kittler and F.~Roli, editors, {\em Multiple Classifier Systems.
  First International Workshop, MCS 2000, Cagliari, Italy}, volume 1857 of {\em
  Lecture Notes in Computer Science}, pages 1--15. Springer-Verlag,
  2000{\natexlab{a}}.

\bibitem[Dietterich(2000{\natexlab{b}})]{Die00b}
T. G. Dietterich.
\newblock An experimental comparison of three methods for constructing
  ensembles of decision trees: Bagging, boosting and randomization.
\newblock {\em Machine Learning}, 40\penalty0 (2):\penalty0 139--158,
  2000{\natexlab{b}}.

\bibitem[Dietterich and Bakiri(1995)]{Die95}
T. G. Dietterich and G.~Bakiri.
\newblock Solving multiclass learning problems via error-correcting output
  codes.
\newblock {\em Journal of Artificial Intelligence Research}, \penalty0
  (2):\penalty0 263--286, 1995.

\bibitem[Domingos(2000{\natexlab{a}})]{Dom00a}
P.~Domingos.
\newblock A unified bias-variance decomposition.
\newblock Technical report, Department of Computer Science and Engineering,
  University of Washington, Seattle, WA, 2000{\natexlab{a}}.

\bibitem[Domingos(2000{\natexlab{b}})]{Dom00c}
P.~Domingos.
\newblock A {U}nified {B}ias-{V}ariance {D}ecomposition and its {A}pplications.
\newblock In {\em Proceedings of the Seventeenth International Conference on
  Machine Learning}, pages 231--238, Stanford, CA, 2000{\natexlab{b}}. Morgan
  Kaufmann.

\bibitem[Domingos(2000{\natexlab{c}})]{Dom00b}
P.~Domingos.
\newblock A {U}nified {B}ias-{V}ariance {D}ecomposition for {Z}ero-{O}ne and
  {S}quared {L}oss.
\newblock In {\em Proceedings of the Seventeenth National Conference on
  Artificial Intelligence}, pages 564--569, Austin, TX, 2000{\natexlab{c}}.
  AAAI Press.

\bibitem[Evgeniou et~al.(2000)Evgeniou, Perez-Breva, Pontil, and Poggio]{Evg00}
T.~Evgeniou, L.~Perez-Breva, M.~Pontil, and T.~Poggio.
\newblock {B}ounds on the {G}eneralization {P}erformance of {K}ernel {M}achine
  {E}nsembles.
\newblock In P.~Langley, editor, {\em Proc. of the Seventeenth International
  Conference on Machine Learning (ICML 2000)}, pages 271--278. Morgan Kaufmann,
  2000.

\bibitem[Freund and Schapire(1996)]{Fre96}
Y.~Freund and R. E. Schapire.
\newblock Experiments with a new boosting algorithm.
\newblock In {\em Proceedings of the 13th International Conference on Machine
  Learning}, pages 148--156. Morgan Kauffman, 1996.

\bibitem[Friedman(1997)]{Frie97}
J. H. Friedman.
\newblock On bias, variance, 0/1 loss and the curse of dimensionality.
\newblock {\em Data Mining and Knowledge Discovery}, 1:\penalty0 55--77, 1997.

\bibitem[Geman et~al.(1992)Geman, Bienenstock, and Doursat]{Gem92}
S.~Geman, E.~Bienenstock, and R.~Doursat.
\newblock Neural networks and the bias-variance dilemma.
\newblock {\em Neural Computation}, 4\penalty0 (1):\penalty0 1--58, 1992.

\bibitem[Grandvalet and Canu(2003)]{Grand02}
Y.~Grandvalet and S.~Canu.
\newblock {A}daptive {S}caling for {F}eature {S}election in {SVMs}.
\newblock In S.~Becker, S.~Thrun, and K.~Obermayer, editors, {\em NIPS 2002
  Conference Proceedings, Advances in Neural Information Processing Systems},
  volume~15, Cambridge, MA, 2003. MIT Press.

\bibitem[Heskes(1998)]{Hes98}
T.~Heskes.
\newblock Bias/{V}ariance {D}ecompostion for {L}ikelihood-{B}ased {E}stimators.
\newblock {\em Neural Computation}, 10:\penalty0 1425--1433, 1998.

\bibitem[Ho and Basu(2002)]{Ho02a}
T. K. Ho and M.~Basu.
\newblock Complexity measures of supervised classification problems.
\newblock {\em IEEE Transactions on Pattern Analysis and Machine Intelligence},
  24\penalty0 (3):\penalty0 289--300, 2002.

\bibitem[Huang and C. Y.(1995)]{Hua95}
Y. S. Huang and Suen. C. Y.
\newblock Combination of multiple experts for the recognition of unconstrained
  handwritten numerals.
\newblock {\em IEEE Transactions on Pattern Analysis and Machine Intelligence},
  17:\penalty0 90--94, 1995.

\bibitem[James(2003)]{James03}
G.~James.
\newblock Variance and bias for general loss function.
\newblock {\em Machine Learning}, \penalty0 (2):\penalty0 115--135, 2003.

\bibitem[Joachims(1999)]{Joa99}
T.~Joachims.
\newblock Making large scale {SVM} learning practical.
\newblock In Smola~A. Scholkopf~B., Burges~C., editor, {\em Advances in Kernel
  Methods - Support Vector Learning}, pages 169--184. MIT Press, Cambridge, MA,
  1999.

\bibitem[Kim et~al.(2002)Kim, Pang, Je, Kim, and Bang]{Kim02}
H. C. Kim, S.~Pang, H. M. Je, D.~Kim, and S. Y. Bang.
\newblock Pattern {C}lassification {U}sing {S}upport {V}ector {M}achine
  {E}nsemble.
\newblock In {\em Proceedings of the International Conference on
  Pattern Recognition, 2002}, volume~2, pages 20160--20163. IEEE, 2002.

\bibitem[Kittler et~al.(1998)Kittler, Hatef, Duin, and J.]{Kit98b}
J.~Kittler, M.~Hatef, R. P. W. Duin, and Matas J.
\newblock On combining classifiers.
\newblock {\em IEEE Trans. on Pattern Analysis and Machine Intelligence},
  20\penalty0 (3):\penalty0 226--239, 1998.

\bibitem[Kleinberg(2000)]{Klein00}
E. M. Kleinberg.
\newblock A {M}athematically {R}igorous {F}oundation for {S}upervised
  {L}earning.
\newblock In J.~Kittler and F.~Roli, editors, {\em Multiple Classifier Systems.
  First International Workshop, MCS 2000, Cagliari, Italy}, volume 1857 of {\em
  Lecture Notes in Computer Science}, pages 67--76. Springer-Verlag, 2000.

\bibitem[Kohavi and Wolpert(1996)]{Kohavi96}
R.~Kohavi and D. H. Wolpert.
\newblock Bias plus variance decomposition for zero-one loss functions.
\newblock In {\em Proc. of the {T}hirteenth {I}nternational {C}onference on
  {M}achine {L}earning, The Seventeenth International Conference on Machine
  Learning}, pages 275--283, Bari, Italy, 1996. Morgan Kaufmann.

\bibitem[Kong and Dietterich(1995)]{Kon95}
E.~Kong and T. G. Dietterich.
\newblock Error-correcting output coding correct bias and variance.
\newblock In {\em The XII International Conference on Machine Learning}, pages
  313--321, San Francisco, CA, 1995. Morgan Kauffman.

\bibitem[Kuncheva et~al.(2001{\natexlab{a}})Kuncheva, Bezdek, and Duin]{Kun01}
L. I. Kuncheva, J. C. Bezdek, and R. P. W. Duin.
\newblock Decision templates for multiple classifier fusion: an experimental
  comparison.
\newblock {\em Pattern Recognition}, 34\penalty0 (2):\penalty0 299--314,
  2001{\natexlab{a}}.

\bibitem[Kuncheva et~al.(2001{\natexlab{b}})Kuncheva, Roli, Marcialis, and
  Shipp]{Kun01a}
L. I. Kuncheva, F.~Roli, G. L. Marcialis, and C. A. Shipp.
\newblock {C}omplexity of {D}ata {S}ubsets {G}enerated by the {R}andom
  {S}ubspace {M}ethod: {A}n {E}xperimental {I}nvestigation.
\newblock In J.~Kittler and F.~Roli, editors, {\em Multiple Classifier Systems.
  Second International Workshop, MCS 2001, Cambridge, UK}, volume 2096 of {\em
  Lecture Notes in Computer Science}, pages 349--358. Springer-Verlag,
  2001{\natexlab{b}}.

\bibitem[Kuncheva and Whitaker(2003)]{Kun03a}
L. I. Kuncheva and C. J. Whitaker.
\newblock Measures of diversity in classifier ensembles.
\newblock {\em Machine Learning}, 51:\penalty0 181--207, 2003.

\bibitem[Li and Vitanyi(1993)]{Li93}
M.~Li and P~Vitanyi.
\newblock {\em An Introduction to Kolmogorov Complexity and Its Applications}.
\newblock Springer-Verlag, Berlin, 1993.

\bibitem[Mason et~al.(2000)Mason, Bartlett, and Baxter]{Mason00}
L.~Mason, P.~Bartlett, and J.~Baxter.
\newblock Improved generalization through explicit optimization of margins.
\newblock {\em Machine Learning}, 2000.

\bibitem[Merz and Murphy(1998)]{Mer98}
C. J. Merz and P. M. Murphy.
\newblock {UCI} repository of machine learning databases, 1998.
\newblock www.ics.uci.edu/mlearn/MLRepository.html.

\bibitem[Prodromidis et~al.(1999)Prodromidis, Chan, and Stolfo]{Prod99}
A.~Prodromidis, P.~Chan, and S.~Stolfo.
\newblock Meta-{L}earning in {D}istributed {D}ata {M}ining {S}ystems: {I}ssues
  and {A}pproaches.
\newblock In H.~Kargupta and P.~Chan, editors, {\em Advances in Distributed
  Data Mining}, pages 81--113. AAAI Press, 1999.

\bibitem[Schapire(1999)]{Scha99}
R. E. Schapire.
\newblock A brief introduction to boosting.
\newblock In Thomas Dean, editor, {\em 16th International Joint Conference on
  Artificial Intelligence}, pages 1401--1406. Morgan Kauffman, 1999.

\bibitem[Schapire et~al.(1998)Schapire, Freund, Bartlett, and Lee]{Scha98}
R. E. Schapire, Y.~Freund, P.~Bartlett, and W.~Lee.
\newblock Boosting the margin: A new explanation for the effectiveness of
  voting methods.
\newblock {\em The Annals of Statistics}, 26\penalty0 (5):\penalty0 1651--1686,
  1998.

\bibitem[Scholkopf and Smola(2002)]{Scholk02}
B.~Scholkopf and A.~Smola.
\newblock {\em Learning with Kernels}.
\newblock MIT Press, Cambridge, MA, 2002.

\bibitem[Tibshirani(1996)]{Tib96}
R.~Tibshirani.
\newblock Bias, variance and prediction error for classification rules.
\newblock Technical report, Department of Preventive Medicine and Biostatistics
  and Department od Statistics, University of Toronto, Toronto, Canada, 1996.

\bibitem[Valentini and Dietterich(2003)]{Val03b}
G.~Valentini and T. G. Dietterich.
\newblock Low {B}ias {B}agged {S}upport {V}ector {M}achines.
\newblock In T.~Fawcett and N.~Mishra, editors, {\em Machine Learning,
  Proceedings of the Twentieth International Conference (ICML 2003)}, pages
  752--759, Washington D. C., USA, 2003. AAAI Press.

\bibitem[Valentini and Masulli(2002)]{Val02h}
G.~Valentini and F.~Masulli.
\newblock {NEURObjects}: an object-oriented library for neural network
  development.
\newblock {\em Neurocomputing}, 48\penalty0 (1--4):\penalty0 623--646, 2002.

\bibitem[Valentini et~al.(2003)Valentini, Muselli, and Ruffino]{Val03a}
G.~Valentini, M.~Muselli, and F.~Ruffino.
\newblock Bagged {E}nsembles of {SVMs} for {G}ene {E}xpression {D}ata
  {A}nalysis.
\newblock In {\em IJCNN2003, The IEEE-INNS-ENNS International Joint Conference
  on Neural Networks}, pages 1844--49, Portland, USA, 2003. IEEE.

\bibitem[Vapnik(1998)]{Vap98}
V.~N. Vapnik.
\newblock {\em Statistical Learning Theory}.
\newblock Wiley, New York, 1998.

\bibitem[Wang et~al.(1998)Wang, Keller, Carson, McAdoo-Edwards, and
  Bailey]{Wang98}
D.~Wang, J. M. Keller, C. A. Carson, K. K. McAdoo-Edwards, and C. W. Bailey.
\newblock Use of fuzzy logic inspired features to improve bacterial recognition
  through classifier fusion.
\newblock {\em IEEE Transactions on Systems, Man and Cybernetics}, 28B\penalty0
  (4):\penalty0 583--591, 1998.

\end{thebibliography}


\end{document}
