論文の概要: Identifying Mixtures of Bayesian Network Distributions
- arxiv url: http://arxiv.org/abs/2112.11602v1
- Date: Wed, 22 Dec 2021 01:04:50 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-23 22:30:22.017132
- Title: Identifying Mixtures of Bayesian Network Distributions
- Title（参考訳）: ベイズネットワーク分布の混合物の同定
- Authors: Spencer L. Gordon, Bijan Mazaheri, Yuval Rabani, Leonard J. Schulman
- Abstract要約: そのようなモデルの有限混合は、より大きなグラフ上のBNDの変数への射影である。
非常に特殊なケースは、空のグラフ(英語版)という文学への長年の関心である。
長年の問題は、製品分布のそれぞれを特定するために、$k$の製品分布の混合分布が一緒に分布していることにある。
- 参考スコア（独自算出の注目度）: 4.893896929103367
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A Bayesian Network is a directed acyclic graph (DAG) on a set of $n$ random
variables (identified with the vertices); a Bayesian Network Distribution (BND)
is a probability distribution on the rv's that is Markovian on the graph. A
finite mixture of such models is the projection on these variables of a BND on
the larger graph which has an additional "hidden" (or "latent") random variable
$U$, ranging in $\{1,\ldots,k\}$, and a directed edge from $U$ to every other
vertex.
Models of this type are fundamental to research in Causal Inference, where
$U$ models a confounding effect. One extremely special case has been of
longstanding interest in the theory literature: the empty graph. Such a
distribution is simply a mixture of $k$ product distributions. A longstanding
problem has been, given the joint distribution of a mixture of $k$ product
distributions, to identify each of the product distributions, and their mixture
weights. Our results are:
(1) We improve the sample complexity (and runtime) for identifying mixtures
of $k$ product distributions from $\exp(O(k^2))$ to $\exp(O(k \log k))$. This
is almost best possible in view of a known $\exp(\Omega(k))$ lower bound.
(2) We give the first algorithm for the case of non-empty graphs. The
complexity for a graph of maximum degree $\Delta$ is $\exp(O(k(\Delta^2 + \log
k)))$.
(The above complexities are approximate and suppress dependence on secondary
parameters.)
- Abstract（参考訳）: ベイズネットワーク(英: Bayesian Network、略称: BND)は、有向非巡回グラフ(DAG)であり、そのグラフ上のマルコビアンであるrv上の確率分布である。
そのようなモデルの有限混合は、より大きなグラフ上の bnd のこれらの変数上の射影であり、追加の "hidden" (または "latent") 確率変数 $u$ を持ち、$\{1,\ldots,k\}$ と、$u$ から他のすべての頂点への有向辺を持つ。
このタイプのモデルは因果推論において基礎的な研究であり、$U$は相反する効果をモデル化する。
非常に特殊な例として、理論文献に長年関心を寄せてきた「空グラフ」がある。
そのような分布は単に$k$の積分布の混合である。
長年の問題は、製品分布のそれぞれとその混合重量を識別するために、$k$の製品分布の混合分布が一緒に分布していることにある。
1)$k$の製品分布の混合を$\exp(O(k^2))$から$\exp(O(k \log k))$に識別するためのサンプル複雑性(およびランタイム)を改善します。
これは、既知の $\exp(\Omega(k))$ lower bound の観点からは最もよい。
(2) 空でないグラフの場合の最初のアルゴリズムを与える。
最大次数$\Delta$のグラフの複雑性は$\exp(O(k(\Delta^2 + \log k))$である。
(上記の複雑さは近似的であり、二次パラメータへの依存を抑える。)
関連論文リスト
- Generation is better than Modification: Combating High Class Homophily Variance in Graph Anomaly Detection [51.11833609431406]
異なるクラス間のホモフィリー分布の差は、ホモフィリックグラフやヘテロフィリックグラフよりも著しく大きい。
我々は、この現象を定量的に記述した、クラスホモフィリーバリアンスと呼ばれる新しい計量を導入する。
その影響を軽減するために,ホモフィリーエッジ生成グラフニューラルネットワーク(HedGe)と呼ばれる新しいGNNモデルを提案する。
論文 参考訳（メタデータ） (2024-03-15T14:26:53Z) - Information-Theoretic Thresholds for Planted Dense Cycles [52.076657911275525]
本研究では,社会科学や生物科学においてユビキタスな小世界ネットワークのランダムグラフモデルについて検討する。
植え込み高密度サイクルの検出と回復の両面において、情報理論の閾値を$n$, $tau$、エッジワイド信号対雑音比$lambda$で特徴づける。
論文 参考訳（メタデータ） (2024-02-01T03:39:01Z) - Understanding Heterophily for Graph Neural Networks [42.640057865981156]
グラフニューラルネットワーク(GNN)における異方性パターンの影響に関する理論的理解について述べる。
分離性ゲインは、$l$の近隣分布の正規化距離によって決定されることを示す。
合成データと実世界のデータの両方の実験により、我々の理論の有効性が検証された。
論文 参考訳（メタデータ） (2024-01-17T11:01:28Z) - Inferences on Mixing Probabilities and Ranking in Mixed-Membership
Models [5.992878098797828]
ネットワークデータは、経済や健康ネットワークを含む多くのビッグデータアプリケーションで広く利用されている。
本稿では,Degree-Corrected Mixed Membership (DCMM)モデルを用いてネットワークをモデル化する。
我々は、$boldsymbolpi_i(k)$sに対して、メンバシップ混合確率と他の関連する集団量の分布と信頼区間を得られるような、新しい有限サンプル展開を導出する。
論文 参考訳（メタデータ） (2023-08-29T02:35:45Z) - Causal Bandits for Linear Structural Equation Models [58.2875460517691]
本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。
グラフの構造は知られており、ノードは$N$である。
頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-26T16:21:31Z) - Diffusion models as plug-and-play priors [98.16404662526101]
我々は、事前の$p(mathbfx)$と補助的な制約である$c(mathbfx,mathbfy)$からなるモデルにおいて、高次元データ$mathbfx$を推論する問題を考える。
拡散モデルの構造は,異なるノイズ量に富んだ定性デノナイジングネットワークを通じて,微分を反復することで近似推論を行うことができる。
論文 参考訳（メタデータ） (2022-06-17T21:11:36Z) - Combinatorial Causal Bandits [25.012065471684025]
因果的包帯において、学習エージェントは、各ラウンドで最大$K$変数を選択して介入し、ターゲット変数$Y$に対する期待される後悔を最小限にすることを目的としている。
因果モデルの簡潔なパラメトリック表現を用いた二元一般化線形モデル(BGLM)の文脈下で検討する。
マルコフ BGLM に対するアルゴリズム BGLM-OFU を最大推定法に基づいて提案し,O(sqrtTlog T)$ regret, ここでは$T$ が時間地平線となることを示す。
論文 参考訳（メタデータ） (2022-06-04T14:14:58Z) - On the Generative Utility of Cyclic Conditionals [103.1624347008042]
2つの条件付きモデル$p(x|z)$を用いて、共同分布$p(x,z)$をモデル化できるかどうか、また、どのようにしてサイクルを形成するかを検討する。
本稿では,周期条件生成モデリングのためのCyGenフレームワークを提案する。
論文 参考訳（メタデータ） (2021-06-30T10:23:45Z) - Generalized Independent Noise Condition for Estimating Latent Variable
Causal Graphs [39.24319581164022]
潜在変数グラフを推定するための一般化独立雑音(GIN)条件を提案する。
GINは潜伏変数の探索と因果方向を含む因果構造の同定に有効であることを示す。
論文 参考訳（メタデータ） (2020-10-10T06:11:06Z) - Fairness constraints can help exact inference in structured prediction [37.76221231305701]
直交連結グラフ$G$と2進ラベルの真のベクトルを持つ生成モデルについて検討する。
フェアネスとモデル性能の間の既知のトレードオフとは対照的に、フェアネス制約の追加は正確なリカバリの確率を向上させる。
論文 参考訳（メタデータ） (2020-07-01T04:11:29Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。