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 <wren@freegeek.org> 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
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe