Probabilistic sequence clustering with spectral learning

In this paper, we derive two novel learning algorithms for time series clustering; namely for learning mixtures of Markov Models and mixtures of Hidden Markov Models. Mixture models are special latent variable models that require the usage of local search heuristics such as Expectation Maximization (EM) algorithm, that can only provide locally optimal solutions. In contrast, we make use of the spectral learning algorithms, recently popularized in the machine learning community. Under mild assumptions, spectral learning algorithms are able to estimate the parameters in latent variable models by solving systems of equations via eigendecompositions of matrices or tensors of observable moments. As such, spectral methods can be viewed as an instance of the method of moments for parameter estimation, an alternative to maximum likelihood. The popularity stems from the fact that these methods provide a computationally cheap and local optima free alternative to EM. We conduct classification experiments on human action sequences extracted from videos, clustering experiments on motion capture data and network traffic data to illustrate the viability of our approach. We conclude that the spectral methods are a practical and useful alternative in terms of computational effort and solution quality to standard iterative techniques such as EM in several sequence clustering applications.     

Discriminative Learning for Dynamic State Prediction

We consider the problem of predicting a sequence of real-valued multivariate states that are correlated by some unknown dynamics, from a given measurement sequence. Although dynamic systems such as the State-Space Models are popular probabilistic models for the problem, their joint modeling of states and observations, as well as the traditional generative learning by maximizing a joint likelihood may not be optimal for the ultimate prediction goal. In this paper, we suggest two novel discriminative approaches to the dynamic state prediction: 1) learning generative state-space models with discriminative objectives and 2) developing an undirected conditional model. These approaches are motivated by the success of recent discriminative approaches to the structured output classification in discrete-state domains, namely, discriminative training of Hidden Markov Models and Conditional Random Fields (CRFs). Extending CRFs to real multivariate state domains generally entails imposing density integrability constraints on the CRF parameter space, which can make the parameter learning difficult. We introduce an efficient convex learning algorithm to handle this task. Experiments on several problem domains, including human motion and robot-arm state estimation, indicate that the proposed approaches yield high prediction accuracy comparable to or better than state-of-the-art methods.     

基于一阶马尔可夫链的实验数据序列分类模型

为了对在线实验系统产生的实验数据序列进行分析,引入一阶马尔可夫链. 通过人工分类把实验数据分为学习积极和懒散作弊两类,分别构建马尔可夫链模型. 根据输出概率判定测试数据来自哪一个模型的可能性较大. 最后讨论了状态的平稳分布情况. 实验结果表明,基于马尔可夫链的分类模型具有较高的正确率.     

Recognising online spatial activities using a bioinformatics inspired sequence alignment approach

In this paper we address the problem of recognising embedded activities within continuous spatial sequences obtained from an online video tracking system. Traditionally, continuous data streams such as video tracking data are buffered with a sliding window applied to the buffered data stream for activity detection. We introduce an algorithm based on Smith-Waterman (SW) local alignment from the field of bioinformatics that can locate and accurately quantify embedded activities within a windowed sequence. The modified SW approach utilises dynamic programming with two dimensional spatial data to quantify sequence similarity and is capable of recognising sequences containing gaps and significant amounts of noise. A more efficient SW formulation for online recognition, called Online SW (OSW), is also developed. Through experimentation we show that the OSW algorithm can accurately and robustly recognise manually segmented activity sequences as well as embedded sequences from an online tracking system. To benchmark the classification performance of OSW we compare the approach to dynamic time warping (DTW) and the discrete hidden Markov model (HMM). Results demonstrate that OSW produces higher precision and recall than both DTW and the HMM in an online recognition context. With accurately segmented sequences the SW approach produces results comparable to DTW and superior to the HMM. Finally, we confirm the robust property of the SW approach by evaluating it with sequences containing artificially incorporated noise.     

Cost-sensitive learning with conditional Markov networks

There has been a recent, growing interest in classification and link prediction in structured domains. Methods such as conditional random fields and relational Markov networks support flexible mechanisms for modeling correlations due to the link structure. In addition, in many structured domains, there is an interesting structure in the risk or cost function associated with different misclassifications. There is a rich tradition of cost-sensitive learning applied to unstructured (IID) data. Here we propose a general framework which can capture correlations in the link structure and handle structured cost functions. We present two new cost-sensitive structured classifiers based on maximum entropy principles. The first determines the cost-sensitive classification by minimizing the expected cost of misclassification. The second directly determines the cost-sensitive classification without going through a probability estimation step. We contrast these approaches with an approach which employs a standard 0/1-loss structured classifier to estimate class conditional probabilities followed by minimization of the expected cost of misclassification and with a cost-sensitive IID classifier that does not utilize the correlations present in the link structure. We demonstrate the utility of our cost-sensitive structured classifiers with experiments on both synthetic and real-world data.     

