The Paper

Steffen Rendle introduced Factorization Machines a while ago in 2010, but I have only more recently come across it.

There is only a very short proof provided of Lemma 3.1 (page 3): “The model equation of a factorization machine can be computed in linear time $O(k * n)$.”

I decided to derive the proof myself and found some things interesting along the way. I wrote down an earful hoping that someone else finds it helpful!

The Proof

Let $f$ be a function with commutative operator $\circ$ (such as multiplication, dot product, Hadamard product, or simultaneously diagonalizable matrix multiplication ¹) that follows the decomposition:

There are many cases in computer science where we want to compute something in a pairwise fashion between all $u(x)$ and $s(x)$. One such case is linear combination of pairwise effects for the function $f(i, j)$. A naive description of the component wise operations that are the “product” between two elements can be computed as follows: $\sum\limits_{i=1}^n \sum\limits_{j=1}^n f(i, j)$

A standard calculation requires $n^2$ operations. However, if $\circ$ is also distributive over summation, we can expand and factorize this computation in $O(n)$ operations. Let’s begin! $$ \sum\limits_{i=1}^n \sum\limits_{j=1}^n f(i, j) = u(0) \circ \left(\sum\limits_{i=1}^n s(i) \right)

• u(1) \circ \left(\sum\limits_{i=1}^n s(i) \right)
• \ldots + u(n) \circ \left(\sum\limits_{i=1}^n s(i) \right) = \left(u(0) + u(1) + \ldots + u(n) \right) \circ \left(\sum\limits_{i=1}^n s(i) \right) = \left(\sum\limits_{i=1}^n u(i) \right) \circ \left(\sum\limits_{i=1}^n s(i) \right) $$

This is really, really awesome. We have reduced from $O(n^2)$ $+$ operations and $O(n^2)$ $\circ$ operations to $O(n)$ $+$ operations and only one lonely $\circ$ operation. This has reduced an unnecessary loop over $j$, illustrating that this problem is actually less complex than it originally appeared ².

Is this intuitive? I think so. Remember in elementary school, where it was way more fun to compute something like $(1 + 2) * (3 + 4)$ than $1 * 3 + 1 * 4 + 2 * 3 + 2 * 4$? This is a similar thing, where you win by factorizing. In this case, we can further cheat becomes it becomes clear when you write the expansion that $j$ is not a necessary variable. This is a case where pairwise interactions can factor out due to the combination of commutative and distributive properties of $\circ$ in such a beautiful way so we don’t care what the value of $j$ is. Amazing!

For a bit of a brain tease, let $+ = \min$, $\circ = \max$. This would be like having each $u(i)$ $s(j)$ pair joust for highest value, and then taking the smallest of these values (perhaps a quasi-winner take all?): $\min_{i, j}(\max(u(i), s(j)))$ Due to our factorization proof, it would mean it is equivalent to computing: $\max(\min_i(u(i)), \min_i(s(i)))$ I find this somewhat intuitive; the largest $\max(u(i), s(j))$ simply depends on either the row $u(i)$ or column $s(j)$ value, not the combination.

What if we don’t care about self similarity $f(i, i)$? We can have a smart factorization that significantly reduces the number of computations when self similarity $f(i, i)$ is unimportant.

Due to the commutative property of $\circ$, the operations are symmetric. The sum can be thought of as summing over all entries for a matrix of the results $f(i, j)$:

where

Due to the triangular nature of this matrix, we can separate into upper triangular, lower triangular, and diagonal matrices:

$M = U + L + D$ $U= \begin{pmatrix} 0 & f(2, 1) & \ldots & f(n, 1)\\ 0 & 0 & \ldots & f(n, 2)\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 &\ldots & 0 \end{pmatrix} , L= \begin{pmatrix} 0 & 0 & \ldots & 0\\ f(1, 2) & 0 & \ldots & 0\\ \vdots & \vdots & \ddots & \vdots\\ f(1, n) & f(2, n) &\ldots & 0 \end{pmatrix}$ $D= \begin{pmatrix} f(1,1) & 0 & \ldots & 0\\ 0 & f(2, 2) & \ldots & 0\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 &\ldots & f(n, n) \end{pmatrix}$

Due to the commutative nature of $\circ$: $\sum U = \sum L$

We can then decompose $\sum M = 2 \sum U + \sum D$

Or rearranged: $\sum U = \frac{\sum M - \sum D}{2}$

Therefore, if all you care about is just the upper triangular: $\sum\limits_{i=1}^n \sum\limits_{j > i}^n f(i, j) = \sum U = \frac{\sum M - \sum D}{2}$

Lets go back to a more verbose, lower level representation expanding the sums $\frac{\sum M - \sum D}{2}$ as follows: $\frac{1}{2}\sum\limits_{i=1}^n \sum\limits_{j=1}^n f(i, j) - \frac{1}{2} \sum\limits_{i=1}^n f(i, i)$

We can simplify the values of the diagonal in $D$: $\sum\limits_{i=1}^n f(i, i) = \sum\limits_{i=1}^n u(i) \circ s(i)$

Putting it all together, we get can compute the upper triangular pairwise interactions as follows: $\sum\limits_{i=1}^n \sum\limits_{j > i}^n f(i, j) = \frac{1}{2}\left(\sum\limits_{i=1}^n u(i) \right) \circ \left(\sum\limits_{i=1}^n s(i) \right) - \frac{1}{2}\sum\limits_{i=1}^n u(i) \circ s(i)$

As an example, when $\circ$ is $*$ and $s(x) = u(x)$, this looks like the following: $\sum\limits_{i=1}^n \sum\limits_{j > i}^n f(i, j) = \frac{1}{2}\left(\sum\limits_{i=1}^n u(i) \right)^2 - \frac{1}{2}\sum\limits_{i=1}^n u(i)^2$

There is something very beautiful about this transformation. It says that summing the upper triangular elements computed by $f(i, j)$ can be decomposed into a one dimensional function that only iterates over the number of components $n$.

Why is this useful?

Basically factorization reduces redundant computation.

When $\circ$ performs some really expensive operation like a dot product upon all pairwise combinations of elements, computing $\sum U$ can be simplified to $O(n * k)$, where $k$ is the length of the vector.

This is exactly the case used in Factorization Machines, where we create a latent space from an input $n$, $k << n$. When modeling real world data, $k$ probably has some sublinear dependency on $n$, perhaps $k \approx \log_2(n)$. That’s much better than the naive $O((n * k)^2)$!

In addition, this simplification is used as a tool to create other proofs, like showing that Spearman’s $\rho$ coefficient is a particular case of the general correlation coefficient.