Extracting optimal actionable plans from additive tree models

作     者：Qiang LU Zhicheng CUI Yixin CHEN Xiaoping CHEN 

作者机构：College of Information Engineering Yangzhou University Yangzhou 225127 China Department of Computer Science and Engineering Washington University in St. Louis St. Louis MO 63130 USA School of Computer Science and Technology University of Science and Technology of China Hefei 230026 China 

出 版 物：《Frontiers of Computer Science》 (中国计算机科学前沿（英文版）)

年 卷 期：2017年第11卷第1期

页      面：160-173页

核心收录：

学科分类：12[管理学] 081603[工学-地图制图学与地理信息工程] 081802[工学-地球探测与信息技术] 07[理学] 08[工学] 070503[理学-地图学与地理信息系统] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 0818[工学-地质资源与地质工程] 0705[理学-地理学] 0816[工学-测绘科学与技术] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：This work was supported in part by China Postdoctoral Science Foundation (2013M531527)  the Fundamental Research Funds for the Central Universities (0110000037)  the National Natural Science Foun- dation of China (Grant Nos. 61502412  61033009  and 61175057)  Natural Science Foundation of the Jiangsu Province (BK20150459)  Natural Science Foundation of the Jiangsu Higher Education Institutions (15KJB520036)  National Science Foundation  United States (IIS-0534699  IIS-0713109  CNS-1017701)  and a Microsoft Research New Faculty Fellowship 

主　　题：actionable knowledge extraction machine learning additive tree models state space search 

摘      要：Although amazing progress has been made in ma- chine learning to achieve high generalization accuracy and ef- ficiency, there is still very limited work on deriving meaning- ful decision-making actions from the resulting models. How- ever, in many applications such as advertisement, recommen- dation systems, social networks, customer relationship man- agement, and clinical prediction, the users need not only ac- curate prediction, but also suggestions on actions to achieve a desirable goal （e.g., high ads hit rates） or avert an unde- sirable predicted result （e.g., clinical deterioration）. Existing works for extracting such actionability are few and limited to simple models such as a decision tree. The dilemma is that those models with high accuracy are often more complex and harder to extract actionability from. In this paper, we propose an effective method to extract ac- tionable knowledge from additive tree models （ATMs）, one of the most widely used and best off-the-shelf classifiers. We rigorously formulate the optimal actionable planning （OAP） problem for a given ATM, which is to extract an action- able plan for a given input so that it can achieve a desirable output while maximizing the net profit. Based on a state space graph formulation, we first propose an optimal heuris- tic search method which intends to find an optimal solution. Then, we also present a sub-optimal heuristic search with an admissible and consistent heuristic function which can re- markably improve the efficiency of the algorithm. Our exper- imental results demonstrate the effectiveness and efficiency of the proposed algorithms on several real datasets in the application domain of personal credit and banking.