= EM transition-count update on a tree
{c}
{title2=$K_{ab}^{\mathrm{new}}=N_{ab}/\sum_cN_{ac}$}
For a common unconstrained <Markov kernel> on the edges of a rooted <tree>, let $N_{ab}$ be the <conditional expectation> of the number of transitions $a\to b$, given observed leaves and the old <Markov kernel>. The <expectation-maximization algorithm> maximizes $\sum_{a,b}N_{ab}\log K_{ab}$ over row <probability distributions>, giving $K_{ab}^{\mathrm{new}}=N_{ab}/\sum_cN_{ac}$. A row with zero total count is unrestricted by this objective. <Belief propagation> computes the counts exactly on a <tree>.
Back to article page
