Title: MULTIAGENT SYSTEM FOR LAYER FREE NETWORK

Abstract: We propose a multiagent system that have feedforward networks as its subset while free from layer structure with matrix-vector scheme. Deep networks are often compared to the brain neocortex or visual perception system. One of the largest difference from human brain is the use of matrix-vector multiplication based on layer architecture. It would help understanding the way human brain works if we manage to develop good deep network model without the layer architecture while preserving their performance. The brain neocortex works as an aggregation of the local level interactions between neurons, which is rather similar to multiagent system consists of autonomous partially observing agents than units aligned in column vectors and manipulated by global level algorithm. Therefore we suppose that it is an effective approach for developing more biologically plausible model while preserving compatibility with deep networks to alternate units with multiple agents. Our method also has advantage in scalability and memory efficiency. We reimplemented Stacked Denoising Autoencoder(SDAE) as a concrete instance with our multiagent system and verified its equivalence with the standard SDAE from both theoritical and empirical perspectives. Additionary, we also proposed a variant of our multiagent SDAE named "Sparse Connect SDAE", and showed its computational advantage with the MNIST dataset.

1. INTRODUCTION:

Figure 1 : Comparison of network structures with adjacency indications. Left: standard feedforward neural network with layer structure. The two solid rectangles represent the weight matrices. The connection is restricted by layer structure. Center: layer-free version of standard feedforward network. We need a whole n × n matrix indicated by the outer solid square to store parameters even when most of them become almost zero as a result of learning. Right: an example of network which is a subset of our proposed multiagent system. Matrices (solid rectangle) are no longer used. The network is free from the layer restriction while requiring fewer number of parameters. Communication between the nodes is prohibited unless they are connected with an edge, which leads to scalability, memory efficiency and biological plausibility.

Deep networks are used in many tasks, especially in image recognition, signal processing, NLP and robot manipulation. Almost all deep network models utilize structure with layers. One of the primary reasons to use those layer structure is to utilize parallel computation techniques and hardware level technologies such as GPU or dedicated tensor processors.

Layers can be viewed as a restriction on the connection pattern of the units that they must be aligned in a row to form a vector. Though layers are related to vector-matrix processing technologies and necessary to make use of them, it is not evident that this vector-matrix restriction is the most appropriate model to capture the latent representation of the data.

Vector-matrix approach requires dense matrices to store weight parameters even after sparse representations and weights are learned, which requires inefficient use of memory.

There are several methods to reduce the cost by downsize the model such as distillation (Hinton et al. (2014)) , and limiting the model space with binarizing (Courbariaux et al. (2015) ) and hashing Han et al. (2015) , but they still needs dense matrix filled with many zeros.

In this paper we propose a framework of multiagent calculation network that has feedforward matrix-vector network as a subset but free from the notion of layer to solve these problems.

Our multiagent network consists of many agents that replaces each unit in standard deep networks. The agents act autonomously and calculations are executed as an accumulation of many local level communication among the agents. This local calculation scheme is contrary to the previous feedforward network implementation that all computations in the units in the same layer is done simultaneously (Figure 1 ). Specifically, we reimplemented Stacked Denoising Autoencoder(SDAE) (Vincent et al. (2008) ) as one of the variations in our framework. SDAE is one of the earliest successful deep network model and free from spatiality assumption in CNNs and RNNs. SDAE is related to the Ladder Network (Rasmus et al. (2015) ) in that both employ reconstruction and denoising mechanism. We suppose starting from the model strictly derived from SDAE and gradually extending the model is one good approach to develop useful algorithms to construct deep multiagent networks. We show that the standard vector-matrix SDAE can be interpreted and reconstructed as a specific case of our multiagent network in the sense that both SDAE compute the exact same result in the end but with different implementations and processes.

Once we establish the basic multiagent SDAE, we aim to extend the SDAE and examine its behavior. One of the minimum and simplest modification to the proposed multiagent SDAE is to keep the node's locations and possible edge connections as they are, but randomly truncate the edges. We call this testing model "Sparse connect SDAE" or "SCSDAE" in the latter section. This model is an example of the potential of our model to handle sparse weight parameters more efficient than the standard networks composed of dense weight matrices.

Our contributions are the following.

1. We propose new multiagent-based neural network system framework that free from restrictions of layer scheme with matrix-vector while getting more biologically plausible.