Online Feature Selection of Class Imbalance via PA Algorithm

Imbalance classification techniques have been frequently applied in many machine learning application domains where the number of the majority (or positive) class of a dataset is much larger than that of the minority (or negative) class. Meanwhile, feature selection (FS) is one of the key techniques for the high-dimensional classification task in a manner which greatly improves the classification performance and the computational efficiency. However, most studies of feature selection and imbalance classification are restricted to off-line batch learning, which is not well adapted to some practical scenarios. In this paper, we aim to solve high-dimensional imbalanced classification problem accurately and efficiently with only a small number of active features in an online fashion, and we propose two novel online learning algorithms for this purpose. In our approach, a classifier which involves only a small and fixed number of features is constructed to classify a sequence of imbalanced data received in an online manner. We formulate the construction of such online learner into an optimization problem and use an iterative approach to solve the problem based on the passive-aggressive (PA) algorithm as well as a truncated gradient (TG) method. We evaluate the performance of the proposed algorithms based on several real-world datasets, and our experimental results have demonstrated the effectiveness of the proposed algorithms in comparison with the baselines.     

基于EM的启动子序列半监督学习

启动子的预测对于基因的定位有重要意义.已有多种对启动子进行预测的算法,涉及到信号搜索、内容搜索和CpG岛搜索等多种策略.基于马尔可夫模型的启动子分类方法也有研究,其中的转移概率都是直接通过统计已标号训练样本序列得来的.将半监督学习思想引入启动子序列分析中,推导出转移概率等参数的最大似然估计公式.实验中将待测试基因序列片段同已标号训练样本混合,利用得出的参数值对基因序列片段进行识别,使用少量的已标号的样本数据能得出较好的启动子识别结果.     

一种基于改进CP网络与HMM相结合的混合音素识别方法

提出了一种基于改进对偶传播（ＣＰ）神经网络与隐驰尔可夫模型（ＨＭＭ）相结合的混合音素识别方法．这一方法的特点是用一个具有有指导学习矢量量化（ＬＶＱ）和动态节点分配等特性的改进的ＣＰ网络生成离散ＨＭＭ音素识别系统中的码书。因此,用这一方法构造的混合音素识别系统中的码书实际上是一个由有指导ＬＶＱ算法训练的具有很强分类能力的高性能分类器,这就意味着在用ＨＭＭ对语音信号进行建模之前,由码书产生的观测序列中     

A Hidden Markov Model approach for appearance-based 3D object recognition

In this paper, a new appearance-based 3D object classification method is proposed based on the Hidden Markov Model (HMM) approach. Hidden Markov Models are a widely used methodology for sequential data modelling, of growing importance in the last years. In the proposed approach, each view is subdivided in regular, partially overlapped sub-images, and wavelet coefficients are computed for each window. These coefficients are then arranged in a sequential fashion to compose a sequence vector, which is used to train a HMM, paying particular attention to the model selection issue and to the training procedure initialization. A thorough experimental evaluation on a standard database has shown promising results, also in presence of image distortions and occlusions, the latter representing one of the most severe problems of the recognition methods. This analysis suggests that the proposed approach represents an interesting alternative to classic appearance-based methods to 3D object classification.     

Temporal and spatial data mining with second-order hidden markov models

In the frame of designing a knowledge discovery system, we have developed stochastic models based on high-order hidden Markov models. These models are capable to map sequences of data into a Markov chain in which the transitions between the states depend on the n previous states according to the order of the model. We study the process of achieving information extraction from spatial and temporal data by means of an unsupervised classification. We use therefore a French national database related to the land use of a region, named Ter Uti, which describes the land use both in the spatial and temporal domain. Land-use categories (wheat, corn, forest, ...) are logged every year on each site regularly spaced in the region. They constitute a temporal sequence of images in which we look for spatial and temporal dependencies. The temporal segmentation of the data is done by means of a second-order Hidden Markov Model (HMM2) that appears to have very good capabilities to locate stationary segments, as shown in our previous work in speech recognition. The spatial classification is performed by defining a fractal scanning of the images with the help of a Hilbert–Peano curve that introduces a total order on the sites, preserving the relation of neighborhood between the sites. We show that the HMM2 performs a classification that is meaningful for the agronomists. Spatial and temporal classification may be achieved simultaneously by means of a two levels HMM2 that measures the a posteriori probability to map a temporal sequence of images onto a set of hidden classes.     

混合连接时间/注意力机制端到端语音识别

