トークナイゼーション問題がNP完全であることが証明され、データ圧縮の課題が倍増
2024-12-22
arXivに掲載された論文では、トークナイゼーションの2つのバリアントのNP完全性が証明されました。トークナイゼーションとは、データセットを最大δ個のシンボルに圧縮する問題であり、その2つのバリアントとは、直接語彙を見つける（直接トークナイゼーション）か、一連の結合操作を選択する（ボトムアップトークナイゼーション）かのいずれかです。この発見は、データ圧縮と自然言語処理に大きな影響を与え、大規模データセットのトークナイゼーション問題を効率的に解決することの途方もない困難さを浮き彫りにしています。