Mining for Proxies in Machine Learning Systems

In deployed machine learning systems that affect people’s lives, it is important to ensure that your model is not resulting in disparate impact for some sub-populations of your data. The typical populations of concern might be the so-called protected basis variables such as race, age, or sex, but can also be any subgroup which is relevant to your industry. Creating ML systems that are fair can be tricky due to the complexities of data used for training.

If you want to ensure that your model isn’t resulting in disparate impact across sex, it might be tempting to simply not use sex as an input variable into the model. This tactic, often referred to as fairness-through-unawareness, is insufficient. Even though the model doesn’t know about sex explicitly, it is highly likely that some other input feature (or combination of features) can act as a highly effective proxy for what you were trying to hide from the model.

Many approaches to FairML have focused on mitigating unfairness either by augmenting the training data, the training algorithm, or the model’s outputs. While these approaches help to obtain a more fair model for any given set of inputs, they don’t illuminate for the data scientist what factors were resulting in the model bias. As the model developer, it is helpful to have full awareness of which features are acting as proxies for sensitive attributes. In this post, we describe a technique for effectively surfacing complex combinations of features which act as proxies for a sensitive attribute.

Proxies

Being able to identify proxies can aid the model developer in being judicious about feature selection and model development. At a first pass, identifying proxy variables is as simple as determining which variables have high correlation with a sensitive attribute, and then choosing whether or not to omit those variables. The downside of this approach is that measures of correlation (perhaps Pearson correlation or mutual information) will marginalize over the full domain, perhaps averaging out important effects only seen for some specific values. Further, it could be the case that pairwise combinations (or higher-order) of features are able to form highly effective proxies, more so than any univariate features.

As a fictitious example, suppose we have a dataset where one variable is a binary sex (Female or Male), and another variable is a boolean is_pregnant. While the is_pregnant variable does provide some overall correlation with the sex variable, the strongest proxying effects are seen only for some combinations of the two variables. That is, if we know that is_pregnant = False for a particular person, then we can’t necessarily conclude much about their sex, and likely p(sex = Female) ~= p(sex = Male). However, if is_pregnant = True, then we’ve likely gained significant certainty about sex and p(sex = Female) >> p(sex = Male).

This example illustrates a desirable property when identifying proxies. It is of only limited utility to know that is_pregnant is correlated with our sensitive attribute sex. It is much more useful to know that is_pregnant = True is a strong proxy for sex = Female, whereas is_pregnant = False is uninformative. The difference here is that we aim to identify small pockets in the data (and combinations of features) that form highly predictive proxies.

To accomplish this, we’ll rely on the techniques of Frequent Pattern Mining and Association Rule Mining. This will allow us to surface exactly which values of a variable, and higher-order combinations thereof, are acting as strong proxies for any sensitive attributes.

Association Rules

Association Rule Mining is a rather classic technique in unsupervised pattern discovery, and it can be especially useful in the context of FairML and proxies. The ideas often stem from “market basket analysis”, which imagines we have a large database of purchases at a supermarket. For each shopper, we know what items they bought together, such as {milk, eggs, cheese} for one shopper and {diapers, beer} for another. From the co-occurrences of items in baskets, our goals are to (1) identify commonly co-occurring items and (2) identify directional correlations. For our first goal, we can use Frequent Pattern Mining techniques such as FPGrowth, which will result in a list of item combinations that were highly probable in the dataset. Going a step further, we can apply Association Rule Mining to identify not just correlated items, but items correlated with a particular directionality. For example, if a person bought sunglasses and a bathing suit, then maybe they also bought sunscreen. But if all we know is that they bought sunscreen, they’re not necessarily in the market for new shades.

Association Rules are of the form “if A, then B”. The antecedent A can be one or more items, and the consequent B can be one or more items. Importantly, we’re not looking solely for relationships that are 100% fulfilled in our dataset. Instead, we’re looking for consequents that follow antecedents with higher probability than we might expect. Quantifying those base-level expectations means we have to introduce some new terminology and measures.

Measures

For a particular itemset (whether it is an antecedent, consequent, or neither), the support for that itemset is a measure of how frequently the itemset occurs in the data. We can think of it as the overall probability of occurrence for an itemset. Note that for a particular itemset, we need to tabulate not just exact matches to that itemset, but also all other larger itemsets that include at least that one. An itemset with high support (like 0.80) would mean that 80% of the dataset is exactly this itemset. As you might imagine, itemsets with fewer items tend to have more support than itemsets with more items. For example, the itemset {milk} probably occurred in many of our shoppers’ baskets, whereas the combination of {milk, lettuce, hat} was probably more rare.

For a particular rule “if A, then B”, the confidence quantifies how often that rule was true. Another way to think about it is: Whenever you saw A, what’s the probability that you would see B? Naturally, if a rule were a really strong correlation, then confidence in the consequent would be close to 100%. In contrast, for a weaker relationship, knowing about antecedent A perhaps doesn’t give us much certainty at all about B.

