提出新分块覆盖方法，比BPE更高效压缩文本。
A Partition Cover Approach to Tokenization
- 将分词建模为优化问题，设计贪心算法GreedTok
- 在真实语料上压缩效果优于BPE和Unigram
- 适合追求高效分词的NLP研究者使用
分词是将字符串编码为固定词汇量令牌的过程，在自然语言处理中广泛应用。当前主流算法是字节对编码（BPE），将其视为压缩问题并通过一系列合并操作求解。本文将分词问题重新建模为优化目标，证明其为NP难问题（通过顶点覆盖简化归约），并提出一种多项式时间贪心算法GreedTok。该模型自然转化为经典的加权最大覆盖问题，可利用(1 - 1/e)近似算法GreedWMC求解。在真实语料上的实证评估显示，GreedTok在压缩性能上优于BPE和Unigram，且覆盖得分接近GreedWMC。此外，对两个参数量达10亿的Transformer语言模型进行大规模预训练，对比BPE与GreedTok作为分词器的效果发现：即使控制数据集比例或总训练标记数，GreedTok仍能实现更低的每字节比特数。
原文摘要 · Abstract (English)
Tokenization is the process of encoding strings into tokens of a fixed vocabulary size, and is widely utilized in Natural Language Processing applications. The leading tokenization algorithm today is Byte-Pair Encoding (BPE), which formulates the tokenization problem as a compression problem and tackles it by performing sequences of merges. In this work, we formulate tokenization as an optimization objective, show that it is NP-hard via a simple reduction from vertex cover, and propose a polynomial-time greedy algorithm GreedTok. Our formulation naturally relaxes to the well-studied weighted maximum coverage problem which has a simple $(1 - 1/e)$-approximation algorithm GreedWMC. Through empirical evaluations on real-world corpora, we show that GreedTok outperforms BPE and Unigram on compression and achieves a covering score comparable to GreedWMC. Finally, our extensive pre-training for two transformer-based language models with 1 billion parameters, comparing the choices of BPE and GreedTok as the tokenizer, shows that GreedTok achieves a lower bit per byte even when we control for either the total dataset proportion or total training tokens.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。