Feature Engineering by Preserving Task Similarity

Joseph S. Miller

Abstract

Feature engineering is the process of transforming data to improve its modelability. The transformed representation ought to make a model easier or faster to fit by aligning its coordinates with a pre-specified model class and thereby improve its performance. Once models are fit, their optimal CEs, even after a 1-1 transformation, are generally different in scale and are optimized by different models (as compared when predictions are pushed into a common space). From the perspective of task-oriented modeling, this is a strange situation in which we are optimizing multiple models by CE each with different implicit geometries, and possibly radically different entropy scales, and then evaluating them in a third geometry, often the predictive one, which we actually care about. Our naively transformed data might make the model fit perfectly well in a subspace of the data, but lose all predictive ability for what we care about, or our model might use its capacity to fit irrelevant noise. Below, I develop the idea that when we have a task geometry we care about, we can transport it to the raw data space and then search for transformations that best retain the task distinctions we care about, measuring similarity-sensitive entropy in the transformed spaces. We will end up with cross entropies that can theoretically be compared, and ideally, a task-oriented feature engineering.

Scaling and PCA choose a geometry

First, an orientation from the perspective of SS-entropy. Take an ordinary data matrix with coordinates $x_1,\ldots,x_d$. If I scale coordinate $j$ by a positive number $s_j$, Euclidean distance in the transformed coordinates becomes

$$d_s^2(x,x')=\sum_{j=1}^d\frac{(x_j-x_j')^2}{s_j^2}.$$

A change of one unit in a coordinate with small $s_j$ now counts more than the same change in a coordinate with large $s_j$, so the scaling influences closeness whenever the downstream model uses this Euclidean geometry. Standardization will lead us to considering a standard-deviation change in each measured coordinate as comparable. If we imagine the SS-entropy with an isotropic radial similarity kernel, its pullback to the raw coordinates has this geometry.

Because full PCA is an orthogonal rotation it leaves Euclidean distances, and any kernel that depends only on those distances, unchanged. A non-orthogonal transformation preserves a specified kernel if we transport the kernel with it. When we keep only some PCA components, we discard low-variance directions even if they matter to the task. I would rather specify the relevant distinctions first, express them through $K$, and then consider simpler representations that preserve them.

A task-preserving representation

Let $K^\star(x,x')$ be the similarity kernel I want to preserve. I'll start with a feature map $T:\mathcal X\to\mathcal Z$ and an output kernel (which we desire to be "simple"). Together they induce the pullback kernel

$$K_T(x,x'):=K_Z(Tx,Tx').$$

The (strong, distribution-free) condition is

$$K_T(x,x')=K^\star(x,x')\qquad\text{for every }x,x'.$$

Note that this gives $H_{K^\star}(P_X)=H_{K_Z}(T_\#P_X)$ for every $P_X$.

I'll call this "kernel sufficiency" for now. The map $T$ may be many-to-one: it is allowed to discard raw distinctions as long as they do not change the target similarity (no ambiguity in the pullback). For a law $Q$, write its typicality as

$$\tau_{K,Q}(x):=(KQ)(x) :=\mathbb E_{X'\sim Q}K(x,X').$$

When $H_K$ is concave, the proper tangent loss derived in the scoring-rule essay is

$$S_K(Q,x)=-\log\tau_{K,Q}(x) -\left[ \mathbb E_{Y\sim Q} \frac{K(Y,x)}{\tau_{K,Q}(Y)}-1 \right].$$

I will use $K$-cross-entropy, or $K$-CE, for its expected risk:

$$\mathcal C_K(P,Q):=\mathbb E_{X\sim P}S_K(Q,X).$$

If $P_Z=T_\#P_X$ and $Q_Z=T_\#Q_X$, kernel sufficiency gives

$$\boxed{ \mathcal C_{K^\star}(P_X,Q_X) =\mathcal C_{K_Z}(P_Z,Q_Z)}. $$

That is the $K$-cross-entropy invariance that I propose is valuable: $\mathcal C_K$ has the same value before and after an exact task-respecting transformation. Ordinary cross-entropy does not have this invariance. I'll note that $\mathcal C_K$, being nonlocal, is more expensive to compute than CE. If we can push most of the complexity into the map $T$, fitting a model in $Z$ with CE and evaluating or fine tuning with $\mathcal C_K$ at the end is reasonable. This would give us a common scale on which to compare representations, and a principled distribution-free goal for finding $T$. What follows are two examples, the first being the simplest.

But before that, I want to separate the two cases specifically where the above general equality appears useful. If a task kernel is naturally specified on an outcome space $Y$ that we want to predict, we ought to straightforwardly model $Y$ (from observed $X$, if available) and fit with $K$-CE. If $K$-CE is too expensive, we may want to transform $Y$ so that the output kernel is more "diagonal" and plausibly better approximated with CE. I hope to develop this further in a later essay. The other interesting case is when we can attain a $K^\star$ on a future or downstream outcome while $X$ is available at deployment. Perhaps we can choose a kernel over a rich object—such as a paragraph or molecule—for which similarity is easy to specify, and we intend to model directly from its embedding $X$. Then the aim is to find the above $T(X)$ that retains the task-relevant distinctions in the kernel while ignoring nuisance variations in $X$. In these cases we expect an independently specified task signal and want to compress $X$ to retain it for later modeling.

Simple finite coarsening example

I'll demonstrate a transformation in the simplest setting. Starting with seven raw states

$$A_1,A_2,\quad B_1,B_2,\quad C_1,C_2,C_3$$

and a similarity kernel pulled back to this same space: the two $A$ states have identical similarity profiles, as do the two $B$ states. The task cannot distinguish the members of either pair. The three $C$ states remain distinguishable, although they're almost identical.

The original seven-state kernel factors exactly through the five-state coarsening, so any score that depends on the states through this kernel is unchanged.

By approximating, we can choose the transformation that merges $C_1,C_2,C_3$ into one state $C$ and pick the identity kernel on $(A,B,C)$. The pullback of this approximation changes only the off-diagonal similarities within the $C$ block, from $0.95$ to $1$ losing a small amount of information for many distributions.

For example, under a uniform distribution on the seven raw states, the exact five-state pushforward has probabilities $(2,2,1,1,1)/7$ and

$$H_{K_5}(P_5)=1.5776\ \text{bits}.$$

The approximate three-state pushforward has probabilities $(2,2,3)/7$, so with the identity kernel

$$H_I(P_3)=1.5567\ \text{bits}.$$

In return for this loss, the output kernel is the identity, so the tangent loss reduces to categorical log loss and $K$-CE reduces to ordinary categorical cross-entropy. In the end, we've traded a little task resolution for a simpler representation and simpler scoring problem, with the change measured by entropy over the empirical distribution.

Learning Gaussian task coordinates

I now want a continuous example where we can reduce the dimensionality of the representation. We'll do this one by assuming we have a similarity oracle we can query and fit to learn the kernel over the raw space. Let $X\in\mathbb R^{50}$ contain four task-relevant coordinates $U$ and 46 high-variance nuisance coordinates, mixed up by a random orthogonal rotation. There is an unknown matrix $B$ such that $U=BX$, and the task similarity is

$$K^\star(x,x') =\exp\!\left[-\frac{\lVert B(x-x')\rVert^2}{2}\right].$$

