論文の概要: A partition cover approach to tokenization

• arxiv url: http://arxiv.org/abs/2501.06246v2
• Date: Sun, 25 May 2025 15:39:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-27 14:32:53.156437
• Title: A partition cover approach to tokenization
• Title（参考訳）: トークン化への分割被覆アプローチ
• Authors: Jia Peng Lim, Shawn Tan, Davin Choo, Hady W. Lauw,
• Abstract要約: トークン化とは、文字列を一定の語彙サイズのトークンに符号化するプロセスである。 Byte-Pair corpora (BPE) は、トークン化問題を圧縮問題として定式化し、マージのシーケンスを実行することでそれに取り組む。 GreedTokは圧縮においてBPEやUnigramよりも優れており、GreedWMCに匹敵するカバースコアが得られることを示す。
• 参考スコア（独自算出の注目度）: 27.78022124795594
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.
• Abstract（参考訳）: トークン化は、文字列を一定の語彙サイズのトークンに符号化するプロセスであり、自然言語処理アプリケーションで広く利用されている。 今日の主要なトークン化アルゴリズムはByte-Pair Encoding (BPE) であり、これはトークン化問題を圧縮問題として定式化し、マージのシーケンスを実行することでそれに取り組む。 本研究では,トークン化を最適化目的として定式化し,頂点被覆からの単純な還元によるNPハードであることが示し,多項式時間グリードアルゴリズムGreedTokを提案する。 我々の定式化は、単純な$(1 - 1/e)$-approximationアルゴリズムであるGreedWMCの重み付き最大カバレッジ問題に自然に緩和する。 実世界のコーパスを実証的に評価した結果,GreedTokはBPEやUnigramよりも圧縮性能が高く,GreedWMCに匹敵するカバースコアが得られた。 最後に,10億のパラメータを持つ2つのトランスフォーマーベース言語モデルに対する広範な事前トレーニングを行い,BPEとGreedTokの選択をトークン化として比較したところ,GreedTokがデータセットの割合やトレーニングトークンの総数を制御する場合でも,バイトあたりのビット数が低いことがわかった。

関連論文リスト

• Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling [90.86991492288487]
  トークンの制約を評価するのは 違法にコストがかかる LCDは文字列上のグローバル分布を歪め、ローカル情報のみに基づいてトークンをサンプリングすることができる。 我々のアプローチは最先端のベースラインよりも優れていることを示す。
  論文  参考訳（メタデータ） (2025-04-07T18:30:18Z)
• Theoretical Analysis of Byte-Pair Encoding [0.8655526882770742]
  Byte-Pair (BPE) はサブワードトークン化の手法として広く使われている。 BPEは、最適ペア符号化の圧縮効率を最悪の要因に近似することを示した。
  論文  参考訳（メタデータ） (2024-11-13T15:04:02Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。 まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。 我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-06-07T12:07:16Z)
• Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits [55.938644481736446]
  Indexed Minimum Empirical Divergence (IMED)は、マルチアームバンディット問題に対する非常に効果的なアプローチである。 UCBベースのアルゴリズムとトンプソンサンプリングを実証的に上回ることが観察されている。 我々は、LinIMEDアルゴリズムのファミリーと呼ぶIMEDアルゴリズムの新しい線形バージョンを提案する。
  論文  参考訳（メタデータ） (2024-05-24T04:11:58Z)
• DISCO : efficient unsupervised decoding for discrete natural language problems via convex relaxation [1.370633147306388]
  テスト時間デコーディングは,自然言語処理(NLP)問題にまたがるほぼすべての逐次テキスト生成タスクにおいて,ユビキタスなステップである。 我々の主な貢献は、NPハード復号問題に対する連続緩和フレームワークの開発であり、標準1次勾配に基づく効率的なアルゴリズムであるディスコを提案することである。
  論文  参考訳（メタデータ） (2021-07-07T00:40:25Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint [75.85952446237599]
  修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。 最適なデータ依存上界を導出する。 また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
  論文  参考訳（メタデータ） (2020-08-12T15:40:21Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。