How do I measure the reliability of a confidence value in a predictive algorithm?

Supposing I have some algorithm that is able to provide me with a confidence value for some event occurring. Let's say on day 1 it tells me that there is a 80% chance it will rain, on day 2 it tells me there is a 20% chance that the mail will be late, and on day 3 it tells me that there's a 90% chance my milk will go off.

3 days later, I measure what actually happened and come up with this result:

Confidence  Occurrence
80.000%         false
20.000%         false
90.000%         true


In other words, it did not rain on day 1, the mail was not late on day 2, and my milk did go off on day 3.

Supposing that the data set is large, but that the confidence values remain distributed and not confined to any particular range, how do I go about measuring the "reliability" of my algorithm, and what metrics could I use?

Note that the floating-point precision of the confidence value is high (say a 8-byte double). I know I could simply divide each confidence up and measure the samples in "buckets", but this would reduce the reliability of the result as it would require me to trade off between reducing the sample set for each range or accepting a larger error in the form of a broader test range. I want to use all of the information to get an accurate a result as possible.

• You'd have to have lots of predictions for each percentage, then test them individually. – Raphael Aug 30 '14 at 8:48

Measuring probability given a single occurrence doesn't really make sense, because the only data that can fit such a sample is 100% or 0%. If you have many samples, that is, if you have some sample distribution, then you can do some measuring.

For example, you could take the KL-Divergence as a measure (although it's not symmetric).

Once you have a certain reliability measure on your algorithm, you can update this data every time you have an additional sample, in an on-line manner.

If you have more details regarding the specific algorithm, or the specific type of predictions, you can probably tailor something that suits better your scenario.

You may calculate a confidence interval for your probabilities (I'm gonna use the term 'probbility' instead of 'confidence' in this answer) s.t. you could say 'for this yes/no decision, with a confidence of e.g. 95%, the probability for 'yes' is $80\% \pm 1.1\%$:

• Use N-fold validation for each yes/no decision. E.g. if you have 100 samples regarding the 'rain'/'no rain' decision pick e.g. 80 samples and calculate the probability of 'rain' $p(rain)_n = \frac{\#rain}{\#rain+\#no\ rain}$. Then repeat the calculation by picking a different set of 80 samples. (Picking can be done randomly or systematically.) Repeating this N times will give N probabilities $p_n$ for the 'rain'/'no rain' question.

• Calculate the mean $\hat{p}$ of the N probabilities. $\hat{p} = \frac{1}{N}\sum{p_n}$

• By approximating the deviation of the N probabilities by a Gaussian probability density function (PDF), you can use the following confidence interval: $\hat{p} \pm z \cdot \sqrt{\frac{\hat{p}(1-\hat{p})}{N}}$, where $z$ is the $(1-\frac{\alpha}{2})$ Quantile of Gaussian PDF: $z = \Phi^{-1}(1-\frac{\alpha}{2})$ (You can look up $z$ in an according table, e.g. here: http://www.mathnstuff.com/math/spoken/here/2class/90/htest2.htm#2ztest). E.g. for a confidence interval of $95\%$, $z = 1.96$.

• Example: Let's say for the 'rain'/'no rain' decision you calculated $\hat{p} = 80\% = 0.8$ from 50 folds (i.e. 50 times picking e.g 80 samples out of 100 and calculating $p_{1\dots50}$), therefore $N = 50$. Then, for a confidence interval of $95\%$, your upper and lower boundaries calculate to $0.8 \pm 1.96 \cdot \sqrt{\frac{0.8(1-0.8)}{50}} = 0.8 \pm 0.111$. Thus, you can say that with a certainity of 95%, the probability of 'rain' is between 78.89% and 81.11%.

Alternatively, you could calculate the variance of all $p_n$ as quality measure: $\sigma^2 = \frac{1}{N-1}\sum_{n=1}^N(p_n - \hat{p})^2$

• I don't think identifying probability and confidence is a good idea. Also, for determining confidence intervals you need to know the underlying distribution, don't you? Does a Gaussian model make sense for binary data (that is not added)? – Raphael Sep 3 '14 at 14:03
• Of course the data is binary. If you take N subsets of your data and calculate the probability $p_n$ for a binary variable in each subset, $p_n$ is a random variable and its distribution can be aproximated by any PDF. Using a Gaussian PDF is a common way, please refer to [1] or Wikipedia: en.wikipedia.org/wiki/… – Nikolaus Sep 3 '14 at 18:29
• [1]: T.M. Mitchell, Machine Learning. McGraw-Hill,1997 – Nikolaus Sep 3 '14 at 18:36