論文の概要: Best-First Beam Search
- arxiv url: http://arxiv.org/abs/2007.03909v4
- Date: Mon, 30 Aug 2021 16:42:16 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-12 13:22:49.655180
- Title: Best-First Beam Search
- Title（参考訳）: ベストファーストビームサーチ
- Authors: Clara Meister, Tim Vieira, Ryan Cotterell
- Abstract要約: 本研究では,ビームサーチの標準実装を10倍高速に実現可能であることを示す。
ダウンストリーム性能の面でも同様に有益な探索バイアスを有するBest-First Beam Searchのメモリ再生版を提案する。
- 参考スコア（独自算出の注目度）: 78.71330480725668
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Decoding for many NLP tasks requires an effective heuristic algorithm for
approximating exact search since the problem of searching the full output space
is often intractable, or impractical in many settings. The default algorithm
for this job is beam search -- a pruned version of breadth-first search. Quite
surprisingly, beam search often returns better results than exact inference due
to beneficial search bias for NLP tasks. In this work, we show that the
standard implementation of beam search can be made up to 10x faster in
practice. Our method assumes that the scoring function is monotonic in the
sequence length, which allows us to safely prune hypotheses that cannot be in
the final set of hypotheses early on. We devise effective monotonic
approximations to popular nonmonontic scoring functions, including length
normalization and mutual information decoding. Lastly, we propose a
memory-reduced variant of Best-First Beam Search, which has a similar
beneficial search bias in terms of downstream performance, but runs in a
fraction of the time.
- Abstract（参考訳）: 多くのnlpタスクのデコードには、完全出力空間を探索する問題はしばしば難解であり、多くの設定において実用的でないため、厳密な探索を近似する効果的なヒューリスティックアルゴリズムが必要である。
このジョブのデフォルトアルゴリズムはbeam searchである。
驚くべきことに、ビーム検索はnlpタスクの有益な検索バイアスのため、正確な推論よりも良い結果を返すことが多い。
本研究では,ビームサーチの標準実装を10倍高速に実現可能であることを示す。
提案手法では, スコアリング関数はシーケンス長において単調であると仮定し, 仮説の最終セットでは得られない仮説を安全にプルインすることができる。
我々は,長さ正規化や相互情報復号を含む,一般的な非単調スコアリング関数に対する効果的な単調近似を考案する。
最後に,下流部でも同様に有益な検索バイアスを持つが,少ない時間で動作可能な,最上位のビーム探索のメモリ削減型を提案する。
関連論文リスト
- Uncertainty-Guided Optimization on Large Language Model Search Trees [42.71167208999792]
大規模言語モデル(LLM)の復号過程における最大可能性列の探索においては,greedy や beam search などの木探索アルゴリズムが標準となっている。
LLMの遷移確率に関する事前の信念を定義し、各反復において最も有望な経路についての後続の信念を得る。
モンテカルロ木探索のような高価なシミュレーションに基づく非光学的手法とは異なり、我々の手法は信念からのサンプルのみを必要とする。
論文 参考訳（メタデータ） (2024-07-04T14:08:50Z) - Rectangle Search: An Anytime Beam Search (Extended Version) [9.59799149404787]
任意の検索アルゴリズムは、(潜在的に最適でない)解をできるだけ早く見つけようとする。
本稿では,ビーム探索に基づく新しい長方形探索法を提案する。
論文 参考訳（メタデータ） (2023-12-19T19:50:45Z) - A Call for Clarity in Beam Search: How It Works and When It Stops [125.55175954381991]
我々は、このビーム復号化実装の簡単な修正である忍耐係数を導入し、停止基準を一般化し、探索深度に柔軟性を提供する。
実験結果から,この忍耐率の調整は,ニューステキスト要約および多言語対における機械翻訳において,強い事前学習されたモデルの復号性能を向上させることが示された。
論文 参考訳（メタデータ） (2022-04-11T22:03:44Z) - Efficient First-Order Contextual Bandits: Prediction, Allocation, and
Triangular Discrimination [82.52105963476703]
統計的学習、オンライン学習、その他における繰り返しのテーマは、低騒音の問題に対してより速い収束率が可能であることである。
1次保証は統計的およびオンライン学習において比較的よく理解されている。
三角識別と呼ばれる対数損失と情報理論量が一階保証を得る上で基本的な役割を担っていることを示す。
論文 参考訳（メタデータ） (2021-07-05T19:20:34Z) - Determinantal Beam Search [75.84501052642361]
ビームサーチは、ニューラルシーケンスモデルをデコードするためのゴーツー戦略である。
複数のソリューションを要求するユースケースでは、多様あるいは代表的なセットがしばしば望まれる。
ビームサーチを一連の部分決定問題として繰り返し行うことにより、アルゴリズムを多種多様なサブセット選択プロセスに変換することができる。
論文 参考訳（メタデータ） (2021-06-14T13:01:46Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Quantum Search with Prior Knowledge [15.384459603233978]
本稿では,Grover の探索アルゴリズムの新たな一般化を提案する。
提案アルゴリズムは,クエリ数が固定された場合の解を見つけるための最適成功確率を実現する。
論文 参考訳（メタデータ） (2020-09-18T09:50:33Z) - Searching for a Search Method: Benchmarking Search Algorithms for
Generating NLP Adversarial Examples [10.993342896547691]
自然言語処理(NLP)タスクの逆例を生成するために,複数のブラックボックス探索アルゴリズムの動作について検討した。
検索アルゴリズム,検索空間,検索予算の3つの要素を詳細に分析する。
論文 参考訳（メタデータ） (2020-09-09T17:04:42Z) - Progressively Pretrained Dense Corpus Index for Open-Domain Question
Answering [87.32442219333046]
本稿では,段落エンコーダを事前学習するための簡易かつ資源効率の高い手法を提案する。
本手法は,事前学習に7倍の計算資源を使用する既存の高密度検索法より優れている。
論文 参考訳（メタデータ） (2020-04-30T18:09:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。