Hierarchical hidden Markov models with general state hierarchy

The hierarchical hidden Markov model (HHMM) is an extension of the hidden Markov model to include a hierarchy of the hidden states. This form of hierarchical modeling has been found useful in applications such as handwritten character recognition, behavior recognition, video indexing, and text retrieval. Nevertheless, the state hierarchy in the original HHMM is restricted to a tree structure. This prohibits two different states from having the same child, and thus does not allow for sharing of common substructures in the model. In this paper, we present a general HHMM in which the state hierarchy can be a lattice allowing arbitrary sharing of substructures. Furthermore, we provide a method for numerical scaling to avoid underflow, an important issue in dealing with long observation sequences. We demonstrate the working of our method in a simulated environment where a hierarchical behavioral model is automatically learned and later used for recognition.

Content structure discovery in educational videos using shared structures in the hierarchical hidden Markov models

In this paper, we present an application of the hierarchical HMM for structure discovery in educational videos. The HHMM has recently been extended to accommodate the concept of shared structure, ie: a state might multiply inherit from more than one parents. Utilising the expressiveness of this model, we concentrate on a specific class of video -educational videos - in which the hierarchy of semantic units is simpler and clearly defined in terms of topics and its subunits. We model the hierarchy of topical structures by an HHMM and demonstrate the usefulness of the model in detecting topic transitions.

Hierarchical semi-markov conditional random fields for recursive sequential data

Inspired by the hierarchical hidden Markov models (HHMM), we present the hierarchical semi-Markov conditional random field (HSCRF), a generalisation of embedded undirected Markov chains to model complex hierarchical, nested Markov processes. It is parameterised in a discriminative framework and has polynomial time algorithms for learning and inference. Importantly, we develop efficient algorithms for learning and constrained inference in a partially-supervised setting, which is important issue in practice where labels can only be obtained sparsely. We demonstrate the HSCRF in two applications: (i) recognising human activities of daily living (ADLs) from indoor surveillance cameras, and (ii) noun-phrase chunking. We show that the HSCRF is capable of learning rich hierarchical models with reasonable accuracy in both fully and partially observed data cases.

On the recognition of abstract Markov policies

Abstraction plays an essential role in the way the agents plan their behaviours, especially to reduce the computational complexity of planning in large domains. However, the effects of abstraction in the inverse process – plan recognition – are unclear. In this paper, we present a method for recognising the agent’s behaviour in noisy and uncertain domains, and across multiple levels of abstraction. We use the concept of abstract Markov policies in abstract probabilistic planning as the model of the agent’s behaviours and employ probabilistic inference in Dynamic Bayesian Networks (DBN) to infer the correct policy from a sequence of observations. When the states are fully observable, we show that for a broad and often-used class of abstract policies, the complexity of policy recognition scales well with the number of abstraction levels in the policy hierarchy. For the partially observable case, we derive an efficient hybrid inference scheme on the corresponding DBN to overcome the exponential complexity.

Topic transition detection using hierarchical hidden Markov and semi-Markov models

In this paper we introduce a probabilistic framework to exploit hierarchy, structure sharing and duration information for topic transition detection in videos. Our probabilistic detection framework is a combination of a shot classification step and a detection phase using hierarchical probabilistic models. We consider two models in this paper: the extended Hierarchical Hidden Markov Model (HHMM) and the Coxian Switching Hidden semi-Markov Model (S-HSMM) because they allow the natural decomposition of semantics in videos, including shared structures, to be modeled directly, and thus enabling efficient inference and reducing the sample complexity in learning. Additionally, the S-HSMM allows the duration information to be incorporated, consequently the modeling of long-term dependencies in videos is enriched through both hierarchical and duration modeling. Furthermore, the use of the Coxian distribution in the S-HSMM makes it tractable to deal with long sequences in video. Our experimentation of the proposed framework on twelve educational and training videos shows that both models outperform the baseline cases (flat HMM and HSMM) and performances reported in earlier work in topic detection. The superior performance of the S-HSMM over the HHMM verifies our belief that duration information is an important factor in video content modeling.

