論文の概要: An efficient search-and-score algorithm for ancestral graphs using multivariate information scores
- arxiv url: http://arxiv.org/abs/2412.17508v1
- Date: Mon, 23 Dec 2024 12:09:14 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-24 15:57:04.220439
- Title: An efficient search-and-score algorithm for ancestral graphs using multivariate information scores
- Title(参考訳): 多変量情報スコアを用いた祖先グラフの効率的な探索・スコアアルゴリズム
- Authors: Nikita Lagrange, Herve Isambert,
- Abstract要約: 本稿では,2方向のエッジを含む祖先グラフのグリージー検索とスコアアルゴリズムを提案する。
計算効率を向上させるため、提案した2段階のアルゴリズムは、周辺ノードに限定した局所的な情報スコアに依存する。
この計算戦略は、最大2コライダーパスを含むAC接続サブセットからの情報提供に制限されているものの、ベンチマークデータセットの挑戦に対して最先端の因果探索法より優れていることを示す。
- 参考スコア(独自算出の注目度): 0.0
- License:
- Abstract: We propose a greedy search-and-score algorithm for ancestral graphs, which include directed as well as bidirected edges, originating from unobserved latent variables. The normalized likelihood score of ancestral graphs is estimated in terms of multivariate information over relevant ``ac-connected subsets'' of vertices, C, that are connected through collider paths confined to the ancestor set of C. For computational efficiency, the proposed two-step algorithm relies on local information scores limited to the close surrounding vertices of each node (step 1) and edge (step 2). This computational strategy, although restricted to information contributions from ac-connected subsets containing up to two-collider paths, is shown to outperform state-of-the-art causal discovery methods on challenging benchmark datasets.
- Abstract(参考訳): 本稿では,非観測潜伏変数から派生した有向エッジと双方向エッジを含む,祖先グラフのグリージー検索とスコアアルゴリズムを提案する。
祖先グラフの正規化確率スコアは、Cの祖先集合に制限されたコライダーパスを介して接続される頂点の'ac-connected subsets''に関する多変量情報から推定される。
この計算戦略は、最大2コライダーパスを含むAC接続サブセットからの情報提供に制限されているものの、ベンチマークデータセットの挑戦に対して最先端の因果探索法より優れていることを示す。
関連論文リスト
- Hierarchical Topological Ordering with Conditional Independence Test for
Limited Time Series [40.236595154429246]
条件付き独立性テスト(HT-CIT)を用いた階層型トポロジカル順序付けアルゴリズムを提案する。
HT-CITアルゴリズムは、刈り取るべきエッジの数を大幅に削減する。
合成および実世界のデータセットから得られた実験結果は,提案したHT-CITアルゴリズムの優位性を示している。
論文 参考訳(メタデータ) (2023-08-16T05:01:33Z) - One-step Bipartite Graph Cut: A Normalized Formulation and Its
Application to Scalable Subspace Clustering [56.81492360414741]
両部グラフの1ステップ正規化カットを、特に線形時間複雑性で実施する方法を示す。
本稿では、まず、正規化制約付き一段階二分グラフカット基準を特徴付けるとともに、そのトレース問題に対する等価性を理論的に証明する。
このカット基準を、適応アンカー学習、二部グラフ学習、一段階正規化二部グラフ分割を同時にモデル化するスケーラブルなサブスペースクラスタリングアプローチに拡張する。
論文 参考訳(メタデータ) (2023-05-12T11:27:20Z) - ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate
Nearest Neighbor Search Algorithms [5.478671305092084]
本稿では,ParlayANNについて紹介する。ParlayANNは決定論的および並列グラフに基づく近接探索アルゴリズムのライブラリである。
我々は、数十億のデータセットにスケールする4つの最先端グラフベースのANNSアルゴリズムに対して、新しい並列実装を開発する。
論文 参考訳(メタデータ) (2023-05-07T19:28:23Z) - Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。
第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
論文 参考訳(メタデータ) (2023-02-02T08:33:36Z) - Learning Heuristics for the Maximum Clique Enumeration Problem Using Low
Dimensional Representations [0.0]
本稿では,最大列挙問題の傾きを低減するために,入力グラフのプルーニング処理に学習フレームワークを用いる。
本手法の性能評価において,異なる頂点表現を用いることが果たす役割について検討する。
分類過程において局所的なグラフ特徴を用いることで,特徴の除去過程と組み合わせることで,より正確な結果が得られることが観察された。
論文 参考訳(メタデータ) (2022-10-30T22:04:32Z) - Interpolation-based Correlation Reduction Network for Semi-Supervised
Graph Learning [49.94816548023729]
補間型相関低減ネットワーク(ICRN)と呼ばれる新しいグラフコントラスト学習手法を提案する。
提案手法では,決定境界のマージンを大きくすることで,潜在特徴の識別能力を向上させる。
この2つの設定を組み合わせることで、豊富なラベル付きノードと稀に価値あるラベル付きノードから豊富な監視情報を抽出し、離散表現学習を行う。
論文 参考訳(メタデータ) (2022-06-06T14:26:34Z) - Reinforcement Learning Based Query Vertex Ordering Model for Subgraph
Matching [58.39970828272366]
グラフマッチングアルゴリズムは、クエリグラフの埋め込みをデータグラフGに列挙する。
マッチング順序は、これらのバックトラックに基づくサブグラフマッチングアルゴリズムの時間効率において重要な役割を果たす。
本稿では,Reinforcement Learning (RL) と Graph Neural Networks (GNN) 技術を適用して,グラフマッチングアルゴリズムの高品質なマッチング順序を生成する。
論文 参考訳(メタデータ) (2022-01-25T00:10:03Z) - Hierarchical Clustering: $O(1)$-Approximation for Well-Clustered Graphs [3.2901541059183432]
階層クラスタリングのための2時間近似アルゴリズムを提案する。
本研究の意義は,合成データセットと実世界のデータセットの両方における経験的分析によって実証された。
論文 参考訳(メタデータ) (2021-12-16T17:52:04Z) - Riemannian classification of EEG signals with missing values [67.90148548467762]
本稿では脳波の分類に欠落したデータを扱うための2つの方法を提案する。
第1のアプローチでは、インプットされたデータと$k$-nearestの隣人アルゴリズムとの共分散を推定し、第2のアプローチでは、期待最大化アルゴリズム内で観測データの可能性を活用することにより、観測データに依存する。
その結果, 提案手法は観測データに基づく分類よりも優れており, 欠落したデータ比が増大しても高い精度を維持することができることがわかった。
論文 参考訳(メタデータ) (2021-10-19T14:24:50Z) - Spatial-Spectral Clustering with Anchor Graph for Hyperspectral Image [88.60285937702304]
本稿では、HSIデータクラスタリングのための空間スペクトルクラスタリングとアンカーグラフ(SSCAG)という新しい非監視アプローチを提案する。
提案されたSSCAGは最先端のアプローチと競合する。
論文 参考訳(メタデータ) (2021-04-24T08:09:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。