Some basic background

The Kalman filter is a (linear) state estimation algorithm that presumes that there is some sort of uncertainty (optimally Gaussian) in the state observations of the dynamical system. The Kalman filter has been extended to nonlinear systems, constrained for cases where direct state observation is impossible, etc. As one should know, the algorithm essentially performs a prediction step based on prior state knowledge, compares that prediction to measurements, and updates the knowledge of the state based on a state covariance estimate that is also updated at every step.

In short, we have a state-space vector usually represented by a vector in $\mathbb{R}^n$. This vector is operated on by a plant matrix, added to a control term (which is operated on by a control matrix), operated on by a covariance matrix, etc. There are usually not intrinsic constraints on the state-space vector beyond those which may be embedded in the description of the dynamical system.

My question

Can we describe the Kalman filter using the language of category theory? In other words, can we generalize the algebra of what is happening with the Kalman filter for a dynamical system to develop Kalman-like estimators for other processes with vector-like components derived from some known (or partially known) model?

A motivating example

A repeated matrix game involves two or more players choosing strategies according to some payoff function -- which is a function of the game's state space and each player's action -- typically with some notion of equilibrium (e.g. Nash equilibrium). A repeated game with a finite action space implies that strategies are discrete probability distributions representable by a vector in $\mathbb{R}^N$ such that every element of the strategy vector is non-negative and the vector sums to unity.

This is a more restrictive case than a general dynamical system because we have constraints on the vector representation of the strategy. But, given input (i.e. actions taken), output (state measurement of the game's state space), and a payoff structure, it might make sense to attempt a Kalman-like estimator for the strategy vector in the game.

The challenge, of course, is developing a compatible notion of covariance. It's not clear what covariance would mean in relation to probability distributions, since we don't treat the quantity $P(\textrm{action} = \textrm{index})$ as random variable. But if we had a category theoretical view of the Kalman filter, could we derive a similar structure based on its algebraic properties in such a way that we can guarantee that our estimate of the opponent's strategy vector converges in some way?

Does what I'm asking even make sense?

  • 2
    $\begingroup$ As an aside; the motivating example is a real example that I have seen attempted in practice. There was some rigor provided in the development of a Kalman-like estimator for the opponent's strategy, but there was no proof of convergence, and it wasn't immediately clear that what was being done actually made any mathematical sense. It seemed like there was an intuitive connection, however, that might be formalized through category theory. $\endgroup$ – Emily Jan 14 '14 at 16:45

The most direct approach, already mentioned by Chris Culter, is to use the fact that Kalman filters are a kind of graphical model and look at categorical treatments of graphical models. This is a rather active area particularly amog people interested in quantum computation, quantum information and quantum foundations in general. Graphical models are usually treated as string/tensor/trace diagrams, a.k.a Penrose notation or graphical languages, rather than directly as categories. The main reference on the abstract categorical treatment of these kinds of diagrams is Peter Selinger, A survey of graphical languages for monoidal categories There is also a very nice interdisciplinary survey by John Baez that covers this and a number of related areas. People with publications in this are include Samson Abramsky, Bob Coecke, Jared Culbertson, Kirk Strutz, Robert Spekkens, John Baez, Jacob Biamonte, Mike Stay, Bart Jacobs, David Spivak and Brendan Fong whose thesis was already provided by Chris Culter in his answer.

Categorical ttreatments graphical models require dealing with probability which is usually done with monads, often using Giry's monad.

You may also want to look at the work of the group at ETH Zurich that includes Patrick Vontobel & Hans-Andrea Loeliger. They work on a kind of graphical model they call Forney factor graphs. They do not use category theory themselves but they have papers on how to translate many kinds of computations, including Kalman filters, electrical circuits and EM algorithms to & from their graphical models. This also provides a means to translate between Kalman filters and electrical circuits indirectly, so their work could be useful to transform KFs into other things things that already have categorical representations.

Here are links to some of the papers:

  • $\begingroup$ !! Perfect! This is exactly what I need! $\endgroup$ – Emily Jan 24 '14 at 17:23
  • $\begingroup$ Great! I would be interested to know more about what you are doing. $\endgroup$ – Daniel Mahler Jan 25 '14 at 2:02

A Kalman filter performs inference on a model which is a simple Bayesian network, and a Bayesian network is a kind of graphical model, and graphical models kind of look like categories, so there may be a connection there. Unfortunately, I can't personally go beyond that vague description. Searching the web for "graphical model" + "category theory" turned up an interesting thesis: Brendan Fong (2012) "Causal Theories: A Categorical Perspective on Bayesian Networks". There's no attempted connection to game theory, but it might be worth a look!

  • $\begingroup$ I'll check it out; thanks. That graphical connection is exactly what I'm thinking about, but unfortunately I have nothing more than a vague notion, either. $\endgroup$ – Emily Jan 14 '14 at 19:18

Here is something on these lines (mean-field game theory and Kalman-type filtering): http://arxiv.org/abs/1302.6563

  • $\begingroup$ Thanks. I've seen several attempts at Kalman-like filtering for game theory, but I'm not only looking for game theory applications. I'm mainly interested in casting the algorithm in an abstract framework, allowing for the notions of convergence and covariance to apply more generally. Nevertheless, the paper looks like an interesting read! $\endgroup$ – Emily Jan 21 '14 at 15:46

In the paper Bayesian Machine Learning via Category Theory, in section 9.2, this idea of a categorical viewpoint of Kalman Filtering is addressed. It is a HMM expressed in the category of conditional probabilities (Kleisi category of the Giry monad). This model is ubiquitous.

  • $\begingroup$ Excellent! I will give this a read. $\endgroup$ – Emily Feb 25 '14 at 18:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.