\documentclass[journal,compsoc]{IEEEtran}
%\documentclass[onecolumn,12pt,journal,compsoc]{IEEEtran}
%\renewcommand{\baselinestretch}{1.41}

\usepackage[table]{xcolor}
\usepackage{rotating}
\usepackage{latexsym}
\usepackage{amssymb}
% *** CITATION PACKAGES ***
%
\ifCLASSOPTIONcompsoc
  % IEEE Computer Society needs nocompress option
  % requires cite.sty v4.0 or later (November 2003)
  % \usepackage[nocompress]{cite}
\else
  % normal IEEE
  % \usepackage{cite}
\fi

\usepackage{cite,url}

%\usepackage[pdftex]{graphicx}
\usepackage{graphicx}


\usepackage{subfig}
\usepackage{verbatim}
\usepackage{fancyvrb}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{timtricks}

% correct bad hyphenation here
\hyphenation{op-tical net-works semi-conduc-tor}

\begin{document}

\title{Exploiting the Effort Estimation Data Structure for Active Learning}
%to Improve STEAK: Learning Better Case Selection Strategies for Analogy Based Software Cost Estimation}

\author{Ekrem~Kocaguneli,~\IEEEmembership{Student Member,~IEEE,}
		and~Tim~Menzies,~\IEEEmembership{Member,~IEEE,}% <-this % stops a space
\IEEEcompsocitemizethanks{\IEEEcompsocthanksitem Ekrem Kocaguneli, Tim Menzies and Kel Cecil are with the Lane Department of Computer Science and Electrical Engineering, West Virginia University.
E-mail: ekocagun@mix.wvu.edu, tim@menzies.us}% <-this % stops a space
}

\markboth{Journal of IEEE Transactions on Software Engineering,~Vol.~X, No.~Y, SomeMonth~201z}%
{Shell \MakeLowercase{\textit{et al.}}: Bare Demo of IEEEtran.cls for Computer Society Journals}
\IEEEcompsoctitleabstractindextext{
\begin{abstract}
~\\\textit{Background:}
It is assumed that \textit{all} instances of the software effort estimation (SEE) datasets are useful in an analogy-based estimation (ABE) context.
Hence, all instances are labeled.
Also SEE datasets favor certain algorithms.
In~\cite{Keung2011} CART and ABE have been identified as the best performing algorithms.
\\\textit{Motivation:}
Labeling all projects is a costly and time-consuming activity.
If datasets have suitable structure/topology, active learning can guide learners to reduce the labeling cost and time.
\\\textit{Aim:} 
We aim to understand the topology of the effort datasets and define an active learning scheme to guide labeling of instances.
\\\textit{Method:}
We define popularity-based E(k) matrices that identify the order of instances to be labeled.
We augment a standard ABE method (\textit{passiveNN}) with this guiding system (\textit{activeNN}).
Then we compare the performance of \textit{activeNN} to that of \textit{passiveNN} and CART.
\\\textit{Results:}
There is no-point in labeling all the instances in a dataset.
\textit{ActiveNN} can attain results comparable to \textit{passiveNN} and CART with orders of magnitude less labels.
\\\textit{Conclusion:} Actual topology of the instance space is different than the expected: Some instances are popular than the others. This knowledge is successfully exploited to build an active-learning based guiding system in effort estimation for the first time. 
\end{abstract}
% Note that keywords are not normally used for peer review papers.
\begin{IEEEkeywords}
Software Cost Estimation, Analogy, \textit{k}-NN
\end{IEEEkeywords}}


% make the title area
\maketitle

\section{Introduction}
\label{sect:introduction}

Software effort estimation (SEE) experiments that use all the instances of a dataset assume that all instances are useful for estimation.
We would like to call that approach \textit{``assumption-all''}, which states that:
\begin{quote}
``All instances are useful in estimation.''
\end{quote}

Another possible assumption is that some of the instances are redundant or even disruptive (noise).
Similarly, some others are more popular, i.e. used more frequently during estimation.
We would like to call that popularity based approach as \textit{``assumption-pop''}. It states that:
\begin{quote}
``Only popular instances are useful.''
\end{quote}

Data collection is a difficult process and in software engineering (SE) domain data it is not easy to access high-quality data.
The so called ``data-drought'' is in fact quite commonly recognized by researchers~\cite{Menzies2009b}.
The first author has the experience that more than half the effort of building an effort estimation model is related with data collection~\cite{Menzies2009b}.
The second author also acknowledges that fact: After two years of effort only $7$ projects could be added to the NASA-wide software cost metrics project~\cite{Menzies2007c}.
Even Boehm shares the same experience, after more than $20$ years there are less than $200$ projects in COCOMO datasets~\cite{Boehm1981}.
After years of research on data collection~\cite{Fenton2007c}, software-metrics expert Norman Fenton also agrees by saying: ``...much of the current software metrics research is inherently irrelevant to industrial mix... any software metrics program that depends on some extensive metrics collection is doomed to failure~\cite{Fenton2007b}.''

Relation between \textit{data-draught} and the SEE data assumptions (\textit{assumption-all} and \textit{assumption-pop}) is that \textit{data-draught} favors \textit{assumption-pop}, which ensures less data collection.
However, utilization of \textit{assumption-pop} requires clever guidance systems that understand the underlying structure of the data so as to guide a learner towards \textit{popular} instances.

The proposed guidance system in this paper is a product of the active learning paradigm.
Active learning is an answer to \textit{data-draught}.
It is based on the motivation that collecting labeled data is expensive~\cite{Kaariainen2006,Dasgupta2008,Hassan2010}.
Data collection activities can be immensely reduced, if labeling efforts are concentrated on certain instances that the learner considers most useful for estimation~.
Unlike \textit{passive} supervised learning that assumes the learning problem is defined by an unknown function producing the training examples; active learning suggests labeling only the instances that are useful for the learning process\cite{Kaariainen2006}.

In this study we investigate SEE data assumptions in the context of analogy-based estimation (ABE) by utilizing an active learning-based guidance system.
This investigation gives critical information regarding the topology/structure of SEE datasets.
It is shown that effort datasets behave in accordance with \textit{assumption-pop}: Using \textit{popular} instances attains as good performance as using \textit{all} instances.
Furthermore, this structural information is used to guide a nearest-neighbor based (only use the closest neighbor for estimation) ABE.
It is shown that with as few as $17.3\%$ of the entire training set (desharnais dataset of \fig{stopping-percentage}), it is possible to attain the same performance values.


\fig{topologies} illustrates the implicit topologies suggested by \textit{assumption-all} and \textit{assumption-pop} in the context of nearest-neighbor based ABE.
In \fig{topologies} a hypothetical dataset of 3 dimensions (with values between 0 and 1) is depicted.
\textit{Assumption-all} favors a topology as in \fig{expected}, i.e. it states that \textit{all} instances are useful for estimation (see cluster where all instances are closest neighbor of some other instance).
On the other hand \textit{assumption-pop} states that some of the instances are more \textit{``popular''} (squares) than the others and a majority of the instances are redundant (plusses) for estimation in a closest-neighbor setting.
Note that \fig{topologies} only demonstrates a concept, actual SEE datasets have much higher dimensions.

\begin{figure}
  \centering
  \subfloat[Expected]{\label{fig:expected}
\includegraphics[width=0.4\textwidth]{../lib/expectedTopology.png}}  \\       
  \subfloat[Actual]{\label{fig:actual}\includegraphics[width=0.4\textwidth]{../lib/actualTopology.png}} 
\caption{Expected and actual topologies for the purpose of demonstration. Assumption-all assumes that \textit{all} instances are used in estimation, hence topology would look like a). Assumption-pop states that only the \textit{popular} instances (filled squares) are used for estimation.}
\label{fig:topologies}
\end{figure}

