Grant: Discovery Grants Program - Individual
University of Toronto
$29,000.00
Understanding and Improving Search-Based Algorithms for Neural Sequence Generation
FY 2022-23
Summary
Neural sequence models, such as recurrent neural networks and transformers, are commonly used in the modeling of sequential data and are the state-of-the-art approach for tasks such as machine translation and image captioning. Sequence generation from neural sequence models is typically done using the beam search algorithm that finds the approximately most likely output sequences, conditioned on the input. Recently, neural sequence models have been successfully applied to combinatorial search problems such as routing problems and molecule synthesis, where solutions are often required to satisfy some goal criteria. Notably, they also underlie most of the recent approaches for neural program synthesis, a long-standing grand challenge in AI with many applications. Despite their popularity, neural sequence models suffer from exposure bias and label bias due to their training and locally-normalized nature. Generation using beam search is susceptible to a range of deficiencies including performance degradation, lack of diversity and bias towards shorter sequences. Recently, in the goal-oriented setting, I showed that beam search suffers from large variability in performance. The proposed research program intends to significantly improve the performance of neural sequence generation by developing a deep empirical understanding of search-based generation in neural sequence models and devising novel, search-based, approaches aimed at addressing the above biases and deficiencies. The program is organized around three technical research themes and grounded in one central application domain: Theme 1 -- Advanced Search Algorithms for Goal-Oriented Neural Sequence Generation. We will develop a deeper understanding of the empirical challenges in goal-oriented sequence generation and devise beam search extensions, as well as novel search-based approaches, that address these challenges. Theme 2 -- Search-based Approaches for Sequence Generation with Learned Sequence-Level Scoring Models. We will develop sequence generation approaches that use learned sequence-level scoring models, such as energy-based models, to mitigate the impact of exposure and label bias. Theme 3 -- Understanding and Improving Reinforcement Learning for Neural Sequence Generation. We will develop empirical models for the interaction between RL-based training schemes and search-based sequence generation. Based on these models, we will devise strategies for combining RL-based training with search-based generation in highly-constrained problems. Application Domain -- Neural Program Synthesis. Neural program synthesis consists of generating sequences of instructions (programs) in a general or domain-specific computer language and is a holy grail in software engineering. Its different instantiations encompass a wide range of concrete applications in areas such as software engineering, natural language processing, and computer vision and will serve as the base for industrial collaborations.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2022-04154
Name nom
Cohen, Eldan
Department département
Mechanical and Industrial Engineering - 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
2022
Competition year année de concours
2022
Award amount
29000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
801
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
Computer software
Area of application fr
Logiciel
Research subject code
2800
Research subject group en
Artificial intelligence
Research subject group fr
Intelligence artificielle
Research subject en
Artificial intelligence (computer vision, use2603)
Research subject fr
Intelligence artificielle (vision artificielle, utiliser 2603)
Installment
inst:1
Partie
1
Nb partie
5
Application title
Understanding and Improving Search-Based Algorithms for Neural Sequence Generation
Application summary
Neural sequence models, such as recurrent neural networks and transformers, are commonly used in the modeling of sequential data and are the state-of-the-art approach for tasks such as machine translation and image captioning. Sequence generation from neural sequence models is typically done using the beam search algorithm that finds the approximately most likely output sequences, conditioned on the input. Recently, neural sequence models have been successfully applied to combinatorial search problems such as routing problems and molecule synthesis, where solutions are often required to satisfy some goal criteria. Notably, they also underlie most of the recent approaches for neural program synthesis, a long-standing grand challenge in AI with many applications. Despite their popularity, neural sequence models suffer from exposure bias and label bias due to their training and locally-normalized nature. Generation using beam search is susceptible to a range of deficiencies including performance degradation, lack of diversity and bias towards shorter sequences. Recently, in the goal-oriented setting, I showed that beam search suffers from large variability in performance. The proposed research program intends to significantly improve the performance of neural sequence generation by developing a deep empirical understanding of search-based generation in neural sequence models and devising novel, search-based, approaches aimed at addressing the above biases and deficiencies. The program is organized around three technical research themes and grounded in one central application domain: Theme 1 -- Advanced Search Algorithms for Goal-Oriented Neural Sequence Generation. We will develop a deeper understanding of the empirical challenges in goal-oriented sequence generation and devise beam search extensions, as well as novel search-based approaches, that address these challenges. Theme 2 -- Search-based Approaches for Sequence Generation with Learned Sequence-Level Scoring Models. We will develop sequence generation approaches that use learned sequence-level scoring models, such as energy-based models, to mitigate the impact of exposure and label bias. Theme 3 -- Understanding and Improving Reinforcement Learning for Neural Sequence Generation. We will develop empirical models for the interaction between RL-based training schemes and search-based sequence generation. Based on these models, we will devise strategies for combining RL-based training with search-based generation in highly-constrained problems. Application Domain -- Neural Program Synthesis. Neural program synthesis consists of generating sequences of instructions (programs) in a general or domain-specific computer language and is a holy grail in software engineering. Its different instantiations encompass a wide range of concrete applications in areas such as software engineering, natural language processing, and computer vision and will serve as the base for industrial collaborations.