Search-based fairness testing for regression-based machine learning systems

Machine learning (ML)-based systems are an important infrastructure that enables our society’s digital transformation, replacing many dangerous, difficult and tedious tasks with automation, with the catch that the resultant decisions, if unchecked, may have a profoundly negative impact on individuals and organisations. Machine learning systems impact us in very deep and personal ways, and are permeating many aspects of life, including healthcare, education, banking, employment and transportation. Such software systems decide how we purchase online (Mattioli 2012), who gets a loan (Olson 2011), what kind of medical diagnosis and treatment we receive (Strickland 2016), and are incorporated into criminal justice systems to determine who goes to jail and who is set free (Ferral).

In recent years, concerns about biased machine learning systems (i.e., software systems that have a machine learning component, and which wrongfully discriminate against certain individuals or groups of individuals in favour of others Friedman and Nissenbaum 1996) have been growing. For example, facial recognition systems often perform poorly on female and African–American faces (Klare et al. 2012). YouTube’s automatic captions for men’s speech are more accurate than women’s (Tatman 2017). Assistant robots in aged-care centres create anxiety in older people when robots work to keep older people happy with pleasant conversations by not telling them the truth (Sharkey 2020). Natural language processing tools for detecting hate speech online are biased against African–American people (Ghaffary 2019). Amazon software decided not to offer same-day delivery to predominantly minority neighbourhoods (Ingold and Soper 2016a). Staples offered online discounts to customers only in wealthier and more affluent neighbourhoods (Hardawar 2012). These examples highlight the importance of the fairness measures in order to quantify the degree of bias in the machine learning systems and fairness testing approaches in order to ensure that machine learning systems do not exhibit biases in their predictions and recommendations.

Various fairness measures have been introduced. For example, conditional statistical parity (Corbett-Davies et al. 2017), equal opportunity (Hardt et al. 2016), counterfactual fairness (Chiappa 2019) and equalised odds (Hardt et al. 2016). However, these fairness measures are only applicable to classification-based ML systems (i.e., machine learning systems that use classification techniques)—which are not purposely designed for regression-based ML systems (i.e., machine learning systems that use regression techniques). In addition, different fairness measures always capture different aspects of bias. Thus, their suitability is still context and domain dependent (Mehrabi et al. 2019). For example, Dieterich et al. (Dieterich et al. 2016) found that COMPAS (i.e., an ML system used by some U.S.A. courts to predict the likelihood of a defendant becoming a recidivist) is not biased when using the disparate impact as the fairness measure, but later is considered unfair when evaluated using other measures (e.g., the equality of error rates (Angwin et al. 2016)).

Similarly, various fairness testing approaches have been introduced in the software engineering literature (Zhang et al. 2020). The goal of these fairness testing approaches is to generate discriminatory inputs, which are the test cases that expose biases (i.e., individual discrimination, group discrimination, and causal discrimination) in the ML-based system under test (SUT). To generate the discriminatory inputs, black-box fairness testing approaches have been proposed, e.g., random test generation (Themis (Galhotra et al. 2017)), directed test generation (Aequitas (Udeshi et al. 2018)), symbolic generation (Aggarwal et al. 2019), as well as white-box fairness testing approaches (Zhang et al. 2020). However, these fairness testing approaches are primarily designed for classification-based ML systems, but not for regression-based ML systems.

Regression-based ML systems use regression techniques to predict continuous values (e.g., patient wait-time estimation). Since the nature of the predicted outcomes of regression-based ML systems is different from classification-based ML systems (i.e., continuous vs binary), existing fairness measures and fairness testing approaches may not be directly applicable, and also not yet effective and efficient. In particular, existing fairness measures for classification-based ML systems are indicative of the number of test cases that exhibit different outcomes (TRUE → FALSE or FALSE → TRUE) for two similar inputs except the difference of a sensitive attribute such as gender. However, for regression-based ML systems, the difference of the predicted outcomes is not binary, but continuous—which is challenging to determine if two predicted continuous outcomes are different or not to be considered as unfair. Thus, one common approach is to use a threshold to determine if a test input is considered discriminatory, i.e., the difference of two predicted outcomes is greater than the threshold (Udeshi et al. 2018). Nevertheless, existing fairness testing approaches that leverage these fairness measures only indicate the number of the discriminatory inputs, without quantifying the magnitude of the difference of the two predicted outcomes.

