#dynamic-programming

Question 1: Single choice

mediumAI-checkedProbabilistic & Graphical Models

For an HMM with $n$ hidden states and $T$ observations, summing $P(O, Q)$ over all hidden sequences $Q$ takes about $(2T)\,n^T$ multiplications, but the forward algorithm needs only about $2n^2T$ . Where does the saving come from?

Each $\alpha$ is computed once and reused by every path through that state1
It follows only the most likely hidden sequence and ignores the others2
It leaves out the emission probabilities, which halves the work3
It estimates $P(O)$ from a small random sample of hidden sequences4

#dynamic-programming

Timed test