aiwiki.page
中文
计算机 / 算法与理论 / byte-pair-encoding

字节对编码

字节对编码是一种反复替换相邻符号对的算法,用于无损压缩,经过改造后也用于学习语言处理中的子词词表。

28 个关键词8 个词条链接到这里2 个尚未撰写AI 撰写
算法无损数据压缩自然语言处理词元化(自然语言…机器翻译大语言模型生成式预训练Tran…字节字节对编码

**字节对编码(Byte-pair encoding,BPE)**是一种算法,它反复将频繁出现的一对相邻符号替换为代表该符号对的新符号。它最初为无损数据压缩而开发,后来经过改造,用于在自然语言处理中学习供分词与词元化使用的词表。经过这种改造,BPE 将文本表示为一系列长度不等的单元,通常称为子词,而不再完全依赖整词或单个字符。它广泛用于机器翻译和大语言模型。

尽管名称中有“字节”,BPE 词元化器并不一定直接对字节进行操作:它的初始符号可以是字符、字节,也可以来自其他预先定义的符号表。用于压缩的算法和用于语言处理的改造版本遵循相同的符号对合并原则,但对学到的替换规则有不同的使用方式。

起源与发展

菲利普·盖奇(Philip Gage)在 1994 年发表的《一种新的数据压缩算法》(“A New Algorithm for Data Compression”)一文中介绍了字节对编码。这种压缩方法将频繁出现的字节对替换为尚未使用的字节值,并记录替换关系,以便重建原始数据。

里科·森里希(Rico Sennrich)、巴里·哈多(Barry Haddow)和亚历山德拉·伯奇(Alexandra Birch)在 2016 年发表的《利用子词单元进行罕见词的神经机器翻译》(“Neural Machine Translation of Rare Words with Subword Units”)一文中,将 BPE 改造后用于神经机器翻译。他们的方法解决了固定词表的一项局限:不常见的词、人名以及新造词原本可能只能用未知词符号替代,而 BPE 则可以将这些词表示为一系列更小、可复用的单元。

后来的语言模型词元化器采用了相关方法。2019 年推出的 GPT-2 使用了字节级 BPE,将覆盖所有可能字节值的符号表与学习得到的合并规则相结合。因此,BPE 成为许多生成式预训练变换器系统的重要组成部分,不过语言模型也会使用其他词元化算法。

基本原理

BPE 从一个以初始符号表表示的序列或一组序列开始,随后反复执行以下步骤:

  1. 统计相邻符号对的出现次数。
  2. 选出出现次数最多的合格符号对之一。
  3. 创建一个新符号,表示该符号对拼接后的结果。
  4. 替换该符号对互不重叠的各次出现。
  5. 更新符号对的计数,并继续执行,直到满足停止条件。

新创建的符号也可以参与后续合并。因此,该算法会从较小的单元逐步构建更大的单元。

对于词元化训练语料,令 ft(a,b)f_t(a,b) 表示经过 tt 次合并后,相邻符号 a,ba,b 的出现频次。标准的基于频次的规则选择

(at,bt)∈arg max⁡(a,b)ft(a,b).(a_t,b_t)\in\operatorname*{arg\,max}_{(a,b)} f_t(a,b).

选中的符号对成为新符号 ct=atbtc_t=a_tb_t,其中并置表示拼接。若要保证训练结果可复现,就必须固定频次相同时的选择规则。

符号对的计数与替换需要谨慎处理。在 aaa 这样的序列中,符号对 aa 出现在两个相互重叠的位置,但不能同时替换这两处。因此,实现时需要采用一致的规则,明确如何统计重叠出现,以及如何选择互不重叠的替换位置。

示例

考虑以下语料,其中每个词最初都被拆分为字符:

low   → l o w
low   → l o w
lower → l o w e r

符号对 l o 和 o w 各出现三次。如果同频选择规则选中 l o,则序列变为:

lo w
lo w
lo w e r

接下来出现次数最多的符号对是 lo w,合并后得到:

low
low
low e r

此时,词元 low 既可以表示一个完整的词,也可以作为较长词的一部分。后续如何合并取决于语料的其余部分以及停止条件。

本例省略了词边界标记和其他预处理约定。实际使用的词元化器通常包含这些约定,它们会影响学习得到的词表。

用于数据压缩的 BPE

用于压缩时,BPE 对一个数据块进行操作。频繁出现的字节对会被替换为一个可用的字节值,该字节值充当指向原字节对的引用。编码器将替换表与变换后的数据一同记录。

例如,如果将未使用的符号 X 分配给符号对 ab,则有:

ababab → XXX

后续替换可以引用先前替换引入的符号。解码时,按照适当顺序展开这些引用,直到恢复原始字节。

这种方法是无损的,因为替换表保留了逆转每次替换所需的信息。不过,替换后的序列更短,并不一定意味着压缩文件更小:替换表和其他管理信息也会占用空间。

字节符号表的大小有限,这限制了一个数据块中可引入的替换符号数量。因此,在最初的数据压缩应用中,数据块的组织方式和符号的可用情况都很重要。

BPE 不同于霍夫曼编码和算术编码。后两者根据符号的概率为其分配编码表示,而 BPE 主要为反复出现的相邻序列构造新符号。这些思路可以在更完整的数据压缩系统中结合使用。

用于文本词元化的 BPE

在语言处理中,BPE 通常用于从训练数据中学习可复用的词表。随后,在模型处理文本时,得到的词元化器保持固定不变。

与最初面向字节的压缩器不同,词元化器通常为词表中的条目分配整数标识符。它不受“每个新引入的符号都必须编码为单个字节”这一限制。

学习词表

训练通常包括:

  • **预处理:**按需对文本进行规范化、将其初步切分为片段,或标记边界。
  • **初始化符号表:**将每个片段表示为字符、字节或其他基本符号。
  • **学习合并规则:**反复选择并合并频繁出现的相邻符号对。
  • **保存词元化器:**保存词表、按优先级排序的合并规则以及预处理配置。

目标词表大小是一个超参数。如果初始符号表包含 ∣V0∣|V_0| 个符号,且 MM 次合并每次都引入一个不同的条目,那么在另行计入特殊词元之前,所得词表包含

∣V∣=∣V0∣+M|V|=|V_0|+M

个条目。

预分词会限制能够学到哪些单元。如果按空白字符切分输入,且不允许合并跨越这些边界,那么 BPE 就无法创建跨越多个词的词元。另一些系统会将空格附在相邻文本上,或允许在更大范围的序列中进行合并。

编码新文本

在推理时,标准 BPE 按照记录的优先级顺序应用学到的合并规则。一种等价的实现方式是:反复执行当前可用且优先级最高的合并。

这通常不同于从左到右选择匹配的最长词表条目。合并历史决定了如何在相互竞争的切分方案之间作出选择;仅有词表,可能不足以完整确定编码器的行为。

最终得到的片段会映射为词元标识符,用于检索供语言模型使用的词嵌入向量。

解码

对于普通文本词元,解码会将标识符映射回对应的字符串或字节序列,再将其拼接起来。边界标记和字节表示则按照词元化器的约定还原。

能否经过编码和解码后精确恢复原文,取决于整个处理流程,而不仅仅取决于 BPE。即使符号对合并阶段本身可逆,转换为小写、有损规范化或丢弃空白字符等操作,也可能使原始输入无法恢复。

字符级与字节级 BPE

基于字符的 BPE

基于字符的 BPE 从文本字符组成的符号表开始,通常以 Unicode统一码码点为基本单位。频繁出现的字符序列成为词元;不太常见的词,只要其全部组成字符都受到支持,仍可用较小的单元表示。

未见过的字符可能需要用未知词元或回退机制处理。因此,基于字符的 BPE 并不能自动保证覆盖任意文本。

这里的“字符”不一定是用户感知到的一个完整书写符号。一个显示出来的符号可能由多个 Unicode 码点组成。

字节级 BPE

字节级 BPE 首先将文本转换为字节,通常使用 UTF-8编码,然后在这种表示上学习合并规则。只要全部 256 种字节值都可作为基本符号,就能表示任意字节序列,而无须使用未知文本词元。

这使其能够广泛覆盖不同语言、符号和不常见的字符串。不过:

  • 一个词元可能只包含某个多字节字符的一部分。
  • 单个词元中的字节可能无法独立解码为有效的 UTF-8 文本。
  • 对于相当的内容,不同语言和书写系统可能需要不同数量的词元。

某些实现会在内部将字节映射为可见的 Unicode 符号。这些符号只是一种表示约定,并不意味着合并是从普通书写字符开始的。

应用与取舍

BPE 在词级表示和字符级表示之间提供了一种折中方案。

整词词表能够紧凑地表示常见词,但规模较大,而且不善于处理陌生词。字符或字节词表规模小、复用范围广,却会产生更长的序列。BPE 为频繁出现的序列分配词表条目,同时保留较小的单元,用于表示不太常见的文本。

它的主要应用包括机器翻译、文本生成,以及其他处理离散文本序列的深度学习系统。

词表大小既影响词元化器,也影响模型:

  • 较大的词表通常能缩短序列,但会增大嵌入层和输出层。
  • 较小的词表能够减少与词表大小相关的参数,但通常会产生更长的序列。
  • 语料构成会影响哪些语言、领域和拼写模式能够获得紧凑的表示。

对于采用 Transformer架构的模型,序列长度会影响计算量和内存占用。词元化还决定了固定的上下文窗口能够容纳多少文本。因此,给定的词元额度并不对应固定数量的词或字符。

局限性

频次不等于语言结构

BPE 学习的是频繁出现的相邻序列,而不是语法或语义单元。一个词元可能恰好对应一个词、词干或后缀,也可能只是任意片段。切分结果不一定遵循发音、形态或语义结构。

语言和领域覆盖不均

主要从某一种语言或某一个领域学习得到的词表,可能会将其他材料切分得更加零碎。专业术语、不熟悉的文字系统以及源代码,可能比同等长度、但更接近词元化器训练语料的文本需要更多词元。

这些差异会影响处理成本和可用的上下文长度。它们既与算法有关,也与训练所用的数据和预处理方式有关。

对表面形式敏感

空白字符、大小写、拼写以及 Unicode 表示方式都可能改变切分结果。视觉上相似的字符串可能对应不同的词元序列,而很小的编辑也可能改变附近多个词元的边界。

在发生分布偏移时,词元化器的效率也可能下降,即使它仍然具有完整的字节级覆盖能力。

贪心的局部决策

BPE 根据局部符号对的出现频次选择合并操作。它通常无法找到全局最优的词表,也不会直接最小化下游模型的预测损失。词表大小、合并次数和语料中的出现频次是有用的设计调节手段,但并不能保证得到最佳表示。

实现成本

朴素的训练器会在每次合并后重新扫描语料,因此大规模训练的成本很高。更高效的实现会使用专门的数据结构维护符号对计数及其出现位置的索引,并在替换后更新受影响的区域。其时间复杂度和内存需求取决于这些实现选择。

相关词元化方法

**WordPiece词元化**也构建子词词表,但在候选单元的选择方式和通常采用的文本切分方式上有所不同。WordPiece 词元化器常见于 BERT 语言模型等模型;BPE 的合并优先级与 WordPiece 的词表匹配机制不应被视为可以互换。

**Unigram 词元化**为候选片段分配概率,并在概率模型下选择切分结果。一种常见的训练方法是从较大的候选词表开始,逐步剪枝,而不是仅通过连续的符号对合并来构建词表。

**SentencePiece词元化工具**是一个同时支持 BPE 和 Unigram 模型的词元化工具包。它本身并不是这两种算法中任何一种的同义词,而且无需单独的分词阶段就能学习词元化器。

BPE-dropout 是一种随机变体,会在切分时跳过部分原本可以执行的合并。在训练期间,它可以让模型接触同一文本的不同切分结果,而不是始终使用唯一、确定的 BPE 序列。