A Survey of Active Learning Techniques
Tim Menzies, West Virginia University
Kelly D. Cecil, West Virginia University
07/24/10
1  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.

2  Active Learning
2.1  What is Active Learning? 

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.

Figure 1 - An Active Learning Heuristic suggested by Dasgupta [1]
2.2  Motivation for Active Learning
Dasgupta describes two ways to explain when active learning is helpful [1]. 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.
2.3  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. [2] 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. 

Figure 2 - A function call graph generated in GrammaTech’s CodeSurfer source-code analysis tool
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. 

3  Feature Subset Selection
We now investigate methods of feature subset selection to intelligently reduce attributes in data sets.
3.1  Motivation
We earlier discussed the application of active learning to the field of software engineering. Software engineering data sets are typically large batches being input at once and can be very time consuming to process. Feature subset selection algorithms provide a method to reduce the features of a data set to those that are deemed to be the most valuable to the analysis. This reduction can lead to higher true positive and lower false positive rates while significantly reducing the time required to analyze the data set.
3.2  Principle Component Analysis
Principle Component Analysis is a feature subset selection technique that employees Eigen-vectors to find the most significant features of the data [4]. 

3.3  Term Frequency-Inverse Document Frequency
Term Frequency-Inverse Document Frequency (tf-idf) is a simple feature subset selection technique that traditionally been applied to text document mining but has been applied to search-based software engineering with much success.

Figure 3 - An example function [5].

Figure 4 - Formulas for tf, idf, and the final tf-idf feature vector.
The weight of a term expresses the importance of the term in a document relevant to the entire collection of documents. A term that occurs rarely in the entire collection of documents but frequently in a module would receive a high weight, while a term that appears frequently in all modules in the collection such as programming language constructs would receive a low weight and could be safely removed from our feature selection.
Table 1 demonstrates Principle Component Analysis and tf-idf with a combination of clustering algorithms. It is worth noting that tf-idf requires less time than Principle Component Analysis for each respective clustering algorithm. tf-idf performs well with K-means and GenIc clustering algorithms when comparing information gain to their Principle Componenent Analysis counterparts. 
4  Sampling Techniques
We now take a look at several available techniques to aid the selection of points to label.
4.1  The Problems of Random Sampling

4.2  Exploration vs. Exploitation

Figure 5 - An random sampling technique favoring exploration (left) vs. a simple sampling algorithm that favors exploitation (right) [8]

4.3  Hierarchical Sampling

Figure 6 - Hierarchical Sampling Algorithm [6]
4.4  Greedy Sampling
Dasgupta suggests a greedy approach that makes use of Vapnik-Chervonenkis (VC) theory to selecting data points to be labeled[9]. 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:

4.5  Agnostic Sampling

Figure 8 -  Agnostic Sampling algorithm [10] 
4.6  Query by Committee

Figure 9 - Query by Committee algorithm for a committee of two [11]
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. 

4.7  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 [12]. 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: 

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.

5  Clustering Methods
5.1  Motivation
The previous section discussed various sampling methods for choosing the most useful queries in an active learning system and their strengths (situations in which they might excel) and weaknesses (queries required for a proper analysis.) We would clearly benefit from using clustering techniques to identify areas of interest and ensure that we further achieve the goal of balancing exploration and exploitation. Our ideal clustering algorithm would have low asymptotic complexity while providing a optimal grouping of similar data points. 
5.2  k-means

Figure 10 - Pseudo-code for K-means Algorithm
K-means is a clustering algorithm that seeks to partition points into k clusters with the nearest mean point. The k-means algorithm has an asymptotic complexity of O(kN) where k is the number of clusters and N is the number of data points in the input set. K-means has an attractive complexity, but it is important to note that the algorithm may have to be executed multiple times to find the best value of k for the given data.
5.3  GenIc

Figure 11 - Pseudo-code for GenIc Algorithm [13]

