論文の概要: LazyIter: A Fast Algorithm for Counting Markov Equivalent DAGs and Designing Experiments

• arxiv url: http://arxiv.org/abs/2006.09670v1
• Date: Wed, 17 Jun 2020 05:51:34 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-19 18:57:06.436143
• Title: LazyIter: A Fast Algorithm for Counting Markov Equivalent DAGs and Designing Experiments
• Title（参考訳）: LazyIter: マルコフ等価DAGの計算と設計実験のための高速アルゴリズム
• Authors: Ali AhmadiTeshnizi, Saber Salehkaleybar, Negar Kiyavash
• Abstract要約: MECのサイズは、介入を行うことで真の因果グラフを回復するための複雑さの尺度である。 そこで本稿では, 介入結果の可能なMECに対して, 効率的な反復法を提案する。 提案手法は,MECの規模を計算し,実験による設計が最先端の手法であることを示す。
• 参考スコア（独自算出の注目度）: 30.592069659778716
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The causal relationships among a set of random variables are commonly represented by a Directed Acyclic Graph (DAG), where there is a directed edge from variable $X$ to variable $Y$ if $X$ is a direct cause of $Y$. From the purely observational data, the true causal graph can be identified up to a Markov Equivalence Class (MEC), which is a set of DAGs with the same conditional independencies between the variables. The size of an MEC is a measure of complexity for recovering the true causal graph by performing interventions. We propose a method for efficient iteration over possible MECs given intervention results. We utilize the proposed method for computing MEC sizes and experiment design in active and passive learning settings. Compared to previous work for computing the size of MEC, our proposed algorithm reduces the time complexity by a factor of $O(n)$ for sparse graphs where $n$ is the number of variables in the system. Additionally, integrating our approach with dynamic programming, we design an optimal algorithm for passive experiment design. Experimental results show that our proposed algorithms for both computing the size of MEC and experiment design outperform the state of the art.
• Abstract（参考訳）: ランダム変数の集合間の因果関係は、通常、DAG (Directed Acyclic Graph) で表され、変数 $X$ から変数 $Y$ への有向エッジが存在する($X$ が$Y$ の直接原因である)。 純粋な観測データから、真の因果グラフは、変数間で同じ条件非依存性を持つDAGの集合であるマルコフ等価クラス(MEC)まで同定することができる。 MECのサイズは、介入によって真の因果グラフを復元する複雑さの尺度である。 そこで本研究では, 介入結果に対するMECよりも効率的な反復法を提案する。 提案手法は,アクティブ・パッシブ・ラーニング環境におけるmecサイズと実験設計の計算に活用する。 従来のMECの計算処理と比較して,提案アルゴリズムは,システム内の変数数が$n$となるスパースグラフに対して,O(n)$の係数で時間複雑性を減少させる。 さらに, 動的プログラミングへのアプローチを統合することにより, 受動的実験設計のための最適アルゴリズムを設計する。 実験結果から,提案アルゴリズムはMECのサイズを計算し,実験設計は技術よりも優れていた。

関連論文リスト

• QWO: Speeding Up Permutation-Based Causal Discovery in LiGAMs [20.661343069864888]
  QWO は与えられた置換に対して$mathcalGpi$ の計算効率を大幅に向上させる新しい手法である。 QWOは、最先端のBICベースの手法と比較して、$O(n2)$$$(n$は変数の数)のスピードアップがあり、非常にスケーラブルである。
  論文  参考訳（メタデータ） (2024-10-30T16:10:46Z)
• Learning causal graphs using variable grouping according to ancestral relationship [7.126300090990439]
  サンプルサイズが変数数に対して小さい場合には,既存手法を用いた因果グラフの推定精度が低下する。 サンプルサイズが変数の数より小さい場合、いくつかのメソッドは実現不可能である。 これらの問題を回避すべく、ある研究者は分割・対数アプローチを用いた因果構造学習アルゴリズムを提案した。
  論文  参考訳（メタデータ） (2024-03-21T04:42:04Z)
• Cost Aware Best Arm Identification [13.380383930882784]
  emphCost Aware Best Arm Identification (CABAI)と呼ぶ。 平方根規則に基づくemphChernoff Overlap (CO)と呼ばれる単純なアルゴリズムを提案する。 この結果から,不均一な動作コストを無視すると,実行時の準最適性が得られ,また,簡単なアルゴリズムにより,幅広い問題に対してほぼ最適性能が得られることがわかった。
  論文  参考訳（メタデータ） (2024-02-26T16:27:08Z)
• Maximum Independent Set: Self-Training through Dynamic Programming [56.670639478539485]
  本研究では、動的プログラミング(DP)にインスパイアされた最大独立集合(MIS)問題を解決するグラフニューラルネットワーク(GNN)フレームワークを提案する。 GNNをベースとしたDPライクな再帰アルゴリズムを提案し、まず2つの小さなサブグラフを構築し、より大きなMISを持つサブグラフを予測し、次に再帰呼び出しを行う。 MISサイズに関する異なるグラフの比較を注釈付けすると、自己学習プロセスが発生し、比較をより正確に自己アノテーションし、その逆も引き起こされる。
  論文  参考訳（メタデータ） (2023-10-28T10:58:25Z)
• On the Sample Complexity of Representation Learning in Multi-task Bandits with Global and Local structure [77.60508571062958]
  マルチタスク・バンディット問題に対する最適アーム学習の複雑さについて検討した。 アームは2つのコンポーネントで構成されます。1つはタスク間で共有され(表現と呼ばれます)、もう1つはタスク固有のもの(予測器と呼ばれます)です。 サンプルの複雑さが下界に近づき、最大で$H(Glog(delta_G)+ Xlog(delta_H))$でスケールするアルゴリズムOSRL-SCを考案する。
  論文  参考訳（メタデータ） (2022-11-28T08:40:12Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。 我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
  論文  参考訳（メタデータ） (2022-10-14T01:42:05Z)
• Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
  本稿では,フェデレートラーニング手法を用いて,オーバー・ザ・エアラーニングのための低複雑さデバイススケジューリングアルゴリズムのクラスを開発する。 最先端の提案方式と比較すると,提案方式は極めて低効率なシステムである。 提案手法の有効性は,CIFARデータセットを用いた実験により確認した。
  論文  参考訳（メタデータ） (2022-06-14T08:14:14Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。 我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
  論文  参考訳（メタデータ） (2021-03-04T19:01:20Z)
• Intervention Efficient Algorithms for Approximate Learning of Causal Graphs [22.401163479802094]
  我々は、潜時の存在下で観察された変数の集合間の因果関係を学習する問題を研究する。 我々の目標は、介入の最小限の費用で、すべての因果関係や祖先関係の方向性を$G$で回収することです。 我々のアルゴリズムは効率的な介入設計と低コストな分離集合系の設計を組み合わせる。
  論文  参考訳（メタデータ） (2020-12-27T17:08:46Z)
• FANOK: Knockoffs in Linear Time [73.5154025911318]
  本稿では,ガウスモデル-Xノックオフを効率的に実装し,大規模特徴選択問題における誤発見率を制御するアルゴリズムについて述べる。 当社のメソッドは、最大50,000ドルという問題でテストしています。
  論文  参考訳（メタデータ） (2020-06-15T21:55:34Z)

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

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