What machine learning algorithm solves this problem?

Question

I want to solve this classification problem. Basically what I have is a sequence of feature vectors $\mathbf{x}_1,\mathbf{x}_2,\dots,\mathbf{x}_N$, and each feature vector is sequential in time. I want to predict the class label $y$ based on the observation of these $N$ feature vectors. The outcome label $y$ can be from a set of two possible classes $y \in \{A,B\}$. So my question is: What machine learning algorithm is best suited for this kind of problem? I know sequential learning like Hidden Markov Model, but they are more suitable for the case where each observation $\mathbf{x}_i$ corresponds to a hidden state $y_i$, versus here in my case only the final class label is needed. There is no hidden states along the time in my problem. So the goal is to predict the class label $y$ based on a sequence of feature vectors $\{\mathbf{x}_i\}_{i=1}^{N}$. Any suggestions?

Answer 1

A Hidden Markov Model without hidden states is just called a Markov Model, and it is a little simpler to implement. As alto mentioned, they give you a probability distribution for a sequence, so you can train one per class label, and pick the label that gives the highest probability for a sequence.

Another option is to try concatenating the vectors into a single $Nd$ vector per instance and using plain classification with some popular classifiers with few parameters (Decision trees, knn, MoG, etc). If the temporal relations are important for the classification, then the classifiers may well pick up on them in the form of correlations.

If this doesn't work, you can try different ways to extract a feature vector from your representation so that the temporal relations become more explicit. You can also define a metric between your instances and use Kernel methods.

Answer 2

A HMM can give you probabilities of a sequence, so you could just learn a HMM for each class. Classification of a new sequence then comes down to 1.) calculating the probability of the new sequence under each model, and 2.) picking the class which corresponds to the model which assigns the highest probability to the new sequence.

Answer 3

Have you tried simply treating the predictors as non-sequential? Maybe the ordinary cross-sectional treatment is sufficient with all the usual classification machinery (CART, Neural Nets, logistic, SVM, etc.)

Answer 4

You might consider Dynamic Bayesian Networks, an algorithm I've been reading about lately. I've been looking into it for predicting gene regulatory networks from time series expression data, which seems analogous to your situation. This paper has a good overview of the method.

Answer 5

I would strongly advise against using Markov Models, Hidden Markov Models, or Dynamic Bayesian networks for sequence classification. A number of discriminative methods are known to be much more effective for this task.

The most commonly used discriminative methods for sequence classification are based on sequence/string kernels.

The Sparse Spacial Sample Kernel and the Local Alignment Kernel are particularly effective for protein sequence classification, and it might be possible to adapt them for your task.

If you are working with continuous data, you can create alignment kernels by adapting the dynamic time warping algorithm to the Local Alignment Kernel setting.

One problem with kernel methods is that they can be computationally intensive. If you precompute the kernel matrix, you would need $O(N^2)$ kernel computations (where $N$ is the size of the dataset), and alignment-based kernels are generally $O(T^2)$ complexity (where $T$ is the length of the sequence). (Computing the Local Alignment kernel for a standard 4000-sequence protein dataset probably requires over six months of single-processor computation time.)

Techniques like the one mentioned the following paper can reduce the number of kernel computations: http://leon.bottou.org/papers/ertekin-bottou-giles-2011.

Other discriminative techniques involve specially constructed neural networks, as described in this paper: http://www.cs.bris.ac.uk/~flach/ECMLPKDD2012papers/1125783.pdf

Learning linear classifiers in large subsequence feature spaces using coordinate descent techniques has also been shown to be effective for both text data and protein sequences (http://arxiv.org/abs/1008.0528), but this technique might require discrete features.