論文の概要: DAGMA: Learning DAGs via M-matrices and a Log-Determinant Acyclicity Characterization

• arxiv url: http://arxiv.org/abs/2209.08037v1
• Date: Fri, 16 Sep 2022 16:31:27 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-19 12:26:09.586504
• Title: DAGMA: Learning DAGs via M-matrices and a Log-Determinant Acyclicity Characterization
• Title（参考訳）: DAGMA:M行列によるDAGの学習とログ決定的非周期性評価
• Authors: Kevin Bello, Bryon Aragam and Pradeep Ravikumar
• Abstract要約: 対数決定関数(log-det)関数に基づいた,$textitfundamentally different$$ acyclicity キャラクタリゼーションを提案する。 我々の手法は、最先端の手法に対して大きなスピードアップとより小さな構造ハミングに到達できる。
• 参考スコア（独自算出の注目度）: 46.03369331654967
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The combinatorial problem of learning directed acyclic graphs (DAGs) from data was recently framed as a purely continuous optimization problem by leveraging a differentiable acyclicity characterization of DAGs based on the trace of a matrix exponential function. Existing acyclicity characterizations are based on the idea that powers of an adjacency matrix contain information about walks and cycles. In this work, we propose a $\textit{fundamentally different}$ acyclicity characterization based on the log-determinant (log-det) function, which leverages the nilpotency property of DAGs. To deal with the inherent asymmetries of a DAG, we relate the domain of our log-det characterization to the set of $\textit{M-matrices}$, which is a key difference to the classical log-det function defined over the cone of positive definite matrices. Similar to acyclicity functions previously proposed, our characterization is also exact and differentiable. However, when compared to existing characterizations, our log-det function: (1) Is better at detecting large cycles; (2) Has better-behaved gradients; and (3) Its runtime is in practice about an order of magnitude faster. From the optimization side, we drop the typically used augmented Lagrangian scheme, and propose DAGMA ($\textit{Directed Acyclic Graphs via M-matrices for Acyclicity}$), a method that resembles the central path for barrier methods. Each point in the central path of DAGMA is a solution to an unconstrained problem regularized by our log-det function, then we show that at the limit of the central path the solution is guaranteed to be a DAG. Finally, we provide extensive experiments for $\textit{linear}$ and $\textit{nonlinear}$ SEMs, and show that our approach can reach large speed-ups and smaller structural Hamming distances against state-of-the-art methods.
• Abstract（参考訳）: データから有向非巡回グラフ(DAG)を学習する組合せ問題は、行列指数関数のトレースに基づくDAGの微分的非巡回性特性を利用した純粋に連続的な最適化問題として最近検討された。 既存の非周期的特徴付けは、隣接行列のパワーが歩行やサイクルに関する情報を含んでいるという考えに基づいている。 本研究では,log-det(log-det)関数を基礎として,dagのnilpotency特性を利用した$\textit{fundamentally different}$ acyclicity characterizationを提案する。 DAGの本質的な非対称性を扱うために、当社の対数行列特徴づけの領域を $\textit{M-matrices}$ の集合に関連付ける。 前述した非巡回関数と同様に、この特徴付けも正確かつ微分可能である。 しかし、既存の特徴と比較すると、(1)大きなサイクルを検出するのが優れていること、(2)より良い勾配を持つこと、(3)実行時間は実際は桁違いに高速である。 最適化側では、一般的に用いられる拡張ラグランジアンスキームを廃止し、障壁法の中心経路に類似した手法であるDAGMA(\textit{Directed Acyclic Graphs via M-matrices for Acyclicity}$)を提案する。 DAGMAの中心経路の各点は、当社のログデット関数によって正規化された制約のない問題の解であり、中央経路の極限において、解がDAGであることが保証されていることを示す。 最後に、$\textit{linear}$および$\textit{nonlinear}$ SEMsに対して広範な実験を行い、我々の手法が最先端の手法に対して大きなスピードアップとより小さな構造的ハミング距離に達することを示す。

関連論文リスト

