I am looking for an algorithm* to solve the following problem


I'm observing a sequence of things. Every thing has some arbitrary visible properties and a hidden probability $p$ to turn out to be red (otherwise it's blue). I also have an oracle that estimates the red/blue probability of things.

The problem is, if, for instance, the oracle gives a thing a $p$ = 70% chance for red and the thing turns out to be blue, I cannot say that the oracle was wrong.

So I have shown the oracle a lot of things and collected both the estimated probabilities and the actual colors.

What algorithms could I use to evaluate the quality of the oracle based on the data?

Test cases

Let's say I have three sets of things: in $T_1$ all things are 100% red ($p = 1$), in $T_2$ all things have a 50% chance to be red ($p = 0.5$), and in $T_3$ half of the things are 100% red ($p = 1$), the other half is 100% blue ($p = 0$).

Also given are three oracles: $O_1$, which always predicts $p = 1$; $O_2$ which always predicts $p = 0.5$; and $O_3$, which always correctly predicts the probability $p$ of each thing.

Given these inputs, I would expect the algorithm to give the following results:

$A(O_1, T_1) = A(O_3, T_1) > A(O_2, T_1)$ (oracle 1 and 3 predict perfectly, 2 is obviously wrong)

$A(O_2, T_2) = A(O_3, T_2) > A(O_3, T_2)$ (oracle 2 and 3 predict perfectly, 3 is obviously wrong)

$A(O_1, T_2) = A(O_1, T_3)$ and $A(O_2, T_2) = A(O_2, T_3)$ (the algorithm can't distinguish between set 2 and 3, because the probability is hidden, and the oracles produce the same results)

$A(O_3, T_2) < A(O_3, T_3)$ (for set 3, $O_3$ gives much better results, so it should get a better rating here)

My solution so far

If I assume that the oracle predicts probabilities only as multiples of, say, $10\%$, I could put the things in buckets based on the estimated probability and then easily evaluate the correctness of each bucket (assuming that there are enough things so that statistical variation can be neglected) and could then sum up the weighted rating of each bucket to get the rating of the oracle.

However, the oracle can produce any real number between 0 and 1 and if I choose the bucket size too small, the result for each individual bucket will always be bad (eg, if there are only 2 things in the "28.75%" bucket), so the bucket approach doesn't really work.

* I tried to make the problem as clear as possible. If it's not, please ask. If this question is off topic, please tell me where I could ask it.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.