2. We prove that SDAE can be reinterpreted as a special case of our multiagent system.

3. We also propose Sparse Connect SDAE, a primitive extension of our multiagent system.

4. We demonstrate the performance of the proposed models on XOR toy dataset and the permutation-invariant MNIST task. Foerster et al. (2016) and Sukhbaatar et al. (2016) model multiagent environment as a deep network, but their unit of agent is a whole network which models an individual actor and not a feature inside the network. The motivation and architecture of our proposal multiagent framework is different from theirs and we suppose our method could be a complementary method between the different granularities of agents.

2. RELATED WORKS:

There are several approaches to design biologically plausible model (Sussillo & Abbott (2009) ; Risi & Stanley (2014) ; Mi et al. (2014) ). Cao et al. (2014) convert regular CNN into spiking neural networks (SNN). Osogami & Otsuka (2015) build a variation of Boltzman Machine that follows the properties of Spike-timing dependent plasticity (STDP), which makes it more close to biological neural networks. Lee et al. (2014) proposes a modification of autoencoder that uses a novel credit assignment method called "target propagation" in place of back-propagation and achieved state of the art performance. It can be a solution to remove inherent biologiacal implausibility of back propagation.

Our SCSDAE is a variation of SDAE and can be viewed as a technique for truncating edges and reduce the computational cost. There are several techniques to downsize networks and enables us to load them on mobile devices for realtime processing. One example is distillation (Hinton et al. (2014) ). It needs huge networks as a superviser network and it cannot be used as a mean to full scratch to new domain. MADE (Mathieu et al. (2015) ) uses binary masking matrix to represent hard zero and thus conditional distribution. Limiting weight connection to binary (Courbariaux et al. (2015) ) is another approach and its applicability is actively studied. Han et al. (2015) combines pruning, quantization and Huffman coding together.

3. REIMPLEMENTATION OF DEEP NETWORK AS A MULTIAGENT SYSTEM:

In this section we describe our algorithm. First we show how we can reinterpret some common properties of multiagent systems to form a deep network. Next we define our multiagent system in general form. Then we prove the standard SDAE is indeed a special case of our multiagent system in the sense that both calculate the exact same computational result in the same order. Finally we show an example of our SDAE's variations.

3.1. THE PROPERTIES OUR MULTIAGENT SYSTEM SHOULD SUFFICE:

We extracted some common aspects of those multiagent system from the view of deep network development as follows:

1. The system consists of several number of autonomous units (as agents) and the environment.

2. All units are autonomous and only act when stimulated by messages from the other units and the environment.

3. Units process calculation only with local information they hold.

3.2. DEFINITION OF MULTIAGENT NETWORK:

In this section we define the multiagent system that has the properties we stated above.

• A system is consists of several units and one environment.

• Units are consists of nodes and edges.

• Edges connect between two nodes.

• Nodes has some variables and can memorize actual computed values of them.

The variables includes not only the input data and feature variables themselves, but parameters of adjacent edge's weights and intermediate variables that are needed to calculate feature variable's activation values. These additional variables can also be updated.

Nodes can transfer informations with other nodes connected with edges by message passing. These information may involve the value of variable computed by the units, the errors accumulated through epoch in the units, and any other things. Sometimes nodes may receive data input from the environment as a message, and may send value back to environment to let them compute global cost function.

The environment can manipulate unit from outside (via message passing) and change their relationships. For example,

• The environment can generate new unit.

• The environment can connect between nodes.

• The environment can change the state of the unit.

• The environment can send units input data.

These special manipulation may seems to break locality and autonomy, but its global manipulation is limited to changing the overall network structure. In the calculation process, the algorithm still run by agents local algorithm themselves rather than step-by-step instructions from the environment. The environment input some data to input units, and then, all it can do is to wait at the output units to get the result and it isn't aware of the internal behavior of each units and the order of execution.

Algorithm 2 is the general form of our proposed multiagent system. The notation is matched with the multiagent MLP in later sections. Note that the order of calculation is not yet specialized to match to standard MLP, and thus free from the constants related to global structure such as N x and N z .

3.3. THE EQUIVALENCE BETWEEN THE MULTIAGENT AND STANDARD VERSIONS OF SDAE:

