用凸优化方法构建分词器，提升语言模型效率与可证明最优性。
Tokenisation via Convex Relaxations
- 将分词器构造转化为线性规划问题，通过凸优化求解。
- 在常见词表规模下，性能接近理论最优，误差小于1%。
- 可提供距最优的下界证明，适合追求理论保障的研究者。
分词是当前自然语言处理流程的关键环节。现有分词算法如BPE和Unigram为贪心策略——仅做局部最优选择，未考虑整体词汇表效果。本文将分词器构建建模为线性规划问题，利用凸优化工具求解，提出新算法ConvexTok。实验表明，ConvexTok在固有分词指标和语言模型的每字节比特数（BpB）上均一致提升；下游任务性能也有所改善，但效果较不稳定。此外，ConvexTok可基于特定目标提供距离最优的下界，实证显示在常见词表规模下其性能距最优不足1%。
原文摘要 · Abstract (English)
Tokenisation is an integral part of the current NLP pipeline. Current tokenisation algorithms such as BPE and Unigram are greedy algorithms -- they make locally optimal decisions without considering the resulting vocabulary as a whole. We instead formulate tokeniser construction as a linear program and solve it using convex optimisation tools, yielding a new algorithm we call ConvexTok. We find ConvexTok consistently improves intrinsic tokenisation metrics and the bits-per-byte (BpB) achieved by language models; it also improves downstream task performance, but less consistently. Furthermore, ConvexTok allows the user to certify how far their tokeniser is from optimal, with respect to a certain objective, via a lower bound, and we empirically find it to be within 1\% of optimal at common vocabulary sizes.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。