Title: UNSUPERVISED DEEP STRUCTURE LEARNING BY RECURSIVE DEPENDENCY ANALYSIS

Abstract: We introduce an unsupervised structure learning algorithm for deep, feed-forward, neural networks. We propose a new interpretation for depth and inter-layer connectivity where a hierarchy of independencies in the input distribution is encoded in the network structure. This results in structures allowing neurons to connect to neurons in any deeper layer skipping intermediate layers. Moreover, neurons in deeper layers encode low-order (small condition sets) independencies and have a wide scope of the input, whereas neurons in the first layers encode higher-order (larger condition sets) independencies and have a narrower scope. Thus, the depth of the network is automatically determined-equal to the maximal order of independence in the input distribution, which is the recursion-depth of the algorithm. The proposed algorithm constructs two main graphical models: 1) a generative latent graph (a deep belief network) learned from data and 2) a deep discriminative graph constructed from the generative latent graph. We prove that conditional dependencies between the nodes in the learned generative latent graph are preserved in the class-conditional discriminative graph. Finally, a deep neural network structure is constructed based on the discriminative graph. We demonstrate on image classification benchmarks that the algorithm replaces the deepest layers (convolutional and dense layers) of common convolutional networks, achieving high classification accuracy, while constructing significantly smaller structures. The proposed structure learning algorithm requires a small computational cost and runs efficiently on a standard desktop CPU.

1. INTRODUCTION:

Over the last decade, deep neural networks have proven their effectiveness in solving many challenging problems in various domains such as speech recognition (Graves & Schmidhuber, 2005) , computer vision (Krizhevsky et al., 2012; Girshick et al., 2014; Simonyan & Zisserman, 2014; Szegedy et al., 2015) and machine translation (Collobert et al., 2011b) . As compute resources became more available, large scale models having millions of parameters could be trained on massive volumes of data, to achieve state-of-the-art solutions for these high dimensionality problems. Building these models requires various design choices such as network topology, cost function, optimization technique, and the configuration of related hyper-parameters.

In this paper, we focus on the design of network topology-structure learning. Generally, exploration of this design space is a time consuming iterative process that requires close supervision by a human expert. Many studies provide guidelines for design choices such as network depth (Simonyan & Zisserman, 2014) , layer width (Zagoruyko & Komodakis, 2016) , building blocks (Szegedy et al., 2015) , and connectivity (He et al., 2016; Huang et al., 2016) . Based on these guidelines, these studies propose several meta-architectures, trained on huge volumes of data. These were applied to other tasks by leveraging the representational power of their convolutional layers and fine-tuning their deepest layers for the task at hand (Donahue et al., 2014; Hinton et al., 2015; Long et al., 2015; Chen et al., 2015; Liu et al., 2015) . However, these meta-architecture may be unnecessarily large and require large computational power and memory for training and inference.

The problem of model structure learning has been widely researched for many years in the probabilistic graphical models domain. Specifically, Bayesian networks for density estimation and causal discovery (Pearl, 2009; Spirtes et al., 2000) . Two main approaches were studied: score-based (search-and-score) and constraint-based. Score-based approaches combine a scoring function, such as BDe (Cooper & Herskovits, 1992) and BIC (Ripley, 2007) , with a strategy for searching through the space of structures, such as greedy equivalence search (Chickering, 2002) . Adams et al. (2010) introduced an algorithm for sampling deep belief networks (generative model) and demonstrated its applicability to high-dimensional image datasets.

Constraint-based approaches (Pearl, 2009; Spirtes et al., 2000) find the optimal structures in the large sample limit by testing conditional independence (CI) between pairs of variables. They are generally faster than score-based approaches (Yehezkel & Lerner, 2009) and have a well-defined stopping criterion (e.g., maximal order of conditional independence). However, these methods are sensitive to errors in the independence tests, especially in the case of high-order conditional-independence tests and small training sets.

Motivated by these methods, we propose a new interpretation for depth and inter-layer connectivity in deep neural networks. We derive a structure learning algorithm such that a hierarchy of independencies in the input distribution is encoded in the network structure, where the first layers encode higher-order independencies than deeper layers. Thus, the number of layers is automatically determined. Moreover, a neuron in a layer is allowed to connect to neurons in deeper layers skipping intermediate layers. An example of a learned structure, for MNIST, is given in Figure 1 .

We describe our recursive algorithm in two steps. In Section 2 we describe a base case-a singlelayer structure learning. In Section 3 we describe multi-layer structure learning by applying the key concepts of the base case, recursively (proofs are provided in Appendix A). In Section 4 we discuss related work. We provide experimental results in Section 5, and conclude in Section 6.

