Random interpretation of prediction

Question

I am trying to build a binary classifier. Normally I'd build a model that predicts $P(y = 1 \mid x)$ and choose a threshold. I classify $1$ if predicted probability $\ge$ threshold.

What about this instead: take the predicted probability, say $p$, and choose a random number (not sure which from distribution, but let's say uniform distribution) $r \in [0, 1]$. If $r \le p$ then classify $1$.

What is this approach called? and what is a good reference to read on this type of "randomized" interpretation of the output of ML models? I am interested on reading up on how bad can this mess up the prediction accuracy, and what are the benefits/cons of this approach.

Answer 1

What about this instead: take the predicted probability, say $p$, and choose a random number (not sure which from distribution, but let's say uniform distribution) $r \in [0, 1]$. If $r \le p$ then classify $1$.

You are talking about randomly sampling your "predictions" from Bernoulli distribution (assuming binary classification) by using inverse transform sampling. As already noted, this is called probability matching. As a general strategy for making predictions it is suboptimal. For example, assuming that you knew that the probability of success is $0.72$, then if you predicted success for every case in your dataset you would get it correct with probability $0.72$. On another hand, if you used probability matching, you would be correct with probability $0.72^2 + (1 - 0.72)^2 = 0.6$. It is so because you predict the outcomes of a random variable, by taking draws from another random variable, so since both variables are independent, the probability of correctly predicting the success is probability of seeing actual success times probability of "guessing" the success. The result is intuitive since by adding noise to your predictions, you can't make it more precise.

In my setup, most customers visit my website multiple times (and/or refresh the page frequently). And I run the prediction on every webpage reload. So in the latter approach there will be a chance that I make different predictions (1 or 0) and take different actions when the same customer refreshes the webpage. But it's also attractive approach for me because if the model predicts 1 (for a customer, John) with probability 60% and the model was wrong, then I expect this approach to remedy the mistake and do the right action on 40% of John's visits.

As noticed by @Juho Kokkala, this is a different scenario. From what you are saying, you are not interested in doing correct predictions, but instead you plan to present several "possible" solutions. In such case, presenting the solutions proportionally to your certainty about the correctness of those solutions seems to be a reasonable solution assuming that the customers will visit your page multiple times.

So if your user visits the page only single time, then it would be most reasonable to show him only the most probable solution. On another hand, if your users visit page multiple times and you care about them seeing the correct solution at least once, then this is a different story. Using the previous example, if your user visits the page two times, then the probability that you would show him any correct result is $1 - [ (0.72 \times (1-0.72)^2) + ((1-0.72) \times 0.72^2) ] = 0.8$ (one minus probability that he won't see any correct results, neither positive, nor negative).

Still, you can do better by presenting the solutions ordered by correctness since if the number of visits is smaller then the number of categories, then if you show all the possibilities to your customer, then you have $100\%$ chance of correctness. Such solution may be not satisfactory for you if you do not want to show the incorrect guesses to your customer, but then you need to define some kind of loss function that adequately for your problem penalizes the misclassifications.

You could make your approach even more optimal if you displayed your "guesses" to the users and then adapt to their reactions, by improving your "guesses" and recalculating the probabilities. In such case your would be using the Thompson sampling (see Thompson, 1933; Chapelle and Li, 2011) and you should read more on the multi-armed bandit problems (e.g., Scott, 2010). Such approach is commonly used in many online scenarions, e.g. by Google or Yahoo! (check the affiliations of the authors of those papers).

Thompson, W. R. (1933). On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4), 285-294.

Chapelle, O., & Li, L. (2011). An empirical evaluation of thompson sampling. In Advances in neural information processing systems (pp. 2249-2257).

Scott, S. L. (2010). A modern Bayesian look at the multi‐armed bandit. Applied Stochastic Models in Business and Industry, 26(6), 639-658. (see also his introductory text on Google Analytics page)