Directly calculating P(e ij ) by summing the probabilities of all paths passing through e ij is an NP problem (Rabiner, 1989), and is intractable if the query is long.
we use the forwardbackward algorithm (Bishop, 2006) to calculate P(e ij ) in a more efficient way.