Just over 24 hours before I leave London for Kathmandu! I’ll be joining The Mountain Institute‘s expedition to Imja Lake in the Khumbu. During the expedition I’ll be assisting with technical operations, getting updates out via satellite. You can follow our progress on the expedition blog.

Floating point numbers are great, I simply can’t join the chorus that maligns them. Nevertheless you need to understand your use case when you’re dealing with them. Floats are ideal if you’d like to distinguish between the mass of a boy and a battleship. Converting between Pounds Sterling and Yen where every penny matters? Bad choice. Working with probabilities? Forget it! If you’ve ever implemented a Hidden Markov Model, you know what I’m talking about.

Many of these problems can be alleviated by log-transforming your domain. Multiplication maps to addition, division to subtraction — huzzah! Precision loss is still an issue, and round-off errors will accumulate as the difference between consecutive values exceeds your multiplicative factor. Nevertheless, in most instances a floating point representation would have failed far earlier than the log transformed analogue.

I’ve prepared a C++ datatype implementing common operations on log transformed floats. I chose to explicitly maintain sign. I probably could have done this via bit-packing the underlying type, but this just seems like a bad idea. If the overhead of lugging around a sign is burdensome (or if you don’t want to risk negative probabilities), it can be easily removed.

There is no cast operator to convert a LogReal to its base type. This operation would have been susceptible precision loss and should never be used implicitly. Moreover, including a cast would have led to syntactic gymnastics to ensure that multiplication of LogReals wasn’t accomplished by demoting the values to their base types.[1]

Adding and subtracting LogReal values yields a base type value. Addition in this domain is inherently unsafe, adding or subtracting two valid LogReals can easily yield a value that cannot be represented by the base type owing to overflow and underflow.

For many values it is the case that: exp(log(x)) != x. Sorry — there’s nothing I can do about the pigeonhole principle.

Fork the code on GitHub! The code is unlicensed. If you find it useful or want to enchance it, e-mail me or send a pull request.

[1] Know a good way to get C-style explicit casts while avoiding kludgey C++ casts and implicit casting? E-mail me.

Augmenting Viterbi’s algorithm with an A* search is a simple technique that can significantly speed parsing. Stu Geman introduced this method to me when I was working on segmentation of tumor array copy-number data.

The trellis of a Viterbi parse is a directed acyclic graph. Edges are labeled with the log emission and transition probabilities. The maximum-likelihood parse corresponds to the shortest path from the start state to the accepting state. Viterbi’s algorithm finds this path by smashing its way through the trellis, traversing every available edge. In the absence of a sharply peaked distribution, this works fine — you pay a fixed cost for every parse.

If you know something about the distribution of your path lengths, you can do a bit better. Dijkstra’s algorithm is a sensible place to start, traversing the shortest edges rather than exploring the entire trellis. However, this approach can fail spectacularly. Since it does not account for progress through the trellis, a low valued edge will be expanded without regard to its distance from the sink node. In this case, the log-factor introduced by maintaining the search’s priority queue becomes a significant factor in the overall run time.

Fortunately, Dijkstra’s algorithm is just a special case of A* Search (one with a zero-valued heuristic). If your problem is amenable to an efficient admissible heuristic, you can reap significant gains by using A* instead of an exhaustive Viterbi search.

A* Parsing: Fast Exact Viterbi Parse Selection [pdf]