論文の概要: A Fast PC Algorithm with Reversed-order Pruning and A Parallelization Strategy

• arxiv url: http://arxiv.org/abs/2109.04626v1
• Date: Fri, 10 Sep 2021 02:22:10 GMT
• ステータス: 処理完了
• システム内更新日: 2021-09-13 23:46:42.450690
• Title: A Fast PC Algorithm with Reversed-order Pruning and A Parallelization Strategy
• Title（参考訳）: 逆次プルーニングと並列化戦略を用いた高速pcアルゴリズム
• Authors: Kai Zhang, Chao Tian, Kun Zhang, Todd Johnson, Xiaoqian Jiang
• Abstract要約: PCアルゴリズムは観測データに基づく因果構造発見のための最先端のアルゴリズムである。 条件付き独立テストが実行された場合、最悪の場合、計算コストがかかる可能性がある。 これにより、タスクが数百から数千のノードを含む場合、アルゴリズムは計算的に難解になる。 本稿では、2つのノードを独立にレンダリングする条件セットが非特異であり、特定の冗長ノードを含む場合、結果の精度を犠牲にしない、という批判的な観察を提案する。
• 参考スコア（独自算出の注目度）: 22.31288740171446
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The PC algorithm is the state-of-the-art algorithm for causal structure discovery on observational data. It can be computationally expensive in the worst case due to the conditional independence tests are performed in an exhaustive-searching manner. This makes the algorithm computationally intractable when the task contains several hundred or thousand nodes, particularly when the true underlying causal graph is dense. We propose a critical observation that the conditional set rendering two nodes independent is non-unique, and including certain redundant nodes do not sacrifice result accuracy. Based on this finding, the innovations of our work are two-folds. First, we innovate on a reserve order linkage pruning PC algorithm which significantly increases the algorithm's efficiency. Second, we propose a parallel computing strategy for statistical independence tests by leveraging tensor computation, which brings further speedup. We also prove the proposed algorithm does not induce statistical power loss under mild graph and data dimensionality assumptions. Experimental results show that the single-threaded version of the proposed algorithm can achieve a 6-fold speedup compared to the PC algorithm on a dense 95-node graph, and the parallel version can make a 825-fold speed-up. We also provide proof that the proposed algorithm is consistent under the same set of conditions with conventional PC algorithm.
• Abstract（参考訳）: pcアルゴリズムは観測データ上の因果構造発見のための最先端アルゴリズムである。 条件付き独立試験が徹底的に行われるため、最悪の場合、計算コストがかかる可能性がある。 これにより、タスクが数百から数千のノードを含む場合、特に真の因果グラフが密集している場合、アルゴリズムは計算的に難解になる。 本研究では,2つのノードを独立にレンダリングする条件セットは不自然であり,冗長ノードを含む条件セットは結果精度を犠牲にしないという批判的観測を提案する。 この発見に基づいて、私たちの仕事の革新は2つある。 まず,アルゴリズムの効率を大幅に向上させるリザーブ・オーダー・リンケージ・プルーニングPCアルゴリズムを革新する。 第2に,テンソル計算を活用し,統計独立性テストのための並列計算戦略を提案する。 また,提案アルゴリズムは,軽度グラフとデータ次元の仮定の下で,統計的損失を生じさせないことを示す。 実験結果から,提案アルゴリズムのシングルスレッドバージョンは,高密度95ノードグラフ上のPCアルゴリズムと比較して6倍の高速化を実現し,並列バージョンは825倍の高速化を実現することができた。 また,提案アルゴリズムは従来のPCアルゴリズムと同一条件下で一致していることを示す。

関連論文リスト

• Quantum Hamiltonian Algorithms for Maximum Independent Sets [6.772902928686719]
  PKアルゴリズムと呼ばれる別のアルゴリズムは、独立集合が創発的PXPモデルの非アーベルゲージ行列によって支配されるメディアグラフ上で拡散することを明らかにする。 2つのアルゴリズムは数学的に等価であるが、PKアルゴリズムはより効率的でリソース節約性能を示す。
  論文  参考訳（メタデータ） (2023-10-23T04:00:34Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。 我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。 また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
  論文  参考訳（メタデータ） (2023-02-14T22:12:16Z)
• A Push-Relabel Based Additive Approximation for Optimal Transport [5.111364864495785]
  最適な輸送を計算するための厳密なアルゴリズムは遅くなる。 我々は、OT距離の$varepsilon$approximationを求めるための、新しい非常に単純なアプローチを導入する。 我々のアルゴリズムは、OT距離を計算するために、O(n2/varepsilon2)$のほぼ最適実行時間を達成する。
  論文  参考訳（メタデータ） (2022-03-07T21:40:14Z)
• Practical, Provably-Correct Interactive Learning in the Realizable Setting: The Power of True Believers [12.09273192079783]
  我々は、対話型学習を実現可能な設定で検討し、最適な腕の識別からアクティブな分類に至るまでの問題に対処する一般的な枠組みを開発する。 我々は,最小限の値と対数係数とを一致させる,計算効率のよい新しいアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-11-09T02:33:36Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。 本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。 ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
  論文  参考訳（メタデータ） (2021-09-13T18:10:52Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Local Algorithms for Estimating Effective Resistance [26.54556748340991]
  本研究では,大規模グラフ上での有効抵抗を推定するための複数のエンファンローカアルゴリズムを設計する。 主アルゴリズムは任意の頂点対 $s,t$ と任意に小さな加算誤差の間の有効抵抗を近似する。 いくつかのベンチマークデータセットについて広範な実験を行い、アルゴリズムを検証した。
  論文  参考訳（メタデータ） (2021-06-07T10:08:12Z)
• Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering [6.4805900740861]
  HDBSCAN$*$のための私達のアルゴリズムの仕事そしてスペースを減らすために十分分離の新しい概念を導入します。 我々のアルゴリズムは理論的に効率的であることを示す: 彼らは逐次対応の作業(操作数)と多対数深さ(並列時間)を持っている。 48コアマシンを用いた大規模実世界および合成データセットの実験により、我々の最速のアルゴリズムは11.13-55.89x、既存の並列アルゴリズムを少なくとも桁違いに上回った。
  論文  参考訳（メタデータ） (2021-04-02T16:05:00Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。 我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
  論文  参考訳（メタデータ） (2020-08-29T14:58:26Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)

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

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