Best AI Track Paper award

See ArXiv version here.

Abstract

Imbalanced learning can be addressed in 3 different ways: resampling, algorithmic modifications and cost-sensitive solutions. Resampling, and specifically oversampling, are more general approaches when opposed to algorithmic and cost-sensitive methods. Since the proposal of the Synthetic Minority Oversampling TEchnique (SMOTE), various SMOTE variants and neural network-based oversampling methods have been developed. However, the options to oversample datasets with nominal and continuous features are limited. We propose Geometric SMOTE for Nominal and Continuous features (G-SMOTENC), based on a combination of G-SMOTE and SMOTENC. Our method modifies SMOTENC’s encoding and generation mechanism for nominal features while using G-SMOTE’s data selection mechanism to determine the center observation and k-nearest neighbors and generation mechanism for continuous features. G-SMOTENC’s performance is compared against SMOTENC’s along with two other baseline methods, a State-of-the-art oversampling method and no oversampling. The experiment was performed over 20 datasets with varying imbalance ratios, number of metric and non-metric features and target classes. We found a significant improvement in classification performance when using G-SMOTENC as the oversampling method. An open-source implementation of G-SMOTENC is made available in the Python programming language.

Paper overview

Artificial intelligence (AI) systems offer the potential to enhance lives, but they also pose the risk of biased or erroneous decision-making. Algorithmic recourse methods aim to empower individuals to take action against an unfavorable outcome produced by these systems. In a nutshell, a system that supports algorithmic recourse will generate a recommendation for an action that an individual can take to change their outcome from unfavorable to favorable. The contract is that, if an individual acts on the recommendation, then they will receive a favorable outcome. However, as we show in this paper, this contract is rarely upheld, because the environment may change from the moment an individual receives the recommendation until they take action. This paper describes a simulation framework to study the effects of a continuously changing environment in algorithmic recourse for multiple agents.

Introduction

When we receive an undesirable result from an automated system, it is common to ask (1) why we received such an outcome and (2) what can we do to reverse it. Algorithmic recourse aims to answer these questions. However, the temporal dimension plays a crucial role in this context. Consider a scenario where an AI system advises a loan applicant to improve their credit score. If it takes several months to achieve this, economic conditions and lending criteria might have evolved, rendering the initial advice obsolete.

This research highlights the importance of time in the reliability of algorithmic recourse. We propose a simulation framework to study and model environmental uncertainty over time. Furthermore, we examine the dynamics emerging from multiple individuals competing to obtain a limited resource, introducing an additional layer of uncertainty in algorithmic recourse.

Our findings highlight the lack of reliability in recourse recommendations over several competitive settings, potentially setting misguided expectations that could result in detrimental outcomes. These findings emphasize the importance of meticulous consideration when AI systems offer guidance in dynamic environments.

Transparency and agency in AI-based decision making

AI is becoming an integral part of critical decision-making domains like healthcare, finance, and hiring. While AI holds the potential of improving our lives, it also carries the risk of erroneous outcomes. Algorithmic recourse addresses this problem by enabling individuals to understand why a particular AI decision was made and what actions can be taken to potentially reverse it. Typically, recourse consists of an individual making a first, unsuccessful, attempt and then being given an opportunity to make a second attempt at a later time. Depending on the delay between receiving recourse, taking action, and retrying, the original recourse recommendations may become demonstrably less reliable.

The temporal aspect of algorithmic recourse

Consider, as an example, a loan application scenario, wherein an AI system denies an individual’s application for a loan but provides information on what that individual can do to be approved for the loan if they apply again at a later date. The individual may be told that their loan application was denied because their credit score is 50 points lower than necessary. One could imagine that it takes the individual 6 months to a year to improve their credit score. However, in the meantime, the criteria for loan approval might change, rendering the initial recourse invalid. As a result, the initial recommendation of “improving your credit score by 50 points” may have set false expectations.

The temporal aspect in algorithmic recourse is often overlooked. In a practical setting, we consider time to be intrinsic to the concept of recourse itself, since it involves individuals receiving advice and having the opportunity to act on it at a later time. Ignoring the temporal dimension can lead to unreliable recommendations and false expectations. We addressed this problem by formalizing multi-agent algorithmic recourse, proposing a simulation framework to evaluate recourse over time, and defining a recourse reliability metric.

Simulating multi-agent algorithmic recourse over time

In the multi-agent algorithmic recourse setting, individuals compete for scarce resources over time. Using the previous example, there might be multiple loan applicants competing for a limited number of loans. A black-box classifier (or ranker) determines which applicants should receive positive outcomes. Instead of just looking at one individual trying to achieve a certain score, in this situation, we need to rank individuals to identify the top candidates. Therefore, there is no predefined threshold; it is dynamically set based on the number of available resources and the scores of the highest-ranked individuals.

We introduce two important factors to model individuals’ behavior: adaptation and effort. Adaptation refers to how faithfully an individual follows the provided recommendation, while effort reflects their willingness to make changes based on the recommendation. We also provide examples of possible settings for each of these factors and combine them into two settings, based on how agents perceive the effort required to match a recommendation (i.e., incentive for adaptation), and how they are able to adapt.

The simulation framework encompasses these concepts. At each time step, applicants receive scores, the top-scored applicants receive positive outcomes, and the threshold for a positive outcome is adjusted accordingly. Those who don’t receive positive outcomes are offered recourse recommendations, which they can choose to take action on at each time step of the simulation with varying degrees of adaptation and effort. We also incorporate global and individual parameters to control the difficulty of taking recourse actions and individual willingness.

Quantifying Recourse Reliability

To assess the reliability of recourse, we introduce a new metric, Recourse Reliability (RR). RR quantifies the extent to which agents’ expectations of positive outcomes through recourse align with reality. It measures the proportion of agents who acted on recourse and successfully received positive outcomes compared to those who acted on recourse and expected positive outcomes.

This comprehensive framework allows us to explore and understand the dynamics of multi-agent recourse in various settings, providing insights into the evolving landscape of access to valuable resources.

Between the lines

Among growing concerns on AI ethics, regulations, and digital agency, algorithmic recourse emerged as an essential tool to address these pressing issues. In fact, algorithmic recourse may become legally necessary with the passing of legislation like the European Union AI Act.

Systems providing recourse without considering temporal changes can create unrealistic expectations and even lead to harmful outcomes. For example, in college admissions, a previously denied applicant’s recommended improvements may fall short if the selectivity of universities changes over time. Our framework can be used to provide guidance to system-level decision-makers like banks, colleges, and governments. It offers a means to measure recourse reliability and provide individuals with uncertainty estimates regarding their actions. By adjusting resource constraints based on empirical insights, decision-makers can optimize recourse reliability. For example, colleges can estimate the ideal incoming class size to maintain stable admission thresholds.

In conclusion, the temporal dimension in algorithmic recourse is critical. Understanding the impact of time and evolving contexts is essential for AI systems to provide reliable, fair, and ethical guidance in a rapidly changing world. The consideration of time in algorithmic recourse calls for substantial additional work on understanding recourse reliability in multi-agent multi-time step settings, and on developing recourse methods that reward individuals’ efforts towards recommendations.