Other useful concepts such as lift and conviction will help us quantify the extent to which A helps us predict B more than we’d be able to predict B otherwise.

Mining for Proxies

Identifying association rules in a dataset can be a useful technique for uncovering proxies for sensitive variables. In this case, we’ll be looking for association rules of the form “if A, then B” where the consequent B is one of the values of our sensitive attributes. For example, if we want to find proxies for Female in our dataset, we can limit ourselves to association rules where the consequent is the itemset {Female} and nothing else. Then, the antecedent of such a rule would be a feature value, or combination, that is highly predictive of a person being Female. The confidence of the rule tells us how strong the association is: a confidence near 50% means that the antecedent isn’t actually a very effective proxy for Female, whereas a confidence near 100% means we have found a combination of feature values that can identify females with near certainty. Let’s try this idea out and see how it works.

Identifying Proxies for Sex

We’ll use the UCI Adult dataset, which includes financial and demographic data about a group of 30,000 adults. While this dataset is often used for classification tasks (predicting if a person has high income), we’ll ignore for now the supervised learning aspect. Instead we’ll focus on some of the demographic variables (such as Sex or Race) and investigate whether these can be proxied by other variables (such as Education, Occupation, MaritalStatus and so on).

We’ll focus on Sex and use Association Rule Mining to identify strong proxies. For generating candidate itemsets, we’ll focus first on categorical variables. Continuous variables can be easily incorporated by discretizing their domains, either manually (such as quartiles) or by dynamically identifying bin splits (in a similar spirit to decision tree algorithms). It is up to us to identify how many input features we might include for itemsets and what order of combinations we want to consider. For ease of interpretability, we might constrain ourselves to first-, second-, and third-order combinations. That is, in the antecedents of our rules, we’ll only want to consider itemsets with one, two, or three items. This choice is up to us, depending on what level of rule complexity we want to access. As we increase this complexity, the combinatorics of itemset and rule generation expands. Luckily, algorithms such as FPGrowth, which are based on tree structures, will allow us to apply these ideas to large datasets and complex itemsets, if we desire.

Let’s see whether the variables MaritalStatus, Occupation, and Education can form proxies for Sex. Remember we’re not just looking at the variables holistically, but instead identifying whether certain values and combinations of those values can be highly predictive of certain values of Sex. We’ll generate rules up to second-order and see which rules can predict Male with high confidence. A few top examples are below.

We see that some (but not all) occupations and educations are strong proxies for males. For example, for all the rows in the data where Occupation was Repair and MaritalStatus was Married, those people were male 99% of the time. This combination is also fairly prevalent, as the antecedent support is 8%, a sizable chunk of the data. So for this pocket of the data, we have a near-perfect proxy for Sex. The same applies for numerous other combinations, though they are less prevalent. There are many association rules generated with confidence greater than 80% for predicting Male. They typically entail small pockets of the data (support of 1% to 5%). The effect of each is small, but the aggregate is that for large volumes of the data space, we can predict males with high confidence.

Similar results are returned if we look for proxies for Female.

Here, we see that MaritalStatus can be a strong proxy for Female in some instances. Especially strong is the antecedent “if MaritalStatus is Widowed”, an unsurprising rule since the term “widowed” is fairly gendered to begin with. In combination with Occupation, MaritalStatus can become an even more precise predictor of Female.

Take for example the rule “if Occupation is Admin-Clerical, then Sex is Female”. This rule’s confidence is 67%, so a bit higher than the base-rate of Female in the dataset, but it does have a support of over 10%. The higher order rule “if Occupation is Admin-Clerical and Education is High School, then Sex is Female”, has slightly higher confidence (at 70%) and slightly lower support (at 5%). As the antecedent becomes more precise, we can find smaller pockets and subsets of the data that yield more confident proxies of the sensitive attribute.

Intuitively, these results are unsurprising: many jobs are highly correlated with males or females. But we now have a more precise way to understand this effect. The support of each rule tells us how prevalent a particular combination is in the data, and the confidence tells us how certain the proxying can be.

This analysis is easy to apply to any sensitive attributes we want to explore. We could identify proxies for certain races, age groups, health conditions, and so on.

Next Steps

Given how informative some of these combinations can be, it would be unsurprising for an ML model to pick up on these proxies even if it didn’t have direct access to sensitive attributes. Any sufficiently complex algorithm (even just a decision tree or tree ensemble) should easily be able to capture the simple combinations highlighted here, if they are helpful in predicting the target variable. Surfacing these relationships should be an early part of the model development process and should play a role in feature selection. Ultimately, our goal must be to mitigate disparate impact in the final system. With this clarity into proxies, we could choose to (i) omit certain variables from a model, (ii) omit/recode certain values of a variable from the model, or (iii) turn to training-time and post-hoc methods for bias mitigation.