We show how to reconstruct Stacked Denoising Autoencoder( (Vincent et al. (2008) )) with the proposed multiagent system.We concurrently prove that our multiagent version of SDAE and the standard SDAE have indeed the same algorithm and do the same calculation. In our case, we suppose that the two criteria below are sufficient for our objective

• the equivalence of the value computed

• the equivalence of the order of computation given the same input and the same random sampling. (e.g. initial parameters, order of input data, noise variables, etc.)

We begin our proof with a simple model and reuse it for prove of more complex models. Our first target model is the simple multi layer perceptron(MLP) with only one hidden layer and no pretraining.

We then go on to the autoencoder and Denoising Autoencoder, which is a kind of extension of MLP.

Finally we show the equivalence of the two SDAEs.

For bravity, we limit the choice of activation function for each unit to sigmoid, and we use unit-wise mean square error (MSE) for cost function. We also use simple SGD without minibatch. There are several methods that empirically known to perform well. (e.g. Adam (Kingma & Ba (2014) ) for optimization, cross entropy for cost function, ReLU and softmax for activation function.) However we prioritize to establish the basic architecture of deep multiagent network, and choose these simpler methods. We can also extend the algorithm to apply minibatch updating easily.

3.3.1. EQUIVALENCE WITH MLP:

Now we prove the equivalence of our proposed multiagent version of MLP and standard implementation.

Suppose there is a MLP consists of an input layer, a hidden layer and an output layer. Let N x , N y , N z be the number of input, hidden and output layer's dimension respectively. Simillary, let

x i (i = 1 • • • N x ), y j (j = 1 • • • N y ), z k (k = 1 • • • N z )

be the activated output value (hereafter simply "output value" ) at each unit in each layer respectively. The weight value between these variables are w ij , w jk , thus the forward propagation from input to hidden is calculated by

y j ← σ(w 0j + Nx i=1 w ij x i ) and from hidden to output is z k ← σ(w 0k + Ny j=1 w jk y j ). Here Θ = {w ij , w jk | i = 0 • • • N x , j = 0 • • • N y , k = 1 • • • N z }

represents the weight parameters and σ is the sigmoid function. We also define dataset D = {(x

(1) data , t (1) data ), • • • , (x (D) data , t (D)

data )} as an array of pairs of input data x

(d) data = {x (d) 1 data , • • • , x (d)

Nx data } and label data t Next we construct a multiagent network that is equivalent to Algorithm 1 by specializing the general Algorithm 2. We first generate units u xi , u yj , u

z k (i = 1 • • • N x , j = 1 • • • N y , k = 1 • • • N z ) from the environment. We also denote the set of units U x = {u xi | i = 1 • • • N x },

and similary U y , U z for set of all u yj , u z k respectively. Each unit and the environment possess the unique varibles as listed in Table 1 .

Algorithm 1 Standard MLP Initialize w ij , w jk for all (i, j), (j, k) while criteria is not satisfied do

for d = 1 • • • D do for k = 1 • • • N z do t k ← t (d) k data end for for i = 1 • • • N x do x i ← x (d) i data end for for j = 1 • • • N y do y j ← σ(w 0j + Nx i=1 w ij x i ) end for for k = 1 • • • N z do z k ← σ(w 0k + Ny j=1 w jk y j ) δ k ← 2 Nz (z k -t k )z k (1 -z k ) for j = 1 • • • N y do w jk ← w jk -ηδ k y j end for end for for j = 1 • • • N y do δ j ← y j (1 -y j ) Nz k=1 w jk δ k for i = 1 • • • N x do w ij ← w ij -ηδ j x i end for end for L (d) ← 1 Nz Nz k=1 (t k -z k ) 2 end for L ← D d=1 L (d) end while

Algorithm 2 General form of our multiagent algorithm (the environment) Initialize u xi , u yj , u z k for all i, j, k while criteria is not satisfied do for 

all d ∈ {1 • • • D} do for all u z k ∈ U z do Input t (d) k data to u z k end for for all u xi ∈ U x do Input x (d) i data to u x end for L (d) ← k (t k -z k ) 2 end for L ← d L (d) end while Algorithm 3 Multiagent MLP (the environment) Initialize u xi , u yj , u z k for all i, j, k while criteria is not satisfied do for d = 1 • • • D do for k = 1 • • • N z do Input t (d) k data to u z end for for i = 1 • • • N x do Input x (d) i data to u x end for L (d) ← 1 Nz Nz k=1 (t k -z k ) 2 end for L ← D d=1 L (d)

