[Haskell-cafe] Higher-order algorithms
wren ng thornton
wren at freegeek.org
Wed Aug 25 00:43:31 EDT 2010
On 8/24/10 11:10 AM, Daniel Peebles wrote:
> 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.
Yeah, factor graphs and graphical models also see this kind of thing.
Basically anything that can be thought of as collecting or combining
paths through a graph is likely to work for arbitrary semirings (again,
because of the connection between languages and free semirings).
Versions of Dijkstra's algorithm for weighted graphs vs unweighted
graphs, for example, same thing.
As for Haskell implementations: this summer I've been working on a
generalized forward--backward algorithm as well as an anytime n-best
algorithm, though I haven't released the code just yet. One of the main
aims of the project is to explore incremental, on-line, and interactive
algorithms for HMMs, and to make sure the implementation is efficient
enough for real-time use. I think the code is pretty attractive, for all
that. Though there are always a few rough edges.
Curiously enough, I ran into some difficulties when trying to make the
algorithm general over different semirings. Basically GHC was having
problems figuring out that two required class instances should be the
same one. That's the big thing holding back a public release right now.
After doing the final report for this summer, I think I've figured out a
new way of tackling it, which I hope will allow GHC to resolve the
types. Once I get that figured out I'll throw it up on Hackage and make
HMMs, including higher-order HMMs, hit a nice sweet spot when it comes
to implementing things efficiently. Trying to do it for arbitrary factor
graphs or graphical models is going to make the implementation bog down.
For instance, you can perform both passes of the forward--backward
algorithm in parallel because the chain structure of an HMM ensures that
the "forward" and "backward" halves of the graph are completely severed.
When generalizing this to tree structures you get the inside--outside
algorithm, but the outside pass requires the results of the inside pass,
so you can't do them in parallel.
More information about the Haskell-Cafe