\documentclass{svjour3}                     % onecolumn (standard format)
%\documentclass[smallextended]{svjour3}     % onecolumn (second format)
%\documentclass[twocolumn]{svjour3}         % twocolumn
%
\smartqed  % flush right qed marks, e.g. at end of proof
%
\usepackage{graphicx}
\usepackage{verbatim}
\usepackage{fancyvrb}
\usepackage{algorithmic}
\usepackage{cite}
\usepackage{multirow}
\usepackage{rotating}
\usepackage{subfigure}
\usepackage{float}
\restylefloat{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\bi}{\begin{itemize}}
\newcommand{\ei}{\end{itemize}}
\newcommand{\be}{\begin{enumerate}}
\newcommand{\ee}{\end{enumerate}}
\newcommand{\tion}[1]{\S\ref{tion:#1}}
\newcommand{\eq}[1]{Equation~\ref{eq:#1}}
\newcommand{\fig}[1]{Figure~\ref{fig:#1}}
\newenvironment{smallitem}
 {\setlength{\topsep}{0pt}
  \setlength{\partopsep}{0pt}
  \setlength{\parskip}{0pt}
  \begin{itemize}
   \setlength{\leftmargin}{.2in}
  \setlength{\parsep}{0pt}
  \setlength{\parskip}{0pt}
  \setlength{\itemsep}{0pt}}
 {\end{itemize}}
\newenvironment{smallenum}
 {\setlength{\topsep}{0pt}
  \setlength{\partopsep}{0pt}
  \setlength{\parskip}{0pt}
  \begin{enumerate}
  \setlength{\leftmargin}{.2in}
  \setlength{\parsep}{0pt}
  \setlength{\parskip}{0pt}
  \setlength{\itemsep}{0pt}}
 {\end{enumerate}}

\begin{document}

\section{What is active learning? Why do we need it?}

Active learning (from now on AL) in the simplest terms is to learn a classifier in the settings where data comes unlabeled, but still certain data points can be queried for their labels at a certain cost~\cite{Dasgupta2005, DasguptaL09}.
Considering the fact that there is a huge amount of unlabeled data in various domains (documents off the web, speech samples, images, videos, fault logs etc.) and the almost impossible to afford cost associated with labeling all these data, AL appears as a promising solution~\cite{Dasgupta2005, DasguptaL09, Martina1998, Balcan2006}.
AL picks up particular instances from a pool of unlabeled data points on the basis of their informative power and asks a human annotator for the labels of these points~\cite{Tomanek2009}.
With this approach the amount of data points required to train an accurate classifier is greatly reduced.
In terms of prediction capability and sample complexity, it has been shown that under certain constraints (hypothesis class of homogenous linear separators and uniformly distributed seperable data on the unit sphere), AL achieves the same error rate as a linear supervised learner with an exponentially lower sample complexity.
In this introduction, we will provide a summary of the theory behind active learning as well as proposed methodologies for this theory and we will also include a section providing the state-of-the-art technologies for the application of active learning.

\section{Theory and Methodologies}
The aim in AL settings is to learn an unsupervised learner that is as accurate as supervised learner, yet with a considerable less sample complexity.
For attaining this goal, recent literature proposes two methodologies~\cite{Dasgupta2008, DasguptaL09}:
\begin{itemize}
\item \textbf{Efficient search through hypothesis space:} We can think of the possible set of classifiers as a hypothesis set.
Our aim in this methodology is to choose the points that would help us shrink this hypothesis space the most, i.e. at each new point, the set of learners that are roughly consistent with the data points seen so far shrinks more.
\item \textbf{Exploiting the cluster structure in data:} This method is based on the assumption that unlabeled data points form clusters and by effectively discovering these clusters, we can use querrying strategies to label instances in each cluster. 
A very simple example is to form clusters of data (via clusterer x), querry random points in each cluster and assign the majority label of queried points as the label of the cluster.
\end{itemize}

Current theory tells us that AL can be applied anywhere, where supervised learning can be applied.
However, although AL seems like an easy to apply approach, it faces a unique problem called sampling bias, which separates it from other learning models.
\begin{itemize}
\item \textbf{Sampling bias:} A standard AL scheme may start with randomly selected points to get an intuition of the decision boundary and continually select points that are closer and closer to its current decision boundary.
Thereby, in the later stages of learning, AL scheme may significantly diverge from discovering the underlying distribution of data and may fall victim of its assumed decision boundary~\cite{Cohn1994}. 
\end{itemize}


\section{Technologies}
After providing a summary of active learning and commonly proposed methodologies, in this section we will provide the technologies proposed in the recent years for AL related problems.
\begin{itemize}
\item \textbf{Hierarchical sampling for active learning:} Dasgupta et. al. make use of cluster structure in the data~\cite{Dasgupta2008}. The summary of their approach is: Hierarchicaly cluster data into a tree structure, querry random instances in the tree, keep statistics (purity/impurity) for each subtree, eliminate the pure clusters (since we think they are pure enough), then query some more instances and follow the same procedure.
For assigning a label to a cluster use majority voting of the labeled instances in the cluster.
\item \textbf{Active learning for biomedical citation screening:} Authors use different oracles to predict the same point (3 oracles) and ask the experts only the points where the oracles differ.
The original idea in this paper is to let expert not only tell the labels but also weight or even delete some of the features (feature weighting)~\cite{Wallace2010}.
\item \textbf{Multilabel learning by exploiting label dependency:} Zhang et. al. propose building Bayes-Net structure on the data labels to discover the dependencies among different labels.
Then they remove features responsible for dependencies among different labels, thereby making each class indepent of one another.
Finally they build another Bayes-Net on each independent class for prediction.
(I do not think that this is directly an active learning solution, since it actually uses labels, i.e. supervised learning. However, it was one of the conference papers that you asked us to read.) 
\item \textbf{Proper unit selection in active learning:} Due to sampling bias missed class effect (complete miss of discovering a class) occurs and authors show that missed class effect can be avoided by changing the granularity level of instance sampling~\cite{Tomanek2009}.
They work on text mining and change granularity level from single words to sentences or word groups.
\item \textbf{Multi-view multi-label active learning:} This work is a solution for multilabel problems (attributes define more than one labels/classes, as in bio-metrics and image processing)~\cite{Zhang2009}.
Authors propose making use of multiple learners and exploiting their agreement/disagreement for the same label set for finding which points to query.  
\item \textbf{Agnostic active learning:} Agnostic sampling is a more robust version of selective sampling. Selective sampling may delete a hypothesis/learner depending on a single query.
However, agnostic learner keeps history of learners and requires multiple query fails for a learner to be deleted from hypothesis set~\cite{Balcan2006}.
Reported to work particularly well in the noisy data, provided that sample points are i.i.d.
\item \textbf{Coarse sample complexit bounds for active learning:} This is a rather theoretical work on sample complexity of active learning.
Authors generalize the complexity measure of homogenous linear classifiers to non-homogenous classifiers~\cite{Dasgupta2005}.
They propose a complexity measure, which takes into account: Distribution of input space, specific target learner and desired error rate.
\item \textbf{Analysis of greedy active learning:} Dasgupta proposes using a greedy method for choosing the learner among the hypothesis space~\cite{Dasgupta2005}. 
Greedily choose the set of learners that most evenly divides the instace space. 
This is a sub-optimal solution and is limited to low dimensional spaces and does not guarantee the lowest number of queries, but it reduces the instance complexity.
\item \textbf{The use of simulated experts:} Since experts are not very easy to find, the study proposes replacing an expert with a learner like Naive Bayes~\cite{Compton1995}.
The idea behind is that experts cannot give a conclusive answer regarding their labeling, hence they can be simulated by algorithms.
since it uses algorithms for labeling, a certain initial amount of data is necessary.
\end{itemize}

\section{Summary of the summary}
The most basic list of technologies exploited by all the above papers (all after 2000 and the important ones before 2000) is:
\begin{itemize}
\item Hierarchical clusterers
\item Majority voting of multiple learners
\item Bayes-net to discover data structure
\item Change of sampling granularity (as solution for sampling bias)
\item Agreement disagreement among multiple learners
\item Agnostic sampling (multiple fails of learner to be deleted)
\item Sample complexity measurement
\item Greedy selection methods for hypothesis space
\item Replace human expert with a learner
\end{itemize}

\bibliographystyle{ieeetr}
\bibliography{references}


\end{document}