\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

%packages

\usepackage{jmlr2e}
\usepackage{epsf}
\usepackage{amsmath}
%\usepackage{mlapa}
%\usepackage{psfig}
\usepackage{subfigure}
\usepackage{graphicx}
\usepackage{color}
\usepackage{algorithmic}
\usepackage{tabularx}
\usepackage[part,boxed]{algorithm}
\usepackage{wrapfig}
\usepackage{boxit}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Macros
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% letters
\newcommand{\h}{\mathcal{H}}
\newcommand{\s}{\mathcal{S}}
\newcommand{\A}{\mathcal{A}}
\newcommand{\X}{\mathcal{X}}
\newcommand{\Y}{\mathcal{Y}}
\newcommand{\V}{\mathcal{V}}
\newcommand{\LLL}{\mathcal{L}}
\newcommand{\YYY}{\mathcal{Y}}
\newcommand{\UUU}{\mathcal{U}}
\newcommand{\VVV}{\mathcal{V}}
\newcommand{\HHH}{\mathcal{H}}
\newcommand{\Phat}{\hat{P}}

% Algs
\newcommand{\expf}{\textsc{exp4}}
\newcommand{\expt}{\textsc{exp3}}
\newcommand{\expto}{\textsc{exp3.1}}
\newcommand{\dblexpf}{\textsc{dbl-exp4}}
\newcommand{\dblexpt}{\textsc{dbl-exp3}}
\newcommand{\gmax}{\textsc{max}}
\newcommand{\simple}{\textsc{simple}}
\newcommand{\maxmin}{\textsc{max-min}}
\newcommand{\maxratio}{\textsc{max-ratio}}
\newcommand{\self}{\textsc{self-conf}}
\newcommand{\comb}{\textsc{comb}}
\newcommand{\alg}{\textsc{alg}}
\newcommand{\act}{\textsc{active}}
\newcommand{\ff}{\textsc{FF}}
\newcommand{\kff}{\textsc{kff}}
\newcommand{\rr}{\textsc{r-robin }}
\newcommand{\rand}{\textsc{rand}}
\newcommand{\Acc}{\textrm{Acc}}
\newcommand{\bbb}{\mathbf b}
\newcommand{\eee}{\mathbf e}
\renewcommand{\ggg}{\mathbf g}
\newcommand{\Def}{\textrm{Def}}

% colors
\newcommand{\Red}{\color{red}}
\newcommand{\Blue}{\color{blue}}
\newcommand{\Green}{\color{green}}
\newcommand{\Black}{\color{black}}
\newcommand{\Magenta}{\color{Magenta}}
\newcommand{\rnote}[1]{{\Blue #1}}
\newcommand{\bnote}[1]{{\Red #1}}

\newcommand{\fracpartial}[2]{\frac{\partial #1}{\partial  #2}}

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

\jmlrheading{5}{2004}{255-291}{10/03}{3/04}{Yoram Baram, Ran El-Yaniv, and Kobi Luz}

% Short headings should be running head and authors last names

\ShortHeadings{Online Choice of Active Learning Algorithms}{Baram,
  El-Yaniv, and Luz}
\firstpageno{255}

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% titles/headings
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\title{Online Choice of Active Learning Algorithms}

\author{\name Yoram Baram \email baram@cs.technion.ac.il\AND
        \name Ran El-Yaniv \email rani@cs.technion.ac.il\AND
        \name Kobi Luz \email kobil@cs.technion.ac.il \\
       \addr Department of Computer Science\\
            Technion - Israel Institute of Technology\\
            Haifa 32000\\
            Israel
}

\editor{Manfred Warmuth}

\maketitle

\begin{abstract}
This work is concerned with the question of how to combine online
an ensemble of active learners so as to expedite the learning
progress in pool-based active learning. We develop an
active-learning master algorithm, based on a known competitive algorithm
for the multi-armed bandit problem. A major challenge in
successfully choosing top performing active learners online is to
reliably estimate their progress during the learning session. To this
end we propose a simple maximum entropy criterion that provides
effective estimates in realistic settings. We study the
performance of the proposed master algorithm using an ensemble
containing two of the best known active-learning algorithms as
well as a new algorithm. The resulting active-learning master
algorithm is empirically shown to consistently perform almost as
well as and sometimes outperform the best algorithm in the
ensemble on a range of classification problems.
\end{abstract}

\begin{keywords}
Active learning, kernel machines, online learning,
multi-armed bandit, entropy maximization
\end{keywords}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Sections
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
The goal in \emph{active learning} is to design and analyze
learning algorithms that can effectively choose the samples for
which they ask the teacher for a label. The incentive for using
active learning is mainly to expedite the learning process and
reduce the labeling efforts required by the teacher. While there
is a lack of theoretical understanding of active learning (in
particular, the generalization power of computationally practical
active-learning algorithms is not well understood\footnote{In
noise-free settings, the Query-by-Committee (QBC) algorithm of
\cite{Freund97indormation} can provably provide exponential
speedups in the learning rate over a random selection. However,
at this time a ``practically efficient'' implementation of this
technique seems to be beyond reach \citep[see,
for example,][]{Bachrach99query}.}), there is substantial empirical
evidence that active learning can dramatically expedite the
learning process.

We focus on \emph{pool-based} active learning by classifiers,
which can be viewed as  the following game composed of
\emph{trials}. The learner is presented with a fixed pool of
unlabeled instances. On each trial the learner chooses one
instance from the pool to be labeled by the teacher. The teacher
provides the learner with the true label of this instance and
then the learner induces a (new) classifier based on all the labeled
samples seen so far and possibly on unlabeled instances in the
pool. Then a new trial begins, etc. Other variants of the
active-learning problem have also been considered. Two important variants
are \emph{stream-based} active learning
\citep{Freund97indormation} and learning with \emph{membership
queries} \citep{Angluin88}; see Section~\ref{sec:related} for more
details. We do not consider these variants in this work.

Seeking top performing active-learning algorithms among the
numerous algorithms proposed in the literature, we found two
algorithms that appear to be among the best performers, based on
empirical studies. The first algorithm relies on kernel machines
and was independently proposed by three research groups
\citep{TongK2001,Schohn00less,CampbellCS00query}. The algorithm,
called $\simple$ by \cite{TongK2001}, uses the current SVM
classifier to query the instance closest to the decision
hyperplane (in kernel space). A theoretical motivation for
$\simple$ is developed by \cite{TongK2001} in terms of version space
bisection. The second algorithm we consider, proposed by
\cite{Roy01toward}, is based on a different motivation: the
algorithm chooses its next example to be labeled while attempting
to reduce the generalization error probability. Since true future
error rates are unknown, the learner attempts to estimate them
using a ``self-confidence'' heuristic that utilizes its current
classifier for probability measurements. Throughout this paper we,
therefore, call this algorithm $\self$. The original $\self$
proposed by \cite{Roy01toward} bases its probability estimates
(and classification) on Naive Bayes calculations and is shown to
significantly outperform other known active-learning algorithms on
text categorization tasks. In our studies we used an SVM-based
variant of $\self$, which appears to be stronger than the original.

Empirical studies we have conducted reveal that neither $\simple$
nor $\self$ is a consistent winner across problems. Moreover, both
algorithms exhibit a severe pitfall that seems to appear in
learning problems with a ``XOR-like'' structure (see
Section~\ref{sec:xor_example}). While perhaps no single
active-learning algorithm should be expected to consistently perform
better than others on all problems, some problems clearly favor
particular algorithms. This situation motivates an online learning
approach whereby one attempts to utilize an \emph{ensemble}
of algorithms online aiming to achieve a performance that is close to the
best algorithm in hindsight. This scheme has been extensively
studied in computational learning theory, mainly in the context of
`online prediction using expert advice' \citep[see,
for example,][]{CesaBianchiFHHSW97}. Our main contribution is an algorithm
that actively learns by combining active learners.

A reasonable approach to combining an ensemble of active-learning
algorithms (or `experts') might be to evaluate their individual
performance and dynamically switch to the best performer
so far. However, two obstacles stand in the way of
successfully implementing this scheme. First, standard classifier
evaluation techniques, such as cross-validation, leave-one-out, or
bootstrap, tend to fail when used to estimate the performance of
an active learner based on the labeled examples chosen by the
learner. The reason is that the set of labeled instances selected
by a good active learner tends to be acutely biased towards `hard'
instances that do not reflect the true underlying distribution. In
Section~\ref{sec:cem} we show an example of this phenomenon.
Second, even if we overcome the first problem, each time we choose
to utilize a certain expert, we only get to see the label of the
example chosen by this expert and cannot observe the consequence
of choices corresponding to other experts without ``wasting'' more
labeled examples.

We overcome these two obstacles by using the following two ideas.
Instead of using standard statistical techniques, such as
cross-validation, we use a novel maximum entropy semi-supervised
criterion, which utilizes the pool of unlabeled samples and can
faithfully evaluate the relative progress of the various experts;
second, we cast our problem as an instance of the
\emph{multi-armed bandit} problem, where each expert corresponds
to one slot machine and on each trial we are allowed to play one
machine (that is, choose one active-learning algorithm to generate the
next query). We then utilize a known online multi-armed bandit
algorithm proposed by \cite{AuerCFS02}. This algorithm enjoys
strong performance guarantees without any statistical assumptions.

We present an extensive empirical study of our new active-learning
master algorithm and compare its performance to its ensemble
members consisting of three algorithms: $\simple$, $\self$ and a
novel active-learning heuristic based on ``furthest-first
traversals'' \citep{HochbaumS85}. Our master algorithm is shown to
consistently perform almost as well as the best algorithm in the
ensemble, and on some problems it outperforms the best algorithm.

\section{Active Learning}
\label{sec:active_learning}

In this section we first define pool-based active learning and
then discuss performance measures for active learners. We consider
a binary classification problem and are given a pool
$\UUU=\{x_1,\ldots,x_n\}$ of unlabeled instances where each $x_i$
is a vector in some space $\mathcal{X}$. Instances are assumed to
be i.i.d. distributed according to some unknown fixed distribution
$P(x)$. Each instance $x_i$ has a label $y_i \in \YYY$ (where in
our case $\YYY=\{\pm 1\}$) distributed according to some unknown
conditional distribution $P(y|x)$. At the start, none of the
labels is known to the learner. At each stage of the
active-learning game, let $\LLL$ be the set of labeled instances already
known to the learner.\footnote{We assume that initially $\LLL$
contains two examples, one from each class.} An \emph{active
learner} consists of a classifier learning algorithm $\A$, and a
\emph{querying function} $Q$, which is a mapping $Q: \LLL \times
\UUU \to \UUU$. The querying function determines one unlabeled
instance in $\UUU$ to be labeled by the teacher. On each
\emph{trial} $t=1,2,\ldots$, the active learner first applies $Q$
to choose one unlabeled instance $x$ from $\UUU$. The label $y$ of
$x$ is then revealed and the pair $(x,y)$ is added to $\LLL$ and
$x$ is removed from $\UUU$. Then the learner applies $\A$ to
induce a new classifier $C_t$ using $\LLL$ (and possibly $\UUU$)
as a training set and a new trial begins, etc. Thus, the active
learner generates a sequence of classifiers $C_1,C_2,\ldots$.
Clearly, the maximal number of trials is the initial size of
$\UUU$. In this paper we focus on active learners $(\A,Q)$ where
$\A$ is always an SVM induction algorithm.

\begin{figure}[htb!]
  \begin{center}
    \epsfig{file=deff.eps,width=3.3in}
    \caption[Illustration of an active learner's \emph{deficiency}.]
    {The definition of an active learner's \emph{deficiency}. $\Acc_n(\alg)$  is
    the maximal achievable accuracy. $\Acc_t(\act)$ is the average
    accuracy achieved by hypothetical active learner $\act$. $\Acc_t(\alg)$ is the
    average accuracy achieved by a ``passive'' learner $\alg$ (which
    queries randomly and uniformly from the pool).
    In this case (when the active-learning curve is above the passive
    learning curve) the \emph{deficiency}, as defined in
    Equation~(\ref{eq:performance}),
    is the ratio of areas $\frac{A}{A+B}$.}
    \label{fig:defficiency}
\end{center}
\end{figure}

To the best of our knowledge, in the literature there is no
consensus on appropriate performance measures for active learning.
A number of performance measures for active-learning algorithms
make sense. For example, some authors \citep[for instance,][]{TongK2001}
test the accuracy achieved by the active learner after a
predetermined number of learning trials. Other authors
\citep[for example,][]{Schohn00less,CampbellCS00query,Roy01toward} simply
show active-learning curves to visually demonstrate advantages in
learning speed. Here we propose the following natural performance
measure, which aims to quantify the ``deficiency'' of the querying
function with respect to random sampling from the pool (which
corresponds to standard ``passive learning''), while using a fixed
inductive learning algorithm $\alg$. Fix a particular
classification problem. Let $\UUU$ be a random pool of $n$
instances. For each $1 \leq t \leq n$ let $\Acc_t(\alg)$ be the
true average accuracy achievable by $\alg$ using a training set of
size $t$ that is randomly and uniformly chosen from $\UUU$.
A hypothetical $\Acc_t(\alg)$ is depicted by the lower learning
curve in Figure~\ref{fig:defficiency}. Let $\act$ be an
active-learning algorithm that uses $\alg$ as its inductive learning
component $\A$. Define $\Acc_t(\act)$ to be the average accuracy
achieved by $\act$ after $t$ active-learning trials starting with
the pool $\UUU$ (see Figure~\ref{fig:defficiency} for a
hypothetical $\Acc_t(\act)$, which is depicted by the higher
learning curve). Then, the \emph{deficiency} of $\act$ is defined
to be
\begin{equation}
\label{eq:performance} \Def_n(\act) = \frac{\sum_{t=1}^n
(\Acc_{n}(\alg)-\Acc_t(\act))} {\sum_{t=1}^n
(\Acc_{n}(\alg)-\Acc_t(\alg))}.
\end{equation}
In words, the deficiency is simply the ratio of areas
$\frac{A}{A+B}$, as depicted in Figure~\ref{fig:defficiency}. This
measure captures the ``global'' performance of an active learner
throughout the learning session. Notice that the numerator is
simply the area between the ``maximal''\footnote{In some cases
\citep[see for example,][]{Schohn00less}, better accuracy can be achieved
using ``early stopping'' (see Section~\ref{sec:related}).}
achievable accuracy $\Acc_n(\alg)$ using the entire pool, and the
learning curve of the active-learning algorithm (area $A$ in
Figure~\ref{fig:defficiency}). The denominator is the area between
the same maximal accuracy and the learning curve of the
``passive'' algorithm (the sum of areas $A$ and $B$ in
Figure~\ref{fig:defficiency}). The purpose of the denominator is
to normalize the measure so as to be ``problem independent''.
Thus, this measure is always non-negative and
\textbf{\emph{smaller}} values in $[0,1)$ indicate more
\emph{efficient} active learning. $\Def_n(\act)$ has the desired
property that if $n$ is sufficiently large so that $\Acc_n(\alg)$
achieves the maximal accuracy (for this classifier), then for any
$n' > n$, $\Def_{n'}(\act) = \Def_n(\act)$.

\section{Related Work}
\label{sec:related}

This paper is the first to consider a utilization of an ensemble
of active learners. Here we discuss selected results related to
the present work. Our main focus is on techniques for devising
querying functions and methods that can be used to evaluate the
progress of an active learner. Note that, in general, a method
estimating the ``value'' of an \emph{unlabeled point} can be used
to construct a querying function, and a method that evaluates the
gain of a newly acquired \emph{labeled point} can be used as an
estimator for an active learner's progress.

We begin with a presentation of various techniques used to
construct querying functions. Although our work focuses on
pool-based active learning, a number of interesting and relevant
ideas appear within other active-learning frameworks. In addition
to the pool-based active-learning setting introduced in
Section~\ref{sec:active_learning}, we consider two other settings:
\begin{itemize}
\item \emph{Stream-based} active learning \citep[see,
for example,][]{Freund97indormation}: the learner is provided with a
stream of unlabeled points. On each trial, a new unlabeled point
is drawn and introduced to the learner who must decide whether or
not to request its label. Note that the stream-based model can be
viewed as an online version of the pool-based model. \item Active
learning with \emph{membership queries} \citep{Angluin88}, also
called \emph{selective sampling}: On each trial the learner
constructs a point in input space and requests its label. This
model can be viewed as a pool-based game where the pool consists
of \emph{all possible points} in the domain.
\end{itemize}
Within the \emph{stream-based} setting, \cite{seung92query}
present the Query by Committee (QBC) algorithm.  This algorithm
is based on a seminal theoretical result stating that by halving
the version space after each query, the generalization error
decreases exponentially (relative to random active learning). To
approximately bisect the version space, the proposed method
randomly samples the version space and induces an even number of
classifiers. The label of a (stream) point is requested whenever a
voting between the classifiers on this point's label results in
a tie. The main obstacle in implementing this strategy is the
sampling of the version space. Currently, it is not known how to
efficiently sample version spaces uniformly at random for many
hypothesis classes of interest \citep[see also discussions
in][]{Bachrach99query,herbrich01bayes}.

A variation of the QBC algorithm was proposed by
\citet{mccallum98employing}. Expectation Maximization (EM) is used
to create a committee of classifiers to implement the querying
function using the QBC voting idea: A diversified committee of
classifiers is created by sampling a population of Naive Bayes
distributions.  Then an EM-like procedure is used to iteratively
classify the unlabelled data and rebuild the classifiers until the
process converges. Experimental results show that this algorithm
has an advantage over random sampling and QBC.\footnote{The QBC
used for comparison utilizes the committee created by sampling of
the Naive Bayes distributions without employing the EM-like
procedure.}

Interesting ideas were also considered within the \emph{learning
with membership queries} setting of \cite{Angluin88}.
\citet{CohnAL94improving} use the following version space
reduction strategy. Two ``distant'' hypotheses are selected from
the version space by finding a ``most specific'' concept (that
classifies as `negative' as much of the domain as possible) and a
``most general'' one (that classifies as `positive' as many points
as possible).\footnote{The most specific (resp. general) concept
is found by classifying many (unlabeled) examples as `negative'
(resp. `positive').} Selective sampling is done by randomly
searching for a domain point on which the most specific and most
general hypotheses disagree. This method ensures that the version
space size is reduced after every query, though it might be
reduced by only one hypothesis. The algorithm was implemented
using a hypothesis class consisting of feed-forward neural
networks trained with the back-propagation algorithm. According to
the authors, the method works well only for ``simple'' concepts.

Again, within the selective sampling model,
\citet{Lindenbaum02selective} propose an active-learning algorithm
for the nearest-neighbor classifier. The paper proposes using a
random field model to estimate class probabilities. Using the
class probabilities of the unlabeled examples a ``utility
function'' of a training set is defined. The querying function of
this algorithm is constructed using a game-tree that models a game
between the learner and the teacher. For each unlabeled example,
its expected utility is measured using the utility function on the
training set and using expected probabilities for the possible
classes of the unlabeled example. A set of domain points is
constructed randomly and the example with highest expected utility
is chosen. This algorithm suffers from extensive time complexity
that depends both on the depth of the game-tree and on the number
of near examples taken to construct the random field.

In the \emph{pool-based} setting, three independent working groups
\citep{Schohn00less, CampbellCS00query, TongK2001} propose the
same querying function for active learners based on support vector machines (SVMs).
This querying function chooses, for the next query, the unlabeled point
closest to the decision hyperplane in kernel space; namely, the
point with the smallest margin. Some theoretical motivation is
given to this function in terms of version space reduction along
the lines of QBC ideas \citep{TongK2001}; see Section~\ref{sec:simple} for
further details. Experimental results presented in these papers
show that the resulting active learner can provide significant
sample complexity speedups compared to random sampling.
\cite{Schohn00less} encountered a phenomenon where the true
accuracy of the learner \emph{decreases} (after reaching a certain
peak) as the active session progresses. This phenomenon motivates
the idea of ``early stopping'' and the authors suggest to stop
querying when no example lies within the SVM margin.
\cite{CampbellCS00query} offer to use this stopping criterion as
a trigger for running a test for the current classifier. In this
test they randomly and uniformly choose a small subsample of
(unlabeled) pool points, request the labels of these points from
the teacher and then test the current classifier on these points.
The algorithm decides to stop if the error (as estimated using
this test) is ``satisfying'' according to a user defined
threshold.

\cite{Zhang00probability} analyze the value of unlabeled data in
both active and transductive learning settings focusing on SVM
learning. The value of unlabeled data is evaluated using Fisher
information matrices. It is proved that selecting unlabeled data
\emph{with low confidence} (i.e. small margin) that is not
subsumed by (i.e., not too close to) previous choices is likely to
cause a large change in the model (once the true label is known).
A few numerical examples presented in this paper show that an SVM-based
active learner using this criterion is superior to random
selection.

\cite{Roy01toward} offer a pool-based active-learning algorithm
that attempts to ``directly'' optimize the true generalization
error rate (rather than reduce the version space). The algorithm
chooses to query points that strengthen the belief of the current
classifier about the pool classification. The learner estimates
its error on the unlabeled pool, where the current classifier's
posterior class probabilities are taken as proxies for the true
ones. For each example in the pool and for each possible label,
the expected loss of a classifier trained after adding this
example to the training set is calculated. The example from the
pool with the lowest total expected loss is chosen as the next
query. The computational complexity required to implement this
scheme is ``hopelessly impractical,'' as noted by the authors.
However, various heuristic approximations and optimizations are
suggested. Some of these optimizations (for example, subsampling) are
general and some are designed for the specific implementation
provided by \cite{Roy01toward}, which is based on Naive Bayes.
The authors report that the resulting active learner exhibits
excellent performance over text categorization
problems.\footnote{Our implementation of this algorithm, as
discussed in Section~\ref{sec:self_conf}, uses SVMs rather than
Naive Bayes and only utilizes the subsampling approximation idea
suggested by \cite{Roy01toward}.} In Section~\ref{sec:three_algs}
we further elaborate on the two pool-based algorithms mentioned
above.

Active learning has also been explored in the contexts of
regression and probabilistic estimation.
\cite{saar-tsechansky-active} examine the use of active learning
for \emph{class probability estimation} (in contrast to exact, or
`hard' classification). The algorithm proposed is based on
creating a number of subsamples from the training set and training
one soft classifier (capable of giving class
probability estimates) on each subsample. All these generated classifiers form an
``ensemble''. The querying function works by drawing a pool point
according to a probability distribution that is proportional to
the variance of the probability estimates computed by the various
ensemble members. This variance is normalized by the average
probability of the minority class. Empirical results indicate that
this algorithm performs better than random sampling (both as a
soft as well as a hard classifier).

In the context of regression, \cite{Cohn96active} assume that the
learner is approximately unbiased and propose an active-learning
algorithm that chooses to query the instance that minimizes the
average expected variance of the learner (integrated over the
input domain). This algorithm is outlined for general feed-forward
neural networks, a mixture of Gaussians and locally weighted
regression. For the latter two learning schemes, this method is
efficient. However, this method ignores the learner's bias. The
algorithm requires a closed form calculation of the learner's
variance, which has been developed only for the three learning
schemes considered.

In the context of ensemble methods for regression,
\cite{krogh95neural} show a nice equality giving the (squared
error loss) regression generalization error as a (weighted) sum of
the generalization errors of the individual members minus a
diversity measure called `ambiguity', which is related to the
anti-correlation between ensemble members. Increasing this
ambiguity (without increasing the weighted sum of individual
errors) will reduce the overall error. Increasing the ambiguity is
done by dividing the training set into a number of disjoint
subsets and training one ensemble member over a distinct training
subset. One nice property of the ambiguity measure is that it can
be computed without the labels. \cite{krogh95neural} apply this
relation (which guarantees that the weighted ambiguity is a lower
bound on the weighted sum of individual ensemble generalization
errors) in the context of pool-based active learning as follows.
Assuming that the most beneficial pool point to sample is the one
that increases the weighted sum of individual ensemble errors,
they search for the point whose contribution to the ensemble
ambiguity is maximal.

We now turn to discuss some approaches to measuring the ``value''
of \emph{labeled} points. Such methods are potentially useful for
obtaining information on the progress of active learners, and may
be useful for implementing our approach that combines an ensemble
of active learners. Within a Bayesian setting,
\cite{mackay92informationbased} attempts to measure the
information that can be gained about the unknown target hypothesis
using a new \emph{labeled} point. Two gain measures are
considered, both based on Shannon's entropy. It is assumed that
given a training set, a probability distribution over the possible
hypotheses is defined. The first measure is how much the entropy
of the hypothesis distribution has decreased using a new labeled
point. A decrease in this entropy can indicate how much the
support of this hypothesis distribution shrinks. The second
measure is the cross-entropy between the hypothesis distributions
before and after the new labeled point is added. An increase in
this cross-entropy can indicate how much the support has changed
due to the new information. It is proved that these two gain
measures are equivalent in the sense that their expectations are
equal.

\cite{guyon96discovering} propose methods to measure the
information gain of labeled points in a data set. The information
gain of a labeled point with respect to a trained probabilistic
(soft) classifier is defined as the probability that the
classification of this point is correct. This probability equals
the Shannon ``information gain'' of the class probability of that
point as measured by the probabilistic classifier. On a given
labeled data set, the information gain of each point can be
measured using the above definition with a leave-one-out
estimator. The paper also addresses the information gain of
labeled points in the context of minimax learning algorithms such
as SVM. The SVM measures the information gain of a labeled point
by its (``alpha'') coefficient in the induced weights vector. The
coefficient of a point that is not a support vector is zero, and
so is its information gain. Support vectors with larger
coefficients are more informative. These ideas are discussed in
the context of ``data cleaning'' of large databases. We note that,
in the context of SVM active learning it is not in general the
case that support vectors identified during early trials will
remain support vectors thereafter.

Finally, we note that active learning is only one way of
exploiting the availability of unlabeled data. In recent years the
broader topic of ``semi-supervised'' or ``learning with
labeled-unlabeled examples'' has been gaining popularity. One can
distinguish between inductive semi-supervised methods and
transductive ones \citep{Vapnik98}; see a recent survey by \cite{seeger00learning}
for a recent review.

\section{On Three Active-Learning Algorithms}
\label{sec:three_algs}

The main purpose of this section is to motivate the challenge
considered in this work. In contrast to what may be implied in
various recent papers in the field, when closely examining
state-of-the-art active-learning algorithms on various learning
problems, there is no consistent single winner. While not
necessarily surprising, it remains unclear how to choose the best
active-learning algorithm for the problem at hand.

To demonstrate this point we focus on two known active-learning
algorithms: $\simple$
\citep{TongK2001,Schohn00less,CampbellCS00query} and the algorithm
of \cite{Roy01toward}, which we call here $\self$. We
selected these algorithms because they are both reasonably well
motivated, achieve high performance on real-world data (and
surpass various other known algorithms) and appear to complement each
other. In particular, as we show below, neither algorithm
consistently tops the other.\footnote{To the best of our
knowledge, no previous attempts to compare these two
algorithms have been conducted.} Moreover, both algorithms fail in
learning problems with ``XOR-like'' structures (in the sense that
they perform considerably worse than random
sampling).\footnote{This deficiency (of $\simple)$ was already
observed by \cite{TongK2001}.} We thus consider another novel
algorithm, which excels on `XOR' problems but exhibits quite poor
performance on problems with simple structures. Altogether, these
three algorithms form the ensemble on which our new ``master''
algorithm is later experimentally applied
(Section~\ref{sec:results}). Throughout the rest of the paper we assume basic
familiarity with SVMs.\footnote{Good
textbooks on the subject were written by \cite{CristianiniS00}
and \cite{ScholkopfS2002}.}

\subsection{Algorithm SIMPLE}
\label{sec:simple}

This algorithm uses an SVM as its induction component. The
querying function of $\simple$ at trial $t$ uses the already
induced classifier $C_{t-1}$ to choose an unlabeled instance,
which is closest to the decision boundary of $C_{t-1}$. Thus, the
querying function can be computed in time linear in $|\UUU|$
(assuming the number of support vectors is a constant).

An intuitive interpretation of $\simple$ is that it chooses to
query the instance whose label is the ``least certain'' according
to the current classifier. A more formal theoretical motivation
for $\simple$ is given by \cite{TongK2001} in terms of
\emph{version space} bisection. This argument utilizes a nice
duality between instances and hypotheses. The \emph{version space}
\citep{Mitchell82} is defined as the set of all hypotheses
consistent with the training set. Let $\LLL = \{(x_1,
y_1),\dots,(x_m, y_m)\}$ be a training set, and let $\HHH$ be the
set of all hypotheses (in our case $\HHH$ is the set of all
hyperplanes in kernel space). The version space $\VVV$ is defined
as
\begin{equation*}
\label{eq:version} \VVV = \{ h \in \HHH | \forall (x, y) \in \LLL,
h(x) = y \}.
\end{equation*}

Let $w^{*}$ be a hyperplane constructed in kernel space by
training an SVM on the entire pool with the true labeling (clearly
$w^*$ cannot be computed by an active learner without querying the
entire pool). A good strategy for an active learner would be to
choose a query that bisects the version space as it brings us
faster to $w^{*}$. The question is how to find the instance that
approximately bisects the version space. The version space can be
viewed as a subsurface of the unit hypersphere in parameter space
(the entire surface contains all possible hypotheses). Every
unlabeled instance $x$ corresponds to a hyperplane $\Phi(x)$ in
the parameter space. The hypotheses $\{w | (w \cdot x) > 0\}$ that
classify $x$ `positively' lie on one side of this hyperplane and
the hypotheses $\{w | (w \cdot x) < 0\}$ that classify $x$
`negatively' lie on the other side. Let $w$ be a hyperplane
constructed in kernel space by training an SVM on the current set
of labeled instances. \cite{TongK2001} show that $w$ is
the center of the largest hypersphere that can be placed in
version space and whose surface does not intersect the hyperplanes
corresponding to the labeled instances. Moreover, the radius of
this hypersphere is the margin of $w$ and the hyperplanes that
``touch'' this hypersphere are those corresponding to the support
vectors. Therefore, in cases where this hypersphere sufficiently
approximates the version space, $w$ approximates the center of
mass of the version space. The closer an unlabeled instance is to
$w$, the closer the hyperplane $\Phi(x)$ is to the center of mass of
the version space. This motivates the strategy of querying the
closest instance to $w$, as it can bisect the version space and
quickly advance the algorithm toward the (unknown) target
hypothesis $w^{*}$.

\cite{TongK2001} require that each of the classifiers (i.e., SVMs)
computed during the operation of $\simple$ is consistent with its
training set. This is essential to guarantee a non-vacuous version
space. This requirement is easy to fulfil using the ``kernel
trick'' discussed by \cite{Shaw-TaylorC99}, which guarantees that
the training set is linearly separable in kernel space. Further
details are specified in Appendix~\ref{sec:imp_details}.

When considering simple binary classification problems, this
strategy provides rapid refinement of the decision boundary and
results in very effective active learning
\citep{TongK2001,Schohn00less,CampbellCS00query}. In our
experience, algorithm $\simple$ is a high-performance
active-learning algorithm, which is hard to beat on a wide range of
real-world problems. In particular, this algorithm performs quite
well on text categorization problems \citep{TongK2001}.

We note that two more querying functions (called ``Maxmin'' and
``Maxratio'') are proposed by \cite{TongK2001}. These are also
based on the version space bisection principle and achieve more
efficient version space reduction than $\simple$. The main
drawback of these functions is their computational intensity, which
makes them impractical. Specifically, for each query,
the computation of each of these functions requires the induction
of two SVMs for each unlabeled point in the
pool.\footnote{Approximation heuristics such as subsampling of
the pool as well as using incremental/decremental SVM algorithms
\citep{Cauwenberghs00incremental} can be used to speed up these
algorithms. We have not explored these possibilities in the
present work.}

\subsection{Algorithm SELF-CONF}
\label{sec:self_conf}

The second algorithm we discuss, proposed by \cite{Roy01toward},
is based on a different motivation. The algorithm chooses its next
example to be labeled while ``directly'' attempting to reduce
future generalization error probability. Since true future error
rates are unknown, the learner attempts to estimate them using a
``self-confidence'' heuristic that utilizes its current classifier
for probability measurements. Throughout this paper we therefore
call this algorithm $\self$.\footnote{This self-confidence
approach is somewhat similar to the one proposed by
\cite{Lindenbaum02selective}.}

At the start of each trial this algorithm already holds a trained
probabilistic (soft) classifier denoted by $\Phat(y|x)$. For each
$x \in \UUU$ and $y \in \YYY$ the algorithm trains a new
classifier $\Phat'$ over $\LLL'(x,y)=\LLL \cup \{(x,y)\}$ and
estimates the resulting ``self-estimated expected
log-loss''\footnote{\cite{Roy01toward} also considered using
zero-one loss instead of log-loss.} defined to be
\begin{equation}
\label{eq:roy} E(\Phat'_{\LLL'(x,y)}) = -\frac{1}{|\UUU|} \sum_{y'\in\YYY, x'\in
\UUU} \Phat'(y'|x')\log\Phat'(y'|x').
\end{equation}
Then, for each $x \in \UUU$ it calculates the self-estimated
average expected loss
$$
\sum_{y \in \YYY} \Phat(y|x)
E(\Phat'_{\LLL'(x,y)}).
$$
The $x$ with the lowest self-estimated expected loss is then
chosen to be queried.

The original $\self$ algorithm proposed by \cite{Roy01toward}
bases its probability estimates (and classification) on Naive
Bayes calculations\footnote{The empirical results of
\cite{Roy01toward} considered multinomial models (in particular,
text categorization), which enabled the required calculations.}
and is shown to outperform other known active-learning algorithms
on text categorization tasks. In our studies, we used an SVM-based
variant of $\self$, which appears to be stronger than the original
Naive Bayes algorithm.\footnote{However, we have not performed an
extensive comparison between the Naive Bayes and SVM variants of
this algorithm.} Thus, in our case, probabilistic estimates are
obtained in a standard way, using logistic
regression.\footnote{If $h(x)$ is the (confidence-rated) SVM value for a point $x$ whose
label is $y$, we take
$\Phat(y|x)=\frac{1}{1+\exp\{-yh(x)\}}$.} Also note that the
algorithm, as presented, is extremely inefficient, since for each
query, two SVMs are induced for each unlabeled point in the pool.
Various optimizations and approximations are proposed by
\cite{Roy01toward}, to make its running time practically
feasible. From all these methods we only use random subsampling in
our implementation of the algorithm: On each trial we estimate the
expression (\ref{eq:roy}) for only a random subset of $\UUU$.
The subsample in the first active session trial contains
100 points; on each subsequent trial we decrement the subsample
size by one point until we reach a minimum of 10 points, which we keep
for the remaining trials.

Observe that the motivation for $\self$ and $\simple$ is
in some sense complementary. While $\simple$ queries instances in $\UUU$ with
the least confidence, as measured by its current model, $\self$ queries
instances that provide the maximal ``reassurance'' of its
current model.

\subsection{Algorithm Kernel Farthest-First (KFF)}
Here we propose a simple active-learning heuristic based on
``farthest-first'' traversal sequences in kernel space.
\emph{Farthest-first (FF)} sequences have been previously used for
computing provably approximate optimal clustering for $k$-center
problems \citep{HochbaumS85}. The FF traversal of the points in a
data set is defined as follows. Start with any point $x$ and find
the farthest point from $x$. Then find the farthest point from the
first two (where the distance of a point from a set is defined to
be the minimum distance to a point in the set), etc. In any metric
space, FF traversals can be used for computing 2-approximation
solutions to the \emph{$k$-center clustering} problem in which one
seeks an optimal $k$-clustering of the data and optimality is
measured by the maximum diameter of the clusters. In particular,
by taking the first $k$ elements in the FF traversal as
``centroids'' and then assigning each other point to its closest
``centroid'', one obtains a $k$-clustering whose cost is within a
factor 2 of the optimal \citep{HochbaumS85}.

We use FF traversals for active learning in the following way. Given the
current set $\LLL$ of labeled instances, we choose as our next
query an instance $x\in \UUU$, which is farthest from $\LLL$.
Using $\LLL \cup \{(x,y)\}$ as a training set, the active learner
then induces the next classifier. This heuristic has a nice
intuitive appeal in our context: the next instance to query is the
farthest (and in some sense the most dissimilar) instance in the
pool from those we have already observed. Unlike $\simple$ (and
other algorithms) whose querying function is based on the
classifier, the above FF querying function can be applied with any
classifier learning algorithm. We apply it with an SVM. For
compatibility with the SVM, we compute the FF traversals in kernel
space as follows. Given any kernel $K$, if $x$ and $y$ are
instances in input space, and $\Phi(x)$ and $\Phi(y)$ are their
embedding in kernel space (so that $\langle \Phi(x),\Phi(y)
\rangle = K(x,y)$), then we measure $d_K(x,y)$, the distance
between $x$ and $y$ in kernel space, as $d^2(x,y) = \| \Phi(x) -
\Phi(y)\|^2 = K(x,x)+K(y,y)-2K(x,y)$. We call the resulting
algorithm $\kff$.

\subsection{Some Examples}
\label{sec:xor_example}

Figure~\ref{fig:active-compare} shows the learning curves of
$\simple$, $\self$, $\kff$ and of a random sampling ``active
learner'' (which we call $\rand$)\footnote{The querying function
of $\rand$ chooses the next example to be labeled uniformly at
random from $\UUU$.} for the artificial `XOR' problem of
Figure~\ref{fig:active-compare} (top left) as well as two other
UCI problems - `Diabetis' and `Twonorm'. These three learning
problems demonstrate that none of the three active-learning
algorithms discussed here is consistently better than the rest. In
the two UCI problems $\simple$ performs better than $\self$ on the
`Twonorm' data set, while $\self$ performs better than $\simple$ on
the `Diabetis' data set. $\kff$ is inferior to the other two in
both cases.
\begin{figure*}[htb!]
  \begin{center}
    \leavevmode
    \begin{tabular}{cc}
     \epsfig{file=xor.eps,width=2.1in} &
     \epsfig{file=xor-active.eps,width=2.7in} \\
     \epsfig{file=diabetis-active.eps,width=2.7in} &
     \epsfig{file=twonorm-active.eps,width=2.8in}
    \end{tabular}
    \caption[Learning curves for $\simple$, $\self$, $\kff$
    and $\rand$ an artificial 'XOR' problem as well as two UCI problems.]
    { \textbf{Top Left}: `XOR' problem consisting of 1000 points
    (250 in each ``cluster''); 250 points form the pool and the rest form the test set.
    \textbf{Top Right}: Learning curves for $\simple$, $\self$, $\kff$
    and $\rand$ for the `XOR' problem where $\kff$ exhibits superior performance.
    \textbf{Bottom left}: Learning curves for the same four learners on
    the `Diabetis' data set in which $\self$ is superior.
    \textbf{Bottom Right}: Learning curves for the same
    four learners on the `Twonorm' data set in which $\simple$ is superior.
    Each point on each learning curve represents an average over 100 folds
    (measured over a test set); each error bar represents one standard
    error of the mean. Error bars are diluted to enhance visibility.}
    \label{fig:active-compare}
  \end{center}
\end{figure*}
In the `XOR' problem $\simple$'s and $\self$'s performances are
significantly worse than that of random sampling. On the other
hand, $\kff$ clearly shows that active learning can expedite
learning also in this problem. This weakness of both $\simple$ and
$\self$ typically occurs when confronting problems with ``XOR-like'' structure.
The inferiority of $\kff$ relative to $\simple$ and $\self$ (and even
$\rand$) typically occurs in learning problems with a ``simple'' structure.
The main advantage in considering $\kff$ is its use within an
ensemble of active-learning algorithms. The ``master'' active
algorithm we present later benefits from $\kff$ in ``XOR-like''
problems without significant compromises in problems where $\kff$
is weaker.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%55
\section{The Multi-Armed Bandit (MAB) Problem}
\label{sec:mab}

A major ingredient in our online learning approach to active
learning is a known competitive algorithm for the multi-armed
bandit problem. In this section we present this problem, its
connection to online choice of active learners and the particular
multi-armed bandit algorithm we use.

In the \textbf{\emph{multi-armed bandit (MAB) problem}}, a gambler
must choose one of $k$ non-identical slot machines to play in a
sequence of trials. Each machine can yield rewards whose
distribution is unknown to the gambler, and the gambler's goal is
to maximize his total reward over the sequence. This classic
problem represents a fundamental predicament
whose essence is the
tradeoff between \emph{exploration} and \emph{exploitation}:
Sticking with any single machine may prevent discovering a better
machine; on the other hand, continually seeking a better machine
will prevent achieving the best total reward.

We make the following straightforward analogy between the problem
of online combining of an ensemble of active learners and the MAB
problem. The $k$ active-learning algorithms in our ensemble are
the $k$ slot machines. On each trial, choosing a query generated
by one active-learning algorithm corresponds to choosing one slot
machine. The true (generalization) accuracy achieved (by the
combined algorithm) using the augmented training set (which
includes the newly queried data point) corresponds to the gain
achieved by the chosen machine. Of course, this rough analogy does
not immediately provide a solution for combining active learners.
In particular, one of the main obstacles in using MAB algorithms
for combining active learners is how to define the reward of a
query. The optimal reward might be the true accuracy achieved by
the learner using the augmented training set, however this
accuracy is unknown to us. We therefore have to estimate it in
some way. The reward estimation technique we use is developed in
Section~\ref{sec:cem}. For the rest of this section we assume we
have some (non-negative and bounded) reward function.

Most known MAB algorithms and their analyses assume that rewards
are distributed according to certain statistical models.
Typically, simple statistical models including independence and
time invariance assumptions are taken (for example, i.i.d. Gaussian
rewards). In our active-learning context (using, for example, the above
analogy), overly simplistic statistical assumptions on reward
distributions are likely to be violated. Therefore, it is
particularly useful to use, in our active-learning context, the
\emph{adversarial} MAB results of \cite{AuerCFS02}, which provide
MAB algorithms that are guaranteed to extract a total gain close
to that of the best slot machine (in hindsight) without \emph{any}
statistical assumptions. Two particular MAB algorithms
developed by \citet{AuerCFS02} are potentially useful for implementing online
choice of active learners. The first algorithm is called $\expt$
\citep[see Section~3 in][]{AuerCFS02} and directly matches the
above analogy. The second algorithm, called $\expf$ \citep[see
Section~7 in][]{AuerCFS02}, appears to be more suitable for our
purposes (see below). We first describe the $\expt$ algorithm
and then describe the $\expf$ algorithm which we have chosen to
use.

$\expt$ is an algorithm for the standard MAB game, where $n$ slot
machines are played. On each trial $t$, one slot machine $i,
i=1,\ldots,n$, is chosen and played, yielding a reward $g_i(t)$,
where $g_i(t)$ is non-negative and bounded. For a game consisting
of $T$ trials, define $G_{\gmax} = \max_{1\leq i \leq n}
\sum_{t=1}^T g_i(t)$, the expected reward of the best slot machine
in hindsight. The goal of the online player in this game is to
achieve a reward as close as possible to $G_{\gmax}$. Let
$G_{\expt}$ be the expected reward of this algorithm. The
``regret'' of $\expt$ is defined to be $G_{\gmax}-G_{\expt}$.
Given an upper bound $g \geq G_{\gmax}$, it is guaranteed
\citep{AuerCFS02} that the regret of $\expt$ is bounded above by
$$
G_{\gmax}-G_{\expt} \leq 2.63 \sqrt{gn \ln n}.
$$
This bound holds for any assignment of rewards and for any number
of trials $T$. We also note that this bound holds for
rewards in the range of $[0,1]$. In our algorithm we also used
rewards in this range (see Section~\ref{sec:comb}).

The problem of providing the upper bound $g \geq G_{\gmax}$ is
solved using a standard doubling algorithm that guesses a bound
and runs the $\expt$ algorithm until this bound is reached. Once
reached, the guessed bound is doubled and $\expt$ is restarted
with the new bound. The guaranteed bound on the regret of this
algorithm is
$$
G_{\gmax}-G_{\dblexpt} \leq 10.5 \sqrt{G_{\gmax}n \ln n} + 13.8n +
2n \ln n,
$$
where $G_{\dblexpt}$ is the expected reward of the doubling
algorithm. Once again, this bound holds for any reward function
and for any number of trials.

Combining active learners using $\expt$ can be done in the
following manner. Each one of the $n$ active-learning algorithms
in the ensemble is modelled as a slot machine. On each trial $t$,
one active learner is chosen to provide the next query. The reward
of this query is associated with the chosen learner.\footnote{The
alternative possibility of modeling the pool samples as the slot
machines clearly misses the `exploitation' dimension of the
problem since once we choose a sample, we cannot utilize it again.
In addition, it is not clear how to utilize an ensemble of
learners using this approach.} In this modeling approach, the
points are not at all considered by $\expt$ and each active
learner is a slot machine ``black box''. Thus, this approach does
not directly utilize some useful information on the unlabeled
points that may be provided by the active learners.

The other algorithm of \cite{AuerCFS02} called $\expf$ is designed
to deal with a more sophisticated MAB variant than the above
(standard) MAB game. Here the goal is to combine and utilize a
number $k$ of \emph{strategies} or \emph{experts}, each giving
``advice'' on how to play the $n$ slot machines. To employ $\expf$
in our context, we associate the $k$ experts with the ensemble of
$k$ active-learning algorithms. The slot machines are associated
with the unlabeled instances in our pool $\UUU$. Using this
approach for modeling active learning has a considerable benefit
since now the choice of the next query is directly based on the
opinions of all ensemble members.

Algorithm $\expf$ operates as follows. On each trial $t$, each
expert $j$, $j=1,\ldots,k$, provides a weighting
$\bbb^{j}(t)=(b^j_1(t),\ldots,b^j_n(t))$ with $\sum_i b^j_i(t) =
1$, where $b^j_i(t)$ represents the confidence (probability) of
expert $j$ for playing the $i$th machine, $i=1,\ldots,n$, on trial
$t$. Denoting the vector of rewards for the $n$ machines on trial
$t$ by $\ggg(t) = (g_1(t),\ldots,g_n(t))$, where $g_i(t)$ is
non-negative and bounded, the expected reward of expert $j$ on
trial $t$ is $\bbb^{j}(t) \cdot \ggg(t)$. Note that in the MAB
game only one reward from $\ggg(t)$ is revealed to the online
player after the player chooses one machine in trial $t$. For a
game consisting of $T$ trials, define $G_{\gmax} = \max_{1\leq j
\leq k} \sum_{t=1}^T \bbb^{j}(t) \cdot \ggg(t)$, the expected
reward of the best \emph{expert} in hindsight. The goal of the
online player in this game is to utilize the advice given by the
experts so as to achieve reward as close as possible to
$G_{\gmax}$. Let $G_{\expf}$ be the expected reward of this
algorithm. Given an upper bound $g \geq G_{\gmax}$, the ``regret''
of $\expf$, defined to be $G_{\gmax} - G_{\expf}$, is bounded
above by
$$
G_{\gmax}-G_{\expf} \leq 2.63 \sqrt{gn \ln k}.
$$
This regret bound holds for any number of trials $T$, provided
that one of the experts in the ensemble is the ``uniform expert,''
which always provides the uniform confidence vector for $n$
slot machines. The problem of providing the upper bound $g \geq
G_{\gmax}$ is solved by employing the same `guess and double'
technique used with $\expt$. The guaranteed bound on the regret of
this algorithm is
$$
G_{\gmax}-G_{\dblexpf} \leq 10.5 \sqrt{G_{\gmax}n \ln k} + 13.8n +
2n \ln k,
$$
where $G_{\dblexpf}$ is the expected reward of the doubling
algorithm.

As mentioned above, we use $\expf$ for active learning by
modeling the $k$ active-learning algorithms as $k$ experts and
the unlabeled pool points in $\UUU$ as the slot machines. Note
that for the performance bound of $\expf$ to hold we must include
$\rand$ in our pool of active learners, which corresponds to the
``uniform expert''. This modeling requires that expert advice
vectors are probabilistic recommendations on points in $\UUU$. It
is thus required that each algorithm in the ensemble will provide
``rating'' for the entire pool on each trial. In practice, the
three algorithms we consider naturally provide such ratings, as
discussed in Section~\ref{sec:comb}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Classification Entropy Maximization}
\label{sec:cem}

In order to utilize the MAB algorithm ($\expf$, see
Section~\ref{sec:mab}) in our context, we need to receive, after
each trial, the gain of the instance $x \in \UUU$ that was chosen
to be queried (corresponding to one slot machine). While the
ultimate reward in our context should be based on the \emph{true}
accuracy of the classifier resulting from training over $\LLL \cup
\{(x,y)\}$ (where $y$ is the label of $x$), this quantity is not
available to us. At the outset it may appear that standard error
(or accuracy) estimation methods could be useful. However, this is
not entirely the case and, unless $\LLL$ (and $\UUU$) is
sufficiently large, standard methods such as cross-validation or
leave-one-out provide substantially biased estimates of an active
learner's performance. This fact, which was already pointed out by
\cite{Schohn00less}, is a result of the biased sample acquired by
the active learner. In order to progress quickly, the learner must
focus on ``hard'' or more ``informative'' samples. Consider
Figure~\ref{fig:cem-loo} (left). The figure shows leave-one-out
(LOO) estimates of four (active) learning algorithms: $\simple$,
$\self$, $\kff$ and $\rand$ on the UCI `Ringnorm' data set. For
each training set size, each point on a curve is generated using
the LOO estimate based on the currently available labeled set
$\LLL$. In Figure~\ref{fig:cem-loo} (middle) we see the ``true
accuracy'' of these algorithms as estimated by an independent test
set. Not only does LOO severely fail to estimate the true
accuracy, it even fails to order the algorithms according to their
relative success as active learners. This unfortunate behavior is
quite typical of LOO on many data sets, and afflicts
other standard error estimation techniques, including
cross-validation. These techniques should, therefore, be avoided in
general for receiving feedback on the (relative) progress of
active learners, especially if one cares about the active
learner's performance using a small number of labeled points.

\begin{figure*}[htb!]
  \begin{center}
    \leavevmode
    \begin{tabular}{ccc}
     \epsfig{file=ringnorm-loo.eps,width=2in} &
     \epsfig{file=ringnorm-true.eps,width=2in} &
     \epsfig{file=ringnorm-cem.eps,width=2in}
    \end{tabular}
    \caption[LOO and CEM estimates of $\simple$, $\self$, $\rand$  and $\kff$ active
    learners over the `Ringnorm' data set.]
    {\textbf{Left}: LOO estimates of active-learning sessions of
    $\simple$, $\self$, $\rand$  and $\kff$ over the `Ringnorm' data set;
    \textbf{Middle}: The ``true'' accuracy of these algorithms, as estimated using a test set;
    \textbf{Right}: CEM entropy scores of these algorithms.
    All estimates are averages of 100 folds. Error bars (diluted to reduce clutter)
    represent one standard error of the mean.}
    \label{fig:cem-loo}
  \end{center}
\end{figure*}

We propose the following semi-supervised estimator, which we call
\emph{Classification Entropy Maximization (CEM)}. Define the
\emph{CEM score} of a classifier with respect to an unlabeled set
of points to be the binary entropy of the classification it
induces on the unlabeled set. Specifically, if $C$ is a binary
classifier giving values in $\{\pm1\}$, let $C^{+1}(\UUU)$ and
$C^{-1}(\UUU)$ be the `positively' and `negatively' classified
subsets of some unlabeled set $\UUU$, respectively, as determined
by $C$. Then, the CEM score of $C$ (with respect to $\UUU$) is the
binary entropy $H(\frac{|C^{+1}(\UUU)|}{|\UUU|})$.\footnote{The
binary entropy of a (Bernoulli) random variable with bias $p$ is
$H(p)=H(1-p) = -p\log(p)-(1-p)\log(1-p)$.} It is not difficult to
see that the CEM score is larger if the division of the pool
classification between classes is more balanced.
Figure~\ref{fig:cem-loo} (right) provides CEM curves for the four
active learners discussed above. Clearly, the CEM measure orders
the algorithms in accordance with their true accuracy as depicted
in Figure~\ref{fig:cem-loo} (middle), and moreover, if we ignore
the scales, all CEM curves in this example appear surprisingly
similar to the corresponding true accuracy curves. This behavior
of CEM is typical in many of our empirical examinations, and
somewhat surprisingly, CEM succeeds in correctly evaluating
performance even when the positive and negative priors are not
balanced. A more comprehensive discussion and analysis of the CEM
criterion is provided later in Section~\ref{sec:cem_analysis}.

\begin{remark}
It is interesting to note that the CEM criterion is also useful
for SVM model selection in (semi-)supervised learning settings
where the (labeled) training set is small and
some set of unlabeled points is available. In Appendix~\ref{sec:cem_passive} we
present an empirical comparison of CEM and LOO in this setting.
\end{remark}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Combining Active Learners Online}
\label{sec:comb}

In this section we describe our master algorithm for combining
active learners. The combination algorithm, called here for short
$\comb$, is based on the $\expf$ multi-armed bandit (MAB)
algorithm discussed in Section~\ref{sec:mab} and on the
CEM criterion presented in
Section~\ref{sec:cem}. In Figure~\ref{fig:comb} we provide an
annotated pseudocode of $\comb$. The algorithm utilizes an
ensemble of active-learning algorithms and tracks online the best
algorithm in the ensemble. Many of the steps in this code are
adapted from the $\expf$ MAB algorithm of \cite{AuerCFS02} (in
particular, steps 4,5,6,11,12). We refer the reader to
\cite{AuerCFS02} for a more detailed exposition (and the proof of
the performance guarantee) of $\expf$. Here we elaborate on steps
1,2,3 and 10, which require further explanation (the remaining
steps, 7,8 and 9, are self-explanatory).

\begin{figure}[htb!]
\fbox{\begin{minipage}{0.9\columnwidth} \centerline{\bf Algorithm
COMB}
\bigskip
{\small {\bf Input:} (i) A Pool $\UUU =
\{x_{1},\ldots,x_{n}\}$; (ii) An ensemble $\{\alg_j\}_{j=1}^k$ of
$k$ active learners;\\
(iii) An initial training set $\LLL_0$\\
{\bf Parameters:} (i) A probability threshold $\alpha$; (ii) A
probability scaling factor $\beta$;\\
(iii) A bound $g_{max}$ on the maximal reward \\
{\bf Init:} Initialize expert weights: $w_j=1$, $j=1,\ldots,k$ \\ \\
For $t=1,2,\ldots$
\begin{enumerate}
\item Receive advice scoring vectors from $\alg_j$,
$j=1,\ldots,k$: $\eee^j(t) = (e^j_1(t),\ldots,e^j_n(t))$.
$e^j_i(t)$ is the score of the $i$th point in the pool. The scores
are normalized to lie within [0,1]. \item For each $\alg_j$,
$j=1,\ldots,k$, we compute an advice probability vector $\bbb^j(t)
= (b^j_1(t),\ldots,b^j_n(t))$ by scaling the advice scoring
vectors. For each $\bbb^j(t)$, $j=1,\ldots,k$, for each
$b^j_i(t)$, $i=1,\ldots,n$: $b^j_i(t)=(\exp\{- \beta
(1-e^j_i(t))\}) / Z$, where $Z$ normalizes $\bbb^j(t)$ to be a
probability vector. \item Extract from $\UUU$ an ``effective
pool'' $\UUU_e$ by thresholding low probability points: For each
point $x_i \in \UUU$ leave $x_i$ in $\UUU_e$, iff $\max_j b^j_i
\geq \alpha$. If $|\UUU_e| =0$, reconstruct with $\alpha/2$, etc.
Set $n_e = |\UUU_{e}|$. \item Set $\gamma = \sqrt{\frac{n_e
\ln{k}}{(e-1) g_{max}}}$. \item Set $W = \sum_{j=1}^{k} w_{j}$ and
for $i=1,\ldots,n_e$, set $p_{i} = (1- \gamma) \sum_{j=1}^k w_{j}
b^{j}_{i}(t)/W + \gamma /n_e$. \item Randomly draw a point $x_q$
from $\UUU_e$ according to $p_1,\ldots,p_{n_e}$. \item Receive the
label $y_q$ of $x_q$ from the teacher and update the training set
and the pool: $\LLL_{t} = \LLL_{t-1} \cup \{(x_q, y_q)\}$;
$U_{t+1}=U_{t} \setminus \{x_q\}$ \item Train a classifier $C_{t}$
using $\LLL_{t}$. \item Use $C_t$ to classify all points in $\UUU$
and calculate $H_t = H_t(\frac{|C^{+1}(\UUU)|}{|\UUU|})$, the
entropy of the resulting partition $C^{+1}(\UUU), C^{-1}(\UUU)$
(as in the CEM score; see Section~\ref{sec:cem}). \item
Calculate the ``reward utility'' of $x_q$:\\
$r(x_q) = ((e^{H_t}-e^{H_{t-1}}) - (1-e))/(2e-2)$. \item For
$i=1,\ldots,n$, set $\hat{r}_i(t) = r(x_q)/p_q$ if $i=q$ and
$\hat{r}_i(t)=0$ otherwise.
\item Reward/punish experts:\\
$w_j(t+1) = w_j(t) \exp( \bbb^{j}(t) \cdot \hat{r}(t) \gamma /
n_e)$.
\end{enumerate}
}
\end{minipage}}
\caption{Algorithm $\comb$} \label{fig:comb}
\end{figure}

In steps 1 and 2, we compute advice probability vectors of the
active learners as required by the original $\expf$ algorithm.
Each algorithm in the ensemble provides (in Step~1) a scoring
vector that ``rates'' each point in the pool $\UUU$. In practice,
the three algorithms we consider naturally provide such ratings:
$\simple$ uses the kernel distance from the decision hyperplane,
$\self$ uses the expected loss and $\kff$ uses the kernel distance
from the current training set. We scale these scoring vectors (in
Step~2) using a scaling parameter $\beta$ and a Gibbs probability
function $\exp\{- \beta x\}$. In all our experiments we used
$\beta = 100$ (a sensitivity analysis of this parameter is
provided in Section~\ref{sec:results}).

In Step~3, after producing (in Step~2) the advice probability
vectors for the active learners, we project the pool $\UUU$ over
high probability candidate instances. The projected pool is
denoted $\UUU_e$. This projection is controlled by the parameter
$\alpha$ and an instance $x$ in $\UUU$ remains in $\UUU_e$ if at
least one active learner assigns to $x$ a probability mass greater
than $\alpha$. In all the experiments described below, we used
$\alpha = 0.05$ (here again, a sensitivity analysis of this
parameter is provided in Section~\ref{sec:results}).

In Step~6, the learner chooses one (unlabeled) point $x_q$ from
$\UUU_e$ as the next query. According to $\expf$, this choice
should be random according to the distribution computed in Step~5.
In practice, in the experiments described in
Section~\ref{sec:results}, we greedily picked the point with the
largest probability (and in case of ties we randomly chose one of
the points). This deterministic implementation is useful for
reducing the additional variance introduced by these random
choices.\footnote{We also experimented with random query choices,
as prescribed by $\expf$. A slight advantage of the deterministic
variant of the algorithm was observed.}

In Step~10 we calculate the ``utility'' of the last query. This
utility is defined using the (convex) function $e^x$ on the
entropic reward calculated in Step~9 (that is, the CEM score discussed
in Section~\ref{sec:cem}). The utility function is essentially the
difference
$$
\Delta_t = e^{H_t}-e^{H_{t-1}},
$$
where $H_t$ is the entropy of the last partition of $\UUU$
generated using the last queried instance in the training set.
$H_{t-1}$ is the entropy of the partition of the same pool
generated without using the last queried instance. Clearly, this
function emphasizes entropy changes in the upper range of possible
entropy values. The rationale behind this utility function is that
it is substantially harder to improve CEM scores (and also
accuracy) that are already large. The additional transformation
$(\Delta_t -(1-e))/(2e-2)$ normalizes the utility to be in [0,1].

The reward bound parameter $g_{max}$, used for setting an optimal
value for $\gamma$ (Step~4) can be and is eliminated in all our
experiments using a standard ``guess and double'' technique. In
particular we operate the $\comb$ algorithm in rounds $r=1,2,\ldots$,
where in round $r$ we set the reward limit to be $g_r =
(n_{e}\ln{k}/(e-1))4^{r}$ and restart the $\comb$ algorithm with
$g_{max}=g_{r}$. The round continues until the maximal reward
reached by one of the ensemble algorithms exceeds
$g_{r}-n_{e}/\gamma_{r}$. For more details, the reader is referred
to the discussion on the $\expto$ algorithm in Section~4 of
\cite{AuerCFS02}.

\section{Empirical Evaluation of the COMB Algorithm}
\label{sec:results}

We evaluated the performance of the $\comb$ algorithm on the entire
benchmark collection selected and used by
\cite{RatschOM01}, consisting of 13 binary
classification problems extracted from the UCI repository. For
almost all problems, this collection includes fixed 100 folds each
consisting of a fixed 60\%/40\% training/test
partition.\footnote{Two data sets in this collection (`Image' and
`Splice') include only 20 folds.} The use of this set is
particularly convenient as it allows for easier experimental
replication. To this collection we also added our artificial `XOR'
problem (see Section~\ref{sec:xor_example}).\footnote{For this
`XOR' data set, consisting of 1000 points, we constructed 100
folds by randomly and uniformly splitting the data to 25\%/75\%
training/test partitions.} Some essential characteristics of all
these data sets appear on Table~\ref{tab:datasets2}. For each
problem we specify its size, its dimension, the bias (proportion
of largest class), the maximal accuracy achieved using the entire
pool as a training set, the (rounded up) number of instances
required by the \emph{worst} learner in the ensemble to achieve
this maximal accuracy and, finally, the average fraction of
support vectors (from the entire pool size) utilized by an SVM
trained over the entire pool (this average is computed over 100
folds).

In all the experiments described below, each active learner is
provided with two initial examples (one from each class) for each
learning problem. These two examples were randomly chosen among
all possible pairs. The same initial training set (pair) was given
to all learners. All active-learning algorithms applied in our
experiments used an SVM with RBF kernel as their learning
component ($\A$). More particular implementation details, which
are essential for replication, are given in
Appendix~\ref{sec:imp_details}.

\begin{figure*}[htb!]
  \begin{center}
    \leavevmode
    \begin{tabular}{cc}
      \epsfig{file=waveform-pool.eps,width=2.8in} &
      \epsfig{file=xor-pool.eps,width=2.8in}
    \end{tabular}
    \begin{tabular}{cc}
      \epsfig{file=image-pool.eps,width=2.8in} &
      \epsfig{file=flare-pool.eps,width=2.8in}
    \end{tabular}
    \caption[Learning curves of $\comb$ and its ensemble
    members on four data sets.]
    {Learning curves of $\comb$ and its ensemble members on four data sets.
    All estimates are averages over 100 folds. Error bars (diluted to reduce clutter)
    represent one standard error of the mean.
    \textbf{Top Left}: `Waveform' data set, where $\comb$ performs almost as well as the winner $\simple$.
    \textbf{Top Right}: `XOR' data set, where $\comb$ performs better than the winner $\kff$.
    \textbf{Bottom Left}: `Image' data set, where $\comb$ performs almost as well as the winner $\self$.
    \textbf{Bottom Right}: `Flare-Solar' data set, where $\comb$ is the overall
    winner and significantly beats its ensemble members.}
    \label{fig:comb-graphs}
  \end{center}
\end{figure*}

In Figure~\ref{fig:comb-graphs} we depict the learning curves of
$\comb$ and its ensemble members obtained on four data sets. Notice
that for three of these data sets a different ensemble member is
the winner. In the `Image' data set it is $\self$, in the `XOR'
data set it is $\kff$ and in the `Waveform' data set it is
$\simple$.\footnote{In the 'Waveform' data set the accuracy
decreases from a certain point.
When there is noise in the data one may
benefit by stopping early.
See a discussion of this phenomenon by \cite{Schohn00less}.}
However, in all of these cases $\comb$
tracks the winner. In the fourth data set presented, the
`Flare-Solar' data set, $\comb$ is the overall winner and
significantly beats its three ensemble members.

\begin{table}[htb!]
\begin{footnotesize}
\begin{center}
\begin{tabular}{l||r|r|l|l|l}
  \hline
Data Set   & Size & Dim  & Bias   & Max Acc. (\%) & SV proportion (\%)\\
          &      &      &        & (Sample Size) \\\hline \hline
Banana    & 5300 & 2    & 0.551   &   88.22 (200) & 14.3 $\pm$ 0.2\\
Breast-Cancer    & 277  & 9    & 0.707   &   73.60 (100) & 45.8 $\pm$ 1.07\\
Diabetis  & 768  & 8    & 0.651   &   74.56 (220) & 38.5 $\pm$ 1.11 \\
Flare-Solar     & 1066 & 9    & 0.552   &   63.76 (200) & 15.08$\pm$ 0.4 \\
German    & 1000 & 20   & 0.700  &   75.48 (330) & 53.00 $\pm$ 0.56 \\
Heart     & 270  & 13   & 0.555  &   82.33 (82)  & 41.29 $\pm$ 0.68 \\
Image     & 2310 & 18   & 0.571  &   95.00 (500) & 46.32 $\pm$ 1.17\\
Ringnorm  & 8300 & 20   & 0.549  &   97.96 (200) & 79.0$\pm$0.3\\
Splice    & 3175 & 60   & 0.519  &   85.86 (450) & 74.1$\pm$2.13 \\
Thyroid   & 215  &  5   & 0.697  &   95.53 (69)  & 26.2$\pm$0.8\\
Titanic   & 2201 &  3   & 0.676  &   74.14 (74)  & 17.09$\pm$0.32 \\
Twonorm   & 7400 & 20   & 0.500  &   95.94 (200) & 87.45$\pm$0.81 \\
Waveform  & 5000 & 21   & 0.670  &   80.58 (200) & 97.78$\pm$0.55 \\
XOR       & 3000 & 2    & 0.500  &   96.35 (240) & 2.19$\pm$0.01\\
\hline
\end{tabular}
\end{center}
\caption[Essential data sets characteristics.] {The data sets: some
essential characteristics. For each problem we provide the size,
the dimension, the bias (proportion of largest class), the maximal
accuracy achieved using the entire pool, the (rounded up) number
of instances required by the worst learner in the ensemble to
achieve this maximal accuracy and the average fraction of the
number of support vectors (from the pool size) utilized by an SVM
trained over the entire pool (the average is computed over 100
folds).} \label{tab:datasets2}
\end{footnotesize}
\end{table}

\begin{table}[htb!]
\begin{footnotesize}
\begin{center}
\begin{tabular}{l|l|l|l|l}
  \hline
  Data Set   & $\simple$ & $\kff$ & $\self$ & $\comb$ \\
  \hline\hline
%  Banana    & $1.13(1.11-1.15)$ & $\mathbf{0.73 *}(0.72-0.73) $ & $\mathbf{0.74}(0.72-0.76)$ & $\mathbf{0.74}(0.73-0.75)$ \\
%  \hline
%  Breast-Cancer & $\mathbf{1.06}(1.04-1.08)$ & $1.28(1.26-1.32)$ & $\mathbf{0.95 *}(0.91-0.98)$ & $1.09(1.07-1.10)$ \\
%  \hline
%  Diabetis & $\mathbf{0.64}(0.59-0.68)$ & $1.07(1.04-1.09)$ & $\mathbf{0.48 *}(0.42-0.52)$ & $0.82(0.77-0.86)$ \\
%  \hline
%  Flare-Solar & $1.13(1.12-1.13)$ & $\mathbf{1.09}(1.05-1.15)$ & $1.39(1.33-1.48)$ & $\mathbf{0.79 *}(0.73-0.83)$ \\
%  \hline
%  German & $0.71(0.66-0.74)$ & $0.85(0.84-0.85)$ & $\mathbf{0.67}(0.64-0.69)$ & $\mathbf{0.64 *}(0.61-0.66)$ \\
%  \hline
%  Heart & $\mathbf{0.57}(0.54-0.60)$ & $1.04(1.04-1.05)$ & $\mathbf{0.50 *}(0.47-0.53)$ & $0.64(0.61-0.66)$ \\
%  \hline
%  Image & $0.54(0.51-0.56)$ & $0.76(0.75-0.76)$ & $\mathbf{0.45 *}(0.44-0.46)$ & $\mathbf{0.47}(0.46-0.48)$ \\
%  \hline
%  Ringnorm & $\mathbf{0.34 *}(0.33-0.36)$ & $4.70(4.34-5.14)$ & $0.38(0.37-0.38)$ & $\mathbf{0.36}(0.35-0.36)$ \\
%  \hline
%  Splice & $\mathbf{0.58}(0.58-0.59)$ & $2.54(2.44-2.67)$ & $0.60(0.59-0.60)$ & $\mathbf{0.57 *}(0.57-0.58)$ \\
%  \hline
%  Thyroid & $\mathbf{0.55}(0.54-0.56)$ & $2.34(2.26-2.45)$ & $\mathbf{0.47 *}(0.45-0.48)$ & $0.64(0.60-0.67)$ \\
%  \hline
%  Titanic & $0.76(0.70-0.79)$ & $0.92(0.90-0.94)$ & $\mathbf{0.68}(0.61-0.73)$ & $\mathbf{0.65 *}(0.58-0.69)$ \\
%  \hline
%  Twonorm & $\mathbf{0.24 *}(0.23-0.26)$ & $1.03(1.03-1.04)$ & $0.32(0.29-0.34)$ & $\mathbf{0.26}(0.24-0.27)$ \\
%  \hline
%  Waveform & $\mathbf{0.58 *}(0.52-0.63)$ & $0.97(0.97-0.98)$ & $0.66(0.62-0.70)$ & $\mathbf{0.60}(0.55-0.66)$ \\
%  \hline
%  XOR      & $1.24(1.18-1.32)$ & $\mathbf{0.63}(0.61-0.65)$ & $1.19(1.15-1.23)$ & $\mathbf{0.47 *}(0.43-0.50)$ \\
%  \hline
  Banana    & $1.13 \pm 0.02$ & $\mathbf{0.73 *} \pm 0.01 $ & $\mathbf{0.74} \pm 0.02 $ & $\mathbf{0.74} \pm 0.01 $ \\
  \hline
  Breast-Cancer & $\mathbf{1.06} \pm 0.02 $ & $1.28 \pm 0.03 $ & $\mathbf{0.95 *} \pm 0.03 $ & $1.09 \pm 0.01 $ \\
  \hline
  Diabetis & $\mathbf{0.64} \pm 0.04 $ & $1.07 \pm 0.02 $ & $\mathbf{0.48 *} \pm 0.05 $ & $0.82 \pm 0.04 $ \\
  \hline
  Flare-Solar & $1.13 \pm 0.01 $ & $\mathbf{1.09} \pm 0.05 $ & $1.39 \pm 0.07 $ & $\mathbf{0.79 *} \pm 0.05 $ \\
  \hline
  German & $0.71 \pm 0.04 $ & $0.85 \pm 0.01 $ & $\mathbf{0.67} \pm 0.02 $ & $\mathbf{0.64 *} \pm 0.02 $ \\
  \hline
  Heart & $\mathbf{0.57} \pm 0.03 $ & $1.04 \pm 0.01 $ & $\mathbf{0.50 *} \pm 0.03 $ & $0.64 \pm 0.02 $ \\
  \hline
  Image & $0.54 \pm 0.02 $ & $0.76 \pm 0.01 $ & $\mathbf{0.45 *} \pm 0.01 $ & $\mathbf{0.47} \pm 0.01 $ \\
  \hline
  Ringnorm & $\mathbf{0.34 *} \pm 0.01 $ & $4.70 \pm 0.4 $ & $0.38 \pm 0.01 $ & $\mathbf{0.36} \pm 0.01 $ \\
  \hline
  Splice & $\mathbf{0.58} \pm 0.01 $ & $2.54 \pm 0.11 $ & $0.60 \pm 0.01 $ & $\mathbf{0.57 *} \pm 0.01 $ \\
  \hline
  Thyroid & $\mathbf{0.55} \pm 0.01 $ & $2.34 \pm 0.09 $ & $\mathbf{0.47 *} \pm 0.01 $ & $0.64 \pm 0.03 $ \\
  \hline
  Titanic & $0.76 \pm 0.04 $ & $0.92 \pm 0.02 $ & $\mathbf{0.68} \pm 0.06 $ & $\mathbf{0.65 *} \pm 0.05 $ \\
  \hline
  Twonorm & $\mathbf{0.24 *} \pm 0.01 $ & $1.03 \pm 0.01 $ & $0.32 \pm 0.02 $ & $\mathbf{0.26} \pm 0.01 $ \\
  \hline
  Waveform & $\mathbf{0.58 *} \pm 0.05 $ & $0.97 \pm 0.01 $ & $0.66 \pm 0.04 $ & $\mathbf{0.60} \pm 0.05 $ \\
  \hline
  XOR      & $1.24 \pm 0.07 $ & $\mathbf{0.63} \pm 0.02 $ & $1.19 \pm 0.04 $ & $\mathbf{0.47 *} \pm 0.03 $ \\
  \hline
\end{tabular}
\end{center}
\caption[Average deficiency ($\pm$ standard error of the mean) achieved by $\comb$ and its ensemble
members.]
{Average deficiency ($\pm$ standard error of the mean)
achieved by $\comb$ and its ensemble
members. For each data set the winner appears in boldface and
is marked with a star. The runner-up appears in boldface.}
\label{tab:comb-defficiency}
\end{footnotesize}
\end{table}

Table~\ref{tab:comb-defficiency} shows the average
\emph{deficiency} of $\comb$ and its ensemble members for all
these data sets. Recall the definition of deficiency of an active
learner as given in Equation~(\ref{eq:performance}), where smaller
values represent a larger active-learning \emph{efficiency}. Each
of these averages is calculated over the corresponding 100 folds.
It is evident that none of the ensemble algorithms is consistently
outdoing all sets ($\self$, $\simple$, and $\kff$ win in 7, 4
and 3 cases, respectively). Nevertheless, $\self$ is the most
dominant algorithm, winning on half of the data sets. In many cases
$\kff$ performs poorly and it is often inferior to $\rand$.
Overall, this algorithm is significantly worse than all the other
algorithms. However, as noted above, $\kff$ usually excels in
``XOR-like'' problems (for example, `Banana', `Flare-Solar' and `XOR').

In 10 cases out of the 14 presented, $\comb$ is either the winner
or a close runner-up. In five cases out of these 10 (`Flare-Solar',
`German', `Splice', `Titanic' and `XOR') $\comb$ is the overall
winner. A striking feature of $\comb$ is that it does not suffer
from the presence of $\kff$ in the ensemble even in cases where
this algorithm is significantly worse than $\rand$, and can
clearly benefit from $\kff$ in those cases where $\kff$ excels.

In three cases (`Heart', `Thyroid' and `Breast-Cancer'), which are
among the smallest data sets, $\comb$ is not the winner and not
even the runner-up, although even in these cases it is not far
behind the winner. This behavior is reasonable because $\comb$
needs a sufficient number of trials for exploration and then a
sufficient number of trials for exploitation. There is only one
case, the `Diabetis' data set, in which $\comb$ completely failed.
A closer inspection of this case revealed that our entropy
criterion failed in the online choosing of the best ensemble
member.

We now turn to examine the possibility of using standard error
estimation techniques instead of our CEM.
In Table~\ref{tab:cv-defficiency} we compare
the deficiencies of $\comb$ using (for computing the query
rewards) both CEM and standard 10-fold cross validation (10-CV) on
the training set. The 10-CV results are obtained by running the
$\comb$ algorithm such that in Step~9 of the pseudocode in
Figure~\ref{fig:comb} we calculate the 10-CV of the current
training set $\LLL_t$.\footnote{For training sets of size smaller
than 20, we used a leave-one-out (LOO) estimator.} Denote this
quantity by $CV_t$. Then in Step~10 we used the same utility
function (applied on the CEM estimator) over the CV outcome,
$r(x_q) = ((e^{CV_t}-e^{CV_{t-1}}) - (1-e))/(2e-2)$. The table
indicates that CEM is more reliable than 10-CV as an online
estimator for active learners' performance. 10-CV is very
unreliable as it performs well in some cases and very
poorly in others. In particular, CEM beats 10-CV on 12 out of 14
data sets, where in some data sets (`Ringnorm' and `Heart' for
example) the difference is quite large. The 10-CV estimator
outperforms CEM on two data sets, `Titanic' and `Breast-Cancer',
where in the first one the difference is small.

\begin{table}[htb!]
\begin{footnotesize}
\begin{center}
\begin{tabular}{l|l|l}
  \hline
  Data Set   & $\comb$ using CEM & $\comb$ using 10-CV \\
  \hline\hline
  Banana    & $\mathbf{0.74} \pm 0.01 $ & $0.78 \pm 0.01$  \\
  \hline
  Breast-Cancer & $1.09 \pm 0.01 $ & $\mathbf{0.99} \pm 0.05$ \\
  \hline
  Diabetis & $\mathbf{0.82} \pm 0.04 $ & $0.88 \pm 0.04$ \\
  \hline
  Flare-Solar & $\mathbf{0.79} \pm 0.05 $ & $0.90 \pm 0.02$ \\
  \hline
  German & $\mathbf{0.64} \pm 0.02 $ & $0.66 \pm 0.03$ \\
  \hline
  Heart & $\mathbf{0.64} \pm 0.02 $ & $0.93 \pm 0.01$ \\
  \hline
  Image & $\mathbf{0.47} \pm 0.01 $ & $0.48 \pm 0.01$ \\
  \hline
  Ringnorm & $\mathbf{0.36} \pm 0.01 $ & $0.68 \pm 0.03$ \\
  \hline
  Splice & $\mathbf{0.57} \pm 0.01 $ & $0.63 \pm 0.01$ \\
  \hline
  Thyroid & $\mathbf{0.64} \pm 0.03 $ & $0.74 \pm 0.03$ \\
  \hline
  Titanic & $0.65 \pm 0.05$ & $\mathbf{0.61} \pm 0.05$ \\
  \hline
  Twonorm & $\mathbf{0.26} \pm 0.01 $ & $0.45 \pm 0.01$ \\
  \hline
  Waveform & $\mathbf{0.60} \pm 0.05 $ & $0.79 \pm 0.06$ \\
  \hline
  XOR      & $\mathbf{0.47} \pm 0.03 $ & $0.53 \pm 0.02$ \\
  \hline
\end{tabular}
\end{center}
\caption[$\comb$'s deficiency when operated using CEM
and 10-fold cross-validation (10-CV) for computing the query
rewards.] {$\comb$'s \emph{deficiency} when operated
using CEM and 10-fold cross-validation (10-CV) for computing the
query rewards. For each data set the winner appears in boldface.}
\label{tab:cv-defficiency}
\end{footnotesize}
\end{table}

As defined, the $\comb$ algorithm has two parameters (see
Figure~\ref{fig:comb}): the probability threshold $\alpha$, and
the probability scaling factor $\beta$. The experimental results
presented above were obtained using the assignments $\alpha =
0.05$ and $\beta = 100$. These assignments were not optimized and
in fact were a priori set to these values, which appeared
``reasonable'' to us. In the rest of this section we provide a
sensitivity analysis of these parameters. This analysis indicates
that better performance may be obtained by optimizing the $\beta$
parameter.

In Table~\ref{tab:comb-alpha} we show a comparison of $\comb$'s
performance obtained with different values of the probability
threshold parameter $\alpha$ (which determines the size of the
``effective pool'' computed in Step~3 of the pseudo-code in
Figure~\ref{fig:comb}). For the presentation here we selected the
four data sets appearing in Figure~\ref{fig:comb-graphs}. Recall
that each of the first three data sets favors (using our
``standard'' $\alpha = 0.05$ value) a different ensemble member
and in the fourth one (data set `Flare-Solar'), $\comb$
significantly beats its ensemble members. When applying $\comb$
with $\alpha=0.01,0.05,0.1$ to these four data sets, there is no
significant difference in the deficiencies demonstrated by $\comb$
(see Table~\ref{tab:comb-alpha}). This result indicates that
$\comb$ is not overly sensitive to the choices of $\alpha$ values
within this range.

\begin{table}[htb!]
\begin{footnotesize}
\begin{center}
\begin{tabular}{l|l|l|l}
  \hline
  Data Set   & $\comb$ with $\alpha=0.05$ & $\comb$ with $\alpha=0.01$ & $\comb$ with $\alpha=0.1$ \\
            &  (used in this paper)       &                            & \\
  \hline\hline
  Flare-Solar & $\mathbf{0.79} \pm 0.05$ & $0.83 \pm 0.02$ & $0.80 \pm 0.04$ \\
  \hline
  Image & $0.47 \pm 0.01$ & $0.47 \pm 0.01$ & $\mathbf{0.46} \pm 0.01$ \\
  \hline
  Waveform & $0.60 \pm 0.05$ & $\mathbf{0.59} \pm 0.05$ & $0.61 \pm 0.05$ \\
  \hline
  XOR      & $0.47 \pm 0.03$ & $\mathbf{0.45} \pm 0.03$ & $0.48 \pm 0.03$ \\
  \hline
\end{tabular}
\end{center}
\caption[$\comb$'s deficiency with different values of
the probability threshold parameter $\alpha$.] {$\comb$'s \emph{deficiency}
with different values of the probability
threshold parameter $\alpha$ (see Figure~\ref{fig:comb}). For each
data set the winner appears in boldface.} \label{tab:comb-alpha}
\end{footnotesize}
\end{table}

In Table~\ref{tab:comb-beta} we show a comparison of $\comb$
performance with three values of the probability scaling factor
parameter $\beta$ (see Step~2 in Figure~\ref{fig:comb}). Here,
again, we use the same four data sets presented in
Table~\ref{tab:comb-alpha}, to check the sensitivity of $\comb$
with respect to this $\beta$ parameter (recall that in the
experiments above we use $\beta=100$). Observing the deficiency of
$\comb$ operated with $\beta=10$ and $\beta=1000$, we see that the
performance is dependent on this parameter. However, it is clear
that the value we use in the experiments above ($\beta = 100$) was
not optimized and the table indicates that $\beta=10$ yields
better results. Hence, here there is room for further
improvements, which we have not pursued in this paper.

\begin{table}[htb!]
\begin{footnotesize}
\begin{center}
\begin{tabular}{l|l|l|l}
  \hline
  Data Set   & $\comb$ with $\beta=100$ & $\comb$ with $\beta=10$ & $\comb$ with $\beta=1000$ \\
            &  (used in this paper)    &                         & \\
  \hline\hline
  Flare-Solar & $0.79 \pm 0.05$ & $\mathbf{0.68} \pm 0.08$ & $0.80 \pm 0.04$ \\
  \hline
  Image & $0.47 \pm 0.01$ & $0.48 \pm 0.01$ & $\mathbf{0.45} \pm 0.01$ \\
  \hline
  Waveform & $\mathbf{0.60} \pm 0.05$ & $\mathbf{0.60} \pm 0.05$ & $0.63 \pm 0.05$ \\
  \hline
  XOR      & $0.47 \pm 0.03$ & $\mathbf{0.39} \pm 0.03$ & $0.67 \pm 0.02$ \\
  \hline
\end{tabular}
\end{center}
\caption[$\comb$'s deficiency with different values of
$\beta$.]{$\comb$'s \emph{deficiency} with different
values of $\beta$, the probability scaling factor parameter (see
Figure~\ref{fig:comb}). For each data set the winner appears in
boldface.} \label{tab:comb-beta}
\end{footnotesize}
\end{table}

\section{On the CEM Criterion}
\label{sec:cem_analysis}

While formal connections between CEM and generalization are
currently unknown, the rather informal discussion in this section
provides further insights into CEM and attempts to characterize
conditions for its effectiveness.

A sequence of sets $S_1,S_2,\ldots$ is called an \emph{inclusion
sequence} if $S_1 \subset S_2 \subset,\cdots$. Consider an
inclusion sequence of training sets. The sequence of training sets
generated by an active learner is an inclusion sequence in which
$S_1$ is the initial training set given to the learner. Let
$S=\{(x_1,y_1),\ldots,(x_m,y_m)\}$ be any binary labeled set of
samples where one of the classes (either $+1$ or $-1$) is a
majority and its empirical proportion is $r$ (that is, the size of
the majority class over $m$ is $r$). Consider any classifier $C$
giving the label $C(x)$ for $x \in S$. We say that the
classification $S_C = (x_1,C(x_1)),\ldots,(x_m,C(x_m))$ is
\emph{majority-biased} (with respect to $S$)  if the majority
class in $S$ is also a majority class in $S_C$ and its proportion
in $S_C$ is larger than or equal to $r$. Let $I= S_1 \subset \cdots
\subset S_T$ be an inclusion sequence of labeled samples. We say
that a \emph{learning algorithm} $\alg$ is \emph{majority-biased}
(with respect to $I$) if the classification of $S_T$ by each of
the classifiers $C_1,\ldots, C_T$ (induced by $\alg$) is
majority-biased, where $C_i$ is induced by $\alg$ using $S_i$ as a
training set.

Our main (empirical) observation is that whenever the learning
algorithm is majority biased with respect to the inclusion
sequence of training sets (generated by the learner), CEM's growth
rate corresponds to the growth rate of the true accuracy, in which
case the CEM criterion can be used to compare online the
performance of active learners. In other words, by comparing the
growth of a learner's pool classification entropy, we can get a
useful indication on the growth of the true accuracy. We next
consider a couple of examples that demonstrate this behavior and
then consider a negative example in which the majority-bias
property does not hold and CEM fails. All our examples consider a
setting in which the prior of the majority class is significantly
larger than that of the other class.

\begin{figure*}[htb!]
  \begin{center}
    \leavevmode
    \begin{tabular}{ccc}
     \epsfig{file=ring.eps,width=1.7in} &
     \epsfig{file=ring-acc.eps,width=2.1in} &
     \epsfig{file=ring-ent.eps,width=2.1in}
    \end{tabular}
    \caption[CEM estimates for $\kff$,
    $\simple$, $\self$ and $\rand$ on a synthetic `Ring' data set.]
    { \textbf{Left}: A synthetic `Ring' problem consisting of 3500 points,
    90\% (3150 circles) in the
    large `ring' cluster, and 10\% equally divided over the
    five small clusters (70 squares in each cluster);
    1500 points were taken (uniformly at random) to form the pool and
    the rest form the test set.
    \textbf{Middle}: True accuracy curves of four active learners - $\kff$,
    $\simple$, $\self$ and $\rand$ on this `Ring' data set as estimated on an independent test set.
    \textbf{Right}: Corresponding pool classification entropies
    (CEM values) of these four learners.
    All estimates are averages of 100 folds. Error bars (diluted to reduce clutter)
    represent one standard error of the mean.}
    \label{fig:ring-acc-ent}
  \end{center}
\end{figure*}

\begin{figure*}[htb!]
  \begin{center}
    \leavevmode
    \begin{tabular}{cc}
     \epsfig{file=ring_kff30.eps,width=2in} &
     \epsfig{file=ring_simple30.eps,width=2in} \\
          ($\kff$) & ($\simple$)
    \end{tabular}
    \begin{tabular}{cc}
     \epsfig{file=ring_self30.eps,width=2in} &
     \epsfig{file=ring_rand30.eps,width=2in} \\
          ($\self$) & ($\rand$)
    \end{tabular}
    \caption[Decision boundaries
    generated by $\kff$, $\simple$, $\self$ and $\rand$ using 30 queries
    on a synthetic `Ring' data set.]
    {Decision boundaries
    generated by four active learners using 30 queries on the
    `Ring' example of Figure~\ref{fig:ring-acc-ent} (left).
    The 30 queries are darker than the pool points.}
    \label{fig:ring_4}
  \end{center}
\end{figure*}

Figure~\ref{fig:ring-acc-ent} (left) depicts a synthetic `Ring'
learning problem whose majority class is the `ring' (blue circles)
and its other (minority) class consists of the five small clusters
(red squares). The class proportion in this data set is $r=0.9$ for
the `ring' majority class. We ran the four active learners on this
data set. Consider Figure~\ref{fig:ring_4} showing the pool
classification (decision boundaries) and the training sets chosen
by these four learners after 30 active-learning iterations. In
this example all pool classifications are majority-biased.
Intuitively, the progress of an active learner corresponds to how
fast the learner discovers the small clusters and their
boundaries. The better active learner, $\kff$, discovered all five
red clusters while the second best learner, $\simple$, has found
four. $\self$ has found only three clusters, and $\rand$ found two. We can
see a clear correspondence between the pool classification entropy
(CEM) and the true accuracy of the learners. Fast exploration of
the minority class clusters corresponds to fast entropy
maximization as well as fast learning (generalization).

The graphs in Figure~\ref{fig:ring-acc-ent} (middle) plot the true
accuracy of the learners as estimated using an independent test
set. The graphs in Figure~\ref{fig:ring-acc-ent} (right) represent
the corresponding pool classification entropies (CEM values). The
striking similarity between these curves is further exhibited in
Table~\ref{tab:ring} giving the performance of each of the four
active learners after 30 queries. Specifically, the table provides
for each learner:
\begin{itemize}
\item[(i)] The proportion of the majority class in the training
subset (consisting of 30 samples). We call this the ``training
proportion''. \item[(ii)] The proportion of the majority class in
the pool classification (generated by the classifier trained over
the 30 samples). We call this the ``pool proportion''.
\item[(iii)] The CEM value (entropy) of the pool classification.
\item[(iv)] The ``true'' accuracy estimated on an independent test
set.
\end{itemize}
As usual, all these numbers are averages over 100 random folds.

\begin{table}[htb!!]
\begin{footnotesize}
\begin{center}
\begin{tabular}{l||r|r|r|r}
  \hline
 & $\rand$ & $\simple$  & $\kff$ &$\self$\\
\hline\hline
Training Proportion               & 86.38 $\pm$ 0.53 & 51.88 $\pm$ 0.24 & 66.06 $\pm$ 0.37 & 37.91 $\pm$ 0.66 \\
Pool Proportion                   & 97.46 $\pm$ 0.21 & 92.75 $\pm$ 0.20 & 92.05 $\pm$ 0.07 & 93.54 $\pm$ 0.24 \\
Pool Classification Entropy (CEM) & 0.14  $\pm$ 0.01 & 0.34  $\pm$ 0.01 & 0.38  $\pm$ 0.01 & 0.29  $\pm$ 0.01 \\
True Accuracy                     & 92.39 $\pm$ 0.23 & 97.15 $\pm$ 0.19 & 97.80 $\pm$ 0.05 & 96.09 $\pm$ 0.25 \\
\hline
\end{tabular}
\end{center}
\caption[Characterization of the state and progress of $\rand$,
$\simple$, $\kff$ and $\self$ after querying 30 samples from the
pool of the synthetic `Ring' data set.] { Characterization of the
state and progress of four active learners after querying 30
samples from the pool of the `Ring' data set given in
Figure~\ref{fig:ring-acc-ent} (left). Each entry provides the mean
(over 100 random folds) and the standard error of this mean.}
\label{tab:ring}
\end{footnotesize}
\end{table}

Although in this example the true proportion of the majority class
is $r=0.9$, some of the learners exhibited a significantly smaller
training proportion (for example, $\simple$ sampled almost equally from
both classes, and $\self$ even favored the minority class). The
SVMs, which were induced using these minority-biased training sets,
have still generated a \emph{majority}-biased classification. In
particular, all generated pool proportions are larger than 0.9. We
note that this behavior is typical of SVM inducers but not of
other learning algorithms.\footnote{When running C4.5, 5-Nearest
Neighbor and Bayes Point Machine (using a kernel perceptron for
sampling) on these same samples, the pool proportions obtained are
significantly minority-biased.} Clearly, this example shows that
the CEM criterion (as measured by the pool proportion) correctly
ranks the true accuracy of these four learners.

\begin{figure*}[htb!]
  \begin{center}
    \leavevmode
    \begin{tabular}{ccc}
     \epsfig{file=sat.eps,width=1.7in} &
     \epsfig{file=sat-acc.eps,width=2.1in} &
     \epsfig{file=sat-ent.eps,width=2.1in}
    \end{tabular}
    \caption[CEM estimates for $\kff$, $\simple$, $\self$ and $\rand$
    on a synthetic `Satellites' data set.]
    { \textbf{Left}: The `Satellites' data set consisting of 3500 points, 10\%
    (350 circles) in the
    ring ``cluster'' and 90\% equally divided between
    the five large round clusters
    (630 squares in each cluster); 1500 points were taken (randomly)
    to form the pool and the rest form the test set.
    \textbf{Middle}: True accuracy of four active learners - $\kff$, $\simple$, $\self$
    and $\rand$ on this `Satellites' data set as estimated using an independent test set.
    \textbf{Right}: Corresponding pool classification entropies of these four learners.
    All estimates are averages of 100 folds. Error bars (diluted to reduce clutter)
    represent one standard error of the mean.}
    \label{fig:sat-acc-ent}
  \end{center}
\end{figure*}

\begin{figure*}[htb!]
  \begin{center}
    \leavevmode
    \begin{tabular}{cc}
     \epsfig{file=sat_kff30.eps,width=2.1in} &
     \epsfig{file=sat_simple30.eps,width=2.1in} \\
          ($\kff$) & ($\simple$)
    \end{tabular}
    \begin{tabular}{cc}
     \epsfig{file=sat_self30.eps,width=2.1in} &
     \epsfig{file=sat_rand30.eps,width=2.1in} \\
          ($\self$) & ($\rand$)
    \end{tabular}
    \caption[Decision boundaries
    generated by $\kff$, $\simple$, $\self$ and $\rand$ using 30 queries
    on a synthetic `Satellites' data set.]
    { Decision boundaries
    generated by four active learners using 30 queries on the
    `Satellites' example of Figure~\ref{fig:sat-acc-ent} (left).
    The 30 queries are darker than the pool points.}
    \label{fig:sat_4}
  \end{center}
\end{figure*}

Our next example is shown in Figure~\ref{fig:sat-acc-ent} (left).
This example can be viewed as an ``inverse'' of the `Ring'
data set of Figure~\ref{fig:ring-acc-ent}.
This data set, called here the `Satellites' data set, contains five clusters
from the majority class (squares) and one small cluster from the
minority class (circles). The class proportion in this
data set is also $r=0.9$.

\begin{table}[htb!]
\begin{footnotesize}
\begin{center}
\begin{tabular}{l||r|r|l|l}
\hline
Data Set `Satellites' & $\rand$ & $\simple$ & $\kff$ &$\self$\\
\hline\hline
Training Proportion               & 87.23 $\pm$ 0.52 & 50.97 $\pm$ 0.29 & 74.97 $\pm$ 0.30 & 45.19 $\pm$ 0.06 \\
Pool Proportion                   & 98.33 $\pm$ 0.33 & 92.42 $\pm$ 0.28 & 96.67 $\pm$ 0.20 & 95.28 $\pm$ 0.17 \\
Pool Classification Entropy (CEM) & 0.08  $\pm$ 0.01 & 0.35  $\pm$ 0.01 & 0.18  $\pm$ 0.01 & 0.22  $\pm$ 0.01 \\
True Accuracy                     & 90.81 $\pm$ 0.19 & 94.18 $\pm$ 0.28 & 92.80 $\pm$ 0.19 & 92.83 $\pm$ 0.10 \\
\hline
\end{tabular}
\end{center}
\caption[Characterization of the state and progress of $\rand$,
$\simple$, $\kff$ and $\self$ after querying 30 samples from the
pool of the synthetic `Satellites' data set.]{ Characterization of
the state and progress of four active learners after querying 30
samples from the pool of the `Satellites' data set of
Figure~\ref{fig:sat-acc-ent} (left). Each entry provides the mean
(over 100 random folds) and the standard error of the mean.}
\label{tab:sat}
\end{footnotesize}
\end{table}

As in the previous example, Figure~\ref{fig:sat_4} shows the
decision boundaries obtained by the four active learners.
Similarly, the learning curves in Figure~\ref{fig:sat-acc-ent}
show the true accuracy (middle) and CEM values (right) and
Table~\ref{tab:sat} is similar to Table~\ref{tab:ring} of the `Ring'
data set. As in the `Ring' data set, all pool classifications are
majority-biased. However, in contrast to the `Ring' example, where
good performance corresponds to quickly finding the minority
clusters, in this example good performance should correspond to
quickly finding the boundaries of the single minority cluster. The
better active learner, now $\simple$, has mapped more rapidly more
areas of the minority cluster than the other learners. Note that
$\rand$ treats the entire minority class points as noise. Once
again we can see a clear correspondence between the pool
classification entropy (CEM) and the true accuracy of the learners
where now fast exploration of the minority cluster boundaries
corresponds to fast entropy maximization as well as fast learning
(generalization).

Here again, although the true proportion is 0.9, some of the learners
exhibited a significantly smaller training proportion and still the
SVMs, which were induced using these training sets, have generated a
majority-biased classification.\footnote{In this example as well,
the C4.5, 5-Nearest Neighbor and Bayes Point Machine learning
algorithms were not majority-biased.} This example also shows
that the CEM criterion correctly identifies the true accuracy of these
four learners (where the best learner is $\simple$, followed by
$\self$, $\kff$ and $\rand$).

Our last example is shown on the left-hand side of
Figure~\ref{fig:concentric}, is referred to as `Concentric-Rings'. This
data set consists of one very large and one very small ring
clusters with a small ring cluster between them. This
example considers a case where the learning algorithm (SVM) is not
majority-biased with respect to a particular inclusion sequence
(generated by the $\simple$ querying function). In this example,
the increase in the CEM criterion does not match the increase in
true accuracy. This happens when the estimated pool entropy at
some point is larger than the true entropy $H(r)$ so that the
estimated entropy must eventually decrease to its true level while
the generalization accuracy can simultaneously improve.

% cemCircle4.arff
\begin{figure*}[htb!]
  \begin{center}
    \leavevmode
    \begin{tabular}{cc}
     \epsfig{file=concentric.eps,width=2.2in} &
     \epsfig{file=concentric_simple20.eps,width=2.3in}
    \end{tabular}
    \caption[Decision boundary
    generated by $\simple$ using 20 queries
    on a synthetic `Concentric-Rings' data set.]
    { \textbf{Left}: The `Concentric-Rings' problem consists
    of 3500 points, 10\% (350 points) in the inner ring ``cluster'',
    2\% (70 points) in the small round cluster in the middle, and
    the rest in the big outer ring ``cluster''; one class consists of all the
    points in the inner ring (consisting of circles) and the other
    class is the union of the small round middle  cluster and the outer
    ring (both consisting of squares); 1500 points form
    the pool and the rest form the test set.
    \textbf{Right}: Decision boundary
    generated by $\simple$ using 20 queries on this problem.
    The 20 queries are darker than the pool points.}
    \label{fig:concentric}
  \end{center}
\end{figure*}

In Figure~\ref{fig:concentric} (right) we observe $\simple$'s decision boundary
after 20 queries. This boundary misclassifies the small central cluster and
therefore favors the minority class. The pool classification entropy in this case is
larger than its final entropy $H(0.9)$. Clearly, when the central cluster is
discovered, the entropy will decrease but the true accuracy will increase. Note that
the size of the central (isolated) cluster is related to its discovery rate; that
is, larger clusters should be discovered faster by a good active learner. In the
above example, even one point from this cluster will immediately change the pool
classification to be majority-biased. In general, as motivated by this example,
whenever a learning algorithm is \emph{minority}-biased (with respect to some
inclusion sequence) the CEM criterion will fail in the sense that the entropy will
not correspond to the true accuracy.

Summarizing the above discussion and considering the experimental
results of Section~\ref{sec:results}, we observe that the success
of the CEM criterion depends on the properties of both the data set
and the learning algorithm. It appears that data sets with isolated
``clusters,'' whose total proportion is small, will more easily
allow for the generation of inclusion sequences of training sets
for which the learning algorithm will be \emph{minority}-biased.
The dependency of CEM on the learning algorithm can be
(intuitively) tied to \emph{algorithmic stability}. For example,
if a learning algorithm is ``stable'' and it is majority-biased
over a prefix of some inclusion sequence of training sets, then it
is likely that the stability of the algorithm will prevent the
generation of classifiers which are minority-biased. Thus, we
speculate that the success of CEM in our context is tied to  the
algorithmic stability of SVMs
\citep[see, for example,][]{BousquetE02,KutinN02}. On the other hand, our limited
experiments with other, not so stable learning algorithms, such as
C4.5, suggests that their CEM estimates
are not accurate.

Let us now go back to the `Concentric-Rings' data set where the SVM
was not majority-biased on the inclusion sequence of training sets
produced by $\simple$. The reason for $\simple$'s minority-biased
classification is that the training set does not include points
from the very small isolated cluster belonging to the majority
class, but this training set does include points from the minority
class ``surrounding'' the small cluster. The consequence of this
configuration is that the classifier will misclassify the majority
class small cluster. This problem can be circumvented by including
in the training set at least one point from the majority class
small cluster. Formulating this setup we can bound the probability
that this configuration will occur due to a random choice of an
initial training set of size $k$ (instead of our ``standard''
choice of a training set of size two; see
Section~\ref{sec:active_learning}). Let $n$ be the total number of
points in the pool. Let $n_{maj}$ be the number of points in a
small cluster from the majority class. Let $n_{min}$ be the number
of points in a subset of points from the minority class
surrounding that small cluster. The classifier (SVM) will
misclassify the small cluster if the resulting training set does
not include any point from that cluster and  at the same time will
include at least two points from the minority class subset (to
induce two support vectors that will guarantee the wrong
classification of the small cluster). Thus, using $(1-x)^z \leq
e^{-zx}$, the probability $\rho$ of choosing such a random
training set satisfies
\begin{equation}
\label{eq:rho} \rho \leq
(\frac{n_{min}}{n})^{2}(1-\frac{n_{maj}}{n})^{k-2} \leq
(\frac{n_{min}}{n})^{2}\exp\{-(k-2)(\frac{n_{maj}}{n})\}.
\end{equation}
Assuming that the bound (\ref{eq:rho}) is smaller than $\delta$ we solve for
$k$:
\begin{align}
&(\frac{n_{min}}{n})^{2}\exp\left\{-(k-2)\frac{n_{maj}}{n}\right\}
\leq \delta
\nonumber\\
\Leftrightarrow \ \ \
&2\ln{\frac{n_{min}}{n}}-(k-2)\frac{n_{maj}}{n} \leq \ln{\delta}
\nonumber\\
\Leftrightarrow \ \ \ &n_{maj}(k-2) \geq
2n\ln\frac{n_{min}}{n}-n\ln{\delta}
\nonumber\\
\Leftrightarrow \ \ \ &k \geq 2 +
2\frac{n}{n_{maj}}\ln\left(\frac{n_{min}}{n}\right)-\frac{n}{n_{maj}}\ln{\delta}
\nonumber\\
\Leftrightarrow \ \ \ &k \geq 2 +
\frac{n}{n_{maj}}\ln\left(\left(\frac{n_{min}}{n}\right)^{2} /
\delta \right). \label{eq:k_bound}
\end{align}
Thus, with probability at least $1-\delta$, if we choose a random
initial training set of size $k$, the above ``bad'' configuration
will not occur. In particular, if the argument of the `$\ln$' in
(\ref{eq:k_bound}) is smaller than $1$, it is sufficient to take
$k=2$. For example, taking $\delta = 0.01$, we have
$(\frac{n_{min}}{n})^{2} / \delta = 1$ when $n_{min}$ is 10\% of
the data.

In summary, the above discussion indicates that when sampling more
points to be in the initial training set provided to an active
learner (based on SVMs), the CEM criterion will not fail with high
confidence.

\begin{remark}
The CEM estimator can be derived using the Information Bottleneck
framework \citep{TishbyPB99} as follows.\footnote{In fact, we
discovered CEM using this framework.} If $X$  is a random variable
representing the data and  $Y$ is another \emph{target} variable,
the information bottleneck method computes a partition $T$ of $X$,
while attempting to conserve as much as possible from the
information $X$  contains on  $Y$. Formally, one seeks $T$ such
that the mutual information $I(T;Y)$ is maximized under some
constraint on the magnitude of $I(X,T)$.\footnote{In particular,
in standard applications of the information bottleneck method,
$I(X,T)$ is forced to be sufficiently small so as to achieve
\emph{compression}; see \citet{TishbyPB99} for details.} The CEM
estimator can be derived by applying the information bottleneck
principle with the target variable  $Y$ being the data  $X$
itself. In our context,  $T$ is always a binary classification
(that is, a binary partition of $X$  into two non-intersecting
subsets), $T=(t^{+},t^{-})$  (with $X = t^{+} \cup t^{-}$), which
must be \emph{consistent} with the current training set $\LLL$.
Therefore, we would like to give higher ``scores'' for
(consistent) partitions $T$ that have higher information content
$I(T,X)$ on the data. Consider a data set of size $n$. Assuming a
uniform prior over the samples (that is, $p(x) = 1/n$) and noting that
$p(t)=|t|/n$ and that $p(x|t) = 1/|t|$ if $x \in t$ (and $p(x|t)=0$
otherwise), we have $p(x,t) = p(x|t) p(t) = 1/n$ if $x \in t$ and 0
otherwise. Thus, for any partition $T=(t^{+},t^{-})$,
\begin{eqnarray*}
I(T;X) &=& \sum_{x \in X, t\in T} p(x,t)\log\frac{p(x,t)}{p(x)p(t)}\\
&=&\sum_{x \in t^{+}} \frac{1}{n} \log \frac{n}{|t^{+}|}
   + \sum_{x \in t^{-}} \frac{1}{n} \log \frac{n}{|t^{-}|}\\
&=& - \frac{|t^{+}|}{n}\log \frac{|t^{+}|}{n} -
    \frac{|t^{-}|}{n}\log \frac{|t^{-}|}{n} = H(T).
\end{eqnarray*}
\end{remark}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Concluding Remarks}
We presented an online algorithm that effectively combines an
ensemble of active learners. The algorithm successfully utilizes
elements from both statistical learning and online (adversarial)
learning. Extensive empirical results strongly indicate that our
algorithm can track the best algorithm in the ensemble on real
world problems. Quite surprisingly, our algorithm can quite often
outperform the best ensemble member. Practitioners can
significantly benefit from our new algorithm in situations where
not much is known about the classification problem at hand.

Some questions require further investigation. In our experience,
the `classification entropy maximization (CEM)' semi-supervised
criterion for tracking active-learning progress outperforms
standard error estimation techniques. Further studies of this
overly simple but effective criterion may be revealing. It would
also be interesting to examine alternative (semi-supervised)
estimators. Farther improvements to our master algorithm may be
achieved by developing MAB bounds which depend on the game
duration. Such bounds can help in controlling the tradeoff between
exploration and exploitation when using very small data sets.
Finally, it would be interesting to extend our techniques to
multi-valued classification problems (rather than binary) and to
other learning tasks such as regression.


\section*{Acknowledgments}
We thank Ron Meir and Ran Bachrach for useful discussions. We also thank Simon Tong
for providing essential information for reproducing the results of \cite{TongK2001}.
The work of R. El-Yaniv was partially
supported by the Technion V.P.R. Fund for the Promotion of Sponsored
Research.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\appendix
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Some Implementation Details}
\label{sec:imp_details}

In this appendix we provide some particular implementation details
which are essential for replication.

We operated all our SVMs using a kernel correction method
discussed by \cite{Shaw-TaylorC02}, which guarantees that the
training set is linearly separable in kernel space as required by
algorithms like $\simple$. Specifically, this is done by modifying
the kernel $K$ so that for each training point $x_i$, the modified
kernel $K'$ is $K'(x_i,x_i) = K(x_i,x_i) + \lambda$ where
$\lambda$ is a positive constant, and for all other arguments the
kernel remains the same. In all the experiments described in this
paper we took a fixed $\lambda=2$.\footnote{This value was crudely
chosen to guarantee zero training error (without test error
optimization).}

The RBF kernel has one parameter. In the SVM implementation we
used \citep{Chang02} this parameter is denoted by $\gamma$. To
obtain high performance it is crucial to use appropriate values of
$\gamma$. This issue of model (and parameter) selection is not the
main concern of our work. We therefore assume that all of our SVM
based active learners have reasonably good parameters and all
learners have the same parameters.\footnote{For each learning
problem different $\gamma$ values were selected for each fold by
randomly splitting the training set in half.  One half  was used
as the pool for the active learner. The other half was used for
choosing the value of $\gamma$ out of a fixed grid of $\gamma$
values using 10-fold cross validation.}

We have normalized each feature to lie in [-1,1] as
recommended by \cite{Chang02}. We have also used a standard
method to ``eliminate'' the bias term by increasing the input
dimension by one with a fixed component.

In noisy settings, active learners such as $\simple$ tend to be
very unstable at the early stages of the learning process. A
description of this phenomenon and a proposed solution are
described in Appendix~\ref{sec:stabling}. The proposed solution is based
on ``buffering'' labeled examples obtained from the learner and
postponing the inclusion of buffered points in the training set.
The buffer size we used in all our experiments is 3.

\section{Semi-Supervised SVM Model Selection Using CEM}
\label{sec:cem_passive}

Here we briefly describe some numerical examples of using the CEM
criterion of Section~\ref{sec:cem} as a model selection criterion
for choosing the kernel parameters of an SVM (using the RBF
kernel). Consider the following semi-supervised binary classification setting. We
are given a small training set (for example, containing 20 instances) and
a larger pool of unlabeled samples. Our goal is to to train an SVM
classifier for the classification problem at hand. Clearly, bad
parameter assignment for the SVM kernel will result in poor
performance. The kernel parameters can of course be chosen using
standard methods such as cross-validation or leave-one-out (LOO).
Here we show that the CEM criterion can do slightly better than
leave-one-out (and cross-validation) without computation time
compromises. We emphasize that this appendix only concerns the CEM
criterion and does not discuss active learning.

We applied CEM and LOO on the entire benchmark data set collection
of \cite{RatschOM01} as described in Table~\ref{tab:datasets2}. Our
experimental design is as follows. In all data sets we used an SVM
inducer with an RBF kernel. The only relevant parameter for this
kernel is $\gamma$, which determines the RBF kernel
resolution.\footnote{Since we use the kernel correction ``trick''
mentioned above, our training sets are guaranteed to be linearly
separable in feature space so there is no need to consider a soft
margin cost parameter.} We fixed a crude feasible set of $\gamma$
values for all the data sets. This set is $\Gamma
=\{0.01,0.05,0.1,0.5,1.0,5.0\}$. Let $F$ be a training fold
partition (that is, one of the fixed 100 train/test folds in the
original benchmark set) consisting of two parts: $F_{train}$  and
$F_{test}$. For each fold we performed the following procedure:
\begin{enumerate}
\item We randomly selected 20 instances from $F_{train}$ and
designated them as the (labeled) training part $S$, denoting the
rest of the instances in  $F_{train}$ by $U$. The labels of
instances in $U$ were kept hidden from both LOO and CEM (and
clearly, in all cases neither LOO nor CEM see any instance from
$F_{test}$). \item For each  $\gamma \in \Gamma$ we applied LOO
and CEM. For LOO this means training 20 classifiers, such that
each classifier is trained on different 19 examples from $S$,
tested on the other example and we count success percentage of
these 20 classifiers. For CEM this means training one classifier
over $S$ and then computing the entropy of the resulting partition
with respect to $U$. \item LOO and CEM then choose their best
candidate $\gamma \in \Gamma$. For LOO this means taking the
parameter corresponding to the highest average precision,
 and for CEM, taking the parameter corresponding to the maximal entropy.
\item Two SVMs with the winning parameters (one for LOO and one
for CEM) are then trained over $S$ and the corresponding
classifiers are tested on $F_{test}$.
\end{enumerate}
In order to get a correct perspective on the performance of LOO
and CEM we also computed the performance of the best and worst
models in hindsight. Specifically, for each $\gamma \in \Gamma$ we
computed the resulting accuracy over $F_{test}$ of the
corresponding SVM (which was trained with $\gamma$ on  $S$). The
results of this procedure are given in Table~\ref{tab:cem-loo}.
Each row of the table corresponds to one data set (among the 13)
and the accuracy results for each of the methods is specified;
that is, the SVM employing the best parameter value obtained for
LOO and CEM. Note that each number in the table is an average over
100 folds and standard errors of the means are specified as well.

The first striking observation is that both LOO and CEM perform
quite well. In particular, based on a tiny training set both
estimators achieve performance quite close to the best possible.
Second, it is evident that CEM outperforms LOO. Experiments we
performed with other training set sizes show that the relative
advantage of CEM increases as the training set size decreases.
When the training set size increases CEM's advantage over LOO
eventually disappears. For instance, when the sample size is 40,
LOO becomes more reliable and slightly outperforms CEM. Similar
results were obtained when instead of LOO we used $k$-fold
cross-validation with ``standard'' values of $k$ (for example, $k=3,4,5$).

\begin{table}[htb]
\begin{footnotesize}
\begin{center}
\begin{tabular}{l||l|l||l|l}
  \hline
Data set & Best Possible & Worst Possible & LOO      & CEM      \\
         & Accuracy      & Accuracy       & Accuracy & Accuracy \\
\hline \hline
Banana        & 71.66$\pm$0.66 & 50.26+-0.51 & \textbf{66.03$\pm$1.13} & 65.98$\pm$0.97 \\
Breast-Cancer & 72.05$\pm$0.51 & 67.16+-0.85 & \textbf{69.83$\pm$0.58} & 69.69$\pm$0.60 \\
Diabetis      & 68.44$\pm$0.36 & 63.26+-0.67 & 66.06$\pm$0.55 & \textbf{67.39$\pm$0.34} \\
Flare-Solar   & 63.96$\pm$0.42 & 59.00+-0.60 & 62.04$\pm$0.52 & \textbf{62.94$\pm$0.45} \\
German        & 70.43$\pm$0.38 & 68.23+-0.67 & 69.35$\pm$0.49 & \textbf{69.48$\pm$0.40} \\
Heart         & 75.11$\pm$0.82 & 53.12+-0.62 & 71.59$\pm$0.11 & \textbf{74.2 $\pm$0.8}  \\
Image         & 69.69$\pm$1.33 & 55.27+-1.04 & 64.51$\pm$1.71 & \textbf{68.40$\pm$1.40} \\
Ringnorm      & 90.35$\pm$1.1  & 53.66+-0.76 & 88.97$\pm$1.21 & \textbf{89.66$\pm$1.1}  \\
Splice        & 55.56$\pm$1.48 & 49.40+-0.49 & 52.86$\pm$1.3  & \textbf{55.46$\pm$1.44} \\
Thyroid       & 89.76$\pm$0.73 & 70.21+-0.61 & 85.73$\pm$0.94 & \textbf{89.56$\pm$0.75} \\
Titanic       & 71.32$\pm$0.82 & 63.02+-1.08 & \textbf{67.41$\pm$1.07} & 64.65$\pm$1.1  \\
Twonorm       & 88.09$\pm$1.09 & 54.11+-0.86 & 86.45$\pm$1.35 & \textbf{88.01$\pm$1.08} \\
Waveform      & 76.73$\pm$0.73 & 65.56+-0.86 & 73.69$\pm$0.87 & \textbf{76.58$\pm$0.72} \\
\hline Averages & 74.08  & 59.40 & 71.11 & \textbf{72.46}
\\ \hline
\end{tabular}
\end{center}
\caption[Average accuracy achieved by CEM and LOO estimators on 13
UCI problems.]
{Average accuracy (and its standard error) achieved
by Classification Entropy Maximization (CEM) and Leave-one-out
(LOO) estimators on the 13 UCI problems of \cite{RatschOM01}. For
each data set, the winner (among CEM and LOO) appears in boldface.
The accuracy of the best and worst possible models (in hindsight)
are also given.} \label{tab:cem-loo}
\end{footnotesize}
\end{table}

\section{Stabling Active Learner Performance}
\label{sec:stabling}

As mentioned above \citep[and following][]{TongK2001} we use the
kernel correction method of \cite{Shaw-TaylorC02}. This
correction guarantees linear separability in feature space, which
guarantees the existence of the version space. However, the use of
this correction, can introduce severe classification instability
in early stages of the an active-learning process (for active
learners such as $\simple$) when learning noisy data sets. In this
appendix we briefly present this problem and propose a simple
solution based on ``buffering''.

This kernel correction of \cite{Shaw-TaylorC02} works by adding a constant to the diagonal
of the kernel matrix, thus providing extra (additive) bias to the
classification of the training points. One main effect of this
correction is that all training points are correctly classified.
This correction introduces discontinuities in the decision
boundary.

\begin{figure*}[htb!]
  \begin{center}
  \leavevmode
  \begin{tabular}{cc}
    \epsfig{file=norm11.eps,width=1.7in} &
    \epsfig{file=norm11acc.eps,width=2.1in}
  \end{tabular}
    \caption[Learning curves of $\simple$ and enhanced $\simple$ (via buffering) on the
    `Twonorm2D' data set.]
    {\textbf{Left}: Data Set `Twonorm2D' that was created by projecting the
    UCI `Twonorm' data set to two dimensions. This data set
    demonstrates the unstable general behavior of active learners
    during early stages of the learning session.
    \textbf{Right}: Learning curves of $\simple$ and enhanced $\simple$ (via buffering) on the
    `Twonorm2D' data set.}
\label{fig:norm11acc}
\end{center}
\end{figure*}

\begin{figure*}[htb!]
  \begin{center}
    \leavevmode
    \begin{tabular}{ccc}
     \epsfig{file=norm11_bad4.eps,width=2.1in} &
     \epsfig{file=norm11_bad5.eps,width=2.1in} &
     \epsfig{file=norm11_bad6.eps,width=2.1in}\\
     (4) & (5) & (6)
    \end{tabular}
    \begin{tabular}{cc}
     \epsfig{file=norm11_bad7.eps,width=2.1in} &
     \epsfig{file=norm11_bad8.eps,width=2.1in}\\
     (7) & (8)
    \end{tabular}
    \caption[Pool classification and training sets generated by the
    $\simple$ active learner after 4-8 iterations on the
    `Twonorm2D' data set.]
    { Pool classification
    and training sets (blackened points) generated by the
    $\simple$ active learner after 4-8 iterations on the
    `Twonorm2D' data set.}
  \label{fig:norm11bad}
  \end{center}
\end{figure*}

\begin{figure*}[htb!]
  \begin{center}
    \leavevmode
    \begin{tabular}{ccc}
     \epsfig{file=norm11_good4.eps,width=2.1in} &
     \epsfig{file=norm11_good5.eps,width=2.1in} &
     \epsfig{file=norm11_good6.eps,width=2.1in} \\
          (4) & (5) & (6)
    \end{tabular}
    \begin{tabular}{cc}
     \epsfig{file=norm11_good7.eps,width=2.1in} &
     \epsfig{file=norm11_good8.eps,width=2.1in} \\
          (7) & (8)
    \end{tabular}
    \caption[Pool classification and training sets generated by the
    enhanced $\simple$ active learner after 4-8 iterations on the
    `Twonorm2D' data set.]
    { Pool classification
    and training sets (blackened points) generated by the
    \textbf{\emph{enhanced}} $\simple$ active learner after 4-8 iterations on the
    `Twonorm2D' data set.}
  \label{fig:norm11good}
  \end{center}
\end{figure*}

Consider the example in  Figure~\ref{fig:norm11acc} (left) showing
a 2D projection of the `Twonorm' data set (see the details of
this data set in Table~\ref{tab:datasets2}).
Figure~\ref{fig:norm11bad} shows the pool classification and the
training sets generated by the $\simple$ active learner after 4-8
iterations. The decision boundary changes drastically from one
iteration to another. Note that the above kernel ``correction''
enables a correct classification of the training set using all the
decision boundaries presented in the figure. A learning curve of
$\simple$ (showing the true error) is given in
Figure~\ref{fig:norm11acc} (right). Clearly the true accuracy is
extremely unstable.

We propose the following solution using the idea of ``buffering'',
as well as our classification entropy estimator. One of the
\emph{symptoms} of the drastic decision boundary instability
described above is a (drastic) change in the classification
entropy. We observe that when the boundary shifts from the border
between the two clusters to the middle of one of the clusters
(iterations 5,7) the entropy decreases. Therefore, the solution we
propose is to look at the change in entropy of the pool (and
training set) classification in the end of each trial. As long as
the entropy decreases, new examples are \emph{buffered} and not
added to the training set. Once the entropy has not decreased, all
buffered points are added to the training set. If we want to keep
a bounded buffer this solution introduces a new parameter; namely,
the buffer size. In our experience a small buffer is sufficient
and in all our experiments we used a buffer of three points.

This buffering approach provides an effective solution to the
above problem. In Figure~\ref{fig:norm11acc} (right) we see the
learning curves of $\simple$ on the `Twonorm2D' data set with and
without this enhancement. It is evident that the learning curve of
the original algorithm is very unstable. Adding the buffering
enhancement smoothes the learning curve.
Figure~\ref{fig:norm11good} shows the pool classification and the
training sets generated by the enhanced $\simple$ active learner
after 4-8 iterations. The decision boundary now does not change
drastically from one iteration to another.

%\bibliographystyle{mlapa}
\bibliography{active}

\end{document}
