\section{Introduction}
The objective of this literature is to review the topic of Active Learning.  We wish to give special attention to techniques that minimize the amount of time required for a user to probe sub-samples of the data to accurately classify code modules as being "defective" or "non-defective".  We focus our investigation on sampling techniques to minimize the number of queries required by the classifier and classification methods to maximize the accuracy of the classification.

\pagebreak

\section{Active Learning}
\subsection{What is Active Learning?}
There is a large amount of data available in unlimited formats such as software engineering data.  These pieces of data are all unlabeled and labeling all of these data points can be expensive. A heuristic to assist in minimizing the quantity of data points to be labeled would be helpful when classifying data.  We introduce \textit{active learning} as a promising solution.

Active learning shares similarities with supervised and unsupervised learning.  Active learning and supervised learning techniques both attempt to learn a accurate classifier to fit a data set.  Labeling points in active learning and unsupervised learning techniques are expensive and should be minimized.  The goal of an active learner should be to obtain an accurate classifier with a lower computational cost than a standard supervised learning algorithm by minimizing the number of queries on data points.

\begin{figure}[h!]
\caption{An Active Learning Heuristic suggested by Dasgupta \cite{DasguptaL09}}
\label{algorithm:ALHeuristic}
\includegraphics[scale=0.6]{ActiveLearningHeuristic.eps}
%\input{activeLearningHeuristic}
\end{figure}

\subsection{Motivation for Active Learning}

Dasgupta describes two ways to explain when active learning is helpful \cite{DasguptaL09}.  Active learning can provide means for an efficient search through a hypothesis space.  Each request for a label may help to shrink the set of plausible classifiers, and active learning techniques can help to select the points that would help to shrink that set as quickly as possible.  This goal of selecting minimal points motivates the investigation of effective sampling techniques to aid in the selection of data points.  Active learning can also help to exploit a cluster structure in data.  A primitive method of constructing classifiers is to find clusters in the data, label selected data points within the cluster, and assign each cluster to the majority class of the labeled points.  The classifier is constructed on the results of these clusters.

\subsection{Applying Active Learning to Software Engineering}

There are considerations that must be faced when applying an active learning technique to software engineering data.  Typical sets of software engineering data are very large, so we must be minimize the complexity of our solution.  A solution with algorithms of low complexity is desirable to minimize the user must wait before providing input.   This consideration is very important for interactive data mining applications where the feature set is updated.  Jakob Nielsen suggests that a second is the limit for the user's flow of thought to continue uninterrupted and ten seconds is the limit for keeping a user's attention focused on dialogue.  Nielsen also states that basic advice regarding these response times have been the same for 30 years. \cite{NIELSEN1993}  A user who must give input on a set of feature sets may have focused their attention on other topics in the time required for the application to finish. 
 
One focus should be to identify clustering and classifier algorithms that minimize their computation complexity while still performing a satisfactory job in their respective domains.  We may also investigate methods of \textit{feature subset selection} to remove attributes that add little value to the classification.  Previous investigations with feature subset selection have found that parts of the training data can be removed without sacrificing the effectiveness of the classifier \cite{Menzies08}.  These investigations have also suggested that simple machine learning algorithms such as Naive Bayes can discover information in defect prediction as well or better than more sophisticated classifiers \cite{Menzies08}.

\begin{figure}[htb]
\begin{center}
\includegraphics[width=0.8\textwidth]{callgraph.eps}
\end{center}
\caption{A function call graph generated in GrammaTech's CodeSurfer source-code analysis tool}
\label{fig:CallGraph}
\end{figure}

We further consider the application of active learning to the typical scientific method: creating a theory, exploration and experimentation of the idea, and formation of a deduction.  We may begin with a single hypothesis  and apply active learning for efficient exploration of interesting instances and data points and quickly reduce the hypothesis space.  The results of our deduction can further lead to more theories to explore in our domain.  Active learning can potentially provide a framework to help us efficiently investigate complex domains including but not limited to software engineering.  Consider existing software engineering tools such as GrammaTech's CodeSurfer and CodeSonar that aim to automate source-code analysis.  These tools augmented with an active learning framework could allow a user to efficiently investigate source code and interactively update their experiment as their hypothesis evolves.  