Polymorphic malware detection using Hierarchical Hidden Markov Model

Binary signatures have been widely used to detect malicious software on the current Internet. However, this approach is unable to achieve the accurate identification of polymorphic malware variants, which can be easily generated by the malware authors using code generation engines. Code generation engines randomly produce varying code sequences but perform the same desired malicious functions. Previous research used flow graph and signature tree to identify polymorphic malware families. The key difficulty of previous research is the generation of precisely defined state machine models from polymorphic variants. This paper proposes a novel approach, using Hierarchical Hidden Markov Model (HHMM), to provide accurate inductive inference of the malware family. This model can capture the features of self-similar and hierarchical structure of polymorphic malware family signature sequences. To demonstrate the effectiveness and efficiency of this approach, we evaluate it with real malware samples. Using more than 15,000 real malware, we find our approach can achieve high true positives, low false positives, and low computational cost.

Discovery of activity structures using the hierarchical hidden Markov model

In building a surveillance system for monitoring people behaviours, it is important to understand the typical patterns of people's movement in the environment. This task is difficult when dealing with high-level behaviours. The flat model such as the hidden Markov model (HMM) is inefficient in differentiating between signatures of such behaviours. This paper examines structure learning for high-level behaviours using the hierarchical hidden Markov model (HHMM).We propose a two-phase learning algorithm in which the parameters of the behaviours at low levels are estimated first and then the structures and parameters of the behaviours at high levels are learned from multi-camera training data. Our algorithm is then evaluated using data from a real environment, demonstrating the robustness of the learned structure in recognising people's behaviour.

Efficient Coxian duration modelling for activity recognition in smart environment with the hidden semi-Markov model

In this paper, we exploit the discrete Coxian distribution and propose a novel form of stochastic model, termed as the Coxian hidden semi-Makov model (Cox-HSMM), and apply it to the task of recognising activities of daily living (ADLs) in a smart house environment. The use of the Coxian has several advantages over traditional parameterization (e.g. multinomial or continuous distributions) including the low number of free parameters needed, its computational efficiency, and the existing of closed-form solution. To further enrich the model in real-world applications, we also address the problem of handling missing observation for the proposed Cox-HSMM. In the domain of ADLs, we emphasize the importance of the duration information and model it via the Cox-HSMM. Our experimental results have shown the superiority of the Cox-HSMM in all cases when compared with the standard HMM. Our results have further shown that outstanding recognition accuracy can be achieved with relatively low number of phases required in the Coxian, thus making the Cox-HSMM particularly suitable in recognizing ADLs whose movement trajectories are typically very long in nature.

A marginalised Markov Chain Monte Carlo approach for model based analysis of EEG data

The work presented in this paper focuses on fitting of a neural mass model to EEG data. Neurophysiology inspired mathematical models were developed for simulating brain's electrical activity imaged through Electroencephalography (EEG) more than three decades ago. At the present well informative models which even describe the functional integration of cortical regions also exists. However, a very limited amount of work is reported in literature on the subject of model fitting to actual EEG data. Here, we present a Bayesian approach for parameter estimation of the EEG model via a marginalized Markov Chain Monte Carlo (MCMC) approach.

Uplink power control via adaptive Hidden-Markov-Model-Based pathloss estimation

Dynamic variations in channel behavior is considered in transmission power control design for cellular radio systems. It is well known that power control increases system capacity, improves Quality of Service (QoS), and reduces multiuser interference. In this paper, an adaptive power control design based on the identification of the underlying pathloss dynamics of the fading channel is presented. Formulating power control decisions based on the measured received power levels allows modeling the fading channel pathloss dynamics in terms of a Hidden Markov Model (HMM). Applying the online HMM identification algorithm enables accurate estimation of the real pathloss ensuring efficient performance of the suggested power control scheme.