論文の概要: QWO: Speeding Up Permutation-Based Causal Discovery in LiGAMs
- arxiv url: http://arxiv.org/abs/2410.23155v1
- Date: Wed, 30 Oct 2024 16:10:46 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-31 14:24:07.362021
- Title: QWO: Speeding Up Permutation-Based Causal Discovery in LiGAMs
- Title（参考訳）: QWO: LiGAMにおける置換に基づく因果発見の高速化
- Authors: Mohammad Shahverdikondori, Ehsan Mokhtarian, Negar Kiyavash,
- Abstract要約: QWO は与えられた置換に対して$mathcalGpi$ の計算効率を大幅に向上させる新しい手法である。
QWOは、最先端のBICベースの手法と比較して、$O(n2)$$$(n$は変数の数)のスピードアップがあり、非常にスケーラブルである。
- 参考スコア（独自算出の注目度）: 20.661343069864888
- License:
- Abstract: Causal discovery is essential for understanding relationships among variables of interest in many scientific domains. In this paper, we focus on permutation-based methods for learning causal graphs in Linear Gaussian Acyclic Models (LiGAMs), where the permutation encodes a causal ordering of the variables. Existing methods in this setting are not scalable due to their high computational complexity. These methods are comprised of two main components: (i) constructing a specific DAG, $\mathcal{G}^\pi$, for a given permutation $\pi$, which represents the best structure that can be learned from the available data while adhering to $\pi$, and (ii) searching over the space of permutations (i.e., causal orders) to minimize the number of edges in $\mathcal{G}^\pi$. We introduce QWO, a novel approach that significantly enhances the efficiency of computing $\mathcal{G}^\pi$ for a given permutation $\pi$. QWO has a speed-up of $O(n^2)$ ($n$ is the number of variables) compared to the state-of-the-art BIC-based method, making it highly scalable. We show that our method is theoretically sound and can be integrated into existing search strategies such as GRASP and hill-climbing-based methods to improve their performance.
- Abstract（参考訳）: 因果発見は、多くの科学領域における興味のある変数間の関係を理解するために不可欠である。
本稿では,線形ガウス非巡回モデル (LiGAM) における因果グラフを学習するための置換に基づく手法に着目し,変数の因果順序を符号化する。
この設定の既存のメソッドは、高い計算複雑性のためにスケーラブルではない。
これらの方法は2つの主要な構成要素から構成される。
i)特定のDAGを構成する$\mathcal{G}^\pi$は、与えられた置換に対して$\pi$で、$\pi$に固執しながら利用可能なデータから学習できる最高の構造を表します。
(ii)$\mathcal{G}^\pi$ の辺の数を最小限に抑えるために置換空間(すなわち因果順序)を探索する。
与えられた置換に対する$\mathcal{G}^\pi$ の計算効率を大幅に向上させる新しいアプローチ QWO を導入する。
QWOは、最先端のBICベースの手法と比較して、$O(n^2)$$$(n$は変数の数)のスピードアップがあり、非常にスケーラブルである。
提案手法は理論的に健全であり,GRASPやヒルクライミング法などの既存の探索手法と統合して性能を向上させることができることを示す。
関連論文リスト
- A $Δ$-evaluation function for column permutation problems [0.0]
新しい$Delta$-evaluation法は、連続する性質を持つスパース二元行列上で定義された列置換問題を解くために導入された。
この問題はグラフ理論と工業生産の文脈における様々な$mathcalNP$-hard問題をモデル化する。
提案手法は一般に競争力があり,特に大規模かつ高密度なインスタンスに有用である。
論文 参考訳（メタデータ） (2024-09-07T22:50:25Z) - Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
クラウドソーシングによって動機づけられた我々は、$d$の質問に対する$n$の専門家の回答の正しさを部分的に観察する問題を考える。
本稿では、専門家$i$が疑問に答える確率を含む行列$M$が、行と列の置換までの双等方性であることを仮定する。
我々は,この分類問題に対して最小限のアルゴリズムを最適に構築する。
論文 参考訳（メタデータ） (2024-08-27T18:28:31Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - A Novel and Optimal Spectral Method for Permutation Synchronization [8.517406772939292]
置換同期はコンピュータ科学において重要な問題であり、多くのコンピュータビジョンタスクの重要なステップを構成する。
本稿では,新しい,統計的に最適なスペクトルアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-03-21T17:43:26Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Optimal Gradient Sliding and its Application to Distributed Optimization
Under Similarity [121.83085611327654]
積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。
エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。
提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
論文 参考訳（メタデータ） (2022-05-30T14:28:02Z) - Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and
Costs [45.87981728307819]
異種空間に居住する関連するデータセットを比較して整列する能力は、機械学習においてますます重要な役割を担っている。
グロモフ・ワッサーシュタイン (Gromov-Wasserstein, GW) 形式主義はこの問題に対処するのに役立つ。
論文 参考訳（メタデータ） (2021-06-02T12:50:56Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳（メタデータ） (2020-12-14T18:14:08Z) - Efficient Permutation Discovery in Causal DAGs [9.22466799504763]
有向非巡回グラフのスパース置換を求めるアルゴリズムを提案する。
We show that our method with depth $w$ run in $O(pw+3) $ time。
また,PC アルゴリズムや GES, GSP などの因果構造学習アルゴリズムと比較し,より短い実行時間で同等の性能が得られることを示す。
論文 参考訳（メタデータ） (2020-11-06T21:56:41Z) - LazyIter: A Fast Algorithm for Counting Markov Equivalent DAGs and
Designing Experiments [30.592069659778716]
MECのサイズは、介入を行うことで真の因果グラフを回復するための複雑さの尺度である。
そこで本稿では, 介入結果の可能なMECに対して, 効率的な反復法を提案する。
提案手法は,MECの規模を計算し,実験による設計が最先端の手法であることを示す。
論文 参考訳（メタデータ） (2020-06-17T05:51:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。