Exact and approximate EM estimation of mutually exciting hawkes processes

Motivated by the availability of continuous event sequences that trace the social behavior in a population e.g. email, we believe that mutually exciting Hawkes processes provide a realistic and informative model for these sequences. For complex mutually exciting processes, the numerical optimization used for univariate self exciting processes may not provide stable estimates. Furthermore, convergence can be exceedingly slow, making estimation computationally expensive and multiple random restarts doubly so. We derive an expectation maximization algorithm for maximum likelihood estimation mutually exciting processes that is faster, more robust, and less biased than estimation based on numerical optimization. For an exponentially decaying excitement function, each EM step can be computed in a single <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$$O(N)$$</EquationSource> </InlineEquation> pass through the data, for <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$$N$$</EquationSource> </InlineEquation> observations, without requiring the entire dataset to be in memory. More generally, exact inference is <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$$\Theta (N^{2})$$</EquationSource> </InlineEquation>, but we identify some simple <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$$\Theta (N)$$</EquationSource> </InlineEquation> approximation strategies that seem to provide good estimates while reducing the computational cost. Copyright Springer Science+Business Media Dordrecht 2013