Interesting. I've come across this general idea/algorithm the factor graph /
sum-product algorithm papers[1] but I was wondering if you knew of any
implementations of it in haskell? I wrote one a while back but it was fairly
ugly and not as general as I'd have liked, so I never released it.
Thanks,
Dan
[1] http://cba.mit.edu/events/03.11.ASE/docs/Loeliger.pdf
On Tue, Aug 24, 2010 at 9:25 AM, 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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe