Interventional Fairness : Causal Database Repair for Algorithmic Fairness
Salimi, Babak
Luke Rodriguez
Howe, Bill
Suciu, Dan
Fairness is increasingly recognized as a critical component of machine learning systems. However, it is the underlying data on which these systems are trained that often reflect discrimination, suggesting a database repair problem. Existing treatments of fairness rely on statistical correlations that can be fooled by statistical anomalies, such as Simpson's paradox. Proposals for causality-based definitions of fairness can correctly model some of these situations, but they require specification of the underlying causal models. In this paper, we formalize the situation as a database repair problem, proving sufficient conditions for fair classifiers in terms of admissible variables as opposed to a complete causal model. We show that these conditions correctly capture subtle fairness violations. We then use these conditions as the basis for database repair algorithms that provide provable fairness guarantees about classifiers trained on their training labels. We evaluate our algorithms on real data, demonstrating improvement over the state of the art on multiple fairness metrics proposed in the literature while retaining high utility.
 Today I'll be talking about algorithmic fairness. This is a joint work with Luke Rodriguez, Bill Howe, and Dan Sushu. So the problem that we are going to look into today is to ensure that prediction algorithms are fair. I don't think I need to motivate studying this problem after Lisa's awesome keynote yesterday, but anyways, algorithm begun replacing human decision makers in number of sensitive domains ranging from helping banks to determine the creditworthiness of their customers and helping judges to score how likely a criminal will commit a crime in future. So we want to make sure that these algorithms are fair. So what do we mean by fairness? Intuitively fairness, we say an algorithm is fair if it is not biased against, systematically bias against minority groups. There have been a number of attempts to reduce fairness, which is of course a social idea into a mathematical formula, but no agreement has been reached yet. In this talk, we're particularly going to focus on fairness in the context of learning algorithms. And when it comes to the learning algorithms, the outcome of the system is determined by the data that we use to train these algorithms, right? So it's not algorithms that are unfair and biased. It's the underlying data that we use to train them that are biased. And data can be biased for a number of reasons, for example, selection bias, measurement bias, and lack of sampling diversity, but you may confirm that a huge part of the problem is the preexisting or historical bias. The available data are collected from chaotic society polluted by years of institutionalized racism and discrimination. Now if we use this raw data to train machine learning algorithms, the model is going to pick up the existing bias and reinforce and amplify it. Two famous examples of these sort of bias is the gender discrimination recently observed in Google Word 2 Wector, Word Embeddings, and Amazon recruitment tool. So in general, we want to make sure that we train our model on data that are collected from the work we wish we had rather than the work that we do have. And this work we advocate for accounting for historical bias upstream by repairing data prior to training models, because this would be the most flexible approach in terms of the data science pipeline, and it's independent of the underlying machine learning algorithm. So our system, Cappuccine, proposes a novel causal notion of fairness, which improves the existing definition. It reduces the problem of building costly, fair classifiers to a database repair problem with respect to integrity constraints. And finally, it develops a set of efficient algorithms to address the repair problem. And if you're wondering why Cappuccine, it actually refers to this funny YouTube video which went viral a couple of years ago and shows that Cappuccine mind keys, they have a sense of fairness. So there has been lots of research interest in this field, mostly machine learning. Most of these works actually use associational metrics to define discrimination and bias. Roughly speaking, they define discrimination as a sort of a strong correlation between a sensitive attribute such as race and gender, and either the outcome or precision of a machine learning algorithm. However, no matter what, all of these associational metrics are subject to a statistical anomaly such as Simpson's paradox and could be misleading. I'm going to share with you one famous example here in 1973, UC Berkeley was sued for gender discrimination because of the fact that in that year, as you see up there, men were more likely to get admitted than women, and the margin was so huge which suggested the strongest disparity against females. However, once the admission results were broken down by the department, the trend was totally reversed. However, no significant distinction between men, admission result of men and women were reported. So in order to somehow explain about this paradoxical observation, we need causal inference. We need to be able to incorporate our background knowledge using the language of causal models. Causal models are simply directed acyclist graph that shows the causal relationship between the attributes and the domain. Specifically each node in this graph shows one attribute in our domain, and we have an arrow between two nodes if there is a causal influence going on between them. This simple causal diagram right there suggests that gender and admission results are correlated, but this correlation might be because gender can influence admission result because through applicants' free will to choose the department, right? Maybe women tended to apply to a more competitive department which turned out to be true in this case. Actually women tended to apply to department F, which as you see has a very low admission rate. So this example somehow exonerated UC Berkeley from accusations of discrimination. This is causal model. So this example suggests association or notion of fairness are insufficient to guarantee fairness and capture it. We need for proving or disproving discrimination, we need evidence of causality. So now let's see if we can use causal diagram to regressly define fairness and discrimination. Let's extend the UC Berkeley example a little bit. Suppose we are dealing with a college in which the admission decisions are made by applicants' gender, applicants' qualification, their extracurricular activities such as their hubbys, right? Clearly this college is discriminative. So the first attempt to define fairness is to say, okay, the sensitive attribute should not be causally related to the outcome of an algorithm, right? In terms of the causal diagram, there is, we should not have any causal pass or any directed pass from sensitive attribute to the outcome. But this definition seems to be too strict and practical because whether you like it or not, gender, race and other sensitive attributes, they affect so many things. Gender would affect choice of department, would affect the courses that people take, would affect their hubbys, right? And not all of these influences can be done so them socially as discriminative. So for example, in this case, the passing, green seems to be totally legit and even unavoidable because applicants have the free will to choose their department and the application decisions are made by each department. In order to be able to distinguish between these discriminative and non-discriminative effects, our system let the user to partition the variables into admissible and inadmissables. Intuitively admissible variables are those such that the effect of sensitive attributes to outcome of an algorithm through these variables, them to be socially not discriminative. In this case, choice of department and qualification seems to be admissible. We implicitly label the other variables, in this case gender and hubbys inadmissable. So this partitioning is totally subjective. It could be different from one context to another context. And we can use it to somehow reflect either the law or social norms and values. There is no magic that can tell us which attribute is admissible and which attributes inadmissible. We cannot reduce fairness to a mathematical formula. So with this partitioning in place now, here comes the second attempt for defining fairness. Now we can say, this is a more relaxed definition, we can say, okay, an algorithm is fair if the sensitive attributes only affect the outcome of the algorithm through these admissible variables. This seems to be a good definition, but there is a problem with it. It requires the causal diagram to be fully specified. In practice, we typically have only partial knowledge. In order to handle this case, we have a definition based on counterfactuals and intervention, which is essentially testable against data subject to existing partial knowledge about the generative model. However the definition is too technical, I'm not going to discuss it today. Please see the paper if you're interested. In this talk, I'm going to keep working with that simple definition based on causal model. Okay, so now suppose you're collected historical data from this college, which is discriminative, right? And we want to build a model to predict admission results. Clearly, the machine learning model is going to pick up the existing discrimination and become discriminative. Now the question becomes, can we still use this bias historical data to train a model which is not causally biased? And the answer to this question is yes, there exists a very naive and baseline approach for doing that. Just drop all sensitive variables and all inadmissible variables from your data. In this case, just train your model based on choice of department and qualification. Then your machine learning model, whatever it is, is going to be a deterministic function of these admissible variables and your algorithm is going to be fair. So there are issues with this simple approach. First of all, it cannot be used in data release situation where data may have several use cases and want to include all attributes in your data, right? And the second issue is it can negatively impact utility because this inadmissible variable, they may still have predictive power which is not discriminative. This motivates our main solution. Our solution is to repair data, historical data, T2Optin, and other data set D prime, such that D prime reflect the word as we wish we had, right? So how does that word look like in our example? We wish that vision results were not made very agnostic to applicants' gender and applicants' hobby, right? We wish the data were generated by this generative model. And since we cannot change the word, or maybe we can change the word only through changing data, let's change data and fool the machine learning algorithms as if data were collected from a fair word, right? If you are now familiar with graphical models and in particular causal diagrams, you know that these diagrams, they essentially include a bunch of conditional independence constraints, such that any data that is generated according to this causal model would satisfy those constraints. And you can read this constraint of the causal diagram by applying a graphical criterion which is called the separation. In this case, the constraint that holds in this ideal word and we are interested in is that constraint, given applicants' qualification and choice of department, admission decision should be independent or is independent in that word of applicants' gender and applicants' hobby, right? It turns out that this constraint can be translated to something that we know very well in database community, multivalor dependencies. In this very case, it translates to the multivalor dependency, D and Q, multi-determine, A. So the repair problem becomes to add or remove tuples from your historical data, training data such that the obtained data becomes close to the original data according to some distance function and consistent with your multivalor dependency, right? Unfortunately, this problem turned out to be NP-hard even for one multivalor dependency. What we did, we proposed several efficient algorithms for solving this problem, including a reduction to max set and low-rank matrix factorization. Then we show that any classifier, trained using the repair to historical data D prime, is going to be fair, costly, fair, even on unseen test data under very mild assumptions. Okay, so now let's see if this idea would work in practice for this experiment. We use UCI adult income census data which contains attributes such as occupation, education, and marital status, and the prediction task is to predict whether individual receives high or low income. Now, suppose a bank is interested in using this data set to train a model to assist them to, I don't know, verify the reliability of their customers. Then the use of, if we use raw data to train a model, it is likely that the model is going to be discriminative against one because of the historical income gap between man and woman. Right? For the sake of illustration, we assume all variables are admissible except for marital status. Then we use our system to remove from data the causal influence of gender on income, both direct and indirect causal influence of gender to income via marital status. Then we use the raw data and the repaired data to train several classifiers. Then we measure bias and accuracy using fivefold cross validation. Note that we only repair the training data, bias and accuracy where measured on untouched test data to see if our approach is generalizable to unseen test data. So then the goal was to see if Capuchin can really remove discrimination without losing too much accuracy. This graph shows utility versus bias. Utility was measured by accuracy and bias essentially quantifies the effect of gender on outcome of an algorithm through these two discriminatory paths. We compare the bias and accuracy for raw data or repair methods and that naive idea of removing all that inadmissible variables. As you observe, at the cost of only two percent accuracy, our system almost removed bias. I should note that the residual bias is not statistically significant in most of the cases. These are just random signals. In most of the cases, it's actually in favor of minority groups. We also compared Capuchin with two baseline machine learning algorithms. Our preprocessing algorithm, namely Flatman and Kalman, they actually use different... The target is something different. The target is to enforce on training data what they call the statistical parity, which is very simple in this case, just to ensure that men and women, they have the same probability of high income. They enforce this constraint and as you observe, as a side effect, they were also reduced cost of bias, but not quite as successful as Capuchin. Both in terms of bias reduction and accuracy. We also compared our system with this method on number of associational metrics, a statistical parity, which is just a difference between positive outcome of algorithm between men and women, false positive balance, which is the difference between false positive rate for men and women and true negative balance, which is the difference between true negative between men and women. These numbers, the lower the bet. As you observe, Capuchin were able to, as a side effect, were able to also reduce associational metrics for fairness. In most cases, even it was quite more successful than the state of the art machine learning algorithm. Why this happens? Because it's actually quite expected because at the end of the day, even our approach reduces the correlation between sensitive attribute and outcome of the algorithm, but we do it in the right way. With this, I'm going to finish with some conclusions. We discussed the popular associational fairness definitions are misleading. Any of those 21 fairness definitions, I can show you one example in which they don't make sense. I believe that there's somewhere between harmless and meaningless. Harmful and meaningless, sorry. In this talk, we discussed how we can use causal model to define fairness. We discussed admissible and admissible partitioning as a way to be able to express different fairness constraints. And then we discussed how we can reduce the problem of building fair predictions, predictive models into a database with respect to integrity constraints. Thanks for listening.
 Today I'll be talking about algorithmic fairness.  This is a joint work with Luke Rodriguez, Bill Howe, and Dan Sushu.  So the problem that we are going to look into today is to ensure that prediction algorithms  are fair.  I don't think I need to motivate studying this problem after Lisa's awesome keynote yesterday,  but anyways, algorithm begun replacing human decision makers in number of sensitive domains  ranging from helping banks to determine the creditworthiness of their customers and helping  judges to score how likely a criminal will commit a crime in future.  So we want to make sure that these algorithms are fair.  So what do we mean by fairness?  Intuitively fairness, we say an algorithm is fair if it is not biased against, systematically  bias against minority groups.  There have been a number of attempts to reduce fairness, which is of course a social idea  into a mathematical formula, but no agreement has been reached yet.  In this talk, we're particularly going to focus on fairness in the context of learning  algorithms.  And when it comes to the learning algorithms, the outcome of the system is determined by  the data that we use to train these algorithms, right?  So it's not algorithms that are unfair and biased.  It's the underlying data that we use to train them that are biased.  And data can be biased for a number of reasons, for example, selection bias, measurement bias,  and lack of sampling diversity, but you may confirm that a huge part of the problem is  the preexisting or historical bias.  The available data are collected from chaotic society polluted by years of institutionalized  racism and discrimination.  Now if we use this raw data to train machine learning algorithms, the model is going to  pick up the existing bias and reinforce and amplify it.  Two famous examples of these sort of bias is the gender discrimination recently observed  in Google Word 2 Wector, Word Embeddings, and Amazon recruitment tool.  So in general, we want to make sure that we train our model on data that are collected  from the work we wish we had rather than the work that we do have.  And this work we advocate for accounting for historical bias upstream by repairing data  prior to training models, because this would be the most flexible approach in terms of  the data science pipeline, and it's independent of the underlying machine learning algorithm.  So our system, Cappuccine, proposes a novel causal notion of fairness, which improves the  existing definition.  It reduces the problem of building costly, fair classifiers to a database repair problem  with respect to integrity constraints.  And finally, it develops a set of efficient algorithms to address the repair problem.  And if you're wondering why Cappuccine, it actually refers to this funny YouTube video  which went viral a couple of years ago and shows that Cappuccine mind keys, they have  a sense of fairness.  So there has been lots of research interest in this field, mostly machine learning.  Most of these works actually use associational metrics to define discrimination and bias.  Roughly speaking, they define discrimination as a sort of a strong correlation between  a sensitive attribute such as race and gender, and either the outcome or precision of a machine  learning algorithm.  However, no matter what, all of these associational metrics are subject to a statistical anomaly  such as Simpson's paradox and could be misleading.  I'm going to share with you one famous example here in 1973, UC Berkeley was sued for gender  discrimination because of the fact that in that year, as you see up there, men were more  likely to get admitted than women, and the margin was so huge which suggested the strongest  disparity against females.  However, once the admission results were broken down by the department, the trend was totally  reversed.  However, no significant distinction between men, admission result of men and women were  reported.  So in order to somehow explain about this paradoxical observation, we need causal inference.  We need to be able to incorporate our background knowledge using the language of causal models.  Causal models are simply directed acyclist graph that shows the causal relationship between  the attributes and the domain.  Specifically each node in this graph shows one attribute in our domain, and we have an  arrow between two nodes if there is a causal influence going on between them.  This simple causal diagram right there suggests that gender and admission results are correlated,  but this correlation might be because gender can influence admission result because through  applicants' free will to choose the department, right?  Maybe women tended to apply to a more competitive department which turned out to be true in this  case.  Actually women tended to apply to department F, which as you see has a very low admission  rate.  So this example somehow exonerated UC Berkeley from accusations of discrimination.  This is causal model.  So this example suggests association or notion of fairness are insufficient to guarantee fairness  and capture it.  We need for proving or disproving discrimination, we need evidence of causality.  So now let's see if we can use causal diagram to regressly define fairness and discrimination.  Let's extend the UC Berkeley example a little bit.  Suppose we are dealing with a college in which the admission decisions are made by applicants'  gender, applicants' qualification, their extracurricular activities such as their hubbys, right?  Clearly this college is discriminative.  So the first attempt to define fairness is to say, okay, the sensitive attribute should  not be causally related to the outcome of an algorithm, right?  In terms of the causal diagram, there is, we should not have any causal pass or any directed  pass from sensitive attribute to the outcome.  But this definition seems to be too strict and practical because whether you like it  or not, gender, race and other sensitive attributes, they affect so many things.  Gender would affect choice of department, would affect the courses that people take,  would affect their hubbys, right?  And not all of these influences can be done so them socially as discriminative.  So for example, in this case, the passing, green seems to be totally legit and even  unavoidable because applicants have the free will to choose their department and the application  decisions are made by each department.  In order to be able to distinguish between these discriminative and non-discriminative  effects, our system let the user to partition the variables into admissible and inadmissables.  Intuitively admissible variables are those such that the effect of sensitive attributes  to outcome of an algorithm through these variables, them to be socially not discriminative.  In this case, choice of department and qualification seems to be admissible.  We implicitly label the other variables, in this case gender and hubbys inadmissable.  So this partitioning is totally subjective.  It could be different from one context to another context.  And we can use it to somehow reflect either the law or social norms and values.  There is no magic that can tell us which attribute is admissible and which attributes  inadmissible.  We cannot reduce fairness to a mathematical formula.  So with this partitioning in place now, here comes the second attempt for defining fairness.  Now we can say, this is a more relaxed definition, we can say, okay, an algorithm is fair if  the sensitive attributes only affect the outcome of the algorithm through these admissible variables.  This seems to be a good definition, but there is a problem with it.  It requires the causal diagram to be fully specified.  In practice, we typically have only partial knowledge.  In order to handle this case, we have a definition based on counterfactuals and intervention,  which is essentially testable against data subject to existing partial knowledge about  the generative model.  However the definition is too technical, I'm not going to discuss it today.  Please see the paper if you're interested.  In this talk, I'm going to keep working with that simple definition based on causal model.  Okay, so now suppose you're collected historical data from this college, which is discriminative,  right?  And we want to build a model to predict admission results.  Clearly, the machine learning model is going to pick up the existing discrimination and  become discriminative.  Now the question becomes, can we still use this bias historical data to train a model  which is not causally biased?  And the answer to this question is yes, there exists a very naive and baseline approach  for doing that.  Just drop all sensitive variables and all inadmissible variables from your data.  In this case, just train your model based on choice of department and qualification.  Then your machine learning model, whatever it is, is going to be a deterministic function  of these admissible variables and your algorithm is going to be fair.  So there are issues with this simple approach.  First of all, it cannot be used in data release situation where data may have several use cases  and want to include all attributes in your data, right?  And the second issue is it can negatively impact utility because this inadmissible variable,  they may still have predictive power which is not discriminative.  This motivates our main solution.  Our solution is to repair data, historical data, T2Optin, and other data set D prime,  such that D prime reflect the word as we wish we had, right?  So how does that word look like in our example?  We wish that vision results were not made very agnostic to applicants' gender and applicants'  hobby, right?  We wish the data were generated by this generative model.  And since we cannot change the word, or maybe we can change the word only through changing  data, let's change data and fool the machine learning algorithms as if data were collected  from a fair word, right?  If you are now familiar with graphical models and in particular causal diagrams, you know  that these diagrams, they essentially include a bunch of conditional independence constraints,  such that any data that is generated according to this causal model would satisfy those constraints.  And you can read this constraint of the causal diagram by applying a graphical criterion  which is called the separation.  In this case, the constraint that holds in this ideal word and we are interested in is  that constraint, given applicants' qualification and choice of department, admission decision  should be independent or is independent in that word of applicants' gender and applicants'  hobby, right?  It turns out that this constraint can be translated to something that we know very well in database  community, multivalor dependencies.  In this very case, it translates to the multivalor dependency, D and Q, multi-determine, A. So  the repair problem becomes to add or remove tuples from your historical data, training  data such that the obtained data becomes close to the original data according to some distance  function and consistent with your multivalor dependency, right?  Unfortunately, this problem turned out to be NP-hard even for one multivalor dependency.  What we did, we proposed several efficient algorithms for solving this problem, including  a reduction to max set and low-rank matrix factorization.  Then we show that any classifier, trained using the repair to historical data D prime,  is going to be fair, costly, fair, even on unseen test data under very mild assumptions.  Okay, so now let's see if this idea would work in practice for this experiment.  We use UCI adult income census data which contains attributes such as occupation, education,  and marital status, and the prediction task is to predict whether individual receives  high or low income.  Now, suppose a bank is interested in using this data set to train a model to assist them  to, I don't know, verify the reliability of their customers.  Then the use of, if we use raw data to train a model, it is likely that the model is going  to be discriminative against one because of the historical income gap between man and  woman.  Right?  For the sake of illustration, we assume all variables are admissible except for marital  status.  Then we use our system to remove from data the causal influence of gender on income, both  direct and indirect causal influence of gender to income via marital status.  Then we use the raw data and the repaired data to train several classifiers.  Then we measure bias and accuracy using fivefold cross validation.  Note that we only repair the training data, bias and accuracy where measured on untouched  test data to see if our approach is generalizable to unseen test data.  So then the goal was to see if Capuchin can really remove discrimination without losing  too much accuracy.  This graph shows utility versus bias.  Utility was measured by accuracy and bias essentially quantifies the effect of gender  on outcome of an algorithm through these two discriminatory paths.  We compare the bias and accuracy for raw data or repair methods and that naive idea of removing  all that inadmissible variables.  As you observe, at the cost of only two percent accuracy, our system almost removed bias.  I should note that the residual bias is not statistically significant in most of the cases.  These are just random signals.  In most of the cases, it's actually in favor of minority groups.  We also compared Capuchin with two baseline machine learning algorithms.  Our preprocessing algorithm, namely Flatman and Kalman, they actually use different...  The target is something different.  The target is to enforce on training data what they call the statistical parity, which  is very simple in this case, just to ensure that men and women, they have the same probability  of high income.  They enforce this constraint and as you observe, as a side effect, they were also reduced cost  of bias, but not quite as successful as Capuchin.  Both in terms of bias reduction and accuracy.  We also compared our system with this method on number of associational metrics, a statistical  parity, which is just a difference between positive outcome of algorithm between men and  women, false positive balance, which is the difference between false positive rate for  men and women and true negative balance, which is the difference between true negative between  men and women.  These numbers, the lower the bet.  As you observe, Capuchin were able to, as a side effect, were able to also reduce associational  metrics for fairness.  In most cases, even it was quite more successful than the state of the art machine learning  algorithm.  Why this happens?  Because it's actually quite expected because at the end of the day, even our approach reduces  the correlation between sensitive attribute and outcome of the algorithm, but we do it  in the right way.  With this, I'm going to finish with some conclusions.  We discussed the popular associational fairness definitions are misleading.  Any of those 21 fairness definitions, I can show you one example in which they don't make  sense.  I believe that there's somewhere between harmless and meaningless.  Harmful and meaningless, sorry.  In this talk, we discussed how we can use causal model to define fairness.  We discussed admissible and admissible partitioning as a way to be able to express different fairness  constraints.  And then we discussed how we can reduce the problem of building fair predictions, predictive  models into a database with respect to integrity constraints.  Thanks for listening.
