論文の概要: Linear-Time WordPiece Tokenization

• arxiv url: http://arxiv.org/abs/2012.15524v1
• Date: Thu, 31 Dec 2020 10:01:29 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-17 17:15:48.706183
• Title: Linear-Time WordPiece Tokenization
• Title（参考訳）: 線形時間WordPieceトークン化
• Authors: Xinying Song, Alex Salcianu, Yang Song, Dave Dopson, Denny Zhou
• Abstract要約: MaxMatchは、WordPieceトークン化のための長期マッチファーストトークン化戦略です。 MaxMatchとWordPieceトークン化のための新しい線形時間アルゴリズムであるLinMaxMatchを提案する。
• 参考スコア（独自算出の注目度）: 14.008336286659514
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: WordPiece tokenization is a subword-based tokenization schema adopted by BERT: it segments the input text via a longest-match-first tokenization strategy, known as Maximum Matching or MaxMatch. To the best of our knowledge, all published MaxMatch algorithms are quadratic (or higher). In this paper, we propose LinMaxMatch, a novel linear-time algorithm for MaxMatch and WordPiece tokenization. Inspired by the Aho-Corasick algorithm, we introduce additional linkages on top of the trie built from the vocabulary, allowing smart transitions when the trie matching cannot continue. Experimental results show that our algorithm is 3x faster on average than two production systems by HuggingFace and TensorFlow Text. Regarding long-tail inputs, our algorithm is 4.5x faster at the 95 percentile. This work has immediate practical value (reducing inference latency, saving compute resources, etc.) and is of theoretical interest by providing an optimal complexity solution to the decades-old MaxMatch problem.
• Abstract（参考訳）: WordPieceトークン化(WordPieceトークン化)は、BERTで採用されているサブワードベースのトークン化スキーマである。 私たちの知る限り、公開されたmaxmatchアルゴリズムはすべて二次的(あるいはそれ以上)である。 本稿では,maxmatch と wordpiece のトークン化のための線形時間アルゴリズム linmaxmatch を提案する。 Aho-Corasickアルゴリズムにインスパイアされ、語彙から構築された三重項の上に追加のリンクを導入し、三重項マッチングが継続できないときのスマートな遷移を可能にする。 実験の結果,HuggingFaceとTensorFlow Textの2つのプロダクションシステムよりも平均3倍高速であることがわかった。 ロングテール入力に関しては、アルゴリズムは95%で4.5倍高速です。 この作業には即時的な実用価値(推論遅延の低減、計算リソースの節約など)があります。 そして、数十年前のMaxMatch問題に対して最適な複雑性ソリューションを提供することによって理論的に興味深い。

関連論文リスト

• Fast decision tree learning solves hard coding-theoretic problems [7.420043502440765]
  我々は、Ehrenfeucht と Haussler のアルゴリズムの改善により、$k$-NCP に対して$O(log n)$-approximation アルゴリズムが得られることを示す。 これは、$k$-NCPのアルゴリズムを設計するための新しい道、あるいはEhrenfeucht と Haussler のアルゴリズムの最適性を確立するための道と解釈できる。
  論文  参考訳（メタデータ） (2024-09-19T21:40:57Z)
• Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages [104.90415092306219]
  4つの形式は、ツリー随伴文法(TAG)、線形指数文法(LIG)、プッシュダウン随伴オートマトン(PAA)、組込みプッシュダウンオートマトン(EPDA)に相当する。 我々は,文字列の導出量(文字列のすべてのオートマトン重み)と全導出量(全ての導出量重み)を計算するための新しいアルゴリズムを設計する。 EPDA の場合、我々のアルゴリズムは、$mathcalO(|Gamma|2)$ および $ の因子による Alonso et al. (2001) のアルゴリズムよりも空間効率と時間効率が良い。
  論文  参考訳（メタデータ） (2023-10-23T18:26:00Z)
• SpecTr: Fast Speculative Decoding via Optimal Transport [30.18181671899423]
  このアルゴリズムはデコーディングの高速化を図り、デコードされた出力に品質劣化がないことを保証します。 提案手法は,最先端の大規模言語モデルに対して,標準的なベンチマーク上での投機的復号化よりもさらに1.37倍の高速化である2.13Xのウォールクロック高速化を実現することを実験的に実証した。
  論文  参考訳（メタデータ） (2023-10-23T17:47:34Z)
• Breaking 3-Factor Approximation for Correlation Clustering in Polylogarithmic Rounds [0.23633885460047763]
  相関クラスタリング問題に対する並列アルゴリズムについて検討する。 目標は、エンティティをクラスタに分割し、ラベルとの相違を最小限にすることである。 現在、全ての効率的な並列アルゴリズムは、近似比が少なくとも3である。 3 より優れた近似比を実現するための最初の多元対数アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-07-13T12:32:49Z)
• Evaluating Various Tokenizers for Arabic Text Classification [4.110108749051656]
  アラビア語に対する3つの新しいトークン化アルゴリズムを導入し、教師なし評価を用いて他の3つのベースラインと比較する。 実験の結果,このようなトークン化アルゴリズムの性能は,データセットのサイズ,タスクの種類,データセットに存在する形態素量に依存することがわかった。
  論文  参考訳（メタデータ） (2021-06-14T16:05:58Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。 我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
  論文  参考訳（メタデータ） (2020-08-29T14:58:26Z)
• Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint [75.85952446237599]
  修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。 最適なデータ依存上界を導出する。 また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
  論文  参考訳（メタデータ） (2020-08-12T15:40:21Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)

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

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