This paper is on quantifying information gain afforded by a label representation (for a fixed encoder). At a high level, the paper proposes a certain quantification (which is called a "unit") of this information gain, observes that the one-hot representation (equivalently, the simplex) is a natural notion of null in terms of label representations. It further decomposes its definition of information gain into two parts: the gain (or really loss) arising from deviating in arrangement from the simplex, and the gain from assigning explicit labels to the elements of a frame (which, e.g., may be organized so that semantically similar labels occupy similar label vectors).
\newcommand{\ig}{\mathrm{IG}} \newcommand{ar}{\operatorname{arrGain}} \newcommand{\as}{\operatorname{asgnGain}} \newcommand{\softmax}{\operatorname{softmax}} \newcommand{\nll}{\mathrm{NLL}}.
The quantification proposed arises thus: suppose that one is trying to predict a label using ridge regression: herein, one may regress (encoded) features X onto a given representation of the labels. Observe that because ridge predictions are linear in the response observations, one can decompose the effect of a different label representation linearly. Now, for a given training dataset (X,Y), validation set (\tilde{X}, \tilde{Y}), let G be the operator that computes first regresses X onto Y (in the one-hot simplex representation), and then produces the predictions for Y~. Then Y^ under the label representation Z is simply GZ.
Now, of course, this ridge procedure does not itself produce a label, or even a distribution over labels. The authors consider the following way to do this: for a ridge prediction y^, let Dℓ denote the squared distance of y^ for zℓ, the representation for the ℓth point, and let p(y)=\softmax(−D/τ) be the induced distribution. For any representation Z, its associated normalised log likelihood for label i is \nlli:=E[−logp(i)∣y=i], where the average is occurring over draws of (validation) instances, and the information gain is $ \ig(Z) := \frac{1}{n} \sum_i (\log (n) - \nll_i),$ where (in a roundabout way in the text) all the logs are base 2. Evidently, this can be measured using a validation set. This information gain is presented as a measure of the quality of the representation. It should be noted that the distribution p depends on Z through only the Gram matrix K=ZZ⊤, and so we can equivalently identify these measures as functions of K. I'll use both below, as the paper does. In any case, the paper standardises K by demanding that its rows (and thus columns too) are centred, and that its trace is fixed to nd.
The authors further propose a decomposition of this \ig. This arises in two steps, stemming from the fact that one can see a label representation as jointly specifying an arrangement of points to the label space, and an assignment of specific label identities to each of these points. Note that the latter property is nontrivial, in that in problems with semantic structure on the labels (or I guess in hierarchical problems too, although the paper doesn't note this), there are certain senses in which subsets of labels are more naturally grouped together, and even for a given arrangement, a poor assignment can violate such implicit structure. Note specifically that one can modify assignment by permuting the entries of Z. The authors propose explicitly capturing what each of these aspects gives thus:
-
First a reference level is defined. This arises as M0:=EZˉ[\ig(Zˉ)], where Zˉ is drawn thus: draw n iid points according to a reference distribution (Gaussian) appropriately normalised, and permute it arbitrarily (for iid reference, the permutation is unnecessary). This M0 is a reference property of the learning task at hand.
-
Second, at an "arrangement level", the arrangement of Z is fixed, but the assignment is randomised, giving M1(Z)=Eπ[\ig(PπZ)], where π is drawn uniformly over permutations, and Pπ is the standard matrix representation of π.
-
Third, at the arrangement and assignment level, both values are fixed to get M2(Z)=\ig(Z).
Then the effect of the arrangement is isolated as \ar(Z):=M1(Z)−M0(Z) and that of assignment with a given arrangement as \as(Z):=\ig(Z)−M1(Z).
An observation is then made that the arrangement gain can only be smaller than that for the simplex: is because \ig is a concave map of the Gramian K, and the average gramian under the permutation structure is that of the simplex, denoted Ks, giving \ar(K)≤\ig(Ks)−M0. Further, it is noted that the assignment gain of the simplex is nought, because permuting the simplex leaves it invariant. In other words, M1(Ks)=\ig(Ks). This sets up the simplex as a notion of null: it maximises arrangement gain, and has no assignment gain, and further arises naturally from the simple priors picked.
This sets up a notion of "arrangement rent," defined as \ig(Ks)−M1(K)=M1(Ks)−M1(K), the amount of information that choosing the non-flat arrangement costs. This needs to be offset by the assignment gain in order for the label representation to gain, in terms of \ig, over the flat representation.
Nex, the authors work out that in the limit as ∣K−Ks∣→0, the arrangement gain can be written as a linear function of the fluctuation in the diagonal entries of K, and the trace of K2 up to the third order, which arises from symmetry considerations induced by the uniform permutation, and an explicit formula is developed in the appendix (specifically, coefficients of these two entries are derived in terms of the ridge fit in a certain limit). It is argued that this captures arrangement gain better than only a spectrum-dependent measure like logsumdet.
Finally, the paper computes these three metrics for four choices of label representation (the simplex, one "label-name representation" arising as an average of many text embeddings, and two from psychometrics), which are evaluated against four encoders (3 neural, one non-neural). The main observation appears to be that the label-name rep indeed gains over the simplex in terms of \ig, and that this (necessarily) occurs because the assignment gain wins over the arrangement rent. Further, evaluation of the functional capturing the the arrangement gain is given, and in particular both it and a radial-index (essentially the variance of diagonal entries term above) capture it much better than purely spectral quantities.