Cross-Entropy Loss Leads To Poor Margins

Intro

目前很多讨论DNN结构的实验都使用了默认的loss function。

cross entropy几乎是分类问题的唯一loss function。它的广泛应用被与KL divergence的联系很好的支持：empirical distribution和classifier的confidence（actual distribution？）之间的KL divergence最小。

最近有一系列的paper研究linear classifier with cross-entropy。他们都确定一个linearly separable dataset上由cross-entropy minimization带来的decision boundary，并且这个解会带来maximum margin。但是在很简单的实验上，这个假设并不成立。Figure 1表明了一个非常简单的例子上，cross entropy minimization会带来的decision boundary会带来非常差的decision boundary，并且几乎是与SVM给的decision boundary orthogonal。

我们开始理解在简单实验上的这种不一致性。我们的贡献归纳如下：

我们研究了在仅有两个点的情况下的cross-entropy minimization，并且展示了dynamics of the gradient descent会带来很差的decision boundary，几乎与maximum margin垂直。（忽略了initialization，图1有点问题，不过可以先看一下怎么证明的）
我们找到最近几篇工作和我们的发现之间不同的原因。阐明了为什么cross entropy minimization与SVM结果不一样。
对于线性可分数据，如果训练数据集在affine subspace上，并且如果使用gradient method（no regularization）来最小化cross-entropy，那么decision boundary的margin会比最优解小。我们确认了如果分类CIFAR-10中的两个类别，那么网络的倒数第二层会产生在affine subspace上的点。
我们表明了如果没有regularization，最后一层的layer会变到无限大。尽管已经有paper提出过这个，我们是第一个指出，这个分歧会使得每一个data point在NN confidence达到100%（经历长时间训练之后）。换句话说，confidence强烈依赖于训练过程，而它的确切数字只要达到50%，重要性就不大。
我们介绍了differential training，一个新的训练方法使用pairwise point loss，其中任意两个point是来自于一个类，而不仅仅是每一个class的一个point。我们展示使用了differential training的decision boundary会产生与SVM类似的结果：margin最大。

Classification of Two Points

