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 $O(N)$ pass through the data, for $N$ observations, without requiring the entire dataset to be in memory. More generally, exact inference is $\Theta (N^{2})$ , but we identify some simple $\Theta (N)$ approximation strategies that seem to provide good estimates while reducing the computational cost.