PaperlayerView exact revision on arXiv

Source-linked AI summary

Deep Learning and Quantum Entanglement: Fundamental Connections with Implications to Network Design

Yoav Levine, David Yakira, Nadav Cohen, Amnon Shashua

arXiv:1704.01552v2cs.LGcs.NEquant-ph

TL;DR

The paper addresses limited understanding of the inductive bias encoded in convolutional networks. It connects ConvAC functions to quantum many-body wave functions and represents ConvACs as Tensor Networks. Min-cut analysis then relates channel counts to modeled input correlations, with applicability to conventional ConvNets demonstrated experimentally.

  • Problem

    Formal understanding of the inductive bias encoded in convolutional-network architecture remains limited.

    Source: §1 · p. 1

  • Method

    The paper maps ConvAC functions to quantum many-body wave functions and Tensor Networks, then analyzes their expressive ability using entanglement measures and graph-theoretic min-cuts.

    Source: §1 · p. 3, §9 · p. 29

  • Results

    Min-cut bounds connect channel counts to the correlations a ConvAC can model, with tight bounds under a general channel setting and experimental demonstration of applicability to ConvNets.

    Source: §1 · p. 3

  • Takeaways & Limitations

    Channel counts can be used to tailor a network’s inductive bias when prior knowledge identifies correlations among input variables.

    Source: §9 · p. 29

    For general, more natural data, the best way to define the relevant input correlations remains unclear.

    Source: §9 · p. 30

Abstract

from arXiv · show

Deep convolutional networks have witnessed unprecedented success in various machine learning applications. Formal understanding on what makes these networks so successful is gradually unfolding, but for the most part there are still significant mysteries to unravel. The inductive bias, which reflects prior knowledge embedded in the network architecture, is one of them. In this work, we establish a fundamental connection between the fields of quantum physics and deep learning. We use this connection for asserting novel theoretical observations regarding the role that the number of channels in each layer of the convolutional network fulfills in the overall inductive bias. Specifically, we show an equivalence between the function realized by a deep convolutional arithmetic circuit (ConvAC) and a quantum many-body wave function, which relies on their common underlying tensorial structure. This facilitates the use of quantum entanglement measures as well-defined quantifiers of a deep network's expressive ability to model intricate correlation structures of its inputs. Most importantly, the construction of a deep ConvAC in terms of a Tensor Network is made available. This description enables us to carry a graph-theoretic analysis of a convolutional network, with which we demonstrate a direct control over the inductive bias of the deep network via its channel numbers, that are related to the min-cut in the underlying graph. This result is relevant to any practitioner designing a network for a specific task. We theoretically analyze ConvACs, and empirically validate our findings on more common ConvNets which involve ReLU activations and max pooling. Beyond the results described above, the description of a deep convolutional network in well-defined graph-theoretic tools and the formal connection to quantum entanglement, are two interdisciplinary bridges that are brought forth by this work.

1. Introduction

The paper addresses limited understanding of the inductive bias embedded in convolutional-network architecture. It connects ConvACs to quantum wave functions and Tensor Networks, then uses entanglement and graph-theoretic min-cut analysis to relate channel counts to modeled correlations.

1. Introduction

  • Earlier work used separation rank to show that pooling geometry favors some input partitions with exponentially high rank, while others require exponentially large networks.The present paper builds on this line of inquiry with entanglement and min-cut analysis.Source: §1 · pp. 2–3
  • A ConvAC function is structurally equivalent to a many-body quantum wave function, allowing entanglement measures to quantify the network’s ability to model input correlations.The paper says these measures subsume algebraic notions such as separation rank.Source: §1 · p. 2
  • Representing a ConvAC as a Tensor Network makes graph-theoretic analysis meaningful, since ordinary network node-and-edge depictions are not graphs in the graph-theoretic sense.For Tensor Networks, max-flow and min-cut have meaningful interpretations.Source: §1 · pp. 2–3
  • Min-cut analysis upper-bounds a ConvAC’s ability to represent correlations between input regions, and the bound is tight under a general setting of channel numbers.The authors prove the results for ConvACs and demonstrate their applicability to ConvNets with ReLU activations and max pooling through experiments.Source: §1 · p. 3
  • Channel-count bounds connect a network’s inductive bias to prior knowledge about the task and can guide architecture design.The paper relates this analysis to quantum min-cut max-flow bounds from physics.Source: §1 · p. 3