GenIc computes the "fitness" of each each center as a function of the number of points assigned to the center. The algorithm computes the probability of the center’s survival and randomly selects a value between 0 and 1 from a uniform distribution to determine if a center is removed. The fittest generally survive to the next generation, but old centers are occasionally replaced with new centers.
5.4  Canopy

Figure 12 - An example of five canopies [14]
The canopy clustering technique is a technique that addresses situations where there can be a large number of points in the data set, each point can have many features, and there can be many clusters to discover in the data set. The canopy seeks to solve all three problems by dividing the clustering into a two stage process. 
The first stage uses some cheap distance or similarity measure to create overlapping subsets called "canopies." Canopies are defined to be a subset of points that are calculated by some estimated distance or similarity measure to be within some distance threshold from a central point [14]. Points may reside in multiple canopies (canopies may overlap), but all points must reside in at least one canopy. An assumption is made that points that are not in the same canopy can not be in the same cluster. 
Figure Error: Reference source not found illustrates an example provided by McCallum et. al. [] of five clusters and their canopies. A solid circle indicates the outer thresholds of the canopy. Points labeled A, B, C, D, and E are the center points of the canopies. The doted circles within each canopy designate an area is excluded for consideration to be the center of a new canopy. 
The second stage uses a traditional clustering algorithm such as K-means using an accurate distance or similarity measure with the restriction that we only measure distances between points that reside in the same canopy (and assume points of different canopies to have an infinite distance). 

5.5  Compass

Figure 13 - Pseudo-code for Compass Clustering Algorithm
Compass is a clustering algorithm that works by finding two points with a maximum distance from the other in the data set and build a tree structure by pulling data to each of the two extreme points to form two sets. We then recurse on each set until the variance between the layers is less than a determined threshold. The Compass algorithm is very simple, and thus is very quick. The algorithm’s complexity is O(3LN) where L is the number of layers and N is the number of input points. Further research is in progress to investigate the inclusion of early stopping rules in the algorithm to reduce the number of layers of the tree.
5.6  Comparison of Clustering Techniques

k-Means can provide a more reasonable time investment for a single execution of the algorithm, but the algorithm may be ran multiple times in order to find the best number of k clusters to fit the data set. The worst case time of O(3LN) and ability to be updated incrementally makes Compass a strong candidate with respect to computational complexity.

Reducer and Clusterer	Time	InterSim	IntraSim	Gain	
TF-IDF*K-means	17.52	-0.085	141.73	141.82	
TF-IDF*GenIc	3.75	-0.14	141.22	141.36	
PCA*K-means	100.0	0.0	100.0	100.0	
PCA*Canopy	117.49	0.0	99.87	99.87	
PCA*GenIc	11.71	-0.07	99.74	99.81	
TF-IDF*Canopy	6.58	5.02	93.42	88.4	
 
Table 1: Results from a text mining experiment comparing combinations of feature subset reduction and clustering algorithms to more sophisticated methods.

Method	Win	Loss	Tie	
COMPASS	180	0	0	
BestK	100	46	34	
K=16	157	20	3	
K=8	142	25	13	
K=4	115	40	25	
K=2	71	70	39	
K=1	62	82	36	
BISECT4	1	76	103	
BISECT6	30	44	106	
BISECT8	36	39	105	
 
Table 2: Win-Loss-Tie Results for the COCOMO81 Data Set

Method	Win	Loss	Tie	
COMPASS	171	8	1	
BestK	109	7	64	
K=16	125	1	54	
K=8	113	6	61	
K=4	77	13	90	
K=2	162	0	18	
K=1	79	10	91	
BISECT4	0	178	2	
BISECT6	31	85	64	
BISECT8	29	86	65	
 
Table 3: Win-Loss-Tie Results for the Maxwell Data Set
We find in our studies that the Compass clustering algorithm performs significantly better in most cases than k-means and bisection methods. 2 and 3 provide a Win-Tie-Loss (Figure 14) comparison of three clustering methods with varying  clusters based on the magnitude of the relative error (MRE)[15]: 

