Neural networks are a priori biased towards Boolean functions with low entropy
Authors: Chris Mingard
Joar Skalse
Guillermo Valle-Pérez
David Martínez-Rubio
Vladimir Mikulik
Ard A. Louis
Venue:  (2020)
Keywords: class imbalance
perceptron
inductive bias
simplicity bias
initialization

Abstract: Understanding the inductive bias of neural networks is critical to explaining their ability to generalise.  Here,  
for one of the simplest neural networks -- a single-layer perceptron with $n$ input neurons,  one output neuron, and no threshold bias term -- we prove that upon random initialisation of weights, the a priori probability  $P(t)$ that it represents a Boolean function that classifies $t$ points in $\{0,1\}^n$ as $1$ has a remarkably simple form: $
P(t) = 2^{-n} \,\, {\rm for} \,\, 0\leq t < 2^n$.
Since a perceptron can express far fewer Boolean functions with small or large values of $t$ (low "entropy") than with intermediate values of $t$ (high "entropy") there is, on average, a strong intrinsic a-priori bias towards individual functions with low entropy. Furthermore, within a class of functions with fixed $t$, we often observe a further intrinsic bias towards functions of lower complexity.
Finally, we prove that, regardless of the distribution of inputs, the bias towards low entropy becomes monotonically stronger upon adding ReLU layers, and empirically show that increasing the variance of the bias term has a similar effect.

Under review as a conference paper at ICLR 2020
NEURAL NETWORKS ARE a priori BIASED TOWARDS BOOLEAN FUNCTIONS WITH LOW ENTROPY
Anonymous authors Paper under double-blind review
ABSTRACT
Understanding the inductive bias of neural networks is critical to explaining their ability to generalise. Here, for one of the simplest neural networks single-layer perceptron with n input neurons, one output neuron, and no threshold bias term we prove that upon random initialisation of weights, the a priori probability P()) that it represents Boolean function that classifies points in {0, 1 as 1 has a remarkably simple form: P(t) 2- " for 0 t 2".
Since a perceptron can express far fewer Boolean functions with small or large values of & (low "entropy"") than with intermediate values of (high "entropy") there is, on average, a strong intrinsic a-priori bias towards individual functions with low entropy. Furthermore, within class of functions with fixed t, often observe further intrinsic bias towards functions of lower complexity. Finally, we prove that, regardless of the distribution of inputs, the bias towards low entropy becomes monotonically stronger upon adding ReLU layers, and empirically show that increasing the variance of the bias term has a similar effect.
1 INTRODUCTION
In order to generalise beyond training data, learning algorithms need some sort of inductive bias. The particular form of the inductive bias dictates the performance of the algorithm. For one of the most important machine learning techniques, deep neural networks (DNNs) {LeCun et al. 2015), sources of inductive bias can include the architecture of the networks, e.g. the number layers, how they are connected, say as a fully connected network (FCN) or as a convolutional neural net (CNN), and the type of optimisation algorithm used, e.g. stochastic gradient descent (SGD) versus full gradient descent (GD). Many further methods such as dropout (Srivastava et al. 2014), weight decay (Krogh Hertz 1992) and early stopping (Morgan & Bourlard 1990) have been proposed as techniques to improve the inductive bias towards desired solutions that generalise well. What is particularly surprising about DNNs is that they are highly expressive and work well in the heavily overparameterised regime where traditional learning theory would predict poor generalisation due to overfitting (Zhang et al.] 2016). DNNs must therefore have a strong intrinsic bias that allows for good generalisation, in spite of being in the overparameterised regime.
Here we study the intrinsic bias of the parameter-function map for neural networks, defined in (Valle- Pérez et al. 2018) as the map between set of parameters and the function that the neural net- work represents. In particular, we define the a-priori probability P(f) of DNN as the probability that a particular function is produced upon random sampling (or initialisation) of the weight and threshold bias parameters. The prior at initialization, P(f). should inform the inductive bias of neural networks, as long as SGD approximates Bayesian inference with Pff) as prior sufficiently well Valle-Pérez et al. (2018). We explain this connection further, and give some ev- idence supporting this behavior of SGD, in Appendix [.] This supports the idea studying neural networks with random parameters Poole et al. (2016); Lee et al. (2018); Schoenholz et al. (2017); Glrriga-Alonso et al. (2018); Novak et al. (2018) is not just relevant to find good initializations for optimization, but also understand their generalization.
A naive null-model for P(f) might suggest that without further information, one should expect that
all functions are equally likely. However, recent very general arguments (Dingle et al., 2018) based on the coding theorem from Algorithmic Information Theory (AIT) (Li et al., 2008) have instead suggested that for wide range of maps M that obey number of conditions such being simple

---