• Riemannian Optimization for Non-convex Euclidean Distance Geometry with Global Recovery Guarantees [6.422262171968397]
  ユークリッド距離幾何学問題を解くために2つのアルゴリズムが提案されている。 第一のアルゴリズムは真の解に線形に収束する。 第2のアルゴリズムは、合成データと実データの両方で強い数値性能を示す。
  論文  参考訳（メタデータ） (2024-10-08T21:19:22Z)
• Linear Transformer Topological Masking with Graph Random Features [52.717865653036796]
  重み付き隣接行列の学習可能な関数としてトポロジカルマスクをパラメータ化する方法を示す。 私たちの効率的なマスキングアルゴリズムは、画像およびポイントクラウドデータのタスクに対して、強力なパフォーマンス向上を提供します。
  論文  参考訳（メタデータ） (2024-10-04T14:24:06Z)
• Non-negative Weighted DAG Structure Learning [12.139158398361868]
  本研究は,真DAGを夜間観測から学習する問題に対処する。 本稿では, ar を返すことが保証される手法に基づく DAG 回復アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-09-12T09:41:29Z)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  グラフ信号解析と処理の利点を享受する統合グラフ信号サンプリングフレームワークを提案する。 キーとなる考え方は、各ユーザのアイテムのレーティングをアイテムイットグラフの頂点上の関数(信号)に変換することである。 オンライン設定では、グラフフーリエ領域における連続ランダムガウス雑音を考慮したベイズ拡張(BGS-IMC)を開発する。
  論文  参考訳（メタデータ） (2023-02-08T08:17:43Z)
• Truncated Matrix Power Iteration for Differentiable DAG Learning [47.69479930501961]
  本稿では,列ベースDAG制約を近似するために,効率的な乱数行列パワーを持つ新しいDAG学習法を提案する。 実験により,DAG学習法は,様々な設定で従来の最先端技術よりも優れていた。
  論文  参考訳（メタデータ） (2022-08-30T23:56:12Z)
• From graphs to DAGs: a low-complexity model and a scalable algorithm [0.0]
  本稿では,低ランク行列因数分解とDAGの連続的な最適化のためのスペース化機構を組み合わせたLoRAM for Low-Rank Additive Modelを提案する。 提案手法は,NoTearsと同じDAG特性関数を扱いながら,立方的複雑性から二次的複雑性への還元を実現する。
  論文  参考訳（メタデータ） (2022-04-10T10:22:56Z)
• Learning Large DAGs by Combining Continuous Optimization and Feedback Arc Set Heuristics [0.3553493344868413]
  線形構造方程式の場合,DAGを学習するための2つのスケーラブルNPを提案する。 対象関数を最適化するために、制約のない勾配降下に基づくステップを交互に組み合わせてDAGを学習する。 この分離のおかげで、私たちのメソッドは何千もの変数を越えてスケールアップされます。
  論文  参考訳（メタデータ） (2021-07-01T16:10:21Z)
• Graph Signal Restoration Using Nested Deep Algorithm Unrolling [85.53158261016331]
  グラフ信号処理は、センサー、社会交通脳ネットワーク、ポイントクラウド処理、グラフネットワークなど、多くのアプリケーションにおいてユビキタスなタスクである。 凸非依存型深部ADMM(ADMM)に基づく2つの復元手法を提案する。 提案手法のパラメータはエンドツーエンドでトレーニング可能である。
  論文  参考訳（メタデータ） (2021-06-30T08:57:01Z)
• DAGs with No Curl: An Efficient DAG Structure Learning Approach [62.885572432958504]
  近年のDAG構造学習は連続的な非巡回性制約を伴う制約付き連続最適化問題として定式化されている。 本稿では,DAG空間の重み付き隣接行列を直接モデル化し,学習するための新しい学習フレームワークを提案する。 本手法は, 線形および一般化された構造方程式モデルにおいて, ベースラインDAG構造学習法よりも精度が高いが, 効率がよいことを示す。
  論文  参考訳（メタデータ） (2021-06-14T07:11:36Z)

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

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