Feature Crossing

📝 Before You Continue: Please read 3.1 Wide & Deep first. This chapter exists precisely to fix 3.1's shortcoming that "the Wide part needs manually designed cross features" — understanding Wide's limitation is what makes FM's motivation click.

The Wide part of 3.1 uses manual cross features to memorize strong rules, but hand-designing features is laborious and can never be exhaustive. A natural follow-up question arises: can the machine learn feature interactions by itself? That is exactly the problem feature crossing solves.

The most direct idea is to automatically capture interactions between all feature pairs — but recommender systems routinely have thousands of features; learning one parameter per pair would explode the parameter count; and the data is highly sparse, so most combinations have no training samples at all. In this chapter we start from FM's elegant factorization, walk all the way to automatic high-order crossing in xDeepFM and AutoInt, and include an interactive demo so you can "see" how high-order combinations are built step by step.

After reading this chapter, you will be able to:

• Explain how FM uses inner products of latent vectors to cut $O(n^2)$ parameters down to $O(nk)$ and ease sparsity
• Distinguish the enhancements that AFM / NFM / PNN / FiBiNET each add on top of FM
• Explain how DeepFM replaces the manual Wide part with "shared Embedding" for an end-to-end model
• Compare the differing motivations of the three high-order crossings: DCN (element-wise) / xDeepFM (vector-wise) / AutoInt (adaptive)
• Work through 4 leveled practice problems, and use the interactive demo to understand how high-order combinations form

3.2.0 Motivation: From Manual to Automatic Crossing

The Wide part of Wide & Deep depends on experts hand-designing cross features, which has two pain points: (1) the combination space is too large for humans to enumerate; (2) newly appearing combinations have no ready-made feature. What we want is a mechanism that automatically learns interactions between arbitrary feature pairs without parameter explosion.

Recall FM from Part 2's retrieval: it factorizes users and items into vectors and uses inner products for efficient retrieval. At the ranking stage, FM shows a different face — its core idea of "learn one vector per feature, then capture interactions with vector inner products" solves exactly the pain points above. The same technique appears twice at different stages.

🧠 Mental Model: Give Every Feature a "Business Card"

Think of FM's latent vector as a "business card" handed to each feature, listing its interests. Want to know whether features A and B click? Instead of keeping a separate ledger for every A×B pair, just take the inner product of the two cards — high compatibility, large inner product. Even better: even if A and B have never appeared together in one sample, as long as each of their cards is well learned through other features, you can still infer the effect of A×B. That is the power of parameter sharing.

3.2.1 FM: Factorization Machines (Second-Order Crossing)

To capture feature interactions, a straightforward idea adds all second-order combination terms of the features to a linear model (a polynomial model):

$$y=w_0+\sum _{i=1}^n{w}_i{x}_i+\sum _{i=1}^{n-1}\sum _{j=i+1}^n{w}_{ij}{x}_i{x}_j$$

It has two fatal flaws: (1) the parameter count is $O(n^2)$, unaffordable with many features; (2) in sparse data, most crossing terms $x_i{x}_j$ never co-occur, so the corresponding weights $w_{ij}$ cannot be learned.

FM's essence is parameter sharing: factorize each interaction weight into the inner product of two low-dimensional latent vectors, $w_{ij}=⟨{\mathbf{v}}_i,{\mathbf{v}}_j⟩$. Thus:

$$y=w_0+\sum _{i=1}^n{w}_i{x}_i+\sum _{i=1}^{n-1}\sum _{j=i+1}^n⟨{\mathbf{v}}_i,{\mathbf{v}}_j⟩x_i{x}_j$$

where ${\mathbf{v}}_i,{\mathbf{v}}_j$ are the $k$-dimensional embeddings of features $i,j$ ($k\ll n$). Instead of learning $O(n^2)$ independent $w_{ij}$'s, each feature now needs only one $k$-dimensional vector, bringing the total parameter count down to $O(nk)$. More crucially: even if $i$ and $j$ never co-occur, as long as each co-occurs and learns well with other features (e.g., $k$), ${\mathbf{v}}_i$ and ${\mathbf{v}}_j$ are still valid, so the model can generalize to predict the effect of $x_i\times x_j$. Moreover, via an algebraic transformation, the FM second-order term's computation drops from $O(k{n}^2)$ to linear $O(kn)$:

$$\sum _{i=1}^{n-1}\sum _{j=i+1}^n⟨{\mathbf{v}}_i,{\mathbf{v}}_j⟩x_i{x}_j=\frac{1}{2}\left[{\left(\sum _{i=1}^n{x}_i{\mathbf{v}}_i\right)}^2-\sum _{i=1}^n{x}_i^2{\mathbf{v}}_i^2\right]$$

