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.

Human activity learning and segmentation using partially hidden discriminative models

Learning and understanding the typical patterns in the daily activities and routines of people from low-level sensory data is an important problem in many application domains such as building smart environments, or providing intelligent assistance. Traditional approaches to this problem typically rely on supervised learning and generative models such as the hidden Markov models and its extensions. While activity data can be readily acquired from pervasive sensors, e.g. in smart environments, providing manual labels to support supervised training is often extremely expensive. In this paper, we propose a new approach based on semi-supervised training of partially hidden discriminative models such as the conditional random field (CRF) and the maximum entropy Markov model (MEMM). We show that these models allow us to incorporate both labeled and unlabeled data for learning, and at the same time, provide us with the flexibility and accuracy of the discriminative framework. Our experimental results in the video surveillance domain illustrate that these models can perform better than their generative counterpart, the partially hidden Markov model, even when a substantial amount of labels are unavailable.

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 computational framework for nucleic acid sub-sequence identification

Identification of nucleic acid sub-sequences within larger background sequences is a fundamental need of the biology community. The applicability correlates to research studies looking for homologous regions, diagnostic purposes and many other related activities. This paper serves to detail the approaches taken leading to sub-sequence identification through the use of hidden Markov models and associated scoring optimisations. The investigation of techniques for locating conserved basal promoter elements correlates to promoter thus gene identification techniques. The case study centred on the TATA box basal promoter element, as such the background is a gene sequence with the TATA box the target. Outcomes from the research conducted, highlights generic algorithms for sub-sequence identification, as such these generic processes can be transposed to any case study where identification of a target sequence is required. Paths extending from the work conducted in this investigation have led to the development of a generic framework for the future applicability of hidden Markov models to biological sequence analysis in a computational context.

A pHMM-ANN based discriminative approach to promoter identification in prokaryote genomic contexts

The computational approach for identifying promoters on increasingly large genomic sequences has led to many false positives. The biological significance of promoter identification lies in the ability to locate true promoters with and without prior sequence contextual knowledge. Prior approaches to promoter modelling have involved artificial neural networks (ANNs) or hidden Markov models (HMMs), each producing adequate results on small scale identification tasks, i.e. narrow upstream regions. In this work, we present an architecture to support prokaryote promoter identification on large scale genomic sequences, i.e. not limited to narrow upstream regions. The significant contribution involved the hybrid formed via aggregation of the profile HMM with the ANN, via Viterbi scoring optimizations. The benefit obtained using this architecture includes the modelling ability of the profile HMM with the ability of the ANN to associate elements composing the promoter. We present the high effectiveness of the hybrid approach in comparison to profile HMMs and ANNs when used separately. The contribution of Viterbi optimizations is also highlighted for supporting the hybrid architecture in which gains in sensitivity (+0.3), specificity (+0.65) and precision (+0.54) are achieved over existing approaches.

Molecular genetics and comparative genomics reveal RNAi is not functional in malaria parasites

Techniques for targeted genetic disruption in Plasmodium, the causative agent of malaria, are currently intractable for those genes that are essential for blood stage development. The ability to use RNA interference (RNAi) to silence gene expression
would provide a powerful means to gain valuable insight into the pathogenic blood stages but its functionality in Plasmodium remains controversial. Here we have used various RNA-based gene silencing approaches to test the utility of RNAi in malaria
parasites and have undertaken an extensive comparative genomics search using profile hidden Markov models to clarify whether RNAi machinery
exists in malaria. These investigative approaches revealed that Plasmodium lacks the enzymology required for RNAi-based ablation of gene expression
and indeed no experimental evidence for RNAi was observed. In its absence, the most likely explanations for previously reported RNAi-mediated knockdown are either the general toxicity of introduced RNA (with global down-regulation of gene expression) or a specific antisense effect mechanistically distinct from RNAi, which will need systematic
analysis if it is to be of use as a molecular genetic tool for malaria parasites.

Design of multiple sequence alignment algorithms on parallel, distributed memory supercomputers

The challenge of comparing two or more genomes that have undergone recombination and substantial amounts of segmental loss and gain has recently been addressed for small numbers of genomes. However, datasets of hundreds of genomes are now common and their sizes will only increase in the future. Multiple sequence alignment of hundreds of genomes remains an intractable problem due to quadratic increases in compute time and memory footprint. To date, most alignment algorithms are designed for commodity clusters without parallelism. Hence, we propose the design of a multiple sequence alignment algorithm on massively parallel, distributed memory supercomputers to enable research into comparative genomics on large data sets. Following the methodology of the sequential progressiveMauve algorithm, we design data structures including sequences and sorted k-mer lists on the IBM Blue Gene/P supercomputer (BG/P). Preliminary results show that we can reduce the memory footprint so that we can potentially align over 250 bacterial genomes on a single BG/P compute node. We verify our results on a dataset of E.coli, Shigella and S.pneumoniae genomes. Our implementation returns results matching those of the original algorithm but in 1/2 the time and with 1/4 the memory footprint for scaffold building. In this study, we have laid the basis for multiple sequence alignment of large-scale datasets on a massively parallel, distributed memory supercomputer, thus enabling comparison of hundreds instead of a few genome sequences within reasonable time.

