\section{Introduction}


Correctly estimating the effort required to develop software is of vital importance.
Over or under-estimation of software development effort can lead to undesirable results:
\bi
\item
Under-estimation results in schedule and budget overruns, which may cause project cancellation.
\item
Over-estimation hinders the acceptance of promising ideas, thus threatening organizational competitiveness.
\ei
%Since effort estimation plays such an important role for software companies,  a considerable effort has been invested in the issue and various methods have been proposed.
%%Early methods have employed relatively simple algorithms as well as data processing techniques.
%For example COCOMO~\cite{Boehm1981} is one of the earliest and one of the most widely used techniques.
%Basis of COCOMO logging the data and fitting a regression model to that data.
%Over the years, consecutive studies have employed more complex approaches (let it be statistics-based methods or machine-learning-based methods).
%Aside from such algorithmic approaches, there are also human-centered approaches that are based on human judgment.
%However, neither the source  (human or algorithm) nor the complexity (simple or complex) can necessarily guarantee the best results.
%It is usually the case that proposed methods are validated on a limited number of datasets and the success of a particular single method on new datasets stays as an external validity issue[XXX].
A
commercial practitioner consulting the literature  in this area 
will encounter a bewildering array of 
techniques
ranging from:
\bi
\item
Simple regression~\cite{Boehm2000};
\item
To analogy-based methods~\cite{Shepperd1996};
\item
To complex combinations of techniques
such as 
Corazza et al.'s~\cite{Corazza2010} use of tabu search to configure support vector machines or Menzies et al.'s~\cite{Menzies2006} cpu-intensive approach that
tries hundreds of different methods. 
\ei
Not only is the current literature confusing and voluminous~\cite{Jorgensen2007}, it also lacks 
guidance on how to select appropriate estimators for  particular projects.
Worse still, some results suggest that it may be impossible to assess which effort models are the best.
Shepperd et al.~\cite{Shepperd2001} warn that when comparing $M$ estimation methods, the ranking of any
one method may change, if the conditions of that experiment are changed. Hence, they argue, it is fundamentally
impossible to offer a definitive ranking such that $method_1$ is better than $method_2$.

This paper revisits the Shepperd results, and offers a more optimistic conclusion. We find 
that if we {\em combine} the estimates from {\em multiple estimators},
then those combined methods perform {\em better than   any single estimator}. That is, we agree with Shepperd et al.
that there may be no single best effort estimator. However, there may be 
{\em best ensembles of methods}.

This should  not be a surprising result.
Many researchers argue that, in theory, best estimates come from  combinations of multiple predictions.
For example, Jorgensen advises that, for expert-based estimation,
it is best to generate estimates from multiple methods~\cite{Jorgensen2004}.
Researchers in machine learning concur: e.g. Seni et al. report that averaging the estimates from {\em many  models} often does
better than using 
{\em any solo model}~\cite{Seni2010}. Similar conclusions are offered by other
researchers in the field of statistics~\cite{Hastie08} and machine learning~\cite{Kohavi95,breiman92}.

Nevertheless, our results are quite surprising,
since current empirical results  in software engineering
report the exact {\em opposite} effect  than that predicted by Jorgensen and Seni et al.,
and others~\cite{Jorgensen2004,Seni2010,Hastie08,Kohavi95,breiman92}:
\bi
\item
Kocaguneli et al.
failed to improve estimation by averaging across the predictions of 14 estimators~\cite{Kocaguneli2009}.
\item
Baker could  not improve  estimation accuracy by 
{\em boosting} ensembles~\cite{Baker2007}\footnote{Boosting is an ensemble method that generates a series of models where $model_i$ focuses on the cases
that were most difficult for $model_{i-1}$~\cite{Freund1999}.}. 
\ei
This paper resolves this contradiction between theory and experimental results. 
In doing so, we can offer clear advice on how to select the right effort estimators for a particular
set of data. To the best of our knowledge, this is the first such result in the effort estimation literature
that is supported by extensive experimentation.

It will be argued that 
the mistake made by Baker, Kocaguneli et al. was to assume that {\em all} solo methods are candidates for combination into multi-method
ensembles. This is not the case.
Solo methods can be sorted
into a minority of  {\em superior} methods and a majority of  {\em inferior} methods.
We show below that, in the majority case,
solo methods are out-performed by ensembles of multi-methods built from the superior set.

