論文の概要: The Complexity of Bayesian Network Learning: Revisiting the Superstructure
- arxiv url: http://arxiv.org/abs/2602.10253v1
- Date: Tue, 10 Feb 2026 19:58:24 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-02-12 21:44:01.263255
- Title: The Complexity of Bayesian Network Learning: Revisiting the Superstructure
- Title（参考訳）: ベイジアンネットワーク学習の複雑さ--超構造を再考する
- Authors: Robert Ganian, Viktoriia Korchemna,
- Abstract要約: ベイズネットワーク構造学習(BNSL)のパラメータ化複雑性について検討する。
我々は、フィードバックエッジセットのサイズによって、異なる種類のパラメータ化が、固定パラメータのトラクタビリティをもたらすことを示す。
この結果が,ポリツリー学習の密接に関連する問題にどのように拡張できるかを示す。
- 参考スコア（独自算出の注目度）: 19.608963148366907
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We investigate the parameterized complexity of Bayesian Network Structure Learning (BNSL), a classical problem that has received significant attention in empirical but also purely theoretical studies. We follow up on previous works that have analyzed the complexity of BNSL w.r.t. the so-called superstructure of the input. While known results imply that BNSL is unlikely to be fixed-parameter tractable even when parameterized by the size of a vertex cover in the superstructure, here we show that a different kind of parameterization - notably by the size of a feedback edge set - yields fixed-parameter tractability. We proceed by showing that this result can be strengthened to a localized version of the feedback edge set, and provide corresponding lower bounds that complement previous results to provide a complexity classification of BNSL w.r.t. virtually all well-studied graph parameters. We then analyze how the complexity of BNSL depends on the representation of the input. In particular, while the bulk of past theoretical work on the topic assumed the use of the so-called non-zero representation, here we prove that if an additive representation can be used instead then BNSL becomes fixed-parameter tractable even under significantly milder restrictions to the superstructure, notably when parameterized by the treewidth alone. Last but not least, we show how our results can be extended to the closely related problem of Polytree Learning.
- Abstract（参考訳）: 本稿では,ベイズネットワーク構造学習(BNSL)のパラメータ化複雑性について考察する。
我々は、入力のいわゆる超構造であるBNSL w.r.t.の複雑さを解析した以前の研究をフォローアップする。
既知の結果から, BNSL は超構造における頂点被覆の大きさによってパラメータ化される場合でも, 固定パラメータ抽出可能である可能性が示唆されるが, ここでは, フィードバックエッジセットのサイズによって, 異なる種類のパラメータ化が, 固定パラメータ抽出性をもたらすことを示す。
この結果がフィードバックエッジセットの局所化バージョンに強化できることを示し、それに対応する下位境界を提供し、BNSL w.r.t.の複雑性分類を提供する。
次に、BNSLの複雑さが入力の表現に依存するかを分析する。
特に、このトピックに関する過去の理論的研究の多くは、いわゆる非ゼロ表現(non-zero representation)の使用を前提としていたが、ここでは、加法表現を代わりに使用すれば、BNSLは、特に木幅単独でパラメータ化される場合において、超構造に対するより穏やかな制限の下でも、固定パラメータ抽出可能であることを証明する。
最後に、Polytree Learningの密接に関連する問題に対して、我々の結果をどのように拡張できるかを示す。
関連論文リスト
- On the Convergence of Overparameterized Problems: Inherent Properties of the Compositional Structure of Neural Networks [0.0]
本稿では,ニューラルネットワークの構成構造が最適化ランドスケープとトレーニングダイナミクスをどう形成するかを検討する。
グローバル収束特性は、適切な実解析的なコスト関数に対して導出可能であることを示す。
これらの知見が、シグモダルアクティベーションを持つニューラルネットワークにどのように一般化されるかについて議論する。
論文 参考訳（メタデータ） (2025-11-12T23:27:02Z) - Gateways to Tractability for Satisfiability in Pearl's Causal Hierarchy [16.72973567404685]
パールズ・コーサル・ヒエラルキー(PCH)は確率的、介入的、反事実的発言を推論する中心的な枠組みである。
パラメータ化複雑性のレンズを通してこの課題を再考し、トラクタビリティへの最初のゲートウェイを特定する。
論文 参考訳（メタデータ） (2025-11-11T10:45:03Z) - On The Sample Complexity Bounds In Bilevel Reinforcement Learning [49.19950489963245]
二段階強化学習(BRL)は、生成モデルを調整するための強力なフレームワークとして登場した。
連続状態-作用複雑性において$mathcalO(epsilon)$の最初のサンプルを示す。
我々の分析は、既存の$mathcalO(epsilon)$のバウンダリで、複雑さを改善します。
論文 参考訳（メタデータ） (2025-03-22T04:22:04Z) - Polynomially Over-Parameterized Convolutional Neural Networks Contain
Structured Strong Winning Lottery Tickets [4.020829863982153]
十分に小さなネットワークを近似できる構造化ニューラルワークの存在を実証する。
この結果は、Strong Lottery Ticket仮説の周りの最初の部分指数境界を与える。
論文 参考訳（メタデータ） (2023-11-16T12:38:45Z) - Explainable Equivariant Neural Networks for Particle Physics: PELICAN [51.02649432050852]
PELICANは、新しい置換同変であり、ローレンツ不変アグリゲーターネットワークである。
本稿では,タグ付け(分類)とローレンツ発泡トップクォークの再構成(回帰)の両文脈におけるPELICANアルゴリズムアーキテクチャについて述べる。
PELICANの適用範囲を、クォーク開始時とグルーオン開始時とを識別するタスクに拡張し、5種類のジェットを対象とするマルチクラス同定を行う。
論文 参考訳（メタデータ） (2023-07-31T09:08:40Z) - Out-of-distributional risk bounds for neural operators with applications
to the Helmholtz equation [6.296104145657063]
既存のニューラル演算子(NO)は、全ての物理問題に対して必ずしもうまく機能しない。
非線形作用素の波動速度を解にマッピングする実験的な近似を可能にするNOのサブファミリーを提案する。
本実験は, 深度導入の一般化と関連性において, ある種のサプライズを明らかにするものである。
我々は、NOsのサブファミリーのハイパーネットワークバージョンを、前述のフォワード演算子のサロゲートモデルとして提案することで結論付ける。
論文 参考訳（メタデータ） (2023-01-27T03:02:12Z) - Robustifying Algorithms of Learning Latent Trees with Vector Variables [92.18777020401484]
Recursive Grouping (RG) と Chow-Liu Recursive Grouping (CLRG) のサンプル複雑性について述べる。
RG,CLRG,Neighbor Joining (NJ) およびSpectral NJ (SNJ) をトラッピングした内積を用いて強化する。
我々は、潜在木の構造学習において、最初の既知のインスタンス依存の不合理性の結果を導出する。
論文 参考訳（メタデータ） (2021-06-02T01:37:52Z) - Bayesian network structure learning with causal effects in the presence
of latent variables [6.85316573653194]
本稿では,cFCIの制約に基づく部分とスコアに基づく学習を組み合わせた,CCHMと呼ばれるハイブリッド構造学習アルゴリズムについて述べる。
ランダム化されたネットワークとよく知られたネットワークの両方に基づく実験により、CCHMは真の祖先グラフの再構築の観点から最先端の改善を図っている。
論文 参考訳（メタデータ） (2020-05-29T04:42:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。