We observe either 1,000 or 4,000 noisy similarity ratings and use 80% of the ratings to estimate a rank-twelve linear map while reserving 20%, drawn from different samples, to guard against overfitting. From this map we construct a nested family

$$T_r(x):=A_rx,\qquad K_r(x,x') :=\exp\!\left[-\frac{\lVert A_r(x-x')\rVert^2}{2}\right], \quad r=1,\ldots,12.$$

Each $A_r$ keeps the first $r$ directions from the estimated map, and $K_r$ measures similarity using those directions. I then evaluate each kernel on independent held-out samples:

$$\widehat H_{K_r} =-\frac{1}{m}\sum_{i=1}^{m} \log_2\!\left[ \frac{1}{n}\sum_{j=1}^{n}K_r(X_i,X_j') \right].$$
Similarity-sensitive entropy on held-out samples by retained dimension for the full task kernel, known task directions, and task coordinates learned from one thousand or four thousand noisy pair ratings.

The full task entropy is $2.296$ bits. At rank four, the representation learned from 1,000 ratings has held-out entropy $2.169$; with 4,000 ratings it reaches $2.244$. The key thing is that $X$ alone does not identify which directions are nuisance, but the pairwise queries do. PCA has no access to those ratings and the task coordinates will be overwhelmed by the 46 nuisance dimensions. Most importantly, this procedure respects the truth that the task has 2.296 bits of entropy and our procedure can estimate that. But matching that entropy is not enough to show that the learned kernel has recovered the same distinctions, and shouldn't be used alone to reduce dimension snice we can't decide what rank model to use from only this plot.

Choosing the number of coordinates

Entropy is a scalar, so an approximate kernel may separate some observations the task regarded as substitutes and merge others the task distinguished, with the two errors canceling. One way to check the curve is to define

$$K_\cap(x,x'):=\min\{K^\star(x,x'),K_r(x,x')\}.$$

(Analogously, we can use the max with the corresponding changes to the definition.) This gives two nonnegative quantities:

$$\begin{aligned} D_{\mathrm{added}}^H &:=H_{K_\cap}(P)-H_{K^\star}(P),\\ D_{\mathrm{removed}}^H &:=H_{K_\cap}(P)-H_{K_r}(P). \end{aligned}$$

Reduced similarity creates distinctions that didn't exist in $K^\star$ and adds entropy; increased similarity erases distinctions and removes entropy. Their difference is the signed change in entropy and these errors might cancel, while their sum gives a summed error:

$$\begin{aligned} H_{K_r}(P)-H_{K^\star}(P) &=D_{\mathrm{added}}^H-D_{\mathrm{removed}}^H,\\ D_{\mathrm{total}}^H &:=D_{\mathrm{added}}^H+D_{\mathrm{removed}}^H. \end{aligned}$$
Summed error by retained dimension for representations learned from one thousand and four thousand similarity ratings.

This criterion allows us to see the true task dimension well. With 1,000 ratings, ranks four and five differ by only $0.0004$ bits. Higher rank models worsen things without enouh oracle data. With 4,000 ratings the plateau is clear and we see that 4 coordinates is ideal.

A proposed workflow

The workflow I would consider is to first define or elicit a target similarity $K^\star$. Then, fit a transformation and simple output kernel on one set of pairwise task signals, compare the retained task entropy across dimensions on held-out objects, choose a dimension by adding up the entropy gained and lost, then fit a model to the resulting task coordinates. Evaluate models with $K$-CE if the kernel is known to lead to a concave entropy.

Dimension reduction is not the only possible benefit. Among representations with similar fidelity, we may prefer coordinates that are interpretable, statistically stable, easy to model, or cheap to score. But low task dimension is a useful place to begin and shows how a high-dimensional observation can contain a much smaller task without equating task information with raw-data variation.

Once we've chosen a representation for the task, there is a separate question: should one fit its complete density by ordinary cross-entropy, or is the finite resolution of the task important in changing the fit? I will discuss that in a later essay.