\section{Sampling Techniques}

We now take a look at several available techniques to aid the selection of points to label.

\subsection{The Problems of Random Sampling}

General active learning algorithms call for a random sampling of the data, but random sampling is not an optimal sampling policy for several reasons.  Labeling data points is an expensive operation, so it is unwise to label areas where misclassification is not possible. Dasgupta and Hsu state that the number of queries required for a proper analysis when using random queries is $O(\frac{1}{\xi})$ where $\xi$ is the desired error rate.\cite{Dasgupta2008}  Cohn et al suggests that labeling data points will be most useful in the {\bf region of uncertainty}, an area defined as the region in the sample space where misclassification is still possible based on information already gathered \cite{Cohn1994}.   The cost of labeling in this region is more rewarding than labeling in an area where misclassification is unlikely occur.  Our project can benefit from a sampling technique that finds a balance between exploration and exploitation of the dataset.

\subsection{Exploration vs. Exploitation}
\begin{figure}[htb]
\begin{center}
\includegraphics[width=0.8\textwidth]{explorevsexploit.eps}
\end{center}
\caption{An random sampling technique favoring exploration (left) vs. a simple sampling algorithm that favors exploitation (right) \cite{Wallace2010}}
\label{fig:ExploreVsExploit}
\end{figure}

An analysis of sampling algorithm will frequently begin to discuss the  algorithm's balance between the exploration and exploitation of their selection of data points to be labeled by the expert.  Tomanek et. al. describes active learning methods as being a highly exploitative strategy since active learning seeks to thoroughly explore the region of uncertainty defined by Cohn above. The trade off is that the method may not explore regions further away from the region of uncertainty.    Wallace and Tomanek both express concerns that clusters may still exist in this unexplored region and refer to this phenomenon as the \textit{missed-cluster effect}.  This concern is demonstrated in Figure \ref{fig:ExploreVsExploit}.  We see that the random sampling algorithm demonstrated on the left found all regions of interest while requesting labels for many unnecessary points.  The simple sampling algorithm demonstrated on the right concentrated requests for labels to the region of uncertainty but failed to identify a cluster in the unexplored region of the data set.   Both authors assert the need for sampling techniques that properly balance exploration and exploitation of a data set.

\subsection{Hierarchical Sampling}

Dasgupta et. al. present an active learning algorithm shown in Figure\ref{algorithm:Hierarchical} where they use inherent cluster structures in the data \cite{Dasgupta2008}.  Their method begins by applying hierarchical clustering on the data.  The root of the forming tree is assumed to be the cluster containing all of the instances.  Random instances in the tree are queried for their labels and, depending on these labels, statistics for each pruning of the tree to see whether a particular pruning is mixed with different labels or is relatively pure with one class.  Labeling can be stopped at any point and the clusters are assigned their labels depending on the majority vote.  The algorithm halts when the pruning of the trees is statistically judged to be pure.  Their method is statistically consistent and never worse than supervised techniques.  When compared to the baseline active learning method of random sampling, it reduces the number of points queried to $O(\sqrt{\frac{1}{\xi}\log \frac{1}{\xi} })$  The success method depends on how well the actual labels align with the cluster structure in the data.

\begin{figure}[h!]
%\input{hierarchicalSamplingAlgorithm}
\includegraphics[scale=0.6]{HierarchicalSampling.eps}
\caption{Hierarchical Sampling Algorithm \cite{Dasgupta2008}}
\label{algorithm:Hierarchical}
\end{figure}
 

\subsection{Greedy Sampling}

Dasgupta suggests a greedy approach that makes use of Vapnik-Chervonenkis (VC) theory to selecting data points to be labeled\cite{Dasgupta2004}. VC theory attempts to use a statistical point of view to describe learning processes.  The greedy strategy selects data points to label by choosing points that are equally weighted as a positive and negative point.  Dasgupta formally defines this as follows:

