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

机器学习和决策论人工智能规划中的一个关键挑战是现有方法无法有效和准确地推理分段连续函数。 这些功能出现在不同的任务中，例如偏好学习和交通信号的实时优化。 例如，在后一个应用领域，最优规划者必须推理当信号改变时发生的交通流的分段连续突发。 拟议的研究计划直接攻击这一挑战，通过进一步发展的连续决策图及其应用程序的问题，从偏好学习和启发关键的在线商务，以优化交通信号控制的高度拥挤的城市环境的关键。 连续决策图，如扩展代数决策图（XADD），是作者发明的，以解决在复杂表示和执行有效的封闭形式计算与分段连续函数的不足。 XADD已经实现了分段图形模型和（部分观察）马尔可夫决策过程（PO）（MDP）中学习，推理和决策问题的一些第一个精确解决方案。 然而，XADD的使用目前仅限于（a）相对较小的问题和（B）高度受限的分段连续函数类。 该提案显着提高了XADD的表达能力和可扩展性，用于精确和有界近似机器学习和决策理论AI规划，具有分段连续函数沿着以下技术研究重点： 重点1 --XADD的紧凑、表达性表示。我们将开发新的表达类的XADD和有界近似方案，以支持改进的易处理性和可扩展性，在现有的XADD。 Thrust 2 --可扩展的，表达性学习和XADD推理。我们将利用XADD开发新型消息传递和马尔可夫链蒙特卡罗（MCMC）学习和推理算法，以克服现有的可追踪性和表达性缺陷。 第三步：使用XADD增强决策理论AI规划。我们将利用扩展的XADD开发新的动态规划解决方案和紧凑的混合整数线性规划（MILP）编译的分段连续（PO）MDPs产生的模型表现力和解决方案的可处理性大幅改善。 工业合作将成为研究的动力和试验平台。具体而言，该研究将基于（i）通过与Kobo，Inc.的持续合作进行个性化在线电子书搜索。以及（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.