Robust recognition and segmentation of human actions using HMMs with missing observations

This paper describes the integration of missing observation data with hidden Markov models to create a framework that is able to segment and classify individual actions from a stream of human motion using an incomplete 3D human pose estimation. Based on this framework, a model is trained to automatically segment and classify an activity sequence into its constituent subactions during inferencing. This is achieved by introducing action labels into the observation vector and setting these labels as missing data during inferencing, thus forcing the system to infer the probability of each action label. Additionally, missing data provides recognition-level support for occlusions and imperfect silhouette segmentation, permitting the use of a fast (real-time) pose estimation that delegates the burden of handling undetected limbs onto the action recognition system. Findings show that the use of missing data to segment activities is an accurate and elegant approach. Furthermore, action recognition can be accurate even when almost half of the pose feature data is missing due to occlusions, since not all of the pose data is important all of the time.

A probabilistic framework for tracking in wide-area environments

Surveillance in wide-area spatial environments is characterised by complex spatial layouts, large state space, and the use of multiple cameras/sensors. To solve this problem, there is a need for representing the dynamic and noisy data in the tracking tasks, and dealing with them at different levels of detail. This requirement is particularly suited to the Layered Dynamic Probabilistic Network (LDPN), a special type of Dynamic Probabilistic Network (DPN). In this paper, we propose the use of LDPN as the integrated framework for tracking in wide-area environments. We illustrate, with the help of a synthetic tracking scenario, how the parameters of the LDPN can be estimated from training data, and then used to draw predictions and answer queries about unseen tracks at various levels of detail.

Tracking-as-recognition for articulated full-body human motion analysis

This paper addresses the problem of markerless tracking of a human in full 3D with a high-dimensional (29D) body model Most work in this area has been focused on achieving accurate tracking in order to replace marker-based motion capture, but do so at the cost of relying on relatively clean observing conditions. This paper takes a different perspective, proposing a body-tracking model that is explicitly designed to handle real-world conditions such as occlusions by scene objects, failure recovery, long-term tracking, auto-initialisation, generalisation to different people and integration with action recognition. To achieve these goals, an action's motions are modelled with a variant of the hierarchical hidden Markov model The model is quantitatively evaluated with several tests, including comparison to the annealed particle filter, tracking different people and tracking with a reduced resolution and frame rate.

Online context recognition in multisensor systems using Dynamic Time Warping

In this paper, we present our system for online context recognition of multimodal sequences acquired from multiple sensors. The system uses Dynamic Time Warping (DTW) to recognize multimodal sequences of different lengths, embedded in continuous data streams. We evaluate the performance of our system on two real world datasets: 1) accelerometer data acquired from performing two hand gestures and 2) NOKIA's benchmark dataset for context recognition. The results from both datasets demonstrate that the system can perform online context recognition efficiently and achieve high recognition accuracy.

Spatial activity recognition in a smart home environment using a chemotactic model

Spatial activity recognition is challenging due to the amount of noise incorporated during video tracking in everyday environments. We address the spatial recognition problem with a biologically-inspired chemotactic model that is capable of handling noisy data. The model is based on bacterial chemotaxis, a process that allows bacteria to change motile behaviour in relation to environmental gradients. Through adoption of chemotactic principles, we propose the chemotactic model and evaluate its performance in a smart house environment. The model exhibits greater than 99% recognition performance with a diverse six class dataset and outperforms the Hidden Markov Model (HMM). The approach also maintains high accuracy (90-99%) with small training sets of one to five sequences. Importantly, unlike other low-level spatial activity recognition models, we show that the chemotactic model is capable of recognising simple interwoven activities.

Human action segmentation via controlled use of missing data in HMMs

Segmentation of individual actions from a stream of human motion is an open problem in computer vision. This paper approaches the problem of segmenting higher-level activities into their component sub-actions using Hidden Markov Models modified to handle missing data in the observation vector. By controlling the use of missing data, action labels can be inferred from the observation vector during inferencing, thus performing segmentation and classification simultaneously. The approach is able to segment both prominent and subtle actions, even when subtle actions are grouped together. The advantage of this method over sliding windows and Viterbi state sequence interrogation is that segmentation is performed as a trainable task, and the temporal relationship between actions is encoded in the model and used as evidence for action labelling.

Recognising and monitoring high-level behaviours in complex spatial environments

The recognition of activities from sensory data is important in advanced surveillance systems to enable prediction of high-level goals and intentions of the target under surveillance. The problem is complicated by sensory noise and complex activity spanning large spatial and temporal extents. This paper presents a system for recognising high-level human activities from multi-camera video data in complex spatial environments. The Abstract Hidden Markov mEmory Model (AHMEM) is used to deal with noise and scalability The AHMEM is an extension of the Abstract Hidden Markov Model (AHMM) that allows us to represent a richer class of both state-dependent and context-free behaviours. The model also supports integration with low-level sensory models and efficient probabilistic inference. We present experimental results showing the ability of the system to perform real-time monitoring and recognition of complex behaviours of people from observing their trajectories within a real, complex indoor environment.