Features

Three concrete reasons. High cardinality: a one-hot over a million values cannot be built, and target encoding loses the semantics — two items with the same average CTR and different audiences are merged into one number, and that costs 50% of the clicks in a simple example with two segments.

Unstructured data: texts, pictures, history — features can be generated from them, but it works worse.

And the main one: embeddings at the input of a tree work badly in principle. The coordinates mean nothing individually, and a split looks at one coordinate; to distinguish 4 levels along each of 16 dimensions you need 4.29 billion leaves, while a linear layer gets by with 16 multiplications.

Plus two practical arguments: many signals at once, and drift — boosting has to be rebuilt entirely, a network can be fine-tuned.

When not a single point of the checklist holds: plenty of data, important high-cardinality features, unstructured data, many signals, a need for fast fine-tuning. If none of that is there, CatBoost on aggregates will be both cheaper and better.

The main drawback of networks is the barrier to entry: GPUs, distributed training, inference in a runtime. That is a real cost, and pretending it does not exist is not a good look in an interview.

Represent the category by a one-hot vector \(e_i \in \{0,1\}^n\) and multiply by a matrix \(W \in \mathbb{R}^{n \times d}\) with no bias. The result \(e_i W\) is the \(i\)-th row of \(W\). So \(W\) is the embedding table, and a lookup is simply an optimisation of a multiplication by a sparse vector.

A useful consequence: at \(d = 1\) the model learns the average CTR of a value, that is, target encoding is the special case of an embedding of dimension one. Everything an embedding gives beyond that is the dimensions in which «who exactly likes it» fits.

It should depend on the cardinality and on the informativeness of the feature; the same size for everything is suboptimal.

The informational estimate: \(d\cdot s = \log_2 n\) bits. Google's heuristic: \(d = 6\sqrt[4]{n}\). The gap between them is enormous — at \(n=10^7\) that is 23 bits against d = 337 — and it is meaningful: almost all the capacity goes into semantics rather than identification.

The heuristic is not taken literally: at \(n=10^9\) it gives 1067 and 4.3 terabytes for one feature. In production the typical dimensions are 32 to 128, and the honest route is to choose the dimensions during training.

Batched lookup: combine the tables of all features into one matrix and do a single lookup with an offset — otherwise you get many small operations on the GPU with the overhead of a kernel launch.

Sparse gradients: a batch of 4096 samples touches no more than 4096 rows out of 10 M, that is, 0.041% of the table; the rest of the gradients are zeros and need neither updating nor sending between cards. An important subtlety: for such parameters the learning rate is worth increasing, because they are updated far less often than dense weights.

Row-wise optimiser: keep Adam's statistics per row rather than per parameter. A table of 10 M × 256 takes 10.2 GB, with Adam's moments 30.7 GB, and with row-wise statistics 10.32 GB, that is, 0.8% more than the table.

Plus sharding, offloading to the CPU and the hashing trick when the tables do not fit on a GPU.

Because networks are sensitive to scale (large values dominate the gradient), break on outliers and cannot handle missing values. Trees have none of these problems — this is the price of moving to networks.

Five transformations: a logarithm against skew; a sigmoid that squeezes outliers (with normalisation before it, otherwise the gradients vanish); the cumulative distribution function, which brings the feature to a uniform distribution; periodic functions for time; quantisation by quantiles.

Quantisation has a fundamental drawback — the order relation is lost both between bins and inside a bin. Piecewise linear encoding repairs that.

Because in raw form 23 and 0 are the most distant pair possible, though they are adjacent hours. The model is forced to spend capacity on learning the join at the boundary of the day.

A sine-cosine pair of one frequency places time on a circle: the distance between 23 and 0 becomes 0.2611 — exactly the same as between 0 and 1, and the smallest possible. The most distant pair turns out to be 23 and 12, the opposite points of the day, as it should be.

Several frequencies give several circles of different scale — the hour, the day of the week and the season at once. The mechanism is the same as for positional embeddings in a transformer.

Piecewise linear encoding: a vector of length T where to the left of the current bin there are ones, to the right zeros, and exactly one component is fractional — the share of the bin travelled. A linear layer on top of such a vector gives a continuous piecewise linear function.

The difference from a one-hot by bins: inside a bin the output is not a constant but moves linearly. On approximating \(x^2\) with 16 bins the MSE differs by a factor of 857. And more important than the gap is how it grows: for piecewise constant encoding the error falls as \(T^{-2}\), for piecewise linear as \(T^{-4}\).

Because it separates two regimes that are mixed together in a dense vector. A dense content vector is a «soft» feature: the model generalises from it but cannot memorise the specifics of a particular object. A discrete hierarchical code gives both: the shared prefix is responsible for generalising to similar objects, the full code for memorising the particular one.

This is exactly the case where discretisation does not lose information but structures it. The flip side of the same argument is the hashing trick: its identifiers carry no semantics, so for a new object you get a combination the model has never seen — full reliance on memorisation and zero generalisation.