Learning Feature Interactions

In one line: the signal lives in combinations of features, most combinations never occur, and the history of CTR modelling is a sequence of attempts to learn interactions you have too little data to observe.

The problem, precisely

Two features cross into a combination that predicts a click. There are billions of possible pairs, almost all of which never occur in your data, and the ones that do occur follow the same brutal skew as everything else here.

So you need a model that can say something sensible about a combination it has seen five times, and about one it has never seen at all.

Logistic regression with hand-crossed features

The baseline that ran production ads systems for years, and still a strong one.

Take the sparse one-hot features, add hand-picked crosses, fit a linear model. It is fast, it trains on enormous data, it is interpretable, and each coefficient is a memorised fact: this exact combination has this effect.

Its failure is exactly that memorisation. A combination not in the training data has no coefficient, so the model has nothing to say about it — and the majority of combinations are in that position. It also requires a human to choose which crosses to build, and the number of candidate pairs is far beyond enumeration.

Factorisation machines

The first good answer, and the idea is elegant enough to be worth stating precisely.

Instead of learning a separate weight for each pair, learn a vector for each feature value, and define the interaction between two values as the dot product of their vectors.

LR with crosses:  one weight per observed pair       -> nothing for unseen pairs
FM:               one vector per value; interaction  -> every pair has an estimate,
                  = dot product of the two vectors      including unseen ones

The consequence: a pair that never co-occurred in training still gets a prediction, because both vectors were trained by their other co-occurrences. iPhone learns a vector from every ad it appeared with; luxury watches learns one from every device it appeared on. Their interaction is estimated even if the two never met.

That is generalisation across combinations, and it is the property linear crosses cannot have at any amount of feature engineering.

The limitation: FM models pairwise interactions only. Higher-order combinations need explicit extension, and the interaction form is fixed as a dot product.

Wide and Deep

Google's 2016 argument was that memorisation and generalisation are both necessary and are best served by different components.

The wide part is a linear model over crossed features — it memorises specific, frequent combinations exactly.

The deep part is embeddings into a neural network — it generalises to combinations never seen, by learning that similar values have similar vectors.

They are trained jointly, so each covers the other's failure.

The reason it needs both is a specific failure: a purely deep model over-generalises. Embeddings make everything similar to something, so the model will confidently recommend a plausible-looking combination that is in fact known to perform badly. The wide part is what remembers that this exact pairing does not work.

The complaint about Wide and Deep is that the wide side still needs hand-engineered crosses, so a human is still guessing.

DeepFM

Replace the wide part's hand-crossed linear model with a factorisation machine, and share the embeddings between the FM and the deep component.

Two properties follow. There is no feature engineering — the FM learns pairwise interactions itself, so nobody picks crosses. And the shared embeddings mean the low-order and high-order components learn a consistent representation rather than two unrelated ones.

Later work — DCN and its successors, xDeepFM — pushes on the same problem: learning explicit higher-order interactions rather than hoping a plain MLP discovers them, since an MLP learns interactions only implicitly and not especially efficiently.

The line, in one view

Each row solves a specific failure of the one above. Being able to narrate that progression — rather than name-dropping architectures — is what the question is testing.

What actually moves the number

Worth stating plainly, because the architecture question is a trap for people who over-index on modelling.

Freshness usually beats sophistication. New ads appear constantly and a model that has not seen them has no opinion.

Feature coverage beats architecture. Adding a genuinely new signal — user's recent interaction history, the ad's performance in similar placements — moves the metric more than swapping architectures.

Calibration beats AUC, because the score is multiplied by money.

Serving cost constrains everything. A model that cannot score a few thousand candidate ads inside the budget cannot ship, however good it is offline.

Next: the label imbalance, and the correction that downsampling forces.