Top

Published in:

2021 | OriginalPaper | Chapter

Reduced Products of Abstract Domains for Fairness Certification of Neural Networks

Authors : Denis Mazzucato, Caterina Urban

Published in: Static Analysis

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We present Libra, an open-source abstract interpretation-based static analyzer for certifying fairness of ReLU neural network classifiers for tabular data. Libra combines a sound forward pre-analysis with an exact backward analysis that leverages the polyhedra abstract domain to provide definite fairness guarantees when possible, and to otherwise quantify and describe the biased input space regions. The analysis is configurable in terms of scalability and precision. We equipped Libra with new abstract domains to use in the pre-analysis, including a generic reduced product domain construction, as well as search heuristics to find the best analysis configuration. We additionally set up the backward analysis to allow further parallelization. Our experimental evaluation demonstrates the effectiveness of the approach on neural networks trained on a popular dataset in the fairness literature.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Selectively-Amortized Resource Bounding

next chapter A Multilanguage Static Analysis of Python Programs with Native C Extensions

https://github.com/caterinaurban/Libra.git.

For simplicity, we ignore ties as they can always be broken arbitrarily.

This is solely for technical reasons as the serialization of abstract domain elements is not available for the polyhedra domain implementation that Libra relies on. We plan to address this shortcoming as part of our future work.

https://archive.ics.uci.edu/ml/datasets/adult.

Barvinok, A.I.: A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed. Math. Oper. Res. 19(4), 769–779 (1994). https://doi.org/10.1287/moor.19.4.769MathSciNetCrossRefMATH

Breiman, L.: Random forests. Mach. Learn. 45(1), 5–32 (2001). https://doi.org/10.1023/A:1010933404324CrossRefMATH

Buolamwini, J., Gebru, T.: Gender shades: Intersectional accuracy disparities in commercial gender classification. In: FAT, vol. 81, pp. 77–91. PMLR (2018)

Cousot, P., Cousot, R.: Static determination of dynamic properties of programs. In: Second International Symposium on Programming, pp. 106–130 (1976)

Cousot, P., Cousot, R.: Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints. In: POPL, pp. 238–252 (1977). https://doi.org/10.1145/512950.512973

Cousot, P., Cousot, R.: Systematic design of program analysis frameworks. In: POPL, pp. 269–282 (1979). https://doi.org/10.1145/567752.567778

Cousot, P., Halbwachs, N.: Automatic discovery of linear restraints among variables of a program. In: POPL, pp. 84–96 (1978). https://doi.org/10.1145/512760.512770

Cristianini, N., Shawe-Taylor, J.: An Introduction to Support Vector Machines and Other Kernel-based Learning Methods. Cambridge University Press, Cambridge (2000). https://doi.org/10.1017/CBO9780511801389

Dwork, C., Hardt, M., Pitassi, T., Reingold, O., Zemel, R.S.: Fairness through awareness. In: ITCS, pp. 214–226. ACM (2012)

10.

European commission: proposal for a regulation laying down harmonised rules on artificial intelligence (artificial intelligence act) (2021). https://digital-strategy.ec.europa.eu/en/library/proposal-regulation-laying-down-harmonised-rules-artificial-intelligence-artificial-intelligence

11.

Friedman, J.H.: Greedy function approximation: a gradient boosting machine. Ann. Stat. 29(5), 1189–1232 (2001). https://doi.org/10.1214/aos/1013203451MathSciNetCrossRefMATH

12.

Galhotra, S., Brun, Y., Meliou, A.: Fairness testing: testing software for discrimination. In: FSE, pp. 498–510 (2017). https://doi.org/10.1145/3106237.3106277

13.

Hickey, T.J., Ju, Q., van Emden, M.H.: Interval arithmetic: from principles to implementation. J. ACM 48(5), 1038–1068 (2001)MathSciNetCrossRef

14.

Jeannet, B., Miné, A.: APRON: a library of numerical abstract domains for static analysis. In: CAV, pp. 661–667 (2009). https://doi.org/10.1007/978-3-642-02658-4_52

15.

Katz, G., Barrett, C.W., Dill, D.L., Julian, K., Kochenderfer, M.J.: Reluplex: an efficient SMT solver for verifying deep neural networks. In: CAV, pp. 97–117 (2017). https://doi.org/10.1007/978-3-319-63387-9_5

16.

Kay, M., Matuszek, C., Munson, S.A.: Unequal representation and gender stereotypes in image search results for occupations. In: CHI, pp. 3819–3828. ACM (2015)

17.

Larson, J., Mattu, S., Kirchner, L., Angwin, J.: How we analyzed the COMPAS recidivism algorithm (2016). https://www.propublica.org/article/how-we-analyzed-the-compas-recidivism-algorithm

18.

Li, J., Liu, J., Yang, P., Chen, L., Huang, X., Zhang, L.: Analyzing deep neural networks with symbolic propagation: towards higher precision and faster verification. In: SAS, pp. 296–319 (2019). https://doi.org/10.1007/978-3-030-32304-2_15

19.

Manisha, P., Gujar, S.: FNNC: achieving fairness through neural networks. In: IJCAI, pp. 2277–2283 (2020)

20.

Miné, A.: Symbolic methods to enhance the precision of numerical abstract domains. In: VMCAI, pp. 348–363 (2006). https://doi.org/10.1007/11609773_23

21.

Nair, V., Hinton, G.E.: Rectified linear units improve restricted boltzmann machines. In: ICML, pp. 807–814 (2010)

22.

Nielson, F., Nielson, H.R., Hankin, C.: Algorithms. In: Principles of Program Analysis, pp. 365–392. Springer, Heidelberg (1999). https://doi.org/10.1007/978-3-662-03811-6_6CrossRefMATH

23.

Obermeyer, Z., Powers, B., Vogeli, C., Mullainathan, S.: Dissecting racial bias in an algorithm used to manage the health of populations. Science 366, 447–453 (2019)CrossRef

24.

Singh, G., Gehr, T., Püschel, M., Vechev, M.T.: An abstract domain for certifying neural networks. Proc. ACM Prog. Lang. 3(POPL), 41:1–41:30 (2019). https://doi.org/10.1145/3290354

25.

Urban, C., Christakis, M., Wüstholz, V., Zhang, F.: Perfectly parallel fairness certification of neural networks. Proc. ACM Prog. Lang. 4(OOPSLA), 185:1–185:30 (2020). https://doi.org/10.1145/3428253

26.

Wang, S., Pei, K., Whitehouse, J., Yang, J., Jana, S.: Efficient formal safety analysis of neural networks. In: NeurIPS 2018, pp. 6369–6379 (2018)

27.

Wang, S., Pei, K., Whitehouse, J., Yang, J., Jana, S.: Formal security analysis of neural networks using symbolic intervals. In: Security, pp. 1599–1614. USENIX (2018)

28.

Yurochkin, M., Bower, A., Sun, Y.: Training individually fair ml models with sensitive subspace robustness. In: ICLR (2020)

Title: Reduced Products of Abstract Domains for Fairness Certification of Neural Networks
Authors: Denis Mazzucato
Caterina Urban
Publisher: Springer International Publishing
Book: Static Analysis
Print ISBN: 978-3-030-88805-3

Electronic ISBN: 978-3-030-88806-0

Copyright Year: 2021
DOI: https://doi.org/10.1007/978-3-030-88806-0_15

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"