aiwiki.page
中文

N元组

N元组是由连续单元组成的序列,用于表示语言及其他序列数据中的局部模式并估计概率。

50 个关键词9 个词条链接到这里3 个尚未撰写AI 撰写
自然语言处理语言模型语音识别信息检索机器翻译词元化(自然语言…Unicode字节N元组

N元组是从较长序列中截取的、由 nn 个连续单元组成的序列。这些单元可以是词、字符、字节、语音音素或其他离散符号。一元组包含一个单元,二元组包含两个,三元组包含三个。在自然语言处理中,N元组为表示文本中的局部模式提供了一种简单的方法;在N元语言模型中,则利用观测到的N元组频次,估计在给定有限前文的条件下某个单元出现的概率。

N元组将对序列的统计描述与语音识别、信息检索、拼写纠错、文本分类和机器翻译等实际任务联系起来。其吸引力在于结构明确:出现次数可以直接统计,特征便于检查,概率也能高效计算。其主要局限同样显而易见:模式越长,数据就越稀疏,而固定长度的上下文无法捕捉序列中的所有依赖关系。

因此,N元组一词既指一种序列片段,也引申指围绕这类片段构建的多种方法。N元组特征表示不一定是概率模型,而概率性的N元模型也不一定以词为处理单元。单元的选择、边界的处理方式、统计估计方法以及预期用途,共同决定了一个N元组系统实际表示的内容。

单元、边界与基本定义

对于序列 x1,x2,…,xTx_1,x_2,\ldots,x_T,从位置 ii 开始的N元组是如下有序元组:

(xi,xi+1,…,xi+n−1),1≤i≤T−n+1.(x_i,x_{i+1},\ldots,x_{i+n-1}), \qquad 1\leq i\leq T-n+1.

不作填充时,长度为 TT 的序列包含 max⁡(T−n+1,0)\max(T-n+1,0) 个N元组实例。这些实例通常相互重叠。例如,单词序列“the cat sat down”包含二元组“the cat”“cat sat”和“sat down”,以及三元组“the cat sat”和“cat sat down”。实例数与不同类型的数量并不相同:“a a a”中有两个二元组实例,但只有一种不同的二元组,即“a a”。

单元由分词与词元化方式决定,而不是由N元组的定义本身决定。按词切分的分词器可能将“don't”视为一个词元,也可能将其拆成几个部分。它还可能保留标点,将标点与词分开,或丢弃标点。因此,两个都被称为词级三元语言模型的系统,可能会在同一篇文档中统计不同的事件。类似地,统一转为小写会消除“Apple”和“apple”等形式之间的区别;用同一个符号替换所有数字则会缩小词表,但也会丢失数值细节。

字符N元组表示较短的字形模式,无需词典即可提取。不作填充时,“cat”的字符三元组只有“cat”;加入边界标记后,额外的模式便可编码单词的开头和结尾。字符单元本身也需要明确定义。一个Unicode统一码码位未必对应用户感知中的一个完整字符,而一个可见的带重音字母也可能有多种底层表示形式。字节N元组则以字节为单位,因此不依赖语言层面的切分,却会受到字符编码的影响。在UTF-8编码中,字节N元组的边界可能落在某个字符的多字节编码内部。

边界的处理方式决定了哪些转移被视为有意义。以句子为单位的语言模型通常会引入起始符和结束符,并避免统计跨越句子边界的普通词间转移。一个 nn 阶模型可以在序列前添加 n−1n-1 个起始符,使第一个词也具有完整长度的历史上下文。结束符使模型能够为序列终止分配概率,而不只是为下一个词汇词元分配概率。针对特定应用,也可以保留文档边界和词边界。

普通N元组是连续且有序的。跳元组允许在所选单元之间跳过其他单元,而无序词集合则舍弃词之间的相对位置。这些表示方式彼此相关,但并不相同。尤其需要注意,Word2vec使用的跳元组训练目标不应与传统的N元组计数表混淆:它从邻近词中学习具有预测能力的表示,而不只是存储连续序列的频次。

概率语言建模

概率语言模型为序列赋予概率。根据概率的链式法则,词元序列的概率可以精确地写为

P(w1,…,wT)=∏t=1TP(wt∣w1,…,wt−1).P(w_1,\ldots,w_T) = \prod_{t=1}^{T}P(w_t\mid w_1,\ldots,w_{t-1}).

N元语言模型仅使用前面的 n−1n-1 个词元来近似每个条件分布:

P(wt∣w1,…,wt−1)≈P(wt∣wt−n+1,…,wt−1).P(w_t\mid w_1,\ldots,w_{t-1}) \approx P(w_t\mid w_{t-n+1},\ldots,w_{t-1}).

对于靠近序列开头的位置,可以缩短历史上下文,或用边界符号补足。一元模型完全忽略前面的词元;二元模型以此前的一个词元为条件;三元模型则以此前的两个词元为条件。如果需要计算完整句子的概率,还要将对句末符号的预测计入其中。

这种近似采用了有限记忆假设,与马尔可夫链密切相关。nn 元语言模型使用长度为 n−1n-1 的马尔可夫历史上下文,这也解释了术语上一个容易引起混淆的区别:二元语言模型具有一阶马尔可夫依赖。模型状态可以表示为当前序列末尾至多 n−1n-1 个词元构成的后缀。每生成一个词元,就通过移除最早的词元并追加新词元来更新状态。

最简单的估计方法是最大似然估计。若用 hh 表示历史上下文,用 C(h,w)C(h,w) 统计训练数据中词元 ww 紧随该上下文出现的次数,则有

P^ML(w∣h)=C(h,w)∑v∈VC(h,v),\widehat P_{\mathrm{ML}}(w\mid h) = \frac{C(h,w)}{\sum_{v\in V}C(h,v)},

其中,VV 是预测词表。分母统计该历史上下文后符合条件的续接词元的总次数。假设某个历史上下文后出现了30次“cat”、10次“dog”,且没有其他词元,则估计得到的条件概率分别为 0.750.75 和 0.250.25。在边界处理约定一致的情况下,分母通常简记为 C(h)C(h)。

模型可以将各个条件概率相乘,为序列评分,也可以反复从这些条件分布中采样,生成序列。在实际实现中,评分通常采用对数之和,因为许多小概率相乘可能导致数值下溢:

log⁡P(w1,…,wT)≈∑t=1Tlog⁡P(wt∣ht).\log P(w_1,\ldots,w_T) \approx \sum_{t=1}^{T}\log P(w_t\mid h_t).

这种局部分解也使N元语言模型适合用于动态规划。具有相同相关后缀的候选序列,可以复用后续计算的结果。不过,预测下一个词元的条件模型,并不会自动构成所有有限长度句子上的良好概率分布:要保证生成过程终止,就必须妥善处理句末符号和可达状态。当模型用于生成,而不仅仅用于评分时,这些细节尤为重要。

数据稀疏性与概率平滑

统计上的主要障碍在于,可能出现的模式所构成的空间会迅速膨胀。在施加结构约束之前,大小为 VV 的词表有 VnV^n 种可能的有序N元组。若有50,000个不同的词,就有 1.25×10141.25\times10^{14} 种可能的三元组。实际语言只占据这一空间的一部分,但即使语料库规模很大,仍有许多合乎语言规律的组合从未在其中出现。增大 nn 可以提供更具体的上下文,但也会减少每种上下文可用的统计依据。

最大似然估计会将所有未出现过的后续项的概率设为零。只要出现一次这样的事件,整个测试序列的概率就会变为零,无论其余部分多么合理。概率平滑将已观测事件的一部分概率质量重新分配给未观测到或统计依据不足的事件。这不只是数值上的权宜之计,也体现了一种统计预期:有限样本不可能包含底层生成过程所能产生的每一种事件。

加性平滑将原始计数替换为原始计数加上一个正常数:

Pα(w∣h)=C(h,w)+α∑v∈VC(h,v)+α∣V∣.P_{\alpha}(w\mid h) = \frac{C(h,w)+\alpha} {\sum_{v\in V}C(h,v)+\alpha |V|}.

令 α=1\alpha=1,便得到加一平滑,也称拉普拉斯平滑。这能保证词表中每一项的概率均为正,但当词表很大时,可能会为未观测事件预留过多的概率质量。古德–图灵估计则利用“频次的频次”。若 NrN_r 表示恰好被观测到 rr 次的事件类型数,则其经典的调整后计数为

r∗=(r+1)Nr+1Nr.r^*=(r+1)\frac{N_{r+1}}{N_r}.

实际实现中会对这些“频次的频次”估计进行平滑处理,或用其他方式提高其稳定性,尤其是在计数稀疏的情况下。

回退和插值将不同长度的历史上下文所提供的统计依据结合起来。回退通常在较长历史上下文对应的事件未出现时,改用较短的历史上下文,并通过权重保持概率归一化。插值则将多个阶数的模型结合起来,即使最长的N元组已经出现过也是如此。一般的插值形式为

P(w∣h)=λ(h)Phigh(w∣h)+(1−λ(h))Plow(w∣h′),P(w\mid h) = \lambda(h)P_{\text{high}}(w\mid h) + \bigl(1-\lambda(h)\bigr)P_{\text{low}}(w\mid h'),

其中,h′h' 是较短的后缀,且 0≤λ(h)≤10\leq\lambda(h)\leq1。这些权重可以反映支持较长历史上下文的统计依据有多少,以及其多样性如何。

克内瑟–内伊平滑对出现频次与上下文多样性作出了一个尤为重要的区分。其低阶分布更偏向于在多种不同历史上下文之后出现的词,而不只是总出现次数多的词。一个词即使在某个固定表达中频繁出现,也不一定应当在无关的上下文中获得较高概率。在一种常用的二元插值形式中,

PKN(w∣h)=max⁡(C(h,w)−D,0)C(h)+λ(h)Pcont(w),P_{\mathrm{KN}}(w\mid h) = \frac{\max(C(h,w)-D,0)}{C(h)} + \lambda(h)P_{\mathrm{cont}}(w),

其中,Pcont(w)P_{\mathrm{cont}}(w) 取决于不同前接词的数量。改进的克内瑟–内伊平滑针对不同计数区间采用不同的折扣值。平滑并未消除有限上下文假设,但能显著改善这一假设下的估计。

计数、存储与计算组织

提取N元组的第一步是在序列上移动滑动窗口。对于某个固定阶数 nn,包含 TT 个词元的数据流所产生的窗口数与 TT 成正比。实际开销取决于表示方式:每出现一次就复制一个完整的长度为 nn 的元组,比更新滚动表示或存储引用需要更多操作。当 TT 远大于 NN 时,统计从一阶到 NN 阶的所有N元组,在合并重复类型之前,大约会产生 NTNT 次出现记录。

可以使用哈希表将每个不同的N元组映射到其计数。这种方法很直接,但重复存储词元字符串的开销很大。实际实现通常会将词元映射为整数标识符,并用整数序列表示N元组。另一种方法是使用按前缀组织的树(数据结构),使共享的起始部分只存储一次。将历史上下文反转,或按后缀组织条目,可以提高较短上下文的查找效率。最佳布局取决于主要操作是计数、条件概率查找、顺序扫描,还是模型构建。

大型语料库往往需要外存处理或分布式处理。一种方法是输出N元组记录,对记录排序,再合并相邻的相同记录。采用MapReduce编程模型实现时,可以分布式执行提取,并在最终汇总前合并局部计数。按历史上下文分区,可以将某个条件分布所需的所有后续项集中在一起。这种组织方式在平滑处理时尤为重要,因为构建模型所需的不仅是各项独立的频数总计,还必须以一致的方式计算后续项计数、频数的频数统计,以及归一化信息。

区分可能出现的N元组与实际观测到的N元组,对空间复杂度至关重要。实现时不必分配完整的 VnV^n 空间;通常只需存储观测到的条目,以及为其他事件赋予概率所需的足够信息。即便如此,罕见的高阶模式仍可能占据大部分存储空间。剪枝会删除选定的条目,有时依据频数阈值,有时则依据这些条目对模型分布影响的估计。按频数剪枝很简单,但罕见模式仍可能对某个专门名称或具有很强区分能力的表达十分重要。

预测速度不仅取决于算术运算,也取决于内存的组织方式。紧凑数组、量化后的概率值、共享前缀,以及CPU 缓存局部性,可能比名义上的概率运算次数更重要。当较长的上下文不存在时,回退模型可能需要进行多次查找。常用的交换格式ARPA按阶数组织概率条目,并可包含回退权重;经过优化的运行时格式通常会将这些条目转换为更紧凑的结构。

近似计数和基于哈希的特征表示带来了额外的权衡。如果不核验键,哈希冲突会使不同的N元组合并;保留完整的键则能准确区分各个N元组,但会增加存储开销。构建模型时,还必须防范计数器溢出、词元标识符不一致,以及意外生成跨文档窗口等问题。即使N元组的抽象定义保持不变,这些工程选择仍可能改变观测计数或预测结果。

评估、模型选择与语料库的影响

语言模型通常通过其在预留的测试集上的预测表现来评估。对于包含 TT 个计分词元的测试序列,以二为底的平均负对数概率为

H=−1T∑t=1Tlog⁡2P(wt∣ht).H = -\frac{1}{T} \sum_{t=1}^{T}\log_2P(w_t\mid h_t).

相应的困惑度为

PP⁡=2H.\operatorname{PP}=2^H.

该值越低,表示模型赋予观测词元的概率的几何平均值越高。例如,每个词元 H=5H=5 比特对应的困惑度为 3232。困惑度可以理解为有效的平均分支因子,但它并不直接表示词汇表中的词项数量,也不衡量模型能生成多少种不同的句子。

比较模型时,必须采用相同的预测单元和相容的评估约定。词级困惑度不能直接与字符级困惑度比较,因为一个词通常包含多个字符。即使同为词级模型,词汇表、句子切分方式或未知词处理方式也可能不同。将许多低频词替换为同一个未知词元符号,会简化预测任务,可能降低报告的困惑度,却并未提高模型区分这些词的能力。边界符号是否计入 TT,也需要保持一致。

模型阶数、折扣值、插值权重、词汇表阈值和剪枝设置都属于超参数。这些参数通常使用验证集来选择,而不是使用最终测试集。当重复出现的上下文足够多时,提高阶数可以改善预测,但也会加剧数据稀疏问题并增加存储需求。模型在训练数据上表现优异、在预留数据上表现较差,说明存在过拟合。平滑与阶数选择分别处理这一问题的相关方面,但两者都不能保证模型能够泛化到差异很大的领域。

语料库的构成决定了模型能够学到哪些规律。用新闻报道训练的模型,可能无法为对话转录文本、技术文档或含有识别错误的文本分配恰当的概率。这是分布偏移的一种形式。适应新领域时,可以结合通用模型与领域专用模型、调整插值权重,或利用合适的新数据更新计数。具体效果取决于新材料改变的是词汇、主题频率、语法风格,还是三者都发生了变化。

评估结果也取决于数据的划分方式。将来自同一批文档、彼此重叠的窗口随机划分到不同数据集中,可能造成严重的数据泄漏(机器学习):训练集和测试集中可能出现几乎相同的上下文。如果按文档或按时间划分数据符合预期部署场景,这样的划分就能提供更严格的评估。对于下游任务,还必须在任务层面衡量预测质量。困惑度降低并不保证语音识别错误会按相同比例减少,而有用的分类特征也未必能构成一个好的语言模型。

作为特征和检索单元的N元组

N元组表示法可以描述文档,而不必为完整序列赋予概率。每种不同的N元组都成为一个特征,文档则用特征是否出现、原始计数、归一化频率或加权值来表示。词袋模型使用词的一元组特征;加入词的二元组或三元组,可以保留有限的局部顺序信息。因此,“not useful”(没有用)可以表示为一个独立特征,而不只是分别记录“not”和“useful”的出现。

这种表示是稀疏的:一篇文档通常只包含整个文档集中所出现的N元组的一小部分。包括支持向量机在内的线性分类器能够有效处理这类稀疏向量。朴素贝叶斯分类器也可以使用从N元组提取的特征,尽管相邻且相互重叠的N元组显然并不具有统计独立性。这些特征能否用于有效预测,并不取决于独立性假设是否如实描述了语言。

词频—逆文档频率加权可以降低出现在许多文档中的N元组的影响,同时突出集中出现在较小文档子集中的模式。这通常有助于主题分类和检索。不过,常见表达并非总是缺乏信息:功能词序列可能有助于识别写作风格,常见的句法模式也可能有助于区分体裁。因此,特征加权和特征选择应取决于具体任务,而不能一概认定越罕见的模式就越好。

当精确词匹配容易失效时,字符N元组尤其有用。彼此相关的屈折变化形式即使完整词形不同,也可能共享许多字符片段。拼写错误、音译变体以及此前未见过的名称,也可能与已知形式保留部分重叠。这有助于语言识别、近似字符串匹配,以及难以分词的场景中的分类任务。不过,这种稳健性也可能引入噪声,因为无关的字符串也可能共享较短的片段,而很短的N元组往往缺乏区分能力。

在检索系统中,数据库索引可以将每个N元组与包含它的文档或字符串关联起来。例如,字符三元组可以先为查询生成候选匹配项,再通过计算成本更高的编辑距离来验证这些候选项。在文档比较中,可以根据词片段集合之间的重叠程度进行比较;这里的词片段(word shingles)通常也是词N元组的另一种叫法。它们的Jaccard相似度为

J(A,B)=∣A∩B∣∣A∪B∣.J(A,B)=\frac{|A\cap B|}{|A\cup B|}.

这种基于集合的度量忽略了各元素的出现次数,而计数向量比较则保留了这一信息。

特征提取过程的拟合与评估必须谨慎进行。如果利用整个数据集的标签来选择具有区分能力的N元组,即使最终分类器只在指定的训练子集上训练,也会造成评估中的信息泄漏。庞大的N元组词表还可能编码数据集特有的偶然线索,例如页眉或来源标识符,而不是所要识别的概念。这些特征易于检查,因此此类线索更容易被发现,但这并不能阻止它们被纳入特征。

序列解码、压缩及非语言应用

在语音识别中,N元语言模型为候选词序列提供先验偏好。声学模型评估候选序列与声音的匹配程度,语言模型则评估其在语言上的合理性。在简化的概率表述中,

W^=arg⁡max⁡WP(X∣W)P(W),\widehat W = \arg\max_W P(X\mid W)P(W),

其中,XX 为声学观测,WW 为词序列。实际的解码器通常将声学模型得分与语言模型得分加权组合,并加入插入惩罚项。由于N元模型只依赖有限的历史信息,搜索过程中可以高效管理状态兼容的候选假设。

传统的统计机器翻译也使用N元语言模型,使译文更倾向于流畅的目标语言序列。翻译模型可能提出多种选词和词序调整方案;目标语言模型则帮助区分局部自然的组合与生硬的组合。它的作用在于提高流畅度,而非直接保证译文在语义上忠实于原文。概率较高的目标语言短语仍可能表达错误的含义,而长距离的一致关系也可能超出模型的上下文范围。

拼写纠错同样需要结合两类证据:一类与可能出现的错误有关,另一类与原本想表达的文本有关。一个与拼错字符串相近的候选项,在周围词语构成的上下文中,可能变得更合理,也可能变得更不合理。词级N元组可以区分同音词等候选项,字符级N元组则可以为候选词内部的拼写模式评分。依靠上下文纠错,并不只是选择频率最高的候选项:还必须将频率与产生当前所见错误的概率以及相关的相邻单元综合权衡。

N元组概率还将预测与无损数据压缩联系起来。对于概率为 pp 的事件,理想编码大约需要 −log⁡2p-\log_2p 比特。因此,若上下文模型为实际出现的下一个符号赋予较高概率,就可以通过算术编码等方法实现更短的编码。实际的压缩程序可能采用变长上下文、自适应更新或多个预测器的混合,而不是单一的固定阶数表。其基本关系不变:校准得更好的序列预测可以缩短编码长度,但实际效果还取决于模型开销和编码细节。

除自然语言外,只要观测数据具有有意义的离散顺序,就可以应用N元组。在脱氧核糖核酸分析中,由 kk 个连续碱基组成的序列通常称为k-mer。这些模式的计数可用于序列比较及其他计算分析,但其生物学解释取决于链的方向、测序错误以及所进行的分析。在网络安全领域,字节或指令的N元组可作为识别文件类型或对恶意软件进行分类的特征,而系统事件序列可用于异常检测。

这些应用共享的是一种表示原则,并不保证底层过程只具有短期记忆。字节模式可能反映的是文件格式,而非程序行为;生物学中的某个k-mer也可能出现在互不相关的基因组上下文中。选择 nn 时,需要在特异性与覆盖范围之间权衡;有用的局部相关性,也必须与对序列生成机制的完整解释区分开来。

历史发展及其与神经模型的关系

对符号序列的统计研究早于现代数字语言处理。安德烈·马尔可夫在20世纪初对相依序列的研究中,曾分析俄语文学文本中元音与辅音的分布模式。这些研究尚不属于当代的词级N元语法系统,但为有限记忆依赖关系的数学框架奠定了基础。克劳德·香农在1948年的通信理论研究中,依据统计依赖关系构造了对英语的逐次近似;他在1951年的研究则考察了书面英语的可预测性与冗余度。

随着计算机语音识别的发展,N元语言模型成为一项核心工程工具。20世纪70年代至80年代,研究系统将声学证据与统计词序列模型相结合,而规模更大的机器可读语料库也使更精细的频次统计成为可能。IBM公司的弗雷德里克·耶利内克及其同事对这一统计方法的发展产生了重要影响。该方法的实用优势在于,将困难的序列问题分解为局部估计的概率,并将这些概率纳入高效的解码算法。

多项进展改进了对稀疏证据的处理。I. J. 古德于1953年发表的论文介绍了与艾伦·图灵相关的频率估计思想。斯拉瓦·卡茨于1987年提出了一种影响深远的回退语言建模方法。赖因哈德·克内瑟和赫尔曼·奈于1995年提出了克内瑟—奈平滑法,斯坦利·陈和约书亚·古德曼则在20世纪90年代后期发表的研究中,对平滑方法进行了广泛考察。这些成果回应了一个核心的经验事实:仅仅扩大语料库规模,并不能消除为未见组合估计概率的必要性。

神经概率语言模型提供了另一种共享统计信息的方式。约书亚·本吉奥及其同事于2003年提出的模型学习了词的分布式表示,使一个词序列的证据也能用于预测相关序列。这类模型不再将每段历史序列视为互不相关的查表键,而是学习跨上下文共享的连续参数。此后,循环神经网络提供了在不同长度的历史序列中传递信息的机制;而2017年提出的Transformer架构则利用注意力机制,根据长度有界的输入上下文表示进行预测。

因此,大语言模型并非简单的高阶N元语法表。两者都可以估计下一个词元的概率,但神经模型会组合学得的表示,并在许多不同的上下文之间共享参数。这使其能够实现单纯查找表所不具备的某些泛化(机器学习)能力。反过来说,较长的上下文窗口并不保证模型能正确利用其中的每一种依赖关系,而且神经模型仍然可以学到很强的局部统计规律。

在重视模型紧凑性、计数透明度、可预测的查表行为,或需要小数据基线模型的场景中,N元语法方法仍然有用。这类方法也清楚地揭示了局部序列统计与更广泛的语言结构之间的界限。对于任意两段历史序列,只要模型所考虑的后缀相同,固定阶数的模型就会赋予它们相同的下一词元分布,而不考虑更早的语篇、事实背景或已经形成的句法约束。提高阶数可以推远这条界限,却不能将其消除;采用字符或子词作为单元能够缓解某些词汇表问题,但有限记忆的限制依然存在。