Recently, Berk et al. (2017) introduced a fairness measure for regression-based ML systems as the average differences of predicted outcomes for two similar inputs which differ in the value of the sensitive attribute, without considering the maximum difference of the two predicted outcomes. Thus, the Berk’s fairness measure may underestimate the possible worst case of unfairness of the SUT. Therefore, the extremely worst cases may go unnoticed during testing if the existing fairness measures are used, making the users of the regression-based ML systems vulnerable to unfair predictions (e.g., female patients are estimated to wait longer than male patients based on the estimation of an emergency department wait-time prediction). To the best of our knowledge, none of the existing fairness measures and testing approaches can estimate the possible worst case of unfairness of the ML-based system under test.

In this paper, we propose (1) a new fairness measure called fairness degree, which is defined as the maximum difference in the predictions for two inputs that are identical except for a sensitive attribute (e.g., gender); and (2) a novel Search-Based Fairness Testing (SBFT) approach to estimate the fairness degree of the ML-based system under test. In contrast to existing fairness testing approaches, SBFT is the first search-based approach designed to test fairness in any machine learning system by employing a genetic algorithm. It has an efficient fitness evaluation procedure which uses an archiving approach for values that are more likely to lead to bias revealing inputs, and a fast local search procedure that improves the search for high quality test inputs that reveal biases. Then, we evaluate the effectiveness and efficiency of our SBFT approach in terms of discovering fairness degree and compare with four existing fairness testing approaches (i.e., Aequitas Udeshi et al. (Udeshi et al. 2018), Themis (Galhotra et al. 2017), symbolic generation (Aggarwal et al. 2019) and random testing).

Our study follows a design science research approach. Fairness metrics for regression-based ML systems are rare and the existing ones ignore to quantify the magnitude of outcome difference. We identify the real problem instance in the context of emergency department (ED) wait-time prediction. We propose a novel fairness metric, i.e., fairness degree, to quantify the degree of bias in a regression-based ML system and a novel search-based fairness testing technique to estimate the fairness degree of an ML system. The proposed solutions are implemented and applied to ED wait-time prediction software. The scientific knowledge gained from our work can be phrased as a technological rule; to measure the fairness of the regression-based ML systems in the context of ED wait-time prediction use fairness degree and search-based techniques to approximate it.

Through an experimental evaluation on 12 emergency department wait-time prediction models based on regression techniques trained from over 1.3 million patient records from 12 hospitals (i.e., the largest emergency department patient datasets to date), we address the following two research questions:

These results confirm that our SBFT approach outperforms the state-of-the-art fairness testing approaches in terms of finding fairness degree of ML software systems based on regression techniques. Thus, we expect that our SBFT approach can help software teams to identify the degree of fairness in predictions and make data-informed decisions about whether such software systems are ready to deploy.

AI-enabled healthcare software is being adopted by the healthcare industry, aiming for improved efficiency, reduced costs and errors, and improvements to both patient satisfaction and experience. It has been estimated that the market value of healthcare software is projected to reach around $29.9 billion by 2023, with a compound annual growth rate (CAGR) of 7.4% from 2018 to 2023.

With the wave of the global COVID-19 pandemic, emergency departments (ED) in many countries are currently overwhelmed and overcrowded due to an unpredictable and unscheduled influx of patients.¹ Overcrowded EDs, usually caused by overcrowded hospitals, jeopardise patient safety and are associated with increased death rates (Di Somma et al. 2015). When EDs are overcrowded, this also cascades back to community health, taking ambulances off the road whilst they are unable to offload patients into ED beds. Patients have limited access to information about ED waiting time and hospital capacity. This lack of transparency from healthcare facilities has negative consequences on patient satisfaction and can make a difficult patient journey much harder for consumers of healthcare (Walker et al. 2020). Hospitals throughout the world have started to deploy AI-enabled healthcare software to support EDs in improving patient satisfaction, healthcare management, and clinical practices. Patient waiting time for healthcare services is identified as one of the key measurements of a responsive healthcare system (Sun et al. 2017), according to the World Health Organization (WHO), and a well-designed and resourced healthcare system should not have long queues for consultations and treatments. Wait times are often highly politicised, for both acute and elective care.

