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(1), which therefore upper bounds the Kolmogorov complexity, giving the relation P (x) ≤ 2 −K(x|f,n)+O BID0 . The O(1) 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(1) holds, then because K(x) ≤ K(x|f, n) + K(f ) + K(n) + O(1), and K(x|f, n) ≤ K(x) + O(1), it follows that K(x|f, n) ≈ K(x) + O(1). The problem remains that Kolmogorov complexity is fundamentally uncomputable BID5 , and that the O(1) terms are hard to estimate. However, in reference (5) 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(1) terms.In addition to the simplicity of the the input-output map f (condition (1)), 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(1) terms? And, how do you know condition 5) is fulfilled? Notwithstanding these important questions, in reference (5) the simplicity bias bound (1) 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 (1), 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 (1). 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. (1) as predicted. Similar robust simplicity bies behaviour to that seen in this figure was observed for the other maps.Similar scaling (5) 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 (1) 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 (1) 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 resulting 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. 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
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.
{"src": "scitldr-AIC_train", "paper_id": "r1l9jy39p4"}