[Haskell-cafe] Higher-order algorithms

[Daniel Peebles]

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 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[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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20100824/48249916/attachment-0001.html