# Block-Wisely Supervised Network Pruning with Knowledge Distillation and Markov Chain Monte Carlo
## 3 Method
### MCMC-Based Substructure Search  
Considering that all blocks can be independently optimized under an analogous manner, we use \(S\) to denote a block of the student network and \(Z\) to denote a substructure of \(S\) without loss of generality. Let \(L\) be the number of layers in block \(S\) and \(\xi_{j}\) be the number of filters in the \(j\)-th layer of block \(S\); we aim to find the optimal number of filters to be preserved in each layer. This problem can be defined as the following optimization problem:  
\[Z^{*}=\operatorname*{arg\,max}_{Z\in\Omega}\mathcal{R}(Z;\mathbf{X}) \tag{4}\]where \(Z=(z_{1},z_{2},\ldots,z_{L})\) represents a substructure, and each element \(z_{j}\) denotes the number of preserved filters or neurons in the \(j\)-th layer, \(\Omega=\{Z|0<z_{j}\leq\xi_{j},\forall j\in[1,L]\}\) defines all candidate substructures of the block \(S\), and \(\mathcal{R}(Z;\mathbf{X})\) is the performance metric defined in Equation (3) to evaluate the goodness of the substructure \(Z\).  
We select the preserved filters by ranking the filters with importance scores; therefore, there are \(\prod_{j}\xi_{j}\) candidate substructures that may constitute a large search space, suggesting an exhaustive search is impractical. Instead, with Equation (3), we sample substructures from the posterior under an MCMC scheme to find the maximum likelihood estimation (MLE) of the substructure. Formally, from the current state \(Z_{t}\), a new state \(Z_{t+1}\) is proposed based on transition probability \(q(Z_{t+1}|Z_{t})\). We sample a move from all feasible moves from \(Z_{t}\) to obtain the next state \(Z_{t+1}\). The feasible moves are defined by the following criteria:  
\[Z_{t+1}\in\{Z\big{\|}Z-Z_{t}\big{\|}_{1}<\varepsilon\} \tag{5}\]  
where \(\big{\|}Z-Z_{t}\big{\|}_{1}\) denotes \(\ell_{1}\)-norm, and \(\varepsilon\) is an integer number to bound the moves within a small space. Figure 2 illustrates the feasible moves under \(\varepsilon=2\). The proposals constrained by the above condition are called the neighborhoods of \(Z_{t}\). The move from \(Z_{t}\) to \(Z_{t+1}\) is accepted with probability:  
\[\rho=\min\biggl{(}1,\frac{q(Z_{t}|Z_{t+1})\mathcal{R}(Z_{t+1};\mathbf{X})}{q( Z_{t+1}|Z_{t})\mathcal{R}(Z_{t};\mathbf{X})}\biggr{)} \tag{6}\]  
To find the optimal solution, we initialize \(Z_{0}\) to meet a desired FLOPs' reduction rate and restart the MCMC chain multiple times. The maximally performing substructure during search is selected as the best solution. Each block of the baseline network is pruned by following the same procedure. A brief description of the MCMC scheme is provided in Algorithm 1.  
Figure 2: Illustration of feasible transitions from current state \(Z_{t}\) to next state \(Z_{t+1}\) under \(\varepsilon=2\). The added or deleted channel is marked by red border.  
```
1:A student block \(S\), input data \(\mathbf{X}\) in validation dataset, number of restarts \(N\), length of each MCMC repetition \(M\).
2:Reduced substructure.
3:for\(k=1\) to \(N\)do
4: randomly initialize \(Z_{0}\) to meet a desired FLOPs' reduction rate;
5:for\(t=1\) to \(M\)do
6:\(Z\gets q(\cdot|Z_{t-1})\);
7:\(u\gets U(0,1)\);
8: calculate probability \(\rho\) using Equation (6);
9:if\(\rho>u\)then
10:\(Z_{t}\gets Z\);
11:else
12:\(Z_{t}\gets Z_{t-1}\);
13:endif
14:endfor
15:\(Z^{(k)}=\operatorname*{arg\,max}_{i}R(Z_{t};\mathbf{X})\);
16:endfor
17:\(Z^{*}=\operatorname*{arg\,max}_{k}R(Z^{(k)};\mathbf{X})\);
18:return\(Z^{*}\).
```  
**Algorithm 1** MCMC scheme in BNP.