# Sequence prediction: ambiguity in training set

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.

• 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? – Wayne Mar 4 '18 at 17:04
• Could be A or B and there is no way to tell which one. (first option of yours) – Denis Kulagin Mar 4 '18 at 18:07

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:

library(PST)
dat <- c("A-A-Z-Z",
"B-A-Z-Z",
"A-A-Z-A",
"B-A-Z-A",
"B-A-Z-D"
)

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",
"A-A-Z-F",
"B-B-Z-F",
"A-B-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
##         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