More Web Proxy on the site http://driver.im/

research-article

Open access

FlipTest: fairness testing via optimal transport

Authors:

Matt FredriksonAuthors Info & Claims

FAT* '20: Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency

Pages 111 - 121

https://doi.org/10.1145/3351095.3372845

Published: 27 January 2020 Publication History

Abstract

We present FlipTest, a black-box technique for uncovering discrimination in classifiers. FlipTest is motivated by the intuitive question: had an individual been of a different protected status, would the model have treated them differently? Rather than relying on causal information to answer this question, FlipTest leverages optimal transport to match individuals in different protected groups, creating similar pairs of in-distribution samples. We show how to use these instances to detect discrimination by constructing a flipset: the set of individuals whose classifier output changes post-translation, which corresponds to the set of people who may be harmed because of their group membership. To shed light on why the model treats a given subgroup differently, FlipTest produces a transparency report: a ranking of features that are most associated with the model's behavior on the flipset. Evaluating the approach on three case studies, we show that this provides a computationally inexpensive way to identify subgroups that may be harmed by model discrimination, including in cases where the model satisfies group fairness criteria.

Supplementary Material

PDF File (p111-black-supp.pdf)

Supplemental material.

Download
754.91 KB

References

[1]

Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: Large-scale machine learning on heterogeneous systems. https://www.tensorflow.org/, 2015.

[2]

Aniya Agarwal, Pranay Lohia, Seema Nagar, Kuntal Dey, and Diptikalyan Saha. Automated test generation to detect individual discrimination in AI models. arXiv preprint arXiv:1809.03260, 2018.

[3]

Jason Altschuler, Jonathan Weed, and Philippe Rigollet. Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration. In Advances in Neural Information Processing Systems, pages 1964--1974, 2017.

[4]

Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine bias: There's software used across the country to predict future criminals. and it's biased against blacks. ProPublica, 2016.

[5]

Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein GAN. arXiv preprint arXiv:1701.07875, 2017.

[6]

Solon Barocas and Andrew D Selbst. Big data's disparate impact. California Law Review, 104:671--732, 2016.

[7]

Rachel K. E. Bellamy, Kuntal Dey, Michael Hind, Samuel C. Hoffman, Stephanie Houde, Kalapriya Kannan, Pranay Lohia, Jacquelyn Martino, Sameep Mehta, Aleksandra Mojsilovic, Seema Nagar, Karthikeyan Natesan Ramamurthy, John T. Richards, Diptikalyan Saha, Prasanna Sattigeri, Moninder Singh, Kush R. Varshney, and Yunfeng Zhang. AI fairness 360: An extensible toolkit for detecting, understanding, and mitigating unwanted algorithmic bias. CoRR, abs/1810.01943, 2018. URL http://arxiv.org/abs/1810.01943.

[8]

François Chollet et al. Keras. https://keras.io, 2015.

[9]

Alexandra Chouldechova. Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. Big Data, 5(2):153--163, 2017.

[10]

City of Chicago. Strategic Subject List. https://data.cityofchicago.org/Public-Safety/Strategic-Subject-List/4aki-r3np, 2017.

[11]

Jeffrey Dastin. Amazon scraps secret AI recruiting tool that showed bias against women. Reuters, 2018.

[12]

Anupam Datta, Shayak Sen, and Yair Zick. Algorithmic transparency via quantitative input influence: Theory and experiments with learning systems. In IEEE Symposium on Security and Privacy, pages 598--617, 2016.

[13]

Anupam Datta, Matt Fredrikson, Gihyuk Ko, Piotr Mardziel, and Shayak Sen. Proxy discrimination in data-driven systems. arXiv preprint arXiv:1707.08120, 2017.

[14]

Eustasio del Barrio, Fabrice Gamboa, Paula Gordaliza, and Jean-Michel Loubes. Obtaining fairness using optimal transport theory. arXiv preprint arXiv:1806.03195, 2018.

[15]

