An Unsuccessful Attempt: Generalizing Multi-Label Cross-Entropy to "n groups of m-class classification"

不成功的尝试：将多标签交叉熵推广到“n个m分类”上去 苏剑林 · 2022-07-15 · Mathematics optimization loss function

Some readers may have noticed that this update has come after quite a long gap. In fact, I started preparing this post last weekend, but I underestimated the difficulty of the problem — I've spent almost an entire week deriving things and still haven't arrived at a satisfactory result. What I'm posting now is still, honestly, a failed attempt, and I hope readers with more experience can offer some guidance.

In the post Generalizing "Softmax + Cross-Entropy" to Multi-Label Classification, we proposed a multi-label classification loss function that automatically balances the imbalance between positive and negative classes, and later, in A Soft-Label Version of Multi-Label "Softmax + Cross-Entropy", we further derived its "soft-label" version. Essentially, multi-label classification is a problem of "$n$ binary classifications." Correspondingly, what would the loss function for "$n$ groups of $m$-class classification" look like?

That is the question this post sets out to explore. more

An Analogy-Based Attempt

In the post on the soft-label generalization A Soft-Label Version of Multi-Label "Softmax + Cross-Entropy", we obtained the final result by directly taking a first-order truncation, within $\log$, of the sigmoid cross-entropy loss for "$n$ binary classifications." The same process can indeed be extended to the softmax cross-entropy loss for "$n$ groups of $m$-class classification" — this was my first attempt.

Let $\text{softmax}(s_{i,j}) = \frac{e^{s_{i,j}}}{\sum\limits_j e^{s_{i,j}}}$, with $s_{i,j}$ as the predictions and $t_{i,j}$ as the labels. Then

\begin{equation}\begin{aligned}-\sum_i\sum_j t_{i,j}\log \text{softmax}(s_{i,j}) =&\,\sum_i\sum_j t_{i,j}\log \left(1 + \sum_{k\neq j} e^{s_{i,k} - s_{i,j}}\right)\\ =&\,\sum_j \log \prod_i\left(1 + \sum_{k\neq j} e^{s_{i,k} - s_{i,j}}\right)^{t_{i,j}}\\ =&\,\sum_j \log \left(1 + \sum_i t_{i,j}\sum_{k\neq j} e^{s_{i,k} - s_{i,j}}+\cdots\right)\\ \end{aligned}\end{equation}

The summation over $i$ defaults to $1\sim n$, and the summation over $j$ defaults to $1\sim m$. Truncating the higher-order terms of $\cdots$, we get

\begin{equation}l = \sum_j \log \left(1 + \sum_{i,k\neq j} t_{i,j}e^{- s_{i,j} + s_{i,k}}\right)\label{eq:loss-1}\end{equation}

This is the loss I initially arrived at — a natural generalization of the earlier result to "$n$ groups of $m$-class classification." Indeed, if $t_{i,j}$ are hard labels, this loss works essentially without issue. But I wanted it to behave like the one in A Soft-Label Version of Multi-Label "Softmax + Cross-Entropy", i.e., to admit an analytical solution for soft labels as well. To this end, I took its derivative:

\begin{equation}\frac{\partial l}{\partial s_{i,j}} = \frac{- t_{i,j}e^{- s_{i,j}}\sum\limits_{k\neq j} e^{s_{i,k}}}{1 + \sum\limits_{i,k\neq j} t_{i,j}e^{- s_{i,j} + s_{i,k}}} + \sum_{h\neq j} \frac{t_{i,h}e^{- s_{i,h}}e^{s_{i,j}}}{1 + \sum\limits_{i,k\neq h} t_{i,h}e^{- s_{i,h} + s_{i,k}}}\end{equation}

By "analytical solution," I mean solving via the equation $\frac{\partial l}{\partial s_{i,j}}=0$. However, after several days of trying, I couldn't find a solution to this equation — I suspect there isn't a simple closed form. So this first attempt failed.

Working Backwards from the Result

After several days of getting nowhere, I flipped my approach: since the result obtained by direct analogy couldn't be solved, why not work backwards from the result instead — first fix what the solution should be, and then figure out what the corresponding loss (equation) must look like. This led to my second attempt.

First, I observed that the original multi-label loss, as well as the loss $\eqref{eq:loss-1}$ derived above, both share the following form:

\begin{equation}l = \sum_j \log \left(1 + \sum_i t_{i,j}e^{- f(s_{i,j})}\right)\label{eq:loss-2}\end{equation}

Taking this form as our starting point, we compute the derivative:

