\section{Related Work}
\label{sect:related-work}

%Prior related work can be grouped into 3 categories: (1)~{\em software effort estimation}, 
%(2)~{\em ensemble of methods}; and (3)~{\em ensemble of methods in SE}.
%Since our reseach fundamentally aims software effort estimation problems, firstly we will provide background information regarding that subject and also we will provide a brief discussion of the stability issue arising from previous studies.
%Secondly and more fundamentally our interest in this research is how the ensemble of methods perform on effort estimation datasets.
%Therefore, second subsection of background will summarize other ensemble method studies in SE.
%Finally, in the last section we are going to discuss the ensemble of methods in other domains.


%In this subsection we first make a sketch of empirical research studies on cost estimation in the last 15 years and comment on the techniqes employed by these studies. 
%Then we biefly discuss the stability issues arising from previous results.

%This subsection reviewed the effort estimation literature with regards to 
%(a) the major estimation techniques used by empirical research studies on cost estimation within the last 15 years and (b) the conclusion instability problem.

\subsection{Algorithmic and Non-algorithmic Estimation}

Algorithmic methods generate effort estimates by passing project data through some model learned from historical data.
There are many reported algorithmic methods in the literature including 
various kinds of regression (simple, partial least square, stepwise, regression trees), 
neural networks and instance-based algorithms, just to name a few.
Later in this article, we detail the algorithmic methods used in this study.
%Within each of these algorithmic methods, there exist a large number of internal options.
%For example, Menzies et al. discuss numerous variations of instance-based effort estimation algorithms:
%\bi
%\item There is even a wider space associated with the options of those algorithms.
%For example, only the space of options associated with instance based algorithms exceed thousands~\cite{Kocaguneli2010}.
%Note that we can make this space yet even wider by combining instance and non-instance based methods.
%Li et al. reports such a combination study, where they use instance-based methods to find a neighborhood of \textit{near} instances and summarize this neighborhood with neural nets\cite{Li2009}.

The alternative to algorithmic approaches are non-algorithmic methods.
Non-algorithmic methods, a.k.a. expert-based estimation, can be defined as a human-intensive process of negotiating the estimate of a new project and arriving at a consensus~\cite{Jorgensen2004}.
There are formal methods proposed for expert-based estimation like Delphi~\cite{Rowe1999}.
However, it is mostly the case that companies follow an informal process for expert-based estimation\cite{Shepperd2001}.
%Different surveys have shown that a significant portion of software companies keep no historical effort data~\cite{Heemstra1990} or they invest in very little time for the estimation process, sometimes even at the level of minutes~\cite{Hughes1996}.
%Inevitably this approach is prone to human-centric problems.
%For example an expert may keep his idea to himself just so as not to diverge from the group opinion.
%Shepperd et al. point out that issue~\cite{Shepperd2001} and define it with the words of DeMarco~\cite{Demarco1986} as ``realism can be mistaken for disloyalty.''

In~\cite{Jorgensen2005} Jorgensen defines some guidelines for generating realistic software effort estimates.
An important finding in Jorgensen's study (which parallels our
findings) is that {\em combining estimations} coming from different
sources (e.g. from experts and instance-based learners) 
captures a
broader range of information related to the estimation problem.
Hence, multi-source predictions
offer the
most robust and accurate estimator.

\subsection{Ranking Instability}
One long-standing issue with
software effort estimation is {\em ranking instability}.
%To answer the question of whether we could derive stable conclusions regarding which estimator is the \textit{best}, there have been a number of studies conducted.
Ideally, given $M$ methods, we can definitively rank them in terms of their predictive accuracy:\[M_1 \ge M_2 \ge M_3 \ge ..\]
This ideal has yet to be seen in the literature.
To the contrary,
Shepperd et al. report that there is no certainty in that sort~\cite{shepperd01,Myrtveit}.
For example, in the
experiments of~\cite{shepperd01}, a large number of synthetic data sets were generated (from distributions found
in one real-world data set).
As they changed the conditions of their experiments, Shepperd et al. found that
no method was consistently best across every condition.
Specifically,
they  found that the performance of a method was dependent on the dataset, the random number generator used to select
train and test sets, and the evaluation method used to assess model accuracy.
Hence, they concluded that it was not feasible to sort methods into some definitive order. 


Extending their work,
we say that when $M$ methods are sorted to find  a rank $r_i$ for method $M_i$, then if experimental
conditions are changed,
then that  rank will change
by an amount ${\delta}r > 0$. 

Recently, researchers have had access to more methods than that used by Shepperd et al.
For example, Menzies et al.~\cite{Menzies2010} studied 158 methods. 
While that study was over a very limited data set (just two old COCOMO data sets), their
preliminary results prompted this study (where we work with 20 data sets).
In  a result consistent with Shepperd et al.,
Menzies et al. found that as we changed the random numbers used to generate train/test sets, then all 158 methods exhibited
some ${\delta}r>0$; i.e. their precise ranking changed.
However, they also found a small number of methods with two interesting properties:
\be
\item Their ranks were very high;
\item Their ${\delta}r$ values were very small.
\ee
Property \#1 means that some methods performed comparatively very well and
Property \#2 means that high ranking persisted across multiple experimental conditions.
Hence, if we look at enough methods, it may be possible to  rank methods even when they exhbit ${\delta}r>0$.
Accordingly, in the results reported below, we will report not only  the rank of each method, but also their
associated ${\delta}r$. The methods we recommend will be those with
\bi
\item high ranks;
\item and low ${\delta}r$.
\ei
\subsection{Ensemble of Methods}
%When we observe software effort estimation as a learning problem, there is a wide variety of approaches that we can adopt such as statistical models or various machine learning methods.
A standard machine learning technique is to  
try mulitple methods on the available data, then recommend 
the one that performs best~\cite{Alpaydin1998}.
Many effort estimation papers apply this technique to  demonstrate that (say)
their preferred
new method is superior to
those proposed in prior work.

