[Haskell-cafe] Higher-order algorithms

[wren ng thornton]

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