The idea that neural networks may exhibit a bias towards simplicity has a long history. Simplicity bias provides a way to quantify this intuition. It predicts, for a broad class of input-output maps which can describe many systems in science and engineering, that simple outputs are exponentially more likely to occur upon uniform random sampling of inputs than complex outputs are. This simplicity bias behaviour has been observed for systems ranging from the RNA sequence to secondary structure map, to systems of coupled differential equations, to models of plant growth. Deep neural networks can be viewed as a mapping from the space of parameters (the weights) to the space of functions (how inputs get transformed to outputs by the network). We show that this parameter-function map obeys the necessary conditions for simplicity bias, and numerically show that it is hugely biased towards functions with low descriptional complexity. We also demonstrate a Zipf like power-law probability-rank relation. A bias towards simplicity may help explain why neural nets generalize so well. In a recent paper BID4, an inequality inspired by the coding theorem from algorithmic information theory (AIT) BID5, and applicable to computable input-output maps was derived using the following simple procedure. Consider a map f: I → O between N I inputs and N O outputs. The size of the inputs space is parameterized as n, e.g. if the inputs are binary strings, then N I = 2 n. Assuming f and n are given, implement the following simple procedure: first enumerate all 2 n inputs and map them to outputs using f. Then order the outputs by how frequently Preliminary work. Under review by the International Conference on Machine Learning (ICML). Do not distribute. they appear. Using a Shannon-Fano code, one can then describe x with a code of length − log 2 P (x) + O, which therefore upper bounds the Kolmogorov complexity, giving the relation P (x) ≤ 2 −K(x|f,n)+O BID0. The O terms are independent of x (but hard to estimate). Similar bounds can be found in standard works BID5. As pointed out in BID4, if the maps are simple, that is condition 1: K(f) + K(n) K(x) + O holds, then because K(x) ≤ K(x|f, n) + K(f) + K(n) + O, and K(x|f, n) ≤ K(x) + O, it follows that K(x|f, n) ≈ K(x) + O. The problem remains that Kolmogorov complexity is fundamentally uncomputable BID5, and that the O terms are hard to estimate. However, in reference a more pragmatic approach was taken to argue that a bound on the probability P (x) that x obtains upon random sampling of inputs can be approximated as DISPLAYFORM0 whereK(x) is a suitable approximation to the Kolmogorov complexity of x. Here a and b are constants that are independent of x and which can often be determined from some basic information about the map. These constants pick up multiplicative and additive factors in the approximation to K(x) and to the O terms. In addition to the simplicity of the the input-output map f (condition), the map also needs to obey conditions BID1 Redundancy: that the number of inputs N I is much larger than the number of outputs N O, as otherwise P (x) can't vary much; 3) Large systems where N O 0, so that finite size effects don't play a dominant role; 4) Nonlinear: If the map f is linear it won't show bias and 5) Well-behaved: The map should not have a significant fraction of pseudorandom outputs because it is hard to find good approximationsK(x). For example many randomnumber generators produce outputs that appear complex, but in fact have low K(x) because they are generated by a relatively simple algorithms with short descriptions. Some of the steps above may seem rather rough to AIT purists. For example: Can a reasonable approximation to K(x) be found? What about O terms? And, how do you know condition 5) is fulfilled? Notwithstanding these important questions, in reference the simplicity bias bound was tested empirically for a wide range of different maps, ranging from a sequence to RNA secondary 055 056 057 058 059 060 061 062 063 064 065 066 067 068 069 070 071 072 073 074 075 076 077 078 079 080 081 082 083 084 085 086 087 088 089 090 091 092 093 094 095 096 097 098 099 100 101 102 103 104 105 106 107 108 109 Simplicity bias in the parameter-function map of deep neural networks structure map, to a set of coupled differential equations, to L-systems (a model for plant morphology and computer graphics) to a stochastic financial model. In each case the bound works remarkably well: High probability outputs have low complexity, and high complexity outputs have low probability (but not necessarily vice versa). A simple matrix map that allows condition 1 to be directly tested also demonstrates that when the map becomes sufficiently complex, simplicity bias phenomena disappear.this method is that it relies on the assumption of the put x, the upper bound was only a poor approximation,. nd b can generally be estimated with a limited amount text. As long as there are ways to estimate max(K(x)), first order can simply be set to zero. Of course some ay obey them, but we can always simply fix a and b only a small amount of information is needed to fix the e chosen approximate measure of complexity. In this a di↵erent complexity sayK ↵, = ↵C LZ (x) +, then nts a ↵, = a/↵ and b ↵, = b a /↵. In other words, the parameters. Such robustness is a useful property.plexity for di↵erent sized systems. (a) RNA n = 10 and simplest structure does have the largest probability. upper bound, a = 0.23, b = 1.08; (c) RNA n = 80 shows er bound, a = 0.33, b = 6.39. FIG0. Probability that an RNA secondary structure x obtains upon random sampling of length L = 80 sequences versus a Lempel-Ziv measure of the complexity of the structure. The black solid line is the simplicity-bias bound, while the dashed line denotes the bound with the parameter b set to zero. In FIG0 we illustrate an iconic input-output map for RNA, a linear biopolymer that can fold into well-defined sructures due to specific bonding between the four different types of nucleotides ACUG from which its sequences are formed. While the full three-dimensional structure is difficult to predict, the secondary structure, which records which nucleotide binds to which nucleotide, can be efficiently and accurately calculated. This mapping from sequences to secondary structures fulfills the conditions above. Most importantly, the map, which uses the laws of physics to determine the lowest free-energy structure for a given sequence, is independent of the length of the sequences, and so fulfills the simplicity condition. The structures (the outputs x) can be written in terms of a ternary string, and so simple compression algorithms can be used to estimate their complexity. In FIG0, we observe, as expected, that the probability P (x) that a particular secondary structure x is found upon random sampling of sequences is bounded by Eq. as predicted. Similar robust simplicity bies behaviour to that seen in this figure was observed for the other maps. Similar scaling was also observed for this map with a series of other approximations to K(x), suggesting that the precise choice of complexity measure was not critical, as long as it captures some basic essential features. In summary then, the simplicity bias bound works robustly well for a wide range of different maps. The predictions are strong: the probability that an output obtains upon random sampling of inputs should drop (at least) exponentially with linear increases in the descriptional complexity of the output. Nevertheless, it is important to note that while the 5 conditions above are sufficient for the bound to hold, they are not sufficient to guarantee that the map will be biased (and therefore simplicity biased). One can easily construct maps that obey them, but do not show bias. Understanding the conditions ing in biased maps is very much an open area of investigation. The question we will address here is: Can deep learning be re-cast into the language of input-output maps, and if so, do these maps also exhibit the very general phenomenon of simplicity bias?2. The parameter-function map It is not hard to see that the map above obeys condition 1: The shortest description of the map grows slowly with the logarithm of the size of the space of functions (which determines the typical K(x)). Conditions 2-4 are also clearly met. Condition 5 is more complex and requires empirical testing. But given that simplicity bias was observed for such a wide range of maps, our expectation is that it will hold robustly for neural networks also. In order to explore the properties of the parameterfunction map, we consider random neural networks. We put a probability distribution over the space of parameters Θ, and are interested in the distribution over functions induced by this distribution via the parameter-function map of a given neural network. We consider Gaussian and uniform distributions over parameters. In the following, when we say "probability of a function", we imply we 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 Simplicity bias in the parameter-function map of deep neural networks are using a Gaussian or uniform i.i.d. distribution over parameters unless otherwise specified. For a convolutional network with 4 layers and no pooling BID0, we have used the Gaussian process approximation(7; 8) to estimate the probability of different labellings 2 on a random sample of 1000 images from CIFAR10. We used the critical sample ratio (CSR) as a measure of the complexity of the functions BID2. FIG1, depicts the strong correlation between the log probability and CSR consistent with Eq..In FIG7, we also show the values of the log probability for a CNN and a FC network, on a larger sample of 10k images from CIFAR10, MNIST, and fashion-MNIST. This illustrates the large range of orders of magnitude for the probability of different labellings, as well as the negative correlation with increasing label corruption. While label corruption is not a direct measure of descriptional complexity, it is almost certainly the case that increasing label corruption generally corresponds to an increase in measures of Kolmogorov complexity. Direct measurements of simplicity bias are extremely computationally expensive, and so far we have not been able to obtain directly sampled for datasets larger than CIFAR10.To further isolate the phenomenon of simplicity bias in the parameter-function map, and study the effect of us-1 See Appendix A for more details on the architecture 2 See Appendix A.1 for details on the Gaussian process approximation BID2 See Appendix C for more details on complexity measures (a) (b) FIG7. log probability of a labelling on 10k random images on three different datasets, as the fraction of label corruption increases. The probability is computed using the Gaussian process approximation for (a) a CNN with 4 layers and no pooling. (b) a 1 hidden layer FC network. ing different complexity measures, we look at a series of MLPs with 7 Boolean input neurons, 1 Boolean output neuron, and a number of layers of 40 hidden neurons each. We use ReLU activation in all hidden layers. For each such architecture, we sample the parameters i.i.d. according to a Gaussian or uniform distribution. We then count how often individual Boolean functions are obtained, and use the normalized empirical frequencies as estimate of their probability. In FIG2, we plot the probability (in log scale) versus the Lempel-Ziv complexity, which is defined in Appendix C.1. In Appendix C.3, we show similar for other complexity measures, demonstrating that the simplicity bias is robust to the choice of complexity measure, as long as it not too simple (like entropy). The simplicity bias observed in FIG2 very closely resembles that seen for the other maps in.In FIG2 in Appendix C.3, we show the same data as in FIG2, but as a histogram, highlighting that most of the probability mass, when sampling parameters, is close to the upper bound. In addition, in FIG9 in Appendix D, we show the probability versus complexity plots for fully-165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 Simplicity bias in the parameter-function map of deep neural networks connected networks with increasing number of layers, showing that the correlation is similar in all cases, although for deeper networks, the bias is a bit stronger. In our experiments in the previous two sections, we observe that the range of probabilities of functions spans many orders of magnitude. Here we show that for the experiment in Section 4, when we plot the probabilities versus the rank of the function (when ranked by probability), we find that the probabilities asymptotically follow Zipf's law: DISPLAYFORM0 where N O is the total number of functions. This was also observed in for networks of Boolean functions, and in for more general circuits. We formalize our findings for neural networks in the following conjecture:Conjecture 1 (Zipf's law beahviour) The probabilityrank relation of functions for sufficiently overparametrized neural networks follows Zipf's law (Equation 2)By "sufficiently over-parametrized" we mean that the networks are in the regime where the Gaussian process approximation to the distribution over function is a good approximation (which appears to be the case for many cases in practice (11; 8; 12) ). We now explain the experiments we conducted to test this conjecture. In FIG3, we show the probabilities of the functions versus their rank (when ranked by probability), for different choices of parameter distribution. We observe that for all the parameter distributions the probability-rank plot appears to approach Zipf's law. To determine the parameter N O in Zipf's law, we checked that this architecture can produce almost all Boolean functions of 7 inputs, by finding that it could fit all the functions in a sample of 1000 random Boolean functions. We thus used N O = 2 DISPLAYFORM1 in the Zipf's law curve in FIG3, finding excellent agreement with no free parameters. These imply in particular that the distribution is extremely biased, with probabilities spanning a huge range of orders of magnitudes. Note that the mean P (x) over all functions is 1/N O ≈ 3 × 10 −39, so that in our plots we are only showing a tiny fraction of functions for which P (x) is orders of magnitude larger than the mean. We can't reliably obtain a probability-rank plot for the experiments we did on CIFAR10, because our sampling of the space of functions is much sparser in this case. How- are weight and bias variances, respectively, where n is the number of hidden neurons ever, the probabilities still span a huge range of orders of magnitude, as seen in FIG1. In fact, the range of orders of magnitude appears to scale with m, the size of the input space. This is consistent with a probability-rank following Zipf's law. The fact that neural networks are biased towards simple solutions has been conjectured to be the main reason they generalize (4; 3; 12). Here we have explored a form of simplicity bias encoded in the parameter-function map. It turns out that this bias is enough to guarantee good generalization, as was shown in via a PAC-Bayesian formalism. In FIG0 in Appendix B, we show the PACBayesian bounds versus the true generalization error they obtained, finding that the bounds are not only nonvacuous but follow the trends of the true error closely. Simplicity bias also provides a lens through which to naturally understand various phenomena observed in deep networks, for example, that the number of parameters does not strongly affect generalization. We have provided evidence that neural networks exhibit simplicity bias. The fact that the phenomena observed are remarkably similar to those of a wide range of maps from science and engineering BID4 suggests that this behaviour is general, and will hold for many neural network architectures. It would be interesting to test this claim for larger systems, which will require new sampling techniques, and to derive analytic arguments for a bias towards simplicity, as done in BID12. 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 Simplicity bias in the parameter-function map of deep neural In the main experiments of the paper we used two classes of architectures. Here we describe them in more detail.• Fully connected networks (FCs), with varying number of layers. The size of the hidden layers was the same as the input dimension, and the nonlinearity was ReLU. The last layer was a single Softmax neuron. We used default Keras settings for initialization (Glorot uniform).• Convolutional neural networks (CNNs), with varying number of layers. The number of filters was 200, and the nonlinearity was ReLU. The last layer was a fully connected single Softmax neuron. The filter sizes alternated between and BID4 BID4, and the padding between SAME and VALID, the strides were 1 (same default settings as in the code for FORMULA0). We used default Keras settings for initialization (Glorot uniform). In recent work ((2; 3; 1; 4)), it was shown that infinitely-wide neural networks (including convolutional and residual networks) are equivalent to Gaussian processes. This means that if the parameters are distributed i.i.d. (for instance with a Gaussian with diagonal covariance), then the (real-valued) outputs of the neural network, corresponding to any finite set of inputs, are jointly distributed with a Gaussian distribution. More precisely, assume the i.i.d. distribution over parameters isP with zero mean, then for a set of n inputs (x 1, ..., x n), DISPLAYFORM0 whereỹ = (ỹ 1, ...,ỹ n). The entries of the covariance matrix K are given by the kernel function k as DISPLAYFORM1 The kernel function depends on the choice of architecture, and properties ofP, in particular the weight variance σ 2 w /n (where n is the size of the input to the layer) and the bias variance σ 2 b. The kernel for fully connected ReLU networks has a well known analytical form known as the arccosine kernel , while for convolutional and residual networks it can be efficiently computed BID0.The main quantity in the PAC-Bayes theorem, P (U), is precisely the probability of a given set of output labels for the set of instances in the training set, also known as marginal likelihood, a connection explored in recent work ((6; 7)). For binary classification, these labels are binary, and are related to the real-valued outputs of the network via a nonlinear function such as a step functionwhich we denote σ. Then, for a training set U = {(x 1, y 1),..., (x m, y m)}, DISPLAYFORM2 This distribution no longer has a Gaussian form because of the output nonlinearity σ. We will discuss approximations to deal with this in the following. There is also the more fundamental issue of neural networks not being infinitely-wide in practice. However, the Gaussian process limit has been found to be a good approximation for nets with reasonable widths (3; 4; 8).In order to calculate P (U) using the GPs, we use the expectation-propagation (EP) approximation, implemented in, which is more accurate than the Laplacian approximation (see BID9 for a description and comparison of the algorithms).In, the authors compare the two approximations and find that EP appears to give better approximations. One of the key steps to practical application of the simplicity bias framework of Dingle et al. in FORMULA0 is the identification of a suitable complexity measureK(x) which mimics aspects of the (uncomputable) Kolmogorov complexity K(x) for the problem being studied. It was shown for the maps in that several different complexity measures all generated the same qualitative simplicity bias behaviour: DISPLAYFORM0 1 We use the code from to compute the kernel for convolutional networks but with different values of a and b depending on the complexity measure and of course depending on the map, but independent of output x. Showing that the same qualitative obtain for different complexity measures is sign of robustness for simplicity bias. Below we list a number of different descriptional complexity measures which we used, to extend the experiments in Section 4 in the main text. Lempel-Ziv complexity (LZ complexity for short). The Boolean functions studied in the main text can be written as binary strings, which makes it possible to use measures of complexity based on finding regularities in binary strings. One of the best is Lempel-Ziv complexity, based on the Lempel-Ziv compression algorithm. It has many nice properties, like asymptotic optimality, and being asymptotically equal to the Kolmogorov complexity for an ergodic source. We use the variation of Lempel-Ziv complexity from FORMULA0 which is based on the 1976 Lempel Ziv algorithm (FORMULA0): DISPLAYFORM0 where n is the length of the binary string, and N w (x 1 ...x n) is the number of words in the Lempel-Ziv "dictionary" when it compresses output x. The symmetrization makes the measure more fine-grained, and the log 2 (n) factor as well as the value for the simplest strings ensures that they scale as expected for Kolmogorov complexity. This complexity measure is the primary one used in the main text. We note that the binary string representation depends on the order in which inputs are listed to construct it, which is not a feature of the function itself. This may affect the LZ complexity, although for low-complexity input orderings (we use numerical ordering of the binary inputs), it has a negligible effect, so that K(x) will be very close to the Kolmogorov complexity of the function. Entropy. A fundamental, though weak, measure of complexity is the entropy. For a given binary string this is defined DISPLAYFORM1 N, where n 0 is the number of zeros in the string, and n 1 is the number of ones, and 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 DISPLAYFORM2 This measure is close to 1 when the number of ones and zeros is similar, and is close to 0 when the string is mostly ones, or mostly zeros. Entropy and K LZ (x) are compared in FIG1, and in more detail in supplementary note 7 (and supplementary information figure 1) of reference BID10. They correlate, in the sense that low entropy S(x) means low K LZ (x), but it is also possible to have Large entropy but low K LZ (x), for example for a string such as 10101010.... Boolean expression complexity. Boolean functions can be compressed by finding simpler ways to represent them. We used the standard SciPy implementation of the Quine-McCluskey algorithm to minimize the Boolean function into a small sum of products form, and then defined the number of operations in the ing Boolean expression as a Boolean complexity measure. Generalization complexity. L. Franco et al. have introduced a complexity measure for Boolean functions, designed to capture how difficult the function is to learn and generalize (FORMULA0), which was used to empirically find that simple functions generalize better in a neural network (FORMULA0). The measure consists of a sum of terms, each measuring the average over all inputs fraction of neighbours which change the output. The first term considers neighbours at Hamming distance of 1, the second at Hamming distance of 2 and so on. The first term is also known (up to a normalization constant) as average sensitivity (FORMULA0). The terms in the series have also been called "generalized robustness" in the evolutionary theory literature (FORMULA0). Here we use the first two terms, so the measure is: DISPLAYFORM3 where Nei i (x) is all neighbours of x at Hamming distance i. Critical sample ratio. A measure of the complexity of a function was introduced in BID16 to explore the dependence of generalization with complexity. In general, it is defined with respect to a sample of inputs as the fraction of those samples which are critical samples, defined to be an input such that there is another input within a ball of radius r, producing a different output (for discrete outputs). Here, we define it as the fraction of all inputs, that have another input at Hamming distance 1, producing a different output. In FIG1, we compare the different complexity measures against one another. We also plot the frequency of each complexity; generally more functions are found with higher complexity. In FIG7 we show how the probability versus complexity plots look for other complexity measures. The behaviour is similar to that seen for the LZ complexity measure in FIG0 of the main text. In FIG3 we show probability versus LZ complexity plots for other choices of parameter distributions. In FIG2, we show a histogram of the functions in the log probability -complexity plane. The histogram counts are weighted by the probability of the function, so that the total weight is proportional to the probability of obtaining a function in a particular bin, when sampling the parameters. In FIG9 we show the effect of the number of layers on the bias (for feedforward neural networks with 40 neurons per layer). The left figures show the probability of individual functions versus the complexity. The right figure shows the histogram of complexities, weighted by the probability by which the function appeared in the sample of parameters. 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 parameters, for a network of shape BID6 40, 40, BID0. Points with a frequency of 10 −8 are removed for clarity because these suffer from finite-size effects (see Appendix E). The measures of complexity are described in Appendix C. 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 FIG2. Histogram of functions in the probability versus Lempel-Ziv complexity plane, weighted according to their probability. Probabilities are estimated from a sample of 10 8 parameters, for a network of shape BID6 40, 40, BID0 The histograms therefore show the distribution over complexities when randomly sampling parameters BID1 We can see that between the 0 layer perceptron and the 2 layer network there is an increased number of higher complexity functions. This is most likely because of the increasing expressivity of the network. For 2 layers and above, the expressivity does not significantly change, and instead, we observe a shift of the distribution towards lower complexity. E. Finite-size effects for sampling probabilitySince for a sample of size N the minimum estimated probability is 1/N, many of the low-probability samples that arise just once may in fact have a much lower probability than suggested. See Figure 7), for an illustration of how this finite-size sampling effect manifests with changing sample size N. For this reason, these points are typically removed from plots. 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549
A very strong bias towards simple outpouts is observed in many simple input-ouput maps. The parameter-function map of deep networks is found to be biased in the same way.