論文の概要: Entropy and the Kullback-Leibler Divergence for Bayesian Networks: Computational Complexity and Efficient Implementation

• arxiv url: http://arxiv.org/abs/2312.01520v3
• Date: Mon, 15 Jan 2024 09:03:19 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-17 21:17:19.643856
• Title: Entropy and the Kullback-Leibler Divergence for Bayesian Networks: Computational Complexity and Efficient Implementation
• Title（参考訳）: ベイジアンネットワークのエントロピーとKulback-Leibler分散:計算複雑性と効率的な実装
• Authors: Marco Scutari
• Abstract要約: 我々は、最も一般的な分布仮定の下で、シャノンのエントロピーと BN に対するクルバック・リーバーの発散を計算する方法を示す。 ガウス BN に対して、KL の計算複雑性を立方体から二次体に還元できることが示されている。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Bayesian networks (BNs) are a foundational model in machine learning and causal inference. Their graphical structure can handle high-dimensional problems, divide them into a sparse collection of smaller ones, underlies Judea Pearl's causality, and determines their explainability and interpretability. Despite their popularity, there are almost no resources in the literature on how to compute Shannon's entropy and the Kullback-Leibler (KL) divergence for BNs under their most common distributional assumptions. In this paper, we provide computationally efficient algorithms for both by leveraging BNs' graphical structure, and we illustrate them with a complete set of numerical examples. In the process, we show it is possible to reduce the computational complexity of KL from cubic to quadratic for Gaussian BNs.
• Abstract（参考訳）: ベイズネットワーク(BN)は、機械学習と因果推論の基礎モデルである。 それらのグラフィカルな構造は、高次元の問題に対処し、それらを小さな問題に分割し、ジュデア・パールの因果性を理解し、それらの説明可能性と解釈可能性を決定する。 その人気にもかかわらず、シャノンのエントロピーの計算方法や、BNのKL(Kulback-Leibler)の発散を最も一般的な分布仮定で計算する方法に関する文献にはほとんど資源がない。 本稿では,bnsのグラフィカルな構造を活かし,計算効率の良いアルゴリズムを両立し,それらの数値例の完全な集合を提示する。 この過程において,KL の計算複雑性をガウスBN の立方体から二次体に還元できることを示す。

関連論文リスト

• Convergence Guarantees for the DeepWalk Embedding on Block Models [9.898607871253775]
  ブロックモデル(SBM)から得られたグラフ上でDeepWalkアルゴリズムの使い方を示す。 単純化されているにもかかわらず、SBMは大きなグラフ上のアルゴリズムを解析するための古典的なモデルであることが証明されている。
  論文  参考訳（メタデータ） (2024-10-26T18:35:11Z)
• LSEnet: Lorentz Structural Entropy Neural Network for Deep Graph Clustering [59.89626219328127]
  グラフクラスタリングは機械学習の基本的な問題である。 近年、ディープラーニング手法は最先端の成果を達成しているが、事前に定義されたクラスタ番号なしでは動作できない。 本稿では,グラフ情報理論の新たな視点からこの問題に対処することを提案する。
  論文  参考訳（メタデータ） (2024-05-20T05:46:41Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• Approximating a RUM from Distributions on k-Slates [88.32814292632675]
  与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。 我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
  論文  参考訳（メタデータ） (2023-05-22T17:43:34Z)
• Reconstructing Bayesian Networks on a Quantum Annealer [0.0]
  O'Gormanらは、このタスクを符号化するアルゴリズムを提案しているが、実験的な評価は提供していない。 i) O'GormanのアルゴリズムをPythonで実装し,(ii)大小のBNSL問題に対処するDeput et imperaアプローチを提案する。 その結果、小サイズのBNSLインスタンスに対するO'Gormanの定式化の有効性と、O'Gormanのアルゴリズムの直接実行におけるDeput et imperaアプローチの優位性を示した。
  論文  参考訳（メタデータ） (2022-04-07T15:53:05Z)
• Partial Counterfactual Identification from Observational and Experimental Data [83.798237968683]
  観測データと実験データの任意の組み合わせから最適境界を近似する有効なモンテカルロアルゴリズムを開発した。 我々のアルゴリズムは、合成および実世界のデータセットに基づいて広範囲に検証されている。
  論文  参考訳（メタデータ） (2021-10-12T02:21:30Z)
• The Separation Capacity of Random Neural Networks [78.25060223808936]
  標準ガウス重みと一様分布バイアスを持つ十分に大きな2層ReLUネットワークは、この問題を高い確率で解くことができることを示す。 我々は、相互複雑性という新しい概念の観点から、データの関連構造を定量化する。
  論文  参考訳（メタデータ） (2021-07-31T10:25:26Z)
• Improved Acyclicity Reasoning for Bayesian Network Structure Learning with Constraint Programming [0.0]
  離散データからベイズネットワーク(BNSL)の構造を学習することはNPハードタスクであることが知られている。 本研究では,可能なクラスタカットのサブセットを発見するための新しい時間アルゴリズムを提案する。 最適ではないにもかかわらず、性能は桁違いに向上することを示す。 結果として得られる解法は、BNSL問題に対する最先端の解法である GOBNILP と好意的に比較できる。
  論文  参考訳（メタデータ） (2021-06-23T09:46:11Z)
• Efficient Inference via Universal LSH Kernel [35.22983601434134]
  本稿では,単純なハッシュ計算と集約で推論手順を近似できる数列の簡潔な集合である,数学的に証明可能なRepresenter Sketchを提案する。 Representer Sketchは、カーネル文学から人気のあるRepresenter Theoremの上に構築されている。 本研究では,Representer Sketchによるストレージ要件の最大114倍,複雑性の最大59倍を精度の低下なく達成できることを示す。
  論文  参考訳（メタデータ） (2021-06-21T22:06:32Z)
• Fast Hierarchical Games for Image Explanations [78.16853337149871]
  本稿では,シェープリー係数の階層的拡張に基づく画像分類のモデル非依存な説明法を提案する。 他のShapleyベースの説明手法とは異なり、h-Shapはスケーラブルで近似を必要とせずに計算できる。 本手法は,合成データセット,医用画像シナリオ,一般コンピュータビジョン問題において,一般的なシャプリーベースおよび非サプリーベース手法と比較した。
  論文  参考訳（メタデータ） (2021-04-13T13:11:02Z)
• Simple heuristics for efficient parallel tensor contraction and quantum circuit simulation [1.4416132811087747]
  本稿では,確率モデルを用いたテンソルネットワークの縮約のための並列アルゴリズムを提案する。 結果のアルゴリズムをランダム量子回路のシミュレーションに適用する。
  論文  参考訳（メタデータ） (2020-04-22T23:00:42Z)

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

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