Cynthia Dwork and Christina Ilvento. Fairness under composition. arXiv preprint arXiv:1806.06122, 2018.

[16]

Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Innovations in Theoretical Computer Science, pages 214--226, 2012.

Digital Library

[17]

Equivant. Practitioner's guide to COMPAS core. http://www.equivant.com/wp-content/uploads/Practitioners-Guide-to-COMPAS-Core-040419.pdf, 2019.

[18]

Michael Feldman, Sorelle A Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasubramanian. Certifying and removing disparate impact. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 259--268, 2015.

Digital Library

[19]

Sainyam Galhotra, Yuriy Brun, and Alexandra Meliou. Fairness testing: testing software for discrimination. In Foundations of Software Engineering, pages 498--510, 2017.

[20]

Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in Neural Information Processing Systems, pages 2672--2680, 2014.

Digital Library

[21]

Gurobi Optimization, LLC. Gurobi optimizer reference manual. https://www.gurobi.com/documentation/8.1/refman.pdf, 2019.

[22]

Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. In Advances in Neural Information Processing Systems, pages 3315--3323, 2016.

Digital Library

[23]

úrsula Hébert-Johnson, Michael Kim, Omer Reingold, and Guy Rothblum. Multicalibration: Calibration for the (computationally-identifiable) masses. In International Conference on Machine Learning, pages 1944--1953, 2018.

[24]

Matthew Joseph, Michael Kearns, Jamie H Morgenstern, and Aaron Roth. Fairness in learning: Classic and contextual bandits. In Advances in Neural Information Processing Systems, pages 325--333, 2016.

Digital Library

[25]

Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing fairness gerrymandering: Auditing and learning for subgroup fairness. In International Conference on Machine Learning, pages 2564--2572, 2018.

[26]

Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. An empirical study of rich subgroup fairness for machine learning. In Conference on Fairness, Accountability, and Transparency, pages 100--109, 2019.

Digital Library

[27]

Jon Kleinberg, Sendhil Mullainathan, and Manish Raghavan. Inherent trade-offs in the fair determination of risk scores. In Innovations in Theoretical Computer Science, pages 43:1--43:23, 2017.

[28]

H. W. Kuhn and Bryn Yaw. The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2:83--97, 1955.

[29]

Matt J Kusner, Joshua Loftus, Chris Russell, and Ricardo Silva. Counterfactual fairness. In Advances in Neural Information Processing Systems, pages 4066--4076, 2017.

[30]

Jacob Leygonie, Jennifer She, Amjad Almahairi, Sai Rajeswar, and Aaron Courville. Adversarial computation of optimal transport maps. arXiv preprint arXiv:1906.09691, 2019.

[31]

Zachary Lipton, Julian McAuley, and Alexandra Chouldechova. Does mitigating ML's impact disparity require treatment disparity? In Advances in Neural Information Processing Systems, pages 8125--8135, 2018.

[32]

Parliament of the United Kingdom. Equality Act 2010. https://www.legislation.gov.uk/ukpga/2010/15/contents, 2010.

[33]

Michaël Perrot, Nicolas Courty, Rémi Flamary, and Amaury Habrard. Mapping estimation for discrete optimal transport. In Advances in Neural Information Processing Systems, pages 4197--4205, 2016.

Digital Library

[34]

Gabriel Peyré and Marco Cuturi. Computational optimal transport. Foundations and Trends® in Machine Learning, 11(5--6):355--607, 2019.

[35]

Kent Quanrud. Approximating optimal transport with linear programs. arXiv preprint arXiv:1810.05957, 2018.

[36]

Vivien Seguy, Bharath Bhushan Damodaran, Rémi Flamary, Nicolas Courty, Antoine Rolet, and Mathieu Blondel. Large-scale optimal transport and mapping estimation. arXiv preprint arXiv:1711.02283, 2017.

[37]

Supreme Court of the United States. Griggs v. Duke Power Co. 401 U.S. 424, 1971.

