論文の概要: Structure learning in polynomial time: Greedy algorithms, Bregman information, and exponential families

• arxiv url: http://arxiv.org/abs/2110.04719v1
• Date: Sun, 10 Oct 2021 06:37:51 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-12 13:42:05.494267
• Title: Structure learning in polynomial time: Greedy algorithms, Bregman information, and exponential families
• Title（参考訳）: 多項式時間における構造学習: greedyアルゴリズム、bregman情報、指数関数系
• Authors: Goutham Rajendran, Bohdan Kivva, Ming Gao, Bryon Aragam
• Abstract要約: DAGを学習するための一般的なグリーディスコアに基づくアルゴリズムについて検討する。 DAGモデルを学習するための最近のアルゴリズム時間アルゴリズムが,このアルゴリズムの特別な例であることを示す。 この観測は、ブレグマン発散と指数族との双対性に基づく新しいスコア関数と最適条件を示唆する。
• 参考スコア（独自算出の注目度）: 12.936601424755944
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Greedy algorithms have long been a workhorse for learning graphical models, and more broadly for learning statistical models with sparse structure. In the context of learning directed acyclic graphs, greedy algorithms are popular despite their worst-case exponential runtime. In practice, however, they are very efficient. We provide new insight into this phenomenon by studying a general greedy score-based algorithm for learning DAGs. Unlike edge-greedy algorithms such as the popular GES and hill-climbing algorithms, our approach is vertex-greedy and requires at most a polynomial number of score evaluations. We then show how recent polynomial-time algorithms for learning DAG models are a special case of this algorithm, thereby illustrating how these order-based algorithms can be rigourously interpreted as score-based algorithms. This observation suggests new score functions and optimality conditions based on the duality between Bregman divergences and exponential families, which we explore in detail. Explicit sample and computational complexity bounds are derived. Finally, we provide extensive experiments suggesting that this algorithm indeed optimizes the score in a variety of settings.
• Abstract（参考訳）: グリーディアルゴリズムは長い間、グラフィカルモデルを学ぶための作業場であり、より広い範囲でスパース構造を持つ統計モデルを学ぶための作業場であった。 学習指向非循環グラフの文脈では、最悪の場合の指数関数的ランタイムにもかかわらず、欲深いアルゴリズムが人気がある。 しかし実際には、それらは非常に効率的である。 DAGを学習するための一般的なグリーディスコアに基づくアルゴリズムを研究することによって、この現象に対する新たな洞察を提供する。 gesやヒルクライミングアルゴリズムのようなエッジグリーディアルゴリズムとは異なり、このアプローチは頂点グリーディであり、スコア評価の多項式数を必要とする。 そこで我々は,最近のDAGモデル学習における多項式時間アルゴリズムが,このアルゴリズムの特別な場合であることを示す。 この観察は、ブレグマンの発散と指数関数族との双対性に基づく新しいスコア関数と最適性条件を示唆する。 明示的なサンプルと計算複雑性境界が導出される。 最後に,このアルゴリズムが様々な設定でスコアを最適化することを示す広範な実験を行った。

関連論文リスト

• A Differentially Private Clustering Algorithm for Well-Clustered Graphs [6.523602840064548]
  このようなグラフに特化された効率的な(epsilon,$delta$)-DPアルゴリズムを提供する。 我々のアルゴリズムは、ほぼバランスの取れたクラスタに対して$k$のグラフを扱う。
  論文  参考訳（メタデータ） (2024-03-21T11:57:16Z)
• Dual Algorithmic Reasoning [9.701208207491879]
  本稿では,基礎となるアルゴリズム問題の双対性を利用してアルゴリズムを学習することを提案する。 アルゴリズム学習における最適化問題の2つの定義を同時に学習することで、より良い学習が可能になることを実証する。 次に、難易度の高い脳血管分類タスクにデプロイすることで、二元アルゴリズム推論の現実的な実用性を検証する。
  論文  参考訳（メタデータ） (2023-02-09T08:46:23Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• A Pragmatic Look at Deep Imitation Learning [0.3626013617212666]
  我々は6つの異なる対向的模倣学習アルゴリズムを再実装する。 広く使われている専門的軌跡データセットで評価する。 GAILは、様々なサンプルサイズにわたって、一貫してよく機能する。
  論文  参考訳（メタデータ） (2021-08-04T06:33:10Z)
• The Bayesian Learning Rule [14.141964578853262]
  我々は、多くの機械学習アルゴリズムが、emphBayesian Learning Ruleと呼ばれる単一のアルゴリズムの特定の例であることを示した。 この規則はベイズ原理から派生したもので、最適化、ディープラーニング、グラフィカルモデルといった分野から幅広いアルゴリズムが得られる。
  論文  参考訳（メタデータ） (2021-07-09T17:28:55Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Evolving Reinforcement Learning Algorithms [186.62294652057062]
  メタラーニング強化学習アルゴリズムの手法を提案する。 学習アルゴリズムはドメインに依存しないため、トレーニング中に見えない新しい環境に一般化することができる。 従来の制御タスク、gridworld型タスク、atariゲームよりも優れた一般化性能を得る2つの学習アルゴリズムに注目した。
  論文  参考訳（メタデータ） (2021-01-08T18:55:07Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Efficient Permutation Discovery in Causal DAGs [9.22466799504763]
  有向非巡回グラフのスパース置換を求めるアルゴリズムを提案する。 We show that our method with depth $w$ run in $O(pw+3) $ time。 また,PC アルゴリズムや GES, GSP などの因果構造学習アルゴリズムと比較し,より短い実行時間で同等の性能が得られることを示す。
  論文  参考訳（メタデータ） (2020-11-06T21:56:41Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。 我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
  論文  参考訳（メタデータ） (2020-08-29T14:58:26Z)
• Run2Survive: A Decision-theoretic Approach to Algorithm Selection based on Survival Analysis [75.64261155172856]
  生存分析(SA)は、自然に検閲されたデータをサポートし、アルゴリズムランタイムの分散モデルを学習するためにそのようなデータを使用する適切な方法を提供する。 我々は、アルゴリズム選択に対する洗練された決定論的アプローチの基礎として、そのようなモデルを活用し、Run2Surviveを疑う。 標準ベンチマークASlibによる広範な実験では、我々のアプローチは競争力が高く、多くの場合、最先端のASアプローチよりも優れていることが示されている。
  論文  参考訳（メタデータ） (2020-07-06T15:20:17Z)

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

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