u xi (i = 1 • • • N x ) x i u yj (j = 1 • • • N y ) y j , δ j , w ij (i = 1 • • • N x ), η u z k (k = 1 • • • N z ) z k , t k , δ k , w jk (j = 1 • • • N y ), η The environment L, L (d)

The unit u xi corresponds to x i and receive x i data from the environment. The unit u z k corresponds to both z k , t k and is input t k data . Each u xi receive input data, assign the data into the variable owned by itself, then send that value as message to u yj (algorithm 6).

u yj corresponds to y j and stores w ij (i = 0 • • • N x ) to calculate y j . The unit must wait until receive message from all u xi (i = 1 • • • M ). Then the unit can calculate y j (algorithm 4). The calculated value of y j is sent again to u z k , so similary z k can also become able to be calculated.

We also need to introduce a state variable for SDAE. We will discuss it at the end of this section.

Finally, the environment inputs data in the following order:

u z1 → • • • → u z Nz → u x1 → • • • → u x Nx (Algorithm 3

). These inputs stimulate units and the units invoke their message handling algorithm individually. The information required to calculate the cost function L (d) is eventually acumulated in the units u y k . The environment would read out these and calculate the objective L (d) .

3.3.4. EQUIVALENCE WITH STANDARD SDAE:

We finally reimplement the whole SDAE algorithm by our multiagent system and show its equivalence with the standard version again. The learning process of SDAE can be divided into pretraining and fine-tuning and we can explain the two phase separately.

pretraining phase In the pretraining phase of SDAE, let x i , y i , z i be the input, hidden, the associated reconstruction layer value of DA, respectively. To stack a learning DA, y j is considered as a new input units from the view of the new DA. Let z j be the reconstruction unit's value of y j itself, and y k be the new stacked hidden layer units. We make a full connection between each layers. Thus the equations relating to these variables change to y k ← σ(w 0 + Ny j=1 w jk y j ) and z j ← σ(w 0 + N y k=1 w kj y k ). The new objective function after the stacking is L j = 1 Ny Ny j=1 (z j -y j ) 2 . Note that by stacking a new DAE layer, we are making a new task of objective function from the previous objective. Now we describe the change needed on our multiagent system. We need to introduce the notion of state for the units associated with the hidden layers in the standard version. When the objective function changed, the network structure and the state of the units must be changed in response too.

The hidden units can take the the two states, "state A (On learning)" and "state B (Learned, stable)". The units are initiated to "state A" and the behavior in this state doesn't change from the previous sections. But the units in "state B" doesn't send messages to the units for reconstruction z i and instead send the same messages to the "state A" units in the stacked layer.

Additionary, we need to append a reconstruction unit for each hidden unit changed to "state B". These pairs of the "state B" unit and appended reconstruction unit act as same as the pairs of input and reconstruction units we stated in DAE section except that they send message not after the data is input, but after the feature y j is calculated.

Once the pretraining for one block of DAE ends, all the hidden units in that DAE change to "state B". Then they form a new DAE starting from "state B" hidden units through the new stacked "state A" units then the associated reconstruction units appended. This DAE can be optimized in the same way of the single multiagent DAE we have described with only one exception that the data is not sent from the environment, but instaed the feature value y j in the previous DAE is calculated in the same order (j = 1 • • • N y ) fine-tuning phase In order to use SDAE for supervised learning task, we pretrain some predefined number of hidden layers by layerwise pretraining, and at the end stack the layer for supervised purpose (typically a softmax layer for classification). This is another form of the change of the objective function and the multiagent system can deal with it too by changing network and unit's state.

Specifically, when the all pretraining phase ends, connect the output units for supervised learning onto the topmost hidden units, and all feature unit changes its state to the newly introduced "state C (On fine-tuning)". The "state C" is almost the same as "state A", but the only differences are the two:

• They don't send message to reconstruction units.

• They always send backpropagation message to the previous units.

This backpropagation message must be sent in ascending order as well as the previous message passing.

Here we reinterpreted the standard pretraining and fine-tuning algorithm with our proposed multiagent system. These two cover the all learning phase of SDAE, therefore we have successfully reinterpreted the whole SDAE and showed its equivalence of the standard SDAE.

