1
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ Nice solution. Can't wait to try it out. $\endgroup$ – Denis Kulagin Mar 6 '18 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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