RecSys Part III · Ranking · chapter 12 of 19
Feature interactions
The task of this chapter is stated in one phrase: teach the model that features matter not separately but together. «A user from Russia» and «the genre is rock» say little on their own; their combination can say a great deal. What follows is a story in six steps, where each next one repairs a specific breakage of the previous. That chain is a ready-made interview answer in itself.
- Explicit cross features fail twice over. At a total cardinality of 3 M that is 18 TB of weights — and, more importantly, the weight of a combination never seen is not trained at all.
- Factorisation repairs both problems in one move. 384 MB instead of 18 TB, 47 thousand times less, plus generalisation by transitivity.
- An MLP does not learn a product on its own — that is the central story of the chapter. Universality of approximation speaks about the existence of weights, not about gradient descent finding them on sparse data.
- By default you take DCN-v2. Everything to the left in the chain is history; everything to the right is the research frontier.
1. A chain of six steps
2. A linear model and cross features
A linear model over a concatenation of one-hot representations is equivalent to assigning a trainable scalar to every value of a feature and then adding up the scalars of the values that occurred:
$$ \hat y = w_0 + \sum_{i} w_i x_i $$There are no interactions here at all — the contribution of «Russia» is the same regardless of genre. Let us add all cross features of the second degree, that is, combinations of the form «language=ru, genre=rock»:
$$ \hat y = w_0 + \sum_i w_i x_i + \sum_{i < j} w_{ij}\, x_i x_j $$Formally the problem is solved. Practically it is broken in two places.
The number of parameters is \(O(n^2)\), where \(n\) is the total cardinality of all the features:
| Total cardinality | Weights | Memory in float32 |
|---|---|---|
| 1e+04 | 5.00e+07 | 200.0 MB |
| 1e+05 | 5.00e+09 | 20.0 GB |
| 1e+06 | 5.00e+11 | 2.0 TB |
| 3e+06 | 4.50e+12 | 18.0 TB |
The numbers are reproduced by the script _tools/cross_demo.py in this repository.
Three million of total cardinality is modest by the standards of recommendations. Eighteen terabytes of weights for interactions of the second degree.
If a combination did not occur in training, the corresponding \(w_{ij}\) is simply untrained. About combinations it has not seen, the model can say nothing at all.
How critical is that? Take 30 fields of 100 000 values each and a dataset of a billion samples:
- pairs of fields: 435;
- possible combinations of values: 4.35e+12;
- observations of pairs across the whole dataset: 4.35e+11.
Even in the ideal case where all the observations are distinct, no more than 10% of the combinations will occur even once. And the distribution is a power law (chapter 1), so the real share is orders of magnitude smaller.
The numbers are reproduced by the script _tools/cross_demo.py.
So the overwhelming majority of the weights will stay at their initial value forever. This is not a problem of scale to be solved with hardware — it is a problem of representation.
3. Factorization Machines
The solution: give every feature a vector and obtain the weight of a pair as an inner product.
$$ w_{ij} \approx \langle v_i, v_j\rangle \qquad\Longrightarrow\qquad \hat y = w_0 + \sum_i w_i x_i + \sum_{i < j} \langle v_i, v_j\rangle\, x_i x_j $$One move repairs both breakages at once — and it is worth stating exactly that way rather than as two separate merits.
- Memory \(O(nd)\) instead of \(O(n^2)\). The matrix \(V\) is simply the feature embeddings, exactly the ones from the previous chapter.
- Generalisation to unseen combinations. To estimate the weight of a pair \((i,j)\) you did not have to see that pair: it is enough that \(v_i\) was trained on other pairs involving \(i\) and \(v_j\) on pairs involving \(j\).
The second point is the same transitivity logic that pulled matrix factorisation along: a low rank ties the observed to the unobserved.
At a total cardinality of 3 M: explicitly 4.50e+12 weights (18.0 TB), a factorization machine with \(d = 32\) — 9.60e+07 (384.0 MB). A difference of 47 thousand times.
But it is more interesting to look at the same thing from the side of information. How many independent numbers have to be determined:
| Features \(n\) | Pairs in total | FM parameters at \(d=16\) | Share |
|---|---|---|---|
| 100 | 4 950 | 1 600 | 32.32% |
| 1000 | 499 500 | 16 000 | 3.20% |
| 10000 | 49 995 000 | 160 000 | 0.32% |
The numbers are reproduced by the script _tools/cross_demo.py.
With a thousand features, the information from 3.2% of the pairs is enough to recover the rest. That is generalisation — not a metaphor but a countable fact about the number of degrees of freedom.
Field-aware FM goes further: a feature has not one vector but a vector per field it interacts with. A piece of history people sometimes ask about: FFM won the Kaggle Criteo CTR Prediction Challenge.
4. Early neural architectures
FM stopped at the second degree: it models pairs and only pairs. The natural wish is triples, quadruples and non-linearities. The most obvious move is to put an MLP on top and hope it works things out for itself. The whole subsequent history is about how it does not work them out.
| Model | Idea | What is new |
|---|---|---|
| Concat + MLP | concatenate the embeddings of the categorical features and the normalised real-valued ones, put an MLP on top | the simplest ranking network; interactions only implicit |
| Wide & Deep | a linear model with hand-picked cross features plus a network; the prediction is their sum | an explicit division of roles: wide is responsible for memorisation and interactions up to the second order, deep for generalisation and higher orders |
| DeepFM | the manual cross features were replaced by a factorization machine | manual feature engineering is gone; the embeddings are reused both in the FM and in the network |
| DLRM | a bottom MLP turns the real-valued features into a single embedding, the top one works over a concatenation of pairwise inner products | explicit pairwise interactions without \(O(n^2)\) parameters |
Details of Wide & Deep worth remembering as a specimen of the engineering decisions of its time: embeddings of size 32 for the categorical features, a CDF transformation for the real-valued ones, concatenation into a vector of dimension 1200, three layers with ReLU.
Both models require all feature embeddings to have the same dimension — otherwise an inner product is simply undefined.
And in industrial data cardinalities vary from tens to millions, so a single dimension is knowingly suboptimal: we have just seen that the size should grow with cardinality. That is the limitation DCN-v2 will remove.
5. Why an MLP does not learn a product on its own
The key question of the chapter, and its answer is unobvious enough to be worth learning word for word.
An MLP is a universal approximator, so in theory it can approximate a product too. But universality is a statement about the existence of weights, not about gradient descent finding them on finite data.
The product \(x_i x_j\) is an awkward function for an MLP: it builds it from piecewise linear splines, and that takes many neurons and much data. Rendle et al. showed this directly: a learned MLP similarity loses to an ordinary inner product.
And in recommendations the situation is worse than in machine learning on average: the features are sparse, a particular combination occurs rarely, and there is simply nothing to «learn the product» from — we counted above that not even 10% of the combinations occur.
Hence the whole line that follows: do not rely on the MLP, write the multiplication into the architecture.
6. DCN-v2: multiplication as part of the layer
The resolution of the plot. The idea is to make multiplication part of the layer itself, and in such a way that the degree of the interactions grows with depth automatically.
Let us take it apart, because everything essential is in that line.
- \(W_l x_l\) is a linear combination of the whole concatenation, so inside it one can obtain the inner product of any feature vectors. That means any pairs, regardless of their dimensions — the limitation of DeepFM and DLRM is removed.
- \(x_0 \odot (\cdot)\) is an elementwise multiplication by the original input. This is the product written into the architecture: every layer raises the degree by one.
- \(+\, x_l\) is the residual connection, which gets a separate discussion in the next section.
\(L\) cross layers model all combinations of degree up to \(L+1\).
| Layers \(L\) | Degree | Distinct monomials with 100 features |
|---|---|---|
| 1 | 2 | 4.950e+03 |
| 2 | 3 | 1.617e+05 |
| 3 | 4 | 3.921e+06 |
| 4 | 5 | 7.529e+07 |
The numbers are reproduced by the script _tools/cross_demo.py.
The number of combinations grows faster than the data can cover them: at the fourth degree it is already 3.92 M monomials with only a hundred features. Hence the rule observed in practice — more than 2 or 3 layers give no gain.
Note that this is the same argument as the one against explicit cross features, only now applied to depth. What limits you is not the capacity of the model but the coverage by data.
The cross layer is computationally heavy: the matrix \(W_l\) has size \(d \times d\), where \(d\) is the dimension of the whole concatenation. At \(d = 1024\) and three layers that is 3.15e+06 parameters.
The cure is a factorisation \(W_l \approx U_l V_l^{\top}\) with narrow matrices:
| Rank \(r\) | Parameters | Cheaper by | Share of the full one |
|---|---|---|---|
| 16 | 9.83e+04 | 32.0 | 3.1% |
| 32 | 1.97e+05 | 16.0 | 6.2% |
| 64 | 3.93e+05 | 8.0 | 12.5% |
| 128 | 7.86e+05 | 4.0 | 25.0% |
The numbers are reproduced by the script _tools/cross_demo.py.
The further development is a mixture of low-rank decompositions: several experts instead of one, chosen by the input.
- Stacked usually beats parallel. That is, the cross network first and the MLP over its output, rather than two branches summed. Before the MLP the wide vector from the cross network is narrowed.
- A cross network gives no gain on top of abstract vector representations. It has to be applied precisely over a concatenation of feature vectors. The detail is unobvious and important: if you feed in an already «mixed» representation — the output of a transformer, say — there is nothing left to multiply, the coordinates no longer correspond to features.
- A division of labour, not a competition. The cross network models low-order interactions explicitly, the MLP high-order ones implicitly. They complement each other, and that is why both stand in the architecture.
7. Transformers over features
DCN-v2 models interactions identically for all pairs: one matrix \(W_l\) per layer. The next question suggests itself — could we decide which pairs matter dynamically, the way attention does? The answer so far is «you can, but it is not obvious that it is better».
| Model | Mechanism | Verdict |
|---|---|---|
| AutoInt | multi-head attention over feature embeddings with a skip connection, an MLP on top | works worse than DCN-v2 |
| Hiformer | heterogeneous attention: separate \(Q, K, V\) for every feature and its own FFN per feature; plus composite features | solves a real problem, but the layers need a great deal of memory |
| Field-aware Transformer | a trainable coefficient inside attention for every pair of features | the idea of FFM carried into a transformer |
| RankMixer | attention replaced by simple token mixing plus an FFN per token | cheaper than attention, the line is developing |
A good interview question with a short answer. A transformer treats all tokens identically. For text that is right — tokens are homogeneous by nature.
But in recommendations the features are heterogeneous: the user's age, an artist identifier, a price, an embedding from another model — objects of different nature and different dimension. Processing them with one and the same transformation means imposing a homogeneity that is not there.
Hence the design of Hiformer: separate projections and its own FFN per feature. The problem is real, and the price of the solution is memory.
8. Why you cannot simply add layers
A separate story that comes up whenever «let us make the network deeper» is proposed. A fact that breaks the naive intuition: as the number of layers grows, quality falls, because the gradients vanish.
Suppose the Jacobian of each layer multiplies the gradient by 0.8 — a moderate value, by no means catastrophic. In an ordinary network the factors multiply:
| Layers | Ordinary MLP: \(0.8^L\) | The path along skip connections | Upper bound \((1+0.8)^L\) |
|---|---|---|---|
| 4 | 4.10e-01 | 1.00 | 1.05e+01 |
| 8 | 1.68e-01 | 1.00 | 1.10e+02 |
| 16 | 2.81e-02 | 1.00 | 1.21e+04 |
| 32 | 7.92e-04 | 1.00 | 1.47e+08 |
The numbers are reproduced by the script _tools/cross_demo.py.
At 32 layers the gradient falls by a factor of 1262 — the lower layers practically do not train.
In a residual network the Jacobian of a block is \(I + F'\), and expanding the product gives a term made of ones alone — the path entirely along skip connections. So from below the gradient is bounded by one and does not vanish at all. From above, though, it grows, and that is exactly why a skip connection always comes paired with normalisation.
While developing the first two-tower transformer model for recommendations, this effect was noticed: if the item tower is made an MLP, about half of the metric gain is retained; if the MLP is replaced by a transformer over a single token — about 80%.
And what is a transformer over a single token? Attention over a sequence of length 1 degenerates into an identity transformation. So what remains of the transformer is only the skip connections and the normalisation around the FFN — and the whole extra gain came from exactly those.
The practical moral: before complicating an architecture, it is worth checking whether most of the effect comes from getting the residual connections and the normalisation right.
ResNet: \(y = F(x) + x\). The gradient flows straight through the sum; a superfluous layer can be «zeroed out» — at \(F \equiv 0\) it becomes the identity, and depth stops doing harm. The problem: a sum requires matching dimensions, so the layers come out heavy.
DenseNet: a concatenation instead of a sum, \(x \to [x; F_1(x)] \to [x; F_1(x); F_2(\cdot)] \to \dots\) The dimensions need not match, so \(F\) can be a cheap narrowing layer; every new layer adds detail, and the original input stays available at every level.
An input of dimension 512, four blocks:
| Layers | Parameters | |
|---|---|---|
| ResNet | 512 × 512 each | 1.05e+06 |
| DenseNet, growth 64 | 512×64, 576×64, 640×64, 704×64 | 1.56e+05 |
The numbers are reproduced by the script _tools/cross_demo.py.
6.7 times fewer parameters, and an output of dimension 768 instead of 512. The price is growing width: every block adds to the input of the next, and on deep networks that becomes a problem in itself.
Interview questions
Tell the chain of feature-interaction models.
Six steps, each repairing the breakage of the previous. A linear model — no interactions at all. Second-degree cross features — there are interactions, but \(O(n^2)\) parameters and no generalisation to unseen combinations. FM — factorise the weight matrix, memory \(O(nd)\) and generalisation by transitivity, but only the second degree. Early networks (Wide & Deep, DeepFM, DLRM) — put an MLP on top, and it turns out it does not find the pairs by itself. DCN-v2 — write the multiplication straight into the layer. Transformers over features — try to choose the important pairs dynamically.
The practical upshot: by default you take DCN-v2. Everything to the left is history, everything to the right is the research frontier.
What is wrong with explicit cross features?
Two things, and the second is more serious. Size: \(O(n^2)\) parameters in the total cardinality; at n = 3 M that is 4.5 trillion weights, 18 TB in float32 — and that is for interactions of only the second degree.
Generalisation: the weight of an unseen combination is not trained at all, and the unseen are the overwhelming majority. With 30 fields of 100 thousand values and a billion samples, even in the ideal case no more than 10% of the combinations occur, and given a power-law distribution, orders of magnitude fewer. This is a problem of representation, not of scale: hardware will not solve it.
How does FM solve both problems?
By factorising the weight matrix: \(w_{ij} \approx \langle v_i, v_j \rangle\). Every feature gets a vector, and the weight of a pair is an inner product.
Memory falls from \(O(n^2)\) to \(O(nd)\): at n = 3 M and d = 32 that is 384 MB instead of 18 TB, 47 thousand times less.
Generalisation arises by transitivity: to estimate the weight of the pair (i, j) it is enough that \(v_i\) was trained on other pairs with i and \(v_j\) on pairs with j. Countably it looks like this: with 1000 features there are 499 500 pairs in all, while FM at d = 16 has just 16 000 parameters, that is, 3.2% — the information from that share of pairs is enough to recover the rest.
Why not just put an MLP there and hope it learns the products?
Because universality of approximation is a statement about the existence of weights, not about gradient descent finding them on finite data.
A product is awkward for an MLP: it builds it from piecewise linear splines, which takes many neurons and much data. Rendle et al. showed directly that a learned MLP similarity loses to an ordinary inner product.
And in recommendations it is worse still: the features are sparse, a particular combination occurs rarely, and there is simply nothing to learn the product from. Hence the conclusion — write the multiplication into the architecture rather than hoping for it.
How is the cross layer of DCN-v2 built?
\(x_{l+1} = x_0 \odot (W_l x_l + b_l) + x_l\). Three parts. \(W_l x_l\) is a linear combination of the whole concatenation, so inside it one can obtain the inner product of any feature vectors regardless of their dimensions: the DeepFM and DLRM requirement of a single dimension is removed. The elementwise multiplication by \(x_0\) is the product written into the architecture, with each layer raising the degree by one. Plus a residual connection.
L layers give combinations of degree up to L+1, but more than 2 or 3 layers give no gain: the number of monomials grows faster than the data covers them — at the fourth degree with a hundred features it is already 3.9 M combinations.
The layer is heavy: \(W_l\) is d × d over the whole concatenation. Hence the low-rank variant \(W_l \approx U_l V_l^\top\) — at d = 1024 and r = 64 it is 8 times cheaper — and beyond that a mixture of low-rank decompositions.
How do you combine a cross network with an MLP?
Stacked usually works better than parallel: the cross network first, then the MLP over its output, with the wide vector narrowed before the MLP.
An important and unobvious detail: a cross network gives no gain on top of abstract vector representations — it has to be applied precisely over a concatenation of feature vectors. If you feed in an already mixed representation, the output of a transformer say, there is nothing left to multiply: the coordinates no longer correspond to features.
And the division of labour: cross models the low orders explicitly, the MLP the high ones implicitly. They complement each other rather than compete.
Why is an ordinary transformer poorly suited to features?
Because it treats all tokens identically. For text that is right — tokens are homogeneous. In recommendations the features are heterogeneous by nature: age, an artist ID, a price, an embedding from another model. A single transformation imposes a homogeneity that is not there.
Hence Hiformer with separate Q, K, V and its own FFN per feature — the problem is real, but the layers need a great deal of memory. AutoInt, which applies ordinary attention, works worse than DCN-v2.
Why does adding layers to an MLP degrade quality, and what is done about it?
The gradients vanish: the factors of the Jacobians multiply. If every layer multiplies the gradient by 0.8, then at 32 layers 7.9e-04 remains — a fall by a factor of 1262, and the lower layers practically do not train.
ResNet: \(y = F(x) + x\). The Jacobian of a block is \(I + F'\), and the product contains a term made of ones alone — the path entirely along skip connections, so from below the gradient is bounded by one. A superfluous layer can also be zeroed out: at \(F \equiv 0\) it is the identity. From above the product grows, which is why a skip always comes with normalisation. The downside is that a sum requires matching dimensions, so the layers are heavy.
DenseNet: a concatenation instead of a sum, the dimensions need not match, and F can be a cheap narrowing layer. With an input of 512 and four blocks of growth 64 that is 1.56e+05 parameters against 1.05e+06 for ResNet — 6.7 times fewer. The price is growing width.
One-screen cheat sheet
The chain
linear → cross → FM → early networks → DCN-v2 → transformers. By default DCN-v2.
Cross features
\(O(n^2)\): 18 TB at n=3e6. And the weight of an unseen pair is untrained — and over 90% are unseen.
FM
\(w_{ij}=\langle v_i,v_j\rangle\). 384 MB instead of 18 TB; 3.2% of pairs determine all the rest.
The central claim
Universality ≠ trainability. An MLP builds a product from splines, and there is no data for that.
The cross layer
\(x_0 \odot (W_l x_l + b_l) + x_l\). L layers → degree L+1. Different dimensions allowed.
Low rank
\(W_l \approx U_lV_l^\top\): at d=1024, r=64 it is 8 times cheaper. Beyond that, a mixture of decompositions.
Depth
\(0.8^{32}\) = 7.9e-04. A skip gives a path with a factor of 1 — bounded below, growing above, hence normalisation.
ResNet / DenseNet
A sum requires equal dimensions; a concatenation does not. 1.56e+05 against 1.05e+06 parameters.
Primary sources
- S. Rendle. Factorization Machines, ICDM 2010.
- H.-T. Cheng et al. Wide & Deep Learning for Recommender Systems, DLRS 2016.
- H. Guo et al. DeepFM: A Factorization-Machine based Neural Network for CTR Prediction, IJCAI 2017.
- M. Naumov et al. Deep Learning Recommendation Model for Personalization and Recommendation Systems, 2019 — DLRM.
- R. Wang et al. DCN V2: Improved Deep & Cross Network and Practical Lessons for Web-scale Learning to Rank Systems, WWW 2021.
- S. Rendle, W. Krichene, L. Zhang, J. Anderson. Neural Collaborative Filtering vs. Matrix Factorization Revisited, RecSys 2020 — on the MLP losing to an inner product.
- W. Song et al. AutoInt: Automatic Feature Interaction Learning via Self-Attentive Neural Networks, CIKM 2019.
- K. He, X. Zhang, S. Ren, J. Sun. Deep Residual Learning for Image Recognition, CVPR 2016; G. Huang et al. Densely Connected Convolutional Networks, CVPR 2017.
- The numbers in this chapter:
_tools/cross_demo.pyin this repository.