Formal understanding of the inductive bias behind deep convolutional networks, i.e. the relation between the network's architectural features and the functions it is able to model, is limited. In this work, we establish a fundamental connection between the fields of quantum physics and deep learning, and use it for obtaining novel theoretical observations regarding the inductive bias of convolutional networks. Specifically, we show a structural equivalence between the function realized by a convolutional arithmetic circuit (ConvAC) and a quantum many-body wave function, which facilitates the use of quantum entanglement measures as quantifiers of a deep network's expressive ability to model correlations. Furthermore, the construction of a deep ConvAC in terms of a quantum Tensor Network is enabled. This allows us to perform a graph-theoretic analysis of a convolutional network, tying its expressiveness to a min-cut in its underlying graph. We demonstrate a practical outcome in the form of a direct control over the inductive bias via the number of channels (width) of each layer. We empirically validate our findings on standard convolutional networks which involve ReLU activations and max pooling. The description of a deep convolutional network in well-defined graph-theoretic tools and the structural connection to quantum entanglement, are two interdisciplinary bridges that are brought forth by this work. A central factor in the application of machine learning to a given task is the restriction of the hypothesis space of learned functions known as inductive bias. In deep convolutional networks, inductive bias manifests itself in architectural features such as number of layers, number of channels per layer, and more BID17 . Formal understanding of the inductive bias behind convolutional networks is limited -the assumptions encoded into these models, which seem to form an excellent prior knowledge for different types of data (e.g. BID16 ; BID15 ; van den Oord et al. (2016) ), are for the most part a mystery.An important aspect of the influence that a certain architectural feature has on the inductive bias, is its effect on the network's ability to model correlations between regions of its input. In this regard, one typically considers partitions that divide input regions into disjoint sets, and asks how far the function realized by the network is from being separable with respect to these partitions BID5 Levine et al., 2017) . For example, BID5 show that when separability is measured through the algebraic notion of separation-rank, deep Convolutional Arithmetic Circuits (ConvACs) BID7 support exponential (in network size) separation-ranks for certain input partitions, while being limited to polynomial separation-ranks for others. ConvACs are a special class of convolutional networks, characterized by linear activations and product pooling, which served a key role in theoretical analyses of convolutional networks, in virtue of their algebraic structure.In this work, we draw upon formal similarities between how physicists describe a system of manyparticles as a quantum mechanical wave function, and how machine learning practitioners map a high-dimensional input (e.g. image) to a set of output labels through a deep network. In particular, we show that there is a structural equivalence between a function modeled by a ConvAC and a many-body quantum wave function, which relies on their underlying tensorial structure. This allows employment of the well-established physical notion of quantum entanglement measures (Plenio and Virmani, 2007) , which subsumes other algebraic notions of separability such as the separation-rank mentioned above, for the analysis of correlations modeled by deep convolutional networks.Importantly, quantum entanglement is used by physicists as prior knowledge to form compact representations of many-body wave functions in what is known as Tensor Networks (TNs) (Östlund and Rommer, 1995; Verstraete and Cirac, 2004; Vidal, 2008; BID11 . In the domain of machine learning, a network in the form of a ConvAC is effectively a compact representation of a multi-dimensional array related to the convolutional weights. This has been analyzed to date via tensor decompositions -where the representations are based on linear combinations of outer-products between lower-order tensors BID7 . A TN, on the other hand, is a way to compactly represent a higher-order tensor through inner-products among lower-order tensors, which allows a natural representation of TNs through an underlying graph. Although the fundamental language is different, we show that a ConvAC can be mapped to a TN, and thus a graph-theoretic setting for studying functions modeled by deep convolutional networks is brought forth. In particular, notions of max-flow/min-cut are shown to convey important meaning.The results we present, connect the inductive bias of deep convolutional networks to the number of channels in each layer, and indicate how these should be set in order to satisfy prior knowledge on the task at hand. Specifically, the ability of a ConvAC to represent correlations between input regions is shown to be related to a min-cut over all edge-cut sets that separate the corresponding input nodes in the associated TN. Such results enable one to avoid bottle-necks and adequately tailor the network architecture through application of prior knowledge. Our results are theoretically proven for a deep ConvAC architecture; their applicability to a conventional deep convolutional network architecture, which involves ReLU activations and max pooling, is demonstrated through experiments.Some empirical reasoning regarding the influence of the channel numbers on the network's performance has been suggested (e.g. Szegedy et al. (2016) ), mainly regarding the issue of bottle-necks which is naturally explained via our theoretical analysis below. Such insights on the architectural design of deep networks are new to machine learning literature, and rely on TN bounds recently derived in physics literature, referred to as 'quantum min-cut max-flow' BID8 . The mapping we present between ConvACs and TNs indicates new possibilities for the use of graphtheory in deep networks, where min-cut analysis could be just the beginning. Additionally, the connections we derive to quantum entanglement and quantum TNs may open the door to further well-established physical insights regarding correlation structures modeled by deep networks.The use of TNs in machine learning has appeared in an empirical context where Stoudenmire and Schwab (2016) trained a matrix product state (MPS) TN architecture to perform supervised learning tasks on the MNIST data-set. Additionally, there is a growing interest in the physics community in RBM based forms for variational many-body wave functions (e.g. BID1 ). BID2 present a theoretical mapping between RBMs and TNs which allows them to connect the entanglement bounds of a TN state to the expressiveness of the corresponding RBM. We provide below the minimal tensor analysis background required for following the analyses of ConvACs and TNs that are carried out in this paper. The core concept in tensor analysis is a tensor, which may be thought of as a multi-dimensional array. The order of a tensor is defined to be the number of indexing entries in the array, which are referred to as modes. The dimension of a tensor in a particular mode is defined as the number of values that may be taken by the index in that mode. If A is a tensor of order N and dimension M i in each mode i ∈ [N ], its entries are denoted A d1... d N , where the index in each mode takes values between 1 and the appropriate dimension, d i ∈ [M i ]. Suppose A is a tensor of order N , and let (A, B) be a partition of [N ] := {1, . . . , N }, i.e. A and B are disjoint subsets of [N ] whose union covers the entire set. The matricization of A w.r.t. the partition (A, B), denoted A A,B , is essentially the arrangement of the tensor elements as a matrix whose rows correspond to A and columns to B (see appendix A for exact definition). The construction of a deep ConvAC in terms of a TN brought forth the main theoretical achievements of this paper. This method enabled us to carry a graph-theoretic analysis of a convolutional network, and tie its expressiveness to a minimal cut in the graph characterizing it. Our construction began with a structural equivalence between the function realized by a ConvAC and a quantum many-body wave function. This facilitated the transfer of mathematical and conceptual tools employed by physicists, such as the tool of TNs and the concept of 'entanglement measures', providing well-defined quantifiers for a deep network's expressive ability to model correlations between regions of its input. By employing these tools, we were able to present theoretical observations regarding the role that the number of channels in each layer fulfills in the overall expressiveness of a deep convolutional network, and how they affect its ability to model given input correlations. Furthermore, practical implications were presented for the construction of a deep network architecture when there is prior knowledge regarding the input correlations.Apart from the direct results discussed above, two important interdisciplinary bridges emerge from this work. The results we drew between min-cut in the graph representation of a ConvAC to network expressivity measures, may constitute an initial example for employing the connection to TNs for the application of graph-theoretic measures and tools to the analysis of the function realized by a deep convolutional network. The second bridge, is the mathematical connection between the two fields of quantum physics and deep learning. The field of quantum TNs is a rapidly evolving one, and the established construction of a successful deep learning architecture in the language of TNs may allow applications and insights to be transferred between the two domains. For example, the tree shaped TN that was shown in this work to be equivalent to a deep convolutional network, has been known in the physics community for nearly a decade to be inferior to another deep TN architecture by the name of MERA (Vidal, 2008) , in its expressiveness and in its ability to model correlations.The MERA TN constitutes an exemplar case of how the TNs/deep-learning connection established in this work allows a bi-directional flow of tools and intuition. MERA architecture introduces over-laps by adding 'disentangling' operations prior to the pooling operations, which, in translation to terms of deep learning, effectively mix activations that are intended to be pooled in different pooling windows. Physicists have a good grasp of how these specific overlapping operations allow a most efficient representation of functions that exhibit high correlations at all length scales (Vidal, 2007) . Accordingly, a new view of the role of overlaps in the high expressivity of deep networks as effectively 'disentangling' intricate correlations in the data can be established. In the other direction, as deep convolutional networks are the most empirically successful machine learning architectures to date, physicists may benefit from trading their current 'overlaps by disentangling' scheme to the use of overlapping convolutional windows (proven to contribute exponentially to the expressive capacity of neural networks by Sharir and Shashua FORMULA1 ), in their search for expressive representations of quantum wave functions. Overall, We view this work as an exciting bridge for transfer of tools and ideas between fields, and hope it will reinforce a fruitful interdisciplinary discourse. DISPLAYFORM0 We provide below a short introduction to the notation used by physicists when describing quantum mechanical properties of a many-body system. We follow relevant derivations in Preskill (1998) and Hall FORMULA1 , referring the interested reader to these sources for a more comprehensive mathematical introduction to quantum mechanics.A state of a system, which is a complete description of a physical system, is given in quantum mechanics as a ray in a Hilbert space (to be defined below). Relevant Hilbert spaces in quantum mechanics are vector spaces over the complex numbers. We restrict our discussion to vector spaces over R, as the properties related to complex numbers are not required for our analysis and do not affect it. Physicists denote such vectors in the 'ket' notation, in which a vector ψ is denoted by: |ψ ∈ H. The Hilbert space H has an inner product denoted by φ|ψ , that maps a pair of two vectors in H to a scalar. This inner product operation is also referred to as 'projecting |ψ onto |φ '. A ray is an equivalence class of vectors that differ by multiplication by a nonzero scalar. For any nonzero ray, a representative of the class, |ψ , is conventionally chosen to have a unit norm: ψ|ψ = 1. A 'bra' notation φ|, is used for the 'dual vector' which formally is a linear mapping between vectors to scalars defined as |ψ → φ|ψ . We can intuitively think of a 'ket' as a column vector and 'bra' as a row vector.Relevant Hilbert spaces can be infinite dimensional or finite dimensional. We limit our discussion to quantum states which reside in finite dimensional Hilbert spaces, as these lie at the heart of our analogy to convolutional networks. Besides being of interest to us, these spaces are extensively investigated in the physics community as well. For example, the spin component of a spinful particle's wave function resides in a finite dimensional Hilbert space. One can represent a general single particle state |ψ ∈ H1, where dim(H1) = M , as a linear combination of some orthonormal basis vectors: DISPLAYFORM0 where v ∈ R M is the vector of coefficients compatible with the basis {|ψ d } M d=1 of H1, each entry of which can be calculated by the projection: DISPLAYFORM1 The extension to the case of N particles, each with a wave function residing in a local finite dimensional Hilbert space Hj for j ∈ [N ] (e.g. N spinful particles), is readily available through the tool of a tensor product. In order to define a Hilbert space which is the tensor product of the local Hilbert spaces: H := ⊗ N j=1 Hj, we will specify its scalar product. Denote the scalar product in each Hj by ·|· j , then the scalar product in the tensor product finite dimensional Hilbert space DISPLAYFORM2 For simplicity, we set the dimensions of the local Hilbert spaces Hj to be equal for all j, i.e. ∀j : dim(Hj) = M . In the spin example, this means that the particles have the same spin, e.g. for N electrons (spin 1/2), M = 2. Denoting as above the orthonormal basis of the local Hilbert space by DISPLAYFORM3 , the many-body quantum wave function |ψ ∈ H = ⊗ N j=1 Hj can be written as: DISPLAYFORM4 Reproducing eq. 2. A Tensor Network (TN) is formally represented by an underlying undirected graph that has some special attributes, we elaborate on this formal definition in appendix E.1. In the following, we give a more intuitive description of a TN, which is nonetheless exact and required for our construction of the ConvAC TN. The basic building blocks of a TN are tensors, which are represented by nodes in the network. The order of a tensor represented by a node, is equal to its degree -the number of edges incident to it, also referred to as its legs. FIG6 (a) shows three examples: 1) A vector, which is a tensor of order 1, is represented by a node with one leg. 2) A matrix, which is a tensor of order 2, is represented by a node with two legs. 3) Accordingly, a tensor of order N is represented in the TN as a node with N legs. In a TN, each edge is associated with a number called the bond dimension. The bond dimension assigned to a specific leg of a node, is simply the dimension of the corresponding mode of the tensor represented by this node (see definitions for a mode and its dimension in section 2).A TN is a collection of such tensors represented by nodes, with edges that can either be connected to a node on one end and loose on the other end or connect between two nodes. Each edge in a TN is represented by an index that runs between 1 and its bond dimension. An index representing an edge which connects between two tensors is called a contracted index, while an index representing an edge with one loose end is called an open index. The set of contracted indices will be denoted by K = {k1, ..., kP } and the set of open indices will be denoted by D = {d1, ..., dN }. The operation of contracting the network is defined by summation over all of the P contracted indices An example for a contraction of a simple TN is depicted in FIG6 . There, a TN corresponding to the operation of multiplying a vector v ∈ R r 1 by a matrix M ∈ R r 2 ×r 1 is performed by summing over the only contracted index, k. As there is only one open index, d, the result of contracting the network is an order 1 tensor (a vector): u ∈ R r 2 which upholds u = M v. In FIG6 (c) a somewhat more elaborate example is illustrated, where a TN composed of order 2 and 3 tensors represents a tensor of order 5. This network represents a decomposition known as a tensor train (Oseledets (2011)) in the tensor analysis community or a matrix product state (MPS) (see overview in e.g. Orús (2014)) in the condensed matter physics community, which arranges order 3 tensors in such a 'train' architecture and allows the representation of an order N tensor with a linear (in N ) amount of parameters. The MPS exemplifies a typical desired quality of TNs. The decomposition of a higher order tensor into a set of sparsely interconnected lower order tensors, was shown (Oseledets and Tyrtyshnikov (2009); BID0 ) to greatly diminish effects related to the curse of dimensionality discussed above. 8
Employing quantum entanglement measures for quantifying correlations in deep learning, and using the connection to fit the deep network's architecture to correlations in the data.
{"src": "scitldr-AIC_train", "paper_id": "SywXXwJAb"}