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

Question

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?

Answer 1

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) $$

using gradient-descent.

Answer 2

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.

Answer 3

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?

Answer 4

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.

Answer 5

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.