Continuous Decision Diagrams for Machine Learning and Decision-theoretic AI Planning

点击翻译按钮获取中文摘要

A key challenge in both Machine Learning and Decision-theoretic AI Planning is the inability of existing methods to efficiently and accurately reason about piecewise continuous functions. Such functions arise in diverse tasks such as preference learning and real-time optimization of traffic signals. For example, in the latter application area, optimal planners must reason about piecewise continuous bursts of traffic flow that occur when signals change. The proposed research program directly attacks this challenge through the further development of continuous decision diagrams and their application to problems ranging from preference learning and elicitation critical for online commerce to optimized traffic signal control critical for highly congested urban environments. Continuous decision diagrams such as the extended algebraic decision diagram (XADD) were invented by the author to address deficiencies in compactly representing and performing efficient closed-form computation with piecewise continuous functions. XADDs have achieved some of the first exact solutions to learning, inference and decision-making problems in piecewise graphical models and (partially observed) Markov decision processes (PO)(MDPs). However, XADD use is currently limited to (a) relatively small problems and (b) highly restricted classes of piecewise continuous functions. This proposal significantly advances the expressiveness and scalability of XADDs for both exact and bounded approximate Machine Learning and Decision-theoretic AI Planning with piecewise continuous functions along the following technical research thrusts: Thrust 1 -- Compact, Expressive Representations for XADDs. We will develop novel expressive classes of XADDs and bounded approximation schemes to support improved tractability and scalability over the existing XADD. Thrust 2 -- Scalable, Expressive Learning and Inference with XADDs. We will leverage XADDs to develop novel message-passing and Markov Chain Monte Carlo (MCMC) learning and inference algorithms to overcome existing tractability and expressiveness drawbacks. Thrust 3 -- Enhanced Decision-theoretic AI Planning with XADDs. We will leverage extensions of the XADD to develop novel dynamic programming solutions and compact mixed-integer linear programming (MILP) compilations of piecewise continuous (PO)MDPs yielding substantial improvements in both model expressivity and solution tractability. Industrial collaborations will serve as a motivator and testbed for the research. Specifically, the research will be grounded in (i) personalized online e-book search via an ongoing collaboration with Kobo, Inc. and (ii) in traffic modeling, prediction, and signal control studies in collaboration with the University of Toronto Intelligent Transportation Systems Centre and Testbed.