Deep neural networks (DNNs) typically have enough capacity to fit random data by brute force even when conventional data-dependent regularizations focusing on the geometry of the features are imposed. We find out that the reason for this is the inconsistency between the enforced geometry and the standard softmax cross entropy loss. To resolve this, we propose a new framework for data-dependent DNN regularization, the Geometrically-Regularized-Self-Validating neural Networks (GRSVNet). During training, the geometry enforced on one batch of features is simultaneously validated on a separate batch using a validation loss consistent with the geometry. We study  a particular case of GRSVNet, the Orthogonal-Low-rank Embedding (OLE)-GRSVNet, which is capable of producing highly discriminative features residing in orthogonal low-rank subspaces. Numerical experiments show that OLE-GRSVNet outperforms DNNs with conventional regularization when trained on real data. More importantly, unlike conventional DNNs, OLE-GRSVNet refuses to memorize random data or random labels, suggesting it only learns intrinsic patterns by reducing the memorizing capacity of the baseline DNN. It remains an open question why DNNs, typically with far more model parameters than training samples, can achieve such small generalization error. Previous work used various complexity measures from statistical learning theory, such as VC dimension (Vapnik, 1998) , Radamacher complexity BID1 , and uniform stability BID2 BID10 , to provide an upper bound for the generalization error, suggesting that the effective capacity of DNNs, possibly with some regularization techniques, is usually limited. However, the experiments by Zhang et al. (2017) showed that, even with data-independent regularization, DNNs can perfectly fit the training data when the true labels are replaced by random labels, or when the training data are replaced by Gaussian noise. This suggests that DNNs with data-independent regularization have enough capacity to "memorize" the training data. This poses an interesting question for network regularization design: is there a way for DNNs to refuse to (over)fit training samples with random labels, while exhibiting better generalization power than conventional DNNs when trained with true labels? Such networks are very important because they will extract only intrinsic patterns from the training data instead of memorizing miscellaneous details.One would expect that data-dependent regularizations should be a better choice for reducing the memorizing capacity of DNNs. Such regularizations are typically enforced by penalizing the standard softmax cross entropy loss with an extra geometric loss which regularizes the feature geometry BID8 Zhu et al., 2018; Wen et al., 2016) . However, regularizing DNNs with an extra geometric loss has two disadvantages: First, the output of the softmax layer, usually viewed as a probability distribution, is typically inconsistent with the feature geometry enforced by the geometric loss. Therefore, the geometric loss typically has a small weight to avoid jeopardizing the minimization of the softmax loss. Second, we find that DNNs with such regularization can still perfectly (over)fit random training samples or random labels. The reason is that the geometric loss (because of its small weight) is ignored and only the softmax loss is minimized.This suggests that simply penalizing the softmax loss with a geometric loss is not sufficient to regularize DNNs. Instead, the softmax loss should be replaced by a validation loss that is consistent with the enforced geometry. More specifically, every training batch B is split into two sub-batches, the geometry batch B g and the validation batch B v . The geometric loss l g is imposed on the features of B g for them to exhibit a desired geometric structure. A semi-supervised learning algorithm based on the proposed feature geometry is then used to generate a predicted label distribution for the validation batch, which combined with the true labels defines a validation loss on B v . The total loss on the training batch B is then defined as the weighted sum l = l g + λl v . Because the predicted label distribution on B v is based on the enforced geometry, the geometric loss l g can no longer be neglected. Therefore, l g and l v will be minimized simultaneously, i.e., the geometry is correctly enforced (small l g ) and it can be used to predict validation samples (small l v ). We call such DNNs Geometrically-Regularized-Self-Validating neural Networks (GRSVNets). See FIG0 for a visual illustration of the network architecture.GRSVNet is a general architecture because every consistent geometry/validation pair can fit into this framework as long as the loss functions are differentiable. In this paper, we focus on a particular type of GRSVNet, the Orthogonal-Low-rank-Embedding-GRSVNet (OLE-GRSVNet). More specifically, we impose the OLE loss (Qiu & Sapiro, 2015) on the geometry batch to produce features residing in orthogonal subspaces, and we use the principal angles between the validation features and those subspaces to define a predicted label distribution on the validation batch. We prove that the loss function obtains its minimum if and only if the subspaces of different classes spanned by the features in the geometry batch are orthogonal, and the features in the validation batch reside perfectly in the subspaces corresponding to their labels (see FIG0 ). We show in our experiments that OLE-GRSVNet has better generalization performance when trained on real data, but it refuses to memorize the training samples when given random training data or random labels, which suggests that OLE-GRSVNet effectively learns intrinsic patterns.Our contributions can be summarized as follows:• We proposed a general framework, GRSVNet, to effectively impose data-dependent DNN regularization. The core idea is the self-validation of the enforced geometry with a consistent validation loss on a separate batch of features.• We study a particular case of GRSVNet, OLE-GRSVNet, that can produce highly discriminative features: samples from the same class belong to a low-rank subspace, and the subspaces for different classes are orthogonal.• OLE-GRSVNet achieves better generalization performance when compared to DNNs with conventional regularizers. And more importantly, unlike conventional DNNs, OLEGRSVNet refuses to fit the training data (i.e., with a training error close to random guess) when the training data or the training labels are randomly generated. This implies that OLE-GRSVNet never memorizes the training samples, only learns intrinsic patterns. We proposed a general framework, GRSVNet, for data-dependent DNN regularization. The core idea is the self-validation of the enforced geometry on a separate batch using a validation loss consistent with the geometric loss, so that the predicted label distribution has a meaningful geometric interpretation. In particular, we study a special case of GRSVNet, OLE-GRSVNet, which is capable of producing highly discriminative features: samples from the same class belong to a low-rank subspace, and the subspaces for different classes are orthogonal. When trained on benchmark datasets with real labels, OLE-GRSVNet achieves better test accuracy when compared to DNNs with different regularizations sharing the same baseline architecture. More importantly, unlike conventional DNNs, OLE-GRSVNet refuses to memorize and overfit the training data when trained on random labels or random data. This suggests that OLE-GRSVNet effectively reduces the memorizing capacity of DNNs, and it only extracts intrinsically learnable patterns from the data.Although we provided some intuitive explanation as to why GRSVNet generalizes well on real data and refuses overfitting random data, there are still open questions to be answered. For example, what is the minimum representational capacity of the baseline DNN (i.e., number of layers and number of units) to make even GRSVNet trainable on random data? Or is it because of the learning algorithm (SGD) that prevents GRSVNet from learning a decision boundary that is too complicated for random samples? Moreover, we still have not answered why conventional DNNs, while fully capable of memorizing random data by brute force, typically find generalizable solutions on real data. These questions will be the focus of our future work. It suffices to prove the case when K = 2, as the case for larger K can be proved by induction. In order to simplify the notation, we restate the original theorem for K = 2:Theorem. Let A ∈ R N ×m and B ∈ R N ×n be matrices of the same row dimensions, and [A, B] ∈ R N ×(m+n) be the concatenation of A and B. We have DISPLAYFORM0 Moreover, the equality holds if and only if A * B = 0, i.e., the column spaces of A and B are orthogonal.Proof. The inequality (8) and the sufficient condition for the equality to hold is easy to prove. More specifically, DISPLAYFORM1 Moreover, if A * B = 0, then DISPLAYFORM2 where |A| = (A * A) 1 2 . Therefore, DISPLAYFORM3 Next, we show the necessary condition for the equality to hold, i.e., DISPLAYFORM4 DISPLAYFORM5 | be a symmetric positive semidefinite matrix. We DISPLAYFORM6 Let DISPLAYFORM7 be the orthonormal eigenvectors of |A|, |B|, respectively. Then DISPLAYFORM8 Similarly, DISPLAYFORM9 Suppose that [A, B] * = A * + B * , then DISPLAYFORM10 Therefore, both of the inequalities in this chain must be equalities, and the first one being equality only if G = 0. This combined with the last equation in FORMULA2 implies DISPLAYFORM11 APPENDIX B PROOF OF THEOREM 2Proof. First, l is defined in equation FORMULA8 as DISPLAYFORM12 The nonnegativity of l g (Z g ) is guaranteed by Theorem 1. The validation loss l v (Y v ,Ŷ v ) is also nonnegative since it is the average (over the validation batch) of the cross entropy losses: DISPLAYFORM13 Therefore l = l g + λl v is also nonnegative.Next, for a given λ > 0, l(X, Y) obtains its minimum value zero if and only if both l g (Z g ) and l v (Y v ,Ŷ v ) are zeros.• By Theorem 1, l g (Z g ) = 0 if and only if span(Z g c )⊥ span(Z g c ), ∀c = c .• According to (19), l v (Y v ,Ŷ v ) = 0 if and only ifŷ(x) = δ y , ∀x ∈ X v , i.e., for every x ∈ X v c , its feature z = Φ(x; θ) belongs to span(Z g c ).At last, we want to prove that if λ > 0, and X v contains at least one sample for each class, then rank(span(Z g c )) ≥ 1 for any c ∈ {1, . . . , K}. If not, then there exists c ∈ {1, . . . , K} such that rank(span(Z g c )) = 0. Let x ∈ X v be a validation datum belonging to class y = c. The predicted probability of x belonging to class c is defined in (3): DISPLAYFORM14 Thus we have DISPLAYFORM15
we propose a new framework for data-dependent DNN regularization that can prevent DNNs from overfitting random data or random labels.
{"src": "scitldr-AIC_train", "paper_id": "B1GSBsRcFX"}