[Haskell-cafe] Higher-order algorithms

[wren ng thornton]

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