CERBO: Certified Recourse at a Requested Rate for Gradient-Boosted Trees
Organizations: Islamic University of Technology · University of Southern California · Qatar Computing Research Institute (QCRI)
Abstract
Recourse-aware learning trains models so that people who receive an adverse decision can reverse it with an affordable change. For gradient-boosted decision trees (GBDTs), the existing method, RABIT, exposes a single recourse weight whose effect on the recourse rate is abrupt and data-dependent, and its training bound cannot certify recourse for any rejected individual. We present Certified Recourse Boosting (CERBO), which takes a requested recourse rate and returns a GBDT with certified actions: it tracks exact additive effort along tree paths, trains against committed boxes (a family of bounds that contains RABIT's and certifies a within-budget action for each training sample) and adjusts the weight after every tree until the certified rate meets the request. A calibration step guarantees the rate on new individuals, and the certifier runs on any tree ensemble, including XGBoost and LightGBM, in milliseconds per person without a solver. In RABIT's own experimental protocol, at equal accuracy, CERBO raises the recourse ratio from 0.90 to 0.99 on FICO and from 0.64 to 0.77 on Bail. Under additive costs on six data sets, it raises the area under the accuracy-recourse frontier in all 12 settings, and in simulated deployments it guarantees recourse to 70% of rejected individuals in 11 of 12 settings, against 2 for RABIT.
Figures & tables
| Data | Method | Accuracy | Recourse ratio | Cost | Sparsity | Plausibility | ROC-AUC | F1 |
|---|---|---|---|---|---|---|---|---|
| FICO | Vanilla | 0.372 | 2.24 | 0.440 | 0.801 | 0.717 | ||
| OAF | 0.316 | 2.77 | 0.443 | 0.786 | 0.704 | |||
| RABIT ( ) | 0.167 | 1.05 | 0.475 | 0.796 | 0.711 | |||
| RABIT (tuned ) | 0.113 | 1.02 | 0.475 | 0.790 | 0.708 | |||
| CERBO | 0.052 | 1.05 | 0.465 | 0.794 | 0.717 | |||
| COMPAS | Vanilla | 0.232 | 1.51 | 0.436 | 0.736 | 0.727 |
| Setting | OAF | RABIT | CERBO | (envelope) | (model frontier) |
| Adult | 0.076 | 0.247 | 0.427 | [ , ] | [ , ] |
| Adult | 0.137 | 0.418 | 0.609 | [ , ] | [ , ] |
| Bail | 0.126 | 0.252 | 0.396 | [ , ] | [ , ] |
| Bail | 0.251 | 0.517 | 0.661 | [ , ] | [ , ] |
| Credit | 0.228 | 0.352 | 0.644 | [ , ] | [ , ] |
| Credit | 0.260 | 0.539 | 0.782 | [ , ] | [ , ] |
| RABIT’s search | Our certifier | |||
| Required rate | RABIT | CERBO | RABIT | CERBO |
| 30% achievable | 11/12 | 12/12 | 7/12 | 12/12 |
| 50% achievable | 7/12 | 12/12 | 5/12 | 11/12 |
| 70% achievable | 2/12 | 11/12 | 2/12 | 9/12 |
| Accuracy cost (points) | 0.66 | 0.17 | 1.35 | 0.33 |
| Violation | 0.8% | 0.4% | 1.2% | 0.8% |
| Setting | A | B | C | D | E | F | G |
|---|---|---|---|---|---|---|---|
| Adult | 0.247 | 0.240 | 0.334 | 0.359 | 0.332 | 0.391 | 0.427 |
| Adult | 0.418 | 0.404 | 0.589 | 0.616 | 0.573 | 0.554 | 0.609 |
| Bail | 0.252 | 0.204 | 0.219 | 0.232 | 0.261 | 0.270 | 0.396 |
| Bail | 0.517 | 0.455 | 0.552 | 0.592 | 0.564 | 0.578 | 0.661 |
| Credit | 0.352 | 0.324 | 0.305 | 0.354 | 0.629 | 0.576 | 0.644 |
| Credit | 0.539 | 0.525 | 0.701 | 0.765 | 0.746 | 0.654 | 0.782 |
Appendix figures & tables12 assets
Supplementary material from the paper’s appendix.
Appendix
| Data set | Mutable | Favorable | Source | License | ||
| FICO | 9,871 | 23 | 15 | 0.480 | FICO et al. (2018) | FICO terms |
| COMPAS | 7,214 | 15 | 7 | 0.549 | Angwin et al. (2016) | none stated |
| Adult | 48,842 | 16 | 5 | 0.239 | Becker & Kohavi (1996) | CC BY 4.0 |
| Bail | 8,923 | 16 | 7 | 0.375 | Schmidt & Witte (1989) | ICPSR terms |
| Credit | 30,000 | 13 | 9 | 0.779 | Yeh & Lien (2009) | CC BY 4.0 |
| German | 1,000 | 51 | 7 | 0.700 | Hofmann (1994) | CC BY 4.0 |
| Component | Setting |
|---|---|
| Shared booster | RABIT’s implementation and configuration for every method: 100 trees of depth 8, learning rate , candidate features per split, 128 bins, ridge term |
| Splits | per seed, a stratified 75/25 train/test split; validation data, where used, are a stratified 80/20 split of the training data |
| RABIT | soft-min surrogate with ; under additive costs, the depth-scheduled budget rule of its code. Weights: its published grid under RABIT’s protocol; 12 weights elsewhere, plus for the 18-weight frontiers |
| CERBO | requested rates ; commitment depth ; midpoint surrogate; initial , , |
| Ablations | B and C: RABIT’s 12 weights; D, E and F: 17 weights from to |
| Leaf refinement | RABIT’s released code at , calibration samples from the training split |
| Experiment | Sections | Data sets | Seeds | Runs | CPU-h | |
|---|---|---|---|---|---|---|
| RABIT’s protocol | 4.2 , C.2 | RABIT’s four | 0.2 (max) | 300–309 | 1,600 | 89 |
| Frontiers and ablations | 4.3 , 4.6 , C.3 | six | 0.1, 0.2 | 200–207 | 9,489 | 341 |
| Refinement along the trade-off | 4.3 , C.3 | Bail, FICO | 0.2 (max); 0.1 | 300–309; 200–204 | 330 | 37 |
| Replication, commitment depth | 4.3 , C.5 | six; synthetic | 0.1, 0.2 | 700–703; 20–22 | 6,623 | 220 |
| Certified recourse | 4.4 , C.4 | six | 0.1, 0.2 | 400–404 | 2,278 | 76 |
| Guaranteed rates | 4.4 | six | 0.1, 0.2 | 800–805 | 1,511 | 47 |
| Data | Method | Values | Accuracy | Recourse | Cost | Sparsity | Plausibility | ROC-AUC | F1 |
|---|---|---|---|---|---|---|---|---|---|
| FICO | Vanilla | ours | 0.734 | 0.542 | 0.372 | 2.24 | 0.440 | 0.801 | 0.717 |
| published | 0.735 | 0.541 | 0.358 | 2.16 | 0.438 | 0.802 | 0.717 | ||
| RABIT ( ) | ours | 0.728 | 0.832 | 0.167 | 1.05 | 0.475 | 0.796 | 0.711 | |
| published | 0.732 | 0.825 | 0.165 | 1.08 | 0.475 | 0.796 | 0.711 | ||
| COMPAS | Vanilla | ours | 0.684 | 0.826 | 0.232 | 1.51 | 0.436 | 0.736 | 0.727 |
| published | 0.682 | 0.832 | 0.230 | 1.52 | 0.436 | 0.734 | 0.728 |
| Data | Method | Accuracy | Recourse | Cost | Sparsity | Plausibility | ROC-AUC | F1 | Time (s) |
|---|---|---|---|---|---|---|---|---|---|
| FICO | Vanilla | ||||||||
| OAF | |||||||||
| RABIT ( ) | |||||||||
| RABIT (tuned ) | |||||||||
| CERBO | |||||||||
| COMPAS | Vanilla |
| FICO | COMPAS | Bail | Adult † | |||||
|---|---|---|---|---|---|---|---|---|
| Tolerance | acc. | rec. | acc. | rec. | acc. | rec. | acc. | rec. |
| 0.5 | ||||||||
| 0.75 | ||||||||
| 1 (paper) | ||||||||
| 1.5 | ||||||||
| 2 | ||||||||
| FICO | COMPAS | Bail | Adult † | |||||
|---|---|---|---|---|---|---|---|---|
| acc. | rec. | acc. | rec. | acc. | rec. | acc. | rec. | |
| 0 (none) | ||||||||
| 0.01 | ||||||||
| 0.02 | ||||||||
| 0.04 | ||||||||
| 0.08 | ||||||||
| FICO | COMPAS | Bail | Adult † | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Method | Acc. | Rec. | Acc. | Rec. | Acc. | Rec. | Acc. | Rec. | ||||
| Vanilla + ref. | 0.709 | 0.696 | 0.01 | 0.679 | 0.888 | 0.01 | 0.697 | 0.827 | 0.32 | 0.854 | 0.682 | 0.04 |
| RABIT + ref. | 0.714 | 0.865 | 0.01 | 0.677 | 0.932 | 0.01 | 0.700 | 0.867 | 0.32 | 0.853 | 0.686 | 0.04 |
| CERBO + ref. | 0.718 | 0.959 | 0.01 | 0.678 | 0.977 | 0.04 | 0.701 | 0.959 | 0.64 | 0.857 | 1.000 | 1.28 |
| Setting | |||
|---|---|---|---|
| Adult | [ , ] | [ , ] | [ , ] |
| Adult | [ , ] | [ , ] | [ , ] |
| Bail | [ , ] | [ , ] | [ , ] |
| Bail | [ , ] | [ , ] | [ , ] |
| Credit | [ , ] | [ , ] | [ , ] |
| Credit | [ , ] | [ , ] | [ , ] |
| Setting | RABIT + ref. | CERBO | CERBO + ref. | |
|---|---|---|---|---|
| Bail, max cost, | 0.686 | 0.607 | 0.843 | [ , ] |
| FICO, max cost, | 0.568 | 0.860 | 0.860 | [ , ] |
| Bail, additive, | 0.378 | 0.237 | 0.564 | [ , ] |
| FICO, additive, | 0.628 | 0.834 | 0.847 | [ , ] |
Algorithmic Recourse
Algorithmic recourse studies actionable changes that can help people obtain favorable outcomes from automated decisions.
See all 30 papers