Inductive Bias of Deep Convolutional Networks through Pooling Geometry

By Nadav Cohen, Amnon Shashua. 2016

142 citations recorded by the source corpus.

Our formal understanding of the inductive bias that drives the success of convolutional networks on computer vision tasks is limited. In particular, it is unclear what makes hypotheses spaces born from convolution and pooling operations so suitable for natural images. In this paper we study the ability of convolutional networks to model correlations among regions of their input. We theoretically analyze convolutional arithmetic circuits, and empirically validate our findings on other types of convolutional networks as well. Correlations are formalized through the notion of separation rank, which for a given partition of the input, measures how far a function is from being separable. We show that a polynomially sized deep network supports exponentially high separation ranks for certain input partitions, while being limited to polynomial separation ranks for others. The network's pooling geometry effectively determines which input partitions are favored, thus serves as a means for controlling the inductive bias. Contiguous pooling windows as commonly employed in practice favor interleaved partitions over coarse ones, orienting the inductive bias towards the statistics of natural images. Other pooling schemes lead to different preferences, and this allows tailoring the network to data that departs from the usual domain of natural imagery. In addition to analyzing deep networks, we show that shallow ones support only linear separation ranks, and by this gain insight into the benefit of functions brought forth by depth - they are able to efficiently model strong correlation under favored partitions of the input.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

Citations in the corpus

Towards Robust Vision Transformer (2021, background): “As shown by previous works [4], such a design contributes to the expressiveness and generalization performance of the network.”
The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks (2018, background): “Cohen & Shashua (2016) show that the inductive bias embedded in the structure of a deep network determines the kinds of data that it can separate more parameter-efficiently than can a shallow network; although Cohen & Shashua (2016) focus on the pooling geometry of convolutional networks, a similar…”
Weight Agnostic Neural Networks (2019, background): “Convolutional networks [24, 56] are especially suited for image processing [16].”
Learning from Protein Structure with Geometric Vector Perceptrons (2020, methodology): “Successful applications of deep learning are often driven by techniques that leverage the problem structure of the domain—for example, convolutions in computer vision (Cohen & Shashua, 2017) and attention in natural language processing (Vaswani et al., 2017).”
The Lottery Ticket Hypothesis at Scale (2019, background): “Frankle & Carbin conjecture that the structure of winning tickets (i.e., the unpruned weights within the full network) encode an inductive bias (Cohen & Shashua, 2016) tailored to the task at hand.”
Rethinking Spatial Dimensions of Vision Transformers (2021, background): “Some studies [6, 26, 5] show that the pooling layer contributes to the expressiveness and generalization performance of the network.”
Tensor Networks for Dimensionality Reduction and Large-scale Optimization: Part 2 Applications and Future Perspectives (2017, methodology): “Example 11 Consider a generalized CP decomposition, which corresponds to a shallow rectifier network in the form [Cohen and Shashua, 2016] W c = R ÿ r=1 λ (c) r ¨ (w (1) r ˝ρ w (2) r ˝ρ ¨ ¨ ¨ ˝ρ w (N) r ), (4.30) where the coefficients λ(c)r represent weights of the output layer, vectors w(n)r P…”
iSegFormer: Interactive Segmentation via Transformers with Application to 3D Knee MR Images (2021, background): “Although these CNN-based meth-ods have achieved excellent performance, they suffer from limited receptive ﬁelds and cannot learn global and long-range semantic information well due to the inductive bias of locality and weight sharing [8].”
Plausible May Not Be Faithful: Probing Object Hallucination in Vision-Language Pre-training (2022, background): “We conjecture that the inductive biases (Cohen and Shashua, 2017) of the Convolutional Neural Network (CNN), such as locality and translation invariance, weaken the connection of different characteristics of a single object and thus lead to more hallucination.”
NeuralScale: Efficient Scaling of Neurons for Resource-Constrained Deep Neural Networks (2020, methodology): “This finding indicates that pruning does introduce inductive bias [5] and adds evidence on the suitability of using pruning as an architecture search technique.”
Which transformer architecture fits my data? A vocabulary bottleneck in self-attention (2021, background): “…the separation rank has been established as a measure of dependencies modeled by deep convolutional and recurrent networks w.r.t. their inputs (Cohen & Shashua, 2017; Cohen et al., 2017; Levine et al., 2018a), and tied to quantum entanglement measures for proving that these deep learning…”
Generalization Error of Invariant Classifiers (2016, unknown): “The role of convolutions and pooling in the context of natural images is also studied by Cohen and Shashua (2016).”
Implicit Regularization in Deep Learning May Not Be Explainable by Norms (2020, background): “[22, 19, 20, 23, 77, 54, 24, 9, 55]), and has also demonstrated promising results in practice (see [18, 21, 78]).”
Limits to Depth Efficiencies of Self-Attention (2020, background): “Importantly, the separation rank has been established as a measure of dependencies modeled by deep convolutional and recurrent networks w.r.t. their inputs [Cohen and Shashua, 2017, Levine et al., 2018a,b].”
On the Expressive Power of Overlapping Architectures of Deep Learning (2017, methodology): “Though the results in Cohen and Shashua (2017) are strictly based on the matricization rank of the coefficients tensors, they can be transferred to the matricization rank of grid tensors as well.”
CoTr: Efficiently Bridging CNN and Transformer for 3D Medical Image Segmentation (2021, background): “to capture the long-range dependency, due to the inductive bias of locality and weight sharing [6].”