Statistically evaluating performance of algorithms I am working on a problem for which I have come up with a couple of algorithms. To assess which one is the best, I compare a set of algorithm outputs (set of numbers) against the "true" set of values by evaluating the absolute value of the difference between the two. I then take the mean of this difference set and also calculate its standard deviation. My approach was to choose the algorithm with mean closest to zero as the best. The problem is that the standard deviation of the least mean algorithm is larger than some of the other algorithms. The relevant values are:
$$ \begin{array}{|c|c|c|} \hline \mbox{Algorithm number}& \mbox{Mean} & \mbox{Standard Deviation} \\ \hline 1 & 0.316 & 0.615 \\ 2 & 0.298 & 0.615 \\ 3 & 0.253 & 0.657 \\ 4 & 0.283 & 0.657 \\ \hline \end{array}
$$
Based on the mean, I would choose the third algorithm. Is this really the best algorithm, given the large standard deviation? And is there any other way to evaluate which algorithm is the best, just by studying the outputs?
 A: It really depends on how you want to penalize your errors. In the evaluation process, you need to define a "loss" function. Here, the loss function you chose is the mean of the absolute values of prediciton errors, also known as "MAE." This is a perfectly good loss function. One property of MAE is that it is not as significantly perturbed by outliers as many other loss functions: if you would like to penalize more strongly for outliers (I think you do) you should consider using the mean of the squared prediction errors (i.e. "mean squared error," or MSE). There are many common loss functions out there to choose from (RSS, RMSE, L1 norm, L2 Norm...), but you aren't limited to these: you can design any loss function you want. MSE is probably the most commonly used, but there are others to explore, and there's nothing inherently wrong with MAE.
Something else to consider is how you value accuracy vs. precision. Algorithm #3 has the highest accuracy, but is tied for the lowest precision. Just like choosing a loss function, you need to decide for yourself what you value most in this regard.
Presumably, your algorithms all had to be "trained" on some data where the desired result was known. Was your evaluation of these algorithms based on the data you used to train them? If so, I strongly recommend that you a) consider using cross validation to get a better understanding of the prediction errors you can anticipate, and b) if you have enough data, set some aside to not be used for training and evaluate based on the held out data in addition to cross validation.
Finally, it's worth noting that although you can make your selection based solely on a loss function, the numbers in your table all look very similar. The improvement you are receiving between these algorithms may be so negligible as to not be statistically significant. You should consider comparing the difference in your means with a one way ANOVA or a series of t-tests to confirm that the you are actually getting different results from your algorithms.
