How to Train Your Accuracy?

如何训练你的准确率？ 苏剑林 · 2022-06-01 · Machine Learning probability optimization loss function

A recent paper on Arxiv, EXACT: How to Train Your Accuracy, caught my attention. As the title suggests, it's about how to train models directly with accuracy as the optimization target. As it happens, I've done some analysis on this topic before, e.g. in Musings on Function Smoothing: Differentiable Approximations to Non-Differentiable Functions and Revisiting Class Imbalance: Comparing Weight Adjustment and Loss Modification, so I was able to get through the paper quickly with that background, and this post is my summary of it, along with some fresh thoughts on the topic that occurred to me recently.

A Misleading Example

The paper opens by pointing out that the classification loss functions we normally use — cross-entropy, or Hinge Loss as in SVMs — don't fit the final evaluation metric, accuracy, very well. To illustrate this, the paper gives a very simple example: suppose the data consists of just three points $\{(-0.25,-1),(0,-1),(0.25,,1)\}$, with $-1$ and $1$ representing the negative and positive classes respectively, and the model to be fit is $f(x)=x-b$, with $b$ as the parameter; we hope to predict the class via $\text{sign}(f(x))$. If we use "sigmoid + cross-entropy," the loss function is $-\log \frac{1}{1+e^{-l \cdot f(x)}}$, where $(x,l)$ denotes a pair of labeled data; if we use Hinge Loss, it's $\max(0, 1 - l\cdot f(x))$.

Since this is just a one-dimensional model, we can directly grid-search for its optimum, and we find that with "sigmoid + cross-entropy," the loss is minimized at $b=0.7$, while with Hinge Loss it's $b\in[0.75,1]$. However, to classify everything correctly via $\text{sign}(f(x))$, we'd need $b\in(0, 0.25)$, and so this is presented as demonstrating the mismatch between cross-entropy or Hinge Loss and the final accuracy metric.

This looks like a neat and elegant example, but I don't think it holds up. The biggest problem is the absence of a temperature parameter in the model: the models that actually get used in practice take the form $f(x)=k(x-b)$, not $f(x)=x-b$. Deliberately dropping the temperature parameter to construct a counterexample that doesn't match reality isn't convincing — in fact, once you add back an adjustable temperature parameter, both of these losses can learn the correct answer. What's even more unfair is that later, when the authors introduce their own scheme, EXACT, it comes with a temperature parameter built in, and that temperature parameter is a key ingredient. In other words, in this example, EXACT only looks better than the other two losses purely because EXACT has a temperature parameter and they don't.

Old Wine in a New Bottle

Next let's look at the scheme proposed in the paper — EXACT (EXpected ACcuracy opTimization). In hindsight, EXACT is rather baffling, because the authors, without any explanation, redefine a conditional probability distribution $p(y|x)$ from a reparameterization perspective:

\begin{equation}p(y|x) = P\left(y = \mathop{\text{argmax}}_i \frac{\mu(x)}{\sigma(x)}+\varepsilon\right)\end{equation}

Here $\mu(x)$ is a vector-valued network, $\sigma(x)$ is a scalar-valued network, $\varepsilon$ has the same dimension as $\mu(x)$, and each component is i.i.d. sampled from $\sim \mathcal{N}(0,1)$. We already discussed the approach of defining probability distributions via reparameterization in the previous post Constructing Discrete Probability Distributions from a Reparameterization Perspective, so I won't repeat that here.

Having defined this new $p(y|x)$, the authors then directly take

\begin{equation}-\mathbb{E}_{(x,y)\sim\mathcal{D}}[p(y|x)]\label{eq:soft-acc}\end{equation}

as the loss function, and that's basically the entirety of the paper's theoretical framework.

From this we can pin down exactly what's baffling about EXACT. As we know from Constructing Discrete Probability Distributions from a Reparameterization Perspective, from the reparameterization viewpoint, the noise distribution corresponding to Softmax is the Gumbel distribution, whereas EXACT swaps this out for a normal distribution. So what's the benefit of that? Why would it be better? None of this is explained.

