Isotonic Regression Calibration
Isotonic Regression Calibration
A classifier may output probabilities that do not reflect true likelihoods. Isotonic regression calibration fits a non-decreasing mapping from raw predicted probabilities to calibrated ones, minimizing squared error on a calibration dataset. New predictions are then transformed through this mapping.
Given calibration data (true labels and predicted probabilities) and a list of new predictions, apply isotonic regression calibration and return the calibrated probabilities.
Steps
1. Sort the calibration data by predicted probability.
2. Fit an isotonic (non-decreasing) regression to the sorted labels. This means finding the non-decreasing sequence of values that minimizes:
i=1∑n(yi−c^i)2subject toc^1≤c^2≤⋯≤c^nThis produces a calibrated value for each calibration point.
3. Transform each new prediction using linear interpolation between calibration points. For a new prediction q that falls between calibration points (p_i, c_i) and (p_{i+1}, c_{i+1}):
q^=ci+pi+1−piq−pi⋅(ci+1−ci)For predictions outside the calibration range, clamp to the nearest calibrated value.
Return a list of calibrated probabilities, one per new prediction.
Examples
Input:
cal_labels = [0, 0, 1, 1] cal_probs = [0.1, 0.3, 0.7, 0.9] new_probs = [0.5]
Output:
[0.5]
The calibration data is already monotonic (labels go 0,0,1,1). Interpolating at 0.5 (between 0.3 and 0.7 with calibrated values 0.0 and 1.0) gives 0.5.
Input:
cal_labels = [0, 1, 0, 1] cal_probs = [0.1, 0.4, 0.6, 0.9] new_probs = [0.2, 0.5, 0.8]
Output:
[0.1667, 0.5, 0.8333]
Sorted labels [0, 1, 0, 1] violate monotonicity. After isotonic regression, the calibrated values become [0.0, 0.5, 0.5, 1.0]. New predictions are then interpolated against this mapping.
Hint 1
When merging blocks that violate monotonicity, use weighted averages and check backwards for cascading violations.
Hint 2
A stack-based approach processes elements one at a time and merges the top of the stack when needed.
Requirements
- Sort calibration data by predicted probability
- Fit a non-decreasing sequence that minimizes squared error against the sorted labels
- Use linear interpolation for new predictions between calibration points
- Clamp predictions outside the calibration range
Constraints
- 2 <= len(cal_labels) == len(cal_probs) <= 5000
- 1 <= len(new_probs) <= 5000
- cal_labels[i] is 0 or 1
- 0.0 <= cal_probs[i], new_probs[i] <= 1.0
- Calibration probabilities are distinct
- Time limit: 300 ms
Log in to take notes on this problem
Accepts: array
Accepts: array
Accepts: array
Isotonic Regression Calibration
Isotonic Regression Calibration
A classifier may output probabilities that do not reflect true likelihoods. Isotonic regression calibration fits a non-decreasing mapping from raw predicted probabilities to calibrated ones, minimizing squared error on a calibration dataset. New predictions are then transformed through this mapping.
Given calibration data (true labels and predicted probabilities) and a list of new predictions, apply isotonic regression calibration and return the calibrated probabilities.
Steps
1. Sort the calibration data by predicted probability.
2. Fit an isotonic (non-decreasing) regression to the sorted labels. This means finding the non-decreasing sequence of values that minimizes:
i=1∑n(yi−c^i)2subject toc^1≤c^2≤⋯≤c^nThis produces a calibrated value for each calibration point.
3. Transform each new prediction using linear interpolation between calibration points. For a new prediction q that falls between calibration points (p_i, c_i) and (p_{i+1}, c_{i+1}):
q^=ci+pi+1−piq−pi⋅(ci+1−ci)For predictions outside the calibration range, clamp to the nearest calibrated value.
Return a list of calibrated probabilities, one per new prediction.
Examples
Input:
cal_labels = [0, 0, 1, 1] cal_probs = [0.1, 0.3, 0.7, 0.9] new_probs = [0.5]
Output:
[0.5]
The calibration data is already monotonic (labels go 0,0,1,1). Interpolating at 0.5 (between 0.3 and 0.7 with calibrated values 0.0 and 1.0) gives 0.5.
Input:
cal_labels = [0, 1, 0, 1] cal_probs = [0.1, 0.4, 0.6, 0.9] new_probs = [0.2, 0.5, 0.8]
Output:
[0.1667, 0.5, 0.8333]
Sorted labels [0, 1, 0, 1] violate monotonicity. After isotonic regression, the calibrated values become [0.0, 0.5, 0.5, 1.0]. New predictions are then interpolated against this mapping.
Hint 1
When merging blocks that violate monotonicity, use weighted averages and check backwards for cascading violations.
Hint 2
A stack-based approach processes elements one at a time and merges the top of the stack when needed.
Requirements
- Sort calibration data by predicted probability
- Fit a non-decreasing sequence that minimizes squared error against the sorted labels
- Use linear interpolation for new predictions between calibration points
- Clamp predictions outside the calibration range
Constraints
- 2 <= len(cal_labels) == len(cal_probs) <= 5000
- 1 <= len(new_probs) <= 5000
- cal_labels[i] is 0 or 1
- 0.0 <= cal_probs[i], new_probs[i] <= 1.0
- Calibration probabilities are distinct
- Time limit: 300 ms
Log in to take notes on this problem
Accepts: array
Accepts: array
Accepts: array