<p>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.</p>
<p>Regression is about minimising the mean squared error. A regression model has a vector of inputs (i.e., the <em>design matrix</em>) <span class="math-container">$X$</span>, a vector of outputs <span class="math-container">$Y$</span> and a set of coefficients <span class="math-container">$\beta$</span>, with a model</p>
<p><span class="math-container">$$
   Y = X\beta + e 
$$</span></p>
<p>where <span class="math-container">$e$</span> is a vector of errors. If we view <span class="math-container">$e$</span> as a function of <span class="math-container">$\beta$</span>, we can write:</p>
<p><span class="math-container">$$
   e(\beta) = Y - X\beta
$$</span></p>
<p>Then, the squared error (as a function of the coefficients <span class="math-container">$\beta$</span>) will be given by the dot product</p>
<p><span class="math-container">$$
   SE(\beta) = e^T e
$$</span></p>
<p>Then a bit of vector calculus will tell you that <span class="math-container">$\beta$</span> gets minimised when</p>
<p><span class="math-container">$$
\beta = (x^T x)^{-1} x^T y
$$</span></p>
<p>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.</p>
<ol>
<li><p>First, the star in Kleene algebra (i.e., models of regular expressions) corresponds to iteration. You can see this in the characterizing equation:</p>
<p><span class="math-container">$$A^\ast = I + A A^\ast$$</span></p>
</li>
<li><p>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:</p>
<p><span class="math-container">$$\begin{array}{lcl}
    A^\ast &amp;=&amp; I + A A^\ast \\
    A^\ast - A A^\ast &amp; = &amp; I \\
    A^\ast (I - A) &amp; = &amp; I \\
    A^\ast &amp;=&amp; (I-A)^{-1} \\
   \end{array}$$</span></p>
<p>So matrix inversion has a fundamental connection to the asteration operation in Kleene algebra.</p>
</li>
</ol>
<p>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 <em>reachability</em> in the graph -- and graph reachability is very obviously a fixed point property.</p>
<p>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. Carré, and were developed by Robert Tarjan in his 1979 paper <a href="https://dl.acm.org/doi/10.1145/322261.322272" rel="nofollow noreferrer"><em>A Unified Approach to Path Problems</em></a>. (Tarjan also points out this means that many graph algorithms can be seen as sparse matrix computations!)</p>

CC BY-SA 4.0
2020-11-12T22:16:20.763Z
Thanks! There’s also this http://r6.ca/blog/20110808T035622Z.html, but Tarjan and Backhouse came first (in that order, I believe).
NietzscheanAI
CC BY-SA 4.0
2020-11-12T22:17:19.587Z
I’d still like to know if it *can* be represented as a hylomorphism ...
NietzscheanAI
CC BY-SA 4.0
2020-11-13T11:20:45.913Z
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$.
Neel Krishnaswami
CC BY-SA 4.0
2020-11-13T11:21:44.027Z
However, note that this a much less useful view, with much less algebraic structure, than thinking of it in terms of closure operators.
Neel Krishnaswami
CC BY-SA 4.0
2020-11-12T16:31:43.150Z
2020-11-12T16:31:43.150Z
Neel Krishnaswami
<p>A <a href="https://en.wikipedia.org/wiki/Hylomorphism_(computer_science)" rel="nofollow noreferrer">hylomorphism</a> consists of an <a href="https://en.wikipedia.org/wiki/Anamorphism" rel="nofollow noreferrer">anamorphism</a> followed by a <a href="https://en.wikipedia.org/wiki/Catamorphism" rel="nofollow noreferrer">catamorphism</a>.</p>
<p>Is it possible to express linear regression as a hylomorphism?</p>

<linear-algebra><recursion>
Linear regression as a hylomorphism
NietzscheanAI
# Linear regression as a hylomorphism

(Asked by: username_0 on 2020-11-12)

A [hylomorphism](https://en.wikipedia.org/wiki/Hylomorphism_(computer_science)) consists of an [anamorphism](https://en.wikipedia.org/wiki/Anamorphism) followed by a [catamorphism](https://en.wikipedia.org/wiki/Catamorphism).

Is it possible to express linear regression as a hylomorphism?

**Tags:** linear-algebra, recursion

---

## 1 answers

### Answer by username_1 on 2020-11-12. Score: 3 | Accepted answer

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. Carré, and were developed by Robert Tarjan in his 1979 paper [*A Unified Approach to Path Problems*](https://dl.acm.org/doi/10.1145/322261.322272). (Tarjan also points out this means that many graph algorithms can be seen as sparse matrix computations!)

> **Comments:**
> **username_0**: Thanks! There’s also this http://r6.ca/blog/20110808T035622Z.html, but Tarjan and Backhouse came first (in that order, I believe).  
> **username_0**: I’d still like to know if it *can* be represented as a hylomorphism ...  
> **username_1**: 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$.  
> **username_1**: However, note that this a much less useful view, with much less algebraic structure, than thinking of it in terms of closure operators.  

---

