Skip to content

Math

The Two Genie Game

Every research project begins with a question. This one began with a disagreement.

A former colleague and I were discussing AI assistants. I argued that systems willing to deliberate—to ask clarifying questions, consider alternatives, and refuse requests when necessary—ought to produce better outcomes than assistants trained primarily to maximize user approval. He agreed they might produce better outcomes, but doubted they could ever compete. Every clarification, every refusal, and every additional moment spent thinking is a cost paid by the user. If another assistant answers immediately and confidently, why would people choose the slower one?

Neither of us could answer that question from intuition alone, so I turned it into a mathematical thought experiment. That thought experiment eventually grew into a formal game-theoretic model and, ultimately, the accompanying paper. This post is a less technical account of what I learned while building it.

Village with two genies

Lazy Symbolic Bayesian Inference: A Compiler for Junction Trees

Most exact-inference libraries treat junction-tree calibration as a numerical procedure: build the tree, run two passes of message passing, return the marginals. Change the evidence and the whole pass runs again. PyBayes treats it as a compiler problem instead. The junction tree is built once, then the calibration is reified as a symbolic computation DAG of typed algebraic terms. A parallel heap of torch.Tensor thunks hangs off that DAG, indexed by the same identifiers, evaluated on demand and invalidated selectively when evidence changes. The library is PyBayes (github.com/dlewissandy/pybayes).

Yet Another Primer on Bayes Nets

A walking-pace introduction to exact inference for discrete Bayesian networks: what they are, what we ask of them, why naive inference is intractable, and how junction trees turn it into a sequence of local computations. Aimed at someone who knows probability and graphs but hasn't worked with Bayesian networks specifically. By the end you should be able to read the algorithm in a graphical-models paper, recognise when exact inference is tractable for a given network, and trace why two variables are or aren't conditionally independent given some set of observations. The running example is the Asia network (Lauritzen and Spiegelhalter 1988); each algorithm is walked through end-to-end on it.

Finding the Right Shape: Implementing BLAS in Haskell

Based on a presentation given in March 2017. The slides contain the full source listings, the simplifier output, and the benchmark plots that this post summarises.

There is an idea, first articulated by Lex Augusteijn in his 1998 paper Sorting Morphisms and later made central to Jeremy Gibbons' 2003 chapter Origami Programming, that has stayed with me ever since: many divide-and-conquer algorithms are determined purely by their recursion pattern. Once you have fixed the right shape for the computation, there are essentially no further design decisions to be made. The algorithm writes itself. Fold the problem on the natural axis and the structure of the computation reveals itself; fold it wrong and you end up writing Fortran by hand, special-casing every traversal, unrolling every loop.

lambda-blas was a six-month attempt to test that claim against an unforgiving benchmark: dense numerical linear algebra. Could the inner loops of BLAS, the de facto reference for dense linear algebra since the 1970s, be expressed as simple compositions of folds and unfolds and still run as fast as the reference Fortran? The answer turned out to be yes. The library is lambda-blas and it is public on GitHub.