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

• arxiv url: http://arxiv.org/abs/2501.06246v1
• Date: Wed, 08 Jan 2025 17:07:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-14 17:24:53.745021
• Title: A partition cover approach to tokenization
• Title（参考訳）: トークン化への分割被覆アプローチ
• Authors: Jia Peng Lim, Davin Choo, Hady W. Lauw,
• Abstract要約: トークン化を最適化の目的として定式化し、単純なカバーの削減によるNPハードであることを示し、グレディアルゴリズムであるGreedTokを提案する。 我々の定式化は、単純な$(1 - 1/e)$-approximationアルゴリズムであるGreedWMCを持つ、よく研究された最大重み付きカバレッジ問題に自然に緩和する。
• 参考スコア（独自算出の注目度）: 27.739820344513088
• License:
• Abstract: Tokenization is the process of encoding strings into tokens from a fixed vocabulary of size $k$ 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, while achieving a comparable objective score as GreedWMC (which could have achieved a higher score due to relaxation).
• Abstract（参考訳）: トークン化(Tokenization)とは、文字列を$kの固定語彙からトークンに符号化するプロセスであり、自然言語処理アプリケーションで広く利用されている。 現在の主要なトークン化アルゴリズムであるByte Pair Encoding (BPE)は、トークン化問題を圧縮問題として定式化し、マージのシーケンスを実行することでそれに取り組む。 本研究では,トークン化を最適化目的として定式化し,頂点被覆からの単純な還元によるNPハードであることが示し,多項式時間グリードアルゴリズムGreedTokを提案する。 我々の定式化は、単純な$(1 - 1/e)$-approximationアルゴリズムであるGreedWMCの重み付き最大カバレッジ問題に自然に緩和する。 実世界のコーパスにおける経験的評価から,GreedTokはBPEよりも優れており,GreedWMCと同等の客観的スコアを達成している(緩和により高いスコアを得た可能性がある)。

関連論文リスト

• 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)
• Reduced Contraction Costs of Corner-Transfer Methods for PEPS [0.0]
  無限に投影された絡み合ったペア状態の収縮を抑えるための最優先計算コストを削減できる近似法を提案する。 計算コストの改善により、大きな結合次元の計算が可能となり、そのポテンシャルを拡大して課題を解決することができる。
  論文  参考訳（メタデータ） (2023-06-14T02:54:12Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。 補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。 各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
  論文  参考訳（メタデータ） (2022-06-30T03:15:23Z)
• 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)

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

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