MACHINE LEARNING TO SCALE UP COMBINATORIAL APPLICATIONS

F A Rezaur Rahman Chowdhury

Combinatorial optimization problems arise in many scientific and engineering domains including graph analytics, computational biology, natural language processing, and computer vision. Existing methods to solve these combinatorial problems can be classified into three categories: exact tractable algorithms by exploiting the structure of these problems; approximation algorithms; and heuristic methods. In many real-world applications, we repeatedly solve a particular type of combinatorial optimization problem on different problem instances. For example, processing different input queries over a graph database. However, these combinatorial optimization solvers don't exploit the availability of this large set of input problem instances to improve their effectiveness. In this thesis, we propose a machine learning based search framework to automatically scale up combinatorial optimization solvers using the training data generated from a distribution of input problem instances. This research is inspired by the ability of humans to improve the speed of their reasoning processes with experience. For example, as a child learns to read or play chess, the reasoning processes involved become more automatic and perform better per unit time. The key idea is to define an effective time-bounded search procedure to solve the underlying combinatorial optimization problem and learn search control knowledge to improve speed and/or accuracy using supervised training data. We instantiate this framework for three important real-world combinatorial problems. First, we improve the effectiveness of processing graph queries over a large-scale graph database. We study two qualitatively different approaches towards this goal. Second, we present a linear-time machine learning-based folding system for RNA secondary structure prediction. Third, we develop learning methods to improve the speed and accuracy of solving structured prediction tasks arising in natural language processing and computer vision (e.g., producing part-of-speech tag sequences for input sequence of words) using randomized greedy search procedures. *The work on RNA secondary structure prediction was done at Baidu Research (Sunnyvale, CA) under the mentorship of Vincent He Zhang and Dr. Liang Huang.

MACHINE LEARNING TO SCALE UP COMBINATORIAL APPLICATIONS

Files and links (1)

Abstract

Metrics

Details