In this paper, we focus on a regression-based machine learning system, which is used in EDs for patient wait-time prediction (aka. ED Software). ED Software provides patients attending the ED at hospitals with an estimated time that they would have to wait before being seen by a doctor or other provider. ED Software is currently being used in hospitals across Melbourne, Australia to estimate the wait time for new patients seeking care (Walker et al. 2021).

Machine learning to predict ED patient wait-times is useful to keep patients informed about the expected wait time before being treated by a doctor (Shah et al. 2015). Such wait-time predictions can also be used to raise awareness of the current flow of waiting patients, improve capacity planning, and identify system bottle-necks (Strobel et al. 2021). The accuracy of the patient wait-time predictions is one of the key factors used in hospitals to better manage patients’ expectations. An overestimated wait-time can cause a patient to decide to delay seeking critical treatment whereas an underestimated wait-time can negatively impact patient experience (Soremekun et al. 2011).

Therefore, ED Software should produce similar wait-time estimations for patients who have the same clinical urgency, arriving at the same time with the same number of patients ahead of them in the queue. This should be the case regardless of individual sensitive attributes (e.g., gender, country of birth, indigenous status, race, religion). Discrimination bias embedded in the prediction models in the ED Software could have a negative impact on patient satisfaction, regardless of the number of patients affected. Patients and families cope better with expected waits than unexpected waits and are disappointed by longer than expected waits. Hospitals that seek to attract more patients (fee-for-service funding) may find customers choosing alternative facilities if their wait-time is overestimated and generate low net promoter scores and ill-will when the wait time is underestimated (also losing customers). Hospitals with block funding also suffer when wait-time predictions are inaccurate, due to reduced patient satisfaction and increased aggression and complaints. Therefore, the use of existing fairness measures (Berk et al. 2017) (e.g., the average differences of predicted outcomes for two similar inputs which differ in the value of the sensitive attribute) may hinder the extreme cases of unfairness, leading to a poor understanding of the ultimate worst case of unfairness of an ML-based system under test and sub-optimal decision-making if such unfair systems are deployed. Thus, a novel fairness degree to indicate the absolute worst case of unfairness by an ML-based system is critically needed.

We conduct this study as design science research. Runeson et al. (2020) designed a visual abstract template to help identify the design science constructs in software engineering research. We use this template to communicate our research methodology as shown in Fig. 1. According to Runeson et al. (2020), there are three main constructs of design science research; i) technological rule, ii) its instantiation in terms of a real problem–solution pair, and iii) the empirical or theoretical support for problem conceptualisation and the solution design.

The scientific knowledge gained from our work can be phrased as a technological rule; to measure the fairness of the regression-based ML systems in the context of ED wait-time prediction use fairness degree and search-based techniques to approximate it.

We understand through the literature that fairness metrics for regression-based ML systems are rare and the existing ones ignore to quantify the magnitude of outcome difference. The real problem instance is identified in the context of emergency department wait time prediction, where extreme errors mean patients either wait longer than the predictions or leave the EDs in case of over-estimations. We propose a novel fairness metric called fairness degree to measure the maximum difference of the outcomes of two identical inputs except for their membership in two different protected groups (Section 4). To find the fairness degree of an ML system, we propose a novel search-based fairness testing technique (Section 5). The proposed solutions are implemented and applied to ED wait-time prediction software.

The relevance of the research, the rigour of the research activities, and the novelty of the technological rule in relation to the underpinning research will be discussed in the Conclusion (Section 9).

A regression-based machine learning system can be formally defined as:

We consider the case where each instance x contains a sensitive feature s and its value is denoted as x^s. An example of a sensitive feature is gender, and its value can be female, male, or non-binary.

In regression-based machine learning systems, the target and predicted values are continuous, and the same value is not likely to occur even twice in the data, which makes it hard to determine whether the system is fair or not.

Berk et al. (2017) introduced the first measure for fairness of the regression-based ML systems. The measure is called individual fairness, and estimates how similarly a model treats two similarly labelled instances, which differ in the value of the sensitive feature.

For every cross pair (x_i,y_i) ∈ g₁ and (x_j,y_j) ∈ g₂, where g₁ and g₂ are groups from the same population that are different in terms of the sensitive attribute s (e.g., women, men), individual fairness measures how differently the machine learning model treats x_i and x_j, weighted by a function of |y_i − y_j|. where d is a fixed non-negative function decreasing in |y_i − y_j|, which takes care of cancellation issues.

More specifically, individual fairness states that the fairness penalty for overestimating several of one group’s labels cannot be mitigated by overestimating several of the other group’s labels. However, this averaging over the instances has a smoothing effect, and hides the impact of outliers.

Previous research shows that assuring machine learning fairness depends more on how fairness is defined than on how it is implemented (Corbett-Davies and Goel 2018), which explains why the issue that has received the most attention in the ML fairness literature is the definition of fairness (Selbst et al. 2019). Indeed, several definitions of fairness have been introduced, such as conditional statistical parity (Corbett-Davies et al. 2017), equal opportunity (Hardt et al. 2016), counterfactual fairness (Chiappa 2019), equalised odds (Hardt et al. 2016), etc.

Feldman et al. (2015), formalise the Equal Employment Opportunity Commission’s 80% rule into a formal measure of fairness called disparate impact, which is used in U.S. law to encode unintentional bias. Disparate impact measures if a decision making process has widely different outcomes for different groups, even as it appears to be neutral. In the well known debate about the COMPAS risk score, the creators argued that COMPAS was fair because the test accuracy was equalised across groups (Dieterich et al. 2016), which was estimated by the disparate impact measure. Instead, ProPublica journalists demonstrated that COMPAS was not fair because another important measure of fairness, known as equality of error rates was violated (Angwin et al. 2016).

This example highlights that existing fairness definitions are simplifications that cannot fully capture the range of existing and overlapping notions of fairness in all philosophical, legal, and sociological contexts. Hence, the suitability of a fairness measure is context dependent (Mehrabi et al. 2019) and must be carefully selected.

Without discounting the importance of avoiding a systemic bias on the whole population, outliers, where the predictions deviate by a large margin from reality, deserve special attention. In other words, minimising extreme deviations in predictions is as important as avoiding systemic bias.

In the context of ED Software, this could mean that the wait-time was grossly overestimated, so the patient may decide to delay treatment or go to another clinic, or underestimated, where the patient may decide to wait and not receive timely treatment (Strobel et al. 2021). Deciding to go to another clinic as a result of overestimation may have negative impacts if the selected clinic is not a specialist one. Not receiving timely treatment due to underestimation can also be detrimental to health. Existing fairness measures do not address this issue, hence we propose a new measure of fairness, which we call fairness degree, and a search-based fairness testing (SBFT) approach that serves for approximating the fairness degree of a machine learning system.

Fairness degree describes the worst-case behaviour of a regression-based machine learning system. It indicates that the machine learning system is more biased (i.e., less fair) if the fairness degree is higher. Formally,

In the case of the ED Software, we would expect the machine learning model to predict similar wait-times for two patients who are identical apart from the sensitive attribute; e.g., it is reasonable to assume that a woman would not need to wait longer than a man to be seen by a doctor, given that all relevant circumstances (urgency, age, etc.) are the same. A larger value of D indicates that the ED Software is more biased. More specifically, this means that there are two patients who are identical except they are members of two different groups (e.g., male and female), and one of them is overestimated a wait-time of D minutes compared to the other.