Foss et al. has demonstrated that using only MRE can lead to an incorrect evaluation of the results in certain situations [15]. Wilcoxon statistics were applied to ensure that these results do not fall into the limitations of MRE. Compass performs significantly better than K-means and bisecting K-means on both data sets. Compass is a very promising algorithm that can provide a small computational complexity while delivering high quality clusters. 

6  Domain Experts
We investigate techniques for machine learning techniques to act as our domain expert.
6.1  Motivation
Compton et al. defines an expert as people whose expertise is scarce and valuable.[16] A human expert can often be difficult to find. Humans are also prone to error and are slow when analyzing large amounts of batch data (i.e. software engineering data). An expert may also possess a bias or may specialize in different strategies than other experts [17]. An active learning scheme may benefit from the input of multiple experts who are capable of processing large amounts of data quickly. 
6.2  The Use of Simulated Experts in Evaluating Knowledge Acquisition
A machine learning algorithm may be used to stand in for a domain expert for cases when a human domain expert is unavailable. The machine learning algorithm is not an ideal substitute of a living, breathing expert, but the simulated expert could improve the knowledge acquisition process. It is important to note that the expert is only as good as the machine learning algorithm governing it’s "opinion" of the data and using only a single expert may not allow the data to be fully explored. Compton[16] and Shaw[17] both suggest the use of multiple experts that can correspond on a problem and "brain-storm" to fully explore their domain of expertise.
6.3  Comparing Conceptual Structures Between Experts
Our experts must be able to communicate with each other if they are to discover on what topics they agree or disagree. Shaw expresses the need for experts to be able to communicate their knowledge of concepts with each other in order to come to a consensus [17]. The author establishes four relationships that can occur between experts: 

Figure 15 - An example of a reperatory (entity-attribute) grid [17]
We can use a reperatory grid (referred to as an entity-attribute grid in Shaw’s literature) as a means of establishing an expert’s knowledge on a topic. Figure 15 shows an example of a reperatory grid. Experts can exchange these reperatory grids to develop a difference grid (shown in Figure 16) to easily establish consensus and conflict between the experts. This difference grid populated by scores of 0 (denoted by blank grid locations) to 5 with lower scores indicating a consensus and higher scores indicating conflicts. Our example shows that our experts agree on concepts in the upper right corner of the grid and show conflict on concepts in the lower left corner of the grid.

Figure 16 - An example of a difference grid [17]
6.4  ID3 and C4.5
C4.5 is a decision tree machine learning algorithm developed by Ross Quinlan that is an extension of the ID3 algorithm that addresses several shortcomings of ID3.

Figure 17 - An example data set to be processed by ID3 [18]

C4.5 extends ID3 by adding the ability to deal with missing data and numeric data and provides pruning of the decision tree.

Figure 18 - An example decision tree produced by the ID3 algorithm [18]
6.5  Naive Bayes

The Naive Bayes algorithm is simple to use in practice, very efficient, and robust against noisy data [19]. The algorithm may be used on raw numeric data using a Gaussian probability density function or on discrete data. A limitation of the Naive Bayes classifier is the assumption of feature independence utilized by the classifier is often violated in the real world. The Naive Bayes classifier works very well despite this limitation. 

Figure 19 - Comparison of Naive Bayes to other algorithms [20]
Testing by Pedro Domingos has found that Naive Bayes performs better than other classification algorithms including C4.5 [20]. Figure 19 shows Domingos’ results comparing Naive Bayes with discretized data (Bayes), Naive Bayes using a Gaussian probability function for the raw numeric data (Gauss), and several other algorithms. Domingos ranked each classifier using 1 to indicate the most accurate algorithm and increasing as accuracy decreases. Naives Bayes with discrete data performs best while Naive Bayes using the Gaussian probability density function ranked second best.
7  Summary
We have investigated the heuristics of an active learning technique and hypothesized about it’s application to complex domains with much focus on software engineering.

References

[4]	L. I. Smith, “A tutorial on principal component analysis.”.

[12]	M. K. Warmuth, G. Rätsch, M. Mathieson, J. Liao, and C. Lemmen, “Active learning in the drug discovery process,” 2002.