Understanding and Improving Search-Based Algorithms for Neural Sequence Generation

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

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.