1
$\begingroup$

Given $N$ sequences of codes $$ c_1 \rightarrow c_3 \rightarrow c_2 \\ ... \\ c_3 \rightarrow c_5 \rightarrow c_7 \rightarrow c_8 \rightarrow c_1 $$ where the codes are from set $\psi = \{c_1, c_2, ...,c_n\}$, I need to construct the most likely sequence given an unordered subset of codes from $\psi$.

So, if the subset which needs to be ordered is $\{c_3, c_6, c_8\}$, and based on the above sequences $c_6 \rightarrow c_8$ and $c_8 \rightarrow c_3$ were more common, then the output sequence should be $c_6 \rightarrow c_8 \rightarrow c_3$.

I am not looking for sum of weights on the path to be minimized. The sequence of codes should be used to infer the direction $c_i \rightarrow c_j$ or $c_j \rightarrow c_i$ based on number of transitions in each direction.

$\endgroup$

1 Answer 1

0
$\begingroup$

You could frame your problem as follows: You have a set of N time series $c_i \to c_j \to \ldots \to c_k$ to which you fit a single time series model $M$. Then, given your set of codes, you want to order them such that your model $M$ gives them the highest probability.

So there are two steps, first fitting the model and second the ordering.

Fitting the model: There are many possible models you could try, e.g. a simple Markov chain or some Hidden Markov model.

The ordering: Now, if your set of codes contains $K$ codes, you would have to apply your model to $K!$ possible orderings to find the one that gives the highest probability. I don't know how large your sets are, but this becomes impossible quite quickly (e.g. $10! = 3628800$). Thus, if your set of codes is large, you should think about some greedy approach. For example, if you have as model a Markov chain, you could first find the most likely consecutive pair in your set, then attach to the front and end the most likely codes from the rest of your set, and then continue in this way to grow the chain. A more general approach, using Bayesian optimization is described here. In this paper, you find pointers to other methods. In general, this is a field of active research and you might even want to search on google scholar for e.g. "optimization over permutations". Note that the choice of a good optimization over your permutation space depends on the objective function, i.e. the model $M$ you have fitted. Different models would lead to different preferable optimization schemes. The paper mentioned above, using Bayesian optimization, is a more general approach, so while applicable, there might be better techniques.

$\endgroup$
2
  • $\begingroup$ Your framing is correct. If the N given sequences are represented on a directed graph with edge weights showing the number of times the a pair of nodes were traversed in that order, I would like the objective when selecting the final sequence to be maximizing the minimum weight. Can you point me to a greedy approach for this so that I can tweak for the objective of interest? $\endgroup$
    – ironv
    Commented Jun 16, 2022 at 5:31
  • $\begingroup$ @ironv Well, this is different, you know describe a Minmax problem. $\endgroup$
    – frank
    Commented Jun 16, 2022 at 5:54

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.