Preliminaries. Consider X = {X i } N i=1 a set of observed (input) random variables, H = {H j } K j=1

a set of latent variables, and Y a class variable. Our algorithm constructs three graphical models and an auxiliary graph. Each variable is represented by a single node and a single edge may connect two distinct nodes. Graph G is a generative DAG defined over the observed and latent variables

X ∪ H. Graph G Inv is called a stochastic inverse of G.

Graph G D is a discriminative model defined over the observed, latent, and class variables X ∪ H ∪ Y . An auxiliary graph G X is defined over X (a CPDAG; an equivalence class of a Bayesian network) and is generated and maintained as an internal state of the algorithm. The parents set of a node X in G is denoted P a(X; G). The order of an independence relation is defined to be the condition set size. For example, if X 1 and X 2 are independent given X 3 and X 4 , denoted X 1 ⊥ ⊥ X 2 |{X 3 , X 4 }, then the independence order is two. Neurons in a layer may connect to neurons in any deeper layer. Depth is determined automatically. Each gather layer selects a subset of the input, where each input variable is gathered only once. A neural route, starting with a gather layer, passes through densely connected layers where it may split (copy) and merge (concatenate) with other routes in correspondence with the hierarchy of independencies identified by the algorithm. All routes merge into the final output layer (e.g., a softmax layer).

2. SINGLE LAYER STRUCTURE LEARNING:

We start by describing the key concepts of our approach using a simple scenario: learning the connectivity of a single-layer neural network.

2.1. CONSTRUCTING A GENERATIVE GRAPH:

Assume the input joint distribution p(X) complies with the following property.

Assumption 1. The joint distribution p(X) is faithful to a DAG G over observed X and latent nodes H, where for all X ∈ X and H ∈ H, P a(X; G) ⊆ H and P a(H; G) ⊆ H\H.

p X; G = p X, H; G dH = p H N i=1 p X i P a(X i ; G) dH.

(1)

Note that the generative graphical model G can be described as a layered deep belief network where parents of a node in layer m can be in any deeper layer, indexes greater than m, and not restricted to the next layer m + 1. This differs from the common definition of deep belief networks (Hinton et al., 2006; Adams et al., 2010) where the parents are restricted to layer m + 1.

It is desired to learn an efficient graph G having small sets of parents and a simple factorization of p(H) while maintaining high expressive power. We first construct an auxiliary graph, a CPDAG (Spirtes et al., 2000) , G X over X (an equivalence class of a fully visible Bayesian network) encoding only marginal independencies1 (empty condition sets) and then construct G such that it can mimic G X over X, denoted G X G (Pearl, 2009) . That is, preserving all conditional dependencies of X in G X .

The simplest connected DAG that encodes statistical independence is the v-structure, a structure with three nodes X 1 → X 3 ← X 2 in which X 1 and X 2 are marginally independent X 1 ⊥ ⊥ X 2 and conditionally dependent X 1 ⊥ ⊥X 2 |X 3 . In graphs encoding only marginal independencies, dependent nodes form a clique. We follow the procedure described by Yehezkel & Lerner (2009) and decompose X into autonomous sets (complying with the Markov property) where one set, denoted X D (descendants), is the common child of all other sets, denoted X A1 , . . . , X AK (ancestor sets). We select X D to be the set of nodes that have the lowest topological order in G X . Then, by removing X D from G X (temporarily for this step), the resulting K disjoint sets of nodes (corresponding to K disjoint substructures) form the K ancestor sets {X Ai } K i=1 . See an example in Figure 2 . Next, G is initialized to an empty graph over X. Then, for each ancestor set X Ai a latent variable H i is introduced and assigned to be a common parent of the pair (X Ai , X D ). Thus,

p X; G = K i=1   p H i X∈XA i p X H i   X ∈XD p X H dH.

(2)

Note that the parents of two ancestor sets are distinct, whereas the parents set of the descendant set is composed of all the latent variables.

In the auxiliary graph G X , for each of the resulting v-structures (X Ai → X D ← X Aj ), a link between a parent and a child can be replaced by a common latent parent without introducing new independencies. For example, in Figure 2 Algorithm 1 summarizes the procedure of constructing G having a single latent layer. Note that we do not claim to identify the presence of confounders and their inter-relations as in Elidan et al. (2001) ; Silva et al. (2006) ; Asbeh & Lerner (2016) . Instead, we augment a fully observed Bayesian network with latent variables, while preserving conditional dependence. 

2.2. CONSTRUCTING A STOCHASTIC INVERSE:

