1
$\begingroup$

A hylomorphism consists of an anamorphism followed by a catamorphism.

Is it possible to express linear regression as a hylomorphism?

$\endgroup$

1 Answer 1

3
$\begingroup$

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!)

$\endgroup$
4
  • $\begingroup$ Thanks! There’s also this r6.ca/blog/20110808T035622Z.html, but Tarjan and Backhouse came first (in that order, I believe). $\endgroup$ Commented Nov 12, 2020 at 22:16
  • 1
    $\begingroup$ I’d still like to know if it can be represented as a hylomorphism ... $\endgroup$ Commented Nov 12, 2020 at 22:17
  • 1
    $\begingroup$ It certainly can! Gaussian elimination for matrix inversion consists of putting a matrix into row-echelon form and then back-substituting. The cost of each round is bounded by the dimensionality of the matrix -- for each row, you need to perform elementary row operations on each of the other rows to put the matrix into row-echelon form. The number of steps in an elementary row operation are bounded by the dimensionality of the matrix, as are the other two things, leading to an $O(n^3)$ bound, which is just three nested folds on the dimension $n$. $\endgroup$ Commented Nov 13, 2020 at 11:20
  • 1
    $\begingroup$ However, note that this a much less useful view, with much less algebraic structure, than thinking of it in terms of closure operators. $\endgroup$ Commented Nov 13, 2020 at 11:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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