Sequence prediction: ambiguity in training set

Question

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.

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:

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

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