論文の概要: AMP Chain Graphs: Minimal Separators and Structure Learning Algorithms
- arxiv url: http://arxiv.org/abs/2002.10870v2
- Date: Tue, 4 Aug 2020 20:38:42 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-29 02:45:31.895842
- Title: AMP Chain Graphs: Minimal Separators and Structure Learning Algorithms
- Title（参考訳）: amp連鎖グラフ:最小分離子と構造学習アルゴリズム
- Authors: Mohammad Ali Javidian, Marco Valtorta, Pooyan Jamshidi
- Abstract要約: アンダーソン・マディガン・パールマン連鎖グラフ(AMP CG)における最小セパレータの探索問題に対処する。
我々は,PCライクなアルゴリズム (Pena, 2012) が,変数が与えられる順序に依存するという意味で,順序に依存していることを示す。
我々は,この順序依存の一部を除去するPCライクなアルゴリズムのいくつかの改良を提案する。
- 参考スコア（独自算出の注目度）: 2.3333090554192615
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We address the problem of finding a minimal separator in an
Andersson-Madigan-Perlman chain graph (AMP CG), namely, finding a set Z of
nodes that separates a given nonadjacent pair of nodes such that no proper
subset of Z separates that pair. We analyze several versions of this problem
and offer polynomial-time algorithms for each. These include finding a minimal
separator from a restricted set of nodes, finding a minimal separator for two
given disjoint sets, and testing whether a given separator is minimal. To
address the problem of learning the structure of AMP CGs from data, we show
that the PC-like algorithm (Pena, 2012) is order-dependent, in the sense that
the output can depend on the order in which the variables are given. We propose
several modifications of the PC-like algorithm that remove part or all of this
order-dependence. We also extend the decomposition-based approach for learning
Bayesian networks (BNs) proposed by (Xie et al., 2006) to learn AMP CGs, which
include BNs as a special case, under the faithfulness assumption. We prove the
correctness of our extension using the minimal separator results. Using
standard benchmarks and synthetically generated models and data in our
experiments demonstrate the competitive performance of our decomposition-based
method, called LCD-AMP, in comparison with the (modified versions of) PC-like
algorithm. The LCD-AMP algorithm usually outperforms the PC-like algorithm, and
our modifications of the PC-like algorithm learn structures that are more
similar to the underlying ground truth graphs than the original PC-like
algorithm, especially in high-dimensional settings. In particular, we
empirically show that the results of both algorithms are more accurate and
stabler when the sample size is reasonably large and the underlying graph is
sparse.
- Abstract（参考訳）: 我々は,andersson-madigan-perlman chain graph (amp cg) における最小分離子の発見,すなわち,z の固有部分集合がその対を分離しないような,与えられた非隣接ノード対を分離するノードの集合 z を見つける問題に対処する。
この問題のいくつかのバージョンを分析し,それぞれに多項式時間アルゴリズムを提供する。
これには、制限されたノードの集合から最小セパレータを見つけること、与えられた2つの分離集合に対する最小セパレータを見つけること、与えられたセパレータが最小であるかどうかをテストすることが含まれる。
データからAMP CGの構造を学習する問題に対処するため、PCライクなアルゴリズム(Pena, 2012)は、変数が与えられる順序に依存するという意味で、順序に依存していることを示す。
この順序依存の一部を除去するPCライクなアルゴリズムのいくつかの改良を提案する。
また、(Xie et al., 2006) が提案したベイズネットワーク(BN) を学習するための分解に基づくアプローチを拡張し、特に BN を含む AMP CG を忠実性の仮定の下で学習する。
最小分離結果を用いて拡張の正確性を証明する。
実験では,標準ベンチマークと合成モデルおよびデータを用いて,PCライクなアルゴリズムと比較し,LCD-AMPと呼ばれる分解に基づく手法の競合性能を実証した。
LCD-AMPアルゴリズムは、通常PCライクなアルゴリズムよりも優れており、PCライクなアルゴリズムの修正は、特に高次元設定において、元のPCライクなアルゴリズムよりも基礎となる真理グラフに近い構造を学ぶ。
特に、サンプルサイズが合理的に大きく、基礎となるグラフがスパースである場合、両方のアルゴリズムの結果がより正確で安定であることを示す。
関連論文リスト
- Scaling LLM Inference with Optimized Sample Compute Allocation [56.524278187351925]
我々は、異なる推論構成の最適な混合を見つけるアルゴリズムであるOSCAを提案する。
実験の結果,学習した混合アロケーションでは,最高の単一構成よりも精度がよいことがわかった。
OSCAはシングルターンタスク以外のエージェント処理にも有効であることが示されており、デフォルト設定よりも3倍少ない計算でSWE-Benchの精度が向上している。
論文 参考訳（メタデータ） (2024-10-29T19:17:55Z) - Optimal estimation of Gaussian (poly)trees [25.02920605955238]
分布学習(KL距離)と構造学習(正確な回復)の両問題を考察する。
最初のアプローチはChow-Liuアルゴリズムに基づいており、最適な木構造分布を効率的に学習する。
第2のアプローチは、制約に基づく構造学習のための条件付き独立試験器として部分相関を用いたポリツリーに対するPCアルゴリズムの修正である。
論文 参考訳（メタデータ） (2024-02-09T12:58:36Z) - An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。
このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。
本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-30T15:57:14Z) - Linearized Wasserstein dimensionality reduction with approximation
guarantees [65.16758672591365]
LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。
我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。
また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
論文 参考訳（メタデータ） (2023-02-14T22:12:16Z) - Parallel Sampling for Efficient High-dimensional Bayesian Network
Structure Learning [6.85316573653194]
本稿では,CPS(Candidate Parent Sets)上で並列サンプリングを行う近似アルゴリズムについて述べる。
修正アルゴリズムはParallel Sampling MINOBS (PS-MINOBS) と呼ばれ、各変数のCPSをサンプリングすることでグラフを構成する。
論文 参考訳（メタデータ） (2022-02-19T22:35:59Z) - SLOSH: Set LOcality Sensitive Hashing via Sliced-Wasserstein Embeddings [18.916058638077274]
本稿では,ANN (Non-parametric and data-independent learning from set-structured data using almost near neighbor (ANN) solutions。
Sliced-Wasserstein set embedding as a computerly efficient "set-2-vector" mechanism that possible downstream ANN。
本稿では,SLOSH (Set-LOcality Sensitive Hashing) と呼ばれるアルゴリズムの有効性を,様々なデータセットで示す。
論文 参考訳（メタデータ） (2021-12-11T00:10:05Z) - Scaling Structured Inference with Randomization [64.18063627155128]
本稿では、構造化されたモデルを数万の潜在状態に拡張するためにランダム化された動的プログラミング(RDP)のファミリを提案する。
我々の手法は古典的DPベースの推論に広く適用できる。
また、自動微分とも互換性があり、ニューラルネットワークとシームレスに統合できる。
論文 参考訳（メタデータ） (2021-12-07T11:26:41Z) - Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via
GDPA Linearization [59.87663954467815]
アルゴリズムの展開は、モデルベースのアルゴリズムの各イテレーションをニューラルネットワーク層として実装することにより、解釈可能で類似のニューラルネットワークアーキテクチャを生成する。
本稿では、Gershgorin disc perfect alignment (GDPA)と呼ばれる最近の線形代数定理を利用して、二進グラフの半定値プログラミング緩和(SDR)のためのプロジェクションフリーアルゴリズムをアンロールする。
実験結果から,我々の未学習ネットワークは純粋モデルベースグラフ分類器よりも優れ,純粋データ駆動ネットワークに匹敵する性能を示したが,パラメータははるかに少なかった。
論文 参考訳（メタデータ） (2021-09-10T07:01:15Z) - Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and
Hierarchical Spatial Clustering [6.4805900740861]
HDBSCAN$*$のための私達のアルゴリズムの仕事そしてスペースを減らすために十分分離の新しい概念を導入します。
我々のアルゴリズムは理論的に効率的であることを示す: 彼らは逐次対応の作業(操作数)と多対数深さ(並列時間)を持っている。
48コアマシンを用いた大規模実世界および合成データセットの実験により、我々の最速のアルゴリズムは11.13-55.89x、既存の並列アルゴリズムを少なくとも桁違いに上回った。
論文 参考訳（メタデータ） (2021-04-02T16:05:00Z) - Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature
Selection [138.97647716793333]
再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。
提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
論文 参考訳（メタデータ） (2020-12-29T04:08:38Z) - Learning LWF Chain Graphs: an Order Independent Algorithm [2.3333090554192615]
忠実性仮定の下で連鎖グラフの構造を求めるPCライクなアルゴリズムを提案する。
我々は,PCライクなアルゴリズムが順序に依存することを証明し,その出力は変数が与えられる順序に依存する。
そこで本研究では,この順序に依存する部分あるいは全部を除去するPCライクなアルゴリズムの2つの修正を提案する。
論文 参考訳（メタデータ） (2020-05-27T01:05:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。