为提高常规自动语音识别(ASR)系统的精度,提出基于隐式马尔可夫模型混合连接时间分类/注意力机制的端到端ASR系统设计方法。首先,针对可观测时变序列语音识别过程中存在的连续性强、词汇量大的语音识别难点,基于隐式马尔可夫模型对语音识别过程进行模拟,实现了语音识别模型参数化;其次,使用连接时间分类目标函数作为辅助任务,在多目标学习框架中训练语音识别过程的关注模型编码器,可降低序列级连接时间分类目标近似度,实现语音识别过程精度提升;最后,通过在自建语音识别库上的仿真实验,验证所提算法在识别效率和精度上的性能优势。     

符号序列多阶Markov分类

针对基于固定阶Markov链模型的方法不能充分利用不同阶次子序列结构特征的问题,提出一种基于多阶Markov模型的符号序列贝叶斯分类新方法。首先,建立了基于多阶次Markov模型的条件概率分布模型;其次,提出一种附后缀表的n-阶子序列后缀树结构和高效的树构造算法,该算法能够在扫描一遍序列集过程中建立多阶条件概率模型;最后,提出符号序列的贝叶斯分类器,其训练算法基于最大似然法学习不同阶次模型的权重,分类算法使用各阶次的加权条件概率进行贝叶斯分类预测。在三个应用领域实际序列集上进行了系列实验,结果表明：新分类器对模型阶数变化不敏感;与使用固定阶模型的支持向量机等现有方法相比,所提方法在基因序列与语音序列上可以取得40%以上的分类精度提升,且可输出符号序列Markov模型最优阶数参考值。     

Host-based intrusion detection using dynamic and static behavioral models

Intrusion detection has emerged as an important approach to network security. In this paper, we adopt an anomaly detection approach by detecting possible intrusions based on program or user profiles built from normal usage data. In particular, program profiles based on Unix system calls and user profiles based on Unix shell commands are modeled using two different types of behavioral models for data mining. The dynamic modeling approach is based on hidden Markov models (HMM) and the principle of maximum likelihood, while the static modeling approach is based on event occurrence frequency distributions and the principle of minimum cross entropy. The novelty detection approach is adopted to estimate the model parameters using normal training data only, as opposed to the classification approach which has to use both normal and intrusion data for training. To determine whether or not a certain behavior is similar enough to the normal model and hence should be classified as normal, we use a scheme that can be justified from the perspective of hypothesis testing. Our experimental results show that the dynamic modeling approach is better than the static modeling approach for the system call datasets, while the dynamic modeling approach is worse for the shell command datasets. Moreover, the static modeling approach is similar in performance to instance-based learning reported previously by others for the same shell command database but with much higher computational and storage requirements than our method.     

Reusing training data with generative/discriminative hybrid model for practical acceleration-based activity recognition

This paper proposes a new daily activity recognition method that can learn an activity classification model with small quantities of training data by sharing training data among different activity classes. Many existing activity recognition studies employ a supervised machine learning approach and thus require an end user’s labeled training data, this approach places a large burden on the user. In this study, we assume that a user wears sensors (accelerometers) on several parts of the body such as the hands, waist, and thigh, and we attempt to share sensor data obtained from only selected accelerometers (e.g., only waist and thigh sensors) among two different activity classes based on a sensor data similarity measure. This approach permits us to correctly learn parameters of an activity classification model by using sufficient quantities of shared sensor data without adding new training data. We confirmed the effectiveness of our method by using 48 h of sensor data obtained from 20 participants, and achieved a good recognition accuracy.     

Modelling sequences using pairwise relational features

We propose a new framework for the modelling of sequences that generalizes popular models such as hidden Markov models. Our approach relies on the use of relational features that describe relationships between observations in a sequence. The use of such relational features allows implementing a variety of models from traditional Markovian models to richer models that exhibit robustness to various kinds of deformation in the input signal. We derive inference and training algorithms for our framework and provide experimental results on on-line handwriting data. We show how the models we propose may be useful for a variety of traditional tasks such as sequence classification but also for applications more related to diagnosis such as partial matching of sequences.     

Markov constraints: steerable generation of Markov sequences