\subsection{Research Questions}
The research questions that guided our study are as follows:
\bi
\item RQ1: Which dataset assumptions are supported by SEE datasets and what is the implication of these assumptions on the dataset topology?
\item RQ2: How does the dataset topology affect the data collection/labeling effort?
\item RQ3: What is the performance of active learning-based ABE methods to other algorithms?
\ei



\subsection{Contributions}
The contributions of this study are:
\bi
\item An investigation of software effort dataset characteristics
\item The first application of active learning on software effort estimation
\item An active-learning guidance system based on dataset characteristics
\bi
\item Reduction in data collection effort
\ei
\ei

\section{Motivation}
\label{sect:motivation}

The intuition of this work came from a quirk during the experiments of another study in our laboratory.
We were interested in the effect of injecting noise to the datasets in the context of ABE.
To our surprise, when a portion of the labels were shuffled (after shuffling instances become noise), the ABE performances before and after noise injection were statistically the same.
This was a hint that the datasets had a different topology than predicted by \textit{assumption-all}.

The initial experiments of this paper questioned the differences between the expected and the actual topology of the instance space.
Our expectation was that the whole instance space was useful, i.e. topology is governed by \textit{assumption-all}.
However, when we generated the so called $E(k)$ matrices (see \tion{methodology} for details), we were surprised to see that the median of useful instances during estimation in a \textit{closest-neighbor} setting had a median value of $25\%$.
In other words, the effort values of more than half the instances in the datasets were redundant.
The exact percentage of instance that are closest-neighbor to any other instance are given in \fig{selec-perc}.
We used that information to build an active-learning based guidance system for ABE.

\begin{figure}[!th]
\scriptsize
\centering
{ 
\begin{tabular}{l|l}  
\textbf{Dataset} & \textbf{Percentage} \\\hline\hline
kemerer	& $67\%$ \\
desharnaisL2	& $64\%$ \\
desharnaisL3	& $	60	\%$ \\
cocomo81s	& $	55	\%$ \\
cocomo81o	& $	50	\%$ \\
nasa93\_center\_1	& $	50	\%$ \\
cocomo81e	& $	36	\%$ \\
telecom	& $	33	\%$ \\
sdr	& $	25	\%$ \\
desharnais	& $	25	\%$ \\
nasa93	& $	22	\%$ \\
desharnaisL1	& $	17	\%$ \\
nasa93\_center\_2	& $	16	\%$ \\
cocomo81	& $	16	\%$ \\
finnish	& $	16	\%$ \\
nasa93\_center\_5	& $	15	\%$ \\
maxwell	& $	15	\%$ \\
miyazaki94	& $	13	\%$ \\
\end{tabular}}
\caption{Ratio of the instances used for prediction in a closest-neighbor setting to the dataset size. Note that the median percentage value is $25\%$, meaning that only a limited amount of instances are the closest neighbor of other instances and are useful in estimation.}
\label{fig:selec-perc}
\end{figure}


Hassan et al. envision the active learning solutions on data collection as a future direction in SE~\cite{Hassan2010}.
The experience of various researchers (including the authors of this paper)~\cite{Menzies2009b, Menzies2007c, Boehm1981, Fenton2007c, Fenton2007b} concerning \textit{data-drought} also points in that direction.
In other words a solution to aid the expensive data collection activities is urgent.
This urgency is even more serious for SEE as collection/labeling of new instances (software projects) can mean many years.
This paper is an answer to that urgent problem and is the first application of active learning in SEE.

\section{Background}
\label{sect:background}


\subsection{Software Effort Estimation}

Software effort estimation (SEE) can be defined as the process/activity of estimating the total effort necessary to complete a software project~\cite{Keung2008}.
Various different methods used for effort estimation are grouped under two main categories:
\bi
\item algorithmic methods
\item non-algorithmic methods
\ei

\textit{Algorithmic methods} require labeled historical data so as to learn a model.
Their estimations are generated by passing new projects through the learned model.
There is a very high number of proposed models in SEE.
Figure 3 of ~\cite{Keung2011} shows that for analogy-based effort estimation alone, likely combinations are more than $6000$.
Furthermore model building comprise an important portion of SEE research.
The biggest research topic in SEE since 1980s is the introduction and comparison of new methods~\cite{Jorgensen2007}.
Some examples to algorithmic methods are: various kinds of regression (simple, partial least square, stepwise, regression trees), 
neural networks and instance-based algorithms, just to name a few.
The common property of all these algorithmic methods is that they all require \textit{labeled} data.
Therefore, the experiments of this study, which show considerable reductions in labelling effort concern an important portion of SEE literature. 

\textit{Non-algorithmic methods} makes use of experienced human experts.
Non-algorithmic methods, a.k.a. expert-based estimation, is defined to be a human intensive approach that is most commonly adopted in practice~\cite{Jorgensen2004}. 
On one hand, these methods are flexible and intuitive as they can be applied in a variety of circumstances where other estimating techniques do not work.
For example, when there is no historical data or the requirements of a project are unavailable at the initial stages, a rough estimate in a very short period of time can be provided by expert estimates.
On the other hand -regardless of the efforts to establish guidelines for expert-based methods~\cite{Jorgensen2004}- there are still many ad-hoc methods used in practice.

\subsection{Active Learning}
\label{sect:active-learning}

Active learning is based on the assumption that some instances are more informative than the others when building a learner~\cite{Dasgupta2008, Kaariainen2006}.
Its motivation comes from the fact that labeling all the instances is very costly and it can be significantly reduced by active learning heuristics~\cite{Dasgupta2008}. 

Active learning differs from passive supervised learning.
The heuristics assume that learner has some control over the training examples~\cite{Cohn1994}.
Through so called experts (human or algorithmic), learner can choose which instances are to be labeled.

In machine learning literature there is a significant amount of active learning studies.
Dasgupta et al. ask for generalizability guarantees in active learning~\cite{Dasgupta2005}.
They use a greedy active learning heuristic and show that it can attain the same performance as good as any other heuristic in terms of reducing the number of required labels~\cite{Dasgupta2005}.
In \cite{Kaariainen2006}, Kaariainen et al. investigate the noise injection effect on the active learning performance in terms of classification performance.
Balcan et al. show in~\cite{Balcan2006} that -given the samples are i.i.d.- active learning can attain the same performance as a supervised learner with exponentially less samples.
In \cite{Wallace2010}, Wallace et al. use active learning for a deployed practical application.
They propose a citation screening model based on active learning augmented with a priori expert knowledge.

In software engineering, the practical applications of active learning can be seen in software testing~\cite{Bowring2004, Xie2004}.
In \cite{Bowring2004} active learning is used to augment learners for automatic classification of program behavior.
Bowring et al. show that learners augmented with active learning yield significant reduction in data labeling effort and they can generate comparable results to those of supervised learning.
Xie et al. use human inspection as an active learning strategy for effective test generation and specification inference~\cite{Xie2004}.
In their experiments, the amount of selected tests for the human inspection were feasible, i.e. labeling required much less effort than screening all the tests.
Hassan et al. points out active learning as part of the future of software engineering data mining~\cite{Hassan2010}.
However, to the best of our knowledge this promising direction for data analysis has not been exploited in software effort domain.
Hence, this paper is the first step in that direction.

\section{Methodology}
\label{sect:methodology}

\subsection{Algorithms}

The algorithms used in this study are the combination of a pre-processor and a learner.
The pre-processors are \textit{logging (log)} and \textit{normalization (norm).}
With the {\bf norm} preprocessor,
numeric values are  normalized
to a
0-1 interval using Equation \ref{equation:normalization}. Normalization means
that no variable has a greater influence than any other. 
\begin{equation}
\small
normalizedValue = \frac{(actualValue - min(allValues))}{(max(allValues) - min(allValues))}
\label{equation:normalization}
\end{equation}
With the {\bf log} preprocessor, all numerics are replaced with their natural logarithm value. This {\bf log}ging
procedure minimizes the effects of the occasional very large numeric values.

