Infinite Hidden Semi-Markov Modulated Interaction Point Process
The correlation between events is ubiquitous and important for temporal events modelling. In many cases, the correlation exists between not only events' emitted observations, but also their arrival times. State space models (e.g., hidden Markov model) and stochastic interaction point process models (e.g., Hawkes process) have been studied extensively yet separately for the two types of correlations in the past. In this paper, we propose a Bayesian nonparametric approach that considers both types of correlations via unifying and generalizing the hidden semiMarkov model and interaction point process model. The proposed approach can simultaneously model both the observations and arrival times of temporal events, and automatically determine the number of latent states from data. A Metropoliswithin-particle-Gibbs sampler with ancestor resampling is developed for efficient posterior inference. The approach is tested on both synthetic and real-world data with promising outcomes.
with a variable duration time for each state. In addition to the HMM components, the HSMM models the duration of a state as a random variable and a state can emit a sequence of observations. The HSMM allows the flexibility of variable inter-arrival times, but it does not consider events' correlation on arrival times. In many real-world applications, one event can trigger the occurrences of others in the near future. For instance, earthquakes and epidemics are diffusible events, i.e., one can cause the occurrences of others. Trading events in financial markets arrive in clusters. Information propagation in social network shows contagious and clustering characteristics. All these events exhibit interaction characteristics in terms of arrival times. The likelihood of an event's arrival time is affected by the previous events' arrival times. Stochastic interaction point process (IPP), e.g., Hawkes process [6], is a widely adopted framework for capturing such arrival time correlation. It models the correlation via a conditional intensity function that depicts the event intensity depending on all the previous events' arrival times. However, unlike the SSMs, it lacks the capability of modelling events' latent states and their interactions.
It is clearly desirable in real-world applications to have both arrival time correlation and observation correlation considered in a unified manner so that we can estimate both when and how events will appear. Inspired by the merits of SSMs and IPPs, we propose a novel Bayesian nonparametric approach that unifies and generalizes SSMs and IPPs via a latent semi-Markov state chain with infinitely countable number of states. The latent states governs both the observation emission and new event triggering mechanism. An efficient sampling method is developed within the framework of particle Markov chain Monte Carlo (PMCMC) [1] for the posterior inference of the proposed model.
We first review closely related techniques in Section 2, and give the description of the proposed model in Section 3. Then Section 4 presents the inference algorithm. In Section 5, we show the results of the empirical studies on both synthetic and real-word data. Conclusions are drawn in Section 6.
This paper develops a joint model for the occurrance times and observed outcomes of discrete events: for example the onset time and electricity usage for variance appliances or the posting time and content of messages on a social network. The model is a sensible extension of a hidden Markov model (HMM) where each state has the standard transition and emission probabilities as well as a state-specific Hawkes process which generates the time until the next event. Using a hierarchical DP prior, the number of active states can be inferred from data.  To fit the proposed model to data, a particle Gibbs sampler algorithm is developed. The observed data in a sequence includes a time value t_n and an observed vector y_n at each discrete index n. The sampler must infer the state sequence s_1 ... s_N as well as the emission parameters, transition parameters, and Hawkes process parameters. Particle methods are used to sample the state sequence given all other variables, and then the remaining variables have standard Gibbs updates, except for the triggering kernels \psi and background rate \mu of the Hawkes process, which use random-walk Metropolis proposals.  Experiments compare the proposed method, called iHSMM-IPP, agains several baselines from the literature including the sticky HDP-HMM (Fox et al) and the semi-Markov HDP-HSMM (Johnson & Willsky '14) and two methods (variational [11] and Metropolis sampling [17]) for the marked Hawkes process. On toy data generated from the proposed model, the proposed algorithm recovers noticeably better Hamming distance scores. On an energy disaggregation task (REDD) and a pipe burst event task, the proposed method does better as well, likely due to its joint modeling of both event times and event emissions.
Overall I recommend accepting this paper as a poster presentation. I can see NIPS attendees benefiting from learning more about the model, inference algorithm, and the practical applications to event failure modeling. My chief concerns are questions about scalability and lack of within-method experiments to validate different features of the algorithm. The technical content could also use revision to improve readability, though the paper is organized well.  Novelty and related work ========================  This is the first paper I know of that combines Hawkes processes, HMMs with semi-Markov durations, and nonparametric priors like the HDP. However, it does look like there is some missing citations to previous efforts to synthesize Hawkes processes and state space models. See for example this somewhat paper on a switching state model where each state has a Hawkes process, which might be worth mentioning in related work (I haven't read carefully):  Markov-modulated Hawkes process with stepwise decay Wang, Bebbington, and Hart Ann Inst Stat Math (2012) 64:521–544 http://www.ism.ac.jp/editsec/aism/pdf/10463_2010_Article_320.pdf  On the inference side, this looks like a nice application of particle Gibbs methods. I hope the authors can share code so others can take advantage of this contribution. The description in the paper itself is likely too dense to easily allow reproducing this algorithm.  Algorithm feedback ================== Sec. 4 provides lots of gory detail about the various substeps of the algorithm, but is somewhat lacking in high-level description. In particular, I'd like to see discussion of the overall runtime complexity of the sampler: What is the big-oh cost of the particle sampling of the state sequence? How does it scale with sequence length, number of states K, number of particles, etc? How would it compare with standard forward-backward type inference for simpler HMM models?  How does the implementation do in a practical sense? That is, can you provide details like: it takes ___ seconds to handle a sequence of length ___ with ___ states.  What kind of hyperparameters/settings is the algorithm sensitive to? I'd expect that the number of particles needs to be set somewhat carefully to balance speed and accuracy. How is this chosen? (I didnt see it anywhere, apologies if I missed it).  How exactly is the algorithm initialized? I'd expect performance to be quite sensitive to initialization, especially if the number of active states is much lower than it needs to be.  The details of the truncated ancestor resampling (Sec 4.2) were confusing to me. What is being truncated? Why is this necessary? Big picture details would be useful here.  Experiment feedback =================== Overall I was pleased with the experiments: they include comparison to a large set of reasonable baselines and consider two challenging datasets (Redd and Pipe). I thought the biggest weakness was a lack of comparison to different possible settings of the proposed method: for example, using different numbers of particles, or with or without some hyperparameter resampling, etc. There are many speed/accuracy tradeoffs that could be made in practice, and the present paper doesn't provide much guidance about how to manage these concerns, or even indicate that such concerns should exist.  For the Pipe data experiments that predict the last 10% of each sequence given the first 90%, I am confused how the number of failure events is estimated for methods like the HDP-HMM that don't have any built-in model for durations. Can you clarify?  For REDD data, it would be interesting to visualize and explore qualitative relationships discovered by the learned triggering kernels. For example, is there a clear relationship between washing machine and dryer events, as expected?  Question: for REDD data, are the Hamming and LogLik score reported on the training set, or a heldout set? Please clarify. Seems that these numbers are for the training set of the Pipe data.  I'm curious how much the poor performance of other methods might be due to local optima, instead of modeling issues. To test this, I'd suggest initializing the HDP-HMM sampler or some other baseline method from the final state of the proposed iHSMM-IPP, or even from the "ground truth" labels, and report the Hamming distance after the sampler has run for a while.   Presentation feedback ==================== I like Fig 1 (illustrating model features alongside the graphical model) a lot. Thanks!  Line 196 typo: "infinite countable with the HDP" should be countably infinite  The graphical model in Fig 1 uses symbol T to indicate the total length of the sequence, but later the symbol N is used. Would be good to just pick one.  Fig 2: Plot on far left is missing x-axis ticks (# iterations). Please fix.