On 8/24/10 12:29 AM, wren ng thornton wrote:
All of these are the same algorithm, just with different (augmented)
semirings. In order to prevent underflow for very small probabilities,
we usually run these algorithms with probabilities in the log-domain.
Those variants are also the same algorithm, just taking the image of the
semiring under the logarithm functor:
Forward : FW ([0,1], +, 0, *, 1)
Technically, the semiring is (E, <+>, <0>, <*>, <1>) where E is an event
space, <+> is union of events[1], <0> is the impossible event, <*> is
intersection of events[2], and <1> is the event of certainty. But we can
simplify things from the event space to a probability space, given the
assumptions made by the forward algorithm.
Just in case anyone cared :)
[1] Pr(x) <+> Pr(y) = Pr(x) + Pr(y) - Pr(x,y)
[2] Pr(x) <*> Pr(y) = Pr(x,y)
--
Live well,
~wren
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
