論文の概要: Causal Structure Recovery of Linear Dynamical Systems: An FFT based Approach

• arxiv url: http://arxiv.org/abs/2309.02571v1
• Date: Tue, 5 Sep 2023 20:45:34 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-07 17:38:10.602792
• Title: Causal Structure Recovery of Linear Dynamical Systems: An FFT based Approach
• Title（参考訳）: 線形力学系の因果構造回復:FFTに基づくアプローチ
• Authors: Mishfad Shaikh Veedu, James Melbourne, Murti V. Salapaka
• Abstract要約: 時系列観測による動的因果関係の同定は,静的シナリオと比較して計算コストが高いことを示す。 因果構造を復元するために,O(Tn3N2)$の複雑さを低減した手法を報告する。 さらに、LTIである相互作用を持つシステムでは、周波数領域アプローチでdo-calculus 機械が実現可能であることを示す。
• 参考スコア（独自算出の注目度）: 4.9493039356268875
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Learning causal effects from data is a fundamental and well-studied problem across science, especially when the cause-effect relationship is static in nature. However, causal effect is less explored when there are dynamical dependencies, i.e., when dependencies exist between entities across time. Identifying dynamic causal effects from time-series observations is computationally expensive when compared to the static scenario. We demonstrate that the computational complexity of recovering the causation structure for the vector auto-regressive (VAR) model is $O(Tn^3N^2)$, where $n$ is the number of nodes, $T$ is the number of samples, and $N$ is the largest time-lag in the dependency between entities. We report a method, with a reduced complexity of $O(Tn^3 \log N)$, to recover the causation structure to obtain frequency-domain (FD) representations of time-series. Since FFT accumulates all the time dependencies on every frequency, causal inference can be performed efficiently by considering the state variables as random variables at any given frequency. We additionally show that, for systems with interactions that are LTI, do-calculus machinery can be realized in the FD resulting in versions of the classical single-door (with cycles), front and backdoor criteria. We demonstrate, for a large class of problems, graph reconstruction using multivariate Wiener projections results in a significant computational advantage with $O(n)$ complexity over reconstruction algorithms such as the PC algorithm which has $O(n^q)$ complexity, where $q$ is the maximum neighborhood size. This advantage accrues due to some remarkable properties of the phase response of the frequency-dependent Wiener coefficients which is not present in any time-domain approach.
• Abstract（参考訳）: データから因果関係を学習することは、特に因果関係が本質的に静的である場合、科学全体で根本的でよく研究されている問題である。 しかし、動的依存関係がある場合、すなわち時間を通してエンティティ間で依存関係が存在する場合、因果効果は調査されない。 時系列観測による動的因果効果の同定は,静的シナリオと比較して計算コストが高い。 ベクトル自己回帰(var)モデルの因果構造を復元する計算の複雑さは$o(tn^3n^2)$であり、ここで$n$はノード数、$t$はサンプル数、$n$はエンティティ間の依存関係において最大のタイムラグである。 我々は,時間系列の周波数領域(FD)表現を得るために,因果構造を復元するために,$O(Tn^3 \log N)$の複雑さを低減した手法を報告する。 FFTは全ての周波数に全ての時間依存を蓄積するため、任意の周波数で状態変数をランダム変数として考えることで因果推論を効率的に行うことができる。 さらに, LTI であるシステムでは, 従来のシングルドア(サイクル付き), フロント, バックドアの基準, などによって, ドカルス機構をFDで実現可能であることを示す。 大規模な問題に対して、多変量ウィナー射影を用いたグラフ再構成は、$O(n)$、$O(n^q)$複雑さを持つPCアルゴリズムのような再構成アルゴリズムよりも、$O(n)$、$q$が最大近傍サイズであるような計算上の優位性を示す。 この利点は、いかなる時間領域アプローチにも存在しない周波数依存ウィナー係数の位相応答のいくつかの顕著な性質によって生じる。

関連論文リスト

• Testing Causal Models with Hidden Variables in Polynomial Delay via Conditional Independencies [49.99600569996907]
  観測データに対して仮説化された因果モデルをテストすることは、多くの因果推論タスクにとって重要な前提条件である。 モデルは指数関数的に多くの条件付き独立関係(CI)を仮定できるが、これら全てをテストすることは実用的でなく不必要である。 隠れ変数を持つ因果グラフのc-LMPを導入し、これらのCIを多時間間隔でリストする遅延アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-09-22T21:05:56Z)
• A Scale-Invariant Sorting Criterion to Find a Causal Order in Additive Noise Models [49.038420266408586]
  分散の増加による変数のソートは、しばしば因果順序に近い順序になることを示す。 本稿ではR2$-SortnRegressと呼ばれる,高いR2$-sortabilityを利用する効率的なベースラインアルゴリズムを提案する。 その結果,因果発見に関連するデータ生成プロセスの仮定として,R2$-sortabilityが高額であることが判明した。
  論文  参考訳（メタデータ） (2023-03-31T17:05:46Z)
• FeDXL: Provable Federated Learning for Deep X-Risk Optimization [105.17383135458897]
  我々は、既存のアルゴリズムが適用できないXリスクのファミリーを最適化するために、新しい連邦学習(FL)問題に取り組む。 Xリスクに対するFLアルゴリズムを設計する際の課題は、複数のマシンに対する目的の非可逆性と、異なるマシン間の相互依存にある。
  論文  参考訳（メタデータ） (2022-10-26T00:23:36Z)
• Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit [36.17720004582283]
  この研究は、$k$sparseパリティを$n$bitsで学習するレンズを通してそのような探索を行う。 データセットのサイズと実行時間をスケールアップする際、ニューラルネットワークは驚くほどの位相遷移を示す。
  論文  参考訳（メタデータ） (2022-07-18T17:55:05Z)
• SITHCon: A neural network robust to variations in input scaling on the time dimension [0.0]
  機械学習では、畳み込みニューラルネットワーク(CNN)はコンピュータビジョンと時間とともに拡張されたパターンの認識の両方に非常に影響を与えている。 本稿では,対数的に分散した時間メモリを用いたSITHCon(Scale-Invariant Temporal History Convolution Network)を提案する。
  論文  参考訳（メタデータ） (2021-07-09T18:11:50Z)
• The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality [8.940054309023525]
  トレーニングデータの寸法$d$が計算の複雑さに与える影響を分析します。 既知のブルートフォース戦略が本質的に最適であることを示す。 特に、一定の$d$ と凸損失関数に対する既知の時間アルゴリズムを、より一般的な損失関数のクラスに拡張する。
  論文  参考訳（メタデータ） (2021-05-18T17:05:26Z)
• Consistency of mechanistic causal discovery in continuous-time using Neural ODEs [85.7910042199734]
  ダイナミカルシステムの研究において,連続時間における因果的発見を検討する。 本稿では,ニューラルネットワークを用いた因果探索アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-06T08:48:02Z)
• Improved rates for prediction and identification of partially observed linear dynamical systems [4.68299658663016]
  部分的な観測から線形時間イン力学系の同定は制御理論の基本的な問題である。 本稿では,システム固有の$d$に依存する非漸近統計率でそのようなシステムを学習するアルゴリズムを提案する。 本アルゴリズムは,ハンケル行列に適用したマルチスケール低ランク近似SVDに基づく。
  論文  参考訳（メタデータ） (2020-11-19T18:04:18Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  強化学習のコアにおける探索・探索トレードオフについて検討する。 特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。 私たちの後悔の限界はエピソードの数とは無関係です。
  論文  参考訳（メタデータ） (2020-11-09T18:32:22Z)
• Connecting the Dots: Multivariate Time Series Forecasting with Graph Neural Networks [91.65637773358347]
  多変量時系列データに特化して設計された汎用グラフニューラルネットワークフレームワークを提案する。 グラフ学習モジュールを用いて,変数間の一方向関係を自動的に抽出する。 提案手法は,4つのベンチマークデータセットのうち3つにおいて,最先端のベースライン手法よりも優れている。
  論文  参考訳（メタデータ） (2020-05-24T04:02:18Z)

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

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