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?
Infer probabilities, for concatenation of words
algorithms;machine learning;probability theory;natural language processing;statistics