\documentclass[twocolumn]{svjour3}

\smartqed

\usepackage{subfigure}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{natbib}
\usepackage{amsmath}
\usepackage{array}
\usepackage{rotating}
\usepackage[super]{nth}

\interfootnotelinepenalty=10000

\newcommand{\argmax}{\operatornamewithlimits{argmax}}

\journalname{International Journal of Computer Vision}


\begin{document}

\title{Active Rare Class Discovery and Classification using Dirichlet Processes}

\author{Tom S. F. Haines \and Tao Xiang}

\institute{T.S.F. Haines \at
           Queen Mary, University of London, Mile End Road, London E1 4NS, UK \\
           \email{thaines@eecs.qmul.ac.uk} \\
           \and
           T. Xiang \at
           \email{txiang@eecs.qmul.ac.uk} \\
}

\date{Received: date / Accepted: date}



\maketitle



\begin{abstract}
Classification is used to solve countless problems.
Many real world problems, such as visual surveillance, contain uninteresting but common classes alongside interesting but rare classes.
The rare classes are often unknown, and need to be discovered whilst training a classifier.
Given a data set active learning selects the members within it to be labelled for the purpose of constructing a classifier, optimising the choice to get the best classifier for the least amount of effort.
We propose an active learning method for scenarios with unknown, rare classes.
By assuming a non-parametric prior on the data the goals of new class discovery and classification refinement are automatically balanced, without any tunable parameters.
The ability to work with any specific classifier is maintained, so it may be used with the technique most appropriate for the problem at hand.
Results are provided for a large variety of problems, demonstrating superior performance.

\keywords{Active Learning \and Rare Class Discovery \and Classification}
\end{abstract}



\section{Introduction}
\label{sec:intro}


\begin{figure}
\begin{center}
\includegraphics[width=\linewidth]{faces/graph_images}
\end{center}
\caption{A visualisation of the imbalance in the faces data set \citep{huang:labeled,guillaumin:is}, showing how many exemplars exist ($y$ axis) for the $128$ most common people ($x$ axis, faces shown for \nth{1}, \nth{8}, \nth{16}, \nth{32}, \nth{64}, \nth{96} and \nth{128}.). The full data set has $9952$ people in it.}
\label{fig:faces}
\end{figure}


Classification is an important technique, key to solving innumerable problems in areas such as computer vision.
A training set is collected, and a domain expert labels each exemplar in the set with the desired (discrete) answer.
The relationship between the exemplars and the labels is then learnt by a classification algorithm, such that the answer can be estimated for future exemplars.
As domain experts are not cheap the greatest expense often lies in the labelling step.
In many real-world problems, such as visual surveillance, computer-aided diagnoses for medical imaging and image segment labelling, the proportion of exemplars in different classes is imbalanced - the majority belong to uninteresting background classes whilst the interesting classes have few exemplars.
This imbalance can dramatically increase the labelling cost, as many more exemplars have to be labelled by the domain expert to have a reasonable chance of including all the rare classes.
Furthermore, the interesting minority is often unknown in advance.
To give examples:
\begin{itemize}
%\item As an example of a purely imbalanced problem oil spills are rare, so much so that when training to detect them via satellite only $4\%$ of the data set is oil, the rest being open water, even though the data set is constructed with images known to contain oil spills \citep{kubat:machine}.
\item In the Sloan Digital Sky Survey most of the survey images of galaxies and quasars capture known phenomena, whilst unusual phenomena, that could be evidence of new science, constitute only $0.001\%$ of the total data set \citep{pelleg:active}.
\item When detecting buildings from aerial/satellite imagery the percentage of positive examples for one data set \citep{maloof:improved} is less than $5\%$.
Buildings can come in many shapes and materials, and for military scenarios buildings may be camouflaged - deliberately designed to look like something else entirely.
\item Figure \ref{fig:faces} demonstrates the inherent imbalance in the faces data set \citep{huang:labeled}.
This data set has been constructed by extracting faces from the news over a $12$ month period - it shows the classical power law bias, with a few people dominating the headlines whilst the vast majority get few mentions.
As a sampling of current media interest new classes can appear at any time, when events push a previously unknown individual into the news - class discovery will never cease.
\end{itemize}
To classify rare classes one typically needs to exhaustively label a sizable data set, to obtain sufficient instances of each rare class.
Such a manual labelling process is often prohibitively expensive, rendering supervised learning impractical.

Active learning \citep{settles:active} offers a solution.
It selects the exemplars to be labelled, with the choice made to minimise the number of labels required to train a good classifier.
Because we have unknown classes that are also rare there are two competing goals to consider - to find all the rare classes, and to refine the boundaries between the currently known classes.
Both of these behaviours will improve classification performance - if a class is unknown then the classifier will incorrectly classify all instances of that class, whilst boundary refinement is needed to get good performance for classes that have already been discovered.
However, most existing active learning methods either assume that all classes are known and thus focus on the classification problem \citep{settles:active}, or focus on the class discovery problem only \citep{pelleg:active,he:nearest,vatturi:category}.
The approaches that try to meet both goals simultaneously \citep{hospedales:finding,stokes:aladin} are heuristic, and have free parameters that need tuning for each scenario.
It should be noted that discovering rare classes is often less of an improvement for classification performance than refining the boundary between common classes.
Consequentially it does not make sense to first perform discovery then boundary refinement, particularly as it is impossible to know when all classes have been found.
Instead the two goals have to be considered simultaneously and queries made accordingly.

We propose a novel active learning approach, which automatically balances the two competing goals, without the need to tune parameters.
It is a pool based approach - it iteratively selects an exemplar from a pool and asks the user to label it.
During each iteration the model is updated with the new label, so it can be used to select the next exemplar from the pool.
The selection proceeds in three steps.
Firstly, for each exemplar in the pool the probability of it belonging to each existing class, and belonging to a new class, are calculated, under a Dirichlet process (DP) assumption.
Secondly, the probability that the instance will be misclassified is calculated.
Misclassification probability is an \emph{uncertainty} based method, that works to improve the boundary between existing classes \citep{settles:active}; however, because a DP assumption allows the probability of belonging to an \emph{unknown} class to be factored in, it also achieves the goal of class discovery.
The balance between the two goals is determined by the concentration parameter of the DP, which is automatically inferred.
Finally, a single instance is selected, based on the estimated chances of misclassification.
Our key contribution is this novel active learning criterion, which is specifically designed to balance the two competing goals of discovery and classification.
Furthermore, its implementation is simple, it has no tunable parameters and it works with any probabilistic classifier\footnote{An implementation is available from \url{http://thaines.com}}.

In the following section the relationship between this work and others is explored.
Section \ref{sec:method} details the actual algorithm, after which it is evaluated in section \ref{sec:eval}.
Finally, conclusions are given in section \ref{sec:conc}.



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

Active learning is a long standing \citep{angluin:queries} and expansive field - the survey of \citet{settles:active} gives an overview, whilst \citet{olsson:literature} also gives a literature review, but focused on natural language processing alone.
Such techniques can be broken down into two parts - a learning algorithm and an active learning criterion, which are often integrated and then targeted at a specific problem domain.
The criterion is responsible for determining which exemplars are to be labelled.
As we are proposing a domain-agnostic and learner-agnostic approach it is the criterion that will now be considered - there are only a few specific approaches, as most papers are about adapting an approach to a specific domain or learning technique.

Random sampling\footnote{Sometimes referred to as \emph{passive learning}.} is the simplest possible criterion, where exemplars are selected at random to be labelled.
Despite its simplicity when dealing with balanced data the odds are that each random item is a new class, and it will often do surprisingly well.
It is inappropriate for unbalanced data however, as the odds of selecting a rare class can become arbitrarily small.


\subsection{Query by uncertainty}

Uncertainty criteria \citep{lewis:sequential} select instances for which the classifier is uncertain - they are thus good at refining the boundaries between classes.
Multiple uncertainty methods exist \citep{settles:active}:
One commonly used technique is based on entropy \citep{settles:active} - the entropy of the class membership distribution for each exemplar is calculated, and the highest scoring selected.
A high entropy indicates a lot of uncertainty in the classification of an exemplar, with a particular emphasis on exemplars for which many classes are considered to be a reasonable classification possibility.
\citet{lewis:sequential} deal with binary classification, and explicitly select the exemplar with membership probability closest to 0.5, the class boundary.
\citet{culotta:reducing} generalise this idea to multiple classes, by selecting the exemplar for which the classifier is least confident.
This is related to our approach as it is optimising the same goal - they both select the exemplar that is most likely to be misclassified, but it only considers known classes, hence it can only improve class boundaries.
\citet{vlachos:active} use a semi-supervised Dirichlet process mixture model to cluster the data; active learning with the entropy approach is used to select the same-cluster/different-cluster constraints used to supervise the clustering.
Whilst superficially similar to our approach they are solving a different problem (boundary refinement) and using the Dirichlet processes for classification only, not for active learning.




\subsection{Query by committee}

Query by committee (QBC) \citep{seung:query} requires the existence of multiple classifiers for the labelled data, and consists of selecting exemplars based on a measure of disagreement between them.
Obtaining multiple classifiers can be explicit, or it can involve a probability distribution over the classifier, from which multiple specific classifiers can be drawn.
Classifiers that include a random element can provide this capability, e.g. boosting and bagging \citet{abe:query}.
Taking the probabilistic interpretation the committee members can be integrated out, using, for instance, an uncertainty-based metric, but this does not utilise disagreement.
A common measure of disagreement is to let each member vote for the exemplars class, treat this as a probability distribution and calculate the entropy \citep{dagan:committee}.
\citet{mccallum:employing} provide an alternative, where they sum the Kullback-Leibler divergence between each committee member's probabilistic assignment and the consensus of the committee, calculated by averaging.
Query by committee works because it considers the space of classifiers that fit the data, and selects exemplars to maximally reduce that space, to get the best classifier quickly.
This tends to focus on outliers however, at the expense of boundary refinement.


\subsection{Expected error reduction}

Expected error reduction \citep{roy:toward} selects the exemplar from the pool that will minimise an estimate of future error.
For each exemplar it considers the model after it has been updated with each possible label, estimating the error of each model using all exemplars.
This includes those for which the class is known, for which it is a direct comparison, but for exemplars still in the pool it uses the probabilistic labelling of the current model.
The expected reduction is then calculated for each exemplar in the pool, and the exemplar with the largest chosen.
Whilst arguably the best approach for boundary refinement, it does not do class discovery, and is computationally expensive, so much so that sampling and efficient incremental learning techniques are required \citep{roy:toward}.
The approximation of expected error for a future model state is problematic, and can result in it selecting exemplars that confirm the current model.
%\citet{hospedales:unifying} explore the use of our presented criterion for expected error reduction.
%Whilst an improvement is demonstrated it is often slight, and at great computational expense - it has to use the presented to reduce the problem size enough to run.

Error reduction may be the obvious goal, but there are alternate criteria that may approximate it, with a more reasonable (though still high) computational demand.
Model change \citep{settles:multiple} selects exemplars that are likely to cause a large change for the classification models parameters.
In principal information resulting in a large parameter change is of greater value than minor tweaks, though it very much depends on the meaning of the parameters.
Variance reduction \citep{cohn:improving} selects exemplars to reduce the variance of the model, which can be interpreted as making the model more certain in its answers - it is related to QBC in this respect.
\citet{cohn:improving} applied this to regression.
The concept of a version space was introduced by \citet{mitchell:generalization} - it is defined as the set of model parameters that correctly classify the currently labelled data.
\citet{tong:support} introduce a margin-based active learning method for SVMs.
Selection from the pool is driven by reducing the size of the version space as quickly as possible, to find the best model in the least number of queries.
Whilst the concept is sound their implementation requires that the data be separable, which is fatal in many real world scenarios.


\subsection{Discovery}

Most existing active learning studies assume that all classes are known a priori.
\citet{hodge:survey} give the likelihood criterion, which proceeds by querying the exemplars that have the lowest probability according to the classifier's current model.
Whilst often considered to be an uncertainty criterion it is better suited to finding new classes than refining the boundaries of existing classes, hence its inclusion here.
Likelihood is limited by its inability to distinguish new classes from outliers, and to find classes that are inseparable from already detected classes.

Recently there have been a number of works that explicitly focus on the rare class discovery problem.
\citet{pelleg:active} use an EM classifier with Gaussian distributions and adopt a variant of the likelihood criterion.
Whilst it is specifically for finding rare classes the total number of rare classes must be provided up front to set the number of EM clusters.
The model and active learning method are also inseparable.
\citet{he:nearest} perform density estimation and query exemplars based on identifying local maxima in the density using gradients.
Like \citet{pelleg:active} this requires knowing how many unknown classes exist; additionally it also needs an estimate of how many exemplars belong to each class - for real problems this is unreasonable.
\citet{vatturi:category} also take a density estimation approach.
Mean shift at multiple scales is used to cluster the examples in the pool, and for each cluster the example nearest to the centre is selected to be queried.
It gives strong performance for rare class discovery.
However, both \citet{vatturi:category} and \citet{he:nearest} avoid interacting with the classification model.
This is advantageous as it applies no restriction on the model, but problematic as it can only work to find new classes, not to improve the classification model, so poor results are expected for classification.
Our approach can also work with any classification method, its only restriction being a requirement that the model provide probabilistic answers.
It interacts with the classifier, and can hence work to improve classification performance.


\subsection{Discovery and boundary refinement}

This is the approach to which the presented \citep{haines:active} belongs - where the discovery of new classes and refinement of the class boundaries for known classes are considered within a single framework.
\citet{stokes:aladin} work on network intrusion detection, where they treat the two goals separately.
Batches of exemplars to label are provided, where some members have been selected based on uncertainty, and some have been selected due to being outliers; the ratio between the types is fixed.
This does not work very well - at the start of training class discovery provides the greatest value, but as the process runs and all the classes are found it needs to focus on class boundary refinement.
\citet{hospedales:finding} resolves this issue by heuristically selecting which approach to use.
The two approaches are a generative classifier (kernel density estimate) with likelihood based selection, and a discriminative model (support vector machine), with selection based on uncertainty.
As the querying progresses it switches between the models based on their past performance.
This initially means it mostly uses the generative model to find new classes, but latter tends to be discriminative, to refine the boundary between classes.
This is ideal as generative tends to work best for classification at the start, when there are few labelled exemplars, whilst discriminative models are ultimately better, but only when given enough data.
Not surprisingly, it outperforms previous active learning methods which are designed for solving either class discovery or classification, not both.
However, the method is entirely heuristic and includes parameters that need to be tuned for each scenario.
Our approach shows similar behaviour when it comes to transitioning between discovery and refinement, but this behaviour is induced by the Dirichlet process assumption, without the need for heuristics.


\subsection{Variations}

We present pool based learning.
This consists of having a pool of exemplars from which to choose the next one to be labelled.
An alternate scenario is stream based active learning \citep{cohn:improving} - in this case exemplars arrive continuously, and are not stored, so an instantaneous decision is required for each on if it should be given to the domain expert or not.

Active learning is traditionally applied to classification, as we do, but can also be applied to regression \citep{mackay:information}.
\citet{mackay:information} is actually concerned with experiment design, where one selects the most informative scientific experiments to run with limited time/budget, an area closely related to active learning.
Transfer learning is related in some situations, by virtue of handling the relationship between known and unknown classes.
An example of this is \citet{lee:object}, which uses the relationship between known classes and unknown classes to automatically infer the unknown classes, ready for human verification followed by further learning.
Reinforcement learning \citep{kaelbling:reinforcement} is also closely related to the presented kind of active learning, via the \emph{exploration-exploitation} problem.


\section{Method}
\label{sec:method}

Given a pool of unlabelled instances the algorithm consists of a loop containing three steps,
\begin{enumerate}
 \item A specific exemplar is selected from the pool.
 \item It is labelled by the domain expert.
 \item The model is updated with the new labelled exemplar. A previously unseen label will result in the creation of a new class in the model.
\end{enumerate}
Our approach is responsible for the first step, and is itself broken down into three tasks,
\begin{enumerate}
\item For each exemplar a distribution over which class it belongs to is estimated, using the current model. It uses the Dirichlet process assumption to also calculate the probability of it belonging to an unknown class.
\item The probability of misclassification is calculated for each exemplar, which includes the possibility of it being misclassified due to it belonging to a new, unknown class.
\item An exemplar is selected, based on the misclassification probability.
\end{enumerate}
These three tasks are detailed in the following subsections.
Additionally a discussion of when to stop and a demonstration of the algorithms behaviour are also provided.



\subsection{New class probability}
Calculating the probability that an instance comes from an unknown class is problematic, as, by definition, nothing is currently known about the unknown classes.
To resolve this it is assumed that a generative model of the data can be used, specifically a \emph{Dirichlet process} (DP) mixture model.
This is a valid assumption for most classification problems \citep{sethuraman:constructive}.

A Dirichlet process \citep{ferguson:bayesian} is typically used for non-parametric Bayesian models, e.g. density estimates \citep{escobar:density} and topic models \citep{teh:hierarchical}.
For the purpose of active learning however two properties are important: that it has clustering behaviour \citep{teh:hierarchical2}, such that it expects the instances to be grouped into discrete classes; and that it considers an infinite number of classes, and hence dynamically adjusts the number of classes given the data.

The Dirichlet process may be denoted as $DP(\alpha,G_0)$, where $\alpha$ is its \emph{concentration parameter} and $G_0$ is its \emph{base measure}.
A draw from a DP provides a probability distribution over draws from the base measure, in the form of a Dirichlet distribution with infinitly many members.
The clustering behaviour occurs because, even if the base measure is continuous, draws from it can be repeated when you draw from the infinite Dirichlet distribution.
The stick-breaking process \citep{sethuraman:constructive} models this behaviour explicitly.
Intuitively, we start with a stick of length $1$, representing the entire probability mass, and keep breaking it in two.
Each time we break it we get two parts - one is assigned to a draw from the base measure, and its length is the probability of drawing that particular item from the distribution we are generating, whilst the second part goes on to the next break.
Specifically, this process generates an infinitely large set of sticks, of length $s_i, i \in \{0, 1, \ldots\}$,
\begin{align}
s_i = s'_i \prod_{j=1}^{i-1}(1-s'_j)
\end{align}
where $s'_i$ can be thought of as the breaking ratio at each step.
It is drawn from a beta distribution, which is dependent on the concentration parameter
\begin{align}
s'_i \sim \beta(1, \alpha)
\end{align}
The concentration parameter therefore influences how much of each break goes to the current stick and how much is shared by future sticks.
In the context of a mixture model, where each stick represents a cluster, a low value means most of the probability mass will be within a few clusters, whilst a high value means it is shared by many.

\begin{figure}
\begin{center}
\subfigure[]{\parbox{\linewidth}{
\includegraphics[width=\linewidth]{restaurant/restauant0008.png}

\vspace{-1cm}
\begin{minipage}[c][2cm]{\linewidth}
\begin{center}
\begin{tabular}{>{\centering}m{1.3cm}>{\centering}m{1.5cm}>{\centering}m{1.7cm}>{\centering}m{2.1cm}}
 & $\frac{\alpha}{\alpha+5}$ & $\frac{3}{\alpha+5}$ & $\frac{2}{\alpha+5}$
\end{tabular}
\end{center}
\end{minipage}
\label{fig:crp:start}
\vspace{-0.5cm}
}}
\subfigure[]{\parbox{\linewidth}{
\includegraphics[width=\linewidth]{restaurant/restauant0010.png}

\vspace{-1cm}
\begin{minipage}[c][2cm]{\linewidth}
\begin{center}
\begin{tabular}{>{\centering}m{1.3cm}>{\centering}m{1.5cm}>{\centering}m{1.7cm}>{\centering}m{2.1cm}}
$\frac{\alpha}{\alpha+6}$ & $\frac{1}{\alpha+6}$ & $\frac{3}{\alpha+6}$ & $\frac{2}{\alpha+6}$
\end{tabular}
\end{center}
\end{minipage}
\label{fig:crp:end}
\vspace{-0.5cm}
}}
\end{center}
\caption{A representation of the Chinese restaurant process - customers sitting around tables with the chosen menu item in the centre. Under each table the probability of an arriving customer choosing it is given. If a person were to arrive at \subref{fig:crp:start} and sit at the empty table the next state would be \subref{fig:crp:end}.}
\label{fig:crp}
\end{figure}

For the purpose of active learning all we need to calculate is the marginal posterior, i.e. given
\begin{align}
G & \sim DP(\alpha,G_0) \\
c_i & \sim G
\end{align}
where $c_i$ is the class of an exemplar it is defined as
\begin{align}
P(c_i | \{c_j ; j \in J_i\}, \alpha, G_0) & \propto \\
\int \prod_{j \in J} & P(c_j|G) P(G|\alpha,G_0) dG \\
J_i = J \setminus \{i\} \\
J = \{1, \ldots, n\}
\end{align}
where $n$ is the number of labelled exemplars.
It is given by the Chinese restaurant process \citep{blackwell:ferguson}.
The Chinese restaurant process is an analogy consisting of a restaurant containing an infinite number of tables at which customers sit.
Each table represents a cluster in the mixture model, whilst the customers represent exemplars from the pool.
On each table only a single dish is served, representing a single choice from the menu.
This represents a draw from the base measure, and for active learning is the class associated with the cluster.
When new customers arrive they either sit at a table with existing patrons, and consume the dish already assigned to the table, or they choose a previously unused table, for which a new dish is selected from the menu.
These correspond to the instance belonging to an existing class and a new class, respectively.
Each of the in-use tables is chosen proportional to the number of customers already sitting at them, whilst a new table is chosen proportional to the concentration parameter.
Note that whilst an infinite number of tables theoretically exist, corresponding to the components of the infinitely sized Dirichlet distribution, only used tables need to be tracked, making this a finite construction.
This is illustrated in figure \ref{fig:crp}.

For each instance in the pool of unlabelled instances the aim is to compute the probability of it belonging to each existing class, and of it belonging to a new class, conditional on all previous instances for which the domain expert has provided a label.
This is assuming a mixture-like model, where each table in the DP corresponds with a class assignment.
Note that this is not a requirement for the classification model to also be a mixture model; it can be any model where $P_c(\mbox{data}|\mbox{class})$ can be calculated.
For the moment the existence of a prior, $P(\mbox{data})$, is also assumed, such that $P_c(\mbox{data}|\mbox{class})$ is its posterior, using Bayes rule.
Accordingly, the probability distribution for an instance is given as
\begin{align}
\label{eqn:prob_inc_new}
&P_n(c \in C \cup \{\mbox{new}\}|d) \propto \hspace{1.5cm} \nonumber \\
&\hspace{1.5cm} \left\{ \begin{array}{ll}
\frac{m_c}{\sum_{k \in C} m_k + \alpha} P_c(d|c) & \mbox{if $c \in C$} \vspace{0.2cm}\\
\frac{\alpha}{\sum_{k \in C} m_k + \alpha} P(d) & \mbox{if $c = \mbox{new}$}
\end{array} \right.
\end{align}
where $d$ is the data for the considered instance, $C$ is the set of known classes, $m_c$ the number of instances labelled with class $c$ and $\alpha$ is the concentration parameter for the DP.
Once normalised this provides a distribution for each instance that consists of the probability of the instance belonging to each of the known classes as well as to an unknown class.
Two issues remain - how to set the concentration parameter and how to set the prior, $P(\mbox{data})$.

Instead of treating $\alpha$ as a user set parameter a prior may be applied and Gibbs sampling used to estimate it, using the technique of \citet{escobar:density}.
The prior on $\alpha$ is a gamma distribution, $G(a, b)$.
This method proceeds by first sampling a quantity $\eta$ given the current concentration, and then resampling the concentration given $\eta$.
$\eta$ given the concentration, $\alpha$, is given in terms of the beta distribution, $\beta(., .)$
\begin{equation}
\eta | \alpha, k, n \sim \beta(\alpha + 1, n)
\end{equation}
where $k$ is the number of classes that currently exist and $n$ the number of examples distributed over the classes.
$\alpha$ given $\eta$ is then a mixture of two gamma distributions, $\Gamma(., .)$
\begin{align}
\alpha | \eta, k, n \sim & \ \pi \Gamma(a + k, b - \log(\eta)) \nonumber \\
& + (1-\pi) \Gamma(a + k - 1, b - \log(\eta))
\end{align}
where the ratio of the mixing terms is given by
\begin{equation}
 \frac{\pi}{1 - \pi} = \frac{a + k - 1}{n (b - \log(\eta))}
\end{equation}
Given a prior the mean of a number of Gibbs samples is used, after a burn in period \cite{stochastic:geman}.
In this work a weakly-informative prior of $\Gamma(1,1)$ is used, with 128 samples used for both burn in and sampling the mean; for initialisation the concentration of the previous query is used.

A prior, $P(\mbox{data})$, is also required.
Whilst a proper prior can certainly be used this term obviously parallels active learning methods based on density estimation (Such as \citet{vatturi:category}) - it defines how likely a sample is something useful, rather than an outlier.
It follows that the prior must be selected based on the data in the pool, for which it is in effect going to be a density estimate.
Given that real priors are often very simple, e.g. conjugate, a good density estimate will be beneficial and, as there is no reason to use an actual prior, a proper density estimate based on the initial pool is preferred.



\subsection{Misclassification probability}
Given the class membership probabilities, $P_n(.)$, which include the probability of belonging to a new class, an actual selection from the pool is required.
The goal is to balance finding new classes against refining existing classes.
A common approach to improving the existing model is to select instances that have a high degree of uncertainty in their classification given the current model.
The most popular method is the entropy method, but entropy cannot be applied when there is a probability of an unknown class, at least not without the introduction of a free parameter.
Several alternative approaches to entropy exist \citep{settles:active}.
One such approach is to calculate the probability of classifying an instance incorrectly.
For instance this approach was implicitly used by \citet{lewis:sequential} for the purpose of text classification.
They described it in terms of selecting instances with class probabilities that are closest to $0.5$, which is equivalent.
To include the possibility of a new class this idea has to be considered explicitly, and proper consideration of multiple classes has to be made.

Two assumptions are made - firstly that the classifier will select the class to which it has assigned the highest probability, noting that this only includes known classes, and secondly that the calculated distribution is an accurate estimate of what the true class of the instance could be, noting that it includes the possibility of a new class.
It is then a simple matter to calculate the probability of incorrectly classifying an instance,
\begin{align}
P(\mbox{wrong}|d) = 1 - P_n(c'|d) \\
c' = \argmax_{c \in C} P_c(c|d)
\end{align}
where $P_n(c|d)$ is the probability of the instance belonging to the selected class as calculated above, whilst $P_c(c|d)$ is the probability calculated by the classifier, typically using Bayes rule with a $P(c)$ term.
If $P(c)$ weights classes by the number of instances seen then $P_n(c|d)$ and $P_c(c|d)$ will be equivalent, other than $P_c$ excluding the probability of a new class and hence being normalised differently.
Alternatively, if a different prior on class probability is assumed, e.g. a uniform distribution, then this will not be the case.

It is important to note that the proposed misclassification probability (denoted as $P(\mbox{wrong})$ hereafter) based active learning criterion is different from a conventional uncertainty criterion that focuses only on boundary refinement for existing classes.
This is because $P_n(c|d)$ includes the probability of the instance belonging to a new class (denoted as $P(\mbox{new})$), which the classifier can never select.
If the $P(\mbox{new})$ value is high, the $P(\mbox{wrong})$ value will also be high; similarly if the $P(\mbox{new})$ value is low but the classifier is uncertain, so that none of the class probabilities are high, a high $P(\mbox{wrong})$ will again be generated.
Therefore the value of $P(\mbox{wrong})$ is determined by two factors: the likelihood that the instance belongs to an unknown class, and how uncertain the current classifier is about the instance.
Which of these two dominates is driven by the concentration parameter.
Specifically, when it is high relative to the number of labelled instances selection becomes equivalent to using $P(\mbox{new})$ directly, but as it heads to zero only classification uncertainty is considered, and the boundaries are refined.
In practice the concentration parameter relative to the instance count tends to start high and drop to a low but constant level as the number of queries increases, i.e. as expected it starts by finding new classes, but as it sees more data and stops finding them it refocuses on boundary refinement.



\subsection{Selection}
\label{sub:selection}

Given the calculation of $P(\mbox{wrong})$ for every item in the pool a specific item still needs to be selected, so it can be labelled.
The obvious solution is to select the exemplar with the highest value of $P(\mbox{wrong})$, as the most useful.
Experiments show this to be suboptimal - instead a \emph{soft} selection strategy is used, where a random selection from the pool is made, weighted by $P(\mbox{wrong})$.
The choice is made because soft selection tends to provide better results, though it does depend on the problem.
Hard selection is problematic because outliers often look like good candidates for new classes, and hence have a high $P(\mbox{wrong})$ score, when they should probably be ignored.
Soft selection avoids this issue as groups of samples with a moderate $P(\mbox{wrong})$ score have a total weight larger than that of any given outlier, so the likelihood that a member of these groups will be chosen is greater than for the outliers.
This can be seen as a density weighting, to avoid classifying exemplars that are irrelevant.

Implicit in this strategy is the assumption that the classifier assigns a single class to each exemplar, when the requirements of $P(\mbox{wrong})$ require that it actually outputs a probabilistic assignment.
It is relatively easy to make the conversion, but this actually compromises performance, because in testing a single class is assigned to each exemplar - unsurprising the approach works better if it uses the same assumptions made when testing it.
A further assumption is made that the classifier will give an accurate estimate, which is clearly not true, especially when few queries have been made.
However, if a Bayesian classifier is used it will express its uncertainty, and $P(\mbox{wrong})$ will react accordingly, to improve that uncertainty and obtain a better classifier.
Whilst non-Bayesian classifiers typically lack such a measure a suitable estimate of confidence can often be obtained.



\subsection{Stopping Conditions}
\label{sub:stop}

Active learning is concerned with limited resources - the fact that it takes time/money/energy to provide ground truth information for a classification algorithm.
Eventually the querying has to stop.
Three common options can be considered:
\begin{itemize}
\item {\bf Query budget:} A fixed number of queries are performed.
\item {\bf Sufficient performance:} Enough queries are performed for classification performance to surpass a threshold. It can be estimated using n fold cross validation once enough queries have been performed to get an accurate enough estimate.
\item {\bf Cost-benefit analysis \cite{dupuit:measurement}:} In many situations misclassification can have a directly attributed cost, as can providing further labelled exemplars - the total cost can then be minimised.
To exemplify a widget factory may have a classifier to detect faulty products, alongside a given defect rate.
The defect rate multiplied by the false negative rate of the classifier will give the percentage of faulty products sent to customers - multiply this by the sales projections and the cost of handling a return and you obtain the money wasted by the classifiers mistakes.
The false positive rate should also be factored in, in terms of throwing out usable widgets.
Given the cost in employee time to train the classifier we can now work out at what point the cost of further training exceeds the value obtained (For a given product lifespan.), and hence when to stop training.
Complex effects can exist, e.g. sending customers faulty products can generate bad publicity, making sales a function of the classifiers false probability rate.
\end{itemize}
The choice of scheme is scenario specific however, and as such we will not be exploring it further.
However, by presenting results to a deep enough query count the above stopping conditions are implicitly represented using graphs of inlier rate against query count (Figure \ref{fig:graphs:classification}).
Query budget is represented by seeing which is highest after a given number of queries (a vertical line), whilst performance is given by which algorithm crosses a given threshold first (a horizontal line).
A cost benefit analysis is often represented by a straight line at an angle set by the relative costs of failure and further training.
More sophisticated cost-benefit models can generate an arbitrary curve.



\subsection{Demonstration}
\label{subsec:demo}

\begin{figure}
\centering
\subfigure[Data set]{\includegraphics[width=0.9\linewidth]{iris/data}\label{fig:demo:data}}
\subfigure[After 1 query]{\includegraphics[width=0.9\linewidth]{iris/query_01.pdf}\label{fig:demo:query01}}
\subfigure[After 2 queries]{\includegraphics[width=0.9\linewidth]{iris/query_02.pdf}\label{fig:demo:query02}}
\subfigure[After 3 queries]{\includegraphics[width=0.9\linewidth]{iris/query_03.pdf}\label{fig:demo:query03}}
\subfigure[After 5 queries]{\includegraphics[width=0.9\linewidth]{iris/query_05.pdf}\label{fig:demo:query05}}
\subfigure[After 12 queries]{\includegraphics[width=0.9\linewidth]{iris/query_12.pdf}\label{fig:demo:query12}}
\subfigure[Interest in new class discovery]{\includegraphics[width=0.9\linewidth]{iris/conc}\label{fig:demo:conc}}
\caption{$1D$ demonstration of the problem with 3 classes, with probability distributions.
The prior is constant, indicated by the dot-dash grey line, whilst the distributions for the 3 classes use the 3 primary colours, dashed.
Orange dots are used for the $P(\mbox{new})$ metric, whilst $P(\mbox{wrong})$ is given in black.}
\label{fig:demo}
\end{figure}

The presented approach, $P(\mbox{wrong})$, is now demonstrated and visualised using a $1D$ problem.
Specifically, the $4D$ 3-class \emph{iris} problem of \citet{fisher:use} is used, as obtained from the UCI repository \citep{frank:uci}.
It is a classification problem where the task is to identify flower species based on flower shape measurements.
Principal component analysis (PCA) is used to reduce the problem to a single dimension\footnote{It is not really solvable after this, as the classes have a lot of overlap, but it is sufficient to illustrate the inner workings of the presented approach, whilst reducing it to $1D$ allows for a clean visualisation.} - the resulting data set is visualised in Figure \ref{fig:demo:data}.
Each line represents a member of the data set - horizontal position indicates the position projected to by PCA, whilst the three primary colours represent the three classes.

Many approaches can be selected for classification - for this and the other experiments the incremental kernel density estimation (KDE) method of \citet{sillito:incremental} is used.
It uses a Gaussian kernel whilst the number of mixture components is capped, to maintain a constant time incremental algorithm.
When the cap is passed\footnote{We set this classifier parameter to 32.} mixture components are optimally merged, in terms of minimising the Kullback-Leibler divergence of the approximation.
One density estimate over the pool is used as the pseudo-prior\footnote{A density estimate that we hallucinate is the prior for the classification algorithm.}, whilst each class also has a density estimate built from its members.
A uniform prior over class assignment is used and kernel size is selected using leave one out cross-validation.
Bayes rule is used to calculate the probability of belonging to each class, and the class with the highest probability selected as the answer.

Figures \ref{fig:demo:query01} through to \ref{fig:demo:query12} show the state of the system after the given number of queries.
They are plots of probability values calculated for every $1D$ feature vector, where each plot has been normalised to fill the available height.
Firstly, the prior is given by the grey line, and it remains constant as the algorithm runs.
Each of the known classes is coloured using a primary colour.
The $P(\mbox{new})$ curve, giving the probability that a point on the line is going to belong to a new class, is given in orange whilst the $P(\mbox{wrong})$ curve is given in black.
$P(\mbox{new})$ has been included as it makes the behaviour of $P(\mbox{wrong})$ with regards to boundaries clearer.
The $P(\mbox{wrong})$ graph indicates how interested in a point the presented algorithm is, with the high points being the positions the algorithm is likely to select for its next query, conditional on such locations actually appearing in the data set.
Figure \ref{fig:demo:conc} plots the sampled concentration normalised by the concentration plus the number of labelled instances, i.e. the weight assigned to new classes, given the number of queries made.

Firstly, a new class is found in each of the first $3$ queries, and with the weight assigned to finding new classes dominating the two metrics have identical interests (the orange line is underneath the black line).
After the third query a slight difference is evident in that $P(\mbox{wrong})$ is more interested in examples that are on the boundary between the blue and green classes.
The state after $5$ queries demonstrates that, as the algorithm loses interest in finding new classes, as plotted in figure \ref{fig:demo:conc}, the two approaches start to differ, with $P(\mbox{wrong})$ showing greater interest in the classification boundaries whilst still maintaining an interest in areas where new classes could be.
By $12$ queries this is much more pronounced.
This demonstration clearly shows the various behaviours expected - an interest in areas where either new classes could be or the boundary could be refined, with the latter gaining dominance as it loses interest in finding new classes.
Figure \ref{fig:demo:conc} demonstrates how the level of interest in finding new classes drops as the algorithm makes more queries\footnote{Note that concentration cannot be calculated until at least two classes have been found, hence the jump in the graph at that time.}.



\section{Evaluation}
\label{sec:eval}

\begin{table*}[t]
\begin{center}
\begin{tabular}{|r|l|c|c|c|c|c|c|c|}
\hline
Problem & Origin & Classes & Dimensions & Train & Test & Largest & Smallest & Queries \\
\hline
glass       & \citet{frank:uci}          &   6 &  10 &    107 &   107 & 34.58\% & 3.74\% & 107 \\
ecoli       & \citet{frank:uci}          &   8 &   7 &    168 &   168 & 48.21\% & 0.60\% & 150 \\
%yeast       & \citet{frank:uci}          &  10 &   8 &    742 &   742 & 30.59\% & 0.27\% & 200 \\
segment     & \citet{frank:uci}          &   7 &  18 &    318 &   317 & 47.80\% & 0.94\% & 150 \\
pageblocks  & \citet{frank:uci}          &   5 &  10 &   3649 &  1824 & 89.28\% & 0.49\% & 150 \\
covertype   & \citet{frank:uci}          &   7 &  10 &   2500 &  2500 & 24.36\% & 3.56\% & 150 \\
thyroid     & \citet{frank:uci}          &   3 &  21 &   3772 &  3428 & 92.47\% & 2.47\% & 150 \\
winequality & \citet{frank:uci}          &   6 &  11 &   2447 &  2446 & 45.24\% & 0.37\% & 150 \\
letters     & \citet{frank:uci}          &  26 &  16 &   2620 &  6656 & 13.74\% & 0.31\% & 200 \\
shuttle     & \citet{frank:uci}          &   7 &   9 &  10000 & 14500 & 77.72\% & 0.03\% & 150 \\
kdd99       & \citet{frank:uci}          &  15 & 113 &  16825 & 16825 & 51.46\% & 0.04\% & 200 \\
gait        & \citet{hospedales:finding} &   9 &  25 &    411 &  1942 & 48.66\% & 2.92\% & 150 \\
digits      & \citet{hospedales:finding} &  10 &  25 &   8184 &  5000 & 50.05\% & 0.10\% & 200 \\
faces       & \citet{huang:labeled}      & 330 &  32 &   5195 &  5195 & 10.95\% & 0.04\% & 1000 \\
%sun         & \citet{xiao:sun}           & 397 &  40 & 103328 &  5426 &  2.17\% & 0.09\% & 1000 \\
\hline
\end{tabular}
\end{center}
\caption{Details of the data sets used. Origin gives the source - most have come from the UCI repository. Classes is the number of classes in the classification problem, dimensions the length of the feature vector. Train gives the number of training exemplars, which is the size of the initial pool; test the number used for testing. Largest is the percentage of exemplars that belong to the largest class, smallest the percentage that belongs to the smallest class, to indicate how imbalanced the problem is. Queries is the number of queries performed - the values were chosen to match previous papers \citep{hospedales:finding, haines:active, loy:stream}, with the other data sets set consistentantly.}
\label{fig:problems}
\end{table*}


Results are given for $13$ data sets, consisting of the following classification problems:
% specifically the problems used by \citet{hospedales:unifying}.
\begin{itemize}
\item \textbf{glass:} Infer glass type given its chemical contents, for forensic investigation. Features include chemical properties and how it breaks.
\item \textbf{ecoli:} Predict which part of a cell contains a protein localisation site, for E.coli.
%\item \textbf{yeast:} Predict which part of a cell contains a protein localization site, for yeast.
\item \textbf{segment:} Labelling regions from images of outdoor scenes, with labels such as grass, path and sky. Input is a small patch of pixels; output is the label for the centre pixel of the patch.
\item \textbf{pageblocks:} Classifying regions from document scans, e.g. as text, picture or graphic. Features include colour ratios and measures of texture.
\item \textbf{covertype:} Predicting forest cover type given geographic information, such as elevation and soil type.
\item \textbf{thyroid:} Determining the disease that a thyroid has given observed and measured properties.
\item \textbf{winequality:} Predict the quality of Portuguese wine given various chemical properties. Strictly speaking this is a quantised regression problem.
\item \textbf{letters:} Recognising handwritten letters from the English alphabet. Input is images of each letter.
\item \textbf{shuttle:} Infer the state of part of the space shuttles propulsion system, given various sensor readings, as relating to the Challenger disaster.
\item \textbf{kdd99:} Data set used for the \emph{3rd Knowledge Discovery and Data Mining Tools Competition} - uses a simulation of a military network with the goal being to detect intrusions given tcp dump data. The original data set included multinomial attributes, which have been concatenated as part of the feature vector, hence the high dimensionality of the problem.
\item \textbf{gait:} Inferring the quantised walking direction from aligned silhouettes that have been averaged over multiple frames (Input is a greyscale image.), as in \citet{han:individual}. This data set was sampled to be unbalanced, such that each class is half the size of the next larger.
\item \textbf{digits:} Recognising the handwritten digits, $0-9$, given images of the digits. This data set was sampled to be unbalanced, such that each class is half the size of the next larger.
\item \textbf{faces:} Large scale face recognition from images extracted using a face detector. Uses the preparation given by \citet{guillaumin:is}; additionally people who have less than 10 entries have been removed.
%\item \textbf{sun:} Large scale scene recognition from images, with scenes such as beach and zoo.
\end{itemize}
In all cases the original features provided by the data sets have been used, though some of the vision problems have been subjected to dimensionality reduction, by principal component analysis (To avoid using an entire image as input.).
The last data set, \emph{faces}, is an example of an extremely large scale problem, having over $300$ classes.
Various statistics summarising the problems are given in table \ref{fig:problems} - note that they vary in size, number of classes and class imbalance.

For testing we use the incremental KDE method of \citet{sillito:incremental}, as described in subsection \ref{subsec:demo} to classify, via Bayes rule, and also to provide a pseudo-prior.
Testing consists of running through the active learning loop and using a separate test set to measure the balanced classification performance after each query.
Different problems are run to different query depths, depending on the number of classes in the data set - see table \ref{fig:problems}.
Multiple runs are performed\footnote{$32$ in all cases except for \emph{kdd99} and \emph{faces}, where it is $24$ and $16$ respectively due to their size.}, to account for the variability with the stochastic algorithms, and the results averaged.
Finally, two graphs may be plotted - either the balanced inlier rate\footnote{Balanced inlier rate is calculated as the average inlier rate for each class in the training set. Inlier rate is the number of correct classifications divided by the number of exemplars being classified. This can be interpreted as \emph{recall} generalised to $3+$ classes.} (classification) or the number of classes discovered (discovery) can be graphed against the number of queries.
These graphs, for all data sets, may be found in figures \ref{fig:graphs:classification} and \ref{fig:graphs:discovery}.
We also report the areas under these graphs, noting that strong classification performance is better aligned with the goal of training as good a classifier as possible with as few queries as possible.

Four algorithms are compared against the presented approach, $P(\mbox{wrong})$:
\begin{itemize}
\item \textbf{random:} Random selection - effectively a dumb algorithm that provides a baseline for performance.
\item \textbf{entropy:} Calculates the entropy of the class distribution of each item in the pool, selecting the exemplar that requires the most information to encode draws from. This approach attempts to refine the boundary between classes.
\item \textbf{likelihood:} Selects the exemplar from the pool that has the lowest probability of belonging to the current model - it selects outliers. This approach attempts to find new classes.
\item \textbf{\citet{hospedales:finding}:} Balances class discovery and boundary refinement by selecting between one model for each, based on current model performance.
A generative model (kernel density estimate.) with \emph{likelihood} based selection is used for class discovery, whilst a discriminative model (svm) with \emph{entropy} based selection is used for boundary refinement.
Selection is entirely probabilistic, including the use of Gibbs functions on the active learning criteria.
Results are only available for three of the datasets; it has the unfair advantages of having been tuned for them and using a better classifier.
\end{itemize}


\begin{table*}[t]
\begin{center}
\begin{tabular}{|r|c|c|c|c|c|}
\hline
Problem & Random & Entropy & Likelihood & \citet{hospedales:finding} & $P(\mbox{wrong})$ \\
\hline
glass       &  70.5 (3) &  61.6 (4) &  72.2 (2) &          &  74.5 (1) \\
ecoli       &  83.4 (3) &  66.9 (4) &  90.0 (1) &          &  84.4 (2) \\
%yeast       &  73.8 (3) &  54.6 (4) &  88.7 (1) &          &  75.0 (2) \\
segment     &  90.7 (3) &  67.3 (4) & 109.4 (1) &          & 107.7 (2) \\
pageblocks  &  64.6 (4) &  70.7 (3) &  76.6 (2) &          &  78.5 (1) \\
covertype   &  71.2 (2) &  50.9 (4) &  62.4 (3) &          &  72.6 (1) \\
thyroid     &  76.8 (2) &  65.7 (4) &  75.3 (3) &          &  80.1 (1) \\
winequality &  36.8 (3) &  33.3 (4) &  37.6 (1) &          &  37.2 (2) \\
letters     &  59.8 (3) &  11.1 (4) &  75.8 (1) &          &  66.9 (2) \\
shuttle     &  53.5 (4) &  51.8 (5) &  79.4 (2) & 61.8 (3) &  79.8 (1) \\
kdd99       &  92.1 (4) &  96.1 (3) &  96.9 (2) &          & 146.6 (1) \\
gait        &  78.9 (3) &  75.3 (4) &  56.5 (5) & 84.8 (2) &  88.4 (1) \\
digits      &  54.6 (5) &  57.1 (4) &  61.9 (3) & 69.5 (2) &  69.7 (1) \\
faces       & 131.2 (2) & 125.4 (3) & 101.2 (4) &          & 136.6 (1) \\
%sun         & & & & \\
\hline
wins        &         0 &         0 &         4 & 0        &         9 \\
\hline 
\end{tabular}
\end{center}
\caption{Results, given as the area under the number of queries-inlier rate graph. The numbers in brackets give the positions. The results of \citet{hospedales:finding} have been included where available.}
\label{fig:classification}
\end{table*}


\begin{table*}[t]
\begin{center}
\begin{tabular}{|r|c|c|c|c|c|}
\hline
Problem & Random & Entropy & Likelihood & \citet{hospedales:finding} & $P(\mbox{wrong})$ \\
\hline
glass       &    581.1 (3) &    480.9 (4) &    611.1 (1) &            &    598.5 (2) \\
ecoli       &    946.6 (3) &    793.8 (4) &   1057.2 (1) &            &   1011.7 (2) \\
%yeast       &   1631.7 (3) &   1561.0 (4) &   1829.9 (1) &            &   1651.3 (2) \\
segment     &    875.2 (3) &    665.2 (4) &    991.2 (1) &            &    945.4 (2) \\
pageblocks  &    535.8 (4) &    537.1 (3) &    735.6 (1) &            &    629.4 (2) \\
covertype   &    983.8 (2) &    825.8 (4) &    978.2 (3) &            &    993.2 (1) \\
thyroid     &    397.2 (4) &    417.8 (2) &    420.4 (1) &            &    409.5 (3) \\ 
winequality &    695.5 (3) &    603.2 (4) &    837.2 (1) &            &    714.2 (2) \\ 
letters     &   3580.0 (3) &    367.0 (4) &   4443.4 (1) &            &   3848.8 (2) \\ 
shuttle     &    486.2 (4) &    423.5 (5) &    950.5 (1) &  933.2 (2) &    923.4 (3) \\ 
kdd99       &   1490.6 (4) &   1857.0 (3) &   2418.0 (2) &            &   2546.1 (1) \\
gait        &   1170.5 (5) &   1183.8 (3) &   1171.7 (4) & 1253.1 (1) &   1241.9 (2) \\
digits      &    915.2 (5) &    974.0 (4) &   1060.2 (3) & 1207.4 (1) &   1133.6 (2) \\
faces       & 183859.9 (3) & 193598.0 (2) & 179906.6 (4) &            & 194776.3 (1) \\
%sun         & & & & \\
\hline 
\end{tabular}
\end{center}
\caption{Results, given as the area under the number of queries-discovered classes graph. The numbers in brackets give the positions. The results of \citet{hospedales:finding} have been included where available.}
\label{fig:discovery}
\end{table*}


\noindent Results are given by the graphs in Figure \ref{fig:graphs:classification}, with discovery graphs additionally given in Figure \ref{fig:graphs:discovery}.
Table \ref{fig:classification} summarises the classification performance by giving the area under the graph; Table \ref{fig:discovery} does similarly for discovery performance.
The classification graphs give the balanced inlier rate of the classifier trained after $x$ queries, whilst the discovery graphs give the number of classes found after $x$ queries.
In both cases an average of many runs is presented.
The presented approach is the best for $9$ out of $14$ problems.
Its nearest competitor is \emph{likelihood}, which wins the remaining $4$.
In the scenarios in which it misses first place $P(\mbox{wrong})$ always comes second - it is \emph{consistently} good.
The same can not be said for likelihood, which on two occasions comes last.
An approximate ordering by complexity has been applied to the problems, with the last few being scenarios where active learning is of the greatest value - for all of these examples $P(\mbox{wrong})$ takes the lead.
It wins for four of the six vision problems, \emph{segment} and \emph{letters} being the exceptions.

The \emph{faces} data set is clearly the most challenging.
It is a naturally imbalanced data set, where instances with less than $10$ entries have been culled\footnote{Note that culling is for the entire data set, whilst separation into training and testing was purely random, so classes can have less than 10 entries in the pool.}.
This chops off its thick tailed class size distribution - $47\%$ of the data set has less than $20$ items in the training set, meaning that a random selection has almost even odds of drawing from an approximately uniform set.
As a result \emph{random} does very well, as when it draws from a uniform distribution random selection has a good chance of finding a new class with every query.
It only obtains second place however, with $P(\mbox{wrong})$ in first, which is a strong result - \emph{entropy} and \emph{likelihood} both fail to even match \emph{random}.
Both random and $P(\mbox{wrong})$ perform random selection at the start - on average $P(\mbox{wrong})$ finds $72.0$ individuals after $100$ queries, whilst random manages $68.1$.
This demonstrates that $P(\mbox{wrong})$ is focused on discovery, more so than random.
The likelihood approach is comparable to random, at $68.4$ classes discovered after $100$ queries, whilst the entropy approach takes the lead, finding $76.0$ on average.
Entropy does poorly despite finding more people however - it focuses on refining the initial query area, and ignores the rest of the search space.

The \emph{segment} data set exemplifies the data term for the simultaneous segmentation and labelling of both \emph{things} and \emph{stuff} in an image \citep{picard:vision}.
It explores the first step of such an approach, where a label is assigned to each pixel independently, before regularisation is applied, typically by some kind of conditional random field \citep{ladicky:associative}.
The presented approach narrowly losses out to the likelihood approach.
As shown in Figure \ref{fig:graphs:classification} $P(\mbox{wrong})$ matches, and slightly exceeds, likelihood most of the time, except for an area later in the query sequence where likelihood demonstrates an advantage.
This occurs after a region where likelihood is doing much better at discovery (Figure \ref{fig:graphs:discovery}), suggesting that likelihood, which is always focused on discovery, gains an advantage at this time because $P(\mbox{wrong})$ is focusing on boundary refinement before it has discovered all classes.
Using a DP prior on the classes, an assumption that class sizes have a logarithmic falloff, is not satisfied by this data set - it has several large classes, which are the \emph{stuff}, whilst the \emph{things} are made up of many smaller but similarly sized classes.
Such a mismatch between the prior and the data leads $P(\mbox{wrong})$ to incorrectly balance the goals of boundary refinement and discovery, though not by much.
This problem also highlights a further issue - it does not make sense to ask the oracle for the label of a single pixel.
In practise, given algorithms such as GrabCut \citep{rother:grabcut}, a user would be better utilised to label a large area of an image for each query.
Such scenarios invite an active learner that selects bags of exemplars to label, rather than a single label each time.


\newcommand{\numimage}[2]{\begin{minipage}{0.058\linewidth}\centering\footnotesize\includegraphics[width=\linewidth]{#1}\\#2\end{minipage}}

\begin{figure*}[t]
\centering
\raisebox{-0.4cm}{
\begin{sideways}
$P(\mbox{wrong})$
\end{sideways}}
\numimage{gait_img/gait_125.png}{1}
\numimage{gait_img/gait_329.png}{2}
\numimage{gait_img/gait_943.png}{3}
\numimage{gait_img/gait_265.png}{4}
\numimage{gait_img/gait_357.png}{5}
\numimage{gait_img/gait_1771.png}{6}
\numimage{gait_img/gait_141.png}{7}
\numimage{gait_img/gait_2633.png}{8}
\numimage{gait_img/gait_3485.png}{9}
\numimage{gait_img/gait_3483.png}{10}
\numimage{gait_img/gait_2209.png}{11}
\numimage{gait_img/gait_117.png}{12}
\numimage{gait_img/gait_173.png}{13}
\numimage{gait_img/gait_941.png}{14}
\numimage{gait_img/gait_491.png}{15}
\vspace{0.1cm}

\raisebox{-0.28cm}{
\begin{sideways}
Entropy
\end{sideways}}
\numimage{gait_img/gait_47.png}{1}
\numimage{gait_img/gait_227.png}{2}
\numimage{gait_img/gait_79.png}{3}
\numimage{gait_img/gait_2635.png}{4}
\numimage{gait_img/gait_25.png}{5}
\numimage{gait_img/gait_481.png}{6}
\numimage{gait_img/gait_2175.png}{7}
\numimage{gait_img/gait_437.png}{8}
\numimage{gait_img/gait_491.png}{9}
\numimage{gait_img/gait_497.png}{10}
\numimage{gait_img/gait_3061.png}{11}
\numimage{gait_img/gait_1309.png}{12}
\numimage{gait_img/gait_955.png}{13}
\numimage{gait_img/gait_893.png}{14}
\numimage{gait_img/gait_1769.png}{15}
\vspace{0.1cm}

\raisebox{-0.5cm}{
\begin{sideways}
Likelihood
\end{sideways}}
\numimage{gait_img/gait_247.png}{1}
\numimage{gait_img/gait_331.png}{2}
\numimage{gait_img/gait_375.png}{3}
\numimage{gait_img/gait_235.png}{4}
\numimage{gait_img/gait_279.png}{5}
\numimage{gait_img/gait_131.png}{6}
\numimage{gait_img/gait_99.png}{7}
\numimage{gait_img/gait_449.png}{8}
\numimage{gait_img/gait_97.png}{9}
\numimage{gait_img/gait_81.png}{10}
\numimage{gait_img/gait_05.png}{11}
\numimage{gait_img/gait_73.png}{12}
\numimage{gait_img/gait_253.png}{13}
\numimage{gait_img/gait_209.png}{14}
\numimage{gait_img/gait_119.png}{15}
\vspace{0.1cm}

\raisebox{-0.4cm}{
\begin{sideways}
$P(\mbox{wrong})$
\end{sideways}}
\numimage{digits_img/digits_18604.png}{1}
\numimage{digits_img/digits_516.png}{2}
\numimage{digits_img/digits_10260.png}{3}
\numimage{digits_img/digits_3259.png}{4}
\numimage{digits_img/digits_26185.png}{5}
\numimage{digits_img/digits_4006.png}{6}
\numimage{digits_img/digits_7058.png}{7}
\numimage{digits_img/digits_2287.png}{8}
\numimage{digits_img/digits_19646.png}{9}
\numimage{digits_img/digits_21682.png}{10}
\numimage{digits_img/digits_5824.png}{11}
\numimage{digits_img/digits_26293.png}{12}
\numimage{digits_img/digits_38575.png}{13}
\numimage{digits_img/digits_2020.png}{14}
\numimage{digits_img/digits_2343.png}{15}
\vspace{0.1cm}

\raisebox{-0.28cm}{
\begin{sideways}
Entropy
\end{sideways}}
\numimage{digits_img/digits_3700.png}{1}
\numimage{digits_img/digits_02.png}{2}
\numimage{digits_img/digits_798.png}{3}
\numimage{digits_img/digits_6550.png}{4}
\numimage{digits_img/digits_2129.png}{5}
\numimage{digits_img/digits_17210.png}{6}
\numimage{digits_img/digits_7720.png}{7}
\numimage{digits_img/digits_7327.png}{8}
\numimage{digits_img/digits_8098.png}{9}
\numimage{digits_img/digits_1376.png}{10}
\numimage{digits_img/digits_851.png}{11}
\numimage{digits_img/digits_2279.png}{12}
\numimage{digits_img/digits_8335.png}{13}
\numimage{digits_img/digits_406.png}{14}
\numimage{digits_img/digits_1314.png}{15}
\vspace{0.1cm}

\raisebox{-0.5cm}{
\begin{sideways}
Likelihood
\end{sideways}}
\numimage{digits_img/digits_35040.png}{1}
\numimage{digits_img/digits_1449.png}{2}
\numimage{digits_img/digits_2741.png}{3}
\numimage{digits_img/digits_221.png}{4}
\numimage{digits_img/digits_24897.png}{5}
\numimage{digits_img/digits_39458.png}{6}
\numimage{digits_img/digits_1263.png}{7}
\numimage{digits_img/digits_7263.png}{8}
\numimage{digits_img/digits_29571.png}{9}
\numimage{digits_img/digits_38199.png}{10}
\numimage{digits_img/digits_678.png}{11}
\numimage{digits_img/digits_2035.png}{12}
\numimage{digits_img/digits_14723.png}{13}
\numimage{digits_img/digits_29.png}{14}
\numimage{digits_img/digits_1421.png}{15}
\vspace{0.1cm}

\caption{The selected problem instances by one run of $P(\mbox{wrong})$, outlier and entropy, as indicated at the side, for the first 15 queries made. Top three rows show \emph{gait}, bottom three show \emph{digits} - the query number is beneath each image.}
\label{fig:images}
\end{figure*}


The initial selections of two vision-related data sets are visualised in Figure \ref{fig:images}.
% \footnote{Originally \emph{faces} was also going to be included, but it selects a new face with every query, which provides no further insight.}
Comparing the three approaches for the gait problem it is interesting to note the existence of gait energy images that have some kind of glitch, caused by a tracking failure or occlusion.
The likelihood approach spends most of its time exploring these - because it is interested in outliers.
Consequentially, it is wasting its queries on exemplars that are likely to confuse the classifier.
Focusing on the \emph{digits} problem note that $P(\mbox{wrong})$ only explores $4$ classes in the queries shown, the digits $0$, $1$, $2$ and $3$.
Firstly, this data set has been geometrically distributed, with class '$0$' having the most entries, class '$1$' the second most, at half as many, and so on.
So it starts by exploring the most common classes, which makes sense.
Furthermore note that it queries '$2$' repeatedly, yet '$1$' only once, despite '$1$' being twice as common.
This can be explained by the '$1$' class having relatively little variety when the '$2$' class has considerable variety, as demonstrated by the queries - each one is different from the others.
Indeed, the zeroes are subject to the greatest querying intensity, and show considerable variety.


\begin{figure*}[t]
\centering
\subfigure[gait]{\includegraphics[width=0.3\linewidth]{concs/gait}\label{fig:concs:gait}}
\subfigure[digits]{\includegraphics[width=0.3\linewidth]{concs/digits}\label{fig:concs:digits}}
\subfigure[faces]{\includegraphics[width=0.3\linewidth]{concs/faces}\label{fig:concs:faces}}

\caption{Plots of the inferred concentration value normalised by the concentration plus the number of instances that have already been labelled. It reflects how much effort $P(\mbox{wrong})$ is putting in to finding new classes.}
\label{fig:concs}
\end{figure*}

Figure \ref{fig:concs} plots
\begin{align}
\frac{\alpha}{\alpha+q}
\end{align}
against the number of queries made, where $\alpha$ is the inferred concentration and $q$ is the number of labelled exemplars, which is of course equal to the query count.
This is effectively the weight assigned to discovering new classes.
In all cases the expected happens - at the start it is very interested in discovering new classes, but as the number of queries progresses its interest drops and it focuses on refining the boundaries between the known classes.
The \emph{gait} and \emph{digits} problems have a similar number of classes, and have similar profiles to their interest curve.
In the case of \emph{faces} however, which has dramatically more classes, the interest remains high for all of the $1000$ queries shown, as $P(\mbox{wrong})$ is continuing to hunt for new classes.

Discovery performance is given in Figure \ref{fig:graphs:discovery}, with the corresponding areas under the graphs in Table \ref{fig:discovery}.
$P(\mbox{wrong})$ is not intended to optimise discovery.
It instead attempts to obtain a good classifier with few queries, noting that discovering new classes will improve classification performance, as will improving the classification boundaries of existing classes - it effectively makes a trade off between these two actions, and in effect discovery performance is reduced so it can build a better classifier.
The \emph{likelihood} technique contrasts with this as it is only interested in discovery, so it is not surprising that \emph{likelihood} gets the higher area the vast majority of the time.
Indeed, a discovery focused algorithm such as \citet{vatturi:category} is expected to take the crown - for \emph{shuttle} it has a winning score of $970.5$.
For the last $3$ problems the presented takes the lead.
This certainly makes sense for \emph{faces}, as the high class count means that a discovery-oriented approach is preferred, so the presented chooses to focus on discovery rather than boundary refinement.


\begin{figure}
\centering
\includegraphics[width=0.9\linewidth]{soft/soft.pdf}
\caption{Comparison of different selection strategies. The graph shows the inlier rate of the test set on the $y$ axis, as a function of the number of queries made, on the $x$ axis, noting that the averages of many runs are shown. The area under the graphs is $74.266$ for hard, $74.519$ for soft and $75.891$ for KDE.}
\label{fig:selection}
\end{figure}


To follow up subsection \ref{sub:selection} Figure \ref{fig:selection} demonstrates that soft selection is better than hard selection, using the \emph{glass} problem.
It also includes KDE selection - this involves reweighting the samples using a kernel density estimate (KDE) of the $P(\mbox{wrong})$ weighted pool members (Using Gaussian kernels).
This demonstrates the reasoning behind soft selection, by emulating it deterministically - this reweighting strategy in effect does approximately the same thing as soft selection\footnote{Whilst this strategy can always beat the presented approach it does so by introducing a scale parameter, which has to be selected for each problem. This is inappropriate, as doing multiple runs to find the best parameter obviates the entire purpose of active learning.}.


\begin{figure*}
\centering
\begin{tabular}{cc}
\raisebox{0.3cm}{\begin{sideways}glass\end{sideways}}\includegraphics[width=0.4\linewidth]{graphs/glass-classification.pdf} & \raisebox{0.3cm}{\begin{sideways}letters\end{sideways}}\includegraphics[width=0.4\linewidth]{graphs/letters-classification.pdf} \\
\raisebox{0.3cm}{\begin{sideways}ecoli\end{sideways}}\includegraphics[width=0.4\linewidth]{graphs/ecoli-classification.pdf} & \raisebox{0.3cm}{\begin{sideways}shuttle\end{sideways}}\includegraphics[width=0.4\linewidth]{graphs/shuttle-classification.pdf} \\
\raisebox{0.3cm}{\begin{sideways}segment\end{sideways}}\includegraphics[width=0.4\linewidth]{graphs/segment-classification.pdf} & \raisebox{0.3cm}{\begin{sideways}kdd99\end{sideways}}\includegraphics[width=0.4\linewidth]{graphs/kdd99-classification.pdf} \\
\raisebox{0.3cm}{\begin{sideways}pageblocks\end{sideways}}\includegraphics[width=0.4\linewidth]{graphs/pageblocks-classification.pdf} & \raisebox{0.3cm}{\begin{sideways}gait\end{sideways}}\includegraphics[width=0.4\linewidth]{graphs/gait-classification.pdf} \\
\raisebox{0.3cm}{\begin{sideways}covertype\end{sideways}}\includegraphics[width=0.4\linewidth]{graphs/covertype-classification.pdf} & \raisebox{0.3cm}{\begin{sideways}digits\end{sideways}}\includegraphics[width=0.4\linewidth]{graphs/digits-classification.pdf} \\
\raisebox{0.3cm}{\begin{sideways}thyroid\end{sideways}}\includegraphics[width=0.4\linewidth]{graphs/thyroid-classification.pdf} & \raisebox{0.3cm}{\begin{sideways}faces\end{sideways}}\includegraphics[width=0.4\linewidth]{graphs/faces-classification.pdf} \\
\raisebox{0.3cm}{\begin{sideways}winequality\end{sideways}}\includegraphics[width=0.4\linewidth]{graphs/winequality-classification.pdf} & \includegraphics[width=0.2\linewidth]{graphs/key.pdf}\\
\end{tabular}
\caption{Graphs of inlier rate against number of queries, to present the classification performance of the algorithm.}
\label{fig:graphs:classification}
\end{figure*}


\begin{figure*}
\centering
\begin{tabular}{cc}
\raisebox{0.3cm}{\begin{sideways}glass\end{sideways}}\includegraphics[width=0.4\linewidth]{graphs/glass-discovery.pdf} & \raisebox{0.3cm}{\begin{sideways}letters\end{sideways}}\includegraphics[width=0.4\linewidth]{graphs/letters-discovery.pdf} \\
\raisebox{0.3cm}{\begin{sideways}ecoli\end{sideways}}\includegraphics[width=0.4\linewidth]{graphs/ecoli-discovery.pdf} & \raisebox{0.3cm}{\begin{sideways}shuttle\end{sideways}}\includegraphics[width=0.4\linewidth]{graphs/shuttle-discovery.pdf} \\
\raisebox{0.3cm}{\begin{sideways}segment\end{sideways}}\includegraphics[width=0.4\linewidth]{graphs/segment-discovery.pdf} & \raisebox{0.3cm}{\begin{sideways}kdd99\end{sideways}}\includegraphics[width=0.4\linewidth]{graphs/kdd99-discovery.pdf} \\
\raisebox{0.3cm}{\begin{sideways}pageblocks\end{sideways}}\includegraphics[width=0.4\linewidth]{graphs/pageblocks-discovery.pdf} & \raisebox{0.3cm}{\begin{sideways}gait\end{sideways}}\includegraphics[width=0.4\linewidth]{graphs/gait-discovery.pdf} \\
\raisebox{0.3cm}{\begin{sideways}covertype\end{sideways}}\includegraphics[width=0.4\linewidth]{graphs/covertype-discovery.pdf} & \raisebox{0.3cm}{\begin{sideways}digits\end{sideways}}\includegraphics[width=0.4\linewidth]{graphs/digits-discovery.pdf} \\
\raisebox{0.3cm}{\begin{sideways}thyroid\end{sideways}}\includegraphics[width=0.4\linewidth]{graphs/thyroid-discovery.pdf} & \raisebox{0.3cm}{\begin{sideways}faces\end{sideways}}\includegraphics[width=0.4\linewidth]{graphs/faces-discovery.pdf} \\
\raisebox{0.3cm}{\begin{sideways}winequality\end{sideways}}\includegraphics[width=0.4\linewidth]{graphs/winequality-discovery.pdf} & \includegraphics[width=0.2\linewidth]{graphs/key.pdf}\\
\end{tabular}
\caption{Graphs of classes found against number of queries, to present the discovery performance of the algorithm.}
\label{fig:graphs:discovery}
\end{figure*}



\section{Conclusions}
\label{sec:conc}

A state of the art active learning criterion has been presented and analysed, backed up by extensive results.
It has all the properties that are desired for real world use:
\begin{itemize}
\item It both discovers unknown classes and refines the boundary between the known, automatically balancing these goals to maximise classification performance.
\item The prior over concentration is the only parameter, and it does not need tuning - it was left as $\Gamma(1,1)$ throughout.
\item Consistent top-tear performance on every problem tried. This and the above mean that it can be used without modification on many problems. Given the nature of active learning, where trying different approaches mitigates its purpose, this confidence to treat $P(\mbox{wrong})$ as a black box is essential.
\end{itemize}

\noindent There are some limitations with $P(\mbox{wrong})$.
Firstly, it is designed to work with unbalanced data - if run with balanced data it will continue to work, but random selection will typically do better.
It aims to build as good a classifier as it can with the least number of queries - this is not the same as trying to discover one instance of every class.
If discovery is the aim then better approaches exist, though there is some evidence that for certain problems, such as \emph{faces}, $P(\mbox{wrong})$ can do better than some discovery oriented approaches at discovery.
Finally, the classifier needs to provide probabilistic information, though this is typically not an issue, as all generative approaches do so by definition, whilst discriminative approaches can provide it in some cases, e.g. random forests \citep{ho:random,breiman:random}, or be altered to provide it in others, e.g. support vector machines \citep{boser:training,platt:probabilistic}

Future work could consider changes to the core algorithm, to improve performance.
Alternative loss functions or a different QBC formulation for instance.
This approach can be adjusted to other scenarios - \citet{loy:stream} already applied a variant of $P(\mbox{wrong})$ to stream-based active learning, with a Pitman-Yor assumption instead of a Dirichlet process assumption and a QBC-like selection strategy.
In demonstrating a (slight) advantage from using a Pitman-Yor process this suggests using more sophisticated priors that better match the expected structure of the data\footnote{There is even an interesting human interface issue of presenting such priors to a non-expert, such that they can communicate what they already know about a specific problem.}.
Whilst separation from the classification model is a definite advantage there are scenarios in which a tighter integration would prove beneficial.
Variations designed for semi- or weak- supervision would be invaluable.



\bibliographystyle{apalike}
\bibliography{video.bib}



\appendix

\section{Alternative choices}
\label{sec:alt}

We now discuss some of the alternatives to the presented approach that were considered.
Firstly, as discussed in subsection \ref{sub:selection}, one variant lead to an improvement, specifically soft selection over hard selection.
Soft selection can be taken further - a parameter can be introduced as a power of the $P(\mbox{wrong})$ value, to emphasis or de-emphasis large values.
This can be tuned to get better results, but as a problem specific parameter it is of no value to active learning, as parameter tuning is incompatible with a single set of queries.
The KDE variant in figure \ref{fig:selection} is similar, except its parameter is fatally sensitive.

The probability of being wrong can be interpreted as an expectation over zero-one loss - alternative loss functions can be considered.
Hinge loss for a multinomial distribution can be defined as the difference between the probability of the correct answer and the highest probability in the distribution, which is $0$ if the correct answer has the greatest probability.
It often undermined performance however.

Query by committee (QBC) was explored by \citet{loy:stream}; however, their formulation really served as a probabilistic selection threshold function.
Using multiple models it can be formulated to measure variance, so that $P(\mbox{wrong})$ also focuses on areas with high model uncertainty\footnote{With KDE this is obtained by training several classifiers on bootstrap samples from the training set. This achieves the goal of measuring model variance, but damages performance, so a fully trained version is kept to do actual classification.}.
Noting that there are two estimates - an estimate of what the actual class membership is, including the possibility of being something new, and an estimate of what the classifier is going to assign, we can use different models from a committee for these two roles.
A QBC variant can then be defined using a committee where all assignment combinations are summed out, so a high QBC $P(\mbox{wrong})$ score is obtained at boundaries between classes, in areas where new classes could be found, and where the current model has high uncertainty.
This unfortunately resulted in too much emphasis being placed on boundary refinement.

For some problems the above variants are better.
The issue is there is no way to predict \emph{which} problems in advance, and for some problems they are much worse.
Active learning is a scenario where you choose a method and apply it to your problem once - multiple runs require that the queries for each be satisfied, which is contrary to the goal.
We therefore present $P(\mbox{wrong})$ as formulated, as it is consistent - it never performs poorly, and usually gives top tier performance.
Future work could consider inferring which data sets work best with different active learners.



\end{document}