3.4. SPARSE CONNECT SDAE:

Now we obtain new multiagent SDAE, and theoritically showed its equivalence to standard SDAE. Next we want to extend this model and experiment its behavior. One of the minimal and simplest We gradually changed the connectivity rate of our proposed SCSDAE and compare its performance.

In this experiment, we measure the performance by the two aspect, the error rate and the calculation time, because we expect that the less number of edge mean the less calculation in time in our model as we described in chapter 3.

Figure 3 shows the meausred calculation time and Figure 4 for the error rate. In both figures the horizontal coordinate indicates the number of iterated epochs and the vertical is for time and error rate, respectively. From Figure 3 , we can verify that the calculation time decreases linearly as we expected.

Figure 4 shows the error rate on test set after the given number of epochs passed. Contrary to our intuition, it can be said that in some cases despite of the decrease in connection probability, error rate do not deteriorate. The reason is not obvious, but we suppose that the more connection established, the more it became difficult and time requiring to the model to converge enough to show the potential of the model class. It can be also possible that the forced sparsity gave the model unexpected advantage to obtain sparse coding efficiently.

5. CONCLUSION:

We proposed a fundamental framework to reinterpret deep networks as multiagent systems. Specifically, we reimplemented a model equivalent to Stacked Denoising Autoencoder(SDAE) but the inside implementation is given with the multiagent system. We verified this equivalence from both theoritical and empirical aspects. We also tested the behaviour when we actually let the model drop some edges permanently and demostrated the reduction of computation time as the connection rate decreases.

Our contribution is to propose new multiagent based neural network system that free existing deep network from restriction of layer scheme. Our system involves the standard SDAE as its subset and has large potential of extension. Our model could be extended to more biologically plausible variation. Our experiment with the proposed Sparse Connect SDAE demostrate the advantage of non-matrix calculation and permanent drop of edges.

The next step is to sophisticate the model so that the agents are more strictly independent from the environment. Then we will be able to use this system as a framework for extending more flexible deep network. For example, we can make arbitrary connection of units. We can also consider mixing of units with different activation function, dropout strategy, learning rate.

:



Figures and Tables:

Nz data }, where d = 1 • • • D. Hereafter we might drop the data index (d) for readability.We define our objective function as L = D d=1 L(d) , whereL (d) = 1 Nz Nz k=1 (t k -z k ) 2and η be a learning rate. Algorithm 1 is the standard version algorithm to optimize this objective.

Figure 3: Mean calculation time for connectivity rate averaged over 3 experiments for each connectivity. The horizontal axis indicates connectivity rate of each model and the vertical shows time spent in training.

Figure 4: Mean error rate for connectivity rate averaged over 3 experiments for each connectivity. The horizontal axis indicates connectivity rate of each model and the vertical for error rate in test dataset.

Figure 2: Mean classification error rate (left: standard SDAE, right: multiagent SDAE). The vertical coordinate indicates their error rate and the horizontal for epoch count. Both SDAE result in almost the same shape.

end while Varibles each unit (and the environment) possess in multiagent MLP

Table content: <table><tr><td>Unit</td><td>Variable</td></tr></table>

Difference of the largest weight change for one input between multiagnet and normal SDAE

Table content: <table><tr><td>Group of edges</td><td>Largest difference</td></tr><tr><td>input to hidden</td><td>1.08 × 10 -19</td></tr><tr><td>hidden bias</td><td>0.0</td></tr><tr><td colspan="2">hidden to output 8.7 × 10 -19</td></tr><tr><td>output bias</td><td>0.0</td></tr></table>

Peer review (iclr2017):
Unfortunately, the paper is not clear enough for me to understand what is being proposed. At a high-level the authors seem to propose a generalization of the standard layered neural architecture (of which MLPs are a special case), based on arbitrary nodes which communicate via messages. The paper then goes on to show that their layer-free architecture can perform the same computation as a standard MLP. This logic appears circular. The low level details of the method are also confusing: while the authors seem to be wanting to move away from layers based on matrix-vector products, Algorithm 4 nevertheless resorts to matrix-vector products for the forward and backwards pass. Although the implementation relies on asynchronously communicating nodes, the “locking” nature of the computation makes the two entirely equivalent.