# Comparing two non-deterministic classifiers

I tried to find some earlier post regarding this, cause it seems to be a common issue, but without any luck.

I've created a couple of methods for a classification task, and after that conducted some experiments.

The difference from my experiments compared to others in the same field is that usually the methods are deterministic, whilst my methods are non-deterministic. In earlier research from the same field I can only find cherry picking when non-deterministic methods have been used (where only the best sample has been published). However, I don't like it and want to apply some statistics to give a better understanding of the performance of the methods.

First I'd like to describe how a non-deterministic is evaluated. Bellow is two deterministic methods, where Method 1 scores 75% and Method 2 scores 100%. Method two has a higher score and thereby considered better. The number of options (a, b, c, d...) the classifier has to chose from is a fixed size set predetermined by the field of research.

$$\begin{array}{c|c|c|c} Case & Method 1 & Method 2 & Correct \\ \hline 1 & a & a & a \\ 2 & b & b & b \\ 3 & x & c & c \\ 3 & d & d & d \\ \hline Score & 75 \% & 100 \% & \end{array}$$

And now over to my case where I have a Method 3 and 4 with two samples each.

$$\begin{array}{c|cc|cc|c} Case & Method 3A & Method 3B & Method 4\alpha & Method 4\beta & Correct \\ \hline 1 & a & a & a & a & a \\ 2 & b & b & b & x & b \\ 3 & x & c & c & c & c \\ 3 & d & x & d & x & d \\ \hline Score & 75 \% & 75 \% & 100 \% & 50 \% \end{array}$$

In previous papers I've seen researcher concluding that Method 4 is the best among the two later ones, because of sample 4$\alpha$ and omit sample 4$\beta$ completely.

My first idea to make a more fair representation was to consider the result of a method to be a r.v. and simply calculate the sample mean and sample standard deviation of the score for each method. The values is then put into a scatter plot with sample mean on the x-axis and sample standard deviation on the y-axis.

My second thought was to make a hypothesis test to compare the methods, and see if one is statistically better given a certain confidence.

However I'm not confident enough in statistics to make it all the way. For instance it feels wrong to have a sample standard deviation that can yield a span stretching out of the 0%-100% range. Regarding the hypothesis testing I'm stuck in comparing two methods with each-other, since I'm used to have a value and a r.v. not two r.v. where the variances isn't the same.

I have 12 samples for 10 different methods. The ideal case would be to be able to compare the methods with results from previous research articles (with deterministic methods).

Any guidance is appreciated and sorry if the problem is trivial (I might just lack the needed vocabulary to make a proper search).

• Note that my answer shows why it is under reasonable assumptions ridiculous to say that method 4 is better than method 3. Specifically, if the test cases are all of equal weight and the classifier is always run independently on each test case, then based on the test data both classifiers have isomorphic (identical up to relabeling) performance, getting 2 test cases right and the other 2 right half the time, and it would be downright dishonest to claim that any one method is better! – user21820 Jan 6 '16 at 5:39

Sample standard deviation is simply a measure of spread, and standard error is an approximation of spread of the underlying population assuming independence and finite variance. Thus there is nothing wrong with computing the sample standard deviation in order to find the standard error. However, to translate that into confidence intervals requires additional assumptions which may not hold, such as normality. That is why your intuition is correct that something is not quite right in using confidence intervals for bounded random variables, and the fact that they sometimes extend beyond the range of the random variable already tells you that there is a problem.

Indeed, if we have sufficiently large samples together with evidence that the sample size is enough to have the resulting aggregate quantity having a normal distribution, then confidence intervals would naturally fall well within the range of the aggregate random variable. Also, if we want to test whether one normal distribution has higher mean than another, we can take their difference and test whether it is significantly more than zero, since a sum of two normal distributions is normal. Note that this test is only an approximation because we already used our estimator for the variance of the difference, but we were already assuming a large enough sample size anyway.

If however you lack a large sample size, one simple way is to bootstrap. In the complete absence of any other data, your sample is the most accurate source of information, so you can simply approximate the original distribution by your sample itself. From that you can approximate the distribution of your sample! After that you can get whatever you want from that, either by analytic methods or by using computer simulation to do random resampling.

In your example, you could simply use the scores as the sample, in which case your approximated distributions are $X ~ U(\{0.75\})$ and $Y ~ U(\{0.5,1\})$ respectively, where "$\{...\}$" denotes a multiset. Trivially any sample from $X$ will have mean $0.75$. And you can compute that a sample from $Y$ of size $2$ will have mean $0.75$ with probability $\frac{1}{2}$, and so you can only conclude with $\frac{1}{2}$ confidence that they have the same mean. Since the distribution is symmetric, the mean will be higher than $0.75$ with probability $\frac{1}{4}$, which means that you expect based on your own results alone that about 25% of people who replicate the experiment will see better results for method 4 than method 3 and 25% will see worse.

A better approach would be to use the raw results themselves, since presumably the classifier is run on each test case independently. The two distributions then are both approximated to be $U(\{0.5,0.75,0.75,1\})$, since each method fails on two of the test cases half the time. We can then compute that if we take two random samples of size $2$ from this, they will have the same mean with probability $\frac{35}{128} \approx 0.27$, and that one will have higher mean than the other with probability $\frac{93}{256} \approx 0.36$. That is very high!

To avoid manual calculation like I did to get the above figures, you can use a computer simulation to resample. In your example, the simulation would create many samples of size $2$, each constructed by choosing for each test case one of the available results with probability given by your own results. You hence get an approximate distribution of the sample test run, from which you can do manual analysis. Alternatively you can push the entire thing to the simulation, creating many pairs of samples of size $2$, one based on your own results for method 3 and the other based on your own results for method 4, and then simply count the number of times one pair has method 3 coming out better/worse/same compared to method 4, which you then take as your confidence level for that category that your own results fall into.

Note that this bootstrapping method is totally unlike the usual hypothesis testing methods. It is superior because you do not need any prior assumptions, nor do you need to concoct and test against a null hypothesis. Conventional null hypotheses often make absolutely no sense, such as in your situation, where the null hypothesis would be something like "both methods have the same mean score", which is ridiculous because in real life sufficiently different randomized methods are for certain not going to have the same mean score!

Also, you might want to consider whether you really want to compare only the mean. If method 1 gets 100% correct 30% of the time but gets 0% correct the rest of the time, and method 2 gets 25% correct all the time, which would you prefer? Note that although method 1 has a higher mean, on average you expect it to perform worse than method 2 for 70% of the time! Depending on what are the exact goals of the classification task, you may want to consider not only the mean but other factors such as quantiles.