Each feature learns one $k$-dimensional latent vector; the interaction of any two features is given by an inner product, with no per-pair weights — parameters drop from $O(n^2)$ to $O(nk)$.

Analysis: FM uses parameter sharing to solve both "parameter explosion" and "hard to learn under sparsity" at once, making it a widely used second-order crossing baseline in industry. Its limitation: it only models second-order pairwise interactions; higher-order combinations still rely on an upper DNN to learn implicitly, and the interaction form is a fixed "inner product" that cannot differentiate the importance of different crossings.

3.2.2 FM Family Enhancements: AFM / NFM / PNN / FiBiNET

FM treats all crossings "equally," but in practice different crossings matter to different degrees. Researchers have made various enhancements on top of it:

• AFM (Attention FM) introduces attention, assigning each pair a weight $a_{ij}$ (Softmax normalized) so the model focuses on important interactions; the attention weights are visualizable and improve interpretability. Its interaction layer first computes the element-wise product $(v_i\odot v_j)x_i{x}_j$, then does attention pooling: ${\hat{y}}_{afm}=w_0+{\sum }_i{w}_i{x}_i+{\mathbf{p}}^T{\sum }_{i<j}{a}_{ij}(v_i\odot v_j)x_i{x}_j$.
• NFM (Neural FM) feeds FM's second-order crossing result (in vector form) as "raw material" into a DNN to learn higher-order nonlinearity. The key is the Bi-Interaction pooling layer: $f_{BI}={\sum }_{i<j}{x}_i{v}_i\odot x_j{v}_j$, also optimizable to $O(kn)$, then fed into an MLP. FM can be seen as the special case of NFM without hidden layers.
• PNN (Product-based NN) argues inner products / element-wise products each have limits, so its "product layer" uses inner products (IPNN) and outer products (OPNN) together to capture richer interactions, with matrix decomposition / superposition approximations reducing complexity from $O(N^{2}M)$ to $O(NM)$.
• FiBiNET first learns feature importance (borrowing SENET from vision: Squeeze → Excitation → Re-weight), then uses bilinear interaction $p_{ij}=v_i\cdot W\odot v_j$ to break the symmetric-interaction constraint, combining "important features" with "flexible interactions."

From "all crossings equally important" (FM) to "attention weighting" (AFM), "feeding a DNN" (NFM), "multiple product operations" (PNN), "re-weight first then bilinear" (FiBiNET) — the evolution always revolves around "more flexible, more expressive."

💡 Key Insight: These models all answer "how to do better on top of FM's second-order crossing" — some add attention (AFM), some attach deep networks (NFM), some change the product form (PNN), some select important features first (FiBiNET). But their second-order crossing form remains fairly fixed.

3.2.3 DeepFM: Unified Low-Order and High-Order Modeling

The Wide part of 3.1 needs heavy manual feature engineering. DeepFM simply replaces Wide with manual-free FM and lets FM and Deep share the same set of embeddings. Two benefits follow: (1) low-order and high-order interactions are learned together; (2) the shared embedding makes training more efficient.

DeepFM consists of two parallel components, FM and DNN, with shared inputs:

• The FM component captures first- + second-order crossings: $y_{FM}=⟨w,x⟩+{\sum }_{i<j}⟨V_i,V_j⟩x_i{x}_j$.
• The Deep component concatenates all embeddings and feeds them to a DNN to learn high-order nonlinearity: $a^{(0)}=[e_1,\dots ,e_m]$, $a^{(l+1)}=\sigma (W^{(l)}{a}^{(l)}+b^{(l)})$.

The two logits are summed and passed through Sigmoid: $\hat{y}=\sigma (y_{FM}+y_{Deep})$.

FM and DNN share one set of embeddings: FM learns low-order (first + second), DNN learns high-order, and their sum gives the final prediction — manual Wide features eliminated entirely.

Analysis: DeepFM's biggest improvement over Wide & Deep is replacing the manual Wide part with automatically learned FM, achieving a truly end-to-end model. Complexity mainly comes from the parallel FM + DNN, but the shared embedding avoids doubling parameters. Limitation: FM explicitly models only second order; higher orders still rely on the DNN implicitly, and the interaction form is fixed.

3.2.4 High-Order Crossing: DCN (Residual High-Order)

The FM family explicitly models second order; higher orders are mostly learned implicitly by the DNN, and we can't tell which order the DNN actually learned. DCN (Deep & Cross Network) replaces the Wide part with a Cross Network, where every layer crosses with the original input ${\mathbf{x}}_0$, thereby explicitly learning high-order interactions:

$${\mathbf{x}}_{l+1}={\mathbf{x}}_0{\mathbf{x}}_l^T{\mathbf{w}}_l+{\mathbf{b}}_l+{\mathbf{x}}_l$$

This is a residual structure: layer $l$ adds a "cross with the original input" term on top of the previous layer's output. The deeper the network, the higher the crossing order — layer 1 contains second order, layer 2 contains third order, and so on — while the parameter count grows only linearly with the input dimension. The Cross Network runs in parallel with the Deep Network, and their concatenated outputs go through logistic regression:

$$\mathbf{p}=\sigma ([{\mathbf{x}}_{L_1}^T,{\mathbf{h}}_{L_2}^T]{\mathbf{w}}_{\text{logits}})$$

Each layer $x_{l+1}=x_0(x_l^T{w}_l)+b_l+x_l$: the residual connection preserves the original information, continual crossing with $x_0$ raises the order with depth, and parameters grow only linearly.

Analysis: DCN learns arbitrarily high-order crossings explicitly and controllably, with efficient (linear-in-dimension) parameters. But it is an element-wise (bit-wise) crossing — every element of an embedding interacts separately, tearing the vector apart instead of treating the embedding as a whole feature. That is exactly what xDeepFM corrects.

3.2.5 xDeepFM: Vector-Wise CIN Interactions

DCN crosses at the element level; xDeepFM proposes the Compressed Interaction Network (CIN) and switches to vector-wise interactions, which better match intuition. xDeepFM has three components: linear + DNN (implicit high-order) + CIN (explicit high-order vector-wise), merged at the end.

The core of CIN: the layer-$k$ output ${\mathbf{X}}_k$ is a weighted sum of all pairwise Hadamard products between the previous layer ${\mathbf{X}}_{k-1}$ and the original input ${\mathbf{X}}_0$:

$${\mathbf{X}}_{h,\ast }^k=\sum _{i=1}^{H_{k-1}}\sum _{j=1}^m{\mathbf{W}}_{i,j}^{k,h}({\mathbf{X}}_{i,\ast }^{k-1}\circ {\mathbf{X}}_{j,\ast }^0)$$

where $\circ$ is the vector-wise Hadamard product, preserving the $D$-dimensional vector structure. Layer $k$'s output contains all $(k+1)$-order vector-wise interactions. The feature maps of each layer are concatenated after Sum Pooling, then merged with the linear and DNN outputs through Sigmoid:

$$\hat{y}=\sigma ({\mathbf{w}}_{\text{linear}}^T\mathbf{a}+{\mathbf{w}}_{\text{dnn}}^T{\mathbf{x}}_{\text{dnn}}^k+{\mathbf{w}}_{\text{cin}}^T{\mathbf{p}}^{+}+b)$$

Each CIN layer takes vector-wise Hadamard products of "previous layer's feature maps × original input," then compresses them with weights into new feature maps; stacked layer by layer, this yields vector-wise crossings from second order up to T+1 order.

Analysis: xDeepFM combines "explicit vector-wise interactions" with "implicit element-wise interactions," gaining expressiveness and interpretable interactions (which layer corresponds to which order). The cost is the extra computation of the $H_{k-1}\times m$ weighted vector sums in CIN, so the number of feature maps must be set carefully.

3.2.6 AutoInt: Self-Attention Adaptive Interactions

Each DCN layer crosses with $x_0$ in a fixed way, and xDeepFM's CIN also interacts in a fixed manner. AutoInt changes the approach: let the model decide which features interact and how strongly — using the Transformer's self-attention to adaptively learn interactions of arbitrary order.

For features $m,k$, the relevance score of attention head $h$:

$${\alpha }_{m,k}^{(h)}=\frac{\exp ({\psi }^{(h)}({\mathbf{e}}_m,{\mathbf{e}}_k))}{{\sum }_{l=1}^M\exp ({\psi }^{(h)}({\mathbf{e}}_m,{\mathbf{e}}_l))},{\psi }^{(h)}=⟨W_Q^{(h)}{\mathbf{e}}_m,W_K^{(h)}{\mathbf{e}}_k⟩$$

The scores weight and sum the Values to obtain the new representation ${\tilde{e}}_m^{(h)}$; multi-head outputs are concatenated with residual connections added. Stacked layers: the first layer contains second order, the second contains third order, and so on — the interaction pattern is entirely determined dynamically by attention weights. Finally, all layers' representations are concatenated and fed to logistic regression.

💡 Key Insight: The motivational differences among the three high-order crossings are clear at a glance — DCN crosses in a fixed residual way (element-wise), xDeepFM crosses in a fixed CIN way (vector-wise), and AutoInt crosses adaptively with attention. The first two hard-code the interaction pattern; AutoInt leaves "who interacts with whom, how strongly" to the data, which is more flexible and interpretable (inspect the attention matrices).

3.2.7 Interactive Demo: How High-Order Crossings Form Layer by Layer

The interactive demo below gives a hands-on feel for how combinations "second order → third order → higher" are constructed from base features step by step. Click "Next" to observe which new crossing combinations each layer adds.

The demo uses 4 base features (e.g., gender, city, category, price tier) and shows layer by layer: layer 1 produces all second-order combinations, layer 2 crosses second-order ones with base features to get third order, and so on — exactly the intuition behind the explicit high-order crossings in DCN / CIN.

⚠️ Common Mistakes in 3.2

Chapter Summary

📌 Key Takeaways

❓ FAQ

Q1: Why not just let a DNN learn high-order crossings — why FM/DCN?

A: A DNN can learn high orders implicitly, but we don't know which order or which combinations it learned, and sparse combinations are hard to guarantee. FM/DCN/xDeepFM make crossings explicit — controllable, interpretable, and friendlier to sparsity.

Q2: DCN or xDeepFM — which should I pick?

A: If feature interactions are better treated as "whole-vector" relations (e.g., semantic embeddings), xDeepFM's vector-wise form fits better; if simplicity and efficiency suffice and element-wise works, DCN is lighter. In practice, let the validation set and compute budget decide.

Q3: Can AutoInt's attention weights be used as feature importance?

A: Yes. The attention matrices ${\alpha }^{(h)}$ directly show which feature pairs contribute to interactions — a major source of interpretability and one of AutoInt's advantages over DCN/xDeepFM.

🔗 Connections to Later Chapters

• 3.3 (Sequence Modeling) steps out of the "static feature bag" and adds the time dimension; DIN's attention shares its roots with the attention in AFM/AutoInt.
• The shared-bottom structures (Shared-Bottom/MMoE) of 3.4 (Multi-Objective) often use DeepFM-style models as the backbone.
• In Part 2 retrieval, FM is used for two-tower retrieval — two ends of the same technique as its ranking use in this chapter.

Practice Problems

Work through all problems in order — they get progressively harder. Each has a complete solution you can reveal after trying it yourself.

Problem 3.2.1 — FM Parameter Sharing 🟢 Easy

A recommendation scenario has $n=1000$ features, and FM's latent vector dimension is $k=8$. Answer:

1. With the original polynomial model, roughly how many second-order crossing weights $w_{ij}$ are there?
2. With FM's latent-vector scheme, roughly how many parameters? How many orders of magnitude does that save?

Problem 3.2.2 — Identify the Crossing Type 🟢 Easy

Match each description to the correct model among FM / DeepFM / DCN / xDeepFM / AutoInt:

• (a) Does residual crossing with the original input layer by layer, but tears apart every element of the embedding.
• (b) FM and DNN share one set of feature embeddings, learning low-order and high-order separately.
• (c) Uses multi-head self-attention to let the model decide which features should interact and how strongly.
• (d) Takes vector-wise Hadamard products of the previous layer's feature maps with the original input, then compresses.

Problem 3.2.3 — Motivation Follow-up 🟡 Medium

Why can FM still give a reasonable prediction for the crossing $x_i\times x_j$ when features $i$ and $j$ have never co-occurred in the training set? Explain using parameter sharing.

Problem 3.2.4 — Derive FM's Linear Complexity 🔴 Hard

Starting from FM's second-order term ${\sum }_{i<j}⟨v_i,v_j⟩x_i{x}_j$, prove it equals $\frac{1}{2}[({\sum }_i{x}_i{v}_i{)}^2-{\sum }_i{x}_i^2{v}_i^2]$, so the computation cost is $O(kn)$. Also explain: when a feature $x_k=0$, how are its interactions with all other features naturally ignored?

🏆 Challenge: Design a Crossing Scheme

A news app has 500 sparse features. It needs to capture second-order strong rules like "age × category," hopes the model automatically discovers patterns of third order and above, and requires an interpretable structure (being able to see which crossings matter). Pick a combination of 2 from FM / AFM / DCN / xDeepFM / AutoInt and justify your choice (within 150 words).