2

After reading sklearn manual it was not very obvious for me to understand how Isotonic regression works in the case of probability calibration (using CalibratedClassifierCV). I briefly read sklearn's github code for this model and some additional theory on the subject (this is a good source) and concluded that in this case we have the following algorithm.
(Below for $i=1,\ldots,N$: $y_i$'s are the true labels, $\hat p_i = \hat P(Y=1|x_i)$'s are the corresponding estimates of probabilities, given by some base classifier, and $w_i$'s are some positive sample weights; for simplicity let's consider binary classification.)

  1. Sort pairs $(\hat p_k, y_k)_{k=1}^N$ from calibration set by first argument, then by second argument (i.e. using $\text{np.lexsort}((y,\hat p))$ ) and get sorted pairs $(\hat p_i, y_i)_{i=1}^N$.
  2. Solve the following constrained optimization problem (i.e. fit Isotonic regression model):
    $\displaystyle \text{minimize}~ \sum_{i=1}^N w_i (q_i - y_i)^2$ with respect to $\mathbf{q} \in \mathbb{R}^N$
    $\text{subject to} ~~0 \le q_1 \le q_2 \le \ldots \le q_N \le 1$.

    In sklearn this optimization problem is solved by using Pool Adjacent Violators Algorithm (PAVA), which is a linear time (and linear memory) $O(N)$ algorithm for linear ordering isotonic regression.
  3. Define the "prediction function" $q(\hat p (x))$ as a linear interpolation on a set of points $(\hat p_1, q_1), \ldots, (\hat p_N, q_N)$. So, for every new point $\hat p_k \in [0,1]$ the prediction is $q(\hat p_k) \in [0,1]$.

So the only difference from the common usage of the Isotonic regression is that for the calibration task we use set of probabilities $\{\hat p_1, \ldots, \hat p_N\}$ (given by some base classifier) instead of a set of train samples $\{x_1, \ldots, x_N\}$ and have requirement $0 \le q \le 1$ (in common case $q \in \mathbb{R}$).
Also, when base classifier has decision function, we will use its values (such as $\{w^T x_1, \ldots, w^T x_N\}$ for linear base classifier) instead of $\{\hat p_1, \ldots, \hat p_N\}$.

I want to know, if my understanding is correct? Please correct me if I have mistakes. Thanks!

Rodvi
  • 749
  • 1
  • 7
  • 17
  • I'm not entirely sure, but in my head I had another variant of this. Instead of regressing against {y} directly, I thought we would regress against the [calibration curve](https://scikit-learn.org/stable/modules/calibration.html#calibration-curves) given a hyperparmeter `n_buckets`. I felt weirded out by the idea of regressing to {y} as it's strictly 0 to 1 (just picture what the regression vs data points would look like). Anyway my answer to your question is: I've thought this through for some hours now and I can at least say your explanation looks very plausible. – Alexander Soare Oct 23 '20 at 20:02
  • Also, I did a whole investigation into this - see in this [SE question](https://stats.stackexchange.com/questions/493393/should-scikit-learn-calibratedclassifiercv-isotonic-mode-use-bucketed-rates-inst) – Alexander Soare Oct 23 '20 at 20:29

0 Answers0