# Challenge an ICML Paper: For a given set of probability predictions and a log loss value, is the set of true labels giving such a loss unique?

Aggarwal's 2021 ICML paper "Label Inference Attacks from Log-loss Scores", seems to argue that the answer to the question in the title is "YES". The paper claims that, given predicted probability values (such as from a logistic regression or neural network) and the log-loss calculated from those predictions and the true labels, there is an algorithm that will produce the true labels.

This means that the label order giving such a log-loss must be unique. If not, then we could have $$\left\{dog, cat, dog, cat\right\}$$ and $$\left\{dog, dog, cat, cat\right\}$$ result in the same log-loss values.

How would the algorithm be able to pick which set of labels is the correct set!?

Coding $$dog$$ and $$0$$ and $$cat$$ as $$1$$, I believe that I have such an example.

library(ModelMetrics)
p  <- c(0.2, 0.8, 0.8, 0.2)
y0 <- c(0, 1, 0, 1) # dog, cat, dog, cat
y1 <- c(0, 0, 1, 1) # dog, dog, cat, cat
ModelMetrics::logLoss(y0, p) == ModelMetrics::logLoss(y1, p)


Both log-loss values are the same.

The "Results on Real Binary Classification Datasets" section sure makes it look like we can just take a vector of labels and a vector of claimed probability values; calculate the log-loss from the claimed probability values and labels; and perfectly reconstruct the labels, as implied by the, "As our attacks construct..." sentence, yet that is impossible for the p that I gave. There are multiple plausible label vectors (y0 and y).

ICML is one of the top conferences in machine learning, so I do not want to be too quick to dismiss the Aggarwal paper. Nonetheless, I seem to have developed a counterexample.

What's going on?

EDIT

After seeing some answers posted, their claim sounds more plausible, but it still seems to have counterexamples. Consider their example after theorem 1, where $$L_v(\sigma)$$ is the log loss for true labels $$\sigma$$ and predictions $$v$$.

As an example, for N = 5, let v = [2, 3, 5, 7, 11]. Suppose the true labeling is [0, 1, 1, 0, 1]. Then, the adversary observes $$L_v(\sigma) = 1/5 \ln ( 2304/ 55 )$$ (obtained by plugging in $$v$$ and $$\sigma$$ in Equation 2). For reconstructing the labels, observe that $$T = 3\times4\times6\times8\times12 = 6912$$, so that all we need is to compute primes that divide $$T \exp (−NL_v(\sigma)) = 165 = 3 \times 5 \times 11$$. This tells us that only the labels for the second, third and fifth datapoints must be 1, which is indeed true.

However, I get multiple possible $$\sigma$$ values that correspond to the same log-loss value.

library(ModelMetrics)

p  <- c(2, 3, 5, 7, 11)
sigma0 <- c(0, 1, 1, 0, 1) # dog, cat, cat, dog, cat
sigma1 <- c(0, 0, 1, 1, 1) # dog, dog, cat, cat, cat
ModelMetrics::logLoss(sigma0, p) == ModelMetrics::logLoss(sigma1, p)


EDIT 2

Yes, I did make a mistake. This is the correct simulation, and it gives distinct loss values.

v  <- c(2, 3, 5, 7, 11) # The prime number code from the paper
p <- v/(1 + v) # Transform to probability values
sigma0 <- c(0, 1, 1, 0, 1) # dog, cat, cat, dog, cat
sigma1 <- c(0, 0, 1, 1, 1) # dog, dog, cat, cat, cat
ModelMetrics::logLoss(sigma0, p) == ModelMetrics::logLoss(sigma1, p) # Unequal!

• By the way, there's a whole "area of research" on this topic on Kaggle called "leaderboard probing", which is somewhat reduced in efficiency by Kaggle only displaying a limited number of decimal places to prevent this kind of attack that would return the exact label of every item in the public test set. Additionally, that public test set only determines the leaderboard during the competition, not the end at the end of the competition (for which there's a separate private test set). Even rendering the public LB during a competition "useless" would be annoying (hence counter-measures). Mar 29, 2022 at 7:13

Take another look at section 3.1 of the paper.

The 'probability' is not real model output, but a code to hack the response. The statement from the paper has an important addition

We answer the question in affirmative by showing that for any finite number of label classes, it is possible to infer all of the dataset labels from just the reported log-loss scores if the prediction probability vectors are carefully constructed and this can be done without any model training

You need to use a carefully constructed probability vector $$\mathbf{u}$$, or otherwise, you won't be able to infer the labels. With your vector you have repeated probabilities so that makes that you get ambiguities. If you have a vector that has no repeated probabilities and more generally no possibilities that linear combinations of the probabilities are the same, then you can infer the true labels $$\sigma$$ based on the log loss.

The code below demonstrates all the 16 possible log likelihood outcomes when you use the prediction vector

$$\mathbf{u} = (0.413, 0.332, 0.198, 0.057)$$

These outcomes are all unique, and therefore, given that vector $$\mathbf{u}$$ and the given log loss outcome that it produces, you can reverse engineer the labels $$\sigma$$ that have been the input.

library(ModelMetrics)
p = c(0.413,0.332,0.198,0.057)
M = matrix(c(0,0,0,0,
1,0,0,0,
0,1,0,0,
1,1,0,0,
0,0,1,0,
1,0,1,0,
0,1,1,0,
1,1,1,0,
0,0,0,1,
1,0,0,1,
0,1,0,1,
1,1,0,1,
0,0,1,1,
1,0,1,1,
0,1,1,1,
1,1,1,1), 16, byrow=TRUE)  ### all 16 possibilities

losses = apply(M, 1, function(y) ModelMetrics::logLoss(y, p))
losses
### output =
#  0.3038833 0.3917776 0.4786716 0.5665659 0.6535937
#  0.7414880 0.8283820 0.9162763 1.0053871 1.0932814
#  1.1801754 1.2680697 1.3550975 1.4429918 1.5298858
#  1.6177801

### with this specific vector p
### we can even convert the possible losses
### to an integer between 0 and 15
round((losses-0.3038833)/0.08789431)
### output =
#    0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15

• And this assumption seems quite plausible as long as there's no numerical under- or overflow in the model outputs. There are over a billion 32-bit floating point numbers in the interval [0, 1]. For a 1000-way classification problem, the probability of a collision (two or more identical probabilities in the vector) is about 0.0005, assuming all probabilities are equally likely to occur. If you have access to the unnormalized logits, the probability is much lower as there are $10^{44}$ unique 32-bit floating point numbers. Also collisions are only problematic if they are potential solutions. Mar 29, 2022 at 8:20

As my counterexample shows, the answer to the question in the title is that the labels need not be unique.

However, that is not the point of the paper. The paper proposes a method that feeds specific values into the loss function, and the combination of loss value and those specific values reveals the true labels. The values fed into the loss function to do this, however, are not the values from any kind of fitted model; they arise from prime number theory as a way to get the loss function to "confess" what the true labels are.