論文の概要: Massively Parallel Exact Inference for Hawkes Processes

• arxiv url: http://arxiv.org/abs/2604.01342v1
• Date: Wed, 01 Apr 2026 19:52:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-03 14:21:09.864515
• Title: Massively Parallel Exact Inference for Hawkes Processes
• Title（参考訳）: ホークスプロセスのための大規模並列エクササイズ推論
• Authors: Ahmer Raza, Hudson Smith,
• Abstract要約: ホークス過程の強度は線形時間連想乗算を許容するスパース遷移行列の積として表現できることを示す。 これにより、線形指数ホークス過程の最大極大推定のための単純だが大規模に並列化可能なアルゴリズムが得られる。 シミュレーションと実際のデータセットのオーダ・オブ・スピードアップ、数千のノードと数千万のイベントへのスケーリングをデモします。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multivariate Hawkes processes are a widely used class of self-exciting point processes, but maximum likelihood estimation naively scales as $O(N^2)$ in the number of events. The canonical linear exponential Hawkes process admits a faster $O(N)$ recurrence, but prior work evaluates this recurrence sequentially, without exploiting parallelization on modern GPUs. We show that the Hawkes process intensity can be expressed as a product of sparse transition matrices admitting a linear-time associative multiply, enabling computation via a parallel prefix scan. This yields a simple yet massively parallelizable algorithm for maximum likelihood estimation of linear exponential Hawkes processes. Our method reduces the computational complexity to approximately $O(N/P)$ with $P$ parallel processors, and naturally yields a batching scheme to maintain constant memory usage, avoiding GPU memory constraints. Importantly, it computes the exact likelihood without any additional assumptions or approximations, preserving the simplicity and interpretability of the model. We demonstrate orders-of-magnitude speedups on simulated and real datasets, scaling to thousands of nodes and tens of millions of events, substantially beyond scales reported in prior work. We provide an open-source PyTorch library implementing our optimizations.
• Abstract（参考訳）: 多変量ホークス過程は、自励点過程の広く用いられるクラスであるが、最大推定は事象数で$O(N^2)$としてNaivelyスケールする。 正準線型指数的ホークス過程はより高速な$O(N)$繰り返しを許容するが、以前の研究では、現代のGPU上での並列化を活用せずに、この繰り返しを逐次評価する。 線形時間連想乗算を許容するスパース遷移行列の積としてホークス過程の強度を表現できることを示し, 並列プレフィックススキャンによる計算を可能にする。 これにより、線形指数ホークス過程の最大極大推定のための単純だが大規模に並列化可能なアルゴリズムが得られる。 提案手法は計算複雑性を約$O(N/P)と$P$の並列プロセッサに削減し,GPUメモリの制約を回避し,メモリ使用量を一定に保つバッチ処理方式を自然に生成する。 重要なことは、追加の仮定や近似なしで正確な確率を計算し、モデルの単純さと解釈可能性を保存することである。 シミュレーションおよび実際のデータセット上でのオーダー・オブ・マグニチュードのスピードアップ、数千のノードと数千万のイベントへのスケーリング、特に前回の作業で報告されたスケール以上のものを示します。 我々は最適化を実装したオープンソースのPyTorchライブラリを提供する。

関連論文リスト

• Optimal quantum simulation of linear non-unitary dynamics [0.31439717339537293]
  有界時間依存演算子$-A$によって生成される時間進化をシミュレートする量子アルゴリズムを提案する。 本稿では,最近のLinear-Combination-of-Hamiltonian-Simulation (LCHS)フレームワークを一般化する。
  論文  参考訳（メタデータ） (2025-08-26T17:58:27Z)
• A Specialized Semismooth Newton Method for Kernel-Based Optimal Transport [92.96250725599958]
  カーネルベース最適輸送(OT)推定器は、サンプルからOT問題に対処するための代替的機能的推定手順を提供する。 SSN法は, 標準正規性条件下でのグローバル収束率$O (1/sqrtk)$, 局所二次収束率を達成できることを示す。
  論文  参考訳（メタデータ） (2023-10-21T18:48:45Z)
• Sublinear scaling in non-Markovian open quantum systems simulations [0.0]
  プロセステンソルを計算する数値的精度のアルゴリズムを導入する。 我々のアプローチでは、無限メモリを持つ環境に対して$mathcalO(nlog n)$の特異値分解しか必要としない。
  論文  参考訳（メタデータ） (2023-04-11T15:40:33Z)
• Softmax-free Linear Transformers [90.83157268265654]
  視覚変換器(ViT)は、視覚知覚タスクの最先端を推し進めている。 既存の手法は理論的に欠陥があるか、視覚認識に経験的に効果がないかのいずれかである。 我々はSoftmax-Free Transformers (SOFT) のファミリーを提案する。
  論文  参考訳（メタデータ） (2022-07-05T03:08:27Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• Mixability made efficient: Fast online multiclass logistic regression [68.8204255655161]
  我々は、混合性は最適な後悔を伴うアルゴリズムを得るための強力なツールであることを示した。 結果として得られる手法は、しばしば計算の複雑さに悩まされ、実用性が低下した。
  論文  参考訳（メタデータ） (2021-10-08T08:22:05Z)
• Sub-Linear Memory: How to Make Performers SLiM [38.068090269482425]
  vanilla Transformerは、入力長$L$の関数としてシリアル時間とメモリで$O(L2)$を必要とする。 最近の研究は、連続計算に$o(l)$でしかスケールしない様々な線形自己アテンション機構を提案している。 計算の柔軟性は顕著であり, サブリニアメモリを用いた近似をすることなく, 前方および後方の伝播を行うことができる。
  論文  参考訳（メタデータ） (2020-12-21T13:56:04Z)
• Accelerating Feedforward Computation via Parallel Nonlinear Equation Solving [106.63673243937492]
  ニューラルネットワークの評価や自己回帰モデルからのサンプリングなどのフィードフォワード計算は、機械学習においてユビキタスである。 本稿では,非線形方程式の解法としてフィードフォワード計算の課題を定式化し,ジャコビ・ガウス・シーデル固定点法とハイブリッド法を用いて解を求める。 提案手法は, 並列化可能な繰り返し回数の削減(あるいは等値化)により, 元のフィードフォワード計算と全く同じ値が与えられることを保証し, 十分な並列化計算能力を付与する。
  論文  参考訳（メタデータ） (2020-02-10T10:11:31Z)

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

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