Comments

2 days ago, SteffenZeidler wrote

Hi, Steffen -- I was after something a little deeper, such as a user-defined numerical class (sketching, now), say logarithmic doubles, in which operator * is mapped to arithmetic + on doubles.  I couldn't find a way to make Viterbi generic over both user-supplied classes with operator overloads AND over built-in types, where operators are not the same kind of thing as operator overloads.  I could wrapper all the built-in types with operator * that maps to * etc., but that's  a lot of work.  That's essentially implementing my own "Numeric Tower" over the CLR basic types, and it didn't seem worth it to me to get a corner case like logarithmic double.  Maybe there *is* a way, I just couldn't find it.  Now I'm going to look at Richard.Hein's link

Edit: just an aside about why logarithmic doubles might be valuable: multiplying a bunch of small probabilities over and over eventually underflows doubles.  Bad.  Sometimes better to add logarithms of probabilities to get the log of the product of the probabilities. 

Just had another little thought -- Since Viterbi is modifying its internal variables V and Path as observations present themselves in OnNext, Viterbi is, itself a little monad.  It could inherit from the state monad or just built up on its own, but the point is that the OnNext function on the surface would internally call "Bind" or "SelectMany" on the Viterbi monad, that is, OnNext would just call the LINQ provider of Viterbi!  This might shrink and robustify the code even more.

@JoshRoss: or even a precomputed corpus from the same folks

http://blog.afterthedeadline.com/2010/07/20/after-the-deadline-bigram-corpus-our-gift-to-you/ 

@Jan de Vaan: Yes, this looks like a promising direction. http://www.codeproject.com/KB/cs/genericnumerics.aspx

I also found out it's possible to go generic on numeric types in F# IFF the methods are INLINED. That's because the compiler just "pastes" the inlined code after resolving the generic type, and then the normal method lookup finds the appropriate operator implementations. Not sure if this approach is available in C#.

@JoshRoss: you will also need "transition probabilities," which you can get from digram frequencies (frequencies of word pairs). One really cool way to get these is to analyze free texts on project gutenberg (public-domain ebooks as plain text!). 

@PCB: yup, just for symmetry (euphemism for "copy-paste" code  ContainsKey would have been better.

@fwaris:Very nice!

Anyone taking up my invitation to try a spelling corrector with this?

@jordanterrell: Yes, yes, yes, PROFILE to find perf bottlenecks!  I jumped straight from the art code to the opposite extreme of in-place mutation, but did not profile the art code, just assumed that spinning up closures in State was the culprit.

And 100% agree that the provability and reliability of monadic functional code is worth it in many (most?) circumstances.  On the perf critical path, profile and compromise as needed, focusing on implementation innards.

@AdamSpeight2008:looks like Option<T> is F#'s implementation of the Maybe monad -- different in name only, so far as I can see.  They even have a good fraction of the LINQ operators implemented on it.  I hope to be able to say more about F#, in general, after getting some more seat time with it.

@Simon: that will work great if you have explicit data that you can represent in-line in the code (and it so happens I do in my Wikipedia example).  But I don't see how to take advantage of these collection initializers when reading data from an external source.  For an application like that, I can still Aggregate over a composable dictionary, as in lines 168 through 174 in my unit test DictionaryExtensionsTests.cs... like this

const int range = 1280;
var kvps = Enumerable
    .Range(0, range)
    .Select(i => new KeyValuePair<int, string>(i, Convert.ToChar(i).ToString()))
    ;

dict = kvps.Aggregate(dict, (d, kvp) => d.AddUnconditionally(kvp));