{\em Ensemble learning} takes a different
approach. Rather than choosing {\em one} method, ensemble learners build 
multiple predictors, then ask them all to vote on the final  prediction~\cite{Dietterich2000}.  

Ensembles are useful since any particular learner
comes with its own assumptions~\cite{Alpaydin1998}.
These assumption may be best suited to different parts of the training data~\cite{Alpaydin1998, Dietterich2000, Kittler1998}.
In ensembles, methods 
can augment each other, i.e. a method patches errors made by another method.
For example, when reducing estimated
mean-squared-error, multi-methods attain
smaller or equal error rates than single-methods~\cite{Seni2010}.

It is a recommended practice to combine solo-methods that have
different characteristics~\cite{Kittler1998, Ali1995, Alpaydin1998}.
There are many techniques  to attain different-characteristic
multi-methods.  The first way is through representation of the data.
The multi-method structure may be based on uni-representation (all
learners use same representation of data) or multi-representation
(different learners use different representations)~\cite{Alpaydin1998}.
Examples to such strategies are the use of different feature
sets~\cite{Ho1994, Gunter2004} or different training sets~\cite{Ho19995}.

The second way is through architectural methodologies.  Bagging
(Bootstrap Aggregating) and boosting are among the most common
examples of that approach~\cite{Alpaydin1998, Zhao2004}.  In bagging
\textit{n}-many solo-methods are independently applied on \textit{n}-many
different training samples, where each training sample is selected
via bootstrap sampling~\cite{Alpaydin1998} with replacement.
Boosting on the other hand arranges solo-methods in a sequential
manner: each solo-method pays more attention to the instances on
which previous method was unsuccessful.  Among the reported results,
boosting is mostly reported to be considerably better than
bagging~\cite{Zhao2004,Witten2000,Bauer1999}, but has trouble in handling
noisy datasets~\cite{Zhao2004,Bauer1999}.


\subsection{Ensemble of Methods in SE}
Ensemble methods are widely used in data mining (see the literature
survey of~\cite{Seni2010}).  %The success of multi-methods in
%other domains does not promise that they will be successful on SE
%problems.  
Nevertheless, in the software domain, they
are not always successful.  
Khosgoftaar et al.~\cite{Khoshgoftaar2009}
 question the performance of different multi-method
schemes under different scenarios in the domain of software quality.
They use different combinations of $17$ learners induced on $7$
datasets and report that multi-methods induced on single datasets
do not yield a significant increase in prediction accuracy.

Kocaguneli et al.~\cite{Kocaguneli2009} 
replicated~\cite{Khoshgoftaar2009} in the domain of software effort
estimation.  They exploited combination of $14$ methods applied on 3
software effort estimation datasets.  Their  conclusion
was similar to that of~\cite{Khoshgoftaar2009}:
the application of multi-methods under different scenarios did not
provide a significant increase in the estimation accuracy.  Similarly,
in
\cite{Kumar2010}, different learners were employed in two types of
committees, but only one of them was reported to be successful.  

Another example to ensembles is the committee of \textit{single-type}
learners, where multiple versions of a single algorithm are combined.
Pahariya et al. use linear combinations of genetic algorithms in
\cite{Pahariya2009}, where they report improvements over single-learners.
In \cite{Kultur2008} Kultur et al. report improvements through
collections of neural networks.  Note that such single-learner 
methods fall into the category of solo-methods (since there is only
one type of learner) in this work.  

There are also some applications
of ensemble methods in effort estimation so as to process datasets:
In ~\cite{Twala2006}, Twala et al. use multiple imputation techniques
to handle missing data and in \cite{Khoshgoftaar2005} Khoshgoftaar
et al. make use of learner ensembles as a filter to improve the
data quality.


Our ensemble is different from the above. We take care to prune
inferior solo methods {\em before} building the ensemble.
As shown below, this leads to very effective effort estimators.
%We mentioned our motivation regarding this study in \tion{motivation}, in summary: On instance basis, there are \textit{good} and \textit{bad} learners and combining their estimations could result in multi-methods that complement one another and hence lower error rates.


%However, the results of previous multi-method studies in SE domain have caused skeptical views and discussions among us before the experimentation phase.
%On the other hand, the fact that there is a very limited literature in SE domain regarding multi-methods and the fact that we would follow a different experimental setting convinced us to follow our intuition and continue with the experimentation.
%To our surprise we observed quite different results than the previous work: Multi-methods were consistently better than single-methods over multiple datasets and multiple performance measures.
%The difference in results is an important topic and we separate a whole section for that discussion in \tion{discussion}.

%When we claim that \cite{Kocaguneli2009} and \cite{Khoshgoftaar2009} are the only multi-methods studies in SE domain, we need to clarfiy one point.
%There is a vast literature in SE that questions ensembles of NN's~\cite{park08, Kultur2008, vent93} and they may seem like multi-method studies at first.
%However, by definition multi-methods aim at bringing together learners that have different and complementary assumptions as well as biases~\cite{Alpaydin1998}.
%Since ensemble of NN's fundamentally employ a single learner, we do not refer to these studies as multi-method studies.


