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

机器学习和决策理论人工智能规划的一个关键挑战是现有方法无法有效和准确地推断分段连续函数。这些功能出现在各种任务中，如偏好学习和交通信号的实时优化。例如，在后一个应用领域，最优规划者必须对信号变化时出现的分段连续交通流进行推理。拟议的研究计划通过进一步发展连续决策图及其应用于从在线商务关键的偏好学习和启发到高度拥挤的城市环境关键的优化交通信号控制等问题，直接应对这一挑战。****连续决策图，如扩展代数决策图（XADD）是由作者发明的，以解决在用分段连续函数紧凑地表示和执行有效的封闭形式计算方面的缺陷。xadd已经在分段图形模型和（部分观察到的）马尔可夫决策过程（PO）（mdp）中实现了一些学习、推理和决策问题的首批精确解决方案。然而，XADD的使用目前仅限于(a)相对较小的问题和(b)分段连续函数的高度受限类。****该提案显著提高了xadd的表达性和可扩展性，用于精确和有界近似机器学习和决策理论AI规划，具有分段连续函数，沿着以下技术研究方向：****Thrust 1—xadd的紧凑，表达性表示。我们将开发新的XADD表达类和有界近似方案，以支持在现有XADD上改进的可跟踪性和可伸缩性。****Thrust 2—使用xadd进行可扩展、表达性学习和推理。我们将利用xadd开发新的消息传递和马尔可夫链蒙特卡罗（Markov Chain Monte Carlo， MCMC）学习和推理算法，以克服现有的可跟踪性和表达性缺点。****推力3—增强决策理论AI规划与xadd。我们将利用XADD的扩展来开发新的动态规划解决方案和分段连续（PO） mdp的紧凑混合整数线性规划（MILP）编译，从而在模型表达性和解决方案可追溯性方面得到实质性改进。****工业合作将成为这项研究的动力和试验台。具体而言，该研究将基于(1)通过与Kobo公司的持续合作进行个性化在线电子书搜索，以及(2)与多伦多大学智能交通系统中心和试验台合作进行交通建模、预测和信号控制研究

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