A Kolmogorov Complexity Approach to Generalization in Deep Learning
Authors: Hazar Yueksel
Kush R. Varshney
Brian Kingsbury
Venue:  (2020)
Keywords: Kolmogorov complexity
information distance
generalization

Abstract: Deep artificial neural networks can achieve an extremely small difference between training and test accuracies on identically distributed training and test sets, which is a standard measure of generalization. However, the training and test sets may not be sufficiently representative of the empirical sample set, which consists of real-world input samples. When samples are drawn from an underrepresented or unrepresented subset during inference, the gap between the training and inference accuracies can be significant. To address this problem, we first reformulate a classification algorithm as a procedure for searching for a source code that maps input features to classes. We then derive a necessary and sufficient condition for generalization using a universal cognitive similarity metric, namely information distance, based on Kolmogorov complexity. Using this condition, we formulate an optimization problem to learn a more general classification function. To achieve this end, we extend the input features by concatenating encodings of them, and then train the classifier on the extended features. As an illustration of this idea, we focus on image classification, where we use channel codes on the input features as a systematic way to improve the degree to which the training and test sets are representative of the empirical sample set. To showcase our theoretical findings, considering that corrupted or perturbed input features belong to the empirical sample set, but typically not to the training and test sets, we demonstrate through extensive systematic experiments that, as a result of learning a more general classification function, a model trained on encoded input features is significantly more robust to common corruptions, e.g., Gaussian and shot noise, as well as adversarial perturbations, e.g., those found via projected gradient descent, than the model trained on uncoded input features.

Under review as a conference paper at ICLR 2020
A KOLMOGOROV COMPLEXITY APPROACH TO GENERALIZATION IN DEEP LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Deep artificial neural networks achieve extremely small difference between training and test accuracies on identically distributed training and test sets, which is standard measure of generalization. However, the training and test sets may not be sufficiently representative of the empirical sample set, which consists of real-world input samples. When samples are drawn from an underrepresented unrepresented subset during inference, the gap between the training and inference accuracies can be significant. To address this problem, we first reformulate learning algorithm as a procedure for searching for source code that maps input features to classes. We then derive necessary and sufficient condition for generalization using a universal cognitive similarity metric, namely information distance, based on Kolmogorov complexity. Using this condition, we formulate an optimization problem to learn more general classification function. To achieve this end, we extend the input features by concatenating encodings of them, and then train the classifier on the extended features. As illustration of this idea, focus image classification, where we use channel codes on the input features as a systematic way to improve the degree to which the training and test sets are representative of the empirical sample set. To showcase our theoretical findings, considering that corrupted or perturbed input features belong to the empirical sample set, but typically not to the training and test sets, we demonstrate through extensive systematic experiments that, as a result of learning a more general classification function, model trained on encoded input features is significantly more robust to common corruptions, e.g., Gaussian and shot noise, as well as adversarial perturbations, e.g., those found via projected gradient descent, than the model trained on uncoded input features.
INTRODUCTION
Generalization error in deep learning is typically defined as the difference between training and test eтrоrs measured on identically distributed training and test sets. This traditional approach fails to take into account how representative these sets of the empirical sample set from which input samples are drawn at inference time. When the training and test sets are not sufficiently representative of the empirical sample set, the difference between training and inference errors can be significant, thus rendering the learned classification function ineffective. The lack of the latter kind of generalization results unreliable decisions, raising questions about how robust, fair, and safe leamed classification function is /Varshney & Alemzadeh 2017).
natural question then arises: is there a necessary and sufficient condition ensuring that deep learning classifiers generalize in this broader sense? If so, how can this condition be satisfied in real-world setting? To answer these questions, we draw on algorithmic information theory, which proposes a complexity measure, Kolmogorov complexity, e.g., a computer program, function, or set. After deriving a necessary and sufficient condition for generalization using the information distance (Bennett et al. 1998), which is universal cognitive similarity metric based on Kolmogorov complexity, and formulating an optimization problem for generalization. turn our attention to coding theory in order to learn more general classification function by extending the input features to a classifier with systematically generated encodings of the original features.
the absolute information content of any object,

---

Under review as a conference paper at ICLR 2020
1.1 OUR CONTRIBUTIONS
For a classification task, we assume that there exists a true classification function. Given training and test sets, neither of which are sufficiently representative of the the empirical sample set from which input samples are drawn during inference, learning algorithm is asked to find the true classification function. In this work, we study how well the learned classification function generalizes with respect to the true classification function. In other words, we study the problem of how to minimize the generalization error, which we define as the difference between the training error and inference error measured on the empirical sample set, as opposed to the difference between the training error and test error. We use robustness to both common corruptions and adversarial robustness to measure how well a learned classification function generalizes on the empirical sample set, which contains corrupted or perturbed samples.
Universal cognitive similarity metric. In order to find a necessary and sufficient condition for generalization in deep learning, we use the normalized information distance. A key finding in algorithmic information theory is that the normalized information distance a universal cognitive similarity metric: the normalized information distance between two objects minorizes any other admissible distance up to an additive logarithmic term (Bennett et al. 1998). In other words, although different learning algorithms will pick up different dominating input features, depending on the classification task that they perform, every such dominating feature will be detected by the normalized information distance.
Classification function source code. We formulate learning algorithm as a procedure for searching for a source code based on training examples. We show that the learned classification function lossy compressor: the classifier discards some information. The input features thus cannot be recovered from the class label. We use the normalized information distance between the true source code (true classification function) and the learned source code (learned classification function) to find necessary and sufficient condition ensuring generalization, and then formulate the problem of learning more general classification function as an optimization problem.
Compression-basee similarity metric. The normalized information distance provides the theo- retical tools needed to learn more general source codes, but in practice the normalized information distance is not effectively computable. We therefore use compression- based similarity metric (Cili brasi & Vitányi 2005) based on real-world compressor to approximate this theoretical construct. Specifically, we use the normalized compression distance between the true source code and learned source code to derive an effectively computable condition on the compressed size of the learned source code identify encodings of the input features that help to learn a more general source code.
Encoding input features. In a typical communication system, a source code is followed by channel code which is then followed by physical channel. In this paper, the learned source code (learned classification function) is preceded by one or more input codes that help ensure the learned classifier is more general by generating relations between input features that are not captured by the set of available input features. In order to showcase our findings for a specific classification task, we use channel codes the input features for CIFAR-10 10 image classification. Precisely, we use a four-dimensional (4-D) five-level pulse-amplitude modulation (5-PAM) trellis-coded modulation (TCM) scheme (Ungerboeck) [982] Hatamian al. 1998 IEEE 2015) to systematically generate multiple encodings of the set of available input features. In doing so, we enable the deep neural network (DNN) to learn information from the empirical sample set which it could not learn from the uncoded input features alone. The generalization error is thereby reduced.
The impact of generalization. Through image classification experiments, we show that a model trained arbitrarily encoded input features is significantly more robust to common corruptions, such as Gaussian noise and shot noise, and to adversarial perturbations, like those generated via projected gradient descent (PGD) (Madry al. 2018), than model trained on uncoded input features.
The role of code design. The code used the input features be designed in various ways for a classification task, and designing input codes is an important step to learning a more general classification function from the set of available input features. We show that merely increasing the
2

---

