There is a set of sequences (train set), where each element is one or multiple tags:

A, B -- A -- Z -- Z, A
B    -- A -- Z -- D

Given a new sequence:

A, B -- A, B -- Z -- F

How to determine the probabilities of each of its instances, like:

B -- A -- Z -- F    0.65
A -- A -- Z -- F    0.34
A -- B -- Z -- F    0.01
B -- B -- Z -- F    0

N.B. Let's call $X(X_1, ..., X_n)$ an instance of sequence $S(S_1, ..., S_n)$ iff for each $1 \le i \le n$: $X_i \in S_i$.

N.B. Instances of the new sequence could have never occurred in the training set. Still algorithm has to produce a discrete probability distribution.

  • $\begingroup$ To clarify, by "A, B" do you mean that state could be A or B, you can't tell which, or do you mean you actually have examples where it was A and examples where it was B? $\endgroup$
    – Wayne
    Mar 4, 2018 at 17:04
  • $\begingroup$ Could be A or B and there is no way to tell which one. (first option of yours) $\endgroup$ Mar 4, 2018 at 18:07

1 Answer 1


I don't know how you obtained the shown probabilities. However, a possibility would be to fit a probabilistic suffix tree to the observed sequences and use the tree to predict the likelihood of the instances of the new sequence.

I illustrate below using the PST R package. Since there are 4 instances of your first sequence, I input them as four sequences with each a weight of .25. PST automatically accounts for those weights. Also, when defining the state sequence object with the TraMineR seqdef function, I explicitly provide the alphabet to include the non-observed state F:

dat <- c("A-A-Z-Z",

weights <- c(.25,.25,.25,.25,1)
alph <- c("A","B","D","Z","F")

s <- seqdef(dat,weights = weights, alphabet=alph)
seqiplot(s) ## i-plot of the instances

## Growing a tree of order L=3
pst <- pstree(s, L=3, ymin=.001)

and now we define the 4 instances of the new sequence and predict their distribution as follows

newdat <- c("B-A-Z-F",
new.s <- seqdef(newdat, alphabet = alphabet(s))
pred <- predict(pst,new.s) ## likelihood of each instance
## Normalize by sum of likelihoods to get distribution of the 4 instances
prob <- as.matrix(round(pred/sum(pred),3))
rownames(prob) <- newdat
##         prob
## B-A-Z-F 0.714
## A-A-Z-F 0.286
## B-B-Z-F 0.000
## A-B-Z-F 0.000

For more details about PSTs see Gabadinho & Ritschard (2016).

  • $\begingroup$ Nice solution. Can't wait to try it out. $\endgroup$ Mar 6, 2018 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.