We therefore offer the following advice for practitioners commissioning an effort estimator at their local site:
\be
\item
Try a large number of methods. 
\item
Sort the methods using the evaluation methods discussed in this paper. Discard all but the best solo methods.
\item
Built ensembles from the remaining solo methods.
\ee
While step \#1 is computationally intensive, the runtimes are not excessive.
For example, we combine 9 learning algorithms and 10 pre-processors 
into $10\times9=90$ solo-methods.
The best of these were combined into 12 ensemble methods and all 102 methods
were applied to 20 effort estimation datasets. The 
CPU time for all this was under 24 hours.
%
%A subset of these chronic problems that are addressed in this
%research are:
%
%\bi
%\item Lack of consistently best learners
%\item Instability in reported conclusions 
%\ei
%
%In this research a novel multi-method scheme is proposed and unlike previous research we report that multi-methods consistently outperform solo-methods.
%The above statement is in disagreement with at least 2 prior conclusions.
%The first disagreement is conclusion instability: The collection of previous studies has resulted in a wide-variety of conclusions that are reported to be instable or contradictory~\cite{Jorgensen2007}.
%%In all, this study applies 102 estimators to 20 datasets and measures their performance in terms of seven different performance criteria.  
%%To the best of our knowledge, this is the largest effort estimation study yet reported in the literature. 
%After exploring a large space of datasets, methods as well as error measures, the results in this study show that it is possible to report stable conclusions.
%%We will clarify this issue through research questions in \tion{research-questions} and provide related answers in \tion{answers-to-research-questions}.
%The second disagreement is in the performance of multi-methods: Unlike previous research, we favor the use of multi-methods on SE data, provided that suitable ensemble methods are applied. 
%%a.k.a learner ensembles: This is a newer and hence less elaborated problem, about which the two previous studies concluded that multi-methods performed poorly on software engineering data and one of those studies belongs to one of the authors of this paper.
%%%Similar to how we approach the previous disagreement, we discuss the second one through research questions as well.
%%We also think that the second problem deserves more attention. 
%%We separate a whole discussion as to why the current and previous studies~\cite{Khoshgoftaar2009, Kocaguneli2009} have different opinions on multi-methods in \tion{discussion}.
%
%%In this research we tackle with the afore mentioned problems through experimenting with a vast variety of pre-processors and learners applied on a large number of datasets.
%We use nine learning algorithms combined with 10 pre-processors, which amounts to $10\times9=90$ solo-methods.
%Solo-methods are combined in 12 different ways to form ensembles, which will be called as multi-methods from now on.
%In total \textit{90 solo-methods + 12 multi-methods = 102 methods} are are applied on 20 different effort estimation datasets.
%%Although the contributions of the findings are subjective, the factual experimental properties of this research makes it a noticeable work in the literature.
%The only software engineering studies -that we are aware of- questioning the performance of learner ensembles are~\cite{Khoshgoftaar2009} by Khoshgoftaar et. al. in software quality domain and~\cite{Kocaguneli2009} by Kocaguneli et. al. in software effort estimation domain.
%The common conclusion of those papers is not to use ensemble of solo-methods on software engineering data.

This research makes the following contributions:
\bi
\item Successful results (unlike previous research) concerning multi-methods applied on effort data 
\item A novel scheme for ensembling the best solo-methods
\item An evaluation method for the stability of methods
\item Stable multi-methods that outperform \textit{all} solo-methods
\item A wide study of 20 datasets and 102 methods. To the best of our knowledge, in terms of methods and datasets this is one of the most comprehensive effort estimation studies to be reported (see Table 4 of~\cite{Mendes2007} for other studies).
%XXXX In addition, in software engineering (SE) there is a limited number of studies regarding the ensemble of solo-methods ~\cite{Khoshgoftaar2009, Kocaguneli2009, Kumar2010, Baker2007} and they do not support the use of multi-methods.
\ei
This paper is structured as follows.
\tion{related-work} discusses related work.
\tion{methods} summarizes the methods (algorithms, pre-processors and ensemble schemes) used in this study.
Our methodology is explained in \tion{methodology}, which generates the results of  \tion{results}.
The threats to the validity of our results are reviewed in \tion{threats_to_validity}.
%The conclusions of \tion{discussion} discuss our answers to following research questions:
%\bi
%\item RQ1: What are the effects of using multi-methods?
%\item RQ2: Why do not ensemble methods work in SE?
%\item RQ3: What can the experiments that use 102 methods over 20 datasets tell us about stability issues?
%\item RQ4: What is the best effort estimator?
%\item RQ5: What are the implications of our results regarding software effort datasets?
%\ei

%This work differs from other papers as follows:
%\bi
%\item This report focuses on the value of combining solo methods into multi-methods. A pre-cursor
%to this study is ~\cite{keung2011a}, which discusses the ranks of the solo methods. Yet,~\cite{keung2011a} does not
%discuss multi-methods.
%\item
%In preparing this report we made the surprising discovery that, contrary to numerous predictions
%made by other researchers, leave-one-out and cross-validation result in similar bias and variance
%for effort predictions. Some quick notes on that discovery are included in the {\em Validity}
%section of this paper. Elsewhere~\cite{ekrem11}, we are preparing a more extensive analysis of that discovery.
%\ei
%
