Index

• Main idea
• K-means 聚类
  • 初始化
  • 实现
  • 优化
• Retrain
• Results

Abstract

Deep Compression中的量化过程首先使用K-means聚类, 得到k个聚类中心. 我们使用聚类中心代替具体权值, 这样, 属于不同聚类簇的权值只需根据index就可以得到量化后的权值.
例如, 原本一个[2048, 625]的矩阵存储了2048625=128000个单精度浮点数, 即: 12800004bytes=5000KB的权值. 我们将权值量化为256个聚类中心后, 只需存储12800002bytes+2564bytes=3524KB的权值, 为原来的70%左右.
很明显, 量化过程我们损失了一定的精度, 这对于最终模型性能有非常大的影响. 因此, 在进行聚类后, 我们需要进行再训练.

量化以及更新过程

上图说明了聚类以及更新中心的过程.
左上角4X4图为初始权值(weights, 32bit float), 并未进行量化.
在聚类后, 我们得到4X4的index(2 bit unit)以及对应index的中心(centroids). 在再训练过程中, 我们得到4X4的梯度值(gradients)后, 并不直接进行更新, 而是同一个聚类簇的梯度值累加. 然后我们只需要将对应中心的梯度乘学习率, 就可以更新centroids, 得到fine-tuned centroids.

所以整体过程可以概况如下:

1. 聚类得到k个聚类中心, 并记录对应index.
2. 再训练, 得到梯度值.
3. 累加同一聚类簇的梯度值, 并乘以学习率
4. 更新聚类中心.

K-means聚类

K-means是最基础的聚类算法, 其优点是简单, 在某些数据下表现不错.缺点是计算量大, 性能非常依赖k值的选取.
算法流程如下:

  1. 初始化k个centroid.
  2. 计算每一点到k个centroid的距离, 并将每一个点分类到最近centroid. 距离即我们最常用的欧几里得距离.
  3. 重新计算每一个聚类簇中心. 值得注意的是, 中心点不一定是"真实"存在的点.
  4. 重复step 2, 直到聚类簇不再变化.

• 初始化
  k值的初始化对聚类结果有较大影响. 常用的聚类中心初始化方法有:
  1. Frogy: 随机从待聚类点集选取k个点作为中心.
  2. Density-based: 基于密度的初始化选取.
  3. 使用Canopy聚类或层次聚类进行初始化聚类.
  4. Linear: 线性选取, 即得到最大点与最小点, 在其间均匀选取.
     在Deep Compression论文中论证了Linear初始化的效果更好.
• 实现
  k-means的实现可以用scipy.cluster或者sklearn.cluster中的k-means模块, 也可以自己写.
  k-means的实现可参照以下代码(待优化):

def k_means(weights,k, init_mode):
    center = []
     
    weights = np.ndarray.flatten(weights)
    if init_mode == 'forgy':
        while len(center) < k:
            temp = np.random.choice(weights)
            if temp not in center:
                center.append(temp)
    elif init_mode == 'linear':
        weights_max = max(weights)
        weights_min = min(weights)
        step = (weights_max-weights_min)/(k-1)
        for i in range(k):
            center.append(weights_min+i*step)
    else:
        raise ValueError('No mode named:{}'.format(init_mode))
    cata = [0]*len(weights)
    old_center = []
    while True:                                                                 
            
        #calculate distance from points to current center
        for i,point in enumerate(weights):
            temp = [cal_distance(point,c) for c in center]
            cata[i] = temp.index(min(temp))
            
        #update center
        for i,c in enumerate(center):
            center[i] = cal_center(weights, cata, c, i)
            
        if len(old_center)!=0 and center == old_center:
            break
        else:
            old_center = center
            
    new_center = []
    for i,val in enumerate(center):
        if val != None:
            new_center.append(val)
        else:
            for j,index in enumerate(cata):
                if index > i:
                    cata[j] = index-1
    return cata,new_center,len(new_center)

def cal_distance(x,y):
    return np.fabs(x-y)
         
         
def cal_center(weights,cata,c,i):
    sum = 0
    count = 0
    for j,val in enumerate(cata):
        if val == i:
            sum += cal_distance(weights[j], c)
            count += 1
    if count>0:
        return sum/count
         
def update_center(center, grad, cata, lr):
    update = [0]*len(center)
    grad = np.ndarray.flatten(grad)
    for i, val in enumerate(cata):
        update[cata[val]] += grad[i]
    for i,val in enumerate(center):
        center[i] = val - update[i]*lr
    return center
         
def update_weights(sess, wo, center, cata):
    wo_a = wo.eval()
    shape = wo_a.shape
    wo_a = np.ndarray.flatten(wo_a)
    for i,val in enumerate(wo_a):
        wo_a[i] = center[cata[i]]
    wo.load(np.reshape(wo_a,shape), sess)

Retrain

• Calculate gradients : 利用tf.gradients()以及tf.stop_gradients()可以对不同层求导.
• Update center: 求出梯度后, 分别将聚类簇内的点梯度值相加, 乘以学习率, 即可更新中心.

Results

本文将训练好的基于MNIST的cnn模型的网络压缩后, 在树莓派上进行实验.
cnn网络结构如下:

• conv1: weights=[3,3,1,32] strides=[1,1,1,1], relu1, dropout1
• conv2: weights=[3,3,32,64] strides=[1,1,1,1], relu2, dropout2
• conv3: weights=[3,3,64,128] strides=[1,1,1,1], relu3, dropout3
• fc4: weights=[12844, 625], relu5
• fc5: weights=[625, 10]

树莓派