Which statistical classification algorithm can predict true/false for a sequence of inputs?

Given a sequence of inputs, I need to determine whether this sequence has a certain desired property. The property can only be true or false, that is, there are only two possible classes that a sequence can belong to.

The exact relationship between the sequence and the property is unclear, but I believe it is very consistent and should lend itself to statistical classification. I have a large number of cases to train the classifier on, although it might be slightly noisy, in the sense that there's a slight probability that a sequence is assigned the wrong class in this training set.

Example training data:

Sequence 1: (7 5 21 3 3) -> true
Sequence 2: (21 7 5 1) -> true
Sequence 3: (12 21 7 5 11 1) -> false
Sequence 4: (21 5 7 1) -> false
...


In rough terms, the property is determined by the set of values in the sequence (e.g. the presence of an "11" means that the property will almost certainly be false), as well as the order of the values (e.g. "21 7 5" significantly increases the chance that the property is true).

After training, I should be able to give the classifier a previously unseen sequence, like (1 21 7 5 3), and it should output its confidence that the property is true. Is there a well-known algorithm for training a classifier with this kind of inputs/outputs?

I have considered the naive Bayesian classifier (which is not really adaptable to the fact that the order matters, at least not without severely breaking the assumption that the inputs are independent). I've also investigated the hidden Markov model approach, which appears to be inapplicable because only a single output is available, instead of one output per input. What did I miss?

