[Haskell-cafe] Higher-order algorithms
pumpkingod at gmail.com
Tue Aug 24 11:10:56 EDT 2010
Interesting. I've come across this general idea/algorithm the factor graph /
sum-product algorithm papers 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.
On Tue, Aug 24, 2010 at 9:25 AM, wren ng thornton <wren at 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, <0> is the impossible event, <*> is
> intersection of events, 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 :)
>  Pr(x) <+> Pr(y) = Pr(x) + Pr(y) - Pr(x,y)
>  Pr(x) <*> Pr(y) = Pr(x,y)
> Live well,
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe