Abstract
A main focus of machine learning research has been improving the generalization accuracy and efficiency of prediction models. However, what emerges as missing in many applications is actionability, i.e., the ability to turn prediction results into actions. Existing effort in deriving such actionable knowledge is few and limited to simple action models while in many real applications those models are often more complex and harder to extract an optimal solution.
In this paper, we propose a novel approach that achieves actionability by combining learning with planning, two core areas of AI. In particular, we propose a framework to extract actionable knowledge from random forest, one of the most widely used and best off-the-shelf classifiers. We formulate the actionability problem to a sub-optimal action planning (SOAP) problem, which is to find a plan to alter certain features of a given input so that the random forest would yield a desirable output, while minimizing the total costs of actions. Technically, the SOAP problem is formulated in the SAS+ planning formalism, and solved using a Max-SAT based approach. Our experimental results demonstrate the effectiveness and efficiency of the proposed approach on a personal credit dataset and other benchmarks. Our work represents a new application of automated planning on an emerging and challenging machine learning paradigm.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Mitchell T M. Machine learning and data mining. Communications of the ACM, 1999, 42(11): 30–36
Bailey T C, Chen Y X,Mao Y, Lu C Y, Hackmann G,Micek S T, Heard K M, Faulkner K M, Kollef M H. A trial of a real-time alert for clinical deterioration in patients hospitalized on general medical wards. Journal of Hospital Medicine, 2013, 8: 236–242
Johnson R A, Gong R, Greatorex-Voith S, Anand A, Fritzler A. A data-driven framework for identifying high school students at risk of not graduating on time. Bloomberg Data for Good Exchange, 2015
Liu B, Hsu W. Post-analysis of learned rules. In: Proceedings of the AAAI Conference on Artificial Intelligence. 1996, 828–834
Liu B, HsuW, Ma YM. Pruning and summarizing the discovered associations. In: Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 1999, 125–134
Cao L B, Zhang C Q. Domain-driven, actionable knowledge discovery. IEEE Intelligent Systems, 2007, 22(4): 78–88
Cao L B, Zhao Y C, Zhang H F, Luo D, Zhang C Q, Park E K. Flexible frameworks for actionable knowledge discovery. IEEE Transactions on Knowledge and Data Engineering, 2010, 22(9): 1299–1312
DeSarbo W S, Ramaswamy V. Crisp: customer response based iterative segmentation procedures for response modeling in direct marketing. Journal of Direct Marketing, 1994, 8(3): 7–20
Levin N, Zahavi J. Segmentation analysis with managerial judgment. Journal of Direct Marketing, 1996, 10(3): 28–47
Moro S, Cortez P, Rita P. A data-driven approach to predict the success of bank telemarketing. Decision Support Systems, 2014, 62: 22–31
Hilderman R J, Hamilton H J. Applying objective interestingness measures in data mining systems. In: Proceedings of European Conference of Principles of Data Mining and Knowledge Discovery. 2000, 432–439
Cao L B, Luo D, Zhang C Q. Knowledge actionability: satisfying technical and business interestingness. International Journal of Business Intelligence and Data Mining, 2007, 2(4): 496–514
Cortez P, Embrechts M J. Using sensitivity analysis and visualization techniques to open black box data mining models. Information Sciences, 2013, 225: 1–17
Szegedy C, Zaremba W, Sutskever I, Bruna J, Erhan D, Goodfellow I, Fergus R. Intriguing properties of neural networks. In: Proceedings of the International Conference on Learning Representations. 2014
Yang Q, Yin J, Ling C, Chen T. Postprocessing decision trees to extract actionable knowledge. In: Proceedings of the 3rd IEEE International Conference on Data Mining. 2003, 685–688
Yang Q, Yin J, Ling C, Pan R. Extracting actionable knowledge from decision trees. IEEE Transactions on Knowledge and Data Engineering, 2007, 19(1): 43–56
Cui Z C, Chen W L, He Y J, Chen Y X. Optimal action extraction for random forests and boosted trees. In: Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2015, 179–188
Friedman J, Hastie T, Tibshirani R. The Elements of Statistical Learning, Vol 1. New York: Springer-Verlag, 2001
Shotton J, Sharp T, Kipman A, Fitzgibbon A, Finocchio M, Blake A, Cook M, Moore R. Real-time human pose recognition in parts from single depth images. Communications of the ACM, 2013, 56(1): 116–124
Viola P, Jones M J. Robust real-time face detection. International Journal of Computer Vision, 2004, 57(2): 137–154
Mohan A, Chen Z, Weinberger K. Web-search ranking with initialized gradient boosted regression trees. Journal of Machine Learning Research, 2011, 14: 77–89
Lu Q, Cui Z C, Chen Y X, Chen X P. Extracting optimal actionable plans from additive tree models. Frontiers of Computer Science, 2017, 11(1): 160–173
Freund Y, Schapire R E. A decision-theoretic generalization of online learning and an application to boosting. Journal of Computer and System Sciences, 1997, 55: 119–139
Friedman J H. Greedy function approximation: a gradient boosting machine. The Annals of Statistics, 2001, 29: 1189–1232
Breiman L. Random forests. Machine Learning, 2001, 45(1): 5–32
Fox M, Long D. PDDL2.1: An extension to PDDL for expressing temporal planning domains. Journal of Artificial Intelligence Research, 2003, 20: 61–124
Bäckström C, Nebel B. Complexity results for SAS+ planning. Computational Intelligence, 1995, 11(4): 625–655
Jonsson P, Bäckström C. State-variable planning under structural restrictions: algorithms and complexity. Artificial Intelligence, 1998, 100(1–2): 125–176
Helmert M. The fast downward planning system. Journal of Artificial Intelligence Research, 2006, 26: 191–246
Kautz H A, Selman B. Planning as satisfiability. In: Proceedings of European Conference on Artificial Intelligence. 1992, 359–363
Blum A, Furst M L. Fast planning through planning graph analysis. Artificial Intelligence, 1997, 90(1–2): 281–300
Lu Q, Huang R Y, Chen Y X, Xu Y, Zhang W X, Chen G L. A SATbased approach to cost-sensitive temporally expressive planning. ACM Transactions on Intelligent Systems and Technology, 2014, 5(1): 18
Huang R Y, Chen Y X, Zhang W X. A novel transition based encoding scheme for planning as satisfiability. In: Proceedings of the AAAI Conference on Artificial Intelligence. 2010, 89–94
Huang R Y, Chen Y X, Zhang W X. SAS+ planning as satisfiability. Journal of Artificial Intelligence Research, 2012, 43: 293–328
Balyo T, Chrpa L, Kilani A. On different strategies for eliminating redundant actions from plans. In: Proceedings of the 7th Annual Symposium on Combinatorial Search. 2014, 10–18
Acknowledgments
This work was supported in part by the National Natural Science Foundation of China (Grant Nos. 61502412, 61379066, and 61402395), Natural Science Foundation of the Jiangsu Province (BK20150459, BK20151314, and BK20140492), Natural Science Foundation of the Jiangsu Higher Education Institutions (15KJB520036), United States NSF grants (IIS-0534699, IIS-0713109, CNS-1017701), Microsoft Research New Faculty Fellowship, and the Research Innovation Program for Graduate Student in Jiangsu Province (KYLX16_1390).
Author information
Authors and Affiliations
Corresponding authors
Additional information
Qiang Lv is currently an assistant professor in College of Information Engineering, Yangzhou University, China. He received the BE and PhD degrees from the School of Computer Science and Technology, University of Science and Technology of China, China in 2007 and 2012, respectively. His research interests include data mining, automated planning and scheduling. He has published more than ten papers in journals and conference proceedings, including ACM TIST, IEEE TSC, EAAI, FCS, AAAI’13, ICAPS’11, Cloud-Com’11, and IPC’11. He is a member of the ACM and the CCF.
Yixin Chen is a professor of computer science at the Washington University in St. Louis, USA. He received the PhD degree in computer science from the University of Illinois at Urbana-Champaign, USA in 2005. His research interests include nonlinear optimization, constrained search, planning and scheduling, data mining, and data warehousing. His work on planning has won First-Class Prizes in the International Planning Competitions (2004 and 2006), the Best Paper Award in AAAI (2010) and ICTAI (2005), and Best Paper nomination at KDD (2009). He has received an Early Career Principal Investigator Award from the Department of Energy (2006) and a Microsoft Research New Faculty Fellowship (2007). Dr. Chen is a senior member of IEEE. He serves as an associate editor of IEEE Transactions on Knowledge and Data Engineering, and ACM Transactions on Intelligent Systems and Technology.
Zhaorong Li is currently a graduate student in the College of Information Engineering, Yangzhou University (YZU), China. She received the Bachelor’s degree from the College of Guangling at YZU. Her research interests include data mining, machine learning and artificial intelligence. She has published two papers in Journal of Chinese Computer Systems and CCDM. She is a student member of the CCF.
Zhicheng Cui received his BE degree in computer science from University of Science and Technology of China, China in 2014. He is now a PhD candidate in the Department of Computer Science and Engineering, Washington University in St. Louis (WUSTL), USA, supervised by Prof. Yixin Chen. His research interests are data mining and machine learning, in the area of large scale time series analysis.
Ling Chen is currently a professor in the College of Information Engineering, Yangzhou University, China. His research interests include bioinformatics, data mining and computational intelligence. He has co-edited six books/proceedings, and published more than 300 research papers including over 120 journal papers. He has received many awards from government and agencies. He has organized several academic conferences and workshops and has also served as a program committee chair or member for several major international conferences. He is a member of IEEE CS society and ACM, and a senior member of the Chinese Computer Society.
Xing Zhang is an assistant professor of marketing at the School of Management, Fudan University, China. She received the PhD degree in marketing from Washington University in St. Louis, USA in 2013. Her research interests are in empirical modeling consumer behavior and firm competition using econometric methodologies. She has conducted various research projects in the domain of marketing and economics. Her research about consumer information search and firm pricing has been published in Management Science.
Haihua Shen is an associate professor with the School of Computer and Control Engineering, University of Chinese Academy of Sciences, China. She received the PhD degree in computer science and technology from Tsinghua University, China in 2002. Her research interests include computer architecture, artificial intelligence, VLSI design & verification and hardware security. She has published more than 30 technical papers, and holds 20 patents.
Electronic supplementary material
Rights and permissions
About this article
Cite this article
Lv, Q., Chen, Y., Li, Z. et al. Achieving data-driven actionability by combining learning and planning. Front. Comput. Sci. 12, 939–949 (2018). https://doi.org/10.1007/s11704-017-6315-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11704-017-6315-2