論文の概要: Exact discovery is polynomial for sparse causal Bayesian networks

• arxiv url: http://arxiv.org/abs/2406.15012v1
• Date: Fri, 21 Jun 2024 09:41:30 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-24 14:03:36.844870
• Title: Exact discovery is polynomial for sparse causal Bayesian networks
• Title（参考訳）: 厳密な発見はスパース因果ベイズネットワークの多項式である
• Authors: Felix L. Rios, Giusi Moffa, Jack Kuipers,
• Abstract要約: 本稿では,ベイジアンネットワークの特性を利用して探索空間を創出し,計算コストを下げる方法について述べる。 そして、我々のアプローチは低い密度で最先端の手法に勝る。 これらの結果は、より大規模でスペーサーなネットワークにおいて、より高速な正確な因果発見の道を開く。
• 参考スコア（独自算出の注目度）: 1.5293427903448027
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Causal Bayesian networks are widely used tools for summarising the dependencies between variables and elucidating their putative causal relationships. Learning networks from data is computationally hard in general. The current state-of-the-art approaches for exact causal discovery are integer linear programming over the underlying space of directed acyclic graphs, dynamic programming and shortest-path searches over the space of topological orders, and constraint programming combining both. For dynamic programming over orders, the computational complexity is known to be exponential base 2 in the number of variables in the network. We demonstrate how to use properties of Bayesian networks to prune the search space and lower the computational cost, while still guaranteeing exact discovery. When including new path-search and divide-and-conquer criteria, we prove optimality in quadratic time for matchings, and polynomial time for any network class with logarithmically-bound largest connected components. In simulation studies we observe the polynomial dependence for sparse networks and that, beyond some critical value, the logarithm of the base grows with the network density. Our approach then out-competes the state-of-the-art at lower densities. These results therefore pave the way for faster exact causal discovery in larger and sparser networks.
• Abstract（参考訳）: 因果ベイズネットワークは変数間の依存関係を要約し、それらの因果関係を解明するために広く利用されている。 データからネットワークを学習することは一般的には困難である。 正確な因果探索に対する現在の最先端のアプローチは、有向非巡回グラフの基礎空間上の整数線形計画法、トポロジカル順序空間上の動的計画法と最短パス探索法、両方を組み合わせた制約プログラミングである。 順序による動的プログラミングでは、計算複雑性はネットワーク内の変数数で指数基底2であることが知られている。 ベイジアンネットワークの特性を用いて探索空間を創り出し、正確な発見を保証しながら計算コストを下げる方法について実証する。 新たなパス探索と分数分解基準を含む場合、マッチングの2次時間と、対数的に有界な最大の連結成分を持つ任意のネットワーククラスに対する多項式時間で最適であることが証明される。 シミュレーション研究において、スパースネットワークの多項式依存を観察し、いくつかの臨界値を超えると、基底の対数がネットワーク密度とともに増加することを観察する。 そして、我々のアプローチは低い密度で最先端の手法に勝る。 これらの結果は、より大規模でスペーサーなネットワークにおいて、より高速な因果発見の道を開いた。

関連論文リスト

• Coordinated Multi-Neighborhood Learning on a Directed Acyclic Graph [6.727984016678534]
  因果非巡回グラフ(DAG)の構造を学習することは、機械学習や人工知能の多くの分野で有用である。 強い、しばしば制限的な仮定なしに優れた経験的、理論的結果を得ることは困難である。 本論文では,複数のユーザ特定ターゲットノードの周囲の局所構造を推定する制約に基づく新しい手法を提案する。
  論文  参考訳（メタデータ） (2024-05-24T08:49:43Z)
