論文の概要: Structural perspective on constraint-based learning of Markov networks
- arxiv url: http://arxiv.org/abs/2403.08562v1
- Date: Wed, 13 Mar 2024 14:14:47 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-14 14:11:07.209089
- Title: Structural perspective on constraint-based learning of Markov networks
- Title（参考訳）: マルコフネットワークの制約に基づく学習に関する構造的視点
- Authors: Tuukka Korhonen, Fedor V. Fomin, Pekka Parviainen
- Abstract要約: すべての$n$-vertexグラフは、最大$nkappa$テストによって、条件付きサイズのセットを最大$kappa$で学習できることを証明します。
正の面において、有界木幅のすべてのグラフは、条件付きサイズの集合を少なくとも2kappa$で持つ多くのテストによって学習できることを証明している。
- 参考スコア（独自算出の注目度）: 11.388331913007248
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Markov networks are probabilistic graphical models that employ undirected
graphs to depict conditional independence relationships among variables. Our
focus lies in constraint-based structure learning, which entails learning the
undirected graph from data through the execution of conditional independence
tests. We establish theoretical limits concerning two critical aspects of
constraint-based learning of Markov networks: the number of tests and the sizes
of the conditioning sets. These bounds uncover an exciting interplay between
the structural properties of the graph and the amount of tests required to
learn a Markov network. The starting point of our work is that the graph
parameter maximum pairwise connectivity, $\kappa$, that is, the maximum number
of vertex-disjoint paths connecting a pair of vertices in the graph, is
responsible for the sizes of independence tests required to learn the graph. On
one hand, we show that at least one test with the size of the conditioning set
at least $\kappa$ is always necessary. On the other hand, we prove that any
graph can be learned by performing tests of size at most $\kappa$. This
completely resolves the question of the minimum size of conditioning sets
required to learn the graph. When it comes to the number of tests, our upper
bound on the sizes of conditioning sets implies that every $n$-vertex graph can
be learned by at most $n^{\kappa}$ tests with conditioning sets of sizes at
most $\kappa$. We show that for any upper bound $q$ on the sizes of the
conditioning sets, there exist graphs with $O(n q)$ vertices that require at
least $n^{\Omega(\kappa)}$ tests to learn. This lower bound holds even when the
treewidth and the maximum degree of the graph are at most $\kappa+2$. On the
positive side, we prove that every graph of bounded treewidth can be learned by
a polynomial number of tests with conditioning sets of sizes at most $2\kappa$.
- Abstract（参考訳）: マルコフネットワーク(Markov network)は、変数間の条件付き独立関係を記述するために無向グラフを使用する確率的グラフィカルモデルである。
我々の焦点は制約に基づく構造学習であり、条件付き独立テストの実行を通じてデータから非方向グラフを学習する。
マルコフネットワークにおける制約に基づく学習の2つの重要な側面、すなわちテストの数と条件セットのサイズに関する理論的限界を確立する。
これらの境界は、グラフの構造的性質とマルコフネットワークを学ぶのに必要なテストの量の間のエキサイティングな相互作用を明らかにする。
我々の研究の出発点は、グラフパラメータの最大対接続である$\kappa$、すなわち、グラフ内の頂点のペアを接続する頂点非結合パスの最大数は、グラフを学ぶのに必要な独立性テストのサイズに責任があるということである。
一方、条件セットのサイズが少なくとも$\kappa$の少なくとも1つのテストは、常に必要であることを示す。
一方、任意のグラフは、最大$\kappa$で大きさのテストを実行することで学習可能であることを証明している。
これは、グラフを学習するのに必要となる条件セットの最小サイズに関する問題を完全に解決する。
テストの数に関して言えば、条件セットのサイズの上限は、すべての$n$-vertexグラフが少なくとも$n^{\kappa}$テストによって学習できることを意味します。
条件集合のサイズ上の任意の上限$q$に対して、学習するために少なくとも$n^{\Omega(\kappa)}$テストを必要とする$O(n q)$頂点を持つグラフが存在することを示す。
この下界は、木幅とグラフの最大度が少なくとも$\kappa+2$である場合でも成り立つ。
正の面において、有界木幅のすべてのグラフは、条件付きサイズの集合を少なくとも2\kappa$とする多項式数で学習できることを証明している。
関連論文リスト
- Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。
我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。
平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
論文 参考訳（メタデータ） (2023-04-17T10:38:08Z) - A Unified Characterization of Private Learnability via Graph Theory [18.364498500697596]
純粋かつ近似微分プライベート(DP)学習性を特徴付ける統一的なフレームワークを提供する。
DP学習性の特徴を特徴づけるグラフ理論次元を同定する。
また、独立な興味を持つかもしれない矛盾グラフの性質も明らかにする。
論文 参考訳（メタデータ） (2023-04-08T12:25:08Z) - Three iterations of $(d-1)$-WL test distinguish non isometric clouds of
$d$-dimensional points [58.9648095506484]
Wesfeiler--Lehman テストが完全距離グラフで表されるユークリッド点の雲に対して完備であるときの研究を行う。
我々の主な結果は、$(d-1)$-dimensional WL テストが$d$-dimensional Euclidean 空間の点雲に対して完備であり、任意の$dge 2$ に対して完備であり、テストサフィスを3回だけ繰り返すことである。
論文 参考訳（メタデータ） (2023-03-22T18:23:24Z) - Probing Graph Representations [77.7361299039905]
グラフ表現でキャプチャされた意味のある情報の量を定量化するために、探索フレームワークを使用します。
本研究は, グラフモデルにおける帰納的バイアスを理解するための探索の可能性を示すものである。
グラフベースモデルを評価する上で有用な診断ツールとして,探索を提唱する。
論文 参考訳（メタデータ） (2023-03-07T14:58:18Z) - Graph Construction using Principal Axis Trees for Simple Graph
Convolution [0.6554326244334866]
本稿では,教師なし情報と教師なし情報を用いて隣接行列$A$を構成するグラフ構築方式を提案する。
2つのよく知られたグラフニューラルネットワーク(GNN)上で、このグラフ構築方式を検証した。
論文 参考訳（メタデータ） (2023-02-22T12:02:23Z) - Learning Universe Model for Partial Matching Networks over Multiple
Graphs [78.85255014094223]
2つまたは複数のグラフの部分的マッチングのための宇宙マッチングスキームを開発する。
不整合及び不整合検出のための微妙なロジックを、明確にモデル化することができる。
これは、2グラフマッチング、複数グラフマッチング、オンラインマッチング、混合グラフマッチングを同時に扱うことができる最初のディープラーニングネットワークである。
論文 参考訳（メタデータ） (2022-10-19T08:34:00Z) - Learning on the Edge: Online Learning with Stochastic Feedback Graphs [12.83118601099289]
有向フィードバックグラフが帯域幅を持つ拡張について検討する。
グラフの各ラウンドにおいて、グラフの各エッジは、それぞれのエッジに対して異なる確率で実現されるか、実現されないかのいずれかである。
我々は、独立性の重み付けされたバージョンと弱い支配数に依存する、より効率的なアルゴリズムを導出する。
論文 参考訳（メタデータ） (2022-10-09T11:21:08Z) - Learning quantum graph states with product measurements [22.463154358632472]
我々は、未知の$n$-qubit量子グラフ状態の同一コピーを製品測定で学習する問題を考察する。
このようなグラフ状態の複数の同一コピー上で製品計測を用いて学習する明示的なアルゴリズムを詳述する。
論文 参考訳（メタデータ） (2022-05-13T02:55:21Z) - Bringing Your Own View: Graph Contrastive Learning without Prefabricated
Data Augmentations [94.41860307845812]
Self-supervisionは最近、グラフ学習の新しいフロンティアに力を入れている。
GraphCLは、グラフデータ拡張のアドホックな手作業による選択によって反映されたプレハブ付きプリファブリックを使用する。
グラフ生成器のパラメータ空間における学習可能な連続前処理へと拡張した。
我々は、情報最小化(InfoMin)と情報ボトルネック(InfoBN)の2つの原則を利用して、学習した事前情報を規則化する。
論文 参考訳（メタデータ） (2022-01-04T15:49:18Z) - Partition and Code: learning how to compress graphs [50.29024357495154]
まず、分割アルゴリズムがグラフを基本構造に分解し、これらを確率分布を学習する小さな辞書の要素にマッピングし、エントロピーエンコーダが表現をビットに変換する。
提案アルゴリズムは,非パラメトリックおよびパラメトリックグラフ圧縮器の異なるファミリーに対して,多種多様な実世界のネットワーク上で定量的に評価し,大幅な性能向上を実現している。
論文 参考訳（メタデータ） (2021-07-05T11:41:16Z) - Learning Bayesian Networks Under Sparsity Constraints: A Parameterized
Complexity Analysis [7.99536002595393]
本稿では,ネットワーク上あるいはそのモラル化されたグラフ上に制約を加える際に,最適なベイズネットワークの構造を学習する問題について検討する。
モラル化されたグラフに少なくとも$k$のエッジを持つ最適ネットワークを学習すると、おそらく$f(k)cdot |I|O(1)$-timeアルゴリズムが存在しない。
論文 参考訳（メタデータ） (2020-04-30T12:31:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。