Sub-Task Decomposition Enables Learning in Sequence to Sequence Tasks
Noam Wies, Yoav Levine、Amnon Shashua The Hebrew University of Jerusalem
Abstract
The field of Natural Language Processing (NLP) has experienced a dramatic leap in capabilities with the recent introduction of huge Language Models (LMs). Despite this success, natural language problems that involve several compounded steps are still practically unlearnable, even by the largest LMs. This complies with experimental failures for end-to-end learning of composite problems that were demonstrated in a variety of domains. An effective mitigation is to introduce intermediate supervision for solving sub-tasks of the compounded problem. Recently, several works have demonstrated high gains by taking a straightforward approach for incorporating intermediate supervision in compounded natural language problems: the sequence-to-sequence LM is fed with an augmented input, in which the decomposed tasks’ labels are simply concatenated to the original input (see figure 1). In this paper, we prove a positive learning result that motivates these recent efforts. We show that when concatenating intermediate supervision to the input and training a sequence-to-sequence model on this modified input, unlearnable composite problems can become learnable. We show that this is true for any famil
中文速览
大型语言模型（如GPT-3）在需要多步推理的复合任务上仍然表现糟糕，一个流行的经验做法是把中间步骤的答案（中间监督，intermediate supervision）拼接到输入序列里再训练，实验上效果显著，但始终缺乏理论解释。本文首次给出了正面的理论证明：对于一类可以被分解为多项式数量、且每个子任务只依赖常数个前序结果的复合问题，将中间监督拼接到输入后，原本无法被任何多项式时间算法学会的任务，可以被一个简单的序列到序列循环神经网络在多项式样本量和梯度更新步数内高效学习；进一步，作者证明任何属于P复杂度类的函数在有充分中间监督时均可高效学习，并以"比特子集奇偶校验"问题为例，展示了有无中间监督之间指数级的可学习性差距。这一结果填补了该领域纯负面理论结论（只证明端到端学习不可行）的空白，为当前大量依赖中间监督的NLP工作提供了首个严格的理论支撑。
原文 arXiv:2204.02892;中英对照 + 大白话阅读 https://aha.fim.ai/paper/2204.02892v4