• Memorization with neural nets: going beyond the worst case [5.662924503089369]
  実際には、ディープニューラルネットワークはトレーニングデータを簡単に補間できることが多い。 しかし、実世界のデータについては、暗記能力によって提案されるよりもネットワークサイズが小さいような良質な構造の存在を直感的に期待する。 2つのクラスを持つ固定有限データセットを与えられた場合、高い確率で3層ニューラルネットワークを時間内に補間する単純なランダム化アルゴリズムを導入する。
  論文  参考訳（メタデータ） (2023-09-30T10:06:05Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• Predictions Based on Pixel Data: Insights from PDEs and Finite Differences [0.0]
  本稿では,各観測が行列である時間列の近似を扱う。 比較的小さなネットワークでは、直線法に基づいて、PDEの数値的な離散化のクラスを正確に表現できることが示される。 我々のネットワークアーキテクチャは、典型的に時系列の近似に採用されているものから着想を得ている。
  論文  参考訳（メタデータ） (2023-05-01T08:54:45Z)
• Automatic Relation-aware Graph Network Proliferation [182.30735195376792]
  GNNを効率的に検索するためのARGNP(Automatic Relation-Aware Graph Network Proliferation)を提案する。 これらの操作は階層的なノード/リレーショナル情報を抽出し、グラフ上のメッセージパッシングのための異方的ガイダンスを提供する。 4つのグラフ学習タスクのための6つのデータセットの実験により、我々の手法によって生成されたGNNは、現在最先端の手作りおよび検索に基づくGNNよりも優れていることが示された。
  論文  参考訳（メタデータ） (2022-05-31T10:38:04Z)
• Deep Architecture Connectivity Matters for Its Convergence: A Fine-Grained Analysis [94.64007376939735]
  我々は、勾配降下訓練におけるディープニューラルネットワーク(DNN)の収束に対する接続パターンの影響を理論的に特徴づける。 接続パターンの単純なフィルタリングによって、評価対象のモデルの数を削減できることが示される。
  論文  参考訳（メタデータ） (2022-05-11T17:43:54Z)
• The Separation Capacity of Random Neural Networks [78.25060223808936]
  標準ガウス重みと一様分布バイアスを持つ十分に大きな2層ReLUネットワークは、この問題を高い確率で解くことができることを示す。 我々は、相互複雑性という新しい概念の観点から、データの関連構造を定量化する。
  論文  参考訳（メタデータ） (2021-07-31T10:25:26Z)
• Berrut Approximated Coded Computing: Straggler Resistance Beyond Polynomial Computing [34.69732430310801]
  本稿では,ストラグラー効果に対処する代替手法として,Berrut Approximated Coded Computing (BACC)を提案する。 BACCは計算複雑性が低い数値的に安定であることが証明されている。 特に、BACCは、サーバのクラスタ上でディープニューラルネットワークをトレーニングするために使用される。
  論文  参考訳（メタデータ） (2020-09-17T14:23:38Z)
• Understanding Boolean Function Learnability on Deep Neural Networks [0.0]
  計算学習理論 (Computational learning theory) は、多くの式が時間内に学習可能であることを述べる。 本稿では, ニューラルネットワークを用いて, 実際にそのような公式を学習する方法について, 未研究の課題に対処する。
  論文  参考訳（メタデータ） (2020-09-13T03:49:20Z)
• Learning Connectivity of Neural Networks from a Topological Perspective [80.35103711638548]
  本稿では,ネットワークを解析のための完全なグラフに表現するためのトポロジ的視点を提案する。 接続の規模を反映したエッジに学習可能なパラメータを割り当てることにより、学習プロセスを異なる方法で行うことができる。 この学習プロセスは既存のネットワークと互換性があり、より大きな検索空間と異なるタスクへの適応性を持っている。
  論文  参考訳（メタデータ） (2020-08-19T04:53:31Z)
• Connecting the Dots: Multivariate Time Series Forecasting with Graph Neural Networks [91.65637773358347]
  多変量時系列データに特化して設計された汎用グラフニューラルネットワークフレームワークを提案する。 グラフ学習モジュールを用いて,変数間の一方向関係を自動的に抽出する。 提案手法は,4つのベンチマークデータセットのうち3つにおいて,最先端のベースライン手法よりも優れている。
  論文  参考訳（メタデータ） (2020-05-24T04:02:18Z)

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

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