滑らか、疎、かつ安定的：平滑化近接勾配法による有限時間での正確なスケルトン復元

TL;DR（結論）

因果探索における連続最適化手法は、漸近的な収束に留まるため離散的なグラフ構造の復元に恣意的な閾値処理を必要とするという根本的な課題を抱えていた。本研究は、ハイブリッド次数非巡回制約（AHOC）と平滑化近接勾配法（SPG-AHOC）を提案し、近接演算子の「トポロジカル・ロッキング」機構によって有限時間内に正確な構造を特定する理論的保証を与えた。実験では、合成データおよび実世界のSachsデータセットにおいて、構造的制約の不安定性を解消しながら、既存手法を上回る最先端の精度と正確なゼロエントリの復元を達成している。

なぜこの問題か

相関関係から因果関係へと分析を移行させるためには、変数間の相互作用における正確な構造を解明することが不可欠である。歴史的に、この問題は組合せ最適化アルゴリズムによって対処されてきたが、変数の数が増えるにつれて計算量が爆発し、スケーラビリティが著しく低下するという課題があった。その後、NOTEARSなどの手法が登場し、離散的な有向非巡回グラフ（DAG）制約を連続的な等式制約に定式化し直すことで、効率的な連続最適化技術の利用が可能になった。しかし、この計算上の進歩にもかかわらず、連続最適化の出力と離散的なグラフ構造の間には依然として大きな隔たりが存在している。 既存の連続最適化手法の多くは、定常点への漸近的な収束のみを保証している。実際には、これにより重み行列が密になり、「ゼロ」であるべきエッジが非常に小さな非ゼロの値（例えば10のマイナス4乗など）として表現される。有効なDAG構造を復元するためには、恣意的な事後閾値処理が必要となるが、これは科学的な曖昧さを引き起こす。小さな重みが弱い因果関係を表しているのか、それとも単なる数値的なノイズなのかを判断する客観的な基準がないためである。…

核心：何を提案したのか

本研究の主要な提案は、安定した非巡回制約のための公理的枠組みと、それを最適化するためのSPG-AHOCアルゴリズムである。まず、安定した非巡回制約が満たすべき3つの基本公理を定義した。第一に、制約関数がゼロであることとグラフがDAGであることが同値であるという「正確性（Correctness）」。第二に、L1正則化と相乗効果を持ち、原点付近で勾配が消失しない「L1シナジー（L1-Synergy）」。第三に、勾配が爆発せず数値的に安定している「数値的有界性（Numerical Boundedness）」である。これらの公理は、連続最適化を因果探索に適用する際の健全性を保証するものである。 これらの公理に基づき、既存の標準的な制約クラス（Hクラス）ではL1シナジーと数値的有界性を同時に満たせないことを明らかにした。これに対し、本研究ではハイブリッド次数非巡回制約（AHOC）およびその変種であるS-AHOCを提案した。…

続きはログイン/プランで閲覧できます。