what's the greedy or dynamic programming approach for this?

Question

Suppose we are making sentences by using bi-gram, which means probability of appearance of each word is dependent on previous word. The probability of a sentence is multiple of probability of words

P(sentence) = p(t0)*multiple from i=1 to i=n p(ti|ti-1)

we have probability matrix which we can use to determine P(ti|ti-1), we want to find the most probable sentence

Is there any greedy or dynamic programming approach for it?

Answer 1

You can use Viterbi algorithm. Your states is a words (t0, t2, t7, ...). Your initial state is t0 and you have a matrix with transition probabilities a_i,j = P(tj|ti), you have no "observations", so you can not think about P(y|k). For every length (t) and every word (t_k) you will find V_t,k that is the probability of the most probable sentence with t words and word t_k at the sentence's end.