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

机器学习和决策理论人工智能规划中的一个关键挑战是现有方法无法有效和准确地对分段连续函数进行推理。这样的功能出现在不同的任务中，例如偏好学习和交通信号的实时优化。例如，在后一个应用领域，最优规划者必须对信号变化时出现的分段连续交通流突发进行推理。该研究计划通过进一步发展连续决策图并将其应用于从对在线商务至关重要的偏好学习和启发到对高度拥堵的城市环境至关重要的优化交通信号控制等问题，直接解决这一挑战。*连续决策图(如扩展代数决策图(XADD))是作者发明的，用于解决用分段连续函数紧凑地表示和执行高效闭式计算的不足。XADDS已经获得了学习、推理和决策问题在分段图模型和(部分观察到的)马尔可夫决策过程(MDP)中的一些第一个精确解。然而，XADD的使用目前仅限于(A)相对较小的问题和(B)高度受限的分段连续函数类。*该建议沿着以下技术研究推进XADD的表达能力和可扩展性：*XADD的紧凑、表达表示法，用于精确和有界的近似机器学习以及具有分段连续函数的决策理论AI规划。我们将开发新的XADD表达类和有界近似方案，以支持比现有XADD更好的易管理性和可伸缩性。*推送2--使用XADD的可伸缩、表达学习和推理。我们将利用XADDS开发新的消息传递和马尔可夫链蒙特卡罗(MCMC)学习和推理算法，以克服现有的可处理性和表现力缺陷。*推送3--使用XADDS增强决策理论AI规划。我们将利用XADD的扩展来开发新的动态编程解决方案和分段连续(PO)MDP的紧凑混合整数线性规划(MILP)编译，从而在模型可表现性和解决方案可处理性方面产生实质性改进。*行业合作将作为研究的动力和试验台。具体地说，这项研究的基础将是：(I)通过与Kobo公司的持续合作，进行个性化的在线电子书搜索；(Ii)与多伦多大学智能运输系统中心和测试床合作，进行交通建模、预测和信号控制研究。**

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.**