In the post “Sentence Similarity Model Based on GRU and AM-Softmax”, we introduced AM-Softmax, which is a version of Softmax with a margin, typically used in scenarios where classification is employed for retrieval. At that time, we briefly mentioned through illustrations that the introduction of a margin is due to the “inequivalence between classification and ranking,” but we did not provide a relatively quantitative explanation for the source of this inequivalence.
In this article, we revisit this topic to derive and understand the necessity of the margin from the perspective of the triangle inequality of distances.
Triangle Inequality
Usually, when we speak of distance, we generally refer to the intuitive “Euclidean distance.” However, in mathematics, distance is also called a “metric,” and it has an axiomatic definition. It is defined as a binary function d(x,y) on a certain set that satisfies:
1. Non-negativity: d(x,y) \geq 0;
2. Identity: d(x,y) = 0 \Leftrightarrow x = y;
3. Symmetry: d(x,y) = d(y,x);
4. Triangle Inequality: d(x,y) \leq d(x,z) + d(z,y).
As the name suggests, distance is used to measure the degree of difference between x and y. Theoretically, as long as the first two requirements are met, it can be used to measure differences; for example, the KL divergence commonly used in probability satisfies only the first two. The addition of the 3rd and 4th points is essentially intended to make the distance defined in this way closer to the Euclidean distance we are familiar with. For instance, symmetry reflects that “distance has no direction,” and the triangle inequality reflects that “the shortest path between two points is a straight line.” These analogies help us think about more general distances by comparing them to Euclidean distance.
From this definition, deep learning actually rarely encounters distances that satisfy all four requirements. For example, common classification directly uses the inner product plus Softmax, where the inner product only satisfies the third point. The cosine distance 1 - \cos(x,y) also only satisfies the 1st and 3rd points, failing the 2nd and 4th. If we treat all vectors in the same direction as equal, then it could be considered to satisfy the 2nd point.
However, we can slightly adjust the definition of certain functions to make them a metric. For example, we know that Euclidean distance satisfies the triangle inequality, so: \left\Vert \frac{x}{\Vert x\Vert} - \frac{y}{\Vert y\Vert}\right\Vert = \sqrt{2 - 2\cos(x,y)} must also satisfy the triangle inequality. Therefore, while the cosine distance 1 - \cos(x,y) does not satisfy the triangle inequality, changing it to \sqrt{1 - \cos(x,y)} makes it satisfy it.
Classification and Ranking
In scenarios such as face recognition or sentence similarity, we use features for ranking during the prediction phase. Naturally, we hope that given any sample, we can retrieve all samples of the same class. This requires that “intra-class discrepancy is smaller than inter-class discrepancy.” However, if we train this as a classification task, this goal may not necessarily be achieved because the objective of a classification task is to be “closest to the center of the assigned class.” A specific example is shown in the figure below:
In this figure, z_1, z_3 belong to class c_1, and z_2 belongs to class c_2. From a classification perspective, d(z_1, c_1) < d(z_1, c_2) and d(z_2, c_2) < d(z_2, c_1), so the classifications are correct. However, d(z_1, z_2) < d(z_1, z_3), so if we use z_1 for retrieval, we find z_2 from a different class instead of z_3 from the same class.
We can use the triangle inequality to describe this inequality more quantitatively. We hope to achieve d(z_1, z_3) < d(z_1, z_2). According to the triangle inequality, we have d(z_1, z_3) \leq d(z_1, c_1) + d(z_3, c_1), so a sufficient condition is: d(z_1, c_1) + d(z_3, c_1) < d(z_1, z_2) Adding d(z_2, c_2) to both sides and using the triangle inequality d(z_1, z_2) + d(z_2, c_2) \geq d(z_1, c_2), we obtain a sufficient condition for the above as: d(z_1, c_1) + d(z_3, c_1) + d(z_2, c_2) < d(z_1, c_2) It is important to note that the classification task only requires d(z_1, c_1) < d(z_1, c_2) for z_1, whereas the above formula includes the extra term d(z_3, c_1) + d(z_2, c_2). This extra term is the margin term.
Notice that d(z_3, c_1) and d(z_2, c_2) are the distances from samples z_3 and z_2 to their respective class centers. Thus, we can consider d(z_3, c_1) + d(z_2, c_2) as the “average class diameter,” which should be close to a constant m. We can treat this as a hyperparameter to be tuned. If adaptive adjustment is desired, one could consider training with m=0 for a period, then estimating the “average class diameter” to use as m for further training, and then re-estimating m, and so on.
AM-Softmax
Through the derivation above, we know that to ensure the features of a classification model can be used for ranking, each sample must not only be closest to its class center but must remain the closest even after adding m to the distance. That is, if z_1 belongs to class c_1, then we require: \begin{aligned} d(z_1, c_1) +&\, m < d(z_1, c_2) \\ d(z_1, c_1) +&\, m < d(z_1, c_3) \\ &\vdots \\ d(z_1, c_1) +&\, m < d(z_1, c_k) \end{aligned} Following the logic in “Generalizing ’Softmax + Cross Entropy’ to Multi-label Classification”: as long as we want s_i < s_j, we can construct a loss by adding e^{s_i - s_j} inside a \log. Thus, we can construct the following loss: \log\left(1+\sum_{i=2}^k e^{s\cdot[d(z_1, c_1) + m - d(z_1, c_i)]}\right) This is the cross-entropy with an additive margin, where s is a scaling factor, equivalent to the temperature parameter in Softmax.
However, do not forget that the above derivation is based on the assumption that d satisfies the triangle inequality, while the scoring functions we usually use do not. For training retrieval models, we typically use cosine distance for scoring. As mentioned earlier, cosine distance can satisfy the triangle inequality by taking the square root, so the corresponding requirement becomes (taking i=2 as an example): \begin{array}{c} \sqrt{1-\cos(z_1, c_1)} + m < \sqrt{1-\cos(z_1, c_2)}\\ \Downarrow\\ \sqrt{1-\cos(z_1, c_2)} - \sqrt{1-\cos(z_1, c_1)} > m \\ \end{array} Multiplying both sides by \sqrt{1-\cos(z_1, c_2)} + \sqrt{1-\cos(z_1, c_1)}, we get: \cos(z_1, c_1) - \cos(z_1, c_2) > m\left(\sqrt{1-\cos(z_1, c_2)} + \sqrt{1-\cos(z_1, c_1)}\right) Clearly, the right side is bounded. Therefore, by appropriately adjusting m, we can make: \cos(z_1, c_1) - \cos(z_1, c_2) > m a sufficient condition. In this case, the corresponding margin cross-entropy is: \log\left(1+\sum_{i=2}^k e^{s\cdot[\cos(z_1, c_i) + m - \cos(z_1, c_1)]}\right) This is AM-Softmax.
Review and Summary
This article derives the necessity of a margin when using classification models for ranking tasks from the perspective of the triangle inequality. Under the assumption that the scoring function used satisfies the triangle inequality, the relevant results can be derived quite naturally.