# Optimization of Linear Quantization for General and Effective Low Bit-Width Network Compression
## 3 Two-Stage Quantization Method
### Clustering
#### 3.2.1 K-Means  
K-means is a simple yet often effective algorithm for clustering. This algorithm has a high degree of interpretability and a relatively fast convergence speed. It only needs to adjust the number of centroids. For neural network quantization, the number of centroids is determined according to the quantization bit-width. Its basic idea is that for a given dataset  
Figure 6: Linear quantization loses inference accuracy when the bit-width is less than 5. \((Z_{1},Z_{2}\ldots Z_{m})\), the number of centroids K is calculated according to the bit-width, and the Euclidean distance is used as the similarity measurement. As shown in Equation (2), where \((M_{1},M_{2}\ldots M_{m})\) are the centroid sets, the dataset is divided into K clusters, and the centroids are updated iteratively. For this paper, we define the following symbols:  
* \(\text{Z}_{i}\) denotes the i-th weight;
* \(\text{M}_{j}\) denotes the centroid of cluster j;
* \(\text{R}_{j}\) is the subset of weights that form cluster j.  
\[\text{d}\big{(}Z_{i},\text{M}_{j}\big{)} =\sqrt{\sum_{\text{n}=1}^{\text{N}}\big{(}Z_{\text{in}}-\text{M}_ {\text{jn}}\big{)}^{2}} \tag{2}\] \[M_{j} =\frac{1}{|R_{j}|}\sum_{X\in R_{j}}X \tag{3}\]  
As described in Algorithm 1, the cluster centroids need to be initialized before the K-means algorithm starts. The results of the K-means algorithm are not stable and are greatly affected by the initial cluster centroids and outliers. Thus, a reasonable initialization scheme needs to be selected. This paper examines three methods to initialize cluster centroids:  
1. Random initialization;
2. Uniform partition;
3. Initialize by the optimization algorithm. The random initialization chooses K weights from the matrix as the initial centroids. In practice, different initial points may cause the inference accuracy to fluctuate by more than 10%. The initial center of the uniform partition is distributed between [min, max], which is greatly affected by the weight distribution and is not suitable for the bell-shaped distribution of the neural network. Particle swarm optimization (PSO) does not suffer from these problems. The main disadvantage of K-means is that it is sensitive to the initial centroid. The PSO algorithm based on population can reduce the impact of initial conditions because it will start the search from multiple locations in parallel. The detail is shown in Algorithm 1. ```
0: Dataset \(\text{D}=\{Z_{1},Z_{2}\ldots Z_{m}\}\), cluster centroids k
0: Result set \(\{R_{1},R_{2}\ldots R_{k}\}\)
1: Initialize k cluster centroids \(\{M_{1},M



#### 3.2.2 PSO-K-Means

PSO is a popular stochastic globalized search technique that uses the principles of the social behavior of swarms [27]. The basic idea of PSO is to find the global optimal solution through information sharing among the individuals in the group. In PSO, each potential solution is regarded as a particle. Each particle iteratively maintains and updates two basic properties: individual position and individual velocity. The velocity is used to evaluate the speed of particle movement, and the position represents the personal best position of the particle. In each iteration, the particle will search for its local optimal solution, update it as the individual extremum, and share the individual extremum with the entire particle swarm. The optimal individual extremum of the current iteration will be the centroid. In the PSO-K-means algorithm, each particle represents a cluster centroid, and the output of the PSO algorithm is used as the initial centroids for K-means. The K-means algorithm usually converges faster than PSO [30]. The performance of PSO can be improved by seeding the initial swarm with the results of the K-means algorithm [31]. The approach, named hybrid PSO, first performs the K-means algorithm once and stops iterating when the maximum number of iterations is exceeded.The hybrid PSO-Kmeans is detailed in Algorithm 2.