Salimi_Rodriguez_Howe_Suciu_0_143.png Salimi_Rodriguez_Howe_Suciu_144_203.png Salimi_Rodriguez_Howe_Suciu_204_251.png Salimi_Rodriguez_Howe_Suciu_252_2051.png Salimi_Rodriguez_Howe_Suciu_2052_3659.png Salimi_Rodriguez_Howe_Suciu_3660_4163.png Salimi_Rodriguez_Howe_Suciu_4164_4379.png Salimi_Rodriguez_Howe_Suciu_4380_5843.png Salimi_Rodriguez_Howe_Suciu_5844_6395.png Salimi_Rodriguez_Howe_Suciu_6396_8111.png Salimi_Rodriguez_Howe_Suciu_8112_9227.png Salimi_Rodriguez_Howe_Suciu_9228_10103.png Salimi_Rodriguez_Howe_Suciu_10104_11507.png Salimi_Rodriguez_Howe_Suciu_11508_12203.png Salimi_Rodriguez_Howe_Suciu_12204_12647.png Salimi_Rodriguez_Howe_Suciu_12648_13955.png Salimi_Rodriguez_Howe_Suciu_13956_14471.png Salimi_Rodriguez_Howe_Suciu_14472_14975.png Salimi_Rodriguez_Howe_Suciu_14976_15923.png Salimi_Rodriguez_Howe_Suciu_15924_16751.png Salimi_Rodriguez_Howe_Suciu_16752_17963.png Salimi_Rodriguez_Howe_Suciu_17964_19979.png Salimi_Rodriguez_Howe_Suciu_19980_21335.png Salimi_Rodriguez_Howe_Suciu_21336_22463.png Salimi_Rodriguez_Howe_Suciu_22464_23939.png Salimi_Rodriguez_Howe_Suciu_23940_25355.png Salimi_Rodriguez_Howe_Suciu_25356_25472.png
Today I'll be talking about algorithmic fairness. This is a joint work with Luke Rodriguez, Bill Howe, and Dan Sushu. So the problem that we are going to look into today is to ensure that prediction algorithms are fair. I don't think I need to motivate studying this problem after Lisa's awesome keynote yesterday, but anyways, algorithm begun replacing human decision makers in number of sensitive domains ranging from helping banks to determine the creditworthiness of their customers and helping judges to score how likely a criminal will commit a crime in future. So we want to make sure that these algorithms are fair. So what do we mean by fairness? Intuitively fairness, we say an algorithm is fair if it is not biased against, systematically bias against minority groups. There have been a number of attempts to reduce fairness, which is of course a social idea into a mathematical formula, but no agreement has been reached yet. In this talk, we're particularly going to focus on fairness in the context of learning algorithms. And when it comes to the learning algorithms, the outcome of the system is determined by the data that we use to train these algorithms, right? So it's not algorithms that are unfair and biased. It's the underlying data that we use to train them that are biased. And data can be biased for a number of reasons, for example, selection bias, measurement bias, and lack of sampling diversity, but you may confirm that a huge part of the problem is the preexisting or historical bias. The available data are collected from chaotic society polluted by years of institutionalized racism and discrimination. Now if we use this raw data to train machine learning algorithms, the model is going to pick up the existing bias and reinforce and amplify it. Two famous examples of these sort of bias is the gender discrimination recently observed in Google Word 2 Wector, Word Embeddings, and Amazon recruitment tool. So in general, we want to make sure that we train our model on data that are collected from the work we wish we had rather than the work that we do have. And this work we advocate for accounting for historical bias upstream by repairing data prior to training models, because this would be the most flexible approach in terms of the data science pipeline, and it's independent of the underlying machine learning algorithm. So our system, Cappuccine, proposes a novel causal notion of fairness, which improves the existing definition. It reduces the problem of building costly, fair classifiers to a database repair problem with respect to integrity constraints. And finally, it develops a set of efficient algorithms to address the repair problem. And if you're wondering why Cappuccine, it actually refers to this funny YouTube video which went viral a couple of years ago and shows that Cappuccine mind keys, they have a sense of fairness. So there has been lots of research interest in this field, mostly machine learning. Most of these works actually use associational metrics to define discrimination and bias. Roughly speaking, they define discrimination as a sort of a strong correlation between a sensitive attribute such as race and gender, and either the outcome or precision of a machine learning algorithm. However, no matter what, all of these associational metrics are subject to a statistical anomaly such as Simpson's paradox and could be misleading. I'm going to share with you one famous example here in 1973, UC Berkeley was sued for gender discrimination because of the fact that in that year, as you see up there, men were more likely to get admitted than women, and the margin was so huge which suggested the strongest disparity against females. However, once the admission results were broken down by the department, the trend was totally reversed. However, no significant distinction between men, admission result of men and women were reported. So in order to somehow explain about this paradoxical observation, we need causal inference. We need to be able to incorporate our background knowledge using the language of causal models. Causal models are simply directed acyclist graph that shows the causal relationship between the attributes and the domain. Specifically each node in this graph shows one attribute in our domain, and we have an arrow between two nodes if there is a causal influence going on between them. This simple causal diagram right there suggests that gender and admission results are correlated, but this correlation might be because gender can influence admission result because through applicants' free will to choose the department, right? Maybe women tended to apply to a more competitive department which turned out to be true in this case. Actually women tended to apply to department F, which as you see has a very low admission rate. So this example somehow exonerated UC Berkeley from accusations of discrimination. This is causal model. So this example suggests association or notion of fairness are insufficient to guarantee fairness and capture it. We need for proving or disproving discrimination, we need evidence of causality. So now let's see if we can use causal diagram to regressly define fairness and discrimination. Let's extend the UC Berkeley example a little bit. Suppose we are dealing with a college in which the admission decisions are made by applicants' gender, applicants' qualification, their extracurricular activities such as their hubbys, right? Clearly this college is discriminative. So the first attempt to define fairness is to say, okay, the sensitive attribute should not be causally related to the outcome of an algorithm, right? In terms of the causal diagram, there is, we should not have any causal pass or any directed pass from sensitive attribute to the outcome. But this definition seems to be too strict and practical because whether you like it or not, gender, race and other sensitive attributes, they affect so many things. Gender would affect choice of department, would affect the courses that people take, would affect their hubbys, right? And not all of these influences can be done so them socially as discriminative. So for example, in this case, the passing, green seems to be totally legit and even unavoidable because applicants have the free will to choose their department and the application decisions are made by each department. In order to be able to distinguish between these discriminative and non-discriminative effects, our system let the user to partition the variables into admissible and inadmissables. Intuitively admissible variables are those such that the effect of sensitive attributes to outcome of an algorithm through these variables, them to be socially not discriminative. In this case, choice of department and qualification seems to be admissible. We implicitly label the other variables, in this case gender and hubbys inadmissable. So this partitioning is totally subjective. It could be different from one context to another context. And we can use it to somehow reflect either the law or social norms and values. There is no magic that can tell us which attribute is admissible and which attributes inadmissible. We cannot reduce fairness to a mathematical formula. So with this partitioning in place now, here comes the second attempt for defining fairness. Now we can say, this is a more relaxed definition, we can say, okay, an algorithm is fair if the sensitive attributes only affect the outcome of the algorithm through these admissible variables. This seems to be a good definition, but there is a problem with it. It requires the causal diagram to be fully specified. In practice, we typically have only partial knowledge. In order to handle this case, we have a definition based on counterfactuals and intervention, which is essentially testable against data subject to existing partial knowledge about the generative model. However the definition is too technical, I'm not going to discuss it today. Please see the paper if you're interested. In this talk, I'm going to keep working with that simple definition based on causal model. Okay, so now suppose you're collected historical data from this college, which is discriminative, right? And we want to build a model to predict admission results. Clearly, the machine learning model is going to pick up the existing discrimination and become discriminative. Now the question becomes, can we still use this bias historical data to train a model which is not causally biased? And the answer to this question is yes, there exists a very naive and baseline approach for doing that. Just drop all sensitive variables and all inadmissible variables from your data. In this case, just train your model based on choice of department and qualification. Then your machine learning model, whatever it is, is going to be a deterministic function of these admissible variables and your algorithm is going to be fair. So there are issues with this simple approach. First of all, it cannot be used in data release situation where data may have several use cases and want to include all attributes in your data, right? And the second issue is it can negatively impact utility because this inadmissible variable, they may still have predictive power which is not discriminative. This motivates our main solution. Our solution is to repair data, historical data, T2Optin, and other data set D prime, such that D prime reflect the word as we wish we had, right? So how does that word look like in our example? We wish that vision results were not made very agnostic to applicants' gender and applicants' hobby, right? We wish the data were generated by this generative model. And since we cannot change the word, or maybe we can change the word only through changing data, let's change data and fool the machine learning algorithms as if data were collected from a fair word, right? If you are now familiar with graphical models and in particular causal diagrams, you know that these diagrams, they essentially include a bunch of conditional independence constraints, such that any data that is generated according to this causal model would satisfy those constraints. And you can read this constraint of the causal diagram by applying a graphical criterion which is called the separation. In this case, the constraint that holds in this ideal word and we are interested in is that constraint, given applicants' qualification and choice of department, admission decision should be independent or is independent in that word of applicants' gender and applicants' hobby, right? It turns out that this constraint can be translated to something that we know very well in database community, multivalor dependencies. In this very case, it translates to the multivalor dependency, D and Q, multi-determine, A. So the repair problem becomes to add or remove tuples from your historical data, training data such that the obtained data becomes close to the original data according to some distance function and consistent with your multivalor dependency, right? Unfortunately, this problem turned out to be NP-hard even for one multivalor dependency. What we did, we proposed several efficient algorithms for solving this problem, including a reduction to max set and low-rank matrix factorization. Then we show that any classifier, trained using the repair to historical data D prime, is going to be fair, costly, fair, even on unseen test data under very mild assumptions. Okay, so now let's see if this idea would work in practice for this experiment. We use UCI adult income census data which contains attributes such as occupation, education, and marital status, and the prediction task is to predict whether individual receives high or low income. Now, suppose a bank is interested in using this data set to train a model to assist them to, I don't know, verify the reliability of their customers. Then the use of, if we use raw data to train a model, it is likely that the model is going to be discriminative against one because of the historical income gap between man and woman. Right? For the sake of illustration, we assume all variables are admissible except for marital status. Then we use our system to remove from data the causal influence of gender on income, both direct and indirect causal influence of gender to income via marital status. Then we use the raw data and the repaired data to train several classifiers. Then we measure bias and accuracy using fivefold cross validation. Note that we only repair the training data, bias and accuracy where measured on untouched test data to see if our approach is generalizable to unseen test data. So then the goal was to see if Capuchin can really remove discrimination without losing too much accuracy. This graph shows utility versus bias. Utility was measured by accuracy and bias essentially quantifies the effect of gender on outcome of an algorithm through these two discriminatory paths. We compare the bias and accuracy for raw data or repair methods and that naive idea of removing all that inadmissible variables. As you observe, at the cost of only two percent accuracy, our system almost removed bias. I should note that the residual bias is not statistically significant in most of the cases. These are just random signals. In most of the cases, it's actually in favor of minority groups. We also compared Capuchin with two baseline machine learning algorithms. Our preprocessing algorithm, namely Flatman and Kalman, they actually use different... The target is something different. The target is to enforce on training data what they call the statistical parity, which is very simple in this case, just to ensure that men and women, they have the same probability of high income. They enforce this constraint and as you observe, as a side effect, they were also reduced cost of bias, but not quite as successful as Capuchin. Both in terms of bias reduction and accuracy. We also compared our system with this method on number of associational metrics, a statistical parity, which is just a difference between positive outcome of algorithm between men and women, false positive balance, which is the difference between false positive rate for men and women and true negative balance, which is the difference between true negative between men and women. These numbers, the lower the bet. As you observe, Capuchin were able to, as a side effect, were able to also reduce associational metrics for fairness. In most cases, even it was quite more successful than the state of the art machine learning algorithm. Why this happens? Because it's actually quite expected because at the end of the day, even our approach reduces the correlation between sensitive attribute and outcome of the algorithm, but we do it in the right way. With this, I'm going to finish with some conclusions. We discussed the popular associational fairness definitions are misleading. Any of those 21 fairness definitions, I can show you one example in which they don't make sense. I believe that there's somewhere between harmless and meaningless. Harmful and meaningless, sorry. In this talk, we discussed how we can use causal model to define fairness. We discussed admissible and admissible partitioning as a way to be able to express different fairness constraints. And then we discussed how we can reduce the problem of building fair predictions, predictive models into a database with respect to integrity constraints. Thanks for listening.
algorithms are fair. So what do we mean by are unfair and biased. It's the underlying data that a huge part of the problem is the to training models, because this would be the most flexible approach in terms of the data underlying machine learning algorithm. So our notion of fairness, which improves the existing costly, fair classifiers to a database repair Roughly speaking, they define discrimination as a algorithm. However, no matter what, all of these statistical anomaly such as Simpson's paradox and fairness and capture it. We need for proving or algorithm through these admissible variables. inadmissible variables from your data. In this impact utility because this inadmissible method on number of associational metrics, a more successful than the state of the art machine outcome of the algorithm, but we do it in the associational fairness definitions are how we can use causal model to define fairness.