紹介論文
今回紹介する論文はTokenisation over Bounded Alphabets is Hardという論文です。
この論文を一言でまとめると
自然言語処理の基本、トークナイゼーション。近年、その計算複雑性が明らかになりつつあります。本記事では、有界アルファベットにおけるトークナイゼーションの困難性について解説し、実用的なアルゴリズムへの示唆を探ります。
トークナイゼーションとは？基本と課題
自然言語処理（NLP）の入り口に立つのが、トークナイゼーションです。これは、テキストを意味のある最小単位「トークン」に分割する処理のこと。例えば、「私は猫が好きです。」という文は、「私」「は」「猫」「が」「好き」「です」「。」という7つのトークンに分けられます。
なぜトークナイゼーションが重要なのか？
トークナイゼーションは、言語モデルがテキストを理解するための第一歩。適切にトークン化することで、モデルは単語の意味や文法構造を学習しやすくなります。逆に、不適切なトークン化はモデルの性能を大きく左右してしまうため、非常に重要な処理と言えます。
トークナイゼーションの代表的な手法
トークナイゼーションには様々な手法がありますが、代表的なものとして以下の3つが挙げられます。
* Word-based：単語をそのままトークンとする最もシンプルな手法。しかし、未知語（語彙にない単語）への対応や、語彙数が膨大になるという課題があります。
* Character-based：文字をトークンとする手法。未知語の問題は解決できますが、系列長が長くなり、文脈を捉えにくいというデメリットがあります。
* Subword-based：単語よりも小さい単位（subword）をトークンとする手法。Word-basedとCharacter-basedのいいとこどりをしたような手法で、未知語問題と語彙数のバランスが良いのが特徴です。
Subword-basedトークナイゼーション：BPEとUnigramLM
Subword-basedトークナイゼーションの代表的なアルゴリズムが、BPE (Byte Pair Encoding)とUnigramLMです。
* BPE：テキスト中で最も頻繁に出現するペアを一つのトークンにマージしていくことで語彙を獲得します（Sennrich et al., 2016）。シンプルで高速ですが、一度マージしたトークンを分割しないため、柔軟性に欠けるという側面も。
* UnigramLM：Unigram言語モデルを用いて、テキストの尤度を最大化するようにsubword分割を学習します（Kudo, 2018）。BPEよりも柔軟な語彙を獲得できますが、計算コストが高いというデメリットがあります。
従来のアルゴリズムが抱える課題
BPE、UnigramLMともに、greedyなアルゴリズムであるため、必ずしも最適なトークン化を保証するわけではありません。より良いトークン化が存在する可能性があり、研究の余地があります。
さらに、最適なトークナイザーを見つける問題は、計算量的に難しい（NP困難）ことが示されています（Kozma and Voderholzer, 2024; Whittington et al., 2025; Lim et al., 2025）。つまり、完璧なトークナイザーを効率的に作ることは難しい、ということです。
トークナイザーの評価軸
トークナイザーの性能は、主に以下の指標で評価されます。
* 圧縮率：テキストをどれだけコンパクトに表現できるか。トークン数が少ないほど良いとされます。
* 未知語の割合：未知語がどれだけ少ないか。未知語が多いと、モデルの性能が低下する可能性があります。
* 下流タスクの性能：翻訳、テキスト分類など、トークナイゼーション後のテキストを用いたタスクの性能。最も重要な評価指標と言えるでしょう。
近年では、圧縮率だけでなく、トークン化された文字列の特性が下流タスクに与える影響も重要視されています（Schmidt et al., 2024; Ali et al., 2024）。
有界アルファベットにおけるトークナイゼーションの難しさ
自然言語処理（NLP）におけるトークナイゼーションは、テキストを意味のある単位（トークン）に分割する重要なプロセスです。しかし、近年の研究では、最適なトークナイザーを効率的に見つけることが、実は非常に難しい問題であることが明らかになりつつあります。
従来のトークナイゼーション研究の多くは、非有界アルファベット、つまり、扱う文字の種類に上限がないという前提に基づいていました。これは、理論的な解析には適していますが、現実のNLPシステムとは異なる点があります。なぜなら、実用的なトークナイザーは、バイトやUnicode文字といった、固定サイズアルファベットで動作することがほとんどだからです。
そこで本記事で紹介する論文「Tokenisation over Bounded Alphabets is Hard」では、有界アルファベット、つまり、扱う文字の種類に上限があるという制約下でのトークナイゼーション問題を扱います。具体的には、n-aryトークナイゼーション問題を定義し、サイズnのアルファベットΣ上の文字列を、最適なトークン列に変換する問題を考えます。
n-aryトークナイゼーション問題とは？
n-aryトークナイゼーション問題では、語彙サイズKが与えられたとき、データセットDを最も圧縮するトークナイザーを求める必要があります。この問題には、以下の2つのバリアントが存在します。
* 直接トークナイゼーション (Direct Tokenization): 語彙Sを直接選択し、最適なエンコードを適用します。
* Bottom-upトークナイゼーション (Bottom-up Tokenization): マージ操作のシーケンスを選択し、それらを適用して語彙を構築します。
なぜ有界アルファベットを考慮する必要があるのか？
実用的なトークナイザーは固定サイズのアルファベットで動作するため、現実的な設定での計算複雑性を理解する必要があります。また、サイズnのアルファベットに対する困難性の証明は、より大きなサイズのアルファベットにも適用可能であるため、基本的なケースとして解析する意義があります。
本研究では、後続のセクションで、この有界アルファベットという制約が、トークナイゼーションの計算複雑性にどのような影響を与えるのかを詳しく見ていきます。
NP困難性の証明：理論的背景と直感的理解
このセクションでは、二値アルファベットという制約下でのトークナイゼーションが、なぜ難しいのかを理論的に解説します。具体的には、**二値アルファベットにおけるbottom-upトークナイゼーションとdirectトークナイゼーションがNP困難であること**を証明し、その証明の概要と意味するところを解説します。
NP困難性とは？
まず、**NP困難性**について簡単に説明します。これは、ある問題が「解くのが非常に難しい」クラスに属することを示すものです。厳密には、NP（非決定性多項式時間）に属する最も難しい問題のクラスであり、NP困難な問題に対する多項式時間アルゴリズムが存在しないと予想されています (P != NP)。
NP困難な問題の例としては、巡回セールスマン問題やナップサック問題などが挙げられます。これらの問題は、入力サイズが大きくなると、計算時間が指数関数的に増加するため、現実的な時間で最適解を求めることが非常に困難になります。
近似アルゴリズムとPTAS
NP困難な問題を解くためには、最適解を諦めて、**近似解**を求めることが現実的な選択肢となります。**近似アルゴリズム**とは、最適解に近い解を多項式時間で求めるアルゴリズムのことです。
さらに、**PTAS (Polynomial-Time Approximation Scheme)** という概念があります。これは、任意の精度で近似解を求められるアルゴリズムのことです。もし、NP困難な問題に対してPTASが存在しない場合、多項式時間で良い近似解を求めることも困難であることを示す強力な根拠となります。
3-OCC-MAX2SATからの帰着
今回のNP困難性の証明では、**3-OCC-MAX2SAT** という問題からの**帰着**という手法を用います。これは、ある問題（この場合は3-OCC-MAX2SAT）の解法が、別の問題（この場合はトークナイゼーション）の解法に帰着できることを示すことで、後者の問題もNP困難であることを証明する手法です。
3-OCC-MAX2SATは、充足可能性問題の一種で、各変数が3回出現するような制約のもとで、充足できる節の数を最大化する問題です。この問題は、近似することが難しいことが知られています。
二値アルファベットにおけるNP困難性
本研究では、二値アルファベット（{0, 1}のような2つの記号のみからなるアルファベット）における**直接トークナイゼーション**と**bottom-upトークナイゼーション**の両方がNP困難であることを証明しています。さらに、APX困難であることも示しています。
APX困難であるということは、多項式時間で一定の近似比率よりも良い近似解を求めることがNP困難であることを意味します。
証明の概要と直感的理解
証明は、3-OCC-MAX2SATのインスタンスから、トークナイゼーション問題のインスタンスを多項式時間で構築することによって行われます。そして、3-OCC-MAX2SATの解が、トークナイゼーション問題の解に対応することを示すことで、帰着が成立することを示します。
直感的には、トークナイゼーションにおいて、最適なトークンの組み合わせを選択する問題が、3-OCC-MAX2SATにおける充足できる節の数を最大化する問題と対応していることがわかります。
NP困難性から何が言えるのか？
これらの結果は、二値アルファベットという非常に単純な設定であっても、最適なトークナイザーを効率的に見つけることは非常に難しい可能性が高いことを示唆しています。つまり、現実的な設定で用いられているBPEやUnigram LMといったアルゴリズムは、最適解を保証するものではなく、あくまで近似的な解を求めているに過ぎないということです。
単項アルファベットにおけるdirectトークナイゼーションの特異性
前のセクションでは、二値アルファベットという、現実に即した設定でもトークナイゼーションがNP困難であることを示しました。しかし、アルファベットのサイズをさらに極端に小さくしたらどうなるでしょうか？
単項アルファベットとは
単項アルファベットとは、{a} のように、たった一つの記号のみから構成されるアルファベットのことです。この場合、文字列は ‘a’, ‘aa’, ‘aaa’ のように、記号の繰り返しで表現され、その違いは長さのみで区別されます。
驚くべき結果：単項アルファベットでもNP困難
ここで驚くべき結果があります。なんと、単項アルファベットという極端な条件下でも、directトークナイゼーションがNP困難であることが示されたのです[cite: whittington et al., 2025]。これは、アルファベットサイズを極限まで小さくしても、トークナイゼーションの本質的な難しさが変わらないことを意味します。
頂点被覆問題からの帰着
このNP困難性を示すために、論文では頂点被覆問題 (Vertex Cover) からの帰着という手法が用いられています。頂点被覆問題とは、グラフが与えられたとき、すべての辺をカバーする最小の頂点の集合を見つける問題です。
この問題を解くアルゴリズムが存在すれば、unary direct tokenization問題も解けることを示すことで、unary direct tokenization問題が少なくとも頂点被覆問題と同程度に難しい、つまりNP困難であることを証明します。
コインシステムとの関係
興味深いことに、unary direct tokenizationは、コインシステムのdenomination（硬貨の種類）を選ぶ問題と等価であると見なすこともできます[cite: shallit, 2003]。つまり、ある金額を支払うために、どのような硬貨の組み合わせが最適かを選ぶ問題です。
この問題は、動的計画法で解けることが知られています。しかし、unary direct tokenizationにおける入力（文字列の長さ）は指数関数的に増加するため、問題全体としてはNP困難となります。
計算複雑性の根源
この結果は何を意味するのでしょうか？アルファベットサイズが問題なのではなく、組み合わせ最適化の性質こそが、計算複雑性の根源であることを示唆しています。つまり、与えられた文字列に対して、最適なトークンの組み合わせを選択するという問題が、本質的に難しいのです。
この発見は、トークナイゼーションの研究における重要な転換点となります。アルファベットサイズという表面的な要素に囚われず、問題の本質的な難しさに目を向ける必要性を示唆しているからです。
今後の展望：近似アルゴリズムと実用への示唆
実用アルゴリズムの限界と、今後の研究の方向性
今回の研究で、有界アルファベットにおけるトークナイゼーションがNP困難であることが示されました。これは、BPEやUnigramLMといった実用的なトークナイザーが、本質的に近似的なアルゴリズムであることを理論的に裏付けています。これらのアルゴリズムは高速に動作するものの、常に最適なトークン化結果を保証するわけではありません。
では、今回の研究結果は、今後のトークナイゼーション研究にどのような示唆を与えるのでしょうか？
理論的な保証のある近似アルゴリズムの開発
まず、近似アルゴリズムの開発が重要になります。NP困難な問題を解決するためには、必ずしも最適解を求める必要はありません。実用的な時間で、ある程度の精度が保証された解を求めることができれば十分です。今後の研究では、BPEやUnigramLMよりも優れた近似精度を持つアルゴリズムや、特定の条件下で最適解を求めることができるアルゴリズムの開発が期待されます。
他の目的関数やトークナイゼーション手法の解析
今回の研究では、圧縮率を目的関数として、directトークナイゼーションとbottom-upトークナイゼーションという2つの手法に焦点を当てました。しかし、トークナイゼーションには、他にも様々な目的関数や手法が存在します。例えば、以下のようなものが考えられます。
* 下流タスクの性能最大化: 特定の翻訳タスクや分類タスクにおいて、最も性能の良いトークン化結果を直接的に学習する。
* 未知語の最小化: 未知語の出現を抑制し、モデルの汎化性能を高める。
* SentencePiece: Googleが開発した、言語に依存しないトークナイザー [未引用]。
これらの目的関数や手法についても、計算複雑性や近似アルゴリズムの観点から解析することで、より深く理解を深めることができるでしょう。
下流タスクとの連携
最終的には、トークナイゼーションは下流タスク（翻訳、分類、言語モデリングなど）のために行われます。そのため、トークナイゼーションを単独で最適化するだけでなく、下流タスクの性能を最大化するようにトークナイゼーションを共同で最適化するというアプローチも重要になります。例えば、下流タスクの勾配情報を用いてトークナイザーを学習したり、トークナイザーの選択を下流タスクのアーキテクチャに組み込んだりするなどの方法が考えられます。
まとめ
今回の研究は、トークナイゼーションという自然言語処理の基本的なタスクが、実は非常に難しい問題であることを改めて示しました。しかし、それは同時に、今後の研究の可能性を広げるものでもあります。近似アルゴリズムの開発、他の目的関数や手法の解析、下流タスクとの連携など、様々な方向性で研究を進めることで、より高性能で実用的なトークナイザーが実現されることが期待されます。
コメント