論文の概要: Fast Causal Discovery by Approximate Kernel-based Generalized Score Functions with Linear Computational Complexity

• arxiv url: http://arxiv.org/abs/2412.17717v1
• Date: Mon, 23 Dec 2024 16:51:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-24 16:00:38.486268
• Title: Fast Causal Discovery by Approximate Kernel-based Generalized Score Functions with Linear Computational Complexity
• Title（参考訳）: 線形計算複雑性を持つ近似カーネルに基づく一般化スコア関数による高速因果発見
• Authors: Yixin Ren, Haocheng Zhang, Yewei Xia, Hao Zhang, Jihong Guan, Shuigeng Zhou,
• Abstract要約: 我々は,$mathcalO(n)$時間と空間複素量を持つカーネルベース一般化スコア関数を提案する。 提案手法は計算コストを大幅に削減するだけでなく,特に大規模データセットの精度も向上する。
• 参考スコア（独自算出の注目度）: 29.444911198185206
• License:
• Abstract: Score-based causal discovery methods can effectively identify causal relationships by evaluating candidate graphs and selecting the one with the highest score. One popular class of scores is kernel-based generalized score functions, which can adapt to a wide range of scenarios and work well in practice because they circumvent assumptions about causal mechanisms and data distributions. Despite these advantages, kernel-based generalized score functions pose serious computational challenges in time and space, with a time complexity of $\mathcal{O}(n^3)$ and a memory complexity of $\mathcal{O}(n^2)$, where $n$ is the sample size. In this paper, we propose an approximate kernel-based generalized score function with $\mathcal{O}(n)$ time and space complexities by using low-rank technique and designing a set of rules to handle the complex composite matrix operations required to calculate the score, as well as developing sampling algorithms for different data types to benefit the handling of diverse data types efficiently. Our extensive causal discovery experiments on both synthetic and real-world data demonstrate that compared to the state-of-the-art method, our method can not only significantly reduce computational costs, but also achieve comparable accuracy, especially for large datasets.
• Abstract（参考訳）: スコアに基づく因果探索手法は、候補グラフを評価し、最も高いスコアの因果関係を選択することにより、因果関係を効果的に識別することができる。 カーネルベースの一般化スコア関数は、因果メカニズムやデータ分布に関する仮定を回避できるため、幅広いシナリオに適応し、実際はうまく機能する。 これらの利点にもかかわらず、カーネルベースの一般化スコア関数は時間と空間において深刻な計算上の問題を引き起こし、時間複雑性は$\mathcal{O}(n^3)$、メモリ複雑性は$\mathcal{O}(n^2)$である。 本稿では、低ランクな手法を用いて、スコアを計算するのに必要な複雑な複合行列演算を扱うためのルールセットを設計し、様々なデータ型のサンプリングアルゴリズムを開発し、多様なデータ型を効率的に扱えるようにすることによる、カーネルベースの一般化スコア関数である$\mathcal{O}(n)$時間と空間の複雑さを近似した一般化スコア関数を提案する。 人工データと実世界のデータの両方に対する大規模な因果探索実験により、最先端の手法と比較して計算コストを著しく削減できるだけでなく、特に大規模データセットにおいて同等の精度を達成できることが実証された。

関連論文リスト

• Optimal Kernel Choice for Score Function-based Causal Discovery [92.65034439889872]
  本稿では,データに最も適合する最適なカーネルを自動的に選択する,一般化スコア関数内のカーネル選択手法を提案する。 合成データと実世界のベンチマークの両方で実験を行い,提案手法がカーネル選択法より優れていることを示す。
  論文  参考訳（メタデータ） (2024-07-14T09:32:20Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• CORE: Common Random Reconstruction for Distributed Optimization with Provable Low Communication Complexity [110.50364486645852]
  コミュニケーションの複雑さは、トレーニングをスピードアップし、マシン番号をスケールアップする上で、大きなボトルネックになっています。 本稿では,機械間で送信される情報を圧縮するための共通Om REOmを提案する。
  論文  参考訳（メタデータ） (2023-09-23T08:45:27Z)
• Efficient distributed representations with linear-time attention scores normalization [3.8673630752805437]
  本研究では,有界ノルムを持つ埋め込みベクトルに対するアテンションスコア正規化定数の線形時間近似を提案する。 推定公式の精度は、競合するカーネルメソッドを桁違いに上回る。 提案アルゴリズムは高度に解釈可能であり,任意の埋め込み問題に容易に適応できる。
  論文  参考訳（メタデータ） (2023-03-30T15:48:26Z)
• Inducing Gaussian Process Networks [80.40892394020797]
  本稿では,特徴空間と誘導点を同時に学習するシンプルなフレームワークであるGaussian Process Network (IGN)を提案する。 特に誘導点は特徴空間で直接学習され、複雑な構造化領域のシームレスな表現を可能にする。 実世界のデータセットに対する実験結果から,IGNは最先端の手法よりも大幅に進歩していることを示す。
  論文  参考訳（メタデータ） (2022-04-21T05:27:09Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。 提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
  論文  参考訳（メタデータ） (2020-12-29T04:08:38Z)
• Learning Compositional Sparse Gaussian Processes with a Shrinkage Prior [26.52863547394537]
  本稿では,カーネル選択のスパーシティをホースシュープリアーで処理することにより,カーネル構成を学習するための新しい確率論的アルゴリズムを提案する。 本モデルは,計算時間を大幅に削減した時系列特性をキャプチャし,実世界のデータセット上での競合回帰性能を有する。
  論文  参考訳（メタデータ） (2020-12-21T13:41:15Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  強化学習のコアにおける探索・探索トレードオフについて検討する。 特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。 私たちの後悔の限界はエピソードの数とは無関係です。
  論文  参考訳（メタデータ） (2020-11-09T18:32:22Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。