論文の概要: Efficient Computation of Expectations under Spanning Tree Distributions
- arxiv url: http://arxiv.org/abs/2008.12988v4
- Date: Thu, 25 Mar 2021 10:12:34 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-23 17:22:57.931658
- Title: Efficient Computation of Expectations under Spanning Tree Distributions
- Title（参考訳）: 木の分布にまたがる期待値の効率的な計算
- Authors: Ran Zmigrod, Tim Vieira, Ryan Cotterell
- Abstract要約: 本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。
我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
- 参考スコア（独自算出の注目度）: 67.71280539312536
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We give a general framework for inference in spanning tree models. We propose
unified algorithms for the important cases of first-order expectations and
second-order expectations in edge-factored, non-projective spanning-tree
models. Our algorithms exploit a fundamental connection between gradients and
expectations, which allows us to derive efficient algorithms. These algorithms
are easy to implement with or without automatic differentiation software. We
motivate the development of our framework with several \emph{cautionary tales}
of previous research, which has developed numerous inefficient algorithms for
computing expectations and their gradients. We demonstrate how our framework
efficiently computes several quantities with known algorithms, including the
expected attachment score, entropy, and generalized expectation criteria. As a
bonus, we give algorithms for quantities that are missing in the literature,
including the KL divergence. In all cases, our approach matches the efficiency
of existing algorithms and, in several cases, reduces the runtime complexity by
a factor of the sentence length. We validate the implementation of our
framework through runtime experiments. We find our algorithms are up to 15 and
9 times faster than previous algorithms for computing the Shannon entropy and
the gradient of the generalized expectation objective, respectively.
- Abstract（参考訳）: 我々は、ツリーモデルにまたがる推論の一般的なフレームワークを提供する。
本稿では,エッジファクタ付き非射影スパンニングツリーモデルにおける一階期待と二階期待の重要事例に対する統一アルゴリズムを提案する。
我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
これらのアルゴリズムは自動微分ソフトウェアで容易に実装できる。
我々は,従来の研究のいくつかの「emph{cautionary stories}」を用いて,我々のフレームワークの開発を動機付け,計算期待値とその勾配値に対する非効率なアルゴリズムを多数開発してきた。
提案手法は,アタッチメントスコア,エントロピー,一般化された期待基準など,既知のアルゴリズムで数量を効率的に計算する方法を示す。
ボーナスとして、KLの発散を含む文献に欠けている量のアルゴリズムを与える。
いずれの場合も、我々の手法は既存のアルゴリズムの効率と一致し、いくつかの場合では文長の係数によって実行時の複雑性を減少させる。
ランタイム実験を通じてフレームワークの実装を検証する。
我々のアルゴリズムは、シャノンエントロピーと一般化された期待目標の勾配を計算する前のアルゴリズムの最大15倍と9倍高速であることがわかった。
関連論文リスト
- Approximation Algorithms for Combinatorial Optimization with Predictions [3.7235228254732524]
従来のアルゴリズムの近似保証よりも高い精度で予測を行う。
我々のアルゴリズムは、完璧な予測が得られたときに最適解を生成する。
この種の問題全体に対して最適なアプローチを示すが、個々の問題の特定の構造的特性を利用して改善された境界を求める可能性はある。
論文 参考訳（メタデータ） (2024-11-25T17:31:34Z) - Dual Algorithmic Reasoning [9.701208207491879]
本稿では,基礎となるアルゴリズム問題の双対性を利用してアルゴリズムを学習することを提案する。
アルゴリズム学習における最適化問題の2つの定義を同時に学習することで、より良い学習が可能になることを実証する。
次に、難易度の高い脳血管分類タスクにデプロイすることで、二元アルゴリズム推論の現実的な実用性を検証する。
論文 参考訳（メタデータ） (2023-02-09T08:46:23Z) - Causal Bandits without Graph Learning [28.021500949026766]
我々は,原子間干渉を用いた報酬ノードの親ノード探索のための効率的なアルゴリズムを開発した。
報奨ノードが複数の親を持つ場合にアルゴリズムを拡張します。
論文 参考訳（メタデータ） (2023-01-26T20:27:14Z) - Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
非論理的スケジューリングでは、優先度不明な処理条件でジョブをスケジューリングするためのオンライン戦略を見つけることが課題である。
我々はこのよく研究された問題を、アルゴリズム設計に(信頼できない)予測を統合する、最近人気の高い学習強化された設定で再検討する。
これらの予測には所望の特性があり, 高い性能保証を有するアルゴリズムと同様に, 自然な誤差測定が可能であることを示す。
論文 参考訳（メタデータ） (2022-02-21T13:18:11Z) - Robustification of Online Graph Exploration Methods [59.50307752165016]
我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。
本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-12-10T10:02:31Z) - Practical, Provably-Correct Interactive Learning in the Realizable
Setting: The Power of True Believers [12.09273192079783]
我々は、対話型学習を実現可能な設定で検討し、最適な腕の識別からアクティブな分類に至るまでの問題に対処する一般的な枠組みを開発する。
我々は,最小限の値と対数係数とを一致させる,計算効率のよい新しいアルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-11-09T02:33:36Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。