It is important to note that G represents a generative distribution of X and is constructed in an unsupervised manner (class variable Y is ignored). Hence, we construct G Inv , a graphical model that preserves all conditional dependencies in G but has a different node ordering in which the observed variables, X, have the highest topological order (parentless)-a stochastic inverse of G. Note that conditional dependencies among X are not required to be preserved in the stochastic inverse as these are treated (simultaneously) as observed variables (highest topological order). Stuhlmüller et al. (2013) ; Paige & Wood (2016) presented a heuristic algorithm for constructing such stochastic inverses where the structure is a DAG (an example is given in Figure 3-[b] ). However, these DAGs, though preserving all conditional dependencies, may omit many independencies and add new edges between layers.

We avoid limiting G Inv to a DAG and instead limit it to be a projection of another latent structure (Pearl, 2009) . That is, we assume the presence of additional hidden variables Q that are not in G Inv but induce dependency2 among H. For clarity, we omit these variables from the graph and use bi-directional edges to represent the dependency induced by them. An example is given in Figure 3 - [c] where a bi-directional edge represents the effect of some variable Q ∈ Q on H A and H B . We construct G Inv in two steps:

1. Invert all G edges (invert inter-layer connectivity).

2. Connect each pair of latent variables, sharing a common child in G, with a bi-directional edge.

This simple procedure ensures G G Inv over X ∪ H while maintaining the exact same number of edges between the layers (Proposition 1, Appendix A). 

{XA i } K i=1 ←-disjoint sets, after removing XD from GX G ←-an empty graph over X add K latent variables H = {Hi} K i=1 to G create a latent layer set each Hi to be a parent of {XA 1 ∪ XD} connect return G 2.3 CONSTRUCTING A DISCRIMINATIVE GRAPH

Recall that G encodes the generative distribution of X and G Inv is the stochastic inverse. We further construct a discriminative graph G D by replacing bi-directional dependency relations in G Inv , induced by Q, with explaining-away relations by adding the observed class variable Y . Node Y is set in G D to be the common child of the leaves in G Inv (latents introduced after testing marginal independencies) (see an example in Figure 3-[d] ). This preserves the conditional dependency relations of G Inv . That is, G D can mimic G Inv over X and H given Y (Proposition 2, Appendix A). It is interesting to note that the generative and discriminative graphs share the exact same inter-layer connectivity (inverted edge-directions). Moreover, introducing node Y provides an "explaining away" relation between latents, uniquely for the classification task at hand.

2.4. CONSTRUCTING A FEED-FORWARD NEURAL NETWORK:

We construct a neural network based on the connectivity in G D . Sigmoid belief networks (Neal, 1992) have been shown to be powerful neural network density estimators (Larochelle & Murray, 2011; Germain et al., 2015) . In these networks, conditional probabilities are defined as logistic regressors. Similarly, for G D we may define for each latent variable H ∈ H,

EQUATION

where sigm(x) = 1/(1 + exp(-x)), X = P a(H ; G D ), and (W , b ) are the parameters of the neural network. Nair & Hinton (2010) proposed replacing each binary stochastic node H by an infinite number of copies having the same weights but with decreasing bias offsets by one. They showed that this infinite set can be approximated by

EQUATION

where v = W X + b . They further approximate this function by max(0, v + ) where is a zerocentered Gaussian noise. Following these approximations, they provide an approximate probabilistic interpretation for the ReLU function, max(0, v). As demonstrated by Jarrett et al. (2009) and Nair & Hinton (2010) , these units are able to learn better features for object classification in images.

In order to further increase the representational power, we represent each H by a set of neurons having ReLU activation functions. That is, each latent variable H in G D is represented in the neural network by a dense (fully-connected) layer. Finally, the class node Y is represented by a softmax layer.

3. RECURSIVE MULTI-LAYER STRUCTURE LEARNING:

We now extend the method of learning the connectivity of a single layer into a method of learning multi-layered structures. The key idea is to recursively introduce a new and deeper latent layer by testing n-th order conditional independence (n is the condition set size) and connect it to latent layers created by previous recursive calls that tested conditional independence of order n + 1. The method is described in Algorithm 2. It is important to note that conditional independence is tested only between input variables X and condition sets do not include latent variables. Conditioning on latent variables or testing independence between them is not required as the algorithm adds these latent variables in a specific manner, preserving conditional dependencies between the input variables.

Algorithm 2: Recursive Latent Structure Learning (multi-layer)

RecurLatStruct (GX , X, Xex, n) Input: an initial DAG GX over observed X & exogenous nodes Xex and a desired resolution n.

Output: G, a latent structure over X and H