-
Do you have way to measure the distance between a pair of sequences? Is the min and/or max sequence length known? – Craig Wright Dec 1 '11 at 21:15
@CraigWright There is no applicable distance measure that I can think of. A maximum length on the order of 12 and a minimum around 4 may be assumed. Also, there are about 30 distinct values (they're not unbounded naturals; just a fairly small set of possibilities) – romkyns Dec 1 '11 at 21:23
What are your multiple response variables you mention? I was reading your problem as this is a binary output and perhaps you could simply create dummy variables Var1.1, Var1.12, ..., Var12.12 – B_Miner Dec 1 '11 at 21:38
@B_Miner I might be misunderstanding how HMM works, but it seems that it works as follows: I feed it my input sequence (a b c d e) and it outputs a hidden sequence best matching that, namely (a' b' c' d' e'). I don't think the dummy variables would solve this; I need a true/false classification for the entire sequence. – romkyns Dec 1 '11 at 21:42
@romkyns, that's not quite how a HMM works. A HMM is a probabilistic process. Given a sequence $s$ and a HMM $M$, you can compute the probability that $M$ would output $s$ (using dynamic programming; the forward algorithm). Also, given a set of training sequences, you can find the HMM $M$ that has the maximum likelihood of producing those training sequences (using the Baum-Welch algorithm). So HMMs could well be something to try here. There will be some details to fill in, though. – D.W. Dec 1 '11 at 23:22

You could try probabilistic approaches similar to the naive Bayes classifier but with weaker assumptions. For example, instead of making the strong independence assumption, make a Markov assumption:

$$p(x \mid c) = p(x_0 \mid c)\prod_t p(x_t \mid x_{t - 1}, c)$$

$c$ is your class label, $x$ is your sequence. You need to estimate two conditional distributions, one for $c = 1$ and one for $c = 0$.

By Bayes' rule:

$$p(c = 1 \mid x) = \frac{p(x \mid c = 1) p(c = 1)}{p(x \mid c = 1) p(c = 1) + p(x \mid c = 0) p(c = 0)}.$$

Which distributions to pick for $p(x_t \mid x_{t - 1}, c)$ depends on which other assumptions you can make about the sequences and how much data you have available.

For example, you could use:

$$p(x_t \mid x_{t - 1}, c) = \frac{\pi(x_t, x_{t - 1}, c)}{\sum_i \pi(x_i, x_{t - 1}, c)}$$

With distributions like this, if there are 21 different numbers occurring in your sequences, you would have to estimate $21 \cdot 21 \cdot 2 = 882$ parameters $\pi(x_t, x_t, c)$ plus $21 \cdot 2 = 42$ parameters for $p(x_0 \mid c)$ plus $2$ parameters for $p(c)$.

If the assumptions of your model are not met, it can help to fine-tune the parameters directly with respect to the classification performance, for example by minimizing the average log-loss

$$-\frac{1}{\#\mathcal{D}} \sum_{(x, c) \in \mathcal{D}} \log p(c \mid x)$$

-
(+1) I like this one. However, one might need awful amounts of data to get reliable estimates for all $p(x_t|x_{t-1},c)$ – steffen Dec 2 '11 at 9:31
If you can make more assumptions about the distributions involved, you may get away with much less parameters. If, for example, you knew that $p(x_t \mid x_{t - 1}, c)$ was binomial and $E[x_t \mid x_{t - 1}, c] = x_{t - 1}$, you would have to estimate only two parameters, one for each value of $c$. Of course, if you can't make any assumptions and don't have enough data, there is not a lot you can do. There's no free lunch. – Lucas Dec 2 '11 at 13:06

I would suggest that you define some features, and then pick a machine learning algorithm to apply to those features.

Features: Basically, each feature should be something that can be computed from a particular sequence, and that you think may be relevant to whether the sequence has the property or not. Based upon your description, you might consider features such as the following:

• "Bag of numbers". You might count how many times each possible number appears in the sequence. For instance, suppose each sequence is made out of the numbers 1-30 only. Then you can generate 30 features; the $i$th feature counts how many times the number $i$ appears in the sequence. For instance, the sequence (7 5 21 3 3) generates the feature vector (0,0,2,0,1,0,1,0,...,0,1,0,...,0).

• "Bag of digrams." A digram is a pair of consecutive numbers. Given a sequence, you can extract all of its digrams. Then you could count how many times each possible digram appears. For instance, the sequence (7 5 21 3 3) has the following as its digrams: 7 5, 5 21, 21 3, and 3 3. Assuming the sequence is made out of the numbers 1-30, there are $30^2$ possible digrams, so you obtain $30^2$ features. Given a sequence, you can generate this feature vector.

• "Bag of trigrams." You could also consider trigrams, which is a subsequence of three consecutive numbers from the original sequence. You can do the same as above.

If you use the above features, you can then extract $d=30+30^2+30^3$ features from each sequence. In other words, to each sequence, you associate a $d$-dimensional feature vector, which is the collection of features. Once you have this, you can throw away the original sequences. For instance, your training set becomes a bunch of input/output-pairs, where the input is the feature vector (corresponding to some sequence from your training set) and the output is a boolean (indicating whether that sequence had the property or not).

Another variation on the above idea is to use "set of X" instead of "bag of X". For instance, instead of counting how many times each number $i$ appears, you could simply generate a boolean that indicates whether the number $i$ has appeared at least once or not. This may or may not give better results. In general, you can experiment with the set of features you use, to figure out which ones give the best results (for instance, maybe you drop the "bag of trigrams"; or maybe you can come up with some other ideas to try).

Machine learning algorithm: I'm not qualified to give you advice about how to select a machine learning algorithm; there are many possibilities. But in general you are going to apply the learning algorithm to your training set (the input/output pairs of features/booleans), and try to use it to predict which of the values in the test set have the property. Your selection of machine learning algorithm may depend upon several factors, including how the size of the training set compares relative to $d$ (the number of features). Your best bet may be to try several machine learning algorithms and see which works the best. You might want to include Support Vector Machines (SVMs) as one of the algorithms you try.

-
The first attempt that I actually implemented was a "bag of trigrams" with naive bayesian classification. The results are encouraging but not great. I thought this could be related to the fact that trigrams are not at all independent: if I have "1 2 3" then I'm also very likely to have a "2 3 *" trigram. Perhaps I should experiment with the exact features some more. – romkyns Dec 1 '11 at 23:45
Experimenting more, both with different feature sets and with different learning algorithms, is a good idea. Also, based on your problem description, you may want to add features for appearance of each individual number (bag of words, not just bag of trigrams): if you use only trigrams, you are making it harder for the machine learning algorithm to learn facts like "sequences that contain 11 almost certainly do not have the property". – D.W. Dec 2 '11 at 10:46

What you're effectively doing is hypothesis testing on time series. HMMs would work for you, though you would have to adapt them to your particular case.

Honestly, if you can't write down some kind of mathematical description of what you're trying to detect, you're not going to get very far. Perhaps you can tell us about what kind of feature you're expecting to see?

-
Machine learning has shown us that we can get very far without having any idea about what to look for. – bayerj Dec 7 '11 at 7:25

Given a max length of 12 on the sequence, then a neural network with 12 inputs and one output may work, but you would have to pad the end of each sequence with zeroes or some inert value.

-

Have you tried using Bayesian networks? That's the first thing I think of when I need to fuse multiple pieces of data (coming in one at a time) to arrive at the probabilities of a random variable.

Bayesian networks don't rely on the independence assumption that naive Bayes does.

BTW, hidden Markov models are a special case of Bayesian networks.

-