ホークス過程に対する大規模並列の厳密推論

要旨: 多変量Hawkes過程は、広く用いられている自己励起型の点過程の一種ですが、最尤推定は素朴に行うと、事象数に対して O(N^2) にスケールします。代表的な線形指数型Hawkes過程は、より高速な O(N) の再帰を許しますが、先行研究ではこの再帰をGPUなどの現代的な計算基盤での並列化を活用せず、逐次的に評価しています。本研究では、Hawkes過程の強度が疎な遷移行列の積として表現でき、線形時間の連想的乗算が可能であることを示します。これにより、並列プレフィックススキャンによる計算が可能になります。これにより、線形指数型Hawkes過程の最尤推定のための、単純でありながら大規模に並列化可能なアルゴリズムが得られます。我々の手法は計算複雑度を、P 個の並列プロセッサに対しておおよそ O(N/P) に低減し、GPUメモリの制約を回避しつつ、一定のメモリ使用量を維持するための自然なバッチング手法も提供します。重要なのは、この手法が追加の仮定や近似を一切せずに厳密な尤度を計算し、モデルの単純さと解釈可能性を保つ点です。模擬データおよび実データにおいて桁違いの速度向上を示し、数千ノードおよび数千万件の事象へとスケールさせ、先行研究で報告された規模を大幅に超えます。我々は、これらの最適化を実装したオープンソースのPyTorchライブラリを提供します。