Linear regression as a hylomorphism

Question

A hylomorphism consists of an anamorphism followed by a catamorphism.

Is it possible to express linear regression as a hylomorphism?

Answer 1

You can indeed see linear regression as arising from a fixed point computation, but it is better to think of it as related to transitive closure computations than to folds or unfolds.

Regression is about minimising the mean squared error. A regression model has a vector of inputs (i.e., the design matrix) $X$, a vector of outputs $Y$ and a set of coefficients $\beta$, with a model

$$ Y = X\beta + e $$

where $e$ is a vector of errors. If we view $e$ as a function of $\beta$, we can write:

$$ e(\beta) = Y - X\beta $$

Then, the squared error (as a function of the coefficients $\beta$) will be given by the dot product

$$ SE(\beta) = e^T e $$

Then a bit of vector calculus will tell you that $\beta$ gets minimised when

$$ \beta = (x^T x)^{-1} x^T y $$

The matrix inversion in the equation above is secretly a fixed point calculation. To get an intuition for why, you need to recall two facts.

1. First, the star in Kleene algebra (i.e., models of regular expressions) corresponds to iteration. You can see this in the characterizing equation:

   $$A^\ast = I + A A^\ast$$

2. Next, square matrices with elements valued in a Kleene algebra form a Kleene algebra. So if you think of the equation above in terms of linear algebra, you can sort of see this as saying:

   $$\begin{array}{lcl} A^\ast &=& I + A A^\ast \\ A^\ast - A A^\ast & = & I \\ A^\ast (I - A) & = & I \\ A^\ast &=& (I-A)^{-1} \\ \end{array}$$

   So matrix inversion has a fundamental connection to the asteration operation in Kleene algebra.

As another source of intuition, if you think of a square Boolean matrix as representing the edge relation in a graph, the Kleene star of the graph represents reachability in the graph -- and graph reachability is very obviously a fixed point property.

This is all quite handwavy, but these ideas have been developed rigorously. They were first (I think) introduced to computer science by Roland Backhouse and B.A. Carré, and were developed by Robert Tarjan in his 1979 paper A Unified Approach to Path Problems. (Tarjan also points out this means that many graph algorithms can be seen as sparse matrix computations!)