AI前沿｜从理论上说明像核采样这样的截断式生成方法为什么有效
尽管像核采样这样的截断采样启发式生成方法在语言生成中普遍存在，但为何它们如此有效仍然未知。作者通过证明丢弃低于某个概率阈值的token（最常见的截断类型）的截断方法可以保证所有采样的token具有非零真实概率，为截断采样的有效性提供了理论解释。然而，阈值仍是一种粗略的启发式方法，并且也必然会丢弃一些具有非零真实概率的token。为追求更精确的采样策略，作者证明他们可以利用已知的模型误差源（softmax bottleneck，下称SMB：由于较小的隐藏层维度与较大的词表导致的模型表达性受限）来证明某些token具有非零真实概率，而不依赖于阈值。根据发现，他们开发了一种实验性截断策略，并且目前的试点实验证明了此类算法的前景。评估表明，在低熵（即接近贪婪）开放式文本生成任务的自动和人工评估指标下，他们的方法优于基于阈值的方法。理论研究结果和试点实验既深入说明了截断采样为何有效，又在更具表现力的采样算法方面取得了进展。
对于截断式采样生成方法，除了LM倾向于为应该具有0或接近0概率的token分配更多概率（类似于平滑）的直觉外，先前工作在确定为什么截断采样在自回归生成中如此重要的研究很有限。作者便针对为何这些方法非常有效给出一个精准的数学解释。首先先了解一下SMB，见下图中文字，A是一个vxn的矩阵其中每个位置都是词表中token i在给定不同长度的前缀后的真实对数概率，而公式1中的A’是模型输出的概率估计，其计算由对WH做logsoftmax得到，W是vxd的矩阵，H则是dxn的给定前缀后的隐层状态的矩阵。另外J是一个全一矩阵，公式1展示了A‘的计算过程。由公式可知A’的秩最多只有d+1，因为WH受限于维度d而公式1中的减数的秩由于行完全相等秩最大为1。而A这一真实概率的秩最多为v，如果A的秩远大于d，那么A’最多只能作为A的低秩估计，而根据低秩估计的EYK定理，真实对数概率和模型给出的估计之间的Frobenius范数最小为公式2中所示，其中小写的西格玛是A的奇异值。因此这意味着模型的估计总会有某种程度的误差。
那为何存在上述误差的情况下，语言模型看起来效果还是不错呢？作者认为截断式采样近似弥补了这部分问题。作者定义p作为给定文本后真实的下一词的分布，p^作为模型预测的分布，如果模型估计存在一个加法上界，即对于每个token i，p^i <= pi + τ，那么只对大于τ的概率采样（意味着pi>0），就说明每次生成词都在真实的分布p的支持下。这正是截断式采样做的事。但问题在于如何推导出这个概率高估overestimation的加法上界。
考虑求出max(A-A’)的范围，即log概率低估underestimation误差的最大值（不考虑overestimation A’-A是因为除非估计的概率为0才有可能让误差为0，否则在真实概率为0时，从log曲线中能看出高估误差为无穷大）。根据max(A-A’) <= maxA - minA’ <= -minA’（maxA最大为0），这就是说A’中的最小值的负数就是模型低估的上界，比如当预测分布为均匀分布时低估最多为-log(1/v)；另一方面，max(A-A’)的下界严格为正且远离0，与A的奇异值有关。至此，我们有了logP的低估的范围，因为概率分布的和为1，我们能根据下图公式5-9轻易得到定理1：如果logp^低估logp* <= δ，那么p^对p的高估最大只有1-exp(-δ)，再见推论1，这意味着存在一个τ大于等于1-exp(-δ)时，基于阈值的截断式采样会正确地抛弃所有不被真实分布p所支持的token。而推论2是截断式采样的另一种形式：对于具有最大对数概率低估误差δ的模型，如果模型输出pˆ并且不存在pi = 0的分布p，使得pj ≤ pˆj exp(δ)，其中j ∈ {1,2,…, v}，则p*i > 0，这能从公式4从轻易得出。
有了上述结论后，作者提出一种新的生成方式来缓解截断生成中的问题，即：如果模型为低质量token分配比高质量token更多的概率，则不存在丢弃低质量token而不丢弃高质量token的阈值。这种问题如果是由低秩softmax矩阵导致，作者提出的新方法就可以恢复高质量的token，而不必冒着采样低质量token的风险。效果如figure2所示。
通过利用W这一模型输出的低秩基，我们能推导出来哪些token误差是源于SMB，不论其相对概率是多少。抽象地看，新方法启发于，将隐层状态h变换到概率p^的函数将模型输出限制于可能概率分布的子集中，当真实分布p在该子集外时，我们期待模型输出的在子集中的p^能最小化与p之间的损失，该性质能用来识别真实分布的集合，如果该集合中没有分布使得给定token概率为0，那么该分布一定有一个非0概率。为易于理解模型的输出是如何被限制的，可以见figure2里的例子，能很清晰地理解映射的过程。该例子可以通过将组合函数softmax ◦ W所定义的线性映射泛化到隐藏维度到d且词表大小为v。首先，模型的softmax矩阵W是vxd的是矩阵，定义了一个d到v维到映射，而softmax函数也是一个映射，将值从v维映射到∆v，这个∆v是一个v-1维的含有有效概率分布的向量空间。也就是说组合函数softmax ◦ W是一个将值从d维映射到d-1维度的线性映射，而函数的“像”是∆v中一个最多d维的子空间。即模型输出空间限制于基于此表达所有概率分布的子集中。那如果真实分布p并不在可能的子空间中呢？由于LM被训练于最小化预测分布与真实分布间的交叉熵，因此训得好的模型输出的在softmax ◦ W像中的p^与真实概率p的交叉熵会极小，也就是说模型的h会是最小化交叉熵的。关键的洞察在于如果h没有最小化任何p使得pi=0，这就意味着p一定不为0，即token i一定是在真实分布中。更规整的说法见下图定理2，证明也见下，其中W_transposed p = W_transposed p^是后续要提出的Basis-aware Constraint(BA constraint)，而pj <= p^j exp(δ)是truncation constraint。
【theorem2，and proof】
混合定理2和推论2，自然产生了一个采样方法：只对被证明被p支持的token采样。作者将其称为basis-aware threshold采样（BAT），还好阈值限制和basis-aware的限制都是线性的，我们可以用现成的线性规划优化器总结判断某个token是否有效，具体而言，如果优化器判定没有任何可行的p使得公式3的条件满足，则p一定大于0。采样策略就是根据模型输出概率采样token后如果优化器找到了公式3的解，就拒绝，否则接受。一个例子见figure3，在这个同样是模型隐层维度为1，词表大小为3的例子中，W_transposed为[0.55 0.71 0.29]，假设此时δ=log1.9，模型输出h=[2.55]，模型预测的分布可以算出来p^ = softmax(Wh) = [0.33 0.50 0.17]_transposed（也就是figure3中的蓝点）。而图中的蓝线则是模型的所有可能输出。根据BA constraint和truncation constraint可以算出这两个限制各自的范围，橙色线就是BA constraint，橙色区域是truncation constraint的区域，可以看到这两个区域和pi = 0这三者的共同的交点只有figure3中的绿点，意味着只有p1可能为0，p2和p3的真实概率p*不可能为零，所以在采样时我们采样到token 1的时候应该丢弃。
下图是更多新算法的实际效果，可以看出来对词的选择更加细致入微了。