The learners are:
\bi
\item \textit{An instance-based learner:} ABE0-\textit{x}NN and 
\item \textit{An iterative dichotomizer :} \textbf{C}lassification \textbf{A}nd \textbf{R}egression \textbf{T}rees (\textit{CART}).
\ei
ABE0 is our name for
a very basic type of ABE that we derived from
various ABE studies~\cite{Mendes2003, Li2009, Kadoda2000}.
In {\bf ABE0-\textit{x}NN}, features are firstly normalized to 0-1 interval,
then the distance between test and train instances is measured
according to Euclidean distance function, \textit{x} nearest neighbors
are chosen from the training set and finally for finding estimated value
(a.k.a adaptation procedure) the median of \textit{x} nearest
neighbors is calculated.  We adopted a single \textit{x} value in this study: 
\begin{quote}
{\bf ABE0-1NN:} Only the closest analogy is used. 
Since the median of a single value is itself, the 
estimated value in {\bf ABE0-1NN} is the actual effort value of the closest analogy.
\end{quote}

The two pre-processors and the learners are combined to form two different learners:
\bi
\item log$\&$ABE0-1NN
\item norm$\&$CART
\ei
The reason for the selection of these particular algorithms is a prior work of the authors~\cite{Keung2011}, where 90 algorithms are evaluated on the datasets of this study.
As a result of this extensive study, norm$\&$CART as well as log$\&$ABE0-1NN turned out to be superior to other algorithms.

There are two different versions of \textit{log$\&$ABE0-1NN}: the one working on the so called \textit{``active-pool''} ( the pool that contains only the instances labeled by the active learning-based guiding system) and the one working on a training set with all instances labeled.
For convenience we will name the former as \textit{``activeNN''} and the latter as \textit{``passiveNN''}.
Since we have only one CART based algorithm (\textit{norm$\&$CART}) the learner name (CART) and the algorithm name (\textit{norm$\&$CART}) will be used interchangeably from now on.


\subsection{Building a Guidance System}

\textit{Generate distance-matrices: } For a dataset $D$ of size $N$, the associated distance-matrix ($DM$) is an $N \times N$ matrix that keeps the distances between every possible instance-tuple.
For example, a cell located at $i^{th}$ row and $j^{th}$ column ($DM(i,j)$) keeps the distance between $i^{th}$ and $j^{th}$ instances of the dataset $D$.
By its definition, matrix $DM$ has certain properties:
\bi
\item Symmetric: Since the distance between the instances \textit{i and j} is equal to the distance between the instances \textit{j and i}. 
\item Zero Diagonals: As cells on the diagonal ($DM(i,i)$) represent the distances of the instances to themselves, diagonal entries are zero.
\ei

\textit{Generate E(k) matrices: } ``\textbf{E}veryone’s \textbf{k}-th nearest matrix'' (E(k)) can be defined as the static analysis of the instance space.
E(k)[i,j] is \textit{true} if ``j'' appears in the \textit{k} nearest neighbors of ``i'' and \textit{false} otherwise.
The trivial case where i=j is ignored, i.e. an instance's nearest neighbor does not include itself.
In this study the nearest-neighbor based ABE is consdiered: E(1) describes just the single nearest-neighbor.
The ``popularity'' of instance ``x'' is defined to be $\sum_{j=1}^{n}{E(1)[x,j]}$, i.e. how often is ``x'' someone else's nearest-neighbor?

\textit{Calculate popularity index based on $E(1)$ and determine the sort order for labeling:}
Popularity index of an instance is the sum of its occurrences as the nearest-neighbor to another instance.
We have observed that the popular instances with $E(1)[x,j] = 1$ have a median percentage of $25\%$ among all datasets, meaning that more than half the data is unpopular with $E(1)[x,j] = 0$.
Our speculation based on that fact is that popularity offers an active learning scheme:
\bi
\item Sort training instances descending by their popularity index
\item Label instances following that sort order
\item Place labelled instances in the active-pool to be used for estimation
\item Compare results of different size active-pools with one another as well as with passive-ABE0-1NN and CART.
\ei

\textit{Find Stopping Point and Halt: } The idea behind an active learning-based the guidance system is to provide a clever ordering for the labeling of  instances.
Thereby, the amount of instances to be labeled will be reduced. 
In our implementation, after a certain amount of instances are labeled and added to the active pool, the guiding system halts.
The stopping point is determined by a set of rules:
\bi
\item If there is no estimation accuracy improvement in the active-pool for $n$ consecutive times.
\bi
\item In our experiments $n=3$ yielded the best results. 
\ei
\item If the $\Delta$ between the best and the worst MRE of the last $n$  instances in the active-pool is infinitesimal
\bi
\item In our experiments $n=3$ and $\Delta < 0.1$ yielded the best results.
\ei
\ei

\subsubsection{Toy Example}

Here we provide a toy example to illustrate the step-by-step execution of the active learning guidance system.
Assume that the training set of the toy example consists of 3 instances/projects: $P_1$, $P_2$ and $P_3$.
Also assume that these projects have 1 dependent and one independent variable.
In that case our toy dataset would look like \fig{toy-dataset}.

\begin{figure}[th!]
\centering
{\scriptsize 
\begin{tabular}{l|l|l}  
\textbf{Project} & \textbf{KLOC} & \textbf{Effort} \\\hline
$P_1$ & $20$ & $3$ \\
$P_2$ & $10$ & $4$ \\
$P_3$ & $40$ & $7$ \\
\end{tabular}
}
\caption{The projects of the toy example. Our hypothetical dataset consists of 3 projects described 1 independent variable (KLOC) and 1 dependent variable (effort in man-months).}
\label{fig:toy-dataset}
\end{figure}


Since our data has only 1 independent variable, we can visualize it on a linear scale as in \fig{linear-scale}.

\begin{figure}[th!]
  \centering
\includegraphics[width=0.3\textwidth]{../lib/linear.png}
\caption{Visualization of projects on a linear scale, where the axis shows KLOC values.}
\label{fig:linear-scale}
\end{figure}

The first step of the guidance system is to \textit{build the distance matrix} from our training set.
Since projects are described by a single attribute (KLOC), the Euclidean distance between two projects will be the difference between the normalized KLOC values.
The resulting \textit{distance-matrix} is given in \fig{toy-distance-matrix}.

\begin{figure}[th!]
\centering
{\scriptsize 
\begin{tabular}{l|l|l|l}  
	&	$P_1$	&	$P_2$	&	$P_3$	\\\hline
$P_1$	&	0	&	0.34	&	0.66	\\\hline
$P_2$	&	0.34	&	0	&	1	\\\hline
$P_3$	&	0.66	&	1	&	0	\\
\end{tabular}
}
\caption{The distance matrix of the projects $P_1$, $P_2$ and $P_3$.}
\label{fig:toy-distance-matrix}
\end{figure}

\textit{Creating the $E(k)$ matrix} based on the distance matrix is the second step.
As we are creating the $E(k)$ matrix we traverse the distance matrix row-by-row and label the instances depending on their distance order: closest neighbor is labeled $1$, the second closest neighbor is labeled $2$ and so on.
Note that diagonal entries with the distance values of $0$ are ignored, as they represent the distance of the instance to itself, not to a neighbor.
After this traversal, the resulting $E(k)$ matrix is given in \fig{ek-matrix}.

