Learning Decision Trees and Forests with Algorithmic Recourse

Kentaro Kanamori, Takuya Takagi, Ken Kobayashi, Yuichi Ike
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:22936-22962, 2024.

Abstract

This paper proposes a new algorithm for learning accurate tree-based models while ensuring the existence of recourse actions. Algorithmic Recourse (AR) aims to provide a recourse action for altering the undesired prediction result given by a model. Typical AR methods provide a reasonable action by solving an optimization task of minimizing the required effort among executable actions. In practice, however, such actions do not always exist for models optimized only for predictive performance. To alleviate this issue, we formulate the task of learning an accurate classification tree under the constraint of ensuring the existence of reasonable actions for as many instances as possible. Then, we propose an efficient top-down greedy algorithm by leveraging the adversarial training techniques. We also show that our proposed algorithm can be applied to the random forest, which is known as a popular framework for learning tree ensembles. Experimental results demonstrated that our method successfully provided reasonable actions to more instances than the baselines without significantly degrading accuracy and computational efficiency.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-kanamori24a, title = {Learning Decision Trees and Forests with Algorithmic Recourse}, author = {Kanamori, Kentaro and Takagi, Takuya and Kobayashi, Ken and Ike, Yuichi}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {22936--22962}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/kanamori24a/kanamori24a.pdf}, url = {https://proceedings.mlr.press/v235/kanamori24a.html}, abstract = {This paper proposes a new algorithm for learning accurate tree-based models while ensuring the existence of recourse actions. Algorithmic Recourse (AR) aims to provide a recourse action for altering the undesired prediction result given by a model. Typical AR methods provide a reasonable action by solving an optimization task of minimizing the required effort among executable actions. In practice, however, such actions do not always exist for models optimized only for predictive performance. To alleviate this issue, we formulate the task of learning an accurate classification tree under the constraint of ensuring the existence of reasonable actions for as many instances as possible. Then, we propose an efficient top-down greedy algorithm by leveraging the adversarial training techniques. We also show that our proposed algorithm can be applied to the random forest, which is known as a popular framework for learning tree ensembles. Experimental results demonstrated that our method successfully provided reasonable actions to more instances than the baselines without significantly degrading accuracy and computational efficiency.} }
Endnote
%0 Conference Paper %T Learning Decision Trees and Forests with Algorithmic Recourse %A Kentaro Kanamori %A Takuya Takagi %A Ken Kobayashi %A Yuichi Ike %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-kanamori24a %I PMLR %P 22936--22962 %U https://proceedings.mlr.press/v235/kanamori24a.html %V 235 %X This paper proposes a new algorithm for learning accurate tree-based models while ensuring the existence of recourse actions. Algorithmic Recourse (AR) aims to provide a recourse action for altering the undesired prediction result given by a model. Typical AR methods provide a reasonable action by solving an optimization task of minimizing the required effort among executable actions. In practice, however, such actions do not always exist for models optimized only for predictive performance. To alleviate this issue, we formulate the task of learning an accurate classification tree under the constraint of ensuring the existence of reasonable actions for as many instances as possible. Then, we propose an efficient top-down greedy algorithm by leveraging the adversarial training techniques. We also show that our proposed algorithm can be applied to the random forest, which is known as a popular framework for learning tree ensembles. Experimental results demonstrated that our method successfully provided reasonable actions to more instances than the baselines without significantly degrading accuracy and computational efficiency.
APA
Kanamori, K., Takagi, T., Kobayashi, K. & Ike, Y.. (2024). Learning Decision Trees and Forests with Algorithmic Recourse. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:22936-22962 Available from https://proceedings.mlr.press/v235/kanamori24a.html.

Related Material