論文の概要: MPE inference using an Incremental Build-Infer-Approximate Paradigm

• arxiv url: http://arxiv.org/abs/2206.01954v1
• Date: Sat, 4 Jun 2022 09:37:44 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-07 16:27:41.527894
• Title: MPE inference using an Incremental Build-Infer-Approximate Paradigm
• Title（参考訳）: 増分ビルドインファー近似パラダイムを用いたMPE推論
• Authors: Shivani Bathla and Vinita Vasudevan
• Abstract要約: ベイジアンネットワークで最も可能性の高い説明(MPE)の具体的な推論はNP完全であることが知られている。 インクリメンタルなビルド・インファー・アポキシメート・フレームワークをベースとした,MPEの近似推定アルゴリズムを提案する。 私たちのソリューションの精度は、ベンチマークの大部分でブランチとバウンド検索に匹敵し、競合する実行時間を持つ。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Exact inference of the most probable explanation (MPE) in Bayesian networks is known to be NP-complete. In this paper, we propose an algorithm for approximate MPE inference that is based on the incremental build-infer-approximate (IBIA) framework. We use this framework to obtain an ordered set of partitions of the Bayesian network and the corresponding max-calibrated clique trees. We show that the maximum belief in the last partition gives an estimate of the probability of the MPE assignment. We propose an iterative algorithm for decoding, in which the subset of variables for which an assignment is obtained is guaranteed to increase in every iteration. There are no issues of convergence, and we do not perform a search for solutions. Even though it is a single shot algorithm, we obtain valid assignments in 100 out of the 117 benchmarks used for testing. The accuracy of our solution is comparable to a branch and bound search in majority of the benchmarks, with competitive run times.
• Abstract（参考訳）: ベイジアンネットワークで最も可能性の高い説明(MPE)の具体的な推論はNP完全であることが知られている。 本稿では,インクリメンタル・ビルド・インファー近似(ibia)フレームワークに基づく近似mpe推定アルゴリズムを提案する。 この枠組みを用いてベイジアンネットワークと対応するmax-calibrated cliqueツリーの順序付きパーティション集合を得る。 我々は,最終分割における最大信念が,MPE割り当ての確率を推定することを示した。 本稿では,代入が得られた変数のサブセットが反復毎に増加することを保証した復号のための反復アルゴリズムを提案する。 収束の問題はなく、解決策の探索も行いません。 単発アルゴリズムであるにもかかわらず、テストに使用される117のベンチマークのうち100のうち、有効な割り当てを得る。 私たちのソリューションの精度は、ベンチマークの大部分でブランチとバウンド検索に匹敵し、競合する実行時間を持つ。

関連論文リスト

• IBIA: An Incremental Build-Infer-Approximate Framework for Approximate Inference of Partition Function [0.0]
  分割関数の厳密な計算は難解であることが知られている。 近似推論のための新しいインクリメンタルなビルドインファー近似フレームワークを提案する。 このフレームワークはパーティション関数の効率的な計算に利用できることを示す。
  論文  参考訳（メタデータ） (2023-04-13T09:40:23Z)
• Selection of the Most Probable Best [2.1095005405219815]
  予測値ランキングと選択(R&S)問題では,すべてのk解のシミュレーション出力が,分布によって不確実性をモデル化可能な共通パラメータに依存する。 我々は、最も確率の高い最適解 (MPB) を、分布に関して最適である確率が最も大きい解と定義する。 最適化条件における未知の手段をその推定値に置き換えるアルゴリズムを考案し,シミュレーション予算が増加するにつれて,アルゴリズムのサンプリング比が条件を満たすことを証明した。
  論文  参考訳（メタデータ） (2022-07-15T15:27:27Z)
• Efficient One Sided Kolmogorov Approximation [7.657378889055477]
  本研究の主な応用は, 時系列並列スケジュールにおいて, 欠落する確率を推定することである。 これらの確率の正確な計算はNPハードであるため,本論文で記述したアルゴリズムを用いて近似を求める。
  論文  参考訳（メタデータ） (2022-07-14T10:03:02Z)
• Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization [63.8557841188626]
  期待されている改善(EI)アルゴリズムは、不確実性の下で最適化するための最も一般的な戦略の1つである。 本稿では,GP予測平均を通した標準既存値を持つEIの変種を提案する。 我々のアルゴリズムは収束し、$mathcal O(gamma_TsqrtT)$の累積後悔境界を達成することを示す。
  論文  参考訳（メタデータ） (2022-03-15T13:17:53Z)
• Parallel Sampling for Efficient High-dimensional Bayesian Network Structure Learning [6.85316573653194]
  本稿では,CPS(Candidate Parent Sets)上で並列サンプリングを行う近似アルゴリズムについて述べる。 修正アルゴリズムはParallel Sampling MINOBS (PS-MINOBS) と呼ばれ、各変数のCPSをサンプリングすることでグラフを構成する。
  論文  参考訳（メタデータ） (2022-02-19T22:35:59Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。 合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
  論文  参考訳（メタデータ） (2022-02-09T06:05:05Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
  多くの現実世界では、T関数の評価の予算を考えると、高価なブラックボックス関数 f の性質を推測したい。 本稿では,アルゴリズムの出力に対して相互情報を最大化するクエリを逐次選択する手法InfoBAXを提案する。 これらの問題に対してInfoBAXは、元のアルゴリズムで要求されるより500倍少ないクエリをfに使用する。
  論文  参考訳（メタデータ） (2021-04-19T17:22:11Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。 我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
  論文  参考訳（メタデータ） (2020-08-29T14:58:26Z)
• Best-First Beam Search [78.71330480725668]
  本研究では,ビームサーチの標準実装を10倍高速に実現可能であることを示す。 ダウンストリーム性能の面でも同様に有益な探索バイアスを有するBest-First Beam Searchのメモリ再生版を提案する。
  論文  参考訳（メタデータ） (2020-07-08T05:56:01Z)
• Certifying clusters from sum-of-norms clustering [13.747619681451875]
  本稿では,近似解から正しいクラスタ割り当てを同定し,証明するクラスタリングテストを提案する。 提案手法では, クラスタ割り当てが, 十分に多くの繰り返しを経て, 原始二重経路追従アルゴリズムによって保証されることが保証されていることを示す。
  論文  参考訳（メタデータ） (2020-06-19T20:26:26Z)

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

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