2. Preliminaries

The preliminaries introduce tensor concepts and ConvACs, a convolutional-network family whose tensor structure supports the paper’s later analysis. ConvACs use linear activations and product pooling rather than common nonlinear activations and average or max pooling.

2. Preliminaries

  • ConvACs are convolutional networks with linear activations and product pooling, rather than common nonlinear activations and average or max pooling.The authors select them for analysis because their tensorial structure resembles that of a quantum many-body wave function.Source: §2 · p. 4, §2.2 · p. 5

2.1. Concepts from Tensor Analysis

  • Tensor analysis treats tensors as multidimensional arrays, with matricization rearranging a tensor as a matrix and tensor products combining tensors into higher-order tensors.A tensor product of two vectors is their rank-1 outer product.Source: §2.1 · pp. 4–5

2.2. Convolutional Arithmetic Circuits

  • A ConvAC applies representation functions to image patches, then uses 1×1 convolutions, product pooling, and a final linear layer to produce class scores.With pointwise affine activations, its representation layer reduces to a standard convolutional layer; its convolutional weights form a tensor.Source: §2.2 · pp. 5–6
  • CP decomposition corresponds to a shallow network with global pooling, while restricted HT decomposition corresponds to a deep network with 2×2 pooling and has an exponential expressiveness advantage over the shallow form.The paper uses these tensor decompositions in its later connection between ConvACs and Tensor Networks.Source: §2.2 · pp. 6–7

3. Quantum Wave Functions and Convolutional Networks

The paper formalizes an analogy between many-input learning functions and quantum many-body wave functions. It establishes a structural equivalence between a ConvAC function and a wave function by matching their tensor representations.

3. Quantum Wave Functions and Convolutional Networks

  • The paper sets up a correspondence between functions mapping many inputs to outputs and quantum wave functions describing relations among many particles.The ConvAC’s tensorial description enables the structural connection.Source: §3 · p. 7

3.1. The Quantum Many-Body Wave Function

  • The quantum discussion is restricted to real vector spaces and finite-dimensional local Hilbert spaces, whose tensor product represents the joint system.For equal local dimensions, the joint-state coefficients form a tensor indexed by the local basis choices.Source: §3.1 · pp. 7–8

3.2. Equivalence to a Convolutional Network

  • A ConvAC score for one class corresponds to the projection of a product state, with the convolutional-weight tensor analogous to the wave function’s coefficient tensor.This equivalence supplies a basis for analyzing network expressiveness through properties of its underlying tensor.Source: §3.2 · pp. 8–9

4. Measures of Entanglement and Correlations

The section transfers quantum entanglement measures to convolutional networks to quantify how well they model correlations across input partitions. It connects the preferred partition to the input’s correlation structure and motivates representing the network with Tensor Networks.

4.1. Measures of Quantum Entanglement

  • Entanglement measures based on singular values quantify correlations across a partition, with minimal values for separable states and larger values for more complex correlations.The Schmidt number is the matricization rank; entanglement entropy and the geometric measure are also described.Source: §4.1 · p. 10

4.2. Correlations Modeled by a Convolutional Network

  • For a ConvAC, entanglement measures defined from the convolutional weights tensor’s partition-specific matricization quantify the correlations the network can model.Higher measures correspond to more elaborate correlations between the two input groups; minimum entanglement corresponds to a function that factors into two parts, implying independence in a statistical setting.Source: §4.2 · p. 11
  • Natural images favor high interleaved-partition entanglement for neighboring-pixel correlations, while symmetric images such as faces favor high left-right-partition entanglement.The channel numbers in each layer can be tailored to control this inductive bias.Source: §4.2 · pp. 11–12, §4.1 · p. 11
  • The convolutional weights tensor has M^N entries, motivating Tensor Networks that use correlation knowledge to represent exponentially complex functions with polynomial resources.The weights tensor encapsulates the correlations of both the wave function and the ConvAC function.Source: §4.2 · p. 12