Under review as a conference paper at ICLR 2020
number of input channels of DNN does not confer any robustness to Gaussian noise or to PGD. How to design efficient input codes to build encoded DNNs is an intriguing research direction for achieving generalization in deep learning.
1.2 RELATED WORK
The literature on generalization, e.g. (Zhang et al. 2017 Neyshabu et al. (017). is largely concerned with minimizing the generalization error, defined as the difference between training and test errors measured identically distributed training and test sets. Minimizing this form of generalization error does not address the problem of generalizing to input samples drawn from an empirical sample set of which the training and test sets are not sufficiently representative,
do herein.
In this subsection, we compare our work with domain genaainnngnnaaazattionnn Nomain-adaptaaie augmentation techniques to highlight their differences. There is substantial body of literature domain generalization (Muandet et al. 2013 Li et al.) 2017] Motiian et al.) 2017] Shankar et al. 2018), which aims to better generalize to unknown domains by training
and data-
samples drawn from different domains, not a single source, which is limitation that our work does not have. In this work, there is no need draw training samples from different domain. We show that encoding the given training set enables a DNN to learn different relations between features that it could not learn from the uncoded training set alone.
There has also been much work on domain adaptation (Daumé III & Marcu 2006; Saenko et al. 2010 Ganin& & Lempitsky 2015 Tzeng et al. 2017 Sun & Saenko 2016 Morerio et 2018
Volpi et al. (0188) that addresses the problem of generalization to priori fixed target domains, which different approach from ours because these algorithms need to access samples from the target distributions during an adaptation phase. Importantly, our approach does not require accessing new samples during an adaptation phase order to achieve generalization to the empirical sample set. Similar to the domain adaptation work, there has been some work adversarial training (Goodfellow et al. 2015 Lee & Raginsky| (2018) Sinha et 2018). which aims to achieve robustness (Zhang et al., 2019) to adversarial perturbations by using training samples perturbed by specific adversarial uddersarrill-peruuraatioo perturbatiio method. Adversarial training can be computationally costly because requires generating adversarially perturbed training samples in each epoch of training, unlike in work where input encodings need to be generated only once before training. Furthermore, as there are numerous wwweerrrrrlllprrurrbrree
methods (Goodfellow et al.) 2015 Kurakin al. 20176 Madry it al., 2018), an adversarially trained DNN does not necessarily generalize well to samples subjected to an adversarial perturbation method that was not used for training (Madry al. 2018).
There is also a substantial body of work on data-augmentattin techniques (LeCun et al. 1995 Volpi et al. 201 8b), which perform simple label-pres transformations of the training samples to provide a DNN with additional data points to learn from. In this work, we do not generate new samples to increase the diversity of the training set; instead, we take a theoreicalll-ggoonnded approach to extend the input features with their encodings in order to enable DNN to learn a sufficiently complex classification function from the set of available input samples.
ALGORITHMIC INFORMATION THEORETIT APPROACH TO DEEP LEARNING
Our goal is to minimize the generalization error (defined in Appendix B B for a classification task, defined as the difference between training error and inference error, given a training set and test set, both of which are not sufficiently representative of the empirical sample set from which input samples are drawn inference time. To accomplish this goal, we derive a necessary and sufficient condition under which a classifier will generalize well, and, based on that condition, cast the search for a classifier with good generalization (defined in Appendix B as an optimization problem. Our approach requires that we describe and compute the absolute information content of any object, e.g.. a computer program, function, or set, in order to determine which a pair of learned classification functions contains more information of the true classification function. The appropriate tool here is a concept in algorithmic information theory: Kolmogorov complexity (defined in Appendix B). Defining the amount of information in individual objects in terms of their Kolmogorov complexity has the advantage that it refers to these objects isolation, not as outcomes of a known random source. In contrast, quantifying the amount of information in individual objects based on their Shannon entropy
3

---

Under review as a conference paper at ICLR 2020
requires that these objects be treated members of set of objects with associated probability distribution. This understanding is fundamental to our study because applying Shannon entropy to "an estimate of the quantity of information contained in a novel or in the translation of novel into another language relative to the original" would not be clear (Kolmogorov 1983). As a DNN may he employed to learn classification function from set of features contained in such object as, for example, a document, image, video, or sound, we study the Kolmogorov complexity of the set of input features, model, and outputs of the DNN.
2.1 NORMALIZED INFORMATION DISTANCE AS UNIVERSAL COGNITIVE SIMILARITY
In our quest to find condition ensuring our running definition of generalization, require distance function that measures how similar two objects are in any aspect so we can decide which of two learned classification functions is closer to the true classification function. The closer a learned classification function is to the true classification function, the better its generalization error. This distance function should satisfy the metric (in)equalities in order for have a meaning in the context of generalization. For example, this distance function would have to be symmetric; i.c., the distance from object to object b must be equal to that from object to object a.
The normalized information distance (Bennett et al. 1998) between objects a and b, defined as
Di b) = max (all), (bla))
max(K(a), (()))
where (aa denotes the Kolmogorov complexity of object a and K(alb) denotes the Kolmogorov complexity of object given satisfies the metric (in)equalities and is also a universal cognitive similarity metric because Di(a, b) minorizes all other normalized admissible distances up to negligible additive error term. This means that all effective similarities between a pair of objects are discovered by the normalized information distance; i.e., two objects that are close according to some effective similarity are also close according to the normalized information distance. The main intuition behind normalizing the information distance max(K K (alb). K (bla)) is that two larger objects that differ by a small amount are closer than two smaller objects that are different by the same amount: the absolute difference between two objects does not measure similarity such, but the relative difference does (Cilibrasi Vitányi 2005).
2.2 DEEP-LEARNING CLASSIFIER AS A SOURCE CODE
successful DNN distills information useful for classification task T from its input features E. In doing so, the DNN has to learn a classification function f(.) from the set X of its input features to an m--ry alphabet of classes
such a way that some information in its input features given less weight in determining its relevance to the class decision û, and then entirely discarded by the arg max operation (Goldfeld et al.) 2019). A deep learning classifier thus acting as a source code C (defined in Appendix
B) Proofs of the following mathematical statements given in Appendix A
For classification task T wherein each n--imenssinal input sample F is mapped to a class drawn from an m-ary signal alphabet A, the true output function f(-) of learning algorithm a source code C' for a multivariate random variable X²
Lemma 1.
Lemma 1 reformulates learning algorithm procedure for searching for source code C' for multivariate random variable X, which compresses the values that this random variable takes, namely the input samples ह. When a DNN generalizes well with respect to the true classification function f(),, is able to decide which information in its input features is more relevant to making a particular class decision. A DNN is lossy compressor when the absolute information content of any of its input samples 7 is larger than that of the class u to which it mapped.
Corollary 1.
The true source code C= f()) of learning algorithm used for the classification task is a lossy compressor when the Kolmogorov complexity K (ă) of one of its input samples is larger than the number of bits required to represent the corresponding class u.
Corollary formalizes a deep learning classifier as a lossy compressor, so the source code C' that corresponds to the true output function f()) is not uniquely decodable; i.e., its input samples 7 cannot
4

---

