Fix an alphabet $\Sigma$, and a set of words, $W = \{w_1,\dots,w_n\} \subseteq \Sigma^*$.

I have a randomized model that works like this: Alice generates a random sequence of words, using some probability distribution over the words, and then I get to see their concatenation -- but I don't see where the word boundaries are. I want to infer what distribution on words Alice is using.

More formally, Alice randomly picks a sequence of words, where each word is chosenly randomly and independently at random according to the probabilities $p(w_1),\dots,p(w_n)$; then Alice outputs the concatenation of these words.

With this model, we can work out the probability of any particular string $x \in \Sigma^*$. It is the sum of $p(s_1) \cdots p(s_k)$, taken over all sequences of words $s_1,\dots,s_k$ whose concatenation is $x$ and such that $s_i \in W$ for all $i$:

$$P(x) = \sum_{s_1 \dots s_k = x} p(s_1) \cdots p(s_k).$$

If I knew the probabilities $p(w_1),\dots,p(w_n)$ (the distribution Alice is using), it'd be easy to compute $P(x)$ using dynamic programming: for each prefix $x_{1..i}$ of $x$, I compute $P(x_{1..i})$.

But I have the inverse problem. I am given $w_1,\dots,w_n$ and $x \in \Sigma^*$, and I want to find probabilities $p(w_1),\dots,p(w_n)$ that make $P(x)$ as large as possible. How can I do that? Is there any efficient algorithm for this?

I would be happy with a practical algorithm that works well enough in practice, or a heuristic that gives an approximate solution.

I haven't managed to come up with any reasonable algorithm. In the special case where no word in $W$ is a prefix of any other word in $W$, then there is a unique decomposition of $x$ into a sequence of words from $W$, and it's easy to use maximum likelihood methods to compute the optimal probabilities: the probability $p(w)$ is just the number of times $w$ appears in this decomposition, divided by the number of words in the decomposition. However, in general there might be exponentially many ways of decomposing $x$ into a sequence of words from $W$, so this strategy doesn't work in general. Is there a better method?

  • $\begingroup$ Your question might be more suitable for cstheory. Note that $P(x)$ can be seen as a polynomial $P(p_1, ..., p_n)$ in the variables $p_1 = p(w_1)$, ... $p_n = p(w_n)$. Moreover, given $W$ and $x$, I know of a algorithm (which might not be optimal, but seems to be reasonable) to compute this polynomial . But I don't know how to address the next question: find the maximum of a polynomial $P(p_1, ..., p_n)$ under the assumption $p_1 + \cdots + p_n = 1$. $\endgroup$
    – J.-E. Pin
    Sep 24 '15 at 12:59

Your Answer

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

Browse other questions tagged or ask your own question.