5. Tensor Networks and Tensor Decompositions

Tensor Networks and tensor decompositions offer ways to represent high-order tensors without storing all their entries directly. The section introduces Tensor Network structure and relates ConvAC weight tensors to decompositions whose ranks correspond to channel counts.

5. Tensor Networks and Tensor Decompositions

  • Storing a general order-N tensor takes exponential space, while a Tensor Network can represent it through polynomially many parameters, though parameter reduction is not guaranteed.Whether a decomposition reduces parameters depends on the tensor’s rank and how well the decomposition fits its correlations.Source: §5 · p. 12

5.1. Introduction to Tensor Networks

  • A Tensor Network contracts connected tensor indices to produce a tensor on its open indices; a tensor train can represent an order-N tensor with parameters linear in N.In the matrix-vector example, contracting the shared index yields the vector u = Mv.Source: §5.1 · p. 14
  • A Tensor Network’s architecture is determined by internal-tensor connectivity and edge bond dimensions, and its suitability depends on the correlations to be represented.The section maps ConvACs into Tensor Network form, bringing a trainable architecture into that formalism.Source: §5.1 · p. 14, §5.2 · p. 16

5.2. Tensor Decompositions

  • Tensor Networks express tensors through index contractions, whereas tensor decompositions use tensor products of lower-order tensors; both target efficient representation.The section notes that their structural differences are mostly semantic.Source: §5.2 · p. 15
  • The CP decomposition corresponds to a one-hidden-layer ConvAC with global pooling, while the deep ConvAC corresponds to a restricted hierarchical Tucker decomposition.The restriction reflects pooling only entries from the same channel; the recursive decomposition’s level-l rank equals the ConvAC channel count at that layer.Source: §5.2 · pp. 15–16

6. A Convolutional Network as a Tensor Network

The section maps ConvAC computations into Tensor Networks (TNs), preserving their computation while exposing a graph structure for analysis. The shallow and deep constructions encode same-channel pooling, and the deep TN’s bond dimensions equal the corresponding channel counts.

6. A Convolutional Network as a Tensor Network

  • The TN mapping is not proposed as a more efficient ConvAC representation; it provides a graph structure for applying graph-theoretic analyses to deep networks.The ConvAC’s tensor operations become TN contractions over a graph.Source: §6 · p. 17

6.1. Tensor Network Construction of a Shallow Convolutional Network

  • In the shallow construction, a δ tensor contracts with the convolutional weight matrices to enforce same-channel pooling in the CP-decomposition TN.The δ tensor is 1 only on its super-diagonal, making each matrix’s kth row pair with the other matrices’ kth rows.Source: §6.1 · p. 17, Figure 4 · p. 18

6.2. Tensor Network Construction of a Deep Convolutional Network

  • For a deep ConvAC, the TN represents the HT decomposition with same-channel pooling, and contracting it yields the network’s class scores.For N = 8, the weight tensor forms the upper block and the rank-1 input tensor the lower block.Source: §6.2 · pp. 18–19, Figure 5 · p. 19
  • Incremental TN contraction from the input layer upward exactly reproduces the level-by-level deep ConvAC computation, and the construction generalizes to other pooling schemes.The pooling-window size determines the number of edges incident to the δ tensors from below.Source: §6.2 · p. 19
  • Each deep TN level’s bond dimension equals its ConvAC channel count, supporting prescriptions for matching channel numbers to input correlations.The paper uses this correspondence in later sections to discuss fitting the correlations modeled by the network to input correlations.Source: §6.2 · pp. 19–20