[38]

Florian Tramèr, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, Jean-Pierre Hubaux, Mathias Humbert, Ari Juels, and Huang Lin. Fairtest: Discovering unwarranted associations in data-driven applications. In IEEE European Symposium on Security and Privacy, pages 401--416, 2017.

[39]

Berk Ustun, Alexander Spangher, and Yang Liu. Actionable recourse in linear classification. In Conference on Fairness, Accountability, and Transparency, pages 10--19, 2019.

Digital Library

[40]

Rhema Vaithianathan, Emily Putnam-Hornstein, Nan Jiang, Parma Nand, and Tim Maloney. Developing predictive models to support child maltreatment hotline screening decisions: Allegheny County methodology and implementation. https://www.alleghenycountyanalytics.us/wp-content/uploads/2018/02/DevelopingPredictiveRiskModels-package_011618.pdf, 2017.

[41]

Cédric Villani. Optimal transport: Old and new, volume 338. Springer Science & Business Media, 2008.

[42]

Sandra Wachter, Brent Mittelstadt, and Chris Russell. Counterfactual explanations without opening the black box: Automated decisions and the gdpr. Harvard Journal of Law & Technology, 31(2):841--887, 2018.

[43]

Linda F Wightman and Henry Ramsey. LSAC national longitudinal bar passage study. Law School Admission Council, 1998.

[44]

Blake Woodworth, Suriya Gunasekar, Mesrob I Ohannessian, and Nathan Srebro. Learning non-discriminatory predictors. In Conference on Learning Theory, pages 1920--1953, 2017.

[45]

Karren D. Yang and Caroline Uhler. Scalable unbalanced optimal transport using generative adversarial networks. arXiv preprint arXiv:1810.11447, 2018.

[46]

Samuel Yeom, Anupam Datta, and Matt Fredrikson. Hunting for discriminatory proxies in linear regression models. In Advances in Neural Information Processing Systems, pages 4568--4578, 2018.

[47]

Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rogriguez, and Krishna P Gummadi. Fairness constraints: Mechanisms for fair classification. In Artificial Intelligence and Statistics, pages 962--970, 2017.

[48]

Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. Learning fair representations. In International Conference on Machine Learning, pages 325--333, 2013.

Digital Library

[49]

Zhe Zhang and Daniel B Neill. Identifying significant predictive bias in classifiers. arXiv preprint arXiv:1611.08292, 2016.

Cited By

Giannopoulos GSacharidis DTheologitis NKavouras LEmiris I(2025)FALE: Fairness-Aware ALE Plots for Auditing Bias in SubgroupsMachine Learning and Principles and Practice of Knowledge Discovery in Databases10.1007/978-3-031-74627-7_37(448-455)Online publication date: 1-Jan-2025
https://doi.org/10.1007/978-3-031-74627-7_37
Franceschi LDonini MArchambeau CSeeger MSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Explaining probabilistic models with distributional valuesProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692623(13840-13863)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3692623
Manole TBalakrishnan SNiles-Weed JWasserman L(2024)Plugin estimation of smooth optimal transport mapsThe Annals of Statistics10.1214/24-AOS237952:3Online publication date: 1-Jun-2024
https://doi.org/10.1214/24-AOS2379
Show More Cited By

Index Terms

FlipTest: fairness testing via optimal transport
1. Computing methodologies
  1. Machine learning
2. Human-centered computing

Recommendations

Relay-volunteered multi-rate cooperative MAC protocol for IEEE 802.11 WLANs

In IEEE 802.11, the rate of a station (STA) is dynamically determined by link adaptation. Low-rate STAs tend to hog more channel time than high-rate STAs due to fair characteristics of carrier sense multiple access/collision avoidance, leading to ...
Airtime Fairness for IEEE 802.11 Multirate Networks

