L. Elisa Celis
ABSTRACT
Developing classification algorithms that are fair with respect to sensitive attributes of the data is an important problem due to the increased deployment of classification algorithms in societal contexts. Several recent works have focused on studying classification with respect to specific fairness metrics, modeled the corresponding fair classification problem as constrained optimization problems, and developed tailored algorithms to solve them. Despite this, there still remain important metrics for which there are no fair classifiers with theoretical guarantees; primarily because the resulting optimization problem is non-convex. The main contribution of this paper is a meta-algorithm for classification that can take as input a general class of fairness constraints with respect to multiple non-disjoint and multi-valued sensitive attributes, and which comes with provable guarantees. In particular, our algorithm can handle non-convex "linear fractional" constraints (which includes fairness constraints such as predictive parity) for which no prior algorithm was known. Key to our results is an algorithm for a family of classification problems with convex constraints along with a reduction from classification problems with linear fractional constraints to this family. Empirically, we observe that our algorithm is fast, can achieve near-perfect fairness with respect to various fairness metrics, and the loss in accuracy due to the imposed fairness constraints is often small.
- ACM. 2017. Statement on Algorithmic Transparency and Accountability. https:/www.acm.org/binaries/content/assets/public-policy/2017_usacm_statement_algorithms.pdf.Google Scholar
- An Act. 1964. Civil Rights Act. Title VII, Equal Employment Opportunities (1964).Google Scholar
- Alekh Agarwal, Alina Beygelzimer, Miroslav Dudik, John Langford, and Hanna M. Wallach. 2018. A Reductions Approach to Fair Classification. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018. 60--69.Google Scholar
- Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. 2016. https://gir.hub.com/propublica/compas-analysis.Google Scholar
- Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. 2016. Machine bias: There's software used across the country to predict future criminals. and it's biased against blacks. ProPublica, May (2016).Google Scholar
- Solon Barocas and Andrew D Selbst. 2016. Big data's disparate impact. California Law Review (2016).Google Scholar
- Richard Berk. 2009. The role of race in forecasts of violent crime. Race and social problems (2009).Google Scholar
- Stephen Boyd and Almir Mutapcic. 2008. Stochastic subgradient methods. Lecture Notes for EE364b, Stanford University (2008).Google Scholar
- Toon Calders and Sicco Verwer. 2010. Three naive Bayes approaches for discrimination-free classification. Data Min. Knowl. Discov. 21, 2 (2010), 277--292. Google ScholarDigital Library
- L Elisa Celis, Lingxiao Huang, and Nisheeth K Vishnoi. 2018. Multiwinner voting with fairness constraints. In Proceedings of the Twenty-seventh International Joint Conference on Artificial Intelligence and the Twenty-third European Conference on Artificial Intelligence, IJCAI-ECAI. Google ScholarDigital Library
- L. Elisa Celis, Vijay Keswani, Amit Deshpande, Tarun Kathuria, Damian Straszak, and Nisheeth K. Vishnoi. 2018. Fair and Diverse DPP-based Data Summarization. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018.Google Scholar
- L. Elisa Celis, Damian Straszak, and Nisheeth K. Vishnoi. 2018. Ranking with Fairness Constraints. In Proceedings of the fourty-fifth International Colloquium on Automata, Languages, and Programming ICALP.Google Scholar
- L. Elisa Celis and Nisheeth K Vishnoi. 2017. Fair Personalization. In Fairness, Accountability, and Transparency in Machine Learning.Google Scholar
- Alexandra Chouldechova. 2017. Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. Big data 5, 2 (2017), 153--163.Google Scholar
- Sam Corbett-Davies, Emma Pierson, Avi Feller, Sharad Goel, and Aziz Huq. 2017. Algorithmic Decision Making and the Cost of Fairness. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2017.797--806. Google ScholarDigital Library
- Amit Datta, Michael Carl Tschantz, and Anupam Datta. 2015. Automated Experiments on Ad Privacy Settings. Proceedings on Privacy Enhancing Technologies (2015).Google ScholarCross Ref
- Bill Dedman et al. 1988. The Color of Money. Atlanta Journal-Constitution (1988).Google Scholar
- Dua Dheeru and Efi Karra Taniskidou. 2017. UCI Machine Learning Repository. http://archive.ics.uci.edu/ml.Google Scholar
- Ilias Diakonikolas. 2016. Learning Structured Distributions. Handbook of Big Data 267 (2016).Google Scholar
- William Dieterich, Christina Mendoza, and Tim Brennan. 2016. COMPAS risk scales: Demonstrating accuracy equity and predictive parity. Northpoint Inc (2016).Google Scholar
- Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. 2012. Fairness through awareness. In Innovations in Theoretical Computer Science 2012. ACM, 214--226. Google ScholarDigital Library
- Cynthia Dwork, Nicole Immorlica, Adam Tauman Kalai, and Mark D. M. Leiserson. 2018. Decoupled Classifiers for Group-Fair and Efficient Machine Learning. In Fairness, Accountability, and Transparency in Machine Learning. 119--133.Google Scholar
- ENTHOUGHT. 2018. SciPy. https:/www.scipy.org/.Google Scholar
- Michael Feldman, Sorelle A Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasubramanian. 2015. Certifying and removing disparate impact. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2015. ACM, 259--268. Google ScholarDigital Library
- Benjamin Fish, Jeremy Kun, and Ádám D Lelkes. 2016. A confidence-based approach for balancing fairness and accuracy. In Proceedings of the 2016 SIAM International Conference on Data Mining. SIAM, 144--152.Google ScholarCross Ref
- Anthony W Flores, Kristin Bechtel, and Christopher T Lowenkamp. 2016. False Positives, False Negatives, and False Analyses: A Rejoinder to Machine Bias: There's Software Used across the Country to Predict Future Criminals. And It's Biased against Blacks. Fed. Probation 80 (2016), 38.Google Scholar
- Sorelle A Friedler, Carlos Scheidegger, and Suresh Venkatasubramanian. 2016. On the (Im) Possibility of Fairness. arXiv preprint arXiv:1609.07236 (2016).Google Scholar
- Sorelle A Friedler, Carlos Scheidegger, Suresh Venkatasubramanian, Sonam Choudhary, Evan P Hamilton, and Derek Roth. 2018. A Comparative Study of Fairness-Enhancing Interventions in Machine Learning. arXiv preprint arXiv: 1802.04422 (2018).Google Scholar
- Naman Goel, Mohammad Yaghini, and Boi Faltings. 2018. Non-Discriminatory Machine Learning through Convex Fairness Criteria. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, 2018.Google ScholarDigital Library
- Sharad Goel, Justin M Rao, Ravi Shroff, et al. 2016. Precinct or prejudice? Understanding racial disparities in New York City's stop-and-frisk policy. The Annals of Applied Statistics 10, 1 (2016), 365--394.Google ScholarCross Ref
- Gabriel Goh, Andrew Cotter, Maya R. Gupta, and Michael P. Friedlander. 2016. Satisfying Real-world Goals with Dataset Constraints. In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016. 2415--2423. Google ScholarDigital Library
- Nina Grgić-Hlača, Elissa M Redmiles, Krishna P Gummadi, and Adrian Weller. 2018. Human Perceptions of Fairness in Algorithmic Decision Making: A Case Study of Criminal Risk Prediction. In Proceedings of the 2018 World Wide Web Conference on World Wide Web, WWW 2018. 903--912. Google ScholarDigital Library
- Nina Grgić-Hlača, Muhammad Bilal Zafar, Krishna P Gummadi, and Adrian Weller. 2018. Beyond Distributive Fairness in Algorithmic Decision Making: Feature Selection for Procedurally Fair Learning. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, 2018.Google Scholar
- Moritz Hardt, Eric Price, and Nati Srebro. 2016. Equality of Opportunity in Supervised Learning. In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016. 3315--3323. Google ScholarDigital Library
- Mara Hvistendahl. 2016. Can "predictive policing" prevent crime before it happens. Science Magazine 28 (2016).Google Scholar
- Matthew Joseph, Michael Kearns, Jamie H Morgenstern, and Aaron Roth. 2016. Fairness in learning: Classic and contextual bandits. In Advances in Neural Information Processing Systems. 325--333. Google ScholarDigital Library
- Faisal Kamiran and Toon Calders. 2009. Classifying without discriminating. In Computer, Control and Communication, 2009. IC4 2009. 2nd International Conference on. IEEE, 1--6.Google Scholar
- Faisal Kamiran and Toon Calders. 2012. Data preprocessing techniques for classification without discrimination. Knowledge and Information Systems 33, 1 (2012), 1--33. Google ScholarDigital Library
- Toshihiro Kamishima, Shotaro Akaho, Hideki Asoh, and Jun Sakuma. 2012. Fairness-Aware Classifier with Prejudice Remover Regularizer. In In Proceedings of Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2012. 35--50.Google Scholar
- Michael Kearns, Aaron Roth, and Zhiwei Steven Wu. 2017. Meritocratic fairness for cross-population selection. In International Conference on Machine Learning. Google ScholarDigital Library
- Jon M. Kleinberg, Sendhil Mullainathan, and Manish Raghavan. 2017. Inherent Trade-Offs in the Fair Determination of Risk Scores. In 8th Innovations in Theoretical Computer Science Conference, ITCS, 2017. 43:1--43:23.Google Scholar
- Emmanouil Krasanakis, Eleftherios Spyromitros-Xioufis, Symeon Papadopoulos, and Yiannis Kompatsiaris. 2018. Adaptive Sensitive Reweighting to Mitigate Bias in Fairness-aware Classification. In Proceedings of the 2018 World Wide Web Conference on World Wide Web, WWW 2018. International World Wide Web Conferences Steering Committee. Google ScholarDigital Library
- Jeff Larson, Surya Mattu, Lauren Kirchner, and Julia Angwin. 2016. How we analyzed the COMPAS recidivism algorithm. ProPublica (5 2016) 9 (2016).Google Scholar
- Binh Thanh Luong, Salvatore Ruggieri, and Franco Turini. 2011. k-NN as an implementation of situation testing for discrimination discovery and prevention. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining 2011. ACM, 502--510. Google ScholarDigital Library
- Susan Magarey. 2004. The sex discrimination act 1984. Australian Feminist Law Journal (2004).Google Scholar
- Aditya Krishna Menon and Robert C. Williamson. 2018. The cost of fairness in binary classification. In Conference on Fairness, Accountability and Transparency, FAT 2018. 107--118.Google Scholar
- Claire Cain Miller. 2015. Can an algorithm hire better than a human. The New York Times 25 (2015).Google Scholar
- Ankur Moitra and Gregory Valiant. 2010. Settling the polynomial learnability of mixtures of gaussians. In Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on. IEEE, 93--102. Google ScholarDigital Library
- Harikrishna Narasimhan, Rohit Vaish, and Shivani Agarwal. 2014. On the Statistical Consistency of Plug-in Classifiers for Non-decomposable Performance Measures. In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014. 1493--1501. Google ScholarDigital Library
- Arvind Narayanan. 2018. Tutorial: 21 Fairness Definitions and Their Politics. https:/www.youtube.com/watch?v=jIXIuYdnyyk.Google Scholar
- Northpointe. 2012. Compas risk and need assessment systems. http://www.northpointeinc.com/files/downloads/FAQ_Document.pdf.Google Scholar
- United States. Executive Office of the President and John Podesta. 2014. Big data: Seizing opportunities, preserving values. White House, Executive Office of the President.Google Scholar
- Dino Pedreshi, Salvatore Ruggieri, and Franco Turini. 2008. Discrimination-aware data mining. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2008. ACM, 560--568. Google ScholarDigital Library
- Geoff Pleiss, Manish Raghavan, Felix Wu, Jon M. Kleinberg, and Kilian Q. Weinberger. 2017. On Fairness and Calibration. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017 5684--5693. Google ScholarDigital Library
- Novi Quadrianto and Viktoriia Sharmanska. 2017. Recycling Privileged Learning and Distribution Matching for Fairness. In Advances in Neural Information Processing Systems. 677--688. Google ScholarDigital Library
- WhiteHouse. 2016. Big data: A report on algorithmic systems, opportunity, and civil rights. Executive Office of the President.Google Scholar
- Blake E. Woodworth, Suriya Gunasekar, Mesrob I. Ohannessian, and Nathan Srebro. 2017. Learning Non-Discriminatory Predictors. In Proceedings of the 30th Conference on Learning Theory, COLT 2017. 1920--1953.Google Scholar
- Ke Yang and Julia Stoyanovich. 2017. Measuring Fairness in Ranked Outputs. In SSDBM. Google ScholarDigital Library
- Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez-Rodriguez, and Krishna P. Gummadi. 2017. Fairness Beyond Disparate Treatment & Disparate Impact: Learning Classification without Disparate Mistreatment. In Proceedings of the 26th International Conference on World Wide Web, WWW 2017 1171--1180. Google ScholarDigital Library
- Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez-Rodriguez, and Krishna P. Gummadi. 2017. Fairness Constraints: Mechanisms for Fair Classification. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017 962--970.Google Scholar
- Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez-Rodriguez, Krishna P. Gummadi, and Adrian Weller. 2017. From Parity to Preference-based Notions of Fairness in Classification. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017. 228--238. Google ScholarDigital Library
- Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. 2013. Learning fair representations. In Proceedings of the 30th International Conference on Machine Learning, ICML 2013. 325--333. Google ScholarDigital Library
- Indre Zliobaite. 2017. Measuring discrimination in algorithmic decision making. Data Min. Knowl. Discov. (2017). Google ScholarDigital Library
Index Terms
- Classification with Fairness Constraints: A Meta-Algorithm with Provable Guarantees
Recommendations
Towards Discrimination-Free Classification via Fairness-Aware Bagging
PCI '21: Proceedings of the 25th Pan-Hellenic Conference on InformaticsOne of the most common and difficult problems to tackle is Bias or Discrimination in Machine Learning, which affects many people in a plethora of ways (e.g. Discrimination in facial recognition, in judicial cases, etc). A satisfying number of methods ...
Model-based and actual independence for fairness-aware classification
The goal of fairness-aware classification is to categorize data while taking into account potential issues of fairness, discrimination, neutrality, and/or independence. For example, when applying data mining technologies to university admissions, ...
Improved classification with allocation method and multiple classifiers
We propose a new allocation method for building a classification ensemble.Allocation method uses multiple classifiers: the allocator and micro classifiers.Allocator separates the dataset and allocates them to one of micro classifiers.Allocator is based ...
Comments