Title: Learning-based Search Algorithm Design

Date: Wednesday, July 19, 2023

Time: 11:00am - 12:00pm ET

Location: Click here to join the meeting

Binghong Chen

Machine Learning Ph.D. Student

School of Computational Science and Engineering
Georgia Institute of Technology

Committee

Dr. Chao Zhang (Advisor), School of Computational Science and Engineering, Georgia Tech

Dr. Le Song (Co-advisor), Department of Machine Learning, Mohamed bin Zayed University of Artificial Intelligence

Dr. Xiuwei Zhang, School of Computational Science and Engineering, Georgia Tech

Dr. Yunan Luo, School of Computational Science and Engineering, Georgia Tech

Dr. Victor Fung, School of Computational Science and Engineering, Georgia Tech

Abstract

Classical search algorithms, such as A* search, evolutionary search, and Monte Carlo tree search, play a central role in solving many combinatorial optimization problems, including robotic path planning, molecule optimization, and playing Go. Conventionally, domain experts design these algorithms analytically by hand. However, such an algorithm design process is not data-driven and cannot benefit from the ever-increasing volumes of data. In this dissertation, we introduce a series of learning-to-search methods for different types of search space. We show that both search efficiency and effectiveness can be improved by learning search algorithms from historical data. Specifically, we focus on addressing challenges in a number of continuous and discrete search spaces with applications in robotics and drug design.

• High-dimensional continuous space. To search for solutions in high-dimensional continuous space, we resort to sampling-based methods to avoid explicitly discretizing the space. We propose a neural path planner that learns from prior experience to solve new path-planning problems. Compared to classical methods, our learning-to-search approach achieves higher sample efficiency in high dimensions and can benefit from prior experience in similar environments.
• Discrete graph space. Finding graph structures with desired properties is a challenging problem. We present a learning-based evolutionary search algorithm to optimize molecules for desired properties. The proposed algorithm leverages a graph explainable model and the REINFORCE algorithm to generate better molecules on a multi-property molecule optimization benchmark.
• Discrete decomposable combinatorial space. We present a framework to search for solutions to recursively decomposable problems based on the AND-OR tree representation that efficiently describes the search space. For the retrosynthesis planning problem, we introduce a learning-based A*-like search algorithm that finds high-quality synthetic routes for target molecules efficiently. The proposed algorithm builds on top of the AND-OR search tree and provides theoretical guarantees similar to the A* algorithm.
• Continuous molecular conformational space. We present an approach to search for molecular conformers with low energy, based on an Equivariant Transformer Forcefield (ETF). This strategy begins with an initial set of conformers, which are subsequently refined through structural optimization with ETF. We demonstrate that our ETF-based optimization significantly improves the quality of the conformers generated by state-of-the-art methods, achieving a 45% reduction in the distance to the reference conformers.

Keywords: Learning to search, Data-driven algorithm design, Deep learning, Reinforcement learning, Meta-learning, Graph representation learning, Structured prediction, Robotics applications, AI for drug discovery, Chemistry applications.