Under a multi rate network scenario, the IEEE 802.11 DCF MAC fails to provide air-time fairness for all competing stations since the protocol is designed for ensuring max-min throughput fairness and the maximum achievable throughput by any station gets ...
On the Power of Randomization in Fair Classification and Representation
FAccT '22: Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency

Fair classification and fair representation learning are two important problems in supervised and unsupervised fair machine learning, respectively. Fair classification asks for a classifier that maximizes accuracy on a given data distribution subject to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

FAT* '20: Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency

January 2020

895 pages

ISBN:9781450369367

DOI:10.1145/3351095

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

ACM: Association for Computing Machinery

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 January 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

FAT* '20

Sponsor:

ACM

FAT* '20: Conference on Fairness, Accountability, and Transparency

January 27 - 30, 2020

Barcelona, Spain

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

44
Total Citations
View Citations
2,454
Total Downloads

Downloads (Last 12 months)462
Downloads (Last 6 weeks)48

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Giannopoulos GSacharidis DTheologitis NKavouras LEmiris I(2025)FALE: Fairness-Aware ALE Plots for Auditing Bias in SubgroupsMachine Learning and Principles and Practice of Knowledge Discovery in Databases10.1007/978-3-031-74627-7_37(448-455)Online publication date: 1-Jan-2025
https://doi.org/10.1007/978-3-031-74627-7_37
Franceschi LDonini MArchambeau CSeeger MSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Explaining probabilistic models with distributional valuesProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692623(13840-13863)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3692623
Manole TBalakrishnan SNiles-Weed JWasserman L(2024)Plugin estimation of smooth optimal transport mapsThe Annals of Statistics10.1214/24-AOS237952:3Online publication date: 1-Jun-2024
https://doi.org/10.1214/24-AOS2379
del Barrio EGonzález-Sanz ALoubes J(2024)Central limit theorems for general transportation costsAnnales de l'Institut Henri Poincaré, Probabilités et Statistiques10.1214/22-AIHP135660:2Online publication date: 1-May-2024
https://doi.org/10.1214/22-AIHP1356
Cen SAlur R(2024)From Transparency to Accountability and Back: A Discussion of Access and Evidence in AI AuditingProceedings of the 4th ACM Conference on Equity and Access in Algorithms, Mechanisms, and Optimization10.1145/3689904.3694711(1-14)Online publication date: 29-Oct-2024
https://dl.acm.org/doi/10.1145/3689904.3694711
Pirhadi AMoslemi MCloninger AMilani MSalimi B(2024)OTClean: Data Cleaning for Conditional Independence Violations using Optimal TransportProceedings of the ACM on Management of Data10.1145/36549632:3(1-26)Online publication date: 30-May-2024
https://doi.org/10.1145/3654963
Chen ZZhang JHort MHarman MSarro F(2024)Fairness Testing: A Comprehensive Survey and Analysis of TrendsACM Transactions on Software Engineering and Methodology10.1145/365215533:5(1-59)Online publication date: 4-Jun-2024
https://dl.acm.org/doi/10.1145/3652155
Deck LSchoeffer JDe-Arteaga MKühl N(2024)A Critical Survey on Fairness Benefits of Explainable AIProceedings of the 2024 ACM Conference on Fairness, Accountability, and Transparency10.1145/3630106.3658990(1579-1595)Online publication date: 3-Jun-2024
https://dl.acm.org/doi/10.1145/3630106.3658990
Yu ZChakraborty JMenzies T(2024)FairBalance: How to Achieve Equalized Odds With Data Pre-ProcessingIEEE Transactions on Software Engineering10.1109/TSE.2024.343144550:9(2294-2312)Online publication date: Sep-2024
https://doi.org/10.1109/TSE.2024.3431445
Mamman HBasri SOluwagbemiga Balogun ARehman Gilal AAbubakar Imam AKumar GFernando Capretz L(2024)Beyond the Seeds: Fairness Testing via Counterfactual Analysis of Non-Seed InstancesIEEE Access10.1109/ACCESS.2024.350216412(172879-172891)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3502164
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents