Deep Learning for High-Cardinality Categoricals

The general claim that trees beat networks on tabular data has a clear and commercially enormous exception. Where the important features are identifiers with millions of levels, user ID, item ID, advertiser, publisher, search query, networks win decisively, and the reason is specific rather than a matter of capacity.

Why trees struggle

A decision tree splits on a feature by partitioning its values. For a numerical feature that is a threshold; for a categorical feature with \(k\) levels it is a subset, and there are \(2^{k-1} - 1\) non-trivial ones. Efficient implementations use a heuristic ordering by target statistic rather than searching subsets, which works at moderate cardinality and degrades as levels multiply.

The deeper problem is that a tree treats levels as atomic. It learns nothing about level A from data about level B, so a level appearing five times has its behaviour estimated from five observations. With a million levels following a long-tail distribution, most levels are rare and most of the data is about levels the model cannot generalise from.

Why embeddings work

An embedding assigns each level a learned vector in a shared space. Levels that behave similarly end up nearby, so statistical strength is shared: a rare item's embedding is shaped by the gradient it receives and by the structure of the space that frequent items established.

The representation is also compositional. Concatenating user and item embeddings and passing them through a network learns interactions that a tree would need many splits to approximate, and the same embeddings serve every downstream task in the system.

This is why recommendation, search ranking and advertising moved to neural models while general tabular problems did not. Their defining features are exactly the ones embeddings handle and trees do not.

What dominates these systems

Embedding tables are the parameters. A model with a hundred million items at 64 dimensions has 6.4 billion embedding parameters and a network on top with a tiny fraction of that. Memory, sharding across machines and lookup latency dominate the engineering, and the dense part is almost incidental.

The tail dominates the difficulty. Frequent items have well-estimated embeddings and rare ones do not, so most modelling effort goes into the long tail: initialisation from content features, hashing to share capacity, and hierarchical fallbacks to a category embedding.

Vocabulary churn is continuous. New items appear constantly and old ones die, so the table is not static and cold start is the normal case rather than an edge case.

When it breaks

Hashing collisions are silent. Mapping a large vocabulary into a fixed number of buckets is standard and makes unrelated items share a vector, which is harmless for rare items and damaging when two frequent ones collide. Multiple hash functions with combined embeddings reduce the damage without eliminating it.

Embeddings memorise identity, which is a privacy surface. A user embedding trained on that user's behaviour encodes it, and sharing or exporting the table exports the behaviour. Embedding tables deserve the access controls applied to the underlying data.

Frequency imbalance skews training. Popular items receive vastly more gradient updates, so their embeddings converge while the tail barely moves. Negative sampling strategy and frequency-aware learning rates are what address it, and getting them wrong produces a model that is excellent on the head and useless elsewhere.

Embedding dimension is a capacity decision made once. It is fixed at training time, applies uniformly to items with wildly different amounts of data, and changing it means retraining everything downstream that consumed the vectors.