# Neural Architecture Search for a Highly Efficient Network with Random Skip Connections
## 3 A Highly Efficient Network with Random Skip Connections  
### Architecture Generation via a Neural Architecture Search  
Skip connections across multiple timestamps have been demonstrated to be beneficial for solving the gradient vanishing problem [13; 14], but too many remote connections would slow the network's execution speed down sharply, and unfortunately, it is difficult to select them by hand. Hence, we used a neural architecture search to manage this problem. First, we proposed a dense network that can provide a selection space for the skip connections, where the cell structure is based on that of the standard LSTM [15], which is defined as:  
\[\begin{array}{c}f_{1}=\sigma(W_{f}h_{t}+U_{f}y_{t-1}+b_{f})\\ i_{t}=\sigma(W_{t}h_{t}+U_{i}y_{t-1}+b_{i})\\ g_{t}=\sigma(W_{g}h_{t}+U_{g}y_{t-1}+b_{g})\\ o_{t}=\sigma(W_{o}h_{t}+U_{o}y_{t-1}+b_{o})\\ c_{t}=f_{t}\odot c_{t-1}+i_{t}\odot g_{t}\\ h_{t}=o_{t}\odot tanh(c_{t})\end{array} \tag{1}\]  
where \(\{\rm f,i,o\}_{\rm t}\) denote the forget, input, and output gates at time \(t\), respectively; \(\sigma\) denotes the sigmoid function; \(c_{t}\) represents the cell state; and \(\rm h_{t}\) indicates the output of the hidden layer. Taking the standard meaning, our cell structure can be formulated as:  
\[\begin{array}{c}f_{t}=\sigma(W_{f}x_{t}+b_{f})\\ i_{t}=\sigma(W_{i}x_{t}+b_{i})\\ c_{t}=f_{t}\odot\left(\begin{matrix}t-1\\ i=1\end{matrix}\omega_{i}c_{i}\right)+i_{t}\odot tanh(W_{c}x_{t}+b_{c})\\ h_{t}=c_{t},\end{array} \tag{2}\]  
where \(\sigma\) represents the sigmoid function, \(x_{t}\) is an input vector at \(t\)-th time step and \(\omega_{i}\) is a combination coefficient. In the cell structure, the forget gate \(\rm f_{t}\) only depends on the inputs at the current timestamp and the input gate \(\rm i_{t}\) only depends on the previous hidden vector, which is different from the standard LSTM; the benefit of this difference is analyzed in Section 4. Moreover, each cell receives state vectors from all of its counterparts at previous timestamps; this architecture consequently forms a dense network. A linear combination of coefficients can be obtained via network training until convergence, where a larger value of \(\omega_{\rm i}\) indicates a stronger remote dependency associated with the corresponding skip connection. Thus, it is reasonable to sample one connection and construct a new network. The probabilities of sampling are generated using \(\rm softmax(\{\omega_{i}|i=1,2,\cdots,t-2\})\), where the timestamp \(\rm t-1\) is excluded since its corresponding cell will be used in the constructed network.  
The framework of this process is depicted in Figure 1 and the auto-generated network is given as:  
\[\begin{array}{c}f_{t}=\sigma(W_{f}h_{t}+b_{f})\\ i_{t}=\sigma(U_{i}y_{t-1}+b_{i})\\ c_{t}=f_{t}\odot(\omega_{1}c_{t-1}+(1-\omega_{1})c_{s})+i_{t}\odot tanh(W_{c} x_{t}+b_{c})\\ h_{t}=c_{t},\end{array} \tag{3}\]  
where \(\rm c_{t}\) means a sampled state vector. Using this method, the network establishes one remote connection for each cell and is capable of shortening the path length of long-term dependencies. Note that when training the dense network, we can use a small number of hidden units to decrease the dimensions and accelerate the speed because only the dependency relationship needs to be explored. Then, we can use the proper number of hidden units to train the constructed network, which is concentrated on performance improvement.