Identifying the fairness degree of a machine learning system can be computationally expensive for large input spaces. This calls for a more effective method for testing such systems, which provides motivation for our Search-Based Fairness Testing approach introduced in the next section.

Search-Based Fairness Testing (SBFT) is the first approach for testing regression-based machine learning systems. The key research challenge SBFT addresses is the identification of test inputs that reveal large bias for regression-based machine learning systems in order to estimate the fairness degree of the system in an efficient way. The optimisation problem is formulated as: where \({x^{s}_{i}}\) and \({x^{s}_{j}}\) are the values of the sensitive attribute. Existing test generation techniques for fairness use no guidance to find test inputs that can expose the fairness degree of the machine learning system. For example, Aequitas (Udeshi et al. 2018) uses a predefined threshold to identify test inputs that are discriminatory, i.e., if a test input reveals a fairness degree above the threshold it is considered discriminatory. Aequitas considers all test inputs that are discriminatory as equally important, hence this approach is not suitable for finding inputs that maximise the fairness degree.

The proposed approach SBFT is presented in Algorithm 1. It is based on a genetic algorithm, and introduces new enhancements to make the search more efficient and effective in identifying test inputs that reveal the fairness degree. In the next subsections, first we introduce the solution representation, and discuss the fitness evaluation and caching of sensitive variables which helps speed up the evaluation of the fairness degree of a machine learning system (Section 5.1). Next, we discuss the search steps with introducing the genetic operators used to create the new offspring from parent solutions and select individuals to the next population (Section 5.2).

We design a set of experiments to evaluate the effectiveness and efficiency of SBFT. Effectiveness is assessed based on the fairness degree exposed of the system under test (SUT) at the end of the search process, which is the maximum fitness as found during the search. The approach that discovers higher fairness degree of the SUT compared to other approaches is considered more effective. Efficiency, on the other hand is the rate at which the approaches discover fairness degree of the SUT. The baseline approaches are presented in Section 6.1, details of the ED Software, i.e., emergency department wait-time prediction models, used as the experimental subjects are given in Section 6.2, experimental settings are described in Section 6.3, and the results are presented in Section 6.4. In essence, with these experiments, we aim to answer the following research questions:

Our study follows a design science research approach. Runeson et al. (Runeson et al. 2020) proposed that the contributions of a design science research be assessed with respect to relevance, rigour and novelty. In regard to relevance of the research, we observe the problem in a real-world regression-based ML system; ED wait-time prediction software and evaluate the proposed solutions on 12 ML systems from healthcare domain. In Section 6.5, we discussed other regression-based ML systems that our proposed solutions can be applied to. In regard to the rigour of the research activities, we evaluate the proposed solutions on 12 ED Software from healthcare domain, which were built using nearly 1.9 million patient records from 12 hospitals. Each ED Software was evaluated for three sensitive attributes. The proposed SBFT technique was compared against four alternative solutions. We use two-tailed non-parametric Mann-Whitney U-Test and Vargha and Delaney’s \(\widehat {A}_{12}\) statistic to draw conclusions from the results. In regard to the novelty of the technological rule, the proposed SBFT technique discover up to 48 minutes of fairness degree, which could go unnoticed if an existing fairness measure was used due to the smoothing effect (averaging) or not quantifying the magnitude of outcome difference. In the context of EDs, this could mean patients delaying treatments because they did not want to wait. The alternative fairness testing techniques are not as effective and efficient as SBFT to measure the fairness degree for regression-based ML system.

The context is subtle and the impacts are nuanced. Overall, the continued exposure to bias adds up and influences health outcomes - more like a thousand cuts rather than one big event. In this scenario, our approach searches for test cases that expose the maximum difference in wait time prediction by the ED Software for patients that are identical apart from the sensitive attribute. We demonstrate that SBFT discovers discriminatory inputs of larger margins in terms of fairness degree compared to the baseline approaches. SBFT is also more efficient than the baseline approaches for discovering discriminatory inputs. In the future, we plan to investigate a new study from ambulance wait-time prediction software and work on other measures of fairness for regression-based machine learning systems.