\begin{figure}[th!]
\centering
{\scriptsize 
\begin{tabular}{l|l|l|l}  
	&	$P_1$	&	$P_2$	&	$P_3$	\\\hline
$P_1$	&	$na$	&	1	&	2	\\\hline
$P_2$	&	1	&	$na$	&	2	\\\hline
$P_3$	&	1	&	2	&	$na$	\\
\end{tabular}
}
\caption{The $E(k)$ matrix resulting from the distance matrix of \fig{toy-distance-matrix}. The cells with a value of $na$ mean that ordering for that cell is \textit{not-applicable}.}
\label{fig:ek-matrix}
\end{figure} 

\textit{Calculating the popularity index based on $E(1)$ and determining the labeling order} is the final step of the guidance system.
$E(1)$ is a special case of $E(k)$, where cells with $k=1$ are marked with $1$'s and the others are marked with $0$'s.
The popularity index associated with each instance is calculated by summing the values in every column, i.e. the sum of the $1^{st}$ column is the popularity index of the $1^{st}$ instance, the sum of the $2^{nd}$ column is the popularity index of the $2^{nd}$ instance and so on.
The $E(1)$ matrix and the popularity indices of our toy example is given in \fig{toy-pop-index}.

\begin{figure}[th!]
\centering
{\small 
\begin{tabular}{r r l l l}  
&	&	$P_1$	&	$P_2$	&	$P_3$	\\\cline{3-5}
&	$P_1$	&	0	&	1	&	0	\\
&	$P_2$	&	1	&	0	&	0	\\
$+$ &	$P_3$	&	1	&	0	&	0	\\\hline
&	$Popularity:$	&	2	&	1	&	0	\\
\end{tabular}
}
\caption{The $E(1)$ matrix and the popularity indices of the toy example. Note that popularity index is the sum of the columns of the $E(1)$ matrix.}
\label{fig:toy-pop-index}
\end{figure} 

According to \fig{toy-pop-index} the labeling order of the instances will be: $P_1$, $P_2$ and then $P_3$.
In other words, in the first round we will ask our hypothetical expert to label $P_1$ and place that label in the active pool.
In that round, since active-pool contains only 1 \textit{labeled-instance} it will be the closest neighbor of every test instance and the estimates for all the test instances will be the same (the label of $P_1$).
In the second round, $P_2$ will be labeled by the expert and placed into the active-pool.
This time test instances will have 2 alternatives to choose their closest-neighbor from, hence the estimates will be either the label of $P_1$ or the label of $P_2$.
Finally expert will label $P_3$ and place it into the active-pool.
The change of the active pool is shown in \fig{active-pool}.
Note that the transition from $Round_i$ to $Round_{i+1}$ in an actual setting is governed by the stopping rules.
Therefore, in an actual setting -unlike the toy example- the expert labels only a small portion of the unlabeled instances.

\begin{figure}[th!]
  \centering
\includegraphics[width=0.48\textwidth]{../lib/active-pool.png}
\caption{The change of active pool for the toy example. Note that in an actual setting transition between $Round_i$ to $Round_{i+1}$ is governed by the stopping rules.}
\label{fig:active-pool}
\end{figure}

\subsection{Experiments}

\textit{Run CART and passiveNN on entire training set: } The algorithms are run on the entire training set and their estimations are stored. 
As for the sampling method 10Way cross-validation is used.
10Way works in the following manner: 
\bi
\item Randomize the order of instances in the dataset
\item Divide dataset into 10 bins
\item Choose 1 bin at a time as the test set and use the remaining bins as the training set
\item Repeat above procedure 10 times
\ei

\textit{Run activeNN on active-pool: } At each iteration active-pool is populated with training instances on the order of their popularity.
The assumption with the active-pool approach is that:
\bi
\item all the training instances outside the active-pool are considered unlabeled 
\item \textit{activeNN} is only allowed to use instances in the active pool.
\ei
Before a training instance is allowed to join the active pool, a hypothetical-expert labels that instance, i.e. the effort value is revealed to the algorithm.
At first active-pool only contains 1 instance: the most popular instance, so the estimates based on a single-instance active pool are all the same.
As the population of the active-pool increases, \textit{activeNN} has more labeled training instances to estimate from.

\textit{Compare algorithms: } Once the execution of the algorithms is over, the performance of \textit{activeNN}, \textit{passiveNN} and CART are compared under different performance measures.
Note that \textit{activeNN} with different active-pool sizes have different estimates for the test instances.
The \textit{activeNN} estimates used for comparison are the ones generated by the active-pool at the stopping point.



\begin{figure}[t!]
\centering
{\scriptsize  
\begin{tabular}{l|l}  
 \textbf{Dataset} & \textbf{Used by} \\\hline 
  telecom & \cite{keung2008c,Shepperd1997}\\
    kemerer & \cite{keung2008c,Shepperd1997,Finnie1997}  \\
   cocomo81o &\cite{Menzies2006,Lum2008,Kocaguneli2010} ,\\
  desharnaisL1 & \cite{Kocaguneli2010} ,\\ 
    cocomo81s &\cite{Menzies2006,Lum2008,Kocaguneli2010} ,\\ 
  desharnaisL3 & \cite{Kocaguneli2010}  ,\\
   albrecht & \cite{keung2008c,Li2009,Li2009a,Shepperd1997,Shepperd1996,Finnie1997} \\ 
   cocomo81e & \cite{Menzies2006,Bakir2009,Kocaguneli2010} \\ 
  nasa93\_center\_5 &\cite{Menzies2006,Lum2008,Kocaguneli2010} \\ 
  desharnaisL2 & \cite{Kocaguneli2010}   \\
  desharnais & \cite{Keung2008,keung2008c,keung2008b,Kocaguneli2010,Shepperd1997,Li2008,Kadoda2000,Kirsopp2002,Li2009,Li2009a}\\ 
  maxwell & \cite{Li2009a,Sentas2005} \\
  sdr &  \cite{Kultur2008,Turhan2007} \\ 
  nasa93\_center\_1 & \cite{Menzies2006,Lum2008,Kocaguneli2010}  \\
  miyazaki94 &\cite{Miyazaki1994} \\
  nasa93\_center\_2 & \cite{Menzies2006,Lum2008,Kocaguneli2010} \\ 
  finnish &\cite{Briand1999,Shepperd1997} \\
  cocomo81 &\cite{Menzies2006,Lum2008,Kocaguneli2010,Boehm1981}, \\
  nasa93 &\cite{Menzies2006,Lum2008,Kocaguneli2010} 
\end{tabular}}
\caption{A sample of effort estimation papers that use the
data sets explored in this paper.}\label{fig:dataset-paper}
\end{figure}

\subsection{Performance Measures}

Performance measures comment on the success of a prediction.
For example, the absolute residual (AR) is the difference between the predicted and the actual:
{\begin{equation}\label{ar}
AR_i={x_i-\hat{x_i}}
\end{equation}}
(where $x_i,\hat{x_i}$ are the actual and predicted value for test instance $i$).

The Magnitude of Relative Error measure a.k.a. MRE is a very widely used evaluation criterion for selecting the best effort estimator from a number of competing software prediction models\cite{Shepperd1997, Foss}. MRE measures the error ratio between the actual effort and the predicted effort and can be expressed as the following equation:  
{\begin{equation}\small\label{one}
MRE_i=\frac{\mid{x_i-\hat{x_i}}\mid}{{x_i}} = \frac{\mid{AR_i}\mid}{{x_i}}
\end{equation}}
A related measure is MER (Magnitude of Error Relative to the estimate \cite{Foss}):
{\begin{equation}\label{onex}
MER_i=\frac{\mid{x_i-\hat{x}_i}\mid}{\hat{x}_i} = \frac{\mid{AR_i}\mid}{\hat{x}_i}
\end{equation}}

The overall average error of MRE can be derived as the Mean or Median Magnitude of Relative Error measure (MMRE, or MdMRE respectively), can be calculated as: 

{\begin{eqnarray}\small\label{one}
MMRE={\sum_{i=1}^n   MRE_i\over {n} } \\
MdMRE={median(all MRE_i) }
\end{eqnarray}}


A common alternative to MMRE is PRED(25), and defined as the percentage of predictions falling within 25\% of the actual values, and can be expressed as:
{\begin{equation}\small
PRED(25) = \frac{100}{N}\sum_{i=1}^N\left\{\begin{array}{ll}
\mbox{1 if $MRE_i \le \frac{25}{100}$}\\
\mbox{0 otherwise}
\end{array}\right.
\end{equation} 
}
For example, PRED(25)=50\% implies that half of the estimates are failing within 25\% of the actual values \cite{Shepperd1997}.

There are many other performance measures including Mean Balanced Relative Error (MBRE) and the Mean Inverted Balanced Relative Error (MIBRE) studied by Foss et al.~\cite{Foss}:

\begin{equation}\small
MBRE_i = \frac{\hat{x_i} - x_i}{min(\hat{x_i},x_i)}
\end{equation} 

\begin{equation}\small
MIBRE_i = \frac{\hat{x_i} - x_i}{max(\hat{x_i},x_i)}
\end{equation} 

\begin{figure}[!h]
\renewcommand{\baselinestretch}{1}
\begin{algorithmic} \footnotesize
\IF{~Mann-Whitney(\textit{$P_i$}, \textit{$P_j$}, 95) says they are the same}
	\STATE \textit{$tie_{i}$} = \textit{$tie_{i}$} + 1;
	\STATE \textit{$tie_{j}$} = \textit{$tie_{j}$} + 1;
\ELSE
   	\IF{~better( median(\textit{$P_{i}$}), median(\textit{$P_{j}$}))}
   		\STATE \textit{$win_{i}$} = \textit{$win_{i}$} + 1
   		\STATE \textit{$loss_{j}$} = \textit{$loss_{j}$} + 1
   	\ELSE
   		\STATE \textit{$win_{j}$} = \textit{$win_{j}$} + 1
   		\STATE \textit{$loss_{i}$} = \textit{$loss_{i}$} + 1 \ENDIF \ENDIF
\end{algorithmic}
\caption{Comparing algorithms (\textit{i},\textit{j})
on performance ($P_i$,$P_j$). The ``better'' predicate changes according to $P$.
For error measures like MRE, ``better'' means lower medians. However, for PRED(25),
``better'' means higher medians.}
\label{fig:pseudocode-wtl}
\end{figure}

Performance measures should be supplemented with appropriate statistical checks.
Otherwise, they may lead to biased or even false conclusions~\cite{Foss}.
In this study so called $win,tie,loss$ statistics are used to aid the performance measures with Mann-Whitney Rank-Sum test ($95\%$ confidence).
The pseudo-code of the $win,tie,loss$ statistics is given in \fig{pseudocode-wtl}: We first check if two distributions $i, j$ are statistically different (Mann-Whitney rank-sum test, $95\%$ confidence);  otherwise we increment $tie_i$ and $tie_j$. 
If the distributions are statistically different, we update $win_i,win_j$
and $loss_i,loss_j$ after comparing the performance measures so as to see which one is better.

\begin{figure*}[th!]
\centering
{\tiny 
%\begin{sideways} 
\begin{tabular}{l|rrl|lrrrrr}  
~\\~\\
 \textbf{} & \textbf{} & \textbf{} & \textbf{}&\multicolumn{6}{c}{\textbf{Historical Effort Data}}\\\cline{5-10} 
 \textbf{Dataset} & \textbf{Features} & \textbf{Size} & \textbf{Description}&\textbf{Units}& \textbf{Min} & \textbf{Median} &\textbf{Mean} & \textbf{Max} & \textbf{Skewness}\\ \hline
  cocomo81 &17&63& NASA projects& months&6&98&683&11400& 4.4\\
  \hspace{4 mm}cocomo81e &17&28& Cocomo81 embedded projects&months&9&354&1153&11400& 3.4\\ 
  \hspace{4 mm}cocomo81o &17&24& Cocomo81 organic projects&months&6&46&60&240& 1.7\\ 
  \hspace{4 mm}cocomo81s &17&11& Cocomo81 semi-detached projects&months&5.9&156&849.65&6400&2.64 \\ 
  nasa93 &17&93& NASA projects&months&8&252&624&8211& 4.2\\ 
  \hspace{4 mm}nasa93\_center\_1 &17 &12 & Nasa93 projects from center 1&months&24 &66 &139.92 &360 &0.86 \\ 
  \hspace{4 mm}nasa93\_center\_2 &17&37& Nasa93 projects from center 2&months&8&82&223&1350& 2.4\\ 
  \hspace{4 mm}nasa93\_center\_5
   &17&40& Nasa93 projects from center 5&months&72&571&1011&8211& 3.4\\ 
  desharnais &12&81& Canadian software projects&hours&546&3647&5046&23940& 2.0\\ 
  \hspace{4 mm}desharnaisL1 &11 &46 & Projects in Desharnais that are developed with Language1 & hours &805 &4035.5 &5738.9 &23940 &2.09 \\ 
  \hspace{4 mm}desharnaisL2 &11 &25 & Projects in Desharnais that are developed with Language2 & hours &1155 &3472 &5116.7 &14973 &1.16 \\ 
  \hspace{4 mm}desharnaisL3 &11 &10 & Projects in Desharnais that are developed with Language3 & hours &546 &1123.5 &1684.5 &5880 &1.86 \\ 
  sdr &22&24& Turkish software projects& months&2&12&32&342& 3.9\\ 
  albrecht &7&24& Projects from IBM&months&1&12&22&105& 2.2\\ 
  finnish &8 &38 &Software projects developed in Finland  &hours &460 &5430 &7678.3 &26670 &0.95 \\
  kemerer &7 &15 &Large business applications  &months &23.2 &130.3 &219.24 &1107.3 &2.76 \\
  maxwell &27 &62 &Projects from  commercial banks in Finland  &hours&583 &5189.5&8223.2&63694&3.26 \\
  miyazaki94 &8 &48 &Japanese software projects developed in COBOL  &months &5.6 &38.1 &87.47 &1586 &6.06 \\
  telecom &3 &18 &Maintenance projects for telecom companies  &months &23.54 &222.53 &284.33 &1115.5 &1.78  \\\cline{3-3}
          \multicolumn{2}{c}{~}  & Total: 699& \multicolumn{7}{c}{~} 
\end{tabular}
%\end{sideways}
}
\caption{The 699 projects used in this study come from 19 datasets.
Indentation in column one denotes that indented dataset is a subset of its non-indented parent.}\label{fig:datasets}
\end{figure*}

\begin{figure*}[th!]
  \centering
  \subfloat[Pro-Active: desharnais]{\label{fig:cat-active}
\includegraphics[width=0.4\textwidth]{../lib/mdmre_desharnais.pdf}}               
  \subfloat[Pro-CART: albrecht]{\label{fig:cat-cart}\includegraphics[width=0.4\textwidth]{../lib/mdmre_albrecht.pdf}}
 \\
  \subfloat[Con-Active: maxwell]{\label{fig:cat-con-active}\includegraphics[width=0.4\textwidth]{../lib/mdmre_maxwell.pdf}}    
  \subfloat[Con-CART: cocomo81s]{\label{fig:cat-con-cart}\includegraphics[width=0.4\textwidth]{../lib/mdmre_cocomo81s.pdf}}    
\caption{Sample plots for different category of results. The line parallel to y-axis indicates the stopping point.}
\label{fig:category-plots}
\end{figure*}

\subsection{Datasets}

There is at least one study in SEE using one or more of the 19 datasets used in our study (see \fig{dataset-paper}).
Therefore, the results presented here are based on a large corpus and concern a number of previously published SEE studies.
The description of 20 datasets used in this study are provided in \fig{datasets}.
These datasets are available at \protect\url{http://promisedata.org/data}.

As described in \fig{datasets}, the datasets were collected in different parts of the world:
\bi
\item The desharnais dataset includes Canadian software projects, 
\item cocomo81 and nasa93 include projects developed in the United States,
\item sdr, contains projects of various software companies in Turkey~\cite{Bakir2009}.
\ei

Note that three of these data sets (nasa93\_center\_1, nasa93\_center\_2, nasa93\_center\_5)
come from different development centers around the United States. Another three of these
data sets (cocomo81e, cocomo81o, cocomo81s) represent different kinds of projects (embedded, organic and semi-detached respectively) developed by different team sizes and under different constraints~\cite{Boehm1981}.


Note also in \fig{datasets}, the skewness of the effort values (up to 6.06):
The datasets are extremely heterogeneous with as much as 60-fold
variation.  
There is also some divergence in the features used to describe the datasets:
\bi
\item 
While data sets have some effort values in common (measured in terms of man-months or man-hours),
no other feature is shared by all data sets.
\item
The cocomo* and nasa* data sets use the features defined by Boehm~\cite{Boehm1981}; e.g.
analyst capability, required software reliability, memory constraints, and use of software tools.
\item
The other data sets use a wide variety of features including, number of entities in the data model, number of basic logical transactions, query count and number of distinct business units serviced.
\ei



\section{Results}
\label{sect:results}

We will interpret our results with regards to two different concerns: Reduction in labeling effort and  performance.
Reduction in labeling effort will question how much effort we can save via an active learning-based guidance system.
Note that the effort reduction makes sense only if \textit{activeNN} has a successful performance.
Therefore,  in the performance part we compare \textit{activeNN} to \textit{passiveNN} and CART.


\subsection{Labeling Effort Reduction}

The reduction in the labeling effort is related to how many labels \textit{activeNN} requested from the expert.
This number is given by the so called \textit{stopping-point} of the guidance system.

In \fig{category-plots} one plot for each performance-category is provided (see \tion{result-perf} for performance-categories).
These plots show the \textit{MdMRE} values of the learners used in this study.
The stopping-point is shown with a vertical line that is parallel to the y-axis.
In all cases \textit{activeNN} stops before asking all the labels of the training set.

Note that the \textit{MdMRE} values of CART and \textit{passiveNN} are stable (horizontal line), whereas the \textit{MdMRE} values \textit{activeNN} change at every point in x-axis.
This is due to the fact that for \textit{activeNN} the instance numbers in x-axis show the size of the \textit{active-pool} and for different \textit{active-pool} sizes \textit{activeNN} yields different performance values.

\begin{figure}[th!]
\scriptsize
\centering
{ 
\begin{tabular}{l|l|l}  
\textbf{Dataset} & \textbf{\# Instances} & \textbf{Perc. Labeled} \\\hline\hline
cocomo81s 	&	11	&	 $ 81.8 \% $ \\
desharnaisL3 	&	10	&	 $ 70 \% $ \\
cocomo81e 	&	28	&	 $ 64.3 \% $ \\
cocomo81o 	&	24	&	 $ 62.5 \% $ \\
desharnaisL1 	&	46	&	 $ 56.5 \% $ \\
nasa93\_center\_1 	&	12	&	 $ 50 \% $ \\
sdr 	&	24	&	 $ 50 \% $ \\
nasa93\_center\_2 	&	37	&	 $ 48.6 \% $ \\
kemerer 	&	15	&	 $ 46.7 \% $ \\
telecom 	&	18	&	 $ 38.9 \% $ \\
albrecht 	&	24	&	 $ 33.4 \% $ \\
nasa93\_center\_5 	&	40	&	 $ 33.4 \% $ \\
desharnaisL2 	&	25	&	 $ 24 \% $ \\
finnish 	&	38	&	 $ 23.7 \% $ \\
miyazaki 	&	48	&	 $ 18.7 \% $ \\
cocomo81 	&	63	&	 $ 17.4 \% $ \\
desharnais 	&	81	&	 $ 17.3 \% $ \\
maxwell 	&	62	&	 $ 12.9 \% $ \\
nasa93 	&	93	&	 $ 8.6 \% $ \\
\end{tabular}}
\caption{The percentage of instances that are labeled at the stopping point. The median percentage value is $38.8\%$. The implication of this table is that it is possible reduce the effort of labeling activities by orders of magnitude.}
\label{fig:stopping-percentage}
\end{figure}

Note also that there is an additional $4^{th}$ line in the plots of \fig{category-plots}: \textit{randActiveNN}.
The purpose of \textit{randActiveNN} is to provide a baseline for the \textit{activeNN} to make sure that the results of \textit{activeNN} are premeditated.
\textit{randActiveNN} works exactly the same as \textit{activeNN}.
The only the difference is that instead of selecting the closest instance from the \textit{active-pool} on the basis of popularity, it randomly picks an instance from the \textit{active-pool}.
In other words it violates the core assumption (\textit{assumption-pop}) of the guidance system.

We see in \fig{category-plots} that \textit{randActiveNN} performs much worse and different than \textit{activeNN}.
This shows that violation of \textit{assumption-pop} destroys the benefits of the guidance system.
It also shows that the performance results of \textit{activeNN} are far from being coincidental.

Since this result repeats itself for every dataset (random behavior of \textit{randActiveNN}) we suffice to provide one plot per category.
The summary of all the datasets is provided in \fig{stopping-percentage}.
\fig{stopping-percentage} shows the percentage of labeled instances in comparison to dataset sizes.
Note that the percentage labeled instances can be as low as $8.6\%$ with a median percentage value of $38.8\%$.
The lowest-percentage dataset that belongs to the category of \textit{Pro-Active} is the \textit{desharnais} dataset with a percentage value of $17.3\%$.
These results show that \textit{activeNN} works with orders of magnitude less labels when compared to \textit{passiveNN}.
The implication of this finding is quite striking.
It means that we can save an orders of magnitude effort from dataset labeling activities in an actual setting.

\newcommand{\R}{\rowcolor[rgb]{0.8,0.8,0.8}}
\newcommand{\G}{\cellcolor[rgb]{0.8,0.8,0.8}}

\begin{figure}[th!]
\centering
{\scriptsize
\renewcommand{\arraystretch}{0.7}
\begin{tabular}{l|l| c | c | c | c | c | c | c }  
\renewcommand{\baselinestretch}{0.4}
\textbf{Dataset}	 &	 \textbf{Method}	
&  \begin{sideways}\parbox{12mm}{\textbf{MMRE}}\end{sideways}	
& \begin{sideways}\parbox{12mm}{\textbf{MAR}}\end{sideways}	
& \begin{sideways}\parbox{12mm}{\textbf{Pred(25)}}\end{sideways}	
& \begin{sideways}\parbox{12mm}{\textbf{MdMRE}}\end{sideways}		
& \begin{sideways}\parbox{12mm}{\textbf{MBRE}}\end{sideways}	
& \begin{sideways}\parbox{12mm}{\textbf{MIBRE}}\end{sideways}		
& \begin{sideways}\parbox{12mm}{\textbf{MMER}}\end{sideways}	\\\hline\hline
cocomo81 & passive & 1 & 0 & 1 & 1 & 0 & 0 &   1 \\
 & active & 1 & 0 & 0 & 0 & 0 & 0 &   -2 \\
 & cart & -2 & 0 & -1 & -1 & 0 & 0 &   1 \\\hline
cocomo81e & passive & 2 &   2 &   0 &   2 &   2 &   2 &   1 \\
 & active & 0 &   -1 &   -1 &   -1 &   -1 &   -1 &   -2 \\
 & cart & -2 &   -1 &   1 &   -1 &   -1 &   -1 &   1 \\\hline
cocomo81o & passive & -1 & -2 & -1 & -1 & -1 & -1 &   -1 \\
 & active & 2 & 1 & 2 & 2 & 2 & 2 &   -1 \\
 & cart & -1 & 1 & -1 & -1 & -1 & -1 &   2 \\\hline
cocomo81s & passive & 1 & 1 & 2 & 2 & 0 & 2 & 2 \\
 & active & 1 & 1 & 0 & 0 & 2 & 0 & 0 \\
 & cart & -2 & -2 & -2 & -2 & -2 & -2 & -2 \\\hline
desharnais & passive & 1 &   -1 &   -1 &   -1 &   -1 &   -1 &   -1 \\
 & active & 1 &   -1 &   -1 &   -1 &   -1 &   -1 &   -1 \\
 & cart & -2 &   2 &   2 &   2 &   2 &   2 &   2 \\\hline
desharnaisL1 & passive & 0 &   2 &   2 &   2 &   2 &   2 &   2 \\
 & active & 2 &   -2 &   -2 &   -2 &   -2 &   -2 &   -1 \\
 & cart & -2 &   0 &   0 &   0 &   0 &   0 &   -1 \\\hline
desharnaisL2 & passive & 1 & 0 & -2 & -2 & 0 & 0 &   0 \\
 & active & 1 & 0 & 1 & 1 & 0 & 0 &   -1 \\
 & cart & -2 & 0 & 1 & 1 & 0 & 0 &   1 \\\hline
desharnaisL3 & passive & 1 & 1 & 1 & 1 & 1 & 1 & -1 \\
 & active & 1 & 1 & 1 & 1 & 1 & 1 & 0 \\
 & cart & -2 & -2 & -2 & -2 & -2 & -2 & 1 \\\hline
nasa93 & passive & 2 &   0 &   2 &   2 &   2 &   2 &   0 \\
 & active & 0 &   -2 &   -2 &   -2 &   -2 &   -2 &   -2 \\
 & cart & -2 &   2 &   0 &   0 &   0 &   0 &   2 \\\hline
nasa93\_center\_1 & passive & 1 & -1 &   0 &   0 &   -1 &   -1 &   -1 \\
 & active & 1 & 0 &   -1 &   -1 &   -1 &   -1 &   -1 \\
 & cart & -2 & 1 &   1 &   1 &   2 &   2 &   2 \\\hline
nasa93\_center\_2 & passive & 2 &   1 & 1 & 1 &   1 & 1 &   2 \\
 & active & 0 &   -1 & 1 & 1 &   -1 & 1 &   -2 \\
 & cart & -2 &   0 & -2 & -2 &   0 & -2 &   0 \\\hline
nasa93\_center\_5 & passive & 1 & 0 &   0 &   0 &   1 &   1 &   1 \\
 & active & 1 & 0 &   -1 &   -1 &   -2 &   -2 &   -2 \\
 & cart & -2 & 0 &   1 &   1 &   1 &   1 &   1 \\\hline
sdr & passive & 1 & 1 & 1 & 1 &   2 &   2 &   2 \\
 & active & 1 & 0 & 1 & 1 &   -1 &   -1 &   -1 \\
 & cart & -2 & -1 & -2 & -2 &   -1 &   -1 &   -1 \\\hline
albrecht & passive & 0 &   -1 &   -1 &   -1 &   -1 &   -1 & -2 \\
 & active & 0 &   -1 &   -1 &   -1 &   -1 &   -1 & 1 \\
 & cart & 0 &   2 &   2 &   2 &   2 &   2 & 1 \\\hline
finnish & passive & 2 &   -1 & -2 &   0 &   -1 &   -1 &   0 \\
 & active & 0 &   -1 & 0 &   -2 &   -1 &   -1 &   -2 \\
 & cart & -2 &   2 & 2 &   2 &   2 &   2 &   2 \\\hline
kemerer & passive & 0 & 0 & 0 & 0 & 0 & 0 & -2 \\
 & active & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\
 & cart & -1 & 0 & 0 & 0 & 0 & 0 & 1 \\\hline
maxwell & passive &   1 &   0 &   0 &   0 &   0 &   0 & -2 \\
 & active &   -2 &   -2 &   -2 &   -2 &   -2 &   -2 & 0 \\
 & cart &   1 &   2 &   2 &   2 &   2 &   2 & 2 \\\hline
miyazaki94 & passive & 1 & -1 &   0 &   0 & -2 &   0 &   -1 \\
 & active & 1 & 1 &   -2 &   -2 & 0 &   -2 &   -1 \\
 & cart & -2 & 0 &   2 &   2 & 2 &   2 &   2 \\\hline
telecom1 & passive & 1 & 0 & 0 & 0 & 0 & 0 & -1 \\
 & active & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
 & cart & -2 & 0 & 0 & 0 & 0 & 0 & 1 \\
\end{tabular}}
\caption{The $win-loss$ values. Those results are used to form the so called \textit{``performance categories''}. }
\label{fig:win-tie-loss}
\end{figure}

\subsection{Performance}
\label{sect:result-perf}

\fig{win-tie-loss} shows the comparison of \textit{activeNN}, \textit{passiveNN} and CART subject to $7$ different performance measures.
The table summarizes the performance measures in terms of $win-loss$ values.
\fig{win-tie-loss} alone is difficult to interpret, therefore we use it as the basis to a more structured analysis: The results of \fig{win-tie-loss} is interpreted in terms of result categories.
Our performance results can be grouped into 4 categories: \textit{Pro-Active}, \textit{Con-Active}, \textit{Pro-CART} and \textit{Con-CART}.

\textit{Pro-Active: } In this category, the \textit{activeNN} has comparable or superior performance (in at least $4$ out of $7$ error measures) to \textit{passiveNN}.
We are interested in \textit{comparable} results as well as the better results, because in both cases \textit{activeNN} has a considerable reduction in data labeling effort.

\textit{Pro-CART: } For the datasets falling in this category, CART is dominantly superior to \textit{activeNN} (better in terms of 3 or more performance measures).

\textit{Con-Active: } For the datasets in this category \textit{activeNN} is the worst performing algorithm, i.e. it loses to \textit{passiveNN} AND CART (which means $win-loss$ value of $-2$) in $3$ or more performance measures.

\textit{Con-CART: } For the datasets in this category, CART is the worst performer, i.e. it is worse than \textit{passiveNN} AND \textit{activeNN} (which means $win-loss$ value of $-2$) in $3$ or more performance measures.


The distribution of the datasets to these categories are given in \fig{dataset-to-category}.
The $win-loss$ values used to generate \fig{dataset-to-category} are given in \fig{win-tie-loss}.

\begin{figure}[th!]
\centering
\scriptsize
{ 
\begin{tabular}{l|l|l}  
\textbf{Category} & \textbf{Datasets} & \textbf{\#}\\\hline\hline
Pro-Active & cocomo81, cocomo81o, cocomo81s & \\ 
		& desharnais, desharnaisL2, desharnaisL3 & 12\\
		& nasa93\_center\_1 , albrecht, finnish  & \\
		& kemerer , miyazaki94, telecom  & \\\hline
Con-Active & desharnaisL1, nasa93, nasa93\_center\_5 & 5 \\
         &  maxwell, miyazaki94 & \\\hline
Pro-CART &  desharnais, nasa93\_center\_1, nasa93\_center\_5 & \\
         &  albrecht, finnish, maxwell & 7 \\
         &  miyazaki94 & \\\hline
Con-CART &  cocomo81s, desharnaisL3, nasa93\_center\_2 &  4 \\
		 &  sdr & \\
\end{tabular}}
\caption{The distribution of datasets into result-categories. Last column shows the number of datasets in each category. Note that $12$ datasets fall into the category of \textit{Pro-Active} and $5$ fall into \textit{Con-Active}. Among $12+5=17$ datasets that differentiate \textit{activeNN} from \textit{passiveNN}, for $70\%$ of the datasets \textit{activeNN} is a substitute for \textit{passiveNN}.}
\label{fig:dataset-to-category}
\end{figure}


In \fig{dataset-to-category} $12$ datasets fall into the category of \textit{Pro-Active} and $5$ fall into \textit{Con-Active}. 
A total of $12+5=17$ datasets are able to differentiate \textit{activeNN} from \textit{passiveNN} as better or worse.
Among $17$ datasets, for $70\%$ of the datasets \textit{activeNN} is a substitute for \textit{passiveNN}.
In other words, in $70\%$ of the datasets \textit{activeNN} is comparable to or better than \textit{passiveNN} for much less data labeling effort.

In the category of \textit{Con-Active} there are $5$ datasets. 
In other words, only in $5/19=26\%$ of the datasets was \textit{activeNN} worse than both competitors at the same time.

Upon that information we can say that for the majority of the datasets \textit{assumption-pop} works.
In other words, for less labeling effort we can gain the same performance as \textit{assumption-all.}

As for the performance of CART in comparison to \textit{activeNN}, we look at the category of \textit{Pro-CART}.
There are $7$ datasets in \textit{Pro-CART}, which shows that for $37\%$ of the datasets CART is dominantly superior to \textit{activeNN}.
This shows that for the majority of the datasets ($100\% - 37\% = 63\%$), \textit{activeNN} is comparable to the most successful algorithm reported in \cite{Keung2011}.
Therefore, an \textit{assumption-pop} based guidance system does not only outperform standard passive ABE methods, but also is comparable to the state-of-the-art learners.

The category of \textit{Con-CART} shows the failure of CART and contains only $4$ datasets.
For only $21\%$ of the datasets CART performs worse than both ABE methods.
The results of this last category support the findings of~\cite{Keung2011} in an ABE context.


\section{Threats To Validity}
\label{sect:threats-to-validity}

 \textit{Internal validity} asks to what extent the cause-effect relationship between dependent and independent variables holds~\cite{Alpaydin2004}. 
The ideal case to observe that relationship would be to learn a theory on the available data and apply the \textit{learned} theory on completely new and unseen data.
However, considering the \textit{data-drought} in SEE, the ideal case is unfeasible. 
Therefore, the ideal scenario is simulated by sampling methods to separate the available data into training and test sets.
In this study we used 10Way sampling method to simulate the ideal case.


\textit{External validity} is the question of how widely the results can be generalized~\cite{Milic2004}.
So as to observe the applicability of our results to a wide spectrum of SEE datasets, we use a total of $19$ datasets that have very different characteristics.
Although the analysis on $19$ datasets is more extensive than an average SEE study, we acknowledge that our experiments need to be replicated on new datasets.

 \textit{Construct validity} (i.e. face validity) asks if we are in fact measuring what we intend to measure~\cite{Robson2002}. 
A beneficial discussion can be found in~\cite{Kitchenham2001}, where Kitchenham et al. state that different performance measures evaluate different aspects of the prediction accuracy.
So as to evaluate our results in terms of different aspects, we use $7$ different performance measures.
Another point made by Kitchenham et al. is that sole usage of performance measures is wrong and they need to be supported with statistical checks.
To address that validity issue we use $win-tie-loss$ statistics, where  we make use of Mann-Whitney U test at a significance level of 95\%. 

Another validity issue is the use of experts in active learning guidance system.
The assumption with the experts is that they are able to provide the labels of the training set upon a request from the guidance system.
As the labels in the training set is also collected by the experts this assumption is fairly appropriate.
On the other hand an interesting application would be to introduce a white-noise on the data labels to introduce the expert-judgment error.
This is currently left as a future work.

\section{Conclusions}
\label{sect:conclusions}

Our conclusions are three-fold following the research questions that guided this study.

\textit{RQ1: Which dataset assumptions are supported by SEE datasets and what is the implication of these assumptions on the dataset topology? } In this study two different assumptions are investigated: \textit{assumption-all} and \textit{assumption-pop}.
The former assumes a random topology and states that any instance may be the closest instance to another instance; hence, all instances of the training set are useful.
The latter assumes a more structured topology where popular instances are central and are the closest-neighbor to multiple other instances; hence a limited number of labels is sufficient.
At the end of our analysis, we have seen that \textit{assumption-all} does not hold and SEE datasets have a topology indicated by \textit{assumption-pop}.

\textit{RQ2: How does the dataset topology affect the data collection/labeling effort? }We have seen the assumptions regarding SEE dataset topology can be successfully used as a guidance system.
Such a guiding removes the need to label all the instances in a dataset.
In fact we observed that it is possible to reduce the number of instances to be labeled by orders of magnitude.
Therefore, our conclusion is that immense amount of effort spent in data collection/labeling can be saved with the proposed guiding system.


\textit{RQ3: What is the performance of active learning-based ABE methods to other algorithms? } Based on the topology foreseen by \textit{assumption-pop} we defined an active learning-based guidance system to be used with ABE0-1NN.
The combination (\textit{activeNN}) proved to be comparable to standard passive-learning based ABE0-1NN (\textit{passiveNN}) as well as more complex learners like CART.

\section{Future Work}

This initial study uses a single popularity metric: so called E(k) matrix.
A plausible future direction would be to device new popularity metrics based on the data topology.
Those new popularity metrics may as well be used to augment the E(k) matrix.
For example E(k) matrices only cares about the popularity index, i.e. two instances with the same popularity index are treated the same.
However, this index can be augmented with a total-distance metric meaning that the instance with the lower total-distance is preferable to the other one.

Another point of future research is the stopping rules: When should the guidance-system stop asking for new labels? 
Currently we make use of multiple rules and they offer favorable performance values.
However, current rules are heuristics and can only approximate the optimum stopping point.

One final and fairly easy-to-do future direction to this research is to introduce the human-error into the experimentation.
Current version of the paper assumes that experts can reveal the actual effort values in the training set.
However, a company with novice experts may end up labels that are far from being perfect.
Addition of a white-noise to the actual effort values as the human-error can simulate such an experimentation.

\bibliographystyle{IEEEtran}      % basic style, author-year citations
\bibliography{library}   % name your BibTeX data base


%\begin{IEEEbiography}{Ekrem Kocaguneli}
%Ekrem Kocaguneli is a PhD student at University of West Virginia.
%\end{IEEEbiography}
%
%% if you will not have a photo at all:
%\begin{IEEEbiography}
%%[{\includegraphics[width=1in,height=1.25in,clip,keepaspectratio]{menzies.jpg}}
%{Tim Menzies}
%Tim Menzies (P.hD, UNSE) is an Assoc. Prof in CSEE at WVU and the author of over 200 referred publications. At WVU, he has been a lead researcher on projects for NSF, NIJ, DoD, NASA's Office of Safety and Mission Assurance, as well as SBIRs and STTRs with private companies. He teaches data mining and artificial intelligence. Tim is the co-founder of the PROMISE conference series devoted to reproducible experiments in software engineering. In 2012, he will be the co-chair of the program committee for the IEEE Automated Software Engineering conference.
%\end{IEEEbiography}


\end{document}

