Grant: Discovery Grants Program - Individual
University of Toronto
$46,000.00
Continuous Decision Diagrams for Machine Learning and Decision-theoretic AI Planning
FY 2020-21
Summary
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.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2016-05705
Name nom
Sanner, Scott
Department département
Mechanical and Industrial Engineering
Organization id
31
Institution établissement
University of Toronto
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2020
Competition year année de concours
2016
Award amount
46000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
802
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
Research subject code
2805
Research subject group en
Artificial intelligence
Research subject group fr
Intelligence artificielle
Research subject en
Learning and inference theories
Research subject fr
Théories de l'apprentissage et l'inférence
Installment
inst:5-6
Partie
2
Nb partie
6
Application title
Continuous Decision Diagrams for Machine Learning and Decision-theoretic AI Planning
Keyword
NSERC
Application summary
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.