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[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.
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 an announcement.
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.
-- Live well, ~wren _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