Moreover, the fact that the negative of expression $\eqref{eq:soft-acc}$ is a smooth approximation to accuracy is already "widely known," but it is likewise widely known that directly optimizing expression $\eqref{eq:soft-acc}$ under a Softmax generally performs worse than optimizing cross-entropy. Here we've just swapped in a "new bottle" (a new way of constructing the probability distribution) to hold the same "old wine" (the same smooth approximation to accuracy) — can this really lead to any improvement?

Experiments Hard to Reproduce

The original paper reports remarkable experimental results, showing EXACT achieving state-of-the-art performance almost across the board:

Experimental results from the original EXACT paper

However, I tried implementing EXACT based on my own understanding of the paper and tested it on NLP tasks, and the results showed that EXACT falls well short of "Softmax + cross-entropy." Furthermore, the original paper claims that optimizing $-\log\mathbb{E}_{(x,y)\sim\mathcal{D}}[p(y|x)]$ is better than $\eqref{eq:soft-acc}$, but in my tests this variant didn't even match $\eqref{eq:soft-acc}$. Overall, my test results are quite far from those in the original paper.

Since the original paper hasn't released its code, I can't further judge the reliability of its experiments. But based on my theoretical understanding and preliminary experimental results, directly optimizing expression $\eqref{eq:soft-acc}$ seems very unlikely to match the effect of optimizing cross-entropy — merely changing how the probability distribution is constructed shouldn't be able to produce any substantive improvement. If readers have new experimental results, I'd welcome further discussion.

A New Perspective

Numerically speaking, expression $\eqref{eq:soft-acc}$ is indeed a closer fit to accuracy than cross-entropy $\mathbb{E}_{(x,y)\sim\mathcal{D}}[-\log p(y|x)]$ is. But why does optimizing cross-entropy so often achieve better accuracy? I used to be quite puzzled by this myself, and in Revisiting Class Imbalance: Comparing Weight Adjustment and Loss Modification, I had no choice but to just treat it as an "axiom" and move on.

Then one day, it suddenly dawned on me that there's a relationship worth noting: as training proceeds, most values of $p(y|x)$ gradually approach 1, so using the approximation $\log x \approx x - 1$ we get

\begin{equation}\mathbb{E}_{(x,y)\sim\mathcal{D}}[-\log p(y|x)]\approx \mathbb{E}_{(x,y)\sim\mathcal{D}}[1 - p(y|x)] = 1 - \mathbb{E}_{(x,y)\sim\mathcal{D}}[p(y|x)]\end{equation}

This lets us explain why optimizing cross-entropy can also achieve good accuracy: from the expression above we can see that, in the middle-to-late stages of training, cross-entropy is essentially equivalent to expression $\eqref{eq:soft-acc}$ — that is, it too is optimizing a smooth approximation to accuracy!

So where does cross-entropy's advantage over expression $\eqref{eq:soft-acc}$ lie? The difference lies in the gap between $-\log p(y|x)$ and $1 - p(y|x)$ when $p(y|x) \ll 1$. When $p(y|x) \ll 1$, i.e. the probability of the target class is very small, meaning the classification is likely quite wrong, $-\log p(y|x)$ gives a result that tends to infinity, whereas $1 - p(y|x)$ can give at most $1$. Comparing the two, we see that cross-entropy's $-\log p(y|x)$ imposes a much heavier penalty on misclassified samples, so it will be more inclined to correct misclassified samples, while its final classification outcome still ends up close to that of directly optimizing the smooth approximation to accuracy.

From this, we arrive at a new perspective on what makes a good loss function:

First, find a smooth approximation to the evaluation metric, ideally expressible as an expectation over individual samples. Then, push the error toward infinity in the "wrong" direction (to ensure the model pays more attention to misclassified samples), while ensuring the loss remains a first-order approximation to the original form in the "correct" direction.

Summary

This post has mainly discussed the question of how to optimize accuracy. I first gave a brief introduction to and critique of the recent paper EXACT: How to Train Your Accuracy, and then offered my own analysis of "why optimizing cross-entropy achieves better accuracy results."