Under review as a conference paper at ICLR 2020
(they have low Kolmogorov complexity (MM) and redundancy (multiple inputs map to the same output) then if they are sufficiently biased, they will be exponentially biased towards outputs of low Kolmogorov complexity. The Enrameteer-unction map of neural networks satisfies these conditions, and it was found empirically (Valle-Pérez et al. 2018) that, as predicted in (Dingle et al. (2018), the probability P(f) of obtaining a function / upon random sampling of parameter weights satisfies the following simplicity-bi bound
P(f) S (b)())))))
(1)
where (ff) is a computable approximation of the true Kolmogorov complexity K Kf)), and a and b are constants that depend on the network, but not on the functions.
is widely expected that real world data is highly structured, and so has a relatively low Kolmogorov complexity (Hinton & Van Camp, 1993 Schmidhuber 1997). The simplicity bias described above may therefore be an important source of the inductive bias that allows DNNs to generalise so well (and not overfit) in the highly over- paraameetttee regime (Valle-Pérez et al., 2018).
Nevertheless, this bound has limitations. Firstly, the only rigorously proven result is for the true Kol- mogorov complexity version of the bound in the case of large enough K(f). Although has been found to work remarkably well for small systems and computable approximations to Kolmogorov complexity (Valle-Pérez et al. 2018 Dingle et al. 2018), this success is not yet fully understood theoretically. Secondly, it does not explain why models like DNNs are biased; it only explains that, they are biased, they should be biased towards simplicity. Also, the AIT bound is very general it predicts probability P(f) that depends mainly the function, and only weakly on the net- work. It may therefore not capture some variations in the bias that are due to details of the network architecture, and which may be important for practical applications.
For these reasons it is of interest to obtain a finer quantitative understanding of the simplicity bias of neural networks. Some work has been done in this direction, showing that infinitely wide neural networks are biased towards functions which are robust to changes in the input (De Palma et al.) 2018). showing that "flatness" connected to function smoothness (Wu et al. (016)) or arguing that low Fourier frequencies are learned first by a ReLU neural network (Rahaman et al. 2018 Yang & Salman| 2019). All of these papers take some notion of "smoothness" as tractable proxy for the complexity of function. One generally expects smoother functions to be simpler, although this clearly a very rough measure of the Kolmogorov complexity.
SUMMARY OF KEY RESULTS
In this paper we study how likely different Boolean functions, defined as f f0, + 1),1), are obtained upon randomly chosen weights of neural networks. Our key results are aimed at flesh- ing out with more precision and rigour what the inductive biases of (very) simple neural networks are, and how they arise For this, we study the prior distribution over functions P(J), upon random initialization of the parameters, which reflects the inductive bias of training algorithms that approx- imate Bayesian inference (see Appendix L for detailed explanation, and data how well SGD follows this behaviour). We focus our study on a notion of complexity, namely the "entropy." H of Boolean function f, defined as the binary entropy of the fraction of possible inputs to f that maps to 1. This quantity essentially measures the amount of class imbalance of the function, and is complementary previous works studying notions of smoothness as a proxy for complexity.
1. In Section 4 we study simple perceptron with no threshold bias term, and with weights w sampled from a distribution which is symmetric under reflections along the coordinate axes. Let the random variable T correspond to the number of points in {0, 13" which that fall above the decision boundary of the network (i.e. T= E {0, 13"h : (w, x) > 0)) upon i.i.d. random initialisation of the weights. We prove that T is distributed uniformly, i.e. P(T = t) = 2- for 0 S < 2n. Let F, be the set of all functions with T t that the perceptron can produce and let [F,]] be its size (cf. Definition (.44.. We expect [F.] for ~ 2n (high entropy) to be (much) larger than [F, for extreme values of t (low entropy). The average probability of obtaining a particular function f which maps t inputs to 1 is 2 2- 2-"/[F,]. The perceptron therefore shows a strong bias towards functions with low entropy, in the sense that individual functions with low entropy have, on average, higher probability than individual functions with high entropy.
2

---

Under review as a conference paper at ICLR 2020
2. In Section 4.3
show that within the sets Ft, there is further bias, and in some cases this is clearly towards simple functions which correlates with Lempel- Ziv complexity [emmpl
& Ziv
1976 Dingle et al. 2018), predicted in (Valle-Pérez al. 2018
3. In Section 4.4 we show that adding threshold bias term to perceptron significantly
increases the bias towards low entropy.
4. In Section 5.1 we provide new expressivity bound for Boolean functions: DNNs with input size n, Thidden layers each with width n 2 + 1 and single output neuron can express all 22" Boolean functions over n variables.
5. In Section 5.2 we generalise our results neural networks with multiple layers, proving (in the -iitt limit) that the bias towards low entropy increases with the number of ReL.U-activated layers.
In Appendix[] we also show some empirical evidence that the results derived in this paper seem to generalize beyond the assumptions of our theoretical analysis, to more complicated data distributions (MNIST, CIFAR) and architectures (CNNs). Finally, Appendix M we show preliminary results on the effect of entropy biases in P(f) learning dlass-ibalaanee data.
DEFINITIONS, TERMINOLOGY, AND NOTATION
Definition 3.1 (DNNs). Fully connected feed-forward neural networks with activations and single output neuron form a parameterised function family f(x) on inputs x E R". This can be defined recursively, for L hidden layers for S I,, as
[(x) 1 11. h(+1) = (1 bb,
h() waz bo
where 1(X) is the Heaviside step function defined as if X > O and O otherwise, and is activation function that acts element-wise. The wi E Tg are the weights, and by R844 are the threshold bias weights at layer I, where is the number of hidden neurons in the 1-th layer. n L++ is the number of outputs (1 in this paper), and no is the dimension of the inputs (which we will n).
also refer
We will refer to the whole set of parameters (wy and b, < L) 0. In the case of perceptrons we use (1) o (w. x) + b) to specify network. We define the farameter-function map as in Valle-Pérez et al. 2018 below.
Definition 3.2 (Parameter-function map). Consider a parameterised supervised model, and let the input space be X. and the output space be Y. The space of functions the model can express F A If the model has real valued parameters, taking values within a set θ C RP, the parameter function map M is defined
M 0 F 0 + So
where So is the function corresponding to parameters 0.
In this paper are interested in the Boolean functions that neural networks express. We consider
the 0-1 Boolean hypercube {0, 1}" as the input domain.
Definition 3.3. The function T(f) defined as the number of points in the hypercube {0, 1) that are mapped to by the action of neural network f.
For example, for perceptron this function defined as,
T(f) T(w,b) = Σ
1((x, w) b).
(E(0.1)
We will sometimes use T(w, b) if the neural network is perceptron.
3

---

Under review as a conference paper at ICLR 2020
Definition 3.4 (F, and P(t)). We define the set Fi be the set of functions expressible by some model M (e.g. a perceptron, a neural network) which all have the same value Tff),
Fr E
=t}
where FM is the set of all functions expressible by M. Given probability measure P on the weights 0, we define the probability measure
=t)= P(0: E.)
We can also define T() and P(T= = in the natural way for sets of input points other than 1)" the context making clear what definition is being used.
Definition 3.5. The entropy (f) of a Boolean functionn f (0, {0, 13 is defined H(f) -p P - p) log2 (1 - p), where p T2/2". It is the binary entropy of the fraction p of possible inputs to f that maps to 1 or equivalently, the binary entropy of the fraction of I's in the right-hand column of the truth table of f.
Definition 3.6. We define the Boolean complexity Booot (f) of a function f as the number of binary connectives the shortest Boolean formula that expresses f.
Note that Boolean complexity can be defined in other ways as well. For example, KBool( (f) is sometimes defined as the number of connectives (rather than binary connectives) in the shortest formula that expresses f. or as the depth the most shallow formula that expresses f. These definitions tend to give similar values for the complexity of a given function, and so they are largely interchangeable in most contexts. We use the definition above because makes our calculations easier.
INTRINSIC BIAS IN A PERCEPTRON'S PARAMETER-FUNCTION MAP
In this section we study the parameter-function map of the perceptron (Rosenblati 1958). in many ways the simplest neural network. While it famously cannot express many Boolean functions including XOR - it remains an important model system. Moreover, many DNN architectures include layers perceptrons, so understanding this very basic architecture may provide important insight into the more complex neural networks used today.
4.1 ENTROPY BIAS IN SIMPLE PERCEPTRON WITH b (NO THRESHOLD BIAS TERM)
Here consider perceptrons fo 1(w, x) b) without threshold bias terms, i.e. d 0.
The following theorem shows that under certain conditions on the weight distribution, a perceptron with threshold bias has a uniform P(0 T(Jo) t). The class of weight distributions includes the commonly used isotropic multivariate Gaussian with zero mean, a uniform distribution on a
centred cuboid, and many other distributions. The full proof of the theorem is in Appendix A
Theorem 4.1. For perceptron fe with b and weights w sampled from a distribution which symmetric under reflections along the coordinate axes, the probability measure P(O : :T(f)) = t) is given by
-22- 2- JOSI<2" 2
P(0 : T(fo) = 1 otherwise
Proof sketch. We consider the sampling of the normal vector w as two-step process: we first sample the absolute values of the elements, giving us vector Wpus with positive elements, and then we sample the signs the elements. Our assumption on the probability distribution implies that each of the 2n sign assignments is equally probable, each happening with probability 2-n, The key of the proof is to show that for any Wposs each of the sign assignments gives a distinct value of T' (and because there are 2" possible sign assignments, for any value of T. there is exactly one sign assignment resulting in a normal vector with that value of T).. This implies that, provided all sign assignments of any upas equally likely, the distribution on 7' is uniform.
4

---

Under review as a conference paper at ICLR 2020
A consequence of Theorem 4.1 is that the average probability of the perceptron producing partic- ular function f with T(f) = t is given by
(P()) 2 |Fr
(3)
where F, denotes the set of Boolean functions that the perceptron can express which satisfy T(f) t, and (-)2 denotes the average (under uniform measure) over all functions f E Ft.
=
We expect [IFr] to be much smaller for more extreme values of t, as there are fewer distinct possible functions with extreme values of t. This would imply a bias towards low entropy functions. By way of an example, [FF) = 1 and [F = n (since the only Boolean functions f perceptron can have (x) = for single one-hot x E {0, 1)"), implying that express which satisfy T(f) 2-m/n (P())) = 2 and
Nevertheless, the probability of functions within a set FF, is unlikely to be uniform. We find that, in contrast to the overall entropy bias, which is independent of the shape of the distribution (as long as it satisfies the right symmetry conditions), the probability P(f) of obtaining function f within set F,, can depend on distribution shape. Nevertheless, for a given distribution shape, the probabilities P(f) are independent of scale of the shape, e.g. they are independent of the variance of the Gaussian, or the width of the uniform distribution. This is because the function is invariant under scaling all weights by the same factor (true only in the case of no threshold bias). We will address the probabilities of functions within given F, further in Section
4.2 SIMPLICITY BIAS OF THE b O PERCEPTRON
The entropy bias of Theorem 4.1 entails an overall bias towards low Boolean complexity. In Theo- rem B.1 in Appendix we show that the Boolean complexity of a function f is bounded by]]
Kooo (f) < 2 x n x min()()), - T())-
(4)
Using Theorem and Equation 4 have that the probability that randomly initialised per- ceptron expresses a function f of Boolean complexity & or greater is upper bounded by
k x
2
x2
k
P(K (f) 2 k) <
=
(5)
xxn n
2 x
Uniformly sampling functions would result in Poo (f) 2 k) ~ 1- which for intermediate
A is much larger than Equation 5 Thus from entropy bias alone, see that the perceptron is much more likely to produce simple functions than complex functions: it has an inductive bias towards simplicity. This derivation is complementary
the AIT arguments from simplicity bias (Dingle jet al., 2018; Valle-Pérez et al.] 20088), and has the advantage that it also proves that bias exists, whereas AlT-based simplicity bias arguments presuppose bias.
To empirically study the inductive bias of the perceptron with b = O. we sampled over many random initialisations with weights drawn from Gaussian uniform distributions and input size 7. As can be seen in Figure Ia and Figure Ib the probability P(f) that function f obtains varies over many orders of magnitude. Moreover, there is a clear simplicity bias upper bound on this probability, which, as predicted by Eq. 1 decreases with increasing Lempel-Ziv complexity (Kiz (using a version from (Diglle et al.,, 2018) applied to the Boolean functions represented as strings of bits, see Appendix E Similar behaviour was observed in (Valle-Pérez et al. 2018) for FCN network. Moreover was also shown there that Lempel-Ziv complexity for these Boolean functions correlates with approximations to the Boolean complexity K A one-layer neural network ( (Figure Icp shows stronger bias than the perceptron, which may be expected because the former has a much larger expressivity, A rough estimate of the slope in Eq. [from (Dingle et al. 2018 suggests that log2 (No) (No)/may) (K (f)) where O is the set of all Boolean functions the model can produce, and
feC
No is the number of such functions. The maximum K()) may not differ that much between the one layer network and the perceptron, but No will be much larger in former than in the latter.
In Appendix [ we also show rank plots for the networks from Figure 1. Interestingly, at larger rank, they all show Zipf like power-law decay, which can be used to estimate No. the total number of
A tighter bound is given in Theorem B.2 but this bound lacks any obvious closed form expression.
5

---

Under review as a conference paper at ICLR 2020
Boolean functions the network can express. We also note that the rank plots for the perceptron with b = 0 with Gaussian or uniform distributions of weights are nearly indistinguishable, which may be because the overall rank plot is being mainly determined by the entropy bias.
10a
10
109
Probabiiity
10-7-
Probability
10
Probability
10
10-4-
10
10
10-4
-4
10
10:4-
0
50
100
150
50
100
150
50
100
150
Kiz
Kiz
Kzz
(a) Perceptron: Gaussian weights
(b) Perceptron: uniform weights.
(c) layer NN
Figure 1: Probability P(f) that a function obtains upon random choice of parameters versus Lempel Ziv complexity (f) for (a) an n = 7 perceptron with b = and weights sampled from a perceptron with b 0 and weights sampled from uniform distribution centred at 0 and (c) 1-hidden layer neural network (with 64 neurons in the hidden layer). Weights w and the threshold bias terms are sampled from tromA((0, A(0 1). For all cases 10 samples were taken and frequencies less than 2 were eliminated to reduce finite sampling effects. We present the graphs with the same scale for ease of comparison.
Gaussian distributions,
(b) an n
4.3 BIAS WITHIN F,
In Figure 2 we compare a rank plot for all functions expressed by an n = 7 perceptron with to the rank plots for functions with T(f) 47 and T(f) 64. To define the rank, order the functions by decreasing probability, and then the rank of a function f is the index of f under this ordering (so the most probable function has rank the second rank 2 and on). The highest probability functions in Fs1 have higher probability than the highest in F17 because the former allows for simpler functions (such as 0101.., but for both sets, the maximum probability is still considerably lower than the maximum probability functions overall.
In Appendix E present further empirical data that suggests that these probabilities are bounded above by Lempel-Zi Ziv complexity (in agreement with (Valle-Péree et al.] 2018)). However, in con- trast to Theorem 4.1 which independent of the parameter distribution (as long as they are symmet- ric), the distributions within F, are different for the Gaussian and uniform parameter distributions, with the latter showing less simplicity bias within a class of fixed (see Appendix E.
10a
10a
10a
P
Probability
10
Probabiltty
10:2-
Proability
20
10-1
10-4
20-1
10-4
10-6
10-4
10
10.8
10
10a
10a
10a
10a
10P
102
10a
10a
10a
10a
rank
rank
(a) All functions
(b) T(f) 47
(c) T(f) = 64
Figure 2: Probability P(J) vs rank for functions for perceptron with n 7, 0 0, and weights sampled from independent Gaussian distributions. In Figures 2b and 2c the functions are ranked within their respective F,. The seven highest probability functions in Figure 2c are f 0101... and equivalent functions obtained by permuting the input dimensions - note that these are very simple functions (simpler than the simplest functions that satisfy T(f) 47).

---

Under review as a conference paper at ICLR 2020
In Appendix F. give further arguments for simplicity bias, based the set of constraints that needs to be satisfied to specify function. Every function f can be specified by a minimal set of linear conditions the weight vector of the perceptron, which correspond to the boundaries of the cone in weight space producing f- The Kolmogorov complexity of conditions should be close to that of the functions they produce they are related to the functions in one-to-one fashion, via a simple procedure. In Appendix [ we focus on conditions which involve more than two weights, and show that within each Ff there exists one function with as few as 1 such conditions, and that 2 such conditions. We also compute the set of necessary
there exists function with as many conditions (up permutations of the axes) explicitly for functions with small t, and find that the range in the number and complexity of the conditions appears to grow with 4, in agreement, with what we observe Figure 2 for the range of complexities. More generally, we find that complex functions typically need more conditions than simple functions do. Intuitively, the more conditions needed to specify a function, the smaller the volume of parameters that can generate the function, so the lower its a-priori probability.
4.4 EFFECT OF b (THE THRESHOLD BIAS TERM) ON P(t)
We next study the behaviour of the perceptron when we include the threshold bias term b, sampled from (00 ob). while still initialising the weights from A/(,, (O, 1). as in Section 4.1 We present results for n = 7 in Figure 3 Interestingly, for infinitesimal σb P(T = 0) is less than for b = 0 (See Appendix C.. but then for increasing σ rapidly grows larger than 1 1/2" and in the limit of large a asymptotes to 1/2 (see Figure 3b). It's not hard to see where this asymptotic behaviour comes from, a large positive or negative means all inputs are mapped to true (I) or false (0) respectively.
0.5
0.0001
10-1
0.2
Probability
1
Probability
0.3
0.2
10-2
0.1
0.0
0
20
40
60
80
100
120
15
(a) P(t) at selected values of as
(b) P(t=0)
Figure 3: Effect of adding bias term sampled from (O, o²) perceptron with weights sampled
from \O0 1). (a) Increasing σb increases the bias against entropy, and with particular strong bias
towards 0 and 2". (b) P(t 0) increases with ar and asymptotes 1/2 in the limit σb + 00.
ENTROPY BIAS IN MULTI-LAYER NEURAL NETWORKS
We next extend results from Section 4 to multi-layer neural networks, with the aim to comment on behaviour P(T = t) as we add hidden layers with ReLU activations.
To study the bias in the parameter-function map of neural networks, it is important to first understand the expressivity of the networks. Section 5.1 we produce a (loose) upper bound on the minimum size of network with ReLU activations and layers that is maximally expressive over Boolean functions. We comment on how sufficiently large expressivity implies a larger bias towards low entropy for models with similarly shaped distribution over T (when compared to the perceptron).
In Section 5.2 we prove, in the limit of infinite width, that adding ReLU activated layers causes the moments of PTT = t) increase. This entails lower expected entropy for neural networks with more hidden layers. We empirically observe that the distribution T becomes convex (with input (0, 1 )) with the addition of ReL.U activated layers for neural networks with finite width.

---

Under review as a conference paper at ICLR 2020
5.1 EXPRESSIVITY CONDITIONS FOR DNNS
We provide upper bounds on the minimum size of a DNNs that can model all Boolean functions. We use the notation (no: , ..,,.....,,,.................... (1,1)) denote neural network with ReLU activations and of the form given in Definition [31]
Lemma 5.1. A neural network with layer sizes (n, 2n- .1), threshold bias terms, and ReLU activa- tions can express all Boolean functions over n. variables (also found in Raj 2018)). See Appendix G for proof.
Lemma 5.2. A neural network with I hidden layers, layer sizes (n, (n + 2--21/1 1)...., (n +
2 1), 1), threshold bias terms, and ReLU activations can express all Boolean functions over variables. See Appendix[Giy proof.
Note that neither of these bounds are (known to be) tight. Lemma 5. says that a network with one hidden layer of size 2n can express all Boolean functions over n variables. We know that a perceptron with n input neurons (and a threshold bias term) can express at most 2n Boolean func- tions ((Anthony] 2001), Theorem 4.3), which is significantly less than the total number of Boolean functions over n variables, which is 22".. Hence there is a very large number of Boolean functions that the network with (sufficiently wide) hidden layer express, but the perceptron cannot. The vast majority of these functions have high entropy (as almost all Boolean functions do). Moreover, observe that the measure P(T L) is convex in the case of the more expressive neural net- works, as discussed in section Section 5.2 This suggests that the networks with hidden layers have much stronger relative bias towards low entropy functions than the perceptron does, which is also consistent with the stronger simplicity bias found in Figure
We further observe from Lemma 5.2 that the number of neurons can be kept constant and spread over multiple layers without loss of expressivity for Boolean classifier (provided the neurons are evenly spread across the layers).
5.2 How MULTIPLE LAYERS AFFECT THE BIAS
We next consider the effect of addition of ReLU activated layers on the distribution P()). Of course adding even just one layer hugely increases expressivity over a perceptron. Therefore, even the distribution of P(t) would not change, the average probability of functions in given F, could drop significantly due to the increase in expressivity.
convex when more ReLU- activated hidden layers are added, see Figure [4] The distribution appears to be monotone on either side of 2 and relatively flat in the middle, even with the addition of 8 intermediate layers] In particular, we show in Figure 4 that for large number of layers, or large os, the probabilities for P(1 0) (and by symmetry, in the infinite width limit, also P(L = 2")) each asymptotically reach 2. and thus take up the vast majority of the probability weight.
However, observe that for inputs 10, P(t) becomes
We now prove some properties the distribution Pt) for DNNs with several layers.
Lemma 5.3. The probability distribution on T for inputs in {0, 13" of a nearal network with linear activations and i.i.d. initialisation of the weights is independent of the number of layers and the layer widths, and is equal to the distribution of perceptron. See A proof.
While it is trivial that such a linear network has the same expressivity as a perceptron, it may not be obvious that the entropy bias is identical.
Lemma 5.4. Applying a ReL.U function in between each layer produces a lower bound on P(T 0) such that P(T 0) 2 2 n, See Appendix H for proof.
This lemma shows that DNN with ReLU functions is no less biased towards the lowest entropy function than a perceptron is. We prove a more general result in the following theorem which concerns the behaviour of the average entropy (H)) (where the average upon random sampling of parameters) as the number of layers grows. The theorem shows that the bias towards low entropy becomes stronger as we increase the number of layers, for any distribution of inputs. We rely
Note that this is when the input is {0, 13 This is not true for all input distributions. See, e.g. Figure 4d The change in probability for other distributions can be more complex.
8

---

Under review as a conference paper at ICLR 2020
0.5
layers
0.5
0 layers
10
PIT
layers
10-1
PIT
0.3
0.4
1 layers
layers
0.0
layers
5 layers
probability
20
layers
Probability
10
20
8 layers
Num ber layers
10-2
Number of layers
10
10-3
10-4
20
10
60
80
100
120
0
20
10
60
80
100
120
(a) {0, 13", db 0.0, number of layers varied
(b) {0. 1)7, 0b 1.0, number layers varied
30000
0.0
0.4
0p 0.5
PIT
=.0
boyer
2000
Probability
5.0
10-2- 2_2
10
0-=
10.0
2.055
10-2
3065
20
40
60
80
100
120
20
100 100
(c) {0, 137, layer, de varied
(d) [-,, 0bb 0.0, number of layers varied
Figure 4: P(T t.) becomes average more biased towards low entropy for increasing number of layers or increasing Tb- Here we use n input layers, with input (0, 1)7 (centered data) {-1, 1} (uncentered data) The hidden layers are of width 2n 64 to guarantee full
expressivity. Tw 1.0 in all cases. The insets show how P(t = 0) asymptotes to 1 with increasing layers db-
on previous work that shows that in the infinite width limit, neural networks approach a Gaussian process (Lee et al. (2018); (Garriga-aloon al, (2018); Novak et al. Yang 2019)), which for the case of fully-connected ReL.U networks, has an analytic form (Lee al. 2018).
et al. (2018);
Theorem 5.5. Let S be set of m = -SS input points in R Consider neural networks with ii.d. Gaussian weights with variances oz! /n and biases with variance ob, in the limit where the width of all hidden layers n goes to infinity. Let Nı and N2 be such neural networks with L and L+ infinitely wide hidden layers, respectively, and no bias. Then, the following holds: (T)) is smaller than or equal for N₂ than for N1. It is strictly smaller if there exist pairs of points in S with correlations less than 1. If the networks have sufficiently large threshold bias (oa > 1 a sufficient condition), the result above also holds. For smaller bias, the result holds only for sufficiently large number of layers.
See Appendix Hffor proof of Theorem 5.5 Theorem 5.3 is complementary to Theorem 4.1 that the former only proves that the bias towards low entropy increases with depth, and the later proves conditions on the data that guarantee bias toward low entropy on the "base case" of layers. We show in Figure 4 that when σ 0, the bias towards low entropy indeed becomes monotonically stronger as we increase the number of ReLU layers, for both inputs in {0, 1 as well as for centered data 11".
For centered inputs 1-1, the perceptron with b = 0 shows rather unusual behaviour. The dis- tribution is completely peaked around t 2n because every input mapping to 1 has the opposite input mapping to O. Not surprisingly, its expressivity is much lower than the equivalent perceptron with (0, 1)a (as can be seen in Figure 6a in Appendix D). Nevertheless, in Figure 4d that

---

Under review as a conference paper at ICLR 2020
as the number of layers increases, the behaviour rapidly resembles that of uncentered data (In Ap- pendix K we also show that the bias toward low entropy is also recovered as we increase σb). So far this is the only exception we have found to the general bias to low entropy observe for all other systems (see also Appendix D). We therefore argue that this is a singular result brought about by particular symmetries of the perceptron with zero bias term. The fact that there is exception does not negate our general result which we find holds much more generally.
The insets of in Figure 4 show that the two trivial functions asymptotically dominate in the limit of large numbers of layers. We note that recent work (QLee et al. 2018 Luther & Seung 2019)) has also pointed out that for fully-connected ReLU networks in the dlfiite-widte all inputs become asymptotically correlated, so that the networks will tend to compute the constant function. Here we give quantitative characterisation of this phenomenon for any number of layers.
aafinttedeepth limit,
Some interesting recent work (Yang & Salman 2019) has shown that certain choices of hyper- parameters lead to networks which are a priori unbiased, that the P(f) appears to be uniform. In Appendix [ we show that this result is due to a choice of hyperparameters that lie deep in the chaotic region defined in (Poole et al. (016). The effect therefore depends on the choice of activa- tion function (it can occur for say tanh and erf, but most likely not ReLU), and we are studying it further.
6 DISCUSSION AND FUTURE WORK
In Section Theorem 4.1, we have proven the existence of an intrinsic bias towards Boolean func- tions of low entropy in perceptron with no threshold bias term, such that P(T = =) 2- for 0 < L < 2". This result puts an upper bound on the probability that a perceptron with no threshold bias term will be initialised to Boolean function with least certain Boolean complexity. Adding a threshold term in general increases the bias towards low entropy.
We also study how the entropy bias is affected by adding a threshold bias term or ReLU-activated hidden layers. One of our main results, Theorem 5.5, proves that adding layers to a feed-forward neural network with ReLU activations makes the bias towards low entropy stronger. We also show empirically that the bias towards low entropy functions is further increased when threshold bias term with high enough variance is added. Recently, (Luther Seung 2019) have argued that batch normalisation (Toffe & Szegedy 2015) makes ReLU networks less likely to compute the constant function (which has also been experimentally shown in (Page) (019)). If batch norm increases the probability of high entropy functions, it could help explain why batch norm improves generalisation for (typically class balanced) datasets. We leave further exploration of the effect of batch normali- sation a- a-priori bias to future work.
Simplicity bias within the set of constant t functions F, is affected by the choice of initialisation, even when the entropy bias is unaffected. This indicates that there are further properties of the parameter-function map that lead to a simplicity bias. In Section 4.3 we suggest that the complexity of the conditions on w producing a function should correlate with the complexity of the function, and we conjecture that more complex conditions correlate with a lower probability.
We note that the priori inductive bias we study here is for randomly initialised network. If a network is trained on data, then the optimisation procedure (for example SGD) may introduce further biases. In Appendix L we give some evidence that the bias initialization is the main driver of the inductive bias on SGD-trained networks. Furthermore, in Appendix M we show preliminary results on how bias in Pff) can affect learning in class-imbalanced problems. This suggests that understanding properties of P(J) (like those we study in this paper), can help design architectures with desired inductive biases.
Simplicity bias in neural networks (Valle-Pérez et al. 2018) offers an explanation of why DNNs work in the highly overparameterised regime. DNNs can express an unimaginably large number of functions that will fit the training data, but almost all of these will give extremely poor generalisation. Simplicity bias, however, means that a DNN will preferentially choose low complexity functions, which should give better generalisation. Here we have shown some examples where changing hy- perparameters can affect the bias further. This raises the possibility of explicitly designing biases to optimise DNN for particular problem.
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Martin Anthony. Discrete mathematics of neural networks: selected topics, volume 8. Siam, 2001.
Giacomo De Palma, Bobak Toussi Kiani, and Seth Lloyd. Deep neural networks are biased towards simple functions. arXiv preprint arXiv: 10156, 2018.
Kamaludin Dingle, Chico Q Camargo, and Ard A Louis. Input-output maps strongly biased towards simple outputs. Nature communications, 9(1):611, 2018.
Adrià Garriga-Alonso, Carl Edward Rasmussen, and Laurence Aitchison. Deep convolutional net- works as shallow gaussian processes. arXiv preprint SEti::/808.0588// 2018.
Geoffrey Hinton and Drew Van Camp. Keeping neural networks simple by minimizing the descrip- tion length of the weights. In in Proc. of the 6th Ann. ACM Conf. on Computational Learning Theory. Citeseer, 1993.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. arXiv preprint arXiv: 2015.
Anders Krogh and John Hertz. A simple weight decay can improve generalization. In Advances in neural information processing systems, pp. 950-957, 1992.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521((553):436, 2015.
Jachoon Lee, Jascha Sohl-dickstein, Jeffrey Pennington, Roman Novak, Sam Schoenholz, and Yasaman Bahri. Deep neural networks gaussian processes. In International Confer- ence on Learning Representations, 2018. URL
net. forum?rdr
BlEA 0Z
Abraham Lempel and Jacob Ziv. On the complexity of finite sequences. IEEE Transactions information theory, 22(1 ):75-81, 1976.
Ming Li, Paul Vitányi, et al. An introduction to Kolmogorov complexity and its applications, vol- ume 3. Springer, 2008
Kyle Luther and H Sebastian Seung. Striance-preserving initialization schemes improve deep net- work training: But which variance is preserved? arXiv preprint arXiv:
2019.
Alexander G de Matthews, Mark Rowland, Jiri Hron, Richard Turner, and Zoubin Ghahramani. Gaussian process behaviour in wide deep neural networks. arXiv preprint arXiv: /::4.1/27/ 1271, 2018.
David A McAllester. Some pac-bayesian theorems. Machine Learning. 37(3)3555-35 -633 1999.
Nelson Morgan and Hervé Bourlard. Generalization and parameter estimation feedforward nets: Some experiments. In Advances in Neural Information Processing Systems, pp. 630-637, 1990.
Roman Novak, Lechao Xiao, Jaehoon Lee, Yasaman Bahri, Daniel A Abolafia, Jeffrey Penning- ton, and Jascha Sohl-Dickstein. Bayesian convolutional neural networks with many channels are gaussian processes. arXiv preprint arXiv:1810.05144: 2018.
David Page. How to train your resnet 7: Batch norm, 2019. URL https://myrtle..r ton-tttttraan--oo--rar resnet- 7-teeet---aacch-oooooo
Ben Poole, Subhaneil Lahiri, Maithra Raghu, Jascha Sohl-Dickstein, and Surya Ganguli. Exponen- tial expressivity in deep neural networks through transient chaos. Advances in neural informa- tion processing systems, pp. 3360-3368, 2016.
Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Draxler, Min Lin, Fred A Hamprecht, Yoshua Bengio, and Aaron Courville. On the spectral bias of neural networks. arXiv preprint 1oXiv:1806..0 08734, 2018.
Bhiksha Raj. Neural networks: What network represent, 2018.
URL http: 2018/ www/
cs cmu, des www.:ccc.unvvrraaeeeo

---

Under review as a conference paper at ICLR 2020
Frank Rosenblatt. The perceptron:
probabilistic model for information storage and organization in the brain. Psychological review, 65(6):386, 1958.
Jürgen Schmidhuber. Discovering neural nets with low koimogorov complexity and high general- ization capability. Neural Networks, 10(5):877-87,, 1997.
Samuel S Schoenholz, Justin Gilmer, Surya Ganguli, and Jascha Sohl-Dickstein, Deep information propagation. In International Conference on Learning Representations, 2017. URL https:
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, llya Sutskever, and Ruslan Salakhutdinov. Dropout: A simple way prevent neural networks from overfitting The Journal of Machine Learning Research, 15(1):1929-1958, 2014.
Guillermo Valle-Pérez, Chico Q Camargo, and Ard A Louis. Deep learning generalizes because the parameter-function map is biased towards simple functions. arXiv preprint arXiv:1805.0880 2018.
Lei Wu, Zhanxing Zhu, and Weinan E. Towards understanding generalization of deep learning: Perspective of loss landscapes. arXiv preprint arXiv: 1706. 10239, 2017.
Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoc Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, et al. Google's neural machine trans- lation system: Bridging the gap between human and machine translation. arXiv preprint arXiv: 1wwp:0004404444 2016.
Greg Yang. Scaling limits of wide neural networks with weight sharing: Gaussian process behavior, gradient independence, and neural tangent kernel derivation. arXiv preprint arXiv:1902.04760 2019.
Greg Yang and Hadi Salman. A fine-grained spectral perspective on neural networks. arXiv preprint arXiv: 10599, 2019.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv: 161 1.03530, 2016.
12

---

Under review as a conference paper at ICLR 2020
A PROOF OF UNIFORMITY
For convenience we repeat some notation we use in this section. Let {0, 1}" be the set of vertices of the n--imeensiona hypercube. We use (+ refer the standard inner product in R Define the function T: _ + N as the number of vertices of the hypercube that are above the hyperplane with normal vector and that passes through the origin. Formally T(w) | {0, 13" (w, (w, 0/.
We use @ for element- dlement-wise multiplication of two vectors.
We slightly abuse notation and denote the probability density function corresponding a probability measure P. with the same symbol, P. The arguments of the function or context should make clear which one meant.
Proof strategy. We consider the sampling of the normal vector w as a two-step process: we first sample the absolute values of the elements, giving vector wpps with positive elements" and then we sample the signs of the elements. Our assumption on the probability distribution implies that each of the sign assignments equally probable, each happening with a probability 2- The key of the proof is to show that for any wopss each of the sign assignments gives a distinct value of (and because there are 2" possible sign assignments, for any value of T, there exactly one sign assignment resulting in normal vector with that value of T*). This implies that, provided all sign assignments of any Ups are equally likely, the distribution on uniform.
Theorem 4.1 Let P be a probability measure on R", which is symmetric under reflections along the coordinate axes, that P(Rx), where Ris reflection matrix (a diagonal matrix with Let the weights of a perceptron without bias, be distributed according to
elements in 1,1, 1,11) P. Then P(T is the uniform measure.
Before proving the theorem, we first need definition and lemma.
Definition We define the function mapping a vector from {-1, 13"h (which interpret the sig- nature of the weight vector), and a vector of nonnegative reals (which we interpret as the absolute values of the elements of the weight vector) to the value of of the corresponding weight vector:
K [- x R2 + {0, I,..., 2". - 1
(0, @
Lemma A.1. The function K is bijective with respect its first argument, for any value of its second argument except for set of measure O.
Proof of Lemma A. Because the cardinality of the codomain K is the same as the domain of its first argument, it enough to prove injectivity of K with respect to its first argument.
Fix a E R% satisfying that the following set has cardinality 3":
S. ((x, a) a 1-")
Note that the set of in which some pair of elements in the definition of S, is equal has measure zero, because their equality implies that lies within hyperplane R". Let us also define the set of subsums of elements of a:
S (1x, a) : 13.
which has cardinality 2" for the considered.
Now, consider a natural bijection Ja (-1, 13" + S, induced by the bijective mapping of signa- tures 1 to vertices of the hypercube {0, 1 13" by mapping -1 to 0 and 1 to 1. To be more precise, (o) = Σm= a, (o())+1)
Then, we claim that
K(o,a) I(s S s Ja)))
This implies that for the have fixed K is injective, for if two mapped to the same value, their corresponding value of Ja (g) should be the same, giving a contradiction. So it only remains to prove equation 7
almmos surely, assuming 0 has zero probahility measure
13

---

Under review as a conference paper at ICLR 2020
Let us also first denote, for {0, and s, s' Sa
[z)) == (2,a)
sss (E~())
sUs (1--)))
: (E-1()))
where we interpret elements of (0, 1)" as subsets of fl..... n}- The notation above lets us interpret subsums in Sa subsets of entries of Note that E is well defined for the fixed considering.
Now, let E (-1,13", &' = _a(o), and consider an E S. such that s'. Then s0s' +8n8
8 < 8 so
s +
>0
(8)
Now, let the operation (we omit dependence on s') be defined for any u E So as u- = unst
(s' s E Sp. Since s' = Ja(a) we have
((o00). = (
Using equation
Therefore, all the points (s") for 8 o are above the hyperplane with normal (a G a). and all points (s*) for 2 s' are below precisely on the hyperplane. All that is left is to show the converse, all points which are above the hyperplane are Σ (s") for one and only one < s'. It suffices to show that the operation is injective for all (as bijectivity follows from the domain and codomain being the same). By contradiction, let 8 and u map to the same value under ", then n s 8 u n' are considering, and so u. Therefore is injective, and equation follows.
8', which implies s's O s' and 8' uuna 8', for the
Proof of Theorem 4.1
P(T = P(w: ((w)=t)) - (T())
Now, we can divide the integral into the quadrants corresponding to different signatures of w, and we can let P(w) = P(ww)), because is symmetric under reflections of the coordinate axes.
P(w: T(w) = -0) = Σ
P(a)d" al ((
2
1.1-1
1
P(a)daa a
Σ
TT(00)==
2n
R%o
oE(-1.13
P(a)daa.1
2n
3%D
2n
The third equality follows from Lemma A.1 Indeed, bijectivity implies that for any a, except for set of measure 0, there is one and only one signature which results in t'.
B BOUNDING BOOLEAN FUNCTION COMPLEXITY, K Bool, WITH
Theorem B.I. n min(t, 2" - t) 1 is an upper bound on the complexity of Boolean functions f for which T()) t.
14

---

Under review as a conference paper at ICLR 2020
Proof. Let f {0, + {0, 1 be function s.t. T(f) =
Let 21 .... .n be propositional variables and let each assignment to 21 .1... Ty correspond to a vector in {0, 13 in the straightforward way.
Let Φ be the Boolean formula ViA e; = 1 then x, else -z, vs E o) | v E {0, : f(v) = 1}. The formula @ expresses f as a Boolean formula in Disjunctive Normal Form (DNF).
Let v be the Boolean formula (iV 2 = 0 then F, else -I; 02 E 2} 0 E [0,1)", ".11)"(((v)) f(u) = 0}. Boolean formula in Conjunctive Normal Form (CNF).
The formula & expresses
Since f maps t out of the 2" vectors in {0, 1]" to 1 must be the case that e has clauses and e has 2n - clauses. Each clause contains
1 binary connectives, and there is one connective between each clause. Hence & contains n x - -1 binary connectives and & contains n x (2" - -t) - binary connectives. Therefore expressed by some Boolean formula of complexity n mimitt, (t) -
Since f was chosen arbitrarily, if a function f {0, 1}"h 7 {0, 13 maps inputs to then the complexity of f is at most n x min(t, 2 -1) 1
Theorem B.2. Let C be defined recursively as follows;
C'n, 0) 0
2") 0
C(n, 1)
C(n,2" - -1) =)=n -1)==- -
C(n,t) -C(n - (t/22) C(n C(n- 1, 1, +2
Then C(n, t) an upper bound on the complexity of Boolean functions f for which T(f) = t.
Proof. Let P(n) be that C(n, t) is an upper bound on the complexity of Boolean functions f over n
variables s.t. T()) L.
Base case P(1): If d is a Boolean formula defined over variable then á is equivalent to True, False, 31, -1. We
by exhaustive enumeration that P(1) holds in each of these four cases.
Inductive step P(n) - P(n + 1): Let & be a Boolean formula defined over n + 1 variables s.t.
T(Ø) tt.
Case 1. 1 = 0: If | = 0 then Φ = False, and so the complexity of Φ is 0. Hence the inductive step holds.
Case 2. = 2": If = 2" then Φ True, and so the complexity of Φ is 0. Hence the inductive step holds.
Case 3. f- 1: If t = 1 then & has just single satisfying assignment. If this is the case then & can be expressed as a formula of length n written in Disjunctive Normal Form, and hence the inductive step holds.
Case 4. f == 2" 1: If = 2n - then & has just single non-satisfying assignment. this is formula of length n written in Conjunctive Normal Form, and
the case then ø can be expressed hence the inductive step holds.
Case 5. 1 < t and t < 2" 1: If o is Boolean formula defined over variables then & is logically equivalent to a formula (In-1 A whi V (-In+1 A 1/2), where t and th are defined over J1 ... Let be the number of assignments to 21 T. that mapped to 1 by 4/1, and let to be the corresponding value for 4/2.
By the inductive assumption the complexity of ti and 122 is bounded by C(n, (1) and C(n, f2) re- spectively. Therefore, since o = (In+1 A vi)) V (-In+1 A v22 it follows that the complexity of at most C(n,t1) + C(n, t2) 2. Since t + t2 = and since C(n, ta) C(n, ty) if to is closer to 2 than to is (lemma B.3). it follows that the complexity of o is bounded by C(n,t) = C(n - 1, [4/2]) C(n 1, (,22 +
Since Case to 5 are exhaustive the inductive step holds.
Lemma B.3. Ift + 1 2n then C(n, t) < C(n, ((),++1)) 1).
Proof. Let P(n) be that if 1 1 $22" 2n then C(n, 1) C(n, L 1).
15

---

Under review as a conference paper at ICLR 2020
Base case P(2): We that ()4 = C(4, = C(4.2) C(4. 2 and C(4, 4)
1. By exhaustive enumeration we can see that P(2) holds. Inductive step P(z) P(n + 1):
Case 1. t even:
C(n + (( (C(n,t/2) C(n,t/2) -
- (C(n,t/2)+ C(n,t/2 1)+ +2)
C(n,t/2)- C((nt/2++1
If é even and + < 2 then f/2 2-11 Hence C(n,t/2) C(n,t/2+ < by the inductive assumption, and so C'n + 1,t) Cnn + 1,t+ <
Case 2. t is odd:
= 1+ =(n,+++++==((t(((tt( ()(2) C(n, 1)/2) +2) (c (t 1)/2) +2)
1,
1)/2)
It't is odd and ++1 ((++1)-1 then (++1)/2 < 2n Hence C'n, (t-1)/2) (11)))))((n,(++1)) <0 by the inductive assumption, and so C'nn + 1, C(n + 1, + 1) < 0.
Since Case and 2 are exhaustive the inductive step holds.
C P(t 0) FOR PERCEPTRON WITH INFINITESIMAL b
If is sampled uniformly from [-c, c). then only if (w,x)) can some be classified differ- ently from a perceptron without a threshold bias term. The set of weight vectors which change the classification of non-zero æ becomes vanishingly small goes
but for P(1((w, 0)+ = 0) = P(1 (w,, 0)++b) = 1) 1/2. Consider some function f, and define g where f- g under the addition of an infinitesimal bias. Then with even probability the origin remains mapped to (meaning T(g) = T(f)). or is mapped to 1 (meaning T(g) + 1) as the rest of is unchanged, (c). As this true of all f, PTT t)o~(-e,e) P(T = +)+ leading to:
have
1),
2 (2- (a+1) - or 2n
P(T =t= 2- otherwise
(9)
For larger σb P(t 0) or P(t 2n) increases with increasing σ as can be seen in Figure of the main text.
D ZIPF'S LAW IN A PERCEPTRON WITH b = 0
In Valle-Pérez et al. 2018 it was shown empirically that the rank plot for simple DNN exhibited a Zipf like power law scaling for larger ranks. Zipf's law occurs many branches of science (and probably for many reasons). In this section check whether this scaling also occurs for the Perceptron.
In Figure 5)
compare rank plot of the probability P(f) for individual functions for the simple perceptron with = O, the perceptron, and for a one layer FCN. While all architectures have n = 7, the perceptrons of course express far fewer functions. Nevertheless, both the perceptrons and the more complex FCN show similar phenomenology, with a Zipf law like tail at larger ranks (i.e. power law).
16

---

Under review as a conference paper at ICLR 2020
10
100
P
Zipf
Zipf
10
10
Probability
Probability
10-4
10
10-6
10-6
10-8
10-8
100
10a
10
106
100
10a
10a
10a
104
10a
106
rank
rank
(a)
(b)
100
p
10-2
Zipf
10-2
Zipf
Probablity
Probability
10
10
10-6
10-6
10
10-8
10a
10a
102
10
10
105
105
10
102
104
10
rank
rank
(c)
(d)
Figure 5: Probability vs rank for functions (ranked by probability) from samples of size 10a, with input size 7, and every weight and bias term sampled from (O 1) unless otherwise specified, over initialisations of: (a) a perceptron with b = 0; (b) perceptron; (c) a one-hidden layer neural network (with 64 neurons in the hidden layer); (d) a perceptron with b and weights sampled from identical centered uniform distributions (note how similar (a) is to (d)!). We cut off frequencies less than eliminate finite size effects. In (a) and (b) lines were fitted using saus-ss regression; for (c) the line corresponding to the ansatz in Equation (T0) is plotted instead.
While the orginal formulations for Zipf's law only allows for a powerlaw with exponent 1, in practice the terminology of Zipf's law is used for other powers, such that b x rank for some positive a, b. If we assume that this scaling persists, then we can relate the total number of functions perceptron can express, the constant b, because the total probability must integrate 1.
For the simplest case with a = 1, this leads to an equation for the probability as function of rank given by
P(r) In(N))r
(10)
where No is the total number of functions expressible.
The FCN appears to show such simple scaling. And as the FCN of width 64 is fully expressive (see Lemma 5.1 there are No = 2 == 3 x 10 possible Boolean functions. We plot the Zipf law prediction of Equation (TO) next to the empirically estimated probabilities in Figure [5c] We observe that the curve is described well at higher values of the rank Zipf's s law. Note that the mean probability uniformly sampled over functions for this FCN (P()) = 1/No s 10-39 so that we only measure tiny fraction of the functions with extremely high probabilities, compared to the mean. Also, most functions have probabilities less than the mean, and only order 2- have probability larger than the mean. A least-squares linear fit on the log-log graph consistent within experimental error for the ansatz.
For the perceptron with bias term Figure 5b observe that the gradient differs substantially from -1, and a linear gives (p) calculating No made in Equation 100.
0.85 log (rank) 2.32. Using the same arguments for obtain prediction of No 7.63 x 10 which is 91%
17

---

Under review as a conference paper at ICLR 2020
10
1-1,3
10
10
10
10"
10
10"1
10'
101
112
102
Tanks
(b)
Figure 6: (a) Probability of functions versus their rank (ranked by probability) for a perceptron with 5, and weights sampled i.i.d. from a Gaussian and no threshold bias term, acting on either centered {] or uncentered {0, 1) data. (b) Probability of functions versus their L.Z complexity for perceptron with n 6, and weights sampled i.i.d. from Gaussian and no threshold bias term, acting on the centered Boolean hypercube {-1,
of the known value" A linear fit for the perceptron with no threshold bias term gives (p) = -0.81 (rank)) 2.31, leading prediction of No 3.97 108. which is, as expected, significantly lower than perceptron with no threshold bias term. We expect there to be some discrepancy between the pure Zipf law prediction, and the true No. because the probability seems to deviate from the Zipf-like behaviour at the highest rank, which we observe for = 5 in Figure (aa as in this case the number of functions is small enough that becomes feasible to sample of them.
It is also worth mentioning that rank- aank-probbbility plot for a perceptron with weights sampled from a uniform distribution (Figure (d) is almost indistinguishable from the Gaussian case (Figure (5h), which is interesting, because when plotted against LZ complexity, as in Figure I of the main text, there is small but discernible difference between the two types of initialisation.
Finally, in Figure 6a we compare the rank plot for centered and uncentered data for a smaller 5, T = 0 perceptron where we can find all functions. Note that for the centered data, only functions with t 16 can be expressed, which is somewhat peculiar, and of course means significantly less functions. Nevertheless, this systems still has clear bias within this one entropy class, and this bias correlates with the I.Z. complextty (bb also observed for the perceptron with centered data.
E FURTHER RESULTS ON THE DISTRIBUTION WITHIN F,
In this appendix we will denote the output function of the perceptron evaluated on {0, 13" by way of bit string f. whose i' i'th bit is given by
f 1( bin (i)))
(11)
where bin(i) takes an integer i and maps it to a point & E {0, 13" according to its binary represen- tation (so bin = 01, 1) and bin(1) (0, 0, 1) when n 3).
E. EMPIRICAL RESULTS
We sample 1 initialisations of the perceptron, divide the list of functions into F,, and present cabbability-complente plots for several values of in Figure 7 We use the Lempel-Ziv -iiv complexity (Lempel & Ziv| 1976. Dingle et al.) 2018) of the output bit string the approximation mogorov complexity of the function (Dingle et al.) 2018). As in (Dingle et al.) 2018 Valle-Pérez) al. 2018), this complexity measure denoted K Kzz(f). ) To avoid finite size effects (as noted in Valle-Péred et al. 2018)), we cut off all frequencies less than or equal to 2.
the Kol-
hhtpps//eei..oog///M00099/ii
18

---

Under review as a conference paper at ICLR 2020
100
100
10-2
10-2
Probability
Probability
10
10"4
10-6
10-6
10-8
10-8
50
100
150
0
50
100
150
Kiz
Kiz
(a) T(f) =
(b) T(f)= 16
10a
10a
10-2
10-2
Probabiitt
Probability
10-4
10-6
10
10-8
10
25
75
100
150
50
125
Kiz
(f)
(d) T(f) 64
Figure 7: P(J) KLz (f)) at selection of values of T()), for perceptron with input dimension 7, weights sampled from (O, 1) and no threshold bias terms. We observe a large range Kzz(fi for fo E F, which increases
approaches 64, which is to be expected - for example the function f f= 000000.... very simple and has maximum entropy, and we expect there to exist higher com- plexity functions at higher entropy. Consistent with the bound in (Valle- Pérez et al. 2018), simpler functions tend to have higher probabilities than more complex ones. The data-points at especially high probabilities in Figure 7d correspond to the function f 0101 and equivalent strings after permuting dimensions.
graph satisfies the simplicity bias bound Equa- tion (I) for all functions. Now, in Figure ? observe subsets F, of the overall set of functions. Firstly, we observe, as expected, that smaller / means smaller range in Kı,,, since high complexity functions not possible low entropy. Conversely, low complexity functions entropy (say for 010101..),, and so larger range of probabilities and complexities is observed for t = 64. For these larger entropies, an overall simplicity bias within the of fixed f be observed.
As can be seen in Figure I the probability
possible at high
The larger range observed in f 64 and = 16 (compared to = 41 and f = 9) can be explained by the presence of highly ordered functions having those values for example, in f 64, there is f = 0101 and its symmetries; and in = 16 there are functions such f 00010001 and its symmetries. The other block entropy (implying low Kız)..
values do not divide 27, there will be no functions with such low
We also demonstrate differences in the variation in P(f) vs Kfz(f) when w is sampled from uniform distributions, in Figure X and compare these pots to those in Figure 7 Whilst we know from Theorem 4.1 that sampling w from a uniform distribution will not affect P(t), to see that there will be some variation in function probability within the classes IF, We observe that the simple functions which have high probability for t = 64 when the perceptron is initialised from Gaussian (Figure 7d) have lower probabilities in the uniform
not hard
(Figure &d). We comment further on this behaviour in Appendix [E.2] However, we see limited differences in their respective rank- brobabrbbayllity plots Figure 5al and Figure
19

---

Under review as a conference paper at ICLR 2020
100
100
10-2
10-2
Probability
Probabiitt
10"4
10-4
10-6
10
10-8
10-8
0
50
100
150
50
100
125
Kuz
Kiz
(a) T(f) =
(b) T(f)= 16
10a
10a
10-2
10-2
Probabiity
Probability
10-4
10-6
10
10-8
10
25
75
100
150
50
125
Kiz
T()) 41
(d) T(f) 64
Figure 8: P(J) kzz(J) (f) at selection of values of T()), for perceptron with input dimension
7, weights sampled from a centered uniform distribution and no threshold bias terms. We compare to Figure 7 and observe that uniform sampling reduces slightly reduces the simplicity bias within the sets IF, (see Appendix E.2
E.2 SUBSTRUCTURE WITHIN 1)"
Consider a subset H C {0, 13" such that 0 E 7m" We have (*) such subsets. Then the marginal distribution over 7 given by
Σ 1((wx))) =t) 2 2m
(12)
This is again independent of the distribution of is (provided it's symmetric about coordinate planes). We give two example applications of Equation (1) in Equation (l3). We use to mean any allowed
value, and sum over all allowed values,
Σ P(J "0=="000~ 00000') 2- 11-
(13)
Σ P(f= +"+**" 2 (x-2)
=
We can apply the same argument that we applied in Section 4 to any set of bits in f defined by some H" to show that there is an "entropy bias" within each these substrings. However, these identities imply strong bias within each F,. For the case of full expressivity, assuming each value of has probability 2-", and every string with the same value of is equally likely, one gets probabilities very close to those in Equation (13) (although slightly lower). However, the perceptron is not fully expressive, so it unclear how much the probabilities on Equation B are due purely to the entropy bias, and how much is due bias within each Fr.
20

---

n! Under review as a conference paper at ICLR 2020
It is difficult to calculate the exact probabilities of any function for Gaussian initialisation not be possible to fine-grain probabilities analytically further than Equation [12 (although we can the techniques in Section 4.3 to come up with analytic expressions for P() for all f).
5
It may
However, we can calculate some probabilities quite easily when w is sampled from a uniform distri- bution, ~ (-1,,, 1). By way of example, we calculate P(f = f) for f = "0101... 0101".. The conditions for f are as follows: wn 0, uy Vi + and Σ, W 0, so
!./
x= dr 2 (n 1)!
P(f = - -
(14)
Using Equation (3) we can calculate how much more likely the function is than expected,
P(=
2--22-1
(15)
(P(f-22-1))
n!
For n 5. calculate Equation 15 using -1 370 and (-,, and
obtain P(f = (P)(((((===-))))
3.08. This clearly shows that f is significantly more likely than expected just by using results from Equation (3). Empirical results further suggest that for Gaussian
initialisation of w, P(f () se 10. This, plus data in Appendix E.1 suggest that Gaussian initialisation may lead to more simplicity bias.
F TOWARDS UNDERSTANDING THE SIMPLICITY BIAS OBSERVED WITHIN F,
Here we offer some intuitive arguments that aim to explain why there should be further bias towards simpler functions within F,,
We first need several definitions.
We define a set A C R such that E A iff a, a Vi j. interpreted as the absolute values of the weight vector.
We now define four sets, I' Σ and Y, which classify the types of linear conditions the weights of a perceptron acting on an n-dimensional hypercube:
1. P. the set of permutations in : n) (which can interpret as permutations of the axes in IR" or as possible orders of the absolute values of the weights if no two of them are equal).
2. Σ = (-1, +13" (which is interpreted as the signature of the weight vector)
3. T is the set of linear inequality conditions on components of a E A, which include more than two elements of (so they exclude the conditions defining A.
A unique weight vector can be specified giving its signature E, the order of its absolute values E Г. and a value E A. On the other hand, a unique function can be specified by a set of linear conditions the weight vector w. These conditions be divided into three types: Σ (signs), r' (ordering), and Y (any other condition).
The intuition to understand the variation in complexity and probability the following. Each function corresponds to unique set of necessary and sufficient conditions on the weight vector (corresponding the faces of the cone in weight space producing that function). We argue that different functions have conditions which vary a lot in complexity, and we conjecture that this correlates with their probability, as we discuss in Section
different functions is
the main text.
As a first approach in understanding this, we consider the role of symmetries under permutations of dimensions. Any string that is symmetric under a permutation essary conditions that represent relative orderings of those i dimensions. Furthermore the set of
dimensions"] can't 't have nec-
'Except for frea, because we know all functions within constant t for t 3 equivalent under permuta- tion of the dimensions all their probabilities are equal the average probabilities given by Equation 3 6370 unique functions were obtained by sampling 10 weight vectors so this is technically lower bound dimensions
or example, "0101010..." symmetric under permutation
21

---

Under review as a conference paper at ICLR 2020
conditions must be invariant under these permutations. This strongly constraints the sets of condi- tions that highly symmetric strings like "010101..." " or "1 "11111...00000.." can have, to be relatively simple sets.
We now consider the set of necessary conditions in for different functions. We expect that con- ditions in Y are more complex than those in I and E. Furthermore, find that functions have R similar number minimal condition so that more conditions in Y seems to imply fewer condi- tions in I and Σ, and therefore, more complex set of conditions overall.
We are going to explicitly study the functions within each set of constant 6, for some small values of I, and find their corresponding conditions in Y and Σ. We fix I to be the identity for simplicity. The conditions for a particular functiin should include the conditions we find here plus their corre- sponding conditions under any permutation of the axes which leaves the function unchanged. This means that on top of the describing the conditions for fixed r, we would need to describe the set of axes which can be permuted. This will result small change to the Kolmogorov complexity of the set of conditions, specially small for functions with many symmetries or very few symmetries.
We find that the conditions appear to be arranged a decision tree (a consequence of Theorem 4.1 with a particular form. First, we will prove the following simple lemma which bounds the value of t that is possible for some special cases of a.
Lemma F.1. We define mm (0) to be the minimum possible value of T C a) for fixed over all a. We define bmax similarly. Consider a
Then:
k-
1. tman (0) 2k-1
2. tmin (o) = h:
3. Changing O, {+1} for some i < le will lead to an increase in Emin(()
Proof. 1. For any a, f(x) = 1 for all (exactly k) points E: {0, 1)" which satisfy
(rk 1) and (a: for exactly one S 1s) and (zy if + i;
We can set f(x) = 0 for all other x E 10, R by imposing the condition + a2 > ag. Thus Emin (o)
2. We can restrict the values of for i < k to be arbitrarily smaller than as provided they satisfy the ordering condition on a, and thus if we impose the condition
k=
ax
then for any a, f(x) for all x E {0, 1)" which satisfy
(Ix 1) and (x: Ofl k)
for any x which does not satisfy these conditions, because ag < aj for all k < and a is the only positive element in Thus fmax = 2
We can see that, for all a, ((x
On changing a such that a, {+1). all x {0, 13" which previously satisfied fxx will remain mapped to 1, plus at least the one-hot vector with a, = 1.
We will now sketch a procedure that allows one to enumerate the conditions in Y and Σ (corre- sponding conditions on and respectively) such that they satisfy T(a a) t, for any given t.
1. From Lemma R.1 we see that all a; = - 1 for > t in order for (m) S t.
2. Iterate through all 2 distinct a which satisfy 1., and retain only those which also satisfy fminn()) S t. fmmn (a) can be computed by counting the number of inputs E (0. 1) such that for every F, with a; = 1, there exists Z, with j > such that 0, = 1. These are all the such that and imply they are mapped to 1 without further conditions on a.
Inn fact we conjecture that the number of conditions is close to n. for most functions, although we empirically find that can sometimes be larger too
22

---

Under review as a conference paper at ICLR 2020
3. Find conditions on these such that T(a @a) t. We find the possible values of T(a @ a) by first ordering the in a way that satisfies z < if x has less is than x'. We then traverse the decision tree corresponding to mapping each of the æ, in order, to either 1 or O. At each step, we propagate the decision by finding all x not yet assigned an output, which can be constructed the coefficients in the combination have opposite signs for x' mapped to different outputs. We stop the traversal if' some point more than t points are mapped 1. Each of the decisions in the tree, correspond to new condition on a. We denote these conditions by e.
linear combination of x's with assignments, where
For small values of one can perform this search by hand. For example, we consider / = 4. We find that all signatures with 024 = -1 are the only set that have (min S 4. As an example we consider the signature
[+1, -1, -1, -).. For this signature result in T(o @ a) 4. need conditions on ø1 = (1, I...) and 22 = (1, 1,0,
which are (a4 > a1 ag) and (a3 < a1 + 02). Figure 9 shows the full sets for = and & We observe that each branching corresponds to complementary conditions which to be expected, as there exists a signature producing & for any a, as per Theorem 4.1
t=
a5 01
02
05 >
01 + 02
4
a1 < 01
02 0. >
01 02
44
01 02 04 > 01 002
+
<
+
02
03 >
+
< +
43
> + 03 +
+
+
(a) 4
(b) 5
Figure 9: We assume that the signs to the right of those shown are all negative. We can list the various -quivallvl classes of functions and their conditions in a pictorial form. A condition at any node in the graph is also condition for any daughter node by way of example, we would read the conditions of t = 4 for the sign arrangement + + (see Figure 9a) as ((a4 a + 02) ((2 < a + a2)).
Fach distinct condition on and produces a unique function f. as the constructive procedure above produces the inequalities on a; by specifying the outputs of each input not already implied by the set of conditions, thus uniquely specifying the output of every input. We now show that there is a large range in the number of conditions in required to specify different function. First, as the analysis in the proof of Lemma F.I shows, for every there exists signature which only requires one further condition,
+1,
v at < a1 + 02
n-t
Furthermore, we prove in Lemma F.2 that for all n there is at least one function which has 2 conditions in T (which are neither Σ I'). This implies that there is large range in the number of conditions in T for large n.
Lemma F.2. There exists a functioon with n - 2 inequalities in Y, that is not including those induced by E or in I.
Proof. We prove this by induction.
Base case n = 2: There exists a function with minimal conditions corresponding to (1,0) mapping to and (1, 1) mapping to O.
Assume that in n dimensions, there exists a function with n minimal conditions corresponding to points {p:)2_ with p; (1, (1....,B ......00 0) with 1s in the first i positions, and 0 in the last
23

---

Let ø and vé be specified over Under review as a conference paper at ICLR 2020
positions, being mapped to f(p.) (1 + (-1)+t1)/2 Now, in dimensions,
extend
each of those n conditions (planes) by adding a to the nth coordinate of each point p,. We now consider cone in dimensions bounded by these planes and bounded by the Wx+1 0 plane, with W6++1 > O if n is even or Wn+1 < 0 n is odd. If n. is even, we can keep increasing Wx+1 until cross the plane Pa-1 0, with Pa++1
(1, (I,...y 11). We do the same, decreasing Wx+1 if is odd. After crossed the Pn+1 0 plane, the boundaries of the plane will be {p: ]= with pi = (1,..., 1,0, dots, 0) with Is in the first positions, and 0 in the last n + - positions, finishing the induction.
We conjecture that more conditions in T (i.e. more complex conditions) correlates with lower probability (if w is sampled from a Gaussian distribution). If this is true for higher t, we should expect to see high probabilities correlating with lower complexities, which if true would explain the "simplicity bias" we observe beyond the entropy bias.
G EXPRESSIVITY CONDITIONS
Lemma 5.1 neural network with layer sizes (n,2" 1) can express all Boolean functions over variables.
Proof. Let f 10. + (00,1) 13 be any Boolean function over n variables, and let be the number of vectors in {0, 13"h that f maps to 1. Let be the negation of f. that is, F(x)
f(x).
It is possible to express f as a Boolean formula ø in Disjunctive Normal Form (DNF) using t clauses, and f as Boolean formula & using 2n -t clauses (see Appendix the variables 21 Zn..
We can specify a neural network N₂ = (Wa1, bæt, Wa2, bo2) with layer sizes (n, f, 1} that expresses f by mimicking the structure of d. Let W [[..)) 1 if z; positive in the j'th clause of ø, W [.] = -1 1 if is negative in the j'th clause of o. and W Woils.]] 0 if x; does not occur in the j thth clause of o (note that the construction in Appendix BJis followed then every variable occurs in every clause in Φ). Let bei()] 1 - y, where y is the number of positive literals in the j'th clause of á. let by2 = O. and let W 62]] = for all j. Now No computes f. Intuitively every neuron in the hidden layer corresponds to clause in c, and the output neuron corresponds to an OR-gate.
We can similarly specify a neural network N₂: = (W b W2,, with layer sizes (n, -t, that expresses F by mimicking the structure of t. Using this network we can specify a third network No (Wo1, bei, Woz, boz) with the same layer sizes as N₂ that expresses f by letting Wo Wa1, boi = b Woz = - Wa2, and bøz = bby + 0.5. Intuitively No simply negates the output of No.
Therefore, any Boolean function f over n variables is expressed by neural network No with layer sizes (n, t, 1) and by a neural network No with layer sizes (n, 2" - t, 1). Since either t < 2n or 2n - t < 2n-1 it follows that any Boolean function over variables can be expressed by neural network with layer sizes (n, 2n-1,
Lemma 5.2 A neural network with I hidden layers and layer sizes (n, (n+ 2n +1), (n+ 2d logg + 1),1) 1) can express all Boolean functions over variables.
Proof. Let f (0, + {0, 1) be any Boolean function over n variables, and let be the number of vectors in {0, 13" that maps to 1. Let be the negation of that is, f(x) = fxx)
is possible to express f as a Boolean formula @ in Disjunctive Normal Form (DNF) using t clauses, and f as a Boolean formula & using 2n -t clauses (see Appendix B Let & and s be specified over the variables F1 Z..
Zn.
Let No = (Wa1. ber.... W Wor+2 b2442) be a neural network with layer sizes (n, (n + [t/ + 1),.... (n [1/l] + 1), 1).
24

---

Under review as a conference paper at ICLR 2020
For 2 < k < 1:
Let WoRA be an identity matrix of size n. x n, and AaKA zero vector of length i.
Let W be matrix of size [t/l] such that W PeBBi.J
1 if z; is positive in the ((k 1) x ([t/T) + t' clause of 6, -1 if it is negative, and 0 if z; does not occur in the ((k: 1) ([t/i) + j) th clause of (note that if the construction in Appendix B is followed then every variable occurs in every clause in Q). Let bøsB be vector of 1-% where 7 the number of positive literals in the ((k 1) x ([t/[) + 5) th clause Φ.
length [t/[]] such that BORBL]
Let Wokc be unit matrix of size (st/1] 1) x 1, and let bØRC [0].
Let Wor and box be the concatenation of WoRA. WobB, Werc and boKa, borB. bokC respectively in the following way:
Sat Onxn
[WRB]] DxxTs
((1//++)x1 [W [Wok]]
W =
bbt = [bboaa] [bok
[bacl]]
Let W61 and bøi be the concatenation of WoKA, WoRB, and baKA, bokB respectively, where these are constructed as above. Let 2o(12) be unit matrix of size ([t/T] + +1 x 1, and let bœ(t+) = [0].
Now No computes f. Intuitively each hidden layer is divided into three parts; neurons that store the value of the input to the network, [4/l] neurons that compute the value of some of the clauses in sb and one neuron that keeps track of whether some clause that has been computed so far is satisfied.
We can similarly specify a neural network No (W byi, Wit+2 bet42) with layer sizes (n, (n + [(2 t)/(] + 1)..... .n + [(2" t)/1 + 1), 1) that expresses F. Using this network we can specify a third network No- = (We1, bei. Wor+2. bạt-2) with the same layer sizes as No that expresses f by letting Wo: W we, box = bos for < and W Wo(+2)
We(+2)) and
be((+2) = 2b42)) + 0.5. Intuitively No simply negates the output Ng--
Therefore, any Boolean function f over variables is expressed by neural network No with layer [t/[] [ + 1), 1) and by neural network Na with layer sizes (n, (n+ [2" t) +)). ...,, (2" -)/[[ + 1), 1). Since either S 2n or 2 mn-t S 2n-1 follows that any Boolean function over variables can be expressed by a neural network with layer sizes (nz [2- +1 (n+ +17+1), 1), 1) (n,(2* (2 (2--1- 1-lg +n++1)... (2 11 1-10a +
sizes (n, (n + [t/l] + .). (n +
+ 1).
H THEOREMS ASSOCIATED WITH ENTROPY INCREASE FOR DNNs
We define the data matrix for general set of input points below.
Definition H.1 (Data matrix). For general set of inputs, {z {zli))i=t.....m E R", we define the data matrix X Rmxn which has elements Xij z(i),, the j-th component of the i-th point.
For any set of inputs 3, the probability distribution on T a connected feedffoodeeedforaadt neural network with linear activations, no bias, and i...d. initialisation of the weights is equivalent to an perceptron with no bias and i..dd weights
Lemma 5.3
Proof. Consider neural network with L layers and weight matrices Wy Wy, (notation in Sec- tion acting on the of points S. The output of the network on an input point E S equals We where W W1 w) Wp As the weight matrices we are i.i.d., their distributions are spherically symmetric P(w; oR) P(w; a) for any rotation matrix R in E. and matrix E x This implies that P aR) = P( = a). Because the value of T is independent of the magnitude of the weight, |ū], this means that P(T = t) equivalent that of an perceptron with i. (and thus spherically symmetric) weights.
One can make Lemma 5.3 stronger, by only requiring the first layer weights wo to have a spherically symmetric distribution, and be independent of the rest of the weights. If the set of inputs is the
25

---

Under review as a conference paper at ICLR 2020
hypercube, S 7(", needs even weaker conditions, namely that the distribution of Wy is sym- metric under reflections along the coordinate axes (as in Theorem 4.1 and has signs independent of the rest of the layer's weights. This implics that the condition of Theorem 4.1 is satisfied by w.
Lemma 5.4 Applying ReLU function in between each layer produces a lower bound on P(T 0) such that P 0) 2 2-
Proof. Consider the action of neural network (n, 11,44...... 1p. 1) with ReLU activation functions on {0. 1)". After passing {0, 1 through 11... Lp and applying the final ReLU function after 4p- all points must lie in R2o by the definition of the ReLU function. Then, if is sampled from distribution symmetric under reflection in coordinate planes:
2 = P(w 20 S 0) < P(T = 0, ReLU)
This result also follows from Corollary H.7
We observe P(T 2 1) R P(T 0) because the states symmetric except in cases where multiple points are mapped to the origin. This happens with zero probability for infinite width hidden layers.
Theorem 5.5 Let S be set of m [S] input points in R". Consider neural networks with i.i.d. Gaussian weights with variances o² / /n. and biases with variance ob in the limit where the width of all hidden layers n. goes infinity. Let N1 and N2 be such neural networks with L and L+ infinitely wide hidden layers, respectively, and no bias. Then, the following holds: (H (T)) is smaller than or equal for N2 than for N1. It strictly smaller there exist pairs points in 3 with correlations less than 1. If the networks has sufficiently large bias (0, > 1 is sufficient condition), the result still holds. For smaller bias, the result holds only for sufficiently large number of layers L.
Proof. The covariance matrix of the activations of the last hidden layer of a fully connected neural network in the limit of infinite width has been calculated and are given by the following recurrence relation for the covariance of the outputs at layer [[cite]]:
Kt 2')
oi
K Kl-1 (I,I)K (x',x') sin 0:-1 + 0%-01 cos or-1
(16)
2T
Kt (I)
8 0
cos-1
(17)
V (at,
For the variance the equation simplifies
-² - (x,
x))
(18)
K² (x,²')
The correlation at layer is pf (x,x') above recursively as
=
(K(( can be obtained using Equation (16)
o' (2,xx) of 2 2
K (I, K (x', x'',,')pp 1 (2t, x¹)
of + oi K K1 of oa K (x', xx)
Note that we can speak interchangeably about the correlations hidden layer / - 1, or the correlations of the output at layer I, the two are the same. This is standard result, which we state, for example, in the proof of Corollary H.7
26

---

Under review as a conference paper at ICLR 2020
where
Po(xx x') = (sin cos -1 (x, + (I - cos (p' (x, x')) (p'
1 π
(x,))))
For the case when 06 = 0, this simply becomes to pf (x(xxz')) = Po (2),
This function is when o² (z, x') (x, x²) < 1, which implies that it is greater than - (z, x²). Therefore the correlation be- tween any pair of points increases if (x, x') < 1 or stays the same if p' (x,,') = 1, as you add one hidden layer. By Lemma H.2 this then implies the theorem, for the case of no bias.
and has a positive derivative less than for 0 S
When σb > 0, we can write, after some algebraic manipulation
(m.aaa)) ((xr,x")
p (xxx²')
1 +
(19)
p² (x,
7 (.)))
+ Ki- (x|,
+ 7a
2 1 +++ 1t7d%
(20)
Voz +22
2
x(1),
(21)
where y (3.""-'aaaa" 0 and _.la..a) (z,
1, and the inequality follows from K' K' a)
>
20
of for any 2, which follows from Equation 16
We will study the behaviour of <(7) as a function of y for different values of a and of. For = O. this function equals 1. If ! < of < a, its derivative is positive, and therefore is greater than 1 for
> 0. If < of there is unique maximum for 7 > 0 at -aj-1 a5-a" Because the function tends a 20, if it went below 1, then at some 7 0 should cross 1 (by the intermediate value theorem), and by the mean value theorem, therefore it would have an extremum below one, and thus local minimum, giving contradiction. Thus the function always greater than 1 when σb 1.
When Th +. (97) can be less than 1, thus the decreasing the correlations, for some values of yy We know that if y 2(1-ao?)
inequality in Equation 19 1)ag the function is greater than equal to 1. However, because of the we can't 't say what happens when yy is smaller than this.
From Equation (18) we know that if of. > 2, K'' x) and (x', (x',x') grow unboundedly as grows. By the above arguments applied to the expression in Equation (19) before taking the
inequality, this implies that after some sufficiently large I, pt 1xx2²) will be 1. If oz < 2,
p'(a),=")
(z, and (x=,"""))') tend to 1-02/2 which also becomes the fixed point of the equation of
for K' (2,xx)) Equation (16), implying that p' (z, x') + 1 as + do, so that the correlation must increase with layers after sufficient number layers, and thus the moments by Lemma H.2
Finally, applying Lemma H.8 the theorem follows.
Lemma H.2. Consider two sets of input points to an n-dimensional perceptron without bias, and V with data matrices and V respectively (see Definition [..]). If for all i, = 1,.., m, then every moment (19) of the distribution P(T =t) is greater for the set of points V than the set of points U.
(VVT) )/// //lg//VVe (VVTT) (VVT))(VV"));; 2 (UU") )is/ (UU");((UU))
Proof of Lemma 1.2
We write T as:
T.
1 ((w, 8)))
i=
T, = Σ
1 1(w, u²)
i=1
27

---

Under review as a conference paper at ICLR 2020
The moments of the distribution P(T, =) can be calculated by the following integral:
(19)8- Σ 1(w,, st)) x 1( sx)) P(S)dS
Where S (Si,..., Sq). Taking the sum outside the integral,
= =E 1((1, si)) x ... x 1((w, ((W))s)))
Σ S
P((w, 8:) > 0, O,...,
,....,,(,, (w, sg) > 0)
t...9
The distribution for U of the equivalent form. From corolloray Corollary H.7 we have that P(w,, 8:) > O,..., (w, 84) "....,,,, for g.
0) I P((,, ui) > .,..., ., (W, Un) > 0). Thus we have Equation (2)
(1))s (1
(22)
Lemma H.3. Consider an 2-dimensional Gaussian random variable with mean and covariance E. the correlation Eij/ / Eij increases, then
P(r; > 0, 0)
increases
Proof. We can write the non-centered orthant probability as a Gaussian integral
P(a: 0, > 0)
- (a- v) dx
R20
Without loss of generality, we consider En = Ejj = 1. Otherwise, we can rescale the variables and obtain new mean vector.
The covariance matrix Σ thus has eigenvalues A4 = 1+ Egy and x_ =1 - Ei with corresponding eigenvectors (1, 1) and (1, We can rotate the axis so that (1, becomes (1, We can then rescale the x axis by L/vA+ and the y axis by 1/V The positive orthant becomes cone centered around the origin and with opening angle given by
A+ X_
tan
which increases when Eij increases. The integral in polar coordinates becomes
[e 2 rdOdr.
Therefore, all that's left to show is that the range for any increases when a increases. See Fig- ure [0] for the illustration. Call ry the angle between one boundary of the cone C and the position vector of the center of the Gaussian in the transformed coordinates. We can find the length of the chord between the points of intersection between the circle and the boundary of the cone the difference between the distances c_, C+, of the segments OA and OB, respectively. Using the cosine
angle formula, find c+ d cos + v12 d² sin 7, and the chord length is vr² d² sin' y, which decreases as y increases. Furthermore, y increases as a increases. Using the same argument for the other boundary of the cone, concludes the proof.
28

---

Under review as a conference paper at ICLR 2020
C+
B
Figure 10: Transformed 2D Gaussian for proof Lemma H.3
The following lemma shows that for a vector of n Gaussian random variables, the probability two variables being simultaneously greater than O, given that all other any fixed signs, increases if their correlation increases.
Lemma H.4 Consider an n--dimensional Gaussian random variable with mean 0 and covariance E, x N(O,E) E). Consider, for any 1-1,1)"-2 the the following probability
ptd P(x: > 0, æ. 0lvk {i.jJonN > 0)
If Eig/ Ej increases, then pij increases.
Proof. We write P0 E[P(#; 0, 0l ). where f.. is the vector of without the ith and jth elements, and the expectation is over the distribution of Fijj conditioned on the condition vk & i, > O.
The conditional distribution P(r;, xy (agg) is also a Gaussian with a, generally non-zero mean f4, and covariance matrix given by
Σx Σ sj
Σ
jj
where 1 is independent of Eej. This means that increasing the Eye (keeping En and Egy fixed) will increase the correlation in E. Therefore, by Lemma H.3 P(x, 0, x Of increases, and thus pü increases.
Corollary H.5. An immediate consequence of Lemma H.4is that P(Vi, x: >0 P(x; > 0. > OlAk & (i.jaa > P(vk & {i,j)a > 0) increases when Eig/ / Ex increases, as P(yk & (i,j)a > 0) stays constant.
29

---

Under review as a conference paper at ICLR 2020
Lemma H.6. In the same setting as Lemma H.4 for covariance matrices Σ and E' of full rank, the following holds: for every i.j. Mig 2i implies Pk =P K'000 and Eng/ Ea >
Eggl V Ei implies Pid K..00
Pk Pii,00 where Pk is the probability measure corresponding to
covariance K.
Proof. The set S of all symmetric positive definite matrices is open convex subset of the set of all matrices. Therefore, it is path-connected. We can traverse the path between and Σ' through sequence of points such that the distance between point 2; and 2441 is smaller than the radius of a ball centered around 2; and contained in the set S. Within this ball, one can move between I; and 21+1 in coordinate steps that only change element of the matrix. Therefore we can apply Lemma H.4 to each step of this path, which implies the theorem.
Corollary H.7. Consider any set of points sli) E R with elements x(i) Let X be the m
data matrix with Xij = x/i);- For weight vector E IR" let y X w be the vector of real- valued outputs of an perceptron, with weights sampled from an isotropic Gaussian N In). If the
correlation between any two inputs increases, then P(T 0) P(E. 1()] = 0) increases
Proof. The vector y =, X,. w; is sum of Gaussian vectors (with covariances of rank 1), and therefore is itself Gaussian, with a covariance given by Σ XXT. If the correlation product between any two inputs increases, then applying Lemma H.6 and Corollary H.5 at each step, the theorem follows.
Lemma H.8. the uncentered moments of the distribution P(T increase, except for its mean (which is 2n-1) then (H( increases.
Proof. We consider the definition of the entropy, H, of a string (Definition and second terms by h; (1/lmaz) In(t/ (n(l/maa)) and h12 1/11mmmm In 1/ /mmx). We taylor expand by about 0:
3.5
We define the first
(1 t/tmaa)) Im(1 t/t t/tmaz))= t/t s/tmaw)
Σ k
+
tmaz
k
Emax
By symmetry, we see that h, (t) ho(tman - -t)), and we can thus Taylor expand h, around tmans
to give: (H(t)) = E (t + (tmax t)²)) = Σ 202zt 2kg
Σ 202z (t2k)
Because every 02k 24(28-1) is positive, we see that increasing every even moment increases the average entropy, (t)).
I BIAS DISAPPEARS IN THE CHAOTIC REGIME
In the paper we have analyzed fully connected networks with ReLU activations, and find general bias towards low entropy for a wide range of parameters. In a stimulating new study, Yang et al. (Yang& Salman 2019)) recently showed an example of network using an erf activation function where bias disappeared with increasing number of layers.
Here we argue that the reason for this behaviour lies the emergence of a chaotic regime, which does not occur for ReLU activations, but does for some other activation functions. In particular, the erf activation function is very similar to the tanh activation function used in an important series of recent papers that studied the propagation of correlations between hidden layer activations through neural networks, which they call "deep information propagation" (Poole et al.) 2016 Schoenholz et al. 2017 Lee al. 2018)). They find that the activation function the behaviour correlations. In particular, these papers show that for FCNs with tanh activation, there are distinet parameter regimes in the asymptotic limit of infinite depth: One in which
have dramatic impact
30

---

Under review as a conference paper at ICLR 2020
imputs approach perfect correlation (the ordered regime), and one in which the inputs approach 0 correlation (the chaotic regime). FCNs with ReLU activation do not appear to exhibit this chaotic regime, although they nevertheless have different dynamic regimes.
The particular example in (Yang & Salman 2019) was for owe = 4.0, and 0 = 0.0, a choice of hyperparameters that, for sufficient depth, lies deep in the chaotic regime. In this regime, inputs with initial correlations > -1 and < 1 will become asymptotically uncorrelated for sufficient depth, while initial correlations with equal to +11 stay fixed, as we show below. The network is therefore equally likely to produce any odd function (on the {- Boolean hypercube).
To confirm our conjecture above, performed experiments calculate the bias of tanh networks in both the chaotic and ordered regime, which we show in Figure I1 We obtain the expected results: in the chaotic regime, the bias gets weaker with number of layers, while in the ordered regime, just as was found for the ReLU activation in the main text, the bias remains, and the trivial functions gain more probability. These experiment illustrate for tanh activation that in either the chaotic or ordered regime, the a-priori bias of the network becomes asymptotically degenerate with depth, either by becoming unbiased, or too biased.
layas
layes
layer
layers
19aers
RRyerr
lavers
layers
10
30
10.4
0017
1017
1211
(a) Chaotic regime, du 4.0, 0% = 0.0
(b) Ordered regime, due 4.0, db = 10.0
Figure 11: Probability versus rank (ranked by probability) of different Boolean functions 131, + {-1,1} produced by a neural network with 1 hidden layer with tanh activation, and weights distributed by Gaussian with different variance hyperparameters chosen lie in the chaotic (a, = 0.0) and ordered (a, 10.0) regimes.
We now explain that a simple extension of the analysis of (Poole et al., 2016) shows that, for the special case of of = 0.0 and tanh activation function, initial correlations equal to 1 stay fixed. This happens because the RHS in Equation 5. describing the propagation correlation in (Poole al., 2016) (which we replicate in Equation (23) below) is odd on the correlation d (which represents the covariance between a pair of activations for inputs 1 and 2 at layer / - 1) when σ, = 0. In addition the fixed point they identified for the correlation being +1 there is therefore another unstable fixed point at 1.
ow; di = C (clé" ..t , 1-1 ( 0b) = oz /
Dz, De20i (ui) di (uz) + o
(23)
U1 v di 21
V V022" 1-1
d2 -1- (dzz)) 22
(24)
where c12 = 1'p(('119 (-2 and 21, 22 are independent standard Gaussian variables, and the qı and 422 are the variances of the activations for input 1 and input 2, respectively. This fixed point at -1 ensures that points which are parallel but opposite (like opposite corners the (-1, 13" hypercube) will stay perfectly anti-correlated. This agrees with the expectation that the erf/tanh network with og = can only produce odd functions, as the activations are odd functions. However, any other pair of points becomes uncorrelated, and this explains why every (real valued) function, up to the oddness constraint, is equally likely. This also implics that every odd Boolean function is equally likely, the region of function space satisfying the oddness constraint has the same shape within
31

---

Under review as a conference paper at ICLR 2020
every octant corresponding to an odd Boolean function. This is because the region in octant related to that on another octant by simply changing signs of elements of the function vector (a reflection transformation).
will be interesting to study the effect these different dynamic regimes, for different activation functions, simplicity bias.
J BIAS TOWARDS LOW ENTROPY IN REALISTIC DATASETS AND ARCHITECTURES
In the main text demonstrate bias towards low entropy only for the Perceptron, where we can prove certain results rigorously, and for fully connected network (FCN). An obvious question is: does this bias persist for other architectures or data sets? In this Appendix we show that similar bias indeed occurs for more realistic datasets and architectures.
We perform experiments whereby we sample the parameters of convolutional neural network (CNN) (with single Boolean output), and evaluate the functions they obtain on subsets of the standard vision datasets MNIST or CIFARIO. Our results suggest that the bias towards low en- tropy (high class imbalance) is generic property of ReLU-activated neural networks. This has in fact been pointed out previously, either empiricallyPage Page (201)), or for the limit of infinite Leet et al. (2018). Extending analytic results to these more complicated architectures and datasets is probably extremely challenging. but perhaps possible for some architectures, by analyzing the infinite-width Gaussian process (GP) limit.
32

---

Under review as a conference paper at ICLR 2020
30000
062
Robubalts
20000
082
D40
(a) MNIST, o. 0.0
(b) MNIST,,, 1.0
12000
12000
10000
4200
4200
100
J00
(c) CIFARIO, uncentered.or, = 0.0
(d) CIFARIO, centered, ob = 0.0
Figure 12: Probability of different values of T for CNN with 4 layers, no pooling, and ReLU activations. The parameters were sampled 10t times and the network was evaluated a fixed random sample 100 images from MNIST CIFARIO. The parameters were sampled i.i.d. from Gaussian, with paramaters ou = 1.0, and σ = 0.0, 1.0. The input images from CIFAR10 where either left uncentered (with values in range [0, 1)) (uncentered), or where centered by substracting the mean value of every pixel (uncentered).
12000
162
Prdbabitty
Dobabbity
0300
4000
10
2000
10
(a)
(b)
Figure 13: Probability of different values of T for the perceptron with n 7 input neurons and dy = 0.0. The parameters were sampled 10a times and the perceptron evaluated random subsample of size 64 of either {0, 1)" ((a)) or {-1,1}" (()). The weights were sampled i.i.d. from Gaussian, with paramaters Tue 1.0.
33

---

Under review as a conference paper at ICLR 2020
K EFFECT OF THE BIAS TERM ON THE PERCEPTRON ON CENTERED DATA
Here we show that the bias towards low entropy is recovered for the perceptron on centered (1 (J") inputs, when the bias term is increased.
0.0
0.1
G 1.0
0 3.0
Probabilty
10
10.5
10
W
Figure 14: σb 1.0
Figure 15: Probability of different values of T for the perceptron evaluated on 111 inputs and varying ab = 0.0. The parameters were sampled 10" times. The weights were sampled i.i.d. from Gaussian, with paramaters ow 1.0.
L CONNECTION BETWEEN THE BIAS AT INITIALIZATION, INDUCTIVE BIAS AND GENERALIZATION
In this appendix we describe more formally the connection between the distribution over functions initialization and the inductive biases, when training with optimizer like SGD, and the link to generalisation.
Following the ideas in (Valle-Pérez al. 2018), will first formally introduce exact Bayesian classifier for classification.
Let P(0) be prior distribution over parameters, which induces prior distribution over Boolean functions given by P(f) == p(0,), where we define O to be the set of parameter values that produce the function f. We assume 0-1 likelihood P(D) for data D { y:) defined as
(xf()) =
P(DI)) 0 otherwise
The likelihood on parameter space defined as P(D == P(D)fe), where fo is the function produced by parameter 6. The Bayesian posterior function space then
P(fD) = P(DIf)P())
P(D)
where P(D) = ((D())((() is the marginal likelihood of the data. In parameter space, the posterior is just P)O P(O)
P(D)
For an exact Bayesian algorithm, like the one described above, the inductive bias (the preference of some functions versus others, for given dataset), is fully encoded in the prior P(f).
The connection with generalisation for the Bayesian learner described above can be expressed through the PAC-Bayes theorem (McAllester 1999 Valle-Pérez.ed al. 2018) which gives bounds
34

---

Under review as a conference paper at ICLR 2020
the expected generalization performance that depend on the marginal likelihood, which is just the probability of the labelling of the data under the prior distribution. In this picture, the distribution P(f) at initialization determines the full inductive bias, but only to extent to which the training algorithm approximates the Bayesian posterior, with P(f) as its prior.
In (Valle-Pérez et al. 2018) trained on CIFAR, and also for an FCN on Boolean data. The success of these bounds indirect evidence that the training algorithm (here different variants of SGD) is indeed behaving somewhat like a Bayesian sampler.
shown that PAC-Bayes bounds work well for FCN and a CNN
We aware that the claim in the paragraph above may be controversial, given that there is also literature arguing that SGD itself is an important source of the inductive bias of deep learning, So is important also find direct evidence that that stochastic gradient descent (SGD) approximates the Bayesian posterior with prior P(f).
In Valle-Pérez et al. 2018), Fig 4, the probability P(f) was compared the probability that two variants of SGD generate functions, for the Boolean system. Good agreement was found, suggesting that SGD indeed samples functions with probability close P(J). at least on log scale and for these problems.
Here we provide further evidence for this behaviour Figure T6] where we compare the probabili- ties of finding different Boolean functions upon training fully connected neural network with SGD to learn relatively simple Boolean function versus the probabilities of obtaining those functions by randomly sampling parameters until they fit the data (which we refer to as approximate Bayesian inference, or ABI). We see that most functions the sample show very similar probabilities to be obtained by either SGD or ABI.
35

---

Under review as a conference paper at ICLR 2020
10-0
0.8
10-1
SGD probabilities
0.6
10
0.4
10
0.2
10
0.0
10-5
10-4
10-3 ABI probabilities
10-2
10-1
Probabilities of finding functions by SGD versus by randomly sampling parameters (ABI), conditioned on 100% training accuracy, for a training set of size 32 for learning a Boolean function on 137 with a fully connected neural network with layer widths (7,40,40,1). Both the parameter sampling and SGD initialization where ii.d. Gaussians with weight variances of 1 /layee width), and bias variances of 1. SGD used a batch size of 8, and cross-enrrppy loss, and reached. Histogram shows number of functions each bin, and is normalized row-wise, so that a value of 1.0 corresponds to the maximum number of functions the row, and 0.0 corresponds 0.0 functions. These are mapped colors from yellow (1.0) to purple (0.0) as shown in the colorbar.
Figure 16:
was stopped
100% accuracy
Although we don't yet have a formal theoretical explanation of this correlation, we can make the following heuristic argument: The parameter-functio map (defined in Section 33, is hugely biased, typically over many orders of magnitude. The basins of attraction of the functions are also likely to vary over many orders of magnitude in size, so that SGD much more likely to find functions with larger P(f), which have larger basins, than functions with smaller P(f) (See also (Wu et al. 2017 This argument would be sufficient to show that the bias upon initialisation (or equivalently upon uniform random sampling of parameters) has an important effect on the functions that SGD finds. However, empirically we find a stronger result, which is that. SGD approximately samples functions with probability directly proportional to P(f). This agreement suggests another stronger ansatz: As long as SGD samples the parameters more or less uniformly (within the region of likelihood 1), then function space the functions samples with probabilities of the same orders of magnitude as D).
Finally, preliminary results MNIST and CIFAR data sets (using the GP approximation) exhibit similar scaling to what observed in Figure 16 We are currently working further on this important and complex question of how SGD samples functions.
36

---

Under review as a conference paper at ICLR 2020
M EFFECT OF BIAS ON LEARNING
The effect of inductive biases such as the ones we discuss on learning is a vast and open research project. particular, we expect that bias towards low entropy should play bigger role when trying to learn class-imbalanced data. In class-imbalanced problems, one is often interested in quantities beyond the raw test accuracy. For example, the sensitivity (the fraction of test-set misclassification on the rare class), and the specificity (the fraction of test-set misclassifications on the common class). Furthermore, the use of tricks, like oversampling the rare class during optimisation, makes the formal analysis of practical cases even more challenging. In this section, we show preliminary results illustrating some of the effects that entropy bias in PJ)) can have on learning.
In the experiments, we shift the bias term of the output neuron b + D' = b + shift. This causes the functions at initialisation to have distributions P(T) which may be biased towards higher or lower values of 7 (mapping most inputs to 0 or 1). We measure the average (T") for different choices of the shift hyperparameter, and train the network, using SGD, on class-imbllanced dataset. Here we perform this experiment dataset consists of sample of either MNIST (10 classes) or balanced EMNIST (47 classes), where single class is labelled 0, and the rest labelled 1.
CNN with 4 layers (and no pooling), and a FCN with 1 layer. The
We see in Figure 17 that values of the shift hyperparameter producing large values (T) give higher test accuracy. We suggest that this could be because the new parameterisation induced by the shifted bias term 1D causes the inductive bias is more "atuned" to the correct target function (which has a class imbalanced of 1:10 and 1:47, respectively for MNIST and balanced EMNIST). However, the detailed shape of the curve seems architecture and data dependent. For instance, for the FCN (with ReLU tanh activation) trained on MNIST we find clear accuracy peak around the true value of (T),, but not for the others.
We also measured the sensitivity and 99% specificity (found by finding the smallest threshold value of the sigmoid unit, giving 99% specificity). Sensitivity seems to follow less clear pattern. For two the experiments, it followed the accuracy quite closely, while for FCN trained on MNIST peaked around a positive value of the ship hyperparameter.
These results suggest that looking at architectural changes that affect the entropy bias of P()) can have significant effect on learning performance for dlass-imallanced tasks. For example, for the tanh-activated FCN, increasing the shift hyperparameter above improves both the accuracy and sensitivity significantly. As mentioned at the beginning, understanding the full effect of entropy bias, and other biases on Pff), on learning is a large research project. In this paper, we focused on explaining properties of P(f), while only showing preliminary results the effect of these properties on learning.
Note that the shifted bias reparameterisation is equivalent to shifted initializattinn in the original parame- terisation. For complex reparameterisation, this may be the case
37

---

Under review as a conference paper at ICLR 2020
Sen2ivity Accurasy 77
0.
D420
Accuricy
0368
0575
TOX 15teccurd
accuroo
0350
60
0.6
895
0500
0.15
03
shitt
21it
(a) CNN with ReLU,MNIST
(b) with ReLU, MNIST
500200iity
100
SensEbity
100
0.5
0.00
075
0.75
0.7
0A-
200
0.50
40
0.6
045
102
83
0.40
0.5
(c) FCN with ReLU, EMNIST
(d) PCN with tanh, MNIST
Figure 17:
Test accuracy, sensitivity (at 99% specificity). and (T) versus the shift hyperparameter (shift of the bias term in the last layer), for different architectures and datasets. The networks were trained with SGD (batch size 32, cross entropy loss), until reaching 100% training accuracy. Accuracies and sensitivities
averages over 10 SGD runs with random initializations (Ø, 0.0, T. = 1.0). The dataset had size 100 for MNIST, and 500 for EMNIST. Images are centered, so pixel values have their mean the whole dataset substracted. The values of (T") are estimated from 100 random parameter samples and evaluating on the same data we train the network on.
38


Reviews:
[{"review_id": "rJxN9w_TYr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 studies the a-priori bias of a feed-forward neural network when the weights are initialised uniformly at random and independent of the network architecture. The paper claims that this initialisation leads to biases towards low entropy functions when the input and output are binary values. \n\nThe paper starts with a single layer perceptron without the bias term, and generalises the analysis to networks with multiple hidden layers and ReLU activations. The proposed approach seems rigorous, but I have a hard time to follow the paper as many of the important results are presented in appendix. In addition, the analysis is based on a feed-forward neural network with binary inputs and a single binary output, it is not clear whether these results can be generalised to architectures of practical importance such as convolutional/recurrent neural networks. Overall an interesting piece of work that contributes to the understanding of deep neural networks.\n\n\nMinor comments:\n\nSection 4.2: \n\"as as predicted by Eq. 1\" -> remove duplicated \"as\"\n\nSection 5.2: \n\"some interesting recent work\" -> \"Some ...\"\n\"produce.At first sight\" -> add a space before \"At\"\n\"If there is not bias\" -> \"If there is no bias\"", "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": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HyxddGNAtH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 authors study the behavior of simple neural networks at initializations. Particularly, the authors show that at initializations, neural networks tend to be functions with high class imbalance.\nFurther, the authors show that how such conclusion would be reached with or without a bias term, with different number of hidden layers, with change of activation functions. \nThe work is fairly interesting, yet the motivation is less clear.\nThe conclusion that study of such initializations can help understand the generalization power is not convincing.\nDespite that neural networks at initializations are biased towards low entropy functions, it’s not clear with training on a dataset with an optimizer, how much we can conclude about the generalization power.\nOverall the paper is well written.\n\nBelow are some more detailed comments:\n1) In the Introduction and the first paragraph of Section 2, the authors motivate by describing how important it is to understand the inductive biases. Yet the study is about the behavior of a random initialization. It would be nice to tie these two better; or motivate from another angle, other than the inductive bias. To my reading, the sentence “what the inductive biases … are, and how they arise” is not well supported because I still don’t follow what the inductive biases are from reading the paper except that a random initialization likely be low entropy functions.\n\n2) In Figure 3(a), 4(b,c,d), there is a spike at the mid-point of t. Though not as high as the extreme points, this is contradictory to the main conclusion. It would nice to add discussions.\n\n3) It would be nice to add experiments to study how such bias at initializations would impact the model training.\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 assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "BJevQEK7jr", "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": "The topic of the paper is the inductive bias of neural networks. The authors study a simple model, namely a perceptron with no bias term viewed as a mapping from {0,1}^n->{0,1}. They show that initializing weights with a distribution that is symmetric under coordinate sign flips corresponds to an initialization in function space that is biased towards low-entropy functions. They also exhibit empirical evidence that by adding a bias term, or by using multiple layers, this tendency towards low entropy appears to increase. They also prove a bound on the minimal size of a network in order for it to represent all boolean functions. Finally, they prove a result that suggests that for ReLU networks with infinite widths the bias towards low-entropy function does indeed increase with depth. \n\nMy main concern regarding this paper is that the claim in the title and the statement of Theorem 4.1 seem to rely crucially on the fact that the functions are viewed with input as {0,1}^n. The origin of the \"simplicity\", in the basic case that the authors address (perceptrons with no bias) appears to be a consequence that hyperplanes through the origin are quite likely to classify input points in {0,1}^n similarly. If one switches to a symmetric domain, for example {-1,1}, the effect in this setting completely disappears. The authors actually mention this in Section 5, noting that the expressivity of the perceptron is much lower for centered inputs. However, this to me suggests that Theorem 4.1 is not capturing any significant aspect of neural networks (in fact, the statement is a property of how linear hyperplanes to separate {0,1}^n, not neural networks). I may be mistaken, but I would like the authors to clarify this point.\n\nAnother concern is related to Theorem 5.5. This might be a more substantial result, but it is difficult to interpret and its implications are not discussed. Understanding the effect of depth on the \"simplicity bias\" seems to me an important problem, but for some reason Theorem 5.5 (which deals with deep neural networks rather than linear perceptrons) is emphasized much less than Theorem 4.1. Why is this the case?\n\nThe paper is well-written but not always very clear. In particular, notation is not always defined and the authors use on notions from complexity theory that are not introduced (e.g., Lepel-Ziv complexity).\n\nOther comments: \n\n* Is the set F_t is defined as set of all functions with assigned \\mathcal T, but later this seems to be restricted to the functions expressible by a network/perceptron.\n* Definition 3.5: this defined the entropy H(f) of a function but then write H(p). It should probably be H(f) = -plog p - (1-p)log(1-p) where p = \\mathcal T(f), right?\n* Definition 3.6: some context or references for this definition could be useful.\n* Regarding the fact that functions in F_t are not uniform, shouldn't the distribution be the same for isotropic weight distributions? Assuming the distribution of w/|w| is uniform on the sphere, a more precise description of  P(f) seems possible\n* Section 4.3: what is the \"rank\" in this setting? Isn't the parameter a vector w in R^n?\n* Some typos: Definition 3.1 w_l \\in R^{n_{l+1}}, \",.\" in the beginning of Section 5, several in the last paragraph of Section 5.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "N/A", "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_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This article studies the inductive bias in a simple binary perceptron without bias, showing that if the weight vector has a symmetric distribution, then the cardinality of the support of the represented function is uniform on 0,...,2^n-1. Since the number of possible functions with support of extreme cardinality values is smaller, the result is interpreted as a bias towards such functions. Further results and experiments are presented. The reviewers found this work interesting and mentioned that it contributes to the understanding of neural networks. However, they also expressed concerns about the contribution relying crucially on 0/1 variables, and that for example with -1/1 the effect would disappear, implying that the result might not be capturing a significant aspect of neural networks. Another concern was whether the results could be generalised to other architectures. The authors agreed that this is indeed a crucial part of the analysis, and for the moment pointed at empirical evidence for the appearance of this effect in other cases. The reviewers also mentioned that the motivation was not very clear, that some of the derivations were difficult to follow (with many results presented in the appendix), and that the interpretation and implications were not sufficiently discussed (in particular, in relation to generalization, missing a more detailed discussion of training). This is a good contribution and the revision made important improvements on the points mentioned above, but not quite reaching the bar. 
Decision: Reject