从两个点开始研究。$$x \in \mathbb{R}^d$$,$$-y \in \mathbb{R}^d$$来自于两个类(($$x,1)$$, $$(-y,0$$)。那么cross-entropy minimization就是

$$ \min \bigg{ -\log \frac{1}{e^{-w^Tx-b} + 1} - \log \frac{e^{w^Ty-b}}{e^{w^Ty-b}+1} \bigg}

等价于

$$ \min \bigg{ \log ({e^{-\hat w ^T \hat x} + 1}) + \log ({e^{\hat w^T \hat y}+1}) \bigg}

其中$$\hat w = [w^T \, b]^T$$, $$\hat x = [x^T \, 1]^T$$, $$-\hat y = [-y^T \, 1]$$。除非这两个点相等，否则上述式子的optimal solution并不会到达其minimum。而如果使用gradient descent来进行求解上述式子，那么在第k个iteration，$$\hat w_k$$会随着k增加而产生分歧。下面的theorem使用continuous-time approximation的方法来阐述$$\hat w_k$$的growth rate以及在极限上的方向。

Theorem 1. 对于cross entropy minimization

$$ \min \bigg{ \log ({e^{-\hat w ^T \hat x} + 1}) + \log ({e^{\hat w^T \hat y}+1}) \bigg}

$$

在gradient descent上使用continuous-time approximation

$$ \frac{d \hat w}{d t} = \hat x \frac{\delta e^{-\hat w^T \hat x}}{1+ e^{-\hat w^T \hat x}} + \hat y \frac{\delta e^{-\hat w^T \hat y}}{1 + e^{-\hat w^T \hat y}}

$$

with $$\hat w = [0]$$ and $$\delta$$ as learning rate。那么有

$$ \lim{t \to \infty} \, \frac{\hat w(t)}{\log(t)} \begin{cases} \frac{\sigma_y - \sigma{xy}}{\sigmax \sigma_y - \sigma^2{xy}} \hat x + \frac{\sigmax - \sigma{xy}}{\sigmax \sigma_y - \sigma^2{xy}} \hat y ,& \text{if }\sigma{xy} < \sigma_x\ \frac{1}{\sigma_x} \hat x, & \text{if } \sigma{xy} \ge \sigma_x \end{cases}

$$

其中$$\sigmax = |\hat x|^2, \sigma{y} = |\hat y|^2, \sigma_{xy} = |\hat x ^T \hat y|^2$$。

Remark 2 Theorem 1展示了$$w$$的norm会随着训练时间的增加而变得无限大。一个分类器在数据点$$x$$上的confidence是

$$ \max(\frac{1}{e^{-w^T x - b}+1}, \frac{e^{-w^Tx-b}}{e^{-w^T x - b}+ 1})

而$$|w|$$的无限制增长就会使得这个confidence趋向于100%。（这个非常make sense，cross entropy loss其实就默认了所有的数据就服从于一个0／1分布）因此模型的confidence会高度依赖于训练的时间。而一个模型不论是给51%还是99%的confidence都不重要，只要大于50%就一样。这种将confidence作为measure的方式需要重新考虑一下。

Classification of Linearly Separable Sets

考虑在linearly separable set上的情况。

Theorem 2: 给定两个点集，$${xi}{i\in I}, {-yj}{j \in J}$$，那么在cross-entropy minimization上的gradient descent

$$ \sum{i \in I} \log(1 + e^{-\hat w^T \hat x_i}) + \sum{j\in J} \log (1 + e^{-\hat w^T y_j})

$$

当step size足够小的时候

$$ \hat w(t) = \bar w \log(t) + \rho(t)

$$

其中$$\bar w = \arg \min_{u \in \mathbb{R}^{d=1}} | u |^2$$ s.t. $$\langle u, \hat x_i \rangle \ge 1, \langle u, \hat y_j \rangle \ge 1$$, and the residual grows at most as | \rho(t) | = O(\log \log (t)). 作为结果，$$\hat w$$ 会朝着 $$\bar w$$的方向增长。

$$ \lim_{t \to \infty} \frac{\hat w(t)}{| \hat w(t) |} = \frac{\bar w}{| \bar w|}

$$

但是这里想说明的是$$\bar w$$的目标函数忽略了bias，因此不准确。应该是$$\bar w = \arg \min_{w,b} | w |^2 + b^2$$.

Theorem 3:

当所有点都在一个affine subspace上时，给有cross-entropy得到的optimal solution给一个bound，会小于等于optimal margin value。

Theorem 4

不要求都在affine subspace，只要linearly separable即可。

Numerical Experiments

图2中的点并不是完全在一个affine subspace上，而differential training的margin会小一点。与Theorem 4对应。

然后测试了neural network。在CIFAR-10上。Figure 3展示了倒数第二层输出的output，是在一个low-dimensional affine subspace上，并且对于很多模型都成立。因此，cross-entropy minimization + gradient descent带来的margin比较差。

Discussion

SVM (Gaussian Kernel)在adversarial training上显示了很高的鲁棒性。

Appendix

under-review

但如果在loss space，cross-entropy minimization实际上在做的就是maximum margin。只是投影到原来的数据空间，不满足maximum margin。

分析中有一点忽略的是initialization的影响。除了Theorem 1中简单的提到了一些，但实际上如果初始状态就是large margin，结果也不会在class-balanced情况下，结果还是能够维持。

Proof of Theorem 1

下面用$$x$$表示$$\hat x$$,$$y$$表示$$\hat y$$, $$w$$表示$$\hat w$$.

因此，我们有$$\frac{d w}{d t} = \delta x \frac{e^{-w^T x}}{1 + e^{-w^T x}} + \delta y \frac{e^{-w^T y}}{1 + e^{-w^T y}}$$

If $$w(0) = 0$$, then $$w(t) = p(t) x + q(t) y$$.

$$w(t)^T x = p | x |^2 + q \langle x, y\rangle$$, and $$w(t)^T y = p \langle x, y\rangle + q | y |^2$$.

另$$z = e^{\alpha}, v=e^{\beta}$$

因为$$\alpha = \log(z) \Longrightarrow \dot \alpha = \frac{1}{z} \dot z \Longrightarrow \dot z = z \dot \alpha$$，所以有

$$ \dot z = \frac{z}{z+1} (a + b\frac{z+1}{v+1})\ \dot v = \frac{v}{v+1} (c + b\frac{v+1}{z+1})

另外，有

$$ \begin{align} \frac{d}{dt}(\frac{z}{v}) & =\dot z v^{-1} - z v^{-2} \dot v\ & = \frac{z}{(z+1)v} (a+b\frac{z+1}{v+z}) - \frac{z}{(v+1)v} (c + b\frac{v+1}{z+1})\ & = \frac{z}{v}[\frac{a}{z+1} + \frac{b}{v+1} - \frac{c}{v+1} - \frac{b}{z+1}]\ & = \frac{z}{v}[\frac{a-b}{z+1} - \frac{c-b}{v+1}]\ & = \frac{z}{v} \frac{c-b}{z+1} (\frac{a-b}{c-b} - \frac{z+1}{v+1}) \end{align}

而$$\frac{d}{dt}(\frac{z+1}{v+1})$$的计算类似。

Lemma 1

If $$b=0$$,

$$ \frac{d(z + \log(z))}{dt} = \dot z + \dot a = a \Longrightarrow z(t) - z_0 + \log(z(t)/z_0) = at

类似的，有 $$\frac{d(v + \log(v))}{dt} = c \Longrightarrow v(t) - v_0 + \log(v(t)/v_0) = ct$$

Lemma 2

如果 $$b<0$$，那么存在

Cross-Entropy Loss Leads To Poor Margins

Cross-Entropy Loss Leads To Poor Margins