Fugu-MT 論文翻訳(概要): Tokenisation is NP-Complete

論文の概要: Tokenisation is NP-Complete

arxiv url: http://arxiv.org/abs/2412.15210v1
Date: Thu, 19 Dec 2024 18:59:46 GMT
ステータス: 翻訳完了
システム内更新日: 2024-12-20 13:30:12.099433
Title: Tokenisation is NP-Complete
Title（参考訳）: トークン化はNP-Completeである
Authors: Philip Whittington, Gregor Bachmann, Tiago Pimentel,
Abstract要約: 我々は、データセットを最大$delta$シンボルに圧縮する問題として定義された2種類のトークン化のNP完全性を証明する。
参考スコア（独自算出の注目度）: 30.170045738206312
License:
Abstract: In this work, we prove the NP-completeness of two variants of tokenisation, defined as the problem of compressing a dataset to at most $\delta$ symbols by either finding a vocabulary directly (direct tokenisation), or selecting a sequence of merge operations (bottom-up tokenisation).
Abstract（参考訳）: 本研究では、2種類のトークン化のNP完全性を証明し、データセットを最大$\delta$シンボルに圧縮する問題として定義し、語彙を直接見つけるか(直接トークン化)、またはマージ操作のシーケンスを選択する(ボットアップトークン化)。

関連論文リスト

A partition cover approach to tokenization [27.739820344513088]
トークン化を最適化の目的として定式化し、単純なカバーの削減によるNPハードであることを示し、グレディアルゴリズムであるGreedTokを提案する。我々の定式化は、単純な$(1 - 1/e)$-approximationアルゴリズムであるGreedWMCを持つ、よく研究された最大重み付きカバレッジ問題に自然に緩和する。
論文参考訳（メタデータ） (2025-01-08T17:07:07Z)
Tokenization as Finite-State Transduction [24.19959327497118]
正規言語の全てのトークン化を効率的にエンコードできる有限状態フレームワークを導入する。そのByte-Pairを示します。 Match(BPE)とMaxPiece(WordPiece)がこのフレームワークに適合する。これの応用は、あるパターンにマッチするように言語モデルの出力を制約するガイド付き生成である。
論文参考訳（メタデータ） (2024-10-21T07:10:07Z)
Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文参考訳（メタデータ） (2024-06-07T12:07:16Z)
Compositional Generalization without Trees using Multiset Tagging and Latent Permutations [121.37328648951993]
まず、各入力トークンに複数の出力トークンをタグ付けします。次に、新しいパラメータ化法と置換予測法を用いて、トークンを出力シーケンスに配置する。我々のモデルは、事前訓練されたセq2seqモデルと、現実的なセマンティック解析タスクに関する先行研究より優れている。
論文参考訳（メタデータ） (2023-05-26T14:09:35Z)
Linear-Time Modeling of Linguistic Structure: An Order-Theoretic Perspective [97.57162770792182]
文字列内のトークンのペア間の関係をモデル化するタスクは、自然言語を理解する上で不可欠な部分である。これらの徹底的な比較は避けられ、さらに、トークン間の関係を文字列上の部分順序としてキャストすることで、複雑さを線形に減らすことができる。提案手法は,文字列中の各トークンの実際の数を並列に予測し,それに従ってトークンをソートすることで,文字列内のトークンの総順序を決定する。
論文参考訳（メタデータ） (2023-05-24T11:47:35Z)
N-Gram Nearest Neighbor Machine Translation [101.25243884801183]
本稿では, 自己回帰翻訳(AT)モデルと非自己回帰翻訳(NAT)モデルの両方に適用可能な, モデルに依存しない新しいn$-gram近傍検索手法を提案する。提案手法は,ATモデルおよびNATモデルおよび一般のドメイン適応翻訳タスクにおいて,トークンレベル法を一貫して上回ることを示す。
論文参考訳（メタデータ） (2023-01-30T13:19:19Z)
AWTE-BERT:Attending to Wordpiece Tokenization Explicitly on BERT for Joint Intent Classification and SlotFilling [5.684659127683238]
BERT (Bidirectional Representations from Transformers) は2つのタスクを共同で最適化する。本稿では,ワードピーストークン化後の複数のサブトークン特徴を明示的にモデル化したBERTに基づく新しいジョイントモデルを提案する。実験により,本モデルが意図分類精度,スロットフィリングF1,文レベルの意味的フレーム精度を大幅に向上することを確認した。
論文参考訳（メタデータ） (2022-11-27T13:49:19Z)
Improving Tokenisation by Alternative Treatment of Spaces [7.596737214110957]
空間は常に個々のトークンとして扱われる別のトークン化アプローチを実験する。修正アルゴリズムにより、下流のNLPタスクのパフォーマンスが向上することがわかった。
論文参考訳（メタデータ） (2022-04-08T13:22:30Z)
On the Complexity of Inductively Learning Guarded Rules [7.99255035557979]
学習ガード付き節はNP完全であり,Horn階層上の学習節のP$完全タスクより1ステップ下にあることを示す。大規模データセットの実践的な応用によって、我々は問題の自然な抽出可能な断片を特定できる。
論文参考訳（メタデータ） (2021-10-07T17:07:28Z)
Multi-level Head-wise Match and Aggregation in Transformer for Textual Sequence Matching [87.97265483696613]
そこで本研究では,複数のレベルにおける頭部のマッチング表現を学習することで,Transformerとのシーケンスペアマッチングを新たに提案する。実験の結果,提案手法は複数のタスクにおいて新しい最先端性能を実現することができることがわかった。
論文参考訳（メタデータ） (2020-01-20T20:02:02Z)

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