Markov chains are a well known tool to model temporal properties of many phenomena, from text structure to fluctuations in economics. Because they are easy to generate, Markovian sequences, i.e. temporal sequences having the Markov property, are also used for content generation applications such as text or music generation that imitate a given style. However, Markov sequences are traditionally generated using greedy, left-to-right algorithms. While this approach is computationally cheap, it is fundamentally unsuited for interactive control. This paper addresses the issue of generating steerable Markovian sequences. We target interactive applications such as games, in which users want to control, through simple input devices, the way the system generates a Markovian sequence, such as a text, a musical sequence or a drawing. To this aim, we propose to revisit Markov sequence generation as a branch and bound constraint satisfaction problem (CSP). We propose a CSP formulation of the basic Markovian hypothesis as elementary Markov Constraints (EMC). We propose algorithms that achieve domain-consistency for the propagators of EMCs, in an event-based implementation of CSP. We show how EMCs can be combined to estimate the global Markovian probability of a whole sequence, and accommodate for different species of Markov generation such as fixed order, variable-order, or smoothing. Such a formulation, although more costly than traditional greedy generation algorithms, yields the immense advantage of being naturally steerable, since control specifications can be represented by arbitrary additional constraints, without any modification of the generation algorithm. We illustrate our approach on simple yet combinatorial chord sequence and melody generation problems and give some performance results.     

Denoising and recognition using hidden Markov models with observation distributions modeled by hidden Markov trees

Hidden Markov models have been found very useful for a wide range of applications in machine learning and pattern recognition. The wavelet transform has emerged as a new tool for signal and image analysis. Learning models for wavelet coefficients have been mainly based on fixed-length sequences, but real applications often require to model variable-length, very long or real-time sequences. In this paper, we propose a new learning architecture for sequences analyzed on short-term basis, but not assuming stationarity within each frame. Long-term dependencies will be modeled with a hidden Markov model which, in each internal state, will deal with the local dynamics in the wavelet domain, using a hidden Markov tree. The training algorithms for all the parameters in the composite model are developed using the expectation-maximization framework. This novel learning architecture could be useful for a wide range of applications. We detail two experiments with artificial and real data: model-based denoising and speech recognition. Denoising results indicate that the proposed model and learning algorithm are more effective than previous approaches based on isolated hidden Markov trees. In the case of the ‘Doppler’ benchmark sequence, with 1024 samples and additive white noise, the new method reduced the mean squared error from 1.0 to 0.0842. The proposed methods for feature extraction, modeling and learning, increased the phoneme recognition rates in 28.13%, with better convergence than models based on Gaussian mixtures.     

Structured prediction with reinforcement learning

We formalize the problem of Structured Prediction as a Reinforcement Learning task. We first define a Structured Prediction Markov Decision Process (SP-MDP), an instantiation of Markov Decision Processes for Structured Prediction and show that learning an optimal policy for this SP-MDP is equivalent to minimizing the empirical loss. This link between the supervised learning formulation of structured prediction and reinforcement learning (RL) allows us to use approximate RL methods for learning the policy. The proposed model makes weak assumptions both on the nature of the Structured Prediction problem and on the supervision process. It does not make any assumption on the decomposition of loss functions, on data encoding, or on the availability of optimal policies for training. It then allows us to cope with a large range of structured prediction problems. Besides, it scales well and can be used for solving both complex and large-scale real-world problems. We describe two series of experiments. The first one provides an analysis of RL on classical sequence prediction benchmarks and compares our approach with state-of-the-art SP algorithms. The second one introduces a tree transformation problem where most previous models fail. This is a complex instance of the general labeled tree mapping problem. We show that RL exploration is effective and leads to successful results on this challenging task. This is a clear confirmation that RL could be used for large size and complex structured prediction problems.     

面向多标签图数据的主动学习

主动学习已经广泛应用于图数据的研究,但应用于多标签图数据的分类较为少见。结合基于误差界最小化的主动学习,给出了一种多标签图数据的分类方法,即通过多标签分类与局部和全局的一致性学习(LLGC)得到一系列目标方程,并将其用于最小化直推式的拉德马赫复杂度,得到最小泛化误差上界,从而在图上获取少量的但蕴含巨大信息量的节点。实验证明,应用该方法的多标签分类器的输出有很高的精确度。     

Harmony search-based hidden Markov model optimization for online classification of single trial eegs during motor imagery tasks

This paper presents an improved method based on single trial EEG data for the online classification of motor imagery tasks for brain-computer interface (BCI) applications. The ultimate goal of this research is the development of a novel classification method that can be used to control an interactive robot agent platform via a BCI system. The proposed classification process is an adaptive learning method based on an optimization process of the hidden Markov model (HMM), which is, in turn, based on meta-heuristic algorithms. We utilize an optimized strategy for the HMM in the training phase of time-series EEG data during motor imagery-related mental tasks. However, this process raises important issues of model interpretation and complexity control. With these issues in mind, we explore the possibility of using a harmony search algorithm that is flexible and thus allows the elimination of tedious parameter assignment efforts to optimize the HMM parameter configuration. In this paper, we illustrate a sequential data analysis simulation, and we evaluate the optimized HMM. The performance results of the proposed BCI experiment show that the optimized HMM classifier is more capable of classifying EEG datasets than ordinary HMM during motor imagery tasks.