\begin{quotation}
Let $S \subseteq  \hat{H}$ be the current version space.  For each unlabeled $x_i$, let $S_{i}^+$ be the hypotheses which label $x_i$ positive and $S_i^-$ the ones which label it negative.  Pick the $x_i$ for which these sets are most nearly equal in $\pi$-mass, that is, for which min$\lbrace\pi$($S_i^2$,$\pi$($S_i^+$)$\rbrace$ is largest \cite{Dasgupta2004}.
\end{quotation}

The greedy choice made by his approach, to always ask for the label which most evenly divides the space, satisfies the greedy choice property.  This does not necessarily minimize the points that must be labeled but typically requires at most O(ln $ \mid H \mid $, where $H$ is the hypothesis space.
Dasgupta's binary search of the space requires $d log m$ labels where $d$ is the VC dimension and $m$ is the total number of data points.   The VC dimension is defined as a measure of the largest data set of cardinality $h$ that can be shattered  (the positive and negative hypotheses are separated) by classification model $f$.

\subsection{Agnostic Sampling}

Balcan et. al.'s $A^2$ agnostic sampling algorithm shown in Figure \ref{algorithm:Agnostic}  is the first to be proposed as an active learning algorithm that works in the presence of any form of (limited) noise. The assumption of the algorithm is that samples come drawn from a fixed distribution. $ A^{2} $ (Agnostic Active) is proposed to be a robust version of the selective sampling proposed by Cohn et. al. The difference of $ A^{2} $ to selective sampling is the agnostic approach taken by the algorithm that does not eliminate a hypothesis based on the result of a single label query.  The authors show that $ A^{2} $ achieves exponential speedups in several settings previously analyzed without a noise.  $ A^{2} $ performs particularly well for the simple case of learning threshold functions (this holds for arbitrary distributions as well, provided the noise rate is low). The expected number of queries required for the algorithm is $O(\frac{\eta^2ln\frac{1}{\delta}}{\xi^2})$ where $\xi$ is the desired error rate, $\eta$ is the noise rate, and $\xi$ is a confidence parameter.

\begin{figure}
\caption{$A^2$ Agnostic Sampling algorithm \cite{Balcan2006} }
\label{algorithm:Agnostic}
\includegraphics[scale=0.6]{AgnosticSampling.eps}
%\input{agnosticSamplingAlgorithm}
\end{figure}

\subsection{Query by Committee}

\begin{figure}
\caption{Query by Committee algorithm for a committee of two \cite{FREUND1997}}
\label{algorithm:QueryBC}
\includegraphics[scale=0.6]{QueryByCommittee.eps}
%\input{queryByCommittee}
\end{figure}

The object of the Query By Committee (QBC) is to use quick multiple prediction methods (the committee) to guess a label for each data point.  The data point is identified to be labeled when the committee is unable to find a consensus regarding the data points label.  The intention of the algorithm is to filter the most informative examples from the set of data points.  We discuss Fruend's algorithm for Query By Committee below. 
 
The algorithm begins by calling an oracle \textbf{Sample} to retrieve an unlabeled data point $x$ from the set of data points.  The algorithm proceeds to call prediction methods to quickly guess the label of $x$.  Freund defines a prediction method \textbf{Gibbs} that randomly chooses a hypothesis h from the possible classes (or labels). The data point is rejected for labeling if the committee of prediction methods agree on a label.  The data point is labeled by the oracle \textbf{Label} if the committee disagrees on the label. 


\subsection{Iterative Approach to Selective Sampling}

Warmuth applies an iterative approach to selectively sampling previously unlabeled data for finding molecules that will bind with a particular molecule \cite{Warmuth2002}.  5\% batches of the data are first chosen at random until positive and negative batches are found.  All further batches are chosen using several sampling strategies detailed below. Positive is the goal state for a batch since those compounds  will bind. Labels were hidden from learn in order to simulate the experiment and performance is benchmarked by reporting false positives.  The sampling strategies were as follows:
\bi \item \textbf{Nearest Neighbor:} The data is normalized and batches are considered for being closest to the already labeled batches' hyperplanes.
\item \textbf{Support Vector Machine (SVM):} The batch is selected by choosing the maximum margin hyperplane produced by a support vector machine.
\item \textbf{Voted Perceptron (VoPerc): } The strategy computes the weight vector of each example  and stores these vectors.  The vectors recorded in each pass are recorded for each 100 random permutations of the labeled examples.  Each weight vector is assigned a $\pm$ vote where the prediction on an example is positive if the resultant vote is greater than zero and negative otherwise.  Unlabeled examples are chosen that are closest to zero.
\ei

All three sampling strategies performed similarly when comparing true and false positives their respective strategies. The authors declare VoPerc as the best performing technique due to having a smaller variance in true and false positives than the other two techniques.

