doi:10.1093/comjnl/bxs124 A Forward–Backward Algorithm for Nested Hidden semi-Markov Model and Application to Network Traffic

Doubly hidden Markov models (DHMMs) have been widely used to analyze a type of time process whose driving factors are hierarchical and hierarchically correlated. A common issue of these models is that they implicitly assume that the dwell time of any system state is constant or exponentially distributed. This property comes from the standard hidden Markov models and causes the DHMM to limitations in some actual application environment, where an application has latent temporal structure and does not follow the exponential distribution but has the period-like or variable-period feature. Such problems are frequently encountered in practice, e.g. network traffic. In this paper, we remove this limitation by a new structural discrete approach named nested hidden semi-Markov model. The proposed model includes a nested latent semi-Markov chain and one observable discrete stochastic process. The bottom latent semi-Markov chain is the core layer and controls the second-layer semi-Markov chain that generates the observable process. The state duration of both the semi-Markov chains can be variable or explicit. The model makes no assumptions on the distribution of the state-duration and the observable processes. An efficient forward and backward recursion procedure is developed for estimating the generator of the proposed model and inferring the underlying state processes for a given observation sequence. To evaluate the performance of the proposed model, w