if the maximal indegree of GX (X) is below n + 1 then exit condition G ←-an observed layer X return G G X ←-IncreaseResolution(GX , n) n-th order independencies {XD, XA 1 , . . . , XA K } ←-SplitAutonomous(X, G X ) identify autonomies for i ∈ {1 . . . K} do GA i ←-RecurLatStruct(G X , XA i , Xex, n + 1) a recursive call GD ←-RecurLatStruct(G X , XD, Xex ∪ {XA i } K i=1 , n + 1) a recursive call G ←-Group(GD, GA 1 , . . . , GA K ) merge results create latent variables H (n) = {H (n) 1 , . . . , H (n) K } in G create a latent layer set each H (n) i

to be a parent of {HA are the sets of parentless latents in GA i and GD, respectively.

return G

The algorithm maintains and recursively updates an auxiliary graph G X (a CPDAG) over X and utilizes it to construct G. Yehezkel & Lerner (2009) introduced an efficient algorithm (RAI) for constructing a CPDAG over X by a recursive application of conditional independence tests with increasing condition set sizes (n). Our algorithm is based on this framework for updating the auxiliary graph G X (Algorithm 2, lines 5 and 6).

The algorithm starts with n = 0, G X a complete graph, and a set of exogenous nodes X ex = ∅. The set X ex is exogenous to G X and consists of parents of X.

The function IncreaseResolution (Algorithm 2-line 5) disconnects (in G X ) conditionally independent variables in two steps. First, it tests dependency between X ex and X, i.e., X ⊥ ⊥ X |S for every connected pair X ∈ X and X ∈ X ex given a condition set S ⊂ {X ex ∪ X} of size n.

Next, it tests dependency within X, i.e., X i ⊥ ⊥ X j |S for every connected pair X i , X j ∈ X given a condition set S ⊂ {X ex ∪ X} of size n. After removing the corresponding edges, the remaining edges are directed by applying two rules (Pearl, 2009; Spirtes et al., 2000) . First, v-structures are identified and directed. Then, edges are continually directed, by avoiding the creation of new v-structures and directed cycles, until no more edges can be directed. Following the terminology of Yehezkel & Lerner (2009) , we say that this function increases the graph d-separation resolution from n -1 to n.

The function SplitAutonomous (Algorithm 2-line 6) identifies autonomous sets in a graph in two steps, as described in Algorithm 1 lines 7 and 8. An autonomous set in G X includes all its nodes' parents (complying with the Markov property) and therefore a corresponding latent structure can be constructed independently using a recursive call. Thus, the algorithm is recursively and independently called for the ancestor sets (Algorithm 2 lines 7-8), and then called for the descendant set while treating the ancestor sets as exogenous (Algorithm 2 line 9). Each recursive call returns a latent structure for each autonomous set. Recall that each latent structure encodes a generative distribution over the observed variables where layer H (n+1) , the last added layer (parentless nodes), is a representation of the input X ⊂ X. By considering only layer H (n+1) of each latent structure, we have the same simple scenario discussed in Section 2-learning the connectivity between H (n) , a new latent layer, and H (n+1) , treated as an "input" layer. Thus, latent variables are introduced as parents of the H (n+1) layers, as described in Algorithm 2 lines 11-13. A simplified example is given in Figure 4 .

Next, a stochastic inverse G Inv is constructed as described in Section 2-all the edge directions are inverted and bi-directional edges are added between every pair of latents sharing a common child in G. An example graph G and a corresponding stochastic inverse G Inv are given in Figure 5 . A discriminative structure G D is then constructed by removing all the bi-directional edges and adding the class node Y as a common child of layer H (0) , the last latent layer that is added (Figure 5-[c] ). Finally, a neural network is constructed based on the connectivity of G D . That is, each latent node, H ∈ H (n) , is replaced by a set of neurons, and each edge between two latents, H ∈ H (n) and n+1) , is replaced by a bipartite graph connecting the neurons corresponding to H and H .

