論文の概要: Tokenization: Hardness and Bicriteria Approximation Algorithms
- arxiv url: http://arxiv.org/abs/2611.15074v1
- Date: Wed, 11 Nov 2026 05:49:07 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-14 01:36:33.057655
- Title: Tokenization: Hardness and Bicriteria Approximation Algorithms
- Title(参考訳): トークン化:ハードネスとビクトリリア近似アルゴリズム
- Abstract要約: バイナリトークン化について検討する:$0,1$以上のバイナリ文字列のコーパスと語彙予算$Kimationを与えられた場合、コーパスを表すのに必要なトークンの総数を表すために、最大$Kimation$を選択する。
0 と $1 のプリミティブシンボルは常に利用可能であり、各ドキュメントは別々に分割されなければならない。
- 参考スコア(独自算出の注目度): 5.593015881081591
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study Binary Tokenization: given a corpus of binary strings over $\{0,1\}$ and a vocabulary budget $K$, select at most $K$ substrings (called vocabulary) to minimize the total number of tokens needed to represent the corpus. The primitive symbols $0$ and $1$ are always available, and each document must be segmented separately. Letting $n$ denote the total corpus length and $M$ for the maximum document length, we prove that, for every fixed $\varepsilon\in(0,1)$, Binary Tokenization problem does not have polynomial-time $n^{1-\varepsilon}$-approximation algorithms unless $\mathsf{P}=\mathsf{NP}$. To complement the hardness result, we give a polynomial-time $(γ,γ)$-bicriteria algorithm, with $γ= \sqrt{M}\log n$: The algorithm outputs a vocabulary of size at most $γK$ with number of tokens at most $γ{\rm OPT}_K$, where ${\rm OPT}_K$ is the optimal number of tokens under the original budget $K$. We also study a storage-budget variant, in which the sum of the selected substrings' lengths is bounded by $B$. For $2\le B<n$, we obtain an $(O(\log n\log B),O(\log n\log B))$-bicriteria approximation algorithm.
- Abstract(参考訳): バイナリトークン化について検討する:${0,1\}$上のバイナリ文字列のコーパスと語彙予算$K$を与えられた場合、コーパスを表すのに必要なトークンの総数を最小限にするために、少なくとも$K$サブストリング(語彙と呼ばれる)を選択する。
プリミティブシンボルの$0$と$1$は常に利用可能であり、各ドキュメントは別々に分割されなければならない。
最大文書長に対して$n$を全コーパス長と$M$とすると、すべての固定された$\varepsilon\in(0,1)$に対して、二項トークン化問題は、$\mathsf{P}=\mathsf{NP}$でない限り多項式時間$n^{1-\varepsilon}$-近似アルゴリズムを持たないことが証明される。
ハードネスの結果を補うために、多項式時間$(γ,γ)$-bicriteriaアルゴリズムを、$γ= \sqrt{M}\log n$: このアルゴリズムは、最大$γK$で、最大$γ{\rm OPT}_K$で、最大$γ{\rm OPT}_K$で、最も多くのトークンを出力する。
また、選択したサブストリングの長さの和を$B$で有界なストレージ予算の変種についても検討する。
2ドルB<n$の場合、$(O(\log n\log B),O(\log n\log B))$-bicriteria近似アルゴリズムを得る。
関連論文リスト
- Fast Approximate $\ell_p$ Chamfer Distance via Lopsided Embeddings and Structured JL [63.08320557041278]
本稿では,Chamfer 距離を $ell_p ノルムで 1 p le 2$ で近似する効率的なアルゴリズムを提案する。
チャムファー距離を保存するのに十分であることを示す。
また, ストリーミング環境における角距離および上下境界について, 追加的な結果を与える。
論文 参考訳(メタデータ) (2026-11-08T05:46:25Z) - A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。
我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
論文 参考訳(メタデータ) (2026-09-09T10:13:43Z) - Faster quantum linear system solver beyond the condition number [50.84794327094274]
線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。
フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
論文 参考訳(メタデータ) (2026-07-08T17:49:40Z) - Quantum Search With Generalized Wildcards [0.4310167974376404]
我々は、コスト$O(sqrtn log n)$の量子アルゴリズムと、ほぼ一致する$Omega(sqrtn)$の低い境界を示す。
以下に示すように、$calQ$が有界サイズセット、連続ブロック、プレフィックス、フルセットのみである場合に、ほぼタイトなバウンダリを表示する。
論文 参考訳(メタデータ) (2025-11-06T18:55:05Z) - Actively Learning Halfspaces without Synthetic Data [34.777547976926456]
我々は、点合成なしでハーフスペースを学習するための効率的なアルゴリズムを設計する。
コーナリーとして、軸整合半空間に対して最適な$O(d + log n)$クエリ決定論的学習器を得る。
我々のアルゴリズムはブール関数を$f$ over $n$要素で学習するより一般的な問題を解く。
論文 参考訳(メタデータ) (2025-09-25T07:39:25Z) - The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳(メタデータ) (2024-10-26T06:21:42Z) - Differentially Private Approximate Pattern Matching [0.0]
我々は差分プライバシー下での$k$-approximateパターンマッチング問題を考察する。
目的は、与えられた文字列のalimate variantsを報告またはカウントすることであり、これは、最大$k$のハミング距離を持つ$S$からパターン$P$までである。
1)$epsilon$-differentially private algorithm with a additive error of $O(epsilon-1log n)$ and no multiplicative error for the existence variant; 2) $epsilon$-differentially private algorithm with an additive error $O(epsilon-1)
論文 参考訳(メタデータ) (2023-11-13T15:53:45Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳(メタデータ) (2023-06-02T18:55:27Z) - Basic quantum subroutines: finding multiple marked elements and summing
numbers [1.1265248232450553]
量子クエリーの最適数$O(sqrtN k)$を用いて、サイズ$N$のリスト内のすべての$k$マーク要素を見つける方法を示す。
論文 参考訳(メタデータ) (2023-02-20T19:11:44Z) - Pseudo Polynomial-Time Top-k Algorithms for d-DNNF Circuits [0.0]
我々は,最大値w.r.$$$の内,$C$のモデルを計算するアルゴリズムを提案する。
また、d-DNNF回路に$C$を変換する擬似時間アルゴリズムを、上位の$k$に値を持つ$C$のモデルによって正確に満たされる。
論文 参考訳(メタデータ) (2022-02-11T23:53:43Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳(メタデータ) (2020-08-24T06:50:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。