基于最小不满足核的随机森林局部解释性分析
作者:
作者简介:

马舒岑(1997-),女,硕士,主要研究领域为形式化方法,机器学习可解释性;
秦胜潮(1974-),男,博士,教授,主要研究领域为软件理论与形式化方法,软件工程,程序语言;
史建琦(1984-),男,博士,副研究员,博士生导师,主要研究领域为工业软件,可信人工智能,嵌入式控制系统;
侯哲(1988-),男,博士,讲师,博士生导师,主要研究领域为自动推理,形式化验证,机器学习,区块链;
黄滟鸿(1986-),女,博士,副研究员,主要研究领域为可信计算,形式化建模与验证,高可信嵌入式控制软件.

通讯作者:

史建琦,E-mail:jqshi@sei.ecnu.edu.cn;黄滟鸿,E-mail:yhhuang@sei.ecnu.edu.cn

中图分类号:

TP311

基金项目:

国家重点研发计划(2019YFB2102602)


Minimal-unsatisfiable-core-driven Local Explainability Analysis for Random Forest
Author:
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [53]
  • |
  • 相似文献
  • |
  • 引证文献
  • | |
  • 文章评论
    摘要:

    随着机器学习在安全关键领域的应用愈加广泛,对于机器学习可解释性的要求也愈加提高.可解释性旨在帮助人们理解模型内部的运作原理以及决策依据,增加模型的可信度.然而,对于随机森林等机器学习模型的可解释性相关研究尚处于起步阶段.鉴于形式化方法严谨规范的特性以及近年来在机器学习领域的广泛应用,提出一种基于形式化和逻辑推理方法的机器学习可解释性方法,用于解释随机森林的预测结果.即将随机森林模型的决策过程编码为一阶逻辑公式,并以最小不满足核为核心,提供了关于特征重要性的局部解释以及反事实样本生成方法.多个公开数据集的实验结果显示,所提出的特征重要性度量方法具有较高的质量,所提出的反事实样本生成算法优于现有的先进算法;此外,从用户友好的角度出发,可根据基于反事实样本分析结果生成用户报告,在实际应用中,能够为用户改善自身情况提供建议.

    Abstract:

    With the broader adoption of machine learning (ML) in security-critical fields, the requirements for the explainability of ML are also increasing. The explainability aims at helping people understand models’ internal working principles and decision basis, which adds their realibility. However, the research on understanding ML models, such as random forest (RF), is still in the infant stage. Considering the strict and standardized characteristics of formal methods and their wide application in the field of ML in recent years, this work leverages formal methods and logical reasoning to develop a machine learning interpretability method for explaining the prediction of RF. Specifically, the decision-making process of RF is encoded into first-order logic formula, and the proposed approach is centered around minimal unsatisfiable cores (MUC) and local interpretation of feature importance and counterfactual sample generation method are provided. Experimental results on several public datasets illustrate the high quality of the proposed feature importance measurement, and the counterfactual sample generation method outperforms the state-of-the-art method. Moreover, from the perspective of user friendliness, the user report can be generated according to the analysis results of counterfactual samples, which can provide suggestions for users to improve their own situation in real-life applications.

    参考文献
    [1] Tian Y, Pei K, Jana S, et al. DeepTest:Automated testing of deep-neural-network-driven autonomous cars. In:Proc. of the 40th Int'l Conf. on Software Engineering. 2018. 303-314.[doi:10.1145/3180155.3180220]
    [2] Chen M, Hao Y, Hwang K, et al. Disease prediction by machine learning over big data from healthcare communities. IEEE Access, 2017, 5:8869-8879.[doi:10.1109/ACCESS.2017.2694446]
    [3] Alexopoulos C, Lachana Z, Androutsopoulou A, et al. How machine learning is changing e-government. In:Proc. of the 12th Int'l Conf. on Theory and Practice of Electronic Governance. 2019. 354-363.[doi:10.1145/3326365.3326412]
    [4] Molnar C. Interpretable machine learning. 2020. https://christophm.github.io/interpretable-ml-book/index.html
    [5] Vilone G, Longo L. Explainable artificial intelligence:A systematic review. arXiv:2006.00093, 2020.
    [6] Arrieta AB, Díaz-Rodríguez N, Del Ser J, et al. Explainable artificial intelligence (XAI):Concepts, taxonomies, opportunities and challenges toward responsible AI. Information Fusion, 2020, 58:82-115.
    [7] Adadi A, Berrada M. Peeking inside the black-box:A survey on explainable artificial intelligence (XAI). IEEE Access, 2018, 6:52138-52160.[doi:10.1109/ACCESS.2018.2870052]
    [8] Ribeiro MT, Singh S, Guestrin C. Anchors:High-precision model-agnostic explanations. In:Proc. of the 32nd AAAI Conf. on Artificial Intelligence. 2018. 1527-1535.
    [9] Ribeiro MT, Singh S, Guestrin C. Why should I trust you?"Explaining the predictions of any classifier. In:Proc. of the ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining. 2016. 1135-1144.[doi:10.1145/2939672.2939778]
    [10] Breiman L. Random forests. Machine Learning, 2001, 45(1):5-32.
    [11] Schapire RE. A brief introduction to boosting. In:Proc. of the Int'l Joint Conf. on Artificial Intelligence. 1999. 1401-1406.[doi:10.1109/CICC.1996.510579]
    [12] Safavian S, Landgrebe D. A survey of decision tree classifier methodology. IEEE Trans. on Systems, Man, and Cybernetics, 1991, 21(3):660-674.[doi:10.1109/21.97458]
    [13] Yu G, Yuan J, Liu Z. Unsupervised random forest indexing for fast action search. In:Proc. of the CVPR 2011. IEEE, 2011. 865-872.[doi:10.1109/CVPR.2011.5995488]
    [14] Goodfellow IJ, Shlens J, Szegedy C. Explaining and harnessing adversarial examples. arXiv:1412.6572, 2014.
    [15] Moosavi-Dezfooli SM, Fawzi A, Frossard P. Deepfool:A simple and accurate method to fool deep neural networks. In:Proc. of the IEEE Conf. on Computer Vision and Pattern Recognition. 2016. 2574-2582.[doi:10.1109/CVPR.2016.282]
    [16] Papernot N, McDaniel P, Jha S, et al. The limitations of deep learning in adversarial settings. In:Proc. of the 2016 IEEE European Symp. on Security and Privacy (EuroS&P). IEEE, 2016. 372-387.[doi:10.1109/EuroSP.2016.36]
    [17] Zhang H, Zhou H, Miao N, et al. Generating fluent adversarial examples for natural languages. In:Proc. of the 57th Annual Meeting of the Association for Computational Linguistics. 2019. 5564-5569.
    [18] Bride H, Cai CH, Dong J, et al. Silas:A high-performance machine learning foundation for logical reasoning and verification. Expert Systems with Applications, 2021, 176(1):Article No.114806.[doi:10.1016/j.eswa.2021.114806]
    [19] Nie C, Shi J, Huang Y. VARF:Verifying and analyzing robustness of random forests. In:Proc. of the Int'l Conf. on Formal Engineering Methods. Cham:Springer, 2020. 163-178.
    [20] Einziger G, Goldstein M, Sa'ar Y, et al. Verifying robustness of gradient boosted models. In:Proc. of the AAAI Conf. on Artificial Intelligence. 2019. 2446-2453.
    [21] Ji SL, Li JF, Du TY, Li B. Survey on techniques, applications and security of machine learning interpretability. Jisuanji Yanjiu yu Fazhan/Computer Research and Development, 2019, 56(10):2071-2096(in Chinese with English abstract).[doi:10.7544/issn1000-1239.2019.20190540]
    [22] Štrumbelj E, Kononenko I. Explaining prediction models and individual predictions with feature contributions. Knowledge and Information Systems, 2014, 41(3):647-665.[doi:https://doi.org/10.1007/s10115-013-0679-x]
    [23] Henelius A, Puolamäki K, Boström H, Asker L, Papapetrou P. A peek into the black box:Exploring classifiers by randomization. Data Mining and Knowledge Discovery, 2014, 28(5):1503-1529.
    [24] Pan WW, Wang XY, Song ML, Chen C. Survey on generating adversarial examples. Ruan Jian Xue Bao/Journal of Software, 2020, 31(1):67-81(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5884.htm[doi:10.13328/j.cnki.jos.005884]
    [25] Ignatiev A, Narodytska N, Marques-Silva J. On relating explanations and adversarial examples. Advances in Neural Information Processing Systems, 2019, 32:15883-15893.
    [26] Poyiadzi R, Sokol K, Santos-Rodriguez R, et al. FACE:Feasible and actionable counterfactual explanations. In:Proc. of the AAAI/ACM Conf. on AI, Ethics, and Society. 2020. 344-350.
    [27] Wachter S, Mittelstadt B, Russell C. Counterfactual explanations without opening the black box:Automated decisions and the GDPR. arXiv:1711.00399, 2017.
    [28] Zhang P, Wang J, Sun J, et al. White-box fairness testing through adversarial sampling. In:Proc. of the 42nd ACM/IEEEInt'l Conf. on Software Engineering. 2020. 949-960.[doi:10.1145/3377811.3380331]
    [29] Tolomei G, Silvestri F, Haines A, et al. Interpretable predictions of tree-based ensembles via actionable feature tweaking. In:Proc. of the 23rd ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining. 2017. 465-474.[doi:10.1145/3097983. 3098039]
    [30] Li XJ, Wu GW, Yao L, Zhang WZ, Zhang B. Progress and future challenges of security attacks and defense mechanisms in machine learning. Ruan Jian Xue Bao/Journal of Software, 2021, 32(2):406-423(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/6147.htm[doi:10.13328/j.cnki.jos.006147]
    [31] Liu RX, Chen H, Guo RY, Zhao D, Liang WJ, Li CP. Survey on privacy attacks and defenses in machine learning. Ruan Jian Xue Bao/Journal of Software, 2020, 31(3):866-892(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5904.htm[doi:10.13328/j.cnki.jos.005904]
    [32] Liu WY, Shen CY, Wang XF, Jin B, Lu XJ, Wang XL, Zha HY, He JF. Survey on fairness in trustworthy machine learning. Ruan Jian Xue Bao/Journal of Software, 2021, 32(5):1404-1426(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/6214.htm[doi:10.13328/j.cnki.jos.006214]
    [33] Hua YY, Zhang DX, Ge SM. Research progress on interpretability of deep learning model. Journal of Cyber Security, 2020, 5(3):1-12(in Chinese with English abstract).[doi:10.19363/J.cnki.cn10-1380/tn.2020.05.01]
    [34] Ehlers R. Formal verification of piece-wise linear feed-forward neural networks. In:Proc. of the Int'l Symp. on Automated Technology for Verification and Analysis. Cham:Springer, 2017. 269-286.
    [35] Yang P, Li R, Li J, et al. Improving neural network verification through spurious region guided refinement. In:Tools and Algorithms for the Construction and Analysis of Systems. 2021. 389-408.[doi:10.1007/978-3-030-72016-2_21]
    [36] Xiang W, Tran HD, Johnson TT. Reachable set computation and safety verification for neural networks with relu activations. arXiv:1712.08163, 2017.
    [37] Tran HD, Lopez DM, Musau P, et al. Star-based reachability analysis of deep neural networks. In:Proc. of the Int'l Symp. on Formal Methods. Cham:Springer, 2019. 670-686.
    [38] Ghosh B, Basu D, Meel KS. Justicia:A stochastic SAT approach to formally verify fairness. In:Proc. of the AAAI Conf. on Artificial Intelligence. 2021, 35(9):7554-7563.
    [39] Shih A, Choi A, Darwiche A. A symbolic approach to explaining Bayesian network classifiers. arXiv:1805.03364, 2018.
    [40] Zhang G, Hou Z, Huang Y, et al. Extracting optimal explanations for ensemble trees via logical reasoning. arXiv:2103.02191, 2021.
    [41] Clarke EM, et al. eds. Handbook of Model Checking. Cham:Springer, 2018.
    [42] Marques-Silva J, Lynce I, Malik S. Conflict-driven Clause Learning SAT Solvers. Handbook of Satisfiability. IOS Press, 2021. 133-182.
    [43] Ignatiev A, Narodytska N, Asher N, et al. On relating'Why?'and'Why Not?'explanations. arXiv:2012.11067, 2020.
    [44] Sülflow A, Fey G, Bloem R, et al. Using unsatisfiable cores to debug multiple design errors. In:Proc. of the 18th ACM Great Lakes Symp. on VLSI. 2008. 77-82.[doi:10.1145/1366110.1366131]
    [45] Cheng M, Le T, Chen PY, et al. Query-efficient hard-label black-box attack:An optimization-based approach. arXiv:1807.04457, 2018.
    [46] Hooker S, Erhan D, Kindermans PJ, et al. A benchmark for interpretability methods in deep neural networks. arXiv:1806.10758, 2018.
    附中文参考文献:
    [21] 纪守领,李进锋,杜天宇,李博.机器学习模型可解释性方法、应用与安全研究综述.计算机研究与发展, 2019, 56(10):2071-2096.[doi:10.7544/issn1000-1239.2019.20190540]
    [24] 潘文雯,王新宇,宋明黎,陈纯.对抗样本生成技术综述.软件学报, 2020, 31(1):67-81. http://www.jos.org.cn/1000-9825/5884.htm[doi:10.13328/j.cnki.jos.005884]
    [30] 李欣姣,吴国伟,姚琳,张伟哲,张宾.机器学习安全攻击与防御机制研究进展和未来挑战.软件学报, 2021, 32(2):406-423. http://www.jos.org.cn/1000-9825/6147.htm[doi:10.13328/j.cnki.jos.006147]
    [31] 刘睿瑄,陈红,郭若杨,赵丹,梁文娟,李翠平.机器学习中的隐私攻击与防御.软件学报, 2020, 31(3):866-892. http://www.jos.org.cn/1000-9825/5904.htm[doi:10.13328/j.cnki.jos.005904]
    [32] 刘文炎,沈楚云,王祥丰,金博,卢兴见,王晓玲,查宏远,何积丰.可信机器学习的公平性综述.软件学报, 2021, 32(5):1404-1426. http://www.jos.org.cn/1000-9825/6214.htm[doi:10.13328/j.cnki.jos.006214]
    [33] 化盈盈,张岱墀,葛仕明.深度学习模型可解释性的研究进展.信息安全学报, 2020, 5(3):1-12.[doi:10.19363/J.cnki.cn10-1380/tn.2020.05.01]
    相似文献
    引证文献
引用本文

马舒岑,史建琦,黄滟鸿,秦胜潮,侯哲.基于最小不满足核的随机森林局部解释性分析.软件学报,2022,33(7):2447-2463

复制
相关视频

分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2021-09-05
  • 最后修改日期:2021-10-14
  • 在线发布日期: 2022-01-28
  • 出版日期: 2022-07-06
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号