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 <[email protected]> wrote: > 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 > [email protected] > http://www.haskell.org/mailman/listinfo/haskell-cafe >
_______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