H ∈ H (

4. RELATED WORK:

Recent studies have focused on automating the exploration of the design space, posing it as a hyperparameter optimization problem and proposing various approaches to solve it. (Miconi, 2016) learns the topology of an RNN network introducing structural parameters into the model and optimize them along with the model weights by the common gradient descent methods. Smith et al. ( 2016) takes a similar approach incorporating the structure learning into the parameter learning scheme, gradually growing the network up to a maximum size.

A common approach is to define the design space in a way that enables a feasible exploration process and design an effective method for exploring it. Zoph & Le (2016) (NAS) first define a set of hyper-parameters characterizing a layer (number of filters, kernel size, stride). Then they use a controller-RNN for finding the optimal sequence of layer configurations for a "trainee network". This is done using policy gradients (REINFORCE) for optimizing the objective function that is based on the accuracy achieved by the "trainee" on a validation set. Although this work demonstrates capabilities to solve large-scale problems (Imagenet), it comes with huge computational cost. In a following work, Zoph et al. (2017) address the same problem but apply a hierarchical approach. They use NAS to design network modules on a small-scale dataset (CIFAR-10) and transfer this knowledge to a large-scale problem by learning the optimal topology composed of these modules. Baker et al. (2016) use reinforcement learning as well and apply Q-learning with epsilon-greedy exploration strategy and experience replay. Negrinho & Gordon (2017) propose a language that allows a human expert to compactly represent a complex search-space over architectures and hyperparameters as a tree and then use methods such as MCTS or SMBO to traverse this tree. Smithson et al. (2016) present a multi objective design space exploration, taking into account not only the classification accuracy but also the computational cost. In order to reduce the cost involved in evaluating the network's accuracy, they train a Response Surface Model that predicts the accuracy at much lower cost, reducing the number of candidates that go through actual validation accuracy evaluation. Another common approach for architecture search is based on evolutionary strategies to define and search the design space. (Real et al., 2017; Miikkulainen et al., 2017) use evolutionary algorithm to evolve an initial model or blueprint based on its validation performance.

Common to all these recent studies is the fact that structure learning is done in a supervised manner, eventually learning a discriminative model. Moreoever, these approaches require huge compute resources, rendering the solution unfeasible for most applications given limited compute and time resources.

5. EXPERIMENTS:

We evaluate the quality of the learned structure in two experiments:

• Classification accuracy as a function of network depth and size for a structure learned directly from MNIST pixels.

• Classification accuracy as a function of network size on a range of benchmarks and compared to common topologies.

All the experiments were repeated five times where average and standard deviation of the classification accuracy were recorded. In all of our experiments, we used a ReLU function for activation, ADAM (Kingma & Ba, 2015) for optimization, and applied batch normalization (Ioffe & Szegedy, 2015) followed by dropout (Srivastava et al., 2014) to all the dense layers. All optimization hyperparameters that were tuned for the vanilla topologies were also used, without additional tuning, for the learned structures. For the learned structures, all layers were allocated an equal number of neurons. Threshold for independence tests, and the number of neurons-per-layer were selected by using a validation set. Only test-set accuracy is reported.

Our structure learning algorithm was implemented using the Bayesian network toolbox (Murphy, 2001) and Matlab. We used Torch7 (Collobert et al., 2011a) and Keras (Chollet, 2015) with the TensorFlow (Abadi et al., 2015) back-end for optimizing the parameters of both the vanilla and learned structures.

5.1. NETWORK DEPTH, NUMBER OF PARAMETERS, AND ACCURACY:

We analyze the accuracy of structures learned by our algorithm as a function of the number of layers and parameters. Although network depth is automatically determined by the algorithm, it is implicitly controlled by the threshold used to test conditional independence (partial-correlation test in our experiments). For example, a high threshold may cause detection of many independencies leading to early termination of the algorithm and a shallow network (a low threshold has the opposite effect). Thus, four different networks having 2, 3, 4, and 5 layers, using four different thresholds, are learned for MNIST. We also select three configurations of network sizes: a baseline (normalized to 1.00), and two configurations in which the number of parameters is 0.5, and 0.375 of the baseline network (equal number of neurons are allocated for each layer).

Classification accuracies are summarized in Table 1 . When the number of neurons-per-layers is large enough (100%) a 3-layer network achieves the highest classification accuracy of 99.07% (standard deviation is 0.01) where a 2-layer dense network has only a slight degradation in accuracy, 99.04%. For comparison, networks with 2 and 3 fully connected layers (structure is not learned) with similar number of parameters achieve 98.4% and 98.75%, respectively. This demonstrates the efficiency of our algorithm when learning a structure having a small number of layers. In addition, for a smaller neuron allocation (50%), deeper structures learned by our algorithm have higher accuracy than shallower ones. However, a decrease in the neurons-per-layer allocation has a greater impact on accuracy for deeper structures. MNIST images as a function of network depth and number of parameters (normalized). For comparison, when a structure is not learned, networks with 2 and 3 dense layers, achieve 98.4% and 98.75% accuracy, respectively (having the same size as learned structures at configuration "100%").

5.2. LEARNING THE STRUCTURE OF THE DEEPEST LAYERS IN COMMON TOPOLOGIES:

We evaluate the quality of learned structures using five image classification benchmarks. We compare the learned structures to common topologies (and simpler hand-crafted structures), which we call "vanilla topologies", with respect to network size and classification accuracy. The benchmarks and vanilla topologies are described in Convolutional layers are powerful feature extractors for images exploiting domain knowledge, such as spatial smoothness, translational invariance, and symmetry. We therefore evaluate our algorithm by using the first convolutional layers of the vanilla topologies as "feature extractors" (mostly below 50% of the vanilla network size) and learning a deep structure from their output. That is, the deepest layers of the vanilla network (mostly over 50% of the network size) is removed and replaced by a structure learned by our algorithm in an unsupervised manner. Finally, a softmax layer is added and the entire network parameters are optimized.

First, we demonstrate the effect of replacing a different amount of the deepest layers and the ability of the learned structure to replace feature extraction layers. VGG-16 is the "vanilla" topology. For both, CIFAR 10/100 benchmarks, the learned structure achieves the highest accuracy by replacing all the layers that are deeper than layer conv.10. Moreover, accuracy is maintained when replacing the layers deeper than layer conv.7.

One interesting phenomenon to note is that the highest accuracy is achieved at conv. 10 rather than at the "classifier" (the last dense layer). This might imply that although convolutional layers are useful at extracting features directly from images, they might be redundant for deeper layers. By using our structure learning algorithm to learn the deeper layers, accuracy of the overall structure increases with the benefit of having a compact network. An accuracy, similar to that of "vanilla" VGG-16, is achieved with a structure having 85% less total parameters (conv. 7) than the vanilla network, where the learned structure is over 50X smaller than the replaced part.

Next, we evaluate the accuracy of the learned structure as a function of the number of parameters and compare it to a densely connected network (fully connected layers) having the same depth and size. For SVHN, we used the Batch Normalized Maxout Network in Network topology (Chang & Chen, 2015) and removed the deepest layers starting from the output of the second NiN block (MMLP-2-2). For CIFAR-10, we used the VGG-16 and removed the deepest layers starting from the output of conv.10 layer. For MNIST, a structure was learned directly from pixels. Results are depicted in Figure 6 . It is evident that accuracy of the learned structures is significantly higher (error bars represent 2 standard deviations) than a set of fully connected layers, especially in cases where the network is limited to a small number of parameters.

[a] Finally, in Table 4 we provide a summary of network sizes and classification accuracies, achieved by replacing the deepest layers of common topologies (vanilla) with a learned structure. In the first row, a structure is learned directly from images; therefore, it does not have a "vanilla" topology as reference (a network with 3 fully-connected layers having similar size achieves 98.75% accuracy). In all the cases, the size of the learned structure is significantly smaller than the vanilla topology, and generally has an increase in accuracy.

Comparison to other methods. Our structure learning algorithm runs efficiently on a standard desktop CPU, while providing structures with competitive classification accuracies and network sizes. For example, the lowest classification error rate achieved by our unsupervised algorithm for CIFAR 10 is 4.58% with a network of size 6M (WRN-40-4 row in Table 4 ). For comparison, the NAS algorithm (Zoph & Le, 2016) achieves error rates of 5.5% and 4.47% for networks of sizes 4.2M and 7.1M, respectively, and requires optimizing thousands of networks using hundreds of GPUs. For AlexNet network, recent methods for reducing the size of a pre-trained network (pruning while maintaining classification accuracy) achieve 5× (Denton et al., 2014) and 9× (Han et al., 2015; 2016) The number of parameters are reported for "feature extraction" (first layers of the vanilla topology), removed section (the deepest layers of the vanilla topology), and the learned structure that replaced the removed part. The sum of parameters in the "feature extraction" and removed parts equals to the vanilla topology size. The first row corresponds to learning a structure directly from image pixels.

6. CONCLUSIONS:

We presented a principled approach for learning the structure of deep neural networks. Our proposed algorithm learns in an unsupervised manner and requires small computational cost. The resulting structures encode a hierarchy of independencies in the input distribution, where a node in one layer may connect another node in any deeper layer, and depth is determined automatically.

We demonstrated that our algorithm learns small structures, and maintains high classification accuracies for common image classification benchmarks. It is also demonstrated that while convolution layers are very useful at exploiting domain knowledge, such as spatial smoothness, translational invariance, and symmetry, they are mostly outperformed by a learned structure for the deeper layers. Moreover, while the use of common topologies (meta-architectures), for a variety of classification tasks is computationally inefficient, we would expect our approach to learn smaller and more accurate networks for each classification task, uniquely.

As only unlabeled data is required for learning the structure, we expect our approach to be practical for many domains, beyond image classification, such as knowledge discovery, and plan to explore the interpretability of the learned structures.

:

In Section 3, conditional independencies are considered, the construction of GX and G is interleaved, and the ability of G to mimic GX over X is described recursively.

For example, "interactive forks"(Pearl, 2009).

Figures and Tables:

Figure 1: An example of a structure learned by our algorithm (classifying MNIST digits).Neurons in a layer may connect to neurons in any deeper layer. Depth is determined automatically. Each gather layer selects a subset of the input, where each input variable is gathered only once. A neural route, starting with a gather layer, passes through densely connected layers where it may split (copy) and merge (concatenate) with other routes in correspondence with the hierarchy of independencies identified by the algorithm. All routes merge into the final output layer (e.g., a softmax layer).

-[b], X A1 = {A}, X A2 = {B}, and X D = {C, D, E}. Adding a common latent parent (Figure3-[a]) H A (or H B ) and removing all the edges from X A1 (or X A2 ) to X D preserves the conditional dependence A ⊥ ⊥ B|{C, D, E}.

Figure 2: [a] An example of a Bayesian network encoding ground-truth conditional independencies (a DAG underlying observed data) and [b] a corresponding CPDAG (G X ) constructed by testing only marginal independencies. Only A and B are marginally independent (d-separated in [a], A ⊥ ⊥ B), where C and D are marginally dependent (C ⊥ ⊥ D) and therefore connected in [b]. Thus, nodes {C, D, E}, having the lowest topological order, form a descendant set X D = {C, D, E} and nodes A and B form two distinct ancestor sets, X A1 = {A}, X A2 = {B}-disjoint if {C, D, E} is removed from the graph.

Figure 4: An example trace of Algorithm 2 where p(X) is faithful to the DAG in Figure 3-[a]. [a] a CPDAG encoding only marginal independencies (n = 0) and the identified autonomous substructures (line 6 in the algorithm). [b] A CPDAG G X over {C, D, E} encoding conditional independencies up to second order n = 2 (nodes A and B are exogenous). [c] Graph G is created for the autonomous set {C, D, E} by introducing latents {H C , H D }. At n = 2 nodes C and D are identified as autonomous ancestors and E as an autonomous descendant. [d] Graph G is created at n = 0 for all nodes {A, B, H C , H D } by introducing {H A , H B }, where {H C , H D } represent the autonomous subset {C, D, E}.

Figure 6: Accuracy as a function of network size. [a] MNIST, [b] SVHN. [c] CIFAR-10. Error bars represent 2 standard deviations.

Mean classification accuracy [%] (and standard deviation) of structures learned from

Table content: <table><tr><td colspan="2">num. of paramters 2 layers</td><td>3 layers</td><td>4 layers</td><td>5 layers</td></tr><tr><td>1.00</td><td>99.04 (0.01)</td><td colspan="3">99.07 (0.012) 99.07 (0.035) 99.07 (0.052)</td></tr><tr><td>0.5</td><td>98.96 (0.03)</td><td colspan="2">98.98 (0.035) 99.02 (0.04)</td><td>99.02 (0.05)</td></tr><tr><td>0.375</td><td colspan="2">98.96 (0.035) 98.94 (0.04)</td><td colspan="2">98.93 (0.041) 98.93 (0.049)</td></tr></table>

In preliminary experiments we found that, for SVHN and ImageNet, a small subset of the training data is sufficient for learning the structure (larger training set did not improve classification accuracy). As a result, for SVHN only the basic training data is used (without the extra data), i.e., 13% of the available training data, and for ImageNet 5% of the training data is used. Parameters were optimized using all of the training data.

Table content: <table><tr><td>benchmark</td><td/><td>vanilla topology</td><td/></tr><tr><td>dataset</td><td>topology</td><td>description</td><td>size</td></tr><tr><td>MNIST (LeCun et al., 1998)</td><td colspan="2">None MNIST-Man 32-64-FC:128 learn a structure directly from pixels</td><td>127K</td></tr><tr><td>SVHN (Netzer et al., 2011)</td><td colspan="2">Maxout NiN (Chang &amp; Chen, 2015) SVHN-Man 16-16-32-32-64-FC:256</td><td>1.6M 105K</td></tr><tr><td>CIFAR 10 (Krizhevsky &amp; Hinton, 2009)</td><td>VGG-16 WRN-40-4</td><td>(Simonyan &amp; Zisserman, 2014) (Zagoruyko &amp; Komodakis, 2016)</td><td>15M 9M</td></tr><tr><td colspan="2">CIFAR 100 (Krizhevsky &amp; Hinton, 2009) VGG-16</td><td>(Simonyan &amp; Zisserman, 2014)</td><td>15M</td></tr><tr><td>ImageNet (Deng et al., 2009)</td><td>AlexNet</td><td>(Krizhevsky et al., 2012)</td><td>61M</td></tr></table>

Benchmarks and vanilla topologies. MNIST-Man and SVHN-Man topologies were manually created by us. MNIST-Man has two convolutional layer (32 and 64 filters each) and one dense layer with 128 neurons. SVHN-Man was created as a small network reference having reasonable accuracy compared to Maxout-NiN. In the first row we indicate that in one experiment a structure for MNIST was learned from the pixels and feature extracting convolutional layers were not used.

Table content: <table/>

Table3describes classification accuracy achieved by replacing a different amount of the deepest layers in VGG-16. For example, column "conv.10" represents learning a structure using the activations of conv.10 layer. Accuracy and the normalized number of network parameters are reported for the overall network, e.g., up to conv.10 + the learned structure. Column "vanilla" is the accuracy achieved by the VGG-16 network, after training under the exact same setting (a setting we found to maximize a validation-set accuracy for the vanilla topologies). Classification accuracy (%) and overall network size (normalized number of parameters).

Table content: <table><tr><td/><td/><td/><td/><td>learned</td><td/><td>vanilla</td></tr><tr><td/><td/><td colspan="4">conv.5 conv.7 conv.10 classifier</td><td>-</td></tr><tr><td>CIFAR 10</td><td>accuracy # parameters</td><td>90.6 0.10</td><td>92.61 0.15</td><td>92.94 0.52</td><td>92.79 0.98</td><td>92.32 1.00</td></tr><tr><td>CIFAR 100</td><td>accuracy # parameters</td><td>63.17 0.10</td><td>68.91 0.13</td><td>70.68 0.52</td><td>69.14 0.98</td><td>68.86 1.00</td></tr></table>

reduction. Our method achieves 13× reduction. For VGG-16 (CIFAR-10),Li et al. (2017) achieve 3× reduction and our method achieves 7× reduction. A summary of network sizes and classification accuracies (and standard deviations), achieved by replacing the deepest layers of common topologies (vanilla) with a learned structure.

Table content: <table><tr><td/><td/><td colspan="2">accuracy</td><td colspan="3">number of parameters</td></tr><tr><td>dataset</td><td>topology</td><td>vanilla</td><td>learned</td><td>"feature</td><td colspan="2">removed learned</td></tr><tr><td/><td/><td/><td>structure</td><td>extraction"</td><td>section</td><td>structure</td></tr><tr><td>MNIST</td><td>None</td><td/><td>99.07 (0.01)</td><td/><td/></tr><tr><td/><td colspan="3">MNIST-Man 99.35 99.45 (0.04)</td><td>23K</td><td>104K</td><td>24.7K</td></tr><tr><td>SVHN</td><td>Maxout NiN</td><td colspan="2">98.10 97.70 (0.05)</td><td>1.07M</td><td>527K</td><td>52.6K</td></tr><tr><td/><td>SVHN-Man</td><td colspan="2">97.10 96.24 (0.05)</td><td>17K</td><td>88K</td><td>25.5K</td></tr><tr><td>CIFAR 10</td><td>VGG-16</td><td colspan="2">92.32 92.61 (0.14)</td><td>1.7M</td><td>13.3M</td><td>0.47M</td></tr><tr><td/><td>WRN-40-4</td><td colspan="2">95.09 95.42 (0.14)</td><td>4.3M</td><td>4.7M</td><td>1.7M</td></tr><tr><td colspan="2">CIFAR 100 VGG-16</td><td colspan="2">68.86 68.91 (0.17)</td><td>1.7M</td><td>13.3M</td><td>0.25M</td></tr><tr><td>ImageNet</td><td>AlexNet</td><td colspan="2">57.20 57.20 (0.03)</td><td>2M</td><td>59M</td><td>2.57M</td></tr></table>

Peer review (iclr2018):
 This paper tackles the important problem of structure learning by introducing an unsupervised algorithm, which encodes a hierarchy of independencies in the input distribution and allows introducing skip connections among neurons in different layers. The quality of the learnt structure is evaluated in the context of image classification, analyzing the impact of the number of parameters and layers on the performance. The presentation of the paper could be improved. Moreover, the paper largely exceeds the recommended page limit (11 pages without references). My main comments are related to the experimental section: - Section 5 highlights that experiments were repeated 5 times; however, the standard deviation of the results is only reported for some cases. It would be beneficial to include the standard deviations of all experiments in the tables summarizing the obtained results. - Are the differences among results presented in table 1 (MNIST) and table 2 (CIFAR10) statistically significant? - It is not clear how the numbers of table 4 were computed (size replaced, size total, t-size, replaced-size). Would it be possible to provide the number of parameters of the vanilla model, the pre-trained feature extractor and the learned structure separately? - In section 5.2., there is only one sentence mentioning comparisons to alternative approaches. It might be worth expanding this and including numerical comparisons. - It seems that the main focus of the experiments is to highlight the parameter reduction achieved by the proposed algorithm. There is a vast literature on model compression, which might be worth reviewing, especially given that all the experiments are performed on standard image classification tasks.