INSPIRE: Incorporating Diverse Feature Preferences in Recourse

Abstract

Most recourse generation approaches optimize for indirect distance-based metrics like diversity, proximity, and sparsity, or a shared cost function across all users. A shared cost function in particular is an unrealistic assumption because users can have diverse feature preferences (FPs), i.e. the features they are willing to act upon to obtain recourse. In this work, we propose a novel method, INSPIRE to incorporate diverse feature preferences in both recourse generation and evaluation procedures by focusing on the cost incurred by a user when opting for a recourse. To achieve this, we first propose an objective function, Expected Minimum Cost (EMC) based on two key ideas: (1) the user should be comfortable adopting at least one solution when presented with multiple options, and (2) we can provide users with multiple options that cover a wide variety of FPs when the user's FPs are unknown. To optimize for EMC, we propose a novel discrete optimization algorithm, Cost-Optimized Local Search (COLS), that is guaranteed to improve the quality of the recourse set over iterations. Next, we propose a cost-based evaluation procedure that computes user satisfaction by simulating each user's cost function and then computing the incurred cost for the provided recourse set. Experiments on popular real-world datasets demonstrate that our method is more fair compared to baselines and satisfies up to 25.9% more users. We also show that our method is robust to misspecifications of the cost function distribution. Our code is available at \href{https://github.com/prateeky2806/EMC-COLS-recourse}https://github.com/prateeky2806/EMC-COLS-recourse.