\begin{equation}\frac{\partial l}{\partial s_{i,k}} = \sum_j \frac{- t_{i,j}e^{- f(s_{i,j})}\frac{\partial f(s_{i,j})}{\partial s_{i,k}}}{1 + \sum\limits_i t_{i,j}e^{- f(s_{i,j})}}\end{equation}

We want $t_{i,j}=\text{softmax}(f(s_{i,j}))=e^{f(s_{i,j})}/Z_i$ to be the analytical solution of $\frac{\partial l}{\partial s_{i,k}}=0$, where $Z_i=\sum\limits_j e^{f(s_{i,j})}$. Substituting this in, we get

\begin{equation}0=\frac{\partial l}{\partial s_{i,k}} = \sum_j \frac{- (1/Z_i)\frac{\partial f(s_{i,j})}{\partial s_{i,k}}}{1 + \sum\limits_i 1/Z_i} = \frac{- (1/Z_i)\frac{\partial \left(\sum\limits_j f(s_{i,j})\right)}{\partial s_{i,k}}}{1 + \sum\limits_i 1/Z_i}\end{equation}

So, for the equation above to hold naturally, we find that we only need $\sum\limits_j f(s_{i,j})$ to equal a constant independent of $i,j$. For simplicity, let's set

\begin{equation}f(s_{i,j})=s_{i,j}- \bar{s}_i,\qquad \bar{s}_i=\frac{1}{m}\sum_j s_{i,j}\end{equation}

This naturally gives us $\sum\limits_j f(s_{i,j})=0$, and the corresponding optimization objective is

\begin{equation}l = \sum_j \log \left(1 + \sum_i t_{i,j}e^{- s_{i,j} + \bar{s}_i}\right)\label{eq:loss-3}\end{equation}

$\bar{s}_i$ does not affect the normalized result, so its theoretical optimum is $t_{i,j}=\text{softmax}(s_{i,j})$.

However, while this looks elegant, its actual performance turns out to be rather poor. $t_{i,j}=\text{softmax}(s_{i,j})$ is indeed the theoretical optimum, but in practice, the closer the labels get to being hard labels, the worse the performance becomes. This is because, for the loss $\eqref{eq:loss-3}$, as long as $s_{i,j} \gg \bar{s}_i$, the loss will already be close to 0 — and to achieve $s_{i,j} \gg \bar{s}_i$, $s_{i,j}$ need not be the largest among $s_{i,1},s_{i,2},\cdots,s_{i,m}$, which fails to accomplish the classification objective.

Reflection and Analysis

We now have two results: equation $\eqref{eq:loss-1}$ is the analogy-based generalization of the original multi-label cross-entropy, and it performs reasonably well in the hard-label case, but since we can't find an analytical solution in the soft-label case, we have no theoretical way to evaluate its soft-label behavior. Equation $\eqref{eq:loss-3}$, on the other hand, was derived by working backwards from a desired result — theoretically, its analytical solution is simply softmax, but due to limitations of practical optimization algorithms, its performance on hard labels is usually poor, and it can't even guarantee that the target logit is the maximum. Notably, when $m=2$, both equation $\eqref{eq:loss-1}$ and equation $\eqref{eq:loss-3}$ reduce to the multi-label cross-entropy.

We know that multi-label cross-entropy can automatically balance the imbalance between positive and negative samples. Similarly, even though we haven't yet arrived at a perfect generalization, in principle the extension to "$n$ groups of $m$-class classification" should still be able to automatically balance the imbalance across the $m$ classes. So what is the mechanism behind this balancing? It's not hard to understand: whether it's the analogy-based equation $\eqref{eq:loss-1}$ or the general hypothesized form $\eqref{eq:loss-2}$, the summation over $i$ is placed inside $\log$. Originally, the loss contribution of each class was roughly proportional to "the number of samples in that class"; once this summation is moved inside $\log$, the loss contribution of each class becomes roughly equal to "the logarithm of the number of samples in that class," which narrows the gap between classes and automatically alleviates the imbalance problem.

Unfortunately, this post has not managed to arrive at a perfect generalization for "$n$ groups of $m$-class classification" — one that should possess two properties: (1) automatically adjusting for class imbalance via the method of $\log$; and (2) admitting an analytical solution in the soft-label case. For hard labels, directly using equation $\eqref{eq:loss-1}$ should be sufficient; but for soft labels, I'm honestly out of ideas, and I welcome interested readers to think it through together with me.

Summary

This post attempted to generalize the earlier multi-label cross-entropy to "$n$ groups of $m$-class classification." Unfortunately, this particular generalization was not entirely successful. I'm sharing the results here for now, in the hope that interested readers will join in and help improve them.