Neural networks could misclassify inputs that are slightly different from their training data, which indicates a small margin between their decision boundaries and the training dataset. In this work, we study the binary classification of linearly separable datasets and show that linear classifiers could also have decision boundaries that lie close to their training dataset if cross-entropy loss is used for training. In particular, we show that if the features of the training dataset lie in a low-dimensional affine subspace and the cross-entropy loss is minimized by using a gradient method, the margin between the training points and the decision boundary could be much smaller than the optimal value. This result is contrary to the conclusions of recent related works such as (Soudry et al., 2018), and we identify the reason for this contradiction. In order to improve the margin, we introduce differential training, which is a training paradigm that uses a loss function defined on pairs of points from each class. We show that the decision boundary of a linear classifier trained with differential training indeed achieves the maximum margin. The results reveal the use of cross-entropy loss as one of the hidden culprits of adversarial examples and introduces a new direction to make neural networks robust against them. Training neural networks is challenging and involves making several design choices. Among these are the architecture of the network, the training loss function, the optimization algorithm used for training, and their hyperparameters, such as the learning rate and the batch size. Most of these design choices influence the solution obtained by the training procedure and have been studied in detail BID9 BID4 BID5 Wilson et al., 2017; BID17 BID19 . Nevertheless, one choice has been mostly taken for granted when the network is trained for a classification task: the training loss function.Cross-entropy loss function is almost the sole choice for classification tasks in practice. Its prevalent use is backed theoretically by its association with the minimization of the Kullback-Leibler divergence between the empirical distribution of a dataset and the confidence of the classifier for that dataset. Given the particular success of neural networks for classification tasks BID11 BID18 BID5 , there seems to be little motivation to search for alternatives for this loss function, and most of the software developed for neural networks incorporates an efficient implementation for it, thereby facilitating its use.Recently there has been a line of work analyzing the dynamics of training a linear classifier with the cross-entropy loss function BID15 b; BID7 . They specified the decision boundary that the gradient descent algorithm yields on linearly separable datasets and claimed that this solution achieves the maximum margin.1 However, these claims were observed not to hold in the simple experiments we ran. For example, FIG6 displays a case where the cross-entropy minimization for a linear classifier leads to a decision boundary which attains an extremely poor margin and is nearly orthogonal to the solution given by the hard-margin support vector machine (SVM).We set out to understand this discrepancy between the claims of the previous works and our observations on the simple experiments. We can summarize our contributions as follows. We compare our results with related works and discuss their implications for the following subjects.Adversarial examples. State-of-the-art neural networks have been observed to misclassify inputs that are slightly different from their training data, which indicates a small margin between their decision boundaries and the training dataset (Szegedy et al., 2013; BID3 MoosaviDezfooli et al., 2017; . Our results reveal that the combination of gradient methods, cross-entropy loss function and the low-dimensionality of the training dataset (at least in some domain) has a responsibility for this problem. Note that SVM with the radial basis function was shown to be robust against adversarial examples, and this was attributed to the high nonlinearity of the radial basis function in BID3 . Given that the SVM uses neither the cross entropy loss function nor the gradient descent algorithm for training, we argue that the robustness of SVM is no surprise -independent of its nonlinearity. Lastly, effectiveness of differential training for neural networks against adversarial examples is our ongoing work. The activations feeding into the soft-max layer could be considered as the features for a linear classifier. Plot shows the cumulative variance explained for these features as a function of the number of principle components used. Almost all the variance in the features is captured by the first 20 principle components out of 84, which shows that the input to the soft-max layer resides predominantly in a low-dimensional subspace.Low-dimensionality of the training dataset. As stated in Remark 3, as the dimension of the affine subspace containing the training dataset gets very small compared to the dimension of the input space, the training algorithm will become more likely to yield a small margin for the classifier. This observation confirms the results of BID13 , which showed that if the set of training data is projected onto a low-dimensional subspace before feeding into a neural network, the performance of the network against adversarial examples is improved -since projecting the inputs onto a low-dimensional domain corresponds to decreasing the dimension of the input space. Even though this method is effective, it requires the knowledge of the domain in which the training points are low-dimensional. Because this knowledge will not always be available, finding alternative training algorithms and loss functions that are suited for low-dimensional data is still an important direction for future research.Robust optimization. Using robust optimization techniques to train neural networks has been shown to be effective against adversarial examples BID12 BID0 . Note that these techniques could be considered as inflating the training points by a presumed amount and training the classifier with these inflated points. Consequently, as long as the cross-entropy loss is involved, the decision boundaries of the neural network will still be in the vicinity of the inflated points. Therefore, even though the classifier is robust against the disturbances of the presumed magnitude, the margin of the classifier could still be much smaller than what it could potentially be.Differential training. We introduced differential training, which allows the feature mapping to remain trainable while ensuring a large margin between different classes of points. Therefore, this method combines the benefits of neural networks with those of support vector machines. Even though moving from 2N training points to N 2 seems prohibitive, it points out that a true classification should in fact be able to differentiate between the pairs that are hardest to differentiate, and this search will necessarily require an N 2 term. Some heuristic methods are likely to be effective, such as considering only a smaller subset of points closer to the boundary and updating this set of points as needed during training. If a neural network is trained with this procedure, the network will be forced to find features that are able to tell apart between the hardest pairs.Nonseparable data. What happens when the training data is not linearly separable is an open direction for future work. However, as stated in Remark 4, this case is not expected to arise for the state-of-the-art networks, since they have been shown to achieve zero training error even on randomly generated datasets (Zhang et al., 2017) , which implies that the features represented by the output of their penultimate layer eventually become linearly separable. A PROOF OF THEOREM 1Theorem 1 could be proved by using Theorem 2, but we provide an independent proof here. Gradient descent algorithm with learning rate δ on the cross-entropy loss (1) yields DISPLAYFORM0 1 + e −w x + δỹ e −w ỹ 1 + e −w ỹ .Ifw(0 ) = 0, thenw(t) = p(t)x + q(t)ỹ for all t ≥ 0, wherė DISPLAYFORM1 Then we can writeα Lemma 2. If b < 0, then there exists t 0 ∈ (0, ∞) such that DISPLAYFORM2 Proof. Note that DISPLAYFORM3 which implies that DISPLAYFORM4 as long as DISPLAYFORM5 By using Lemma 2, DISPLAYFORM6 Proof. Solving the set of equations DISPLAYFORM7 , DISPLAYFORM8 Proof. Note thatż ≥ a/2 andv ≥ c/2; therefore, DISPLAYFORM9 if either side exists. Remember thaṫ DISPLAYFORM10 We can compute f (w) = 2acw + bcw 2 + ab b 2 w 2 + 2abw + a 2 . The function f is strictly increasing and convex for w > 0. We have DISPLAYFORM11 Therefore, when b ≥ a, the only fixed point of f over [0, ∞) is the origin, and when a > b, 0 and (a − b)/(c − b) are the only fixed points of f over [0, ∞). Figure 4 shows the curves over whichu = 0 andẇ = 0. Since lim t→∞ u = lim t→∞ w, the only points (u, w) can converge to are the fixed points of f . Remember thaṫ DISPLAYFORM12 so when a > b, the origin (0, 0) is unstable in the sense of Lyapunov, and (u, w) cannot converge to it. Otherwise, (0, 0) is the only fixed point, and it is stable. As a result, DISPLAYFORM13 Figure 4: Stationary points of function f . DISPLAYFORM14 Proof. From Lemma 6 , DISPLAYFORM15 Consequently , DISPLAYFORM16 which gives the same solution as Lemma 5: DISPLAYFORM17 Proof. We can obtain a lower bound for square of the denominator as DISPLAYFORM18 DISPLAYFORM19 As a result, Then, we can write w as DISPLAYFORM20 Remember, by definition, w SVM = arg min w 2 s.t. w, x i + y j ≥ 2 ∀i ∈ I, ∀j ∈ J.Since the vector u also satisfies u, x i + y j = w, x i + y j ≥ 2 for all i ∈ I, j ∈ J, we have u ≥ w SVM = 1 γ . As a result, the margin obtained by minimizing the cross-entropy loss is DISPLAYFORM21
We show that minimizing the cross-entropy loss by using a gradient method could lead to a very poor margin if the features of the dataset lie on a low-dimensional subspace.
{"src": "scitldr-AIC_train", "paper_id": "ByfbnsA9Km"}