7. How the Number of Channels Affects the Expressiveness of a Deep Network

The section maps ConvACs to Tensor Networks so graph cuts can bound correlation expressivity and guide channel allocation. It also relates this analysis to depth efficiency.

7.1. The ConvAC Tensor Network as a Graph

  • The ConvAC-weights Tensor Network becomes a graph by assigning each edge its bond dimension, equal to the corresponding ConvAC layer’s channel count.The graph adds virtual vertices for input edges and omits the output edge, which does not affect flow between input groups.Source: §7.1 · p. 21

7.2. Bounds on the Entanglement Measure

  • A ConvAC’s input-correlation rank across a partition is upper-bounded by the minimum product of bond dimensions over cuts separating that partition.The bound also indicates when channel numbers leave the network too weak to model a desired correlation structure.Source: §7.2 · p. 23
  • For general channel arrangements, Theorem 2 guarantees rank at least that of a network whose channel numbers are rounded down to powers of p; the upper bound is saturated when channel numbers are powers of p.The authors report simulations indicating that deviations from the upper bound are rare and small.Source: §7.2 · p. 23

7.3. Implications - How to Distribute the Number of Channels in a Deep Network

  • Channel allocation can target input correlations: more lower-layer channels suit short-range correlations, while deeper-layer channels matter for long-range correlations.For contiguous partition segments of length ξ, the minimum cut may involve only channel numbers through layer ceil(log2 ξ).Source: §7.3 · p. 25
  • For features of characteristic size D, channel numbers through layer ceil(log2 D) matter more than those in deeper layers in a ConvAC with pooling windows of size 2.The paper says experiments extend these theoretical findings to ConvNets with ReLU activations and average or max pooling.Source: §7.3 · p. 25

7.4. Reproducing Depth Efficiency

  • A shallow ConvAC needs a hidden-layer width that grows exponentially with N to match the interleaved-partition entanglement of a polynomially sized deep network.For general pooling windows, multiple cut edges connected to the same δ tensor contribute their bond dimension only once, reducing the upper bound.Source: §7.4 · p. 26

8. Experiments

The experiments test whether channel-width arrangements matched to short- versus long-range input correlations improve classification. Wide-base performs better on the local task, while wide-tip performs better on the global task, extending the ConvAC predictions to ConvNets with ReLU and max pooling.

Tasks

  • The local and global tasks use randomly positioned MNIST digits resized to 8×8 and 32×32, respectively, in 64×64 black-background images.Both tasks classify digits into labels 0–9.Source: §8 · pp. 26–27

Network design

  • Wide-base widens early layers and narrows deeper ones, whereas wide-tip reverses that channel ordering; both networks have the same parameter count.Each network has a representation layer followed by six shared-convolution, ReLU, max-pooling layers.Source: §8 · p. 27

Results

  • Wide-base significantly outperforms wide-tip on the local task, while wide-tip shows the opposite advantage on the global task.The authors attribute these patterns to wide-base supporting short correlation lengths and wide-tip focusing on longer ones.Source: §8 · p. 27, Figure 10 · p. 28
  • The accuracy gap between channel arrangements decreases as r grows, and the authors expect harder tasks to reveal a more noticeable difference at larger parameter counts.The authors explain the shrinking gap in relation to task difficulty and parameter count.Source: §8 · p. 28

9. Discussion

The discussion presents Tensor Networks as a graph-theoretic representation of ConvACs, linking channel counts and network expressivity to input correlations. It also outlines implications for transferring ideas between deep learning and quantum physics, alongside open research directions.

Theoretical contribution

  • The ConvAC Tensor Network construction enables graph-theoretic analysis and ties network expressivity to graph min-cuts and layer channel counts.These results can guide network design when prior knowledge about correlations among input variables is available.Source: §9 · pp. 28–29

Quantum connection

  • Structural equivalence between ConvAC functions and quantum many-body wave functions lets entanglement measures quantify a network’s ability to model intricate input correlations.The analysis adapts Tensor Network entanglement bounds related to min-cuts, following Cui et al. (2016).Source: §9 · p. 29

Interdisciplinary bridges

  • The authors identify two interdisciplinary bridges: graph-theoretic tools for analyzing convolutional networks and potential transfer of methods between Tensor Networks and deep learning.They note that MERA adds disentangling operations before pooling, mixing activations intended for different pooling windows.Source: §9 · p. 29

Open directions

  • Characterizing correlations in general natural datasets remains unclear beyond the paper’s simple fixed-feature-size case.The discussion also proposes exploring DMRG-inspired training through mapping ConvNets to Tensor Networks and back; prior MPS training attempts lacked a mapping to an existing ConvNet architecture before optimization.Source: §9 · p. 30

Appendix A. A Recursive Construction of the Deep ConvAC Tensor Network

The appendix constructs the recursive Tensor Network representation of a deep ConvAC computation. Its contractions recover the network’s layer operations and output.

Recursive representation

  • For a one-dimensional ConvAC with general N where log2N is an integer, the appendix gives a recursively defined Tensor Network representation.The vector v(l,j) denotes activations at level l, and v(0,j) represents vectors in the representation layer.Source: Appendix A · p. 34

Recovering layer operations

  • Contracting the Tensor Network indices and applying matrix multiplication reduces the recursion to the ConvAC activation operation.The operation forms each feature-map activation by multiplicatively pooling two preceding activation vectors convolved with the corresponding weight vector.Source: Appendix A · p. 34

Network output

  • Applying the operation recursively yields the ConvAC’s conv→pool sequence, with the network output defined at the final level.The construction identifies the final rank rL with the number of network outputs Y.Source: Appendix A · p. 35

B.1. Upper Bound on the Entanglement Measure

The appendix bounds the rank of a Tensor Network’s matricization across an external-index partition by the smallest cut weight separating the two groups. It then notes conditions for tightness and a smaller bound for larger pooling windows.

Rank bound

  • The rank of the matricization across external-index groups A and B is at most the minimum product of bond dimensions over cuts separating those groups.The bound applies to a general Tensor Network and specifically to the ConvAC Tensor Network.Source: §B.1 · pp. 35–36

Proof construction

  • A cut may include external edges, and contracting tensors on each side leaves two tensors connected by the cut indices.Coalescing the external indices on each side and the cut indices gives the matricization as a matrix product.Source: §B.1 · p. 36

Tightness and scope

  • The upper bound is tight for a deep ConvAC with pooling window size 2 under certain conditions; a smaller upper bound is available for pooling windows larger than 2.The latter bound informs the discussion of shallow networks’ expressiveness relative to deep networks.Source: §B.1 · p. 36

B.2. Lower Bound on the Entanglement Measure

The section establishes a generic lower bound on matricization rank for deep ConvACs with bond dimensions that are powers of a common integer, matching the minimum cut weight and tightening the known upper bound. Its proof constructs tensor assignments using δ-restricted edge-disjoint paths and extends the bound to bond dimensions rounded down to powers of that integer.

B.2. Lower Bound on the Entanglement Measure

  • A network with bond dimensions rounded down to powers of p transfers its achieved matricization rank to the original network almost always.The construction embeds the rounded network’s tensor as a hypercube in the original tensor, with zeros elsewhere; a polynomial-rank result then yields the almost-always claim.Source: §B.2 · pp. 37–38
  • For deep ConvACs with pooling window 2 and bond dimensions that are powers of a common p, matricization rank is at least min_C W_C almost always, making claim 1’s upper bound tight.“Almost always” means for all network-weight configurations except a set of Lebesgue measure zero.Source: §B.2 · p. 38
  • Replacing each bond of dimension p^n with n parallel bonds of dimension p preserves the matricization rank, enabling analysis of the transformed network φ∗.The construction preserves a one-to-one correspondence between tensor assignments and the resulting linear-map ranks.Source: §B.2 · pp. 39–40, Figure 13 · p. 39
  • The transformed minimum cut yields edge-disjoint paths, constructed from integral flow so duplicate edges carry flow in the same direction and paths can respect the δ-tensor restrictions.Menger’s theorem gives the edge-disjoint paths; the integral-flow construction decomposes flow into paths while respecting edge capacities.Source: §B.2 · pp. 40–42
  • The graph admits L δ-restricted edge-disjoint paths between V_A* and V_B*, the maximum number under the δ restriction.The paths are assigned distinct indices while respecting the restriction at δ tensors.Source: §B.2 · p. 42
  • Weight-tensor assignments force path-edge indices to match along each path, while indices on edges outside the paths equal 1.Each path index can take values in [p].Source: §B.2 · p. 43
  • The constructed tensor assignment yields matricization rank p^L = min_C W_C, establishing the lemma’s lower bound.The matricized tensor has an identity block of size p^L and zeros elsewhere.Source: §B.2 · pp. 42–43
  • Applying the lemma to bond dimensions rounded down to powers of p establishes the theorem’s bound for p maximizing the min-cut expression, almost always.The proof considers p ∈ argmax_p min_C W_C^p.Source: §B.2 · pp. 43–44

Appendix C. Upper Bound for a General Pooling Window Case

For ConvACs with general pooling windows, a modified min-cut weight upper-bounds the rank of the convolutional-weights tensor’s matricization. The bound accounts for δ-tensor constraints, which can reduce the bound, while size-2 pooling avoids an expressivity penalty from those constraints.

Appendix C. Upper Bound for a General Pooling Window Case

  • The modified cut weight multiplies bond dimensions across distinct edge groups, counting edges linked to one δ tensor only once.Edges incident to the same δ tensor belong to the same group.Source: Appendix C · p. 44
  • For general pooling windows, the matricization rank is at most the minimum modified cut weight.The modified weight counts bond dimensions of edges connected to the same δ tensor only once.Source: Appendix C · p. 44
  • Replacing one general tensor with a δ tensor can reduce the upper bound; in the illustrated shallow ConvAC, the central δ tensor limits expressivity.The example compares the network with a general tensor against one obeying the δ constraint.Source: Figure 15 · p. 45
  • δ constraints make unequal cut indices linked to the same δ tensor vanish, allowing them to be coalesced into one representative summation index.This coalescence bounds the index range by the modified cut weight.Source: Appendix C · p. 45
  • With pooling windows of size 2, δ-tensor restrictions do not harm expressivity, so channel mixing through a more elaborate pooling scheme would not help.The three-legged δ tensors allow a cut crossing multiple legs of one δ tensor to be replaced by an equivalent cut crossing one leg.Source: Appendix C · p. 46

Appendix D. Upper Bound Deviations Simulation

Simulations found that the upper bound was reached in nearly all tested configurations, with small deviations in the few exceptions. The evidence covers networks up to N=16, and broader theoretical analysis remains open.

Appendix D. Upper Bound Deviations Simulation

  • For general channel numbers, tightness is not theoretically guaranteed; the authors leave a theoretical account of deviations for future work.The simulations checked only up to N=16, and larger networks might show more substantial discrepancies.Source: Appendix D · p. 46
  • The simulations used an N=16, M=2 ConvAC TN and 360 bond-dimension arrangements drawn from the first six primes, [2, 3, 5, 7, 11, 13].Weights were randomized according to a normal distribution, and all 6,435 input partitions were checked per arrangement.Source: Appendix D · p. 46
  • The comparison tested whether matricization rank equaled the exponentiated max-flow, with max-flow computed using Ford–Fulkerson.The logarithm of the rank upper bound corresponds to max-flow in a graph whose edge capacities are logarithms of the bond dimensions.Source: Appendix D · p. 46
  • Only 1,300 of 2.3166 million configurations missed the upper bound, and each deviation was at most 10%.The tests used channel settings chosen to be far from the case where all channel numbers are powers of the same integer.Source: Appendix D · p. 46
Loading 1704.01552v2…