Under review as a conference paper at ICLR 2020
be recovered from the class to which they are mapped. A DNN can be trained to learn source code that generalizes well with respect to the true source code, but first we will analyze the similarity between these two source codes by using the normalized information distance.
Source codes are designed for the most efficient representation of data (Cover & Thomas 1991). Whether it is designed for data-transmission lossless or lossy, should retain information about the data necessary to accomplish a given task. The same consideration applies a learning system. The information in the input features of learning system is represented by the classification function that it learns; thus, a neural network can be viewed as source code that encodes inputs features for its classification task. The reformulation of a learning algorithm as procedure for searching for source code allow us to exploit theoretical results from algorithmic information theory and coding theory for deep learning. thereby avoiding the necessity to reinvent theory that is already established in these fields. Given that source codes are designed for the most efficient representation of data (Cover & Thomas] 199T), we will exploit the duality of source code and channel code to learn a classification function that represents the input features more efficiently for the classification task T:; i.e., a more general classification function. Showing that deep learning classifier is non- uniquely decodable source code is also fundamental to understanding that the normalized information distance between the input features and the output cannot be used to derive a condition for generalization in deep learning. This results from the fact that deriving such a condition would require finding the conditional Kolmogorov complexity K(Fly) of the input features with respect the output, which is impossible because the source code is not uniquely decodable; i.c., the program to go from the output to the input features cannot be found. A necessary and sufficient condition for generalization based on the normalized information distance can hence be found only between a learned source code and the true source code.
data-storage system, source code, whether
2.3 ACHIEVING GENERALIZZTION IN DEEP LEARNING
The normalized information distance
DI(C,O)= max( (AX((((C)), (ax(K(C),K(C))
between the true source code C' and learned source code Ö reveals how general Č is with respect to C. A necessary and sufficient condition ensuring that learned source code Co is more general than learned source code Ćn with respect to the true source code C is
Di(C, < Di(C, VÒO + C2.
(3)
Equation 3 is direct result of using the normalized information distance as a universal cognitive similarity metric determine whether learned source code Co C1 is more general with respect to the true source code C. Because the normalized information distance (Bennett et al., 1998) is a metric that uncovers all effective similarities between the true source code and learned source code, learning a source code that is closer to the true source code C under this metric ensures achieving generalization. The normalized information distance (C,, C)) between the true source code C and the learned source code Č' must thus be minimized in order to minimize the generalization error.
Theorem 1.
When learning algorithm used for the classification task T finds a suboptimal source code Ò instead of the true source code C, the optimization problem for the generalization of Ö is ming(DD(C, Õ)) = min& max (K (CCCC), ((CC))
Theorem 1 has formulated the optimization objective for generalization as the minimization of Di(C, C') and states that to achieve generalization we should make the learned function sufficiently complex for the classification task T. Theorem 1 states that the Kolmogorov complexity K(CIC) of the program that computes how to go from the learned source code Ć' to the true source code C or the Kolmogorov complexity K KCCC)) of the program that computes how to go from the true source code C' to the learned source code Č, whichever is larger, must be minimized in order to minimize generalization error. Thus, the goal is increase the complexity of the learned source code Č. but not beyond the complexity of the true source code C. Therefore, Occam's 's first razor (Domingos) 1999) still holds: simpler classifiers generalize better than complex ones. However, classifier that
5

---

Under review as a conference paper at ICLR 2020
Encoded Model
encoded input features
input features
E, (Ts)
Encoder
Base Model
class decision
Bal))
Cz())
Figure I: Encoded model architecture. An uncoded model simply feeds the input features to a base model, while the encoded model stacks the input features and encoded features and feeds those to base model with enough input channels to handle the original and encoded features.
does not perform well on its empirical sample set X is too simple for its classification task. Ideally, the learning algorithm would learn the true source code C, achieving the best possible performance metrics determined by its classification task T. In practice. because the learning algorithm will see only a small subset Xğ of the possible inputs training time, the learned source code C' will be partial function of the true source code C' at perfect training accuracy (that is, when the classifier has sufficient capacity to memorize the training samples (Zhang et al., 2017)) Whether a model is over-fit fit or under-fit is conventionally determined on a cross- vrossvaaldationn set and/or test set that are/is identically distributed with the training set, all of which are subsets of the empirical sample set. Being more general on such cross-validation set and/or test set does not as such guarantee generalization on the empirical sample set X because the latter may contain corrupted or perturbed samples and/or there may be samples in the empirical sample set that are out of distribution of the cross-valle validation set and test set. Therefore, whether a model is over-fit or under-fit does not have a consequence for Theorem 1. Next, we target learning source code that is more general on the empirical sample set X", not only on a cross- validatio set and/or test set.
In this work, we increase the complexity of the learned source code Č' by generating encodings Eo, E,- of the available input features 7s that capture relations between the features which are not learned well from the original features, and then append these encodings to the original features. Note that the available input features are denoted by Zig, which drawn from the set Xg of available features; i.e., Fs E XS. which is a subset of the empirical sample set X". By providing a different view of the relations between the features, the encodings E, help the learning algorithm to learn more complex source code Ög whose normalized information distance CC Cg) to the true source code C' is less than DI(C, This results in learning more general source code.
Theorem 2. For classification task T, a more general suboptimal code Ög is learned from the concatenation {Es, (Fs)), where E, : Xg + Yg is encoding of the input sample Hy such that Wg 2 Xg.
The effective capacity of several successful DNN architectures is sufficiently large to memorize the set X of available input samples (Zhang et al. 2017). Any encoding F. X2 - Wg. where Y the set of available encoded samples such that Y E Xg. when concatenated with the uncoded input samples øs. thus increases the Kolmogorov complexity of the learned source code, which is now called Čg. The task of the source code is to find the most efficient representation of its input data Cover & Thomas [999)). In typical communication system. the source code compresses the input, then a channel code adds redundancy to guard against noise in the channel, then the encoded information is transmitted over the physical channel. The design goal for the source and channel codes is to achieve the channel capacity (maximum mutual information between the channel input and output), In contrast, Theorem 2 considers a learning system in which an input code is followed by learned source code, the classification function, and the design goal is for the composition of the input and source codes to generalize as well as possible (see Figure T. In other words, in a learning system the "physical channel" precedes the source code, and it be seen as a process whereby the empirical sample set x is reduced to the set X5 of available input samples and/or whereby common corruptions, such as Gaussian noise, and adversarial perturbations, such those

---

Under review as a conference paper at ICLR 2020
generated by PGD, are applied to the set of available imput samples. Because the "physical channel" comes first in a learning system, there is no access to the set of information bits. Only a subset of these information bits can be accessed. which may have been subjected to common corruptions or adversarial perturbations. It is therefore crucial for learning algorithm to compress its features while retaining information useful for its classification task. One way accomplish this is to extend the input features with encodings that capture relations between features that are useful for classification and not captured well by the original set of input features. The classification task I' does not change when input features are extended by their encodings because it is defined by the mapping between the input features and the output (Goodfellow et al., 2016), which remains the same because the only input to the encoded model is the uncoded input features (see Figure D.. The encoder is simply new layer in the encoded model, which is designed from an encoder and an uncoded model.
2.4 APPROXIMATING NORMALIZED INFORMATION DISTANCE BY NORMALIZED COMPRESSION DISTANCE
The normalized information distance is based on the notion of Kolmogorov complexity, which is partial recursive function; i.c., it is not effectively computable. While we can use normalized informa- tion distance to analyze whether source code ÖE learned from the concatenation (Tg, E (Zs)} } of the encoded input samples (Tg) with the uncoded input samples z more general with respect to the true source code C, in practice we may need to approximate the normalized information distance with the normalized compression distance, so we can determine which of any pair of source codes is more general with respect to the true source code C.
Based on a real-world compressor, the normalized compression distance
(Cilibrasi & Vitányi 2005
Dc(C,CE)= Z((C,če) - min(Z max (ax()(()),Z((E))
approximates the normalized information distance (C), where is real-world compres- sor. Thus, the generalization condition and minimization of (C, Cg) can be cast in effectively computable forms. Note that neither Equation 2 nor Equation is training criterion. but they specify the normalized information distance and the normalized compression distance between the true source code C' and a learned source code, respectively. They are used to derive theoretical results, particularly the use of input codes to achieve generalization as illustrated by experiments in Section 3
Proposition 1. For the classification task T, DI(C, < ŌI = Z(CE)> Z(Ō).
Proposition 1 states for classification task T that the compressed size 7(Cx)) of the source code Čp learned from the concatenation (īs, } of the encoded input samples (iis) and the uncoded input samples Vg is larger than the compressed size Z(C') of the source code Ö learned from the uncoded input samples alone zs.
Proposition When a learning algorithm used for classification task T finds suboptimal source code ČE instead of the true source code C, the effectively computable optimization problem for the generalization of ÖF is ming, Dc(C, Cz) = maxcs Z(Cr), VÜ=: Z(Cr)) < Z(C).
Proposition 2 shows that the compressed size Z(Cz) of the source code ÖF learned from the concatenation (ās, Ex(īs) of the encoded input samples (xsss and the uncoded input samples Ts must be maximized until it reaches the compressed size Z(C) of the true source code C to learn the most general source code with respect to the true source code C for the classification task T. This statement is a consequence of the fact that Ög is a partial function of C' at perfect training accuracy. In other words, the source code Cg learned from the concatenation {Øg. E, (#s)} of the encoded input samples E, and the uncoded input samples Hs can be made more general if the encoded input samples (Ts) bear information of relations between input features that are not represented by its input samples.
7

---

Under review as a conference paper at ICLR 2020
flattening inpur features
encoded input features
x
2
4-D
Convolutional Encoder
5-PAM TCM Symbol Mapper
Bit Mapper
E
Figure 2: Flattening and encoding input features.
2.5 USING CHANNEL CODES ON INPUT FEATURES FOR IMAGE CLASSIFICATION
A channel encoder generates encodings from its input features that enable classifier learn relations between these features not captured by the set of available input samples. Concatenated together, these features are then input to model produce a class decision. For example, we use 4-D 5-PAM TCM scheme (Ungerboeck] 1982 Hatamian et al. 1998 IEEE 2015) as a systematic way to generate multiple encodings of input features.
As shown in Figure 2, the channel encoder flattens the input features by them into 2 x 2 patches of features, then, starting from the upper left feature and ending at the lower left feature, ordering them in sequence going in the clockwise direction. The features are traversed twice in order to avoid the initialization length of the channel code. This particular scheme is used because it focuses on local relations between features. Exploration of other flattening schemes is left for future research.
The features in the CIFAR-I0 dataset are represented by eight bits. The flattened features are fed to the convolutional encoder, which produces one extra bit out of the two least significant bits of the eight bits representing each feature. The 4-D 5-PAM TCM symbol mapper then maps each nine bits into four equidistant 5-PAM symbols, which are then mapped to 12 bits by the bit mapper. The bit mapper uses different symbol-to-be mappings to generate different encodings of the input features, and the matrix used for generating these encodings is given in Appendix C.7 Each encoding has the same size as the original input samples. Figure in Appendix C.1 shows three CIFAR-10 10 images and four of their encodings, which arbitrarily chosen. As seen in this figure, each encoding conveys a different view of the input features, which helps the source code (learned classification function) model relations between the features that useful for the image classification task. Note that using channel codes on the input features is not a data- aatta--agmenattionn technique: the encodings are appended the input features, not treated as new input samples. These encodings enable the classifier to learn from the set of available input samples a source code that is sufficiently complex for its classification task. As in a tata-transmission or data-storage system, the source code designed for the most efficient representation of the data, which is the set of available input features for the classification task at hand, and the channel code is independently designed for the channel. This combination is key to achieving generalization in deep learning, and how best to design a channel code for a given classification task is an intriguing future research direction.
3 EXPERIMENTAL RESULTS
Let the set of available input samples subjected common corruptions and adversarial perturbations belong to the empirical sample space from which input samples are drawn during inference. To show that using channel codes on the input features results in learning more general source code with respect to the true source code, we conduct experiments on the CIFAR-10 10 and CIFAR-10- (Hendrycks & Dietterich) 2019) datasets to show increased robustness to common corruptions and adversarial perturbations. For CIFAR-10 and CIFAR-10-C, we train uncoded VGG-11 and VGG- 16 models, encoded VGG-11 1 and VGG-16 models, and an uncoded ResNet- 18 model. The VGG networks are modified only by adding the encoder and increasing the number of input channels. The encoded models use the same training criterion as the uncoded models, namely the cross-entropy loss. The training setup and the achieved test accuracies given in Appendix C
8

---

Under review as a conference paper at ICLR 2020
Gaussian Noise
Shot Noise
Impulse Noise
25000
cumulative number
Uncoded
of test errors
20000
encodings
encodings 32 encodings
15000
10000
5000
2
3
4
1
2
4
5
2
3
severity
severity
severity
Figure 3: The uncoded VGG-11 model and encoded VGG-11 models tested the corrupted samples in the CIFAR-10- dataset.
In all experiments conducted on the encoded models, are corrupted or perturbed before they are input to the encoded models, as the uncorrupted or unperturbed input samples would not be accessible by neural network in real-world application. Increasing the number of encodings may reduce the generalization error, but at the expense of increased run time. However, encoding the training and samples a one-time process that be done prior to training, unlike adversarial training, which requires generating perturbed input samples each epoch. In Appendix [C.6] we show that increasing the number of input channels does not, as such, confer robustness to Gaussian noise or to PGD. Designing efficient input codes for given classification task considering the generalization error and the required number of encodings is a direction for future research. To the best of the authors' knowledge, there is no other published method that can achieve robustness to both common corruptions and adversarial perturbations.
arbitrary encodings. The input samples
3.1 ROBUSTNESS TO COMMON CORRUPTIONS
The set of available input samples may be subjected to common corruptions before reaching real- world image classifier. For example, Gaussian noise can appear in low-lighting conditions, and shot noise is caused by the discrete nature of light. To show robustness to such corruptions, conduct experiments on the CIFAR-IO-C and CIFAR-10 datasets. We use four common corruptions in our experiments, namely Gaussian noise, shot noise, impulse noise, and speckle noise.
The CIFAR-10-C dataset consists the 10,000-sample CIFAR-10 test set subjected to five different noise levels, called severity, number of arbitrary encodings concatenated to the original input features increases robustness to Gaussian noise, shot noise, and impulse noise. The results for speckle noise is given Appendix (C3 For example, when test samples are subjected to impulse noise with severity level of 4, we see sharper increase in the number of test errors for the uncoded VGG-11 model than that for the VGG- model with 32 encodings. Note that the vertical axis in these plots is cumulative: the number of test errors made at the previous severity level is added to that at the current severity level. Table [ in Appendix C.4 compares the encoded VGG-11 model with 32 encodings with previously published methods on the CIFAR-IO-C dataset, which shows that the encoded VGG-1 model achieves the highest inference accuracy (defined in Appendix B) against shot noise with severity level of compared with all the other works listed in this table. Additional experimental results on Gaussian noise are shown in Figure i Appendix C.3
has 50,000 samples in all. As shown in Figure increasing the
3.2 ROBUSTNESS TO ADVERSARIAL PERTURBATIONS
To show robustness to adversarial perturbations without adversarial training, we conduct experiments on the CIFAR-1 10 dataset. We use the white-box PGD attack (Madry et al.) (2018) and transfer attacks from an uncoded VGG-16 and an uncoded ResNet-13 18 model to evaluate the adversarial robustness of the encoded VGG-16 models. The results for the black-box boundary attack (Brendel et al., 2018) given in Appendix C.3 The white-box PGD attacks use the gradient of the loss function with respect to the uncoded input features in the encoded VGG-16 models because the channel encoder is part of the encoded VGG- 16 models; i.e., the only input to the encoded model is the uncoded input features. The encoder is simply a new layer of the neural network architecture, whose outputs are computed directly from the uncoded input features. Changing the outputs of the encoder layer is

---

Under review as a conference paper at ICLR 2020
cumulative number of successful attacks
7500
5000
Uncoded
encodings 8 encodings 32 encodings
2500
0.00
0.01 0.02 0.03 0.04 0.05 0.0 (L-inf distance)
0.2
0.3
0.4
0.5
0.0
0.2
0.4
0.5
(L-inf distance)
(L-inf distance)
Figure 4: Robustness is tested with samples perturbed by the white-box PGD attack (left), transfer PGD attack generated on the uncoded VGG-16 model (middle), transfer PGD attack generated on ResNet- 18 model (right).
tantamount to changing the outputs of any other layer of the model, which a threat model that falls of the scope of work.
For the CIFAR-10 experiments, we use different numbers of encodings, and robustness to all adversarial perturbations in our experiments systemically increased with an increasing number of arbitrary encodings concatenated to the input features, Figure4 the results for the white-box PGD and transfer PGD attacks. The plot on the left shows the increase in robustness to white-box PGD starting from a random perturbation around the natural example and using 20 iterations and step size of 0.003. For example, at lo distance of 0.031, the inference accuracy of the VGG-16 model with 32 encodings is 30.19% while keeping a test accuracy of 87.38%. To test the robustness of the encoded VGG-16 models against transfer attacks using the same PGD settings, we generate adversarial examples the uncoded VGG-16 model and uncoded ResNet-18 model. As before, the encoded VGG-16 models show more robustness with an increasing number of encodings as shown in the
the middle and right plots of Figure 4 For example, when adversarial examples generated ResNet-18 18 model are used to test the robustness of the uncoded VGG- 16 model and the encoded VGG-16 models, at epsilon of 0.2 (f.o), the inference accuracy of the uncoded VGG-16 16 model is 12.25%, whereas that of the VGG-16 model with 32 encodings is 63.87%.
Table 2 in Appendix C.5 compares the encoded VGG-16 model with previously published defenses on the CIFAR-10 dataset (Zhang et al.) 2019). The adversarial attack type used for all the works listed in this table is the white-box PGD starting from random perturbation around the natural example, using 20 iterations, step size of 0.003, and an epsilon of 0.031 (foo). It can be observed that this work achieves sizable inference accuracy Aiffrence of 30. 30.19% while keeping the highest test accuracy Aust of 87.38% among all the works listed in this table, and importantly does not use adversarial training. Generating input encodings can be done just once prior to training, whereas adversarial training requires generating adversarial examples in each epoch, which is expensive when an iterative method such as PGD used (Madry et al. 2018). The difficult problem of achieving adversarial robustness in real-waroee world application requires a holistic approach. Our approach, which does not depend on adversarial training. can be readily used combination with adversarial training and other known methods to achieve greater robustness to adversarial perturbations.
4 CONCLUSION
We presented a theoretical and experimental framework for defining and understanding generalization in deep learning, defined the difference between training and inference errors. The theoretical findings and experimental results show that a learned classification function must be sufficiently complex for a classification task order to closer to the true classification function. Another insight from this study is that concatenating encodings of input features to the original input features helps to achieve generalization in deep learning by enabling the classifier to learn relations between features not captured by the original inputs. Experiments demonstrate that model trained on arbitrarily encoded input features is more robust to common corruptions and adversarial perturbations and that using more encodings may be beneficial to minimize the generalization error. Designing input codes to help a DNN learn a more general classification function with a minimum number of encodings is intriguing research direction achieve reliability in machine leaming.
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Charles H. Bennett, Péter Gács, Ming Li, Paul M. B. Vitányi, and Wojciech H. Zurek. Information distance. IEEE Transactions on Information Theory,
1998.
Vighnesh Birodkar, Hossein Mobahi, Dilip Krishman, and Samy Bengio. A closed-form learned pooling for deep classification networks. arXiv preprint arXiv: 03808, 2019.
Wieland Brendel, Jonas Rauber, and Matthias Bethge. pecision-based adversarial attacks: Reliable attacks against black-box machine learning models. In Proceedings of the International Conference on Learning Representations, 2018.
Rudi Cilibrasi and Paul M. B. Vitányi. Clustering by compression. IEEE Transactions on Information Theory, 1144::55331154 2005.
Thomas M. Cover and Joy A. Thomas. Elements of information theory. John Wiley & Sons, New York, New York, 1991.
Hal Daumé III and Daniel Marcu. Domain adaptation for statistical classifiers. Journal of Artificial Intelligence Research, 26:101-126, 2006.
Pedro Domingos. The role of Occam's 's razor in knowledge discovery. Data Mining and Knowledge Discovery, 344):409-425, 1999.
Yaroslav Ganin and Victor Lempitsky. Unsupervised domain adaptation by backpropagation. In Proceedings of the International Conference on Machine Learning. 2015.
Ziv Goldfeld, Ewout Van Den Berg, Kristjan Greenewald, Igor Melnyk, Nam Nguyen, Brian Kings- bury, and Yury Polyanskiy. Estimating information flow in deep neural networks. In Proceedings of the International Conference Machine Learning, 2019.
Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016. http:
/www.deepleerrnnnnoo.. org
lan Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In Proceedings of the International Conference on Learning Representations, 2015.
Mehdi Hatamian, Oscar E. Agazzi, John Creigh, Henry Samueli, Andrew J. Castellano, David Kruse, Avi Madisetti, Nariman Yousefi, Klaas Bult, Patrick Pai, Myles Wakayama, Mike M. McConnell, and Marty Colombatto. Design considerations for Gigabit Ethernet 1000Base-T twisted pair transceivers. In IEEE Custom Integrated Circuits Conference, 1998.
Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness to common corruptions and perturbations. In Proceedings of the International Conference Learning Representations, 2019.
IEFE, Physical coding sublayer, physical medium attachment (PMA) sublayer and baseband medium, type 1000BASE-T. IEEE Standard 802.3ab, 2015.
Harini Kannan, Alexey Kurakin, and Ian Goodfellow. Adversarial logit pairing, arXiv preprint arXiv: Ttt.::803303777 2018.
Kenji Kawaguchi, Leslie Pack Kaelbling, and Yoshua Bengio. Generalization in deep learning. arXiv preprint 17X.v:1710.05468, 2017.
Andrei N. Kolmogorov. Combinatorial foundations of information theory and the calculus of probabilities. Russian Mathematical Surveys, 38(4):29-40, 1983.
Liu Kuang. Train CIFAR10 with PyTorch. pytorch-cifar 2019.
iu/
Alexey Kurakin, Ian J. Goodfellow, and Samy Bengio. Adversarial machine learning at scale. In Proceedings of the International Conference Learning Representations, 2017a.
11

---

Under review as a conference paper at ICLR 2020
Alexey Kurakin, Ian J. Goodfellow, and Samy Bengio. Adversarial examples in the physical world. In Proceedings of the International Conference on Learning Representations Workshops, 2017b.
Y. LeCun, L. Jackel, L. Bottou, A. Brunot, C. Cortes, J. Denker, H. Drucker, I. Guyon, U. Muiller, E. Sackinger, P. Simard, and V. Vapnik. Comparison of learning algorithms for handwritten digit recognition. In International Conference on Artificial Neural Networks, 1995.
Jaeho Lee and Maxim Raginsky. Minimax statistical learning with Wasserstein distances. In Advances in Neural Information Processing Systems, 2018.
Da Li, Yongxin Yang, Yi-Zhe Song, and Timothy M. Hospedales. Deeper, broader and artier domain generalization. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2017.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In Proceedings of the International Conference on Learning Representations, 2018.
Pietro Morerio, Jacopo Cavazza, and Vittorio Murino. Minimal-entroop correlation alignment for unsupervised deep domain adaptation. In Proceedings of the International Conference on Learning Representations, 2018.
Saeid Motiian, Marco Piccirilli, Donald Adjeroh, and Gianfranco Doretto. Unified deep supervised domain adaptation and generalization. In Proceedings of the IEEE International Conference Computer Vision, 2017.
Krikamol Muandet, David Balduzzi, and Bernhard Schölkopf. Domain generalization via invariant feature representation. In Proceedings of the International Conference on Machine Learning, 2013.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring generaliza- tion in deep learning. In Advances in Neural Information Processing Systems, 2017.
Kate Saenko, Brian Kulis, Mario Fritz, and Trevor Darrell. Adapting visual category models to new domains. In Proceedings of the European Conference on Computer Vision, 2010.
Shiv Shankar, Vihari Piratla, Soumen Chakrabarti, Siddhartha Chaudhuri, Preethi Jyothi, and Sunita Sarawagi. Generalizing across domains via cross-gradient training. In Proceedings of the Interna- tional Conference on Learning Representations, 2018.
Aman Sinha, Hongseok Namkoong, and John Duchi. Certifiable distributional robustness with principled adversarial training. In Proceedings of the International Conference on Learning Representations, 2018
Baochen Sun and Kate Saenko. Deep CORAL: Correlation alignment for deep domain adaptation. In Proceedings of the European Conference on Computer Vision, 2016.
Yu Sun, Xiaolong Wang, Zhuang Liu, John Miller, Alexei Efros, and Moritz Hardt. Test-time 2019.
training for out-of-distribution generalization. arXiv preprini 1909.
Eric Tzeng, Judy Hoffman, Kate Saenko, and Trevor Darrell. Adversarial discriminative domain adaptation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2017.
Goufried Ungerboeck. Channel coding with multilevel/phase signals. IEEE Transactions on Infor- mation Theory, 28(1)555-67, 1982.
Kush R. Varshney and Homa Alemzadeh. On the safety of machine learning: Cyber-physical systems, decision sciences, and data products. Big Data, (33)224-255,, 2017.
Riccardo Volpi, Pietro Morerio, Silvio Savarese, and Vittorio Murino. Adversarial feature augmenta- tion for unsupervised domain adaptation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2018a.
12

---

Under review as a conference paper at ICLR 2020
Riccardo Volpi, Hongseok Namkoong, Ozan Sener, John Duchi, Vittorio Murino, and Silvio Savarese. Generalizing to unseen domains via adversarial data augmentation. In Advances in Neural Information Processing Systems, 2018b.
Eric Wong, Frank R. Schmidt, Jan Hendrik Metzen, and J. Zico Kolter. Scaling provable adversarial defenses. In Advances in Neural Information Processing Systems, pp. 8400-8409, 2018.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In Proceedings of the International Conference on Learning Representations. 2017.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric P. Xing, Laurent El Ghaoui, and Michael I. Jordan. Theoretically principled trade-off between robustness and accuracy. In Proceedings the International Conference on Machine Learning, 2019.
A PROOF OF MATHEMATICAL STATEMENTS
Proof of Lemma 1. For classification task T. a learning algorithm is asked to produce the true output function f(-) X - A. There exists a source code C' for random variable X, which is also mapping from the sample space X of X to the m-ary signal alphabet A from which a class is drawn. The true output function f(-) is equivalent the source code C' for the random variable X because their domain X" and codomain are equal and the image of both functions is the same for each input sample 7 in the domain X
Proof of Corollary 1. If the Kolmogorov complexity (()) of an input sample Ø is larger than the number of bits required to describe the class u to which it mapped, which is at most [log, m) bits, then some information about the input sample 7 is lost. Satisfying this condition, the true source code is lossy compressor.
Proof of Theorem 1. The normalized information distance
D) max ((((((()))))))))))())((() (C(C), max(K(C), K(Ō))
(5)
a universal cognitive similarity metric that minorizes all other admissible distances up to negligible additive error term. This means that decreasing the normalized information distance (C C') ensures that the true source code C' and the learned source code Ö are more similar; i.c., the learned source code C' is more general with respect the true source code C. In a real-world setting, because the empirical sample space X" may be too large, the learning algorithm sees an input sample 2g drawn from subset Xg of x"; i.e., Xg C X Put differently, the set Xg of available input samples which a neural network is trained and tested a subset of the empirical sample set X which the trained neural network sees during inference. This means that true source code C bears information of all possible relations between input features that are useful for the classification task T, whereas the learned source code Ć bears information of subset of all possible relations between the input features. The Kolmogorov complexity of the true source code is thus larger than that of a source code learned from the set of available input samples by sufficiently high-capacity neural network, which can memorize its input samples (Zhang et al. 2017;; i.e., KCC) > K(C). Therefore,
min(Di(C,,)) min max max(K(C))), C
(6)
is an optimization problem for the generalization of the learned source code Ö with respect to the true source code C.
Proof of Theorem 2. Any encoding E, X Y that bears information useful for the classifica- tion task T' that is not entirely represented by the subset Xy of uncoded input samples; i.e., Yg g Xg. when concatenated with the uncoded input samples Ty. increases the Kolmogorov complexity of the learned source code, which is now called Čr, because sufficiently high-capacity neural network
13

---

Under review as a conference paper at ICLR 2020
memorize its imput samples (Zang al. 2017). Put differently, the Kolmogorov complexity K ((C)) of the source code Cg learned from concatenation {ās, (ās) } of uncoded and encoded input samples is larger than that of the source code C learned from uncoded input samples alone if the encodings bear information of relations between input features that are not represented by the uncoded input samples. As the the true source code C bears information of all possible relations between input features, the Kolmogorov complexity ((CE) of the source code CF learned from a concatenation {ăg, (Ts)) of uncoded input samples and their encodings bearing information of a subset of all possible relations between input features is upper bounded by the Kolmogorov complexity (C) of the true source code C; i.e., ((C) ((Cp). In other words, sufficiently high-capacity neural network can memorize its input samples (Zhang et al. 2017) without being assisted by encodings E.. However, the encodings E, bear information of relations between input features, which help to increase the Kolmogorov complexity of the learned source code if they are useful for the classification task 7: i.e., they are contained in the empirical sample set X", of the neural network and if the information in the mappings contained in the input code, which is used to generate the encodings E, is not represented in the set XS of available input samples. The conditional Kolmogorov complexities (CCC)), ((CC)) are thus both larger than (K(C)CE), K ((Cr(C)), respectively, because the program that computes how to go from ÖE to C' is shorter in length than the program that computes how to go from Ó' to C. The same holds in the reverse direction. Therefore, max K (CICE), K(CE(C)) < max( (CCC), which results in Di(C, Cg) < DI(C, Õ). The source code Cg learned from the concatenation {Ts, (ās)) is thus more general than the source code Ö learned from Tg.
Proof of Proposition 1. As the normalized information distance DC CB) is not effectively computable, it can be approximated for practical purposes by the normalized compression distance
Dc(C,Cε) Z(IC, Z((C,č=)) - min Z(CE))
max(Z(C),ZZ(aa)
where a real-world compressor. The learning algorithm sees an input sample Ts drawn from subset Xg of X" as the empirical sample space X may be too large. Because a sufficiently high-capacity neural network can memorize its input samples (Zhang et al.) 2017). the compressed size of the true source code is larger than that of the learned source code; i.e., Z(C) > Z(Cg). At perfect training accuracy, the compressed size 7 Cæ}) of the concatenation {C, Cε) is equal to (C)), as ČΦ is a partial function of C. For a sufficiently high training accuracy, we can consider [Z[[, CEJ) Z(C) to be negligible for the purposes of generalization. As the generalization condition Di(C, Čε) < Dr(C, is not effectively computable, an equivalent effectively computable condition is useful for practical purposes. As Di(C, Cg) < D) = Dc(C, CB) C) for the purposes of generalization, the effectively computable condition
Z(IC, - min() Z((C,C)) min min(2(C),
(8)
max(Z(C),
max(Z(C),Z(())
equivalent to
Z(Cx) > Z(Ć).
(9)
Proof of Proposition By the Proof of Proposition 1, the effectively computable optimization problem for the generalization of ČE with respect to C is
min (o(C,(EC max Z(ŌE), VỘB: Z(CB) < Z(C). CR
(10)
Ön
B DEFINITIONS
Inference Accuracy. The classification accuracy measured on subset of the empirical sample set X", which may be subjected to common corruptions or adversarial perturbations and which may be out of distribution of the training set, is defined as inference accuracy.
14

---

Under review as a conference paper at ICLR 2020
The definition of inference accuracy can be contrasted with that of test accuracy by considering that the former is measured on subset the empirical sample set X" which consists of corrupted or perturbed samples which may be out of distribution of the training set and that the latter is measured on the test set which consists of uncorrupted and unperturbed samples that are presumed to come from the same distribution the training set.
Generalization Error. The difference between the training error measured the training set and inference error measured on a subset of the empirical sample set X", which may be subjected to common corruptions or adversarial perturbations and which may be out of distribution of the training set, is defined as the generalization error.
This definition is different from that of prior works (Neyshabur et al. 2017: Kawaguchi et al. 2017) which define generalization error as the difference between the training error measured on the training set and test error measured the test set.
Generalization. A learned classification function is said to be more general with decreasing generalization error.
This definition is different from that of prior works (Neyshabur et al. 2017 Kawaguchi et al. 2017 which define a learned classification function to more general with a decreasing difference between the training enror measured on the training set and test error measured the test set.
Source Code. A source code for a random variable X is mapping from the sample space X" of to an m-ary signal alphabet A.
Source codes can be designed for the most efficient representation of the data (Cover & Thomas 1991). Channel codes appropriate for a channel can be designed separately and independently. This combination is efficient any other method that can be designed by considering both problems together. We refer the reader to a textbook such as (Cover & Thomas 199I) for a detailed understanding of source codes.
Kolmogorov Complexity. The Kolmogorov complexity Krr(z) of string æ with respect to universal computer U defined as
Ky (z) min 1(p).
(11)
pp)
where p denotes a program, and (p)) denotes the length of the program
Thus, (x) is the shortest description length of æ over all descriptions interpreted by computer U.
We fix such a universal computer U as reference and write Ky (x) = K(x). We refer the reader to a
textbook such (Cover & Thomas [991] and (Bennett al. 1998 Cilibrasi & Vitányi 2005) for
detailed understanding of Kolmogorov complexity.
C SUPPLEMENTARY EXPERIMENTAL INFORMATION
C.I ENCODED CIFAR-1O 10 IMAGES
Figure shows three CIFAR- 10 images and four of their encodings, which are arbitrarily chosen. This figure shows that each encoding conveys different view of the input features, which helps the learned source code model relations between the features that are useful for the image classification task.
C.2 TRAINING SETUP
All models are trained in PyTorch with 16 random initializations. We train the networks over 450 epochs with batch size of 128 and with a dynamic learning rate equal to 0.1 until epoch 150, 0.01 until epoch 250, and 0.001 until epoch 450 (Kuang) 2019). A test accuracy of 92.54% is achieved for the uncoded VGG-11 model, and 92.1 12%, 91.45% % and 90.199 19% for the VGG-11 model with 2, 8, and 32 encodings, respectively. A test accuracy of 94.15% is achieved for the uncoded VGG-16 model,
15

---

Under review as a conference paper at ICLR 2020
Uncoded
Encoding 0
Encoding
Encoding 2
Encoding
Figure 5: CIFAR-10 uncoded and encoded images. Top, middle, and bottom rows correspond to red, green, blue channels, respectively.
number test errors
10000
cumu latiic number
25000
Gaussian noise Shot noise
of test errors
20000
6000
15000
4000
Uncoded
10000
encodings encodings
2000
5000
32 encodings
0
25
20
15
10
5
2
3 severity
signal-to-noise ratio (dB)
Figure 6: The uncoded VGG-11 model and encoded VGG-11 1 models tested the CIFAR-11 10 test set corrupted by Gaussian noise (left) and the VGG-16 16 model with 32 encodings tested on the samples in the CIFAR-10-C dataset corrupted by Gaussian noise and shot noise (right).
and 91.11 91.11% %, 88.93%, and 87.38% for the VGG- model with 2, and 32 encodings, respectively. The uncoded ResNet- 18 model, which is used for transfer attacks, achieves 95.20% test accuracy.
Speckle Noise
cumulaatve number errors
15000
Uncoded encodings
cumulative number of successful attacks
10000
encodings 32 encodings
7500
10000
5000
5000
2500
0.00
0.02
0.04
0.06
0.08
0.10
severity
(normalized L2 distance)
Figure 7: The uncoded VGG-11 model and encoded VGG-11 models tested on the samples in the CIFAR-10-C dataset corrupted by speckle noise (left) and the uncoded VGG- 16 model and encoded VGG-16 model tested on the samples in the CIFAR-16 10 dataset perturbed by the black-box boundary attack (right).
16

---

Under review as a conference paper at ICLR 2020
C.3 ADDITIONAL EXPERIMENTS
To show the robustness of the encoded VGG-11 models to Gaussian noise beyond the noise levels included in the CIFAR-IO-C dataset, apply Gaussian noise with zero mean and variance o the CIFAR- 10 test set. The average input-feature energy equals
(12)
kn
where F; is feature of the imput sample ž, l is the number of input samples in the test set, and is the number of features in an input sample. We define the signal-to-noise ratio to be
lnn
(13)
kno
1=0
In Figure 6 we show on the left plot that increasing the number of arbitrary encodings concatenated to the input features significantly increases robustness to Gaussian noise applied to the CIFAR-10 test set with signal-to-noise ratios from 25 to 0 dB. For example, at signal-to-noise ratio of 12 dB, the inference accuracy of the VGG-11 model with 32 encodings is 61. 61.15%, whereas that of the uncoded VGG-11 model is 21.49% On the right plot, the experimental results for the VGG-16 16 model with 32 encodings tested on the samples in the CIFAR-IO-C dataset corrupted by Gaussian noise and shot noise are given. The results indicate that using larger encoded model does not necessarily confer more robustness to such common corruptions as Gaussian noise and shot noise than a smaller encoded model.
In Figure 7 the results of the experiments conducted on the CIFAR-10-C dataset corrupted by speckle noise and black-box boundary attack experiments the CIFAR-10 dataset are shown. On the right plot, as with the other type of common-corruption experiments, we see that increasing the number of encodings increases robustness to speckle noise. On the left plot, we see that the encoded model is significantly more robust to the boundary attack than the uncoded model. For example, at normalized & distance of 0.01, an inference accuracy of approximately 50% is achieved by the model with 32 encodings, whereas the inference accuracy of the uncoded model already drops to 0% an Eg distance much closer to
C.4 PERFORMANCE COMPARISON: COMMON CORRUPTIONS
Table T compares the encoded VGG-11 model with 32 encodings with previously published methods on the CIFAR-IO-C dataset.
At a severity level of 5, the encoded VGG-11 model achieves the highest inference accuracy against shot noise compared with all the other works listed in this table, which use a ResNet-18 or ResNet-26 model. The highest inference accuracy (77.30% against Gaussian noise attained by the adversarial logit pairing (ALT) method published in Kannan et al. (2018), but the test accuracy of this method 83.50% whereas the encoded VGG-II model achieves the second highest inference accuracy (75.22%) against Gaussian noise with test accuracy of 90. 19%. Our results seem to indicate that using a larger number of encodings improves robustness to common corruptions, so the inference accuracy achieved by the channel-coding method may be improved by merely increasing the number of encodings or designing higher performance codes.
C.5 PERFORMANCE COMPARISON: ADVERSARIAL. PERTURBATIONS
Table 2 compares the encoded VGG- 16 model with previously published defenses on the CIFAR-10 dataset. The experimental results do not imply that encoded input features are more robust to common corruptions and adversarial perturbations than uncoded features. The encoded input features simply bear information of relations between input features that are not represented by the uncoded input features, so source code learned from a concatenation of uncoded and encoded input features bears more information of the true source code than source code learned from uncoded input features alone. A source code learned from a concatenation of uncoded and encoded input features is thus more robust than source code learned from uncoded input features alone.
17

---

Under review as a conference paper at ICLR 2020
Table 1: Comparison of the inference accuracy of the encoded model with that of prior methods the CIFAR-10-4 dataset corrupted by Gaussian noise, shot noise, and impulse noise with a severity level 5. Reference
Method
Network
Atest
Ainference Gaussian Noise
Ainfrrnnce Shot Noise
Aiffrence Impulse Noise
Birodkar et al. (2019)
RPO
ResNet-18
95.70%
25.00%
32.70%
21.90%
Sun et
(2019)
JT
ResNet-26 91.90%
50.60%
54.70%
46.60%
Sun et al.
(0199)
TTT
ResNet-26 92.10%
54.40%
58.20%
50.00%
Sun
(2019)
TTTO
ResNet-226 91.80%
74.20%
77.40%
69.40%
Kannan et al.
(201 8)
ALP
ResNet-26
83.50%
77.30%
77.10%
71.70 %
This work
CC
VGG-11
90.19%
75.22%
77.58%
60.18%
RPO: replacing pooling operator; JT: joint training; TTT: test-time training; TTTO: test-time training
online; ALP: adversarial logit pairing; CC: channel coding.
Table 2: Comparison of the encoded model with prior defense models under white-box PGD attacks with iterations, a step size of 0.003, and an epsilon of 0.031 (foe) on the CIFAR-10 dataset.
Reference
Defense type
Adversarial training
Atest
Ajferrncc
Kurakin et al. 2017a)
regularization
Yes
85.25%
45.89%
Madry et al. 2018
robust optimization
Yes
87.30%
47.04%
Wong et al. 2018
robust optimization
Yes
27.07%
23.54%
Zhang al. 2019
regularization channel coding
Yes
84.92%
56.61 %
This work
No
87.38 %
30.19%
C.6 IMPACT OF INCREASING THE NUMBER OF INPUT CHANNELS OF DNN ON ITS ROBUSTNESS
To study the impact of increasing the numher of input channels of the uncoded VGG-11 and VGG-16 models, conducted experiments the encoded VGG-11 and and VGG-16 models that use identical encodings; i.c., the input features are replicated across additional input channels (the "encoders" are just identity functions). In Figure we see on the left that increasing the number of input channels of the uncoded VGG-11 model confers no robustness to Gaussian noise whatsoever. The plot on the right shows that increasing the number input channels of the uncoded VGG-16 model does not confer robustness white-box PGD either.
cumulativee number successful attacks
8000
7500
number test
6000
5000
4000
Uncoded replica
2000
2500
32 replicas
0,1
25
20
15
10
0.00
0.01
0.02
0.03
0.04
0.05
signal-to-noise ratio (dB)
(L-inf distance)
Figure 8: Impact of increasing the number of input channels in the uncoded models on robustness. Robustness to Gaussian noise (left) and the PGD attack (right) is tested by providing identical samples from CIFAR-I0 test set to increased number of input channels.
18

---

Under review as a conference paper at ICLR 2020
C.7 SYMBOL-TO-BEE BIT MAPPING
The bit mapper in Figure 2
uses the matrix
0
0
0
1
0
1
0
0
0
1
0
1
1
1 0 1
1 1
0
0
0
1
0
0
0
1
0
0
0
1
1
1
0
0
00000000000
1
OOOTEOO COOOOOO
0
O
0
O
00201100
0
1111111000
1
TODOOO
O
000000000000000
O
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
O
0
1
0 0 1
0
0
0
10101
1
11111
0
1
1
1
0
0
0
0
1 1
0
0
0
1
0
0
1
00000
0
1
0
0
to map four 5-PAM symbols into 12 bits. In this symbol-to-bit mapping matrix, the 7th row cor- responds to the encoding E,, where 0 < 31. Each symbol in the 5-PAM symbol alphabet is converted into three bits by using the corresponding three columns in this matrix. For example, the first symbol in the 5-PAM symbol alphabet for the encoding Eg is converted [1 0 0] by drawing the bits from the third row and third, fourth, and fifth columns of the symbol-to-N bit mapping matrix. After all four of the 5-PAM symbols are converted into their respective three bits, these bits are concatenated to each other, determining the value of the corresponding feature in the encoded sample.
19


Reviews:
[{"review_id": "S1xdSRt39r", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a novel approach to training classifiers inspired by concepts from algorithmic information theory. Specifically, the inputs are augmented with additional features formed by encoding the image (using a source code). In addition, the paper argues to use the normalized compression distance as a loss criterion when training; this is a computationally tractable proxy for the normalized information distance, which the paper argues is what one really should use to generalize well, but which is not computationally tractable. (In particular, evaluating the Kolmogorov complexity, which is required to compute the normalized information distance, is not tractable.) The idea is demonstrated via experiments training common image classifiers (VGG-11 and ResNet-18) on clean and corrupted versions of the CIFAR-10 dataset, and comparing how they fare against adversarially trained methods on noisy and adversarial examples.\n\nI believe that this paper contains interesting and novel ideas, but there are also some inconsistencies and some points that are vague. I would consider raising my score if the authors address or clarify these issues, which are detailed below.\n\nThe introduction discusses generalization very broadly, suggesting that the usual definition of generalization (e.g., accuracy on a hold-out set, drawn from the same distribution as the training set) is not the version of generalization that one should focus on. However, the precise definition of generalization is never provided. The intro also mentions briefly about adversarial examples, and this is the focus of the experiments. It would help to clarify whether the paper focuses on being robust to adversarial examples as a form of generalization, or more precisely, what how is the concept of generalization defined/measured in this paper. (E.g., the first sentence of Sec 2.1 mentions \"our running definition of generalization,\" but no precise definition has yet been provided.\n\nTo make the paper self-contained, it would help to recall the formal definition of Kolmogorov complexity; this could be done in the appendix.\n\nSec 2 begins to make the connection between a classifier and a source code. However, these definitions are not precise. For example, in the usual PAC learning setting one has a distribution D over the training data (x,y). After specifying a particular loss function, the Bayes-optimal classifier is well defined. Does the source code C correspond this classifier? I would guess not, since the paper seems to be introducing a specific loss criterion, but it would be good to clarify this in the paper. Since you are assuming there is a \"true output function\" f, does this correspond to what is usually referred to as the \"realizable\" setting (i.e., where y = f(x) is a deterministic function of x)?\n\nNotation is sometimes used without having been defined. For example, what is $\\vec{x}_{S}$?\n\nIt isn't clear how one can train using the criterion (4), or equivalently, solve the problem set forth in Prop 2, in practice, since the true source code C is not known. Please elaborate on this.\n\nIn the experiments, how precisely is the VGG network modified to handle the encoded inputs? Are these just passed as additional input channels? Is the network architecture need to be modified in any other way to account for these additional inputs? Also, what loss criterion is used for training? Cross-entropy? Or something related to normalized information distance? This isn't clear from the discussion in Sec 3.\n\nIn Sec 3.2, is it really fair for the PGD attacks to only use the gradient of the loss wrt the uncoded input? Is this still really \"white box\"? How does the proposed approach perform if the attack also has access to the encoded input? It would be good to report both settings in the paper.\n\nThe introduction made connections to other forms of generalization, including domain generalization and domain adaptation. Based on this, I had expected to experiments illustrating the utility of the proposed for these problems.\n\nThe existing experiments do make clear that the encoded inputs are more robust to perturbations and aversarial attacks than uncoded inputs. Is the encoding assumed to be performed on the perturbed input, or on an unperturbed input (i.e., before it is perturbed)?\n\nI don't find the results in Table 1 fully convincing that the proposed approach should be preferred over previous approaches. For instance, the approach of Madry et al. (2018) achieves slightly lower test accuracy, but substantially higher inference accuracy. In general, one expects to see a tradeoff here. If one were to plot these points, would the proposed method clearly fall above the Pareto frontier? Minor: Please clarify the definition of \"inference accuracy\" in the paper.\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "S1xOJc_pFS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes an approach to generalization for deep networks based on kolmogorov complexity. The normalized information distance and its approximation via a compression algorithm were developed in earlier work, as noted by the authors. So the main contribution seems to be framing the deep learning classifier as a source code and developing a method to minimize the proposed information distance to improve generalization.\n\nI found a few gaps that I think the authors should clarify for me. Why is framing the deep learning classifier as a source code important? It seems to me that the K(C) is the same as K(f) where the f is the function mapping X -> y, whether it is learned or not. \n\n- Moreover, unless I'm missing something, the source code is a way to encode the values of a random variable such that communication is minimized. If the C=f  is a map from X_i -> y, X_i is an image, and y is a scalar, the source code as defined is not encoding X_i, it is simply encoding a part of X_i that is relevant to the classification task.\n\n1. The claim \" Because a sufficiently high-capacity neural network can memorize its input samples the Kolmogorov complexity of the true source code is larger than that of the learned source code: i.e., K(C) > K(C~).\" needs proof in itself. This stands opposed to the intuition that an over-fit model has larger kolmogorov complexity because it is not \"simple\".\n\n- Further, how does this square with the claim that the K(C~) is increased by adding encodings? If K(C~) is increased, then I think one needs to show that K(C~)< K(C) even with the encodings added?\n- Finally, by adding the encodings, the task has been fundamentally changed to the classification on the dataset [x, E1(x), E2(x) .. ] . So, the insight about minimizing information distance computed between C and C~ applies when the learned and the true \"source code\" correspond to the new task. This does not seem to be addressed in the theory.\n\n2. For the noise robustness experiments, there are no other baselines for robustness provided. \n\n3. For the adversarial robustness claims, I don't believe that the justification provided in the paper is the necessarily only one. The adversarial attacks are only done on the uncoded image. So, if 'encodings' are robust to these attacks, the network could also be robust. Unless this hypothesis is rejected, the provided theoretical justification and experiments do not exactly match-up.\n\n(writing comments): I felt that the paper could use a better structure with terms like source code defined in a consolidated section. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJxnAMqatB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper provides a very interesting viewpoint for understanding the generalization in deep learning, where the concept of generalization is defined as “the difference between training error and inference error”, and covers the concept of adversarial robustness.  More specifically, \n1. The author treats the deep model as a source code, and provides some theoretic analysis based on the Kolmogorov complexity. The insight drawn from this theory is: finding a better source code is equivalent to minimize a Kolmogorov complexity term given the true source code; as a result, a learned classification function needs to be sufficiently complex to minimize the generalization gap. \n2. The author tries to approximate the normalized information distance and form an effectively computable optimization problem, which suggests that one can use channel codes on input features as additional inputs. \n3. The experiments show that using additional encodings improve robustness in several settings, including in the sense of adversarial robustness. \n\n\nPros: \n1. The writing is pretty clear. \n2. The complexity viewpoint provides more insights for understanding generalization, which is something not covered by learning theory. \n3. The empirical method that the authors proposed is simple, and computationally friendly. \n4. I personally like the way adversarial robustness is covered in this paper, especially when comparing with tons of other adversarial robustness papers. \n\n\nCons: \n1. Can you provide exact reference for the definition of normalized information distance? It is not directly mentioned in (Bennett 1988) through a quick scan. The normalization seems important for the theoretical analysis, so it would be better to explain where this definition comes from more clearly. \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BkldR7lIcB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a theoretical framework for studying the generalization of deep neural networks in a broader sense; i.e.,  generalizing with underrepresented or unrepresented training/test samples. The main idea is to cast the problem of improving generalization as the problem of minimizing the normalized information distance between the learned source code and the true source code, defined using the Kolmogorov complexity. Built upon this framework, the method of using extended encodings of an input sample is presented, which empirically seems to lead to better generalization in the settings of adversarial attack and corruptions.\n\nWhile the idea and the results seem to be appealing, and the concept is novel to the mainstream deep learning community, I suspect that some of the proofs in the paper might not be well grounded. For example, in Equation (3), the authors claim that \"a necessary and sufficient condition ensuring that ... the learned source code C_0 is more general than the learned source code C1 is ...\". However, this is not proved and does not seem obvious to me. Also, in the proof of Theorem 1 in the Appendix, the authors state \"Because a sufficiently high-capacity neural network can memorize its input samples (Zhang et al 2017), the Kolmogorov complexity of the true source code is larger than that of the source code\". This, to me, is more like some intuition or conjecture, rather than rigorous mathematical proof. As a result, I am skeptical about the theoretical claims made in the paper.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is an interesting paper that aims to redefine generalization based on the difference between the training error and the inference error (measured on the empirical sample set), rather than the test error. The authors propose to improve generalization in image classification by augmenting the input with encodings of the image using a source code, and learn this encoding using the compression distance, an approximation of the Kolmogorov complexity. They show that training in this fashion leads to performance that is more robust to corruption and adversarial perturbations that exist in the empirical sample set. 

Reviewers agree on the importance of this topic and the novelty of the approach, but there continue to exist sharp disagreement in the ratings. Most have concerns about the formalism and clarity in the presentation. Especially given that the paper is 10 pages, it should be evaluated against a more rigorous standard, which doesn't appear to be met. I encourage the authors to consider a rewrite with a goal towards clarity for a more general ML audience and resubmit for a future conference.

Decision: Reject