Understanding and Improving Search-Based Algorithms for Neural Sequence Generation

神经序列模型，如循环神经网络和变压器，通常用于序列数据的建模，并且是机器翻译和图像字幕等任务的最新方法。神经序列模型的序列生成通常使用波束搜索算法完成，该算法根据输入条件找到最可能的近似输出序列。近年来，神经序列模型已成功地应用于路径问题和分子合成等组合搜索问题，这些问题的解通常需要满足一些目标准则。值得注意的是，它们也是最近大多数神经程序合成方法的基础，神经程序合成是人工智能在许多应用中长期存在的巨大挑战。尽管神经序列模型很受欢迎，但由于其训练和局部归一化的性质，神经序列模型存在暴露偏差和标签偏差。使用波束搜索的生成容易受到一系列缺陷的影响，包括性能下降、缺乏多样性和偏向于较短的序列。最近，在面向目标的设置中，我展示了波束搜索在性能上有很大的可变性。提出的研究计划旨在通过对神经序列模型中基于搜索的生成进行深入的经验理解，并设计新颖的基于搜索的方法来解决上述偏差和缺陷，从而显著提高神经序列生成的性能。该计划围绕三个技术研究主题组织，并以一个中心应用领域为基础：主题1 -面向目标的神经序列生成的高级搜索算法。我们将更深入地了解面向目标的序列生成中的经验挑战，并设计波束搜索扩展，以及基于搜索的新方法，以应对这些挑战。主题2 -基于搜索的序列生成方法与学习序列级评分模型。我们将开发使用已学习的序列级评分模型（如基于能量的模型）的序列生成方法，以减轻暴露和标签偏见的影响。主题3 -理解和改进神经序列生成的强化学习。我们将开发基于强化学习的训练方案和基于搜索的序列生成之间相互作用的经验模型。基于这些模型，我们将设计策略，在高度约束的问题中结合基于强化学习的训练和基于搜索的生成。应用领域——神经程序合成。神经程序合成包括用通用或特定领域的计算机语言生成指令（程序）序列，是软件工程中的圣杯。它的不同实例涵盖了软件工程、自然语言处理和计算机视觉等领域的广泛具体应用，并将作为工业协作的基础。

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.