作者：Zhirong Wu Yuanjun Xiong Stella X. Yu Dahua Lin
方向：对比学习
会议：CVPR2018
地址：
Abstract:
有类别标签标注的神经网络分类器往往能够自动捕捉不同种类数据的视觉相似性，例如，当分类的对象是leopard，返回的分类结果有leopard（得分最高），jaguar（得分第二）和cheetah（得分第三）以及其他看起来逐渐不相似的种类（雪豹——猫——船）见图一。由此，分类结果往往不仅反应在语义标签上，更反应在视觉相似度上。即，视觉相似度并不是来自语义标签，而是来自数据本身。
作者因此想通过这一发现在传统监督学习领域进行扩展。让特征表示不再只区分类别而是区分每个实例。即引入在个体级别的无参分类器（non-parametric），将每一张图片当作类别，并使用softmax进行分类。类似于NLP中的Word2-vec方法，每个单词都是类别。
方法实现了ImageNet的sota，并且通过微调在半监督和目标检测上也取得了不错的效果，每张图片只有128维的特征也方便保存。
Related work:
作者在这里对度量学习进行了一定的介绍，以及相似工作的对比。
①首先个体的特征表示 F 可以引入两者之间的度量 y:d_F(x,y)=||F(x)-F(y)|| 因此特征学习又可看作度量学习，在人脸识别和行人再识别中度量学习都取得了很好的效果
②但在这些任务中测试的类别和训练的相分离。我们只能在神经网络训练得到的特征表示进行推断而不是他之后的线性分类器。
③度量中一个重要的人脸识别技术是normalization，文章同样采用。
④所有提到的方法或多或少带有监督性质，作者则完全没有。
⑤Exempler CNN类似于这篇文章，但采用了有参paradigm，计算量大。
Goal：
训练目标作者介绍很清楚：
结合图3看，就是在128维特征空间中，把训练目标拉得远，使得相似得目标更接近。
Method:
本文通过无语义类别标签的无监督学习，获得区分单个个体相似度的特征表示，并把它称作个体判别或者度量学习。
①在特征提取部分，代码中采用ResNet50作为backbone，获得的特征进行softmax分类。
②论文的softmax不设置参数w。而是和Word2vec一样把特征当作参数，并创建一个叫做memory bank的堆进行存储所有单词的128维特征，每次通过loss更新backbone和memory bank。这样训练和测试通过存储的memory bank同使用一个度量空间。
③测试时，使用KNN进行分类，由于同处一个度量空间，就可以避免过去很多无监督工作都依赖于线性分类器如SVM，但并不清楚为什么训练任务上的特征对一个测试任务同样线性可分的情况。
Non-Parametric Softmx Classifier:
n张图片 x_1,...,x_n 对应着n个类别，他们的特征表示为： v_i=f_\theta(x_i)
对于传统的有参softmax，对于图片 x_i 和特征 v_i ，它被当作第 i 个类别的条件概率为：
\qquad P(i|v)=\frac{exp(w^T_iv)}{\sum_{j=1}^{n}{exp(w^T_jv)}}
作者认为纯粹的参数w阻碍了个体之间的对比，于是文章采用的无参softmax，其中 \tau 是超参数， v 通过L2正则化：
\qquad P(i|v)=\frac{exp(v^T_iv/\tau)}{\sum_{j=1}^{n}{exp(v^T_jv/\tau)}}
训练目标即最大化联合概率： \prod_{i=1}^{n}P_\theta(i|f_\theta(x_i)) 又即最小化似然概率：
\qquad J(\theta)=-\sum_{i=1}^{n}logP_\theta(i|f_\theta(x_i))
这里的最大化联合概率连乘值是每次train_Loader返回的batch中的每一个值相乘。最大化联合概率的同时必然使得分母最小而分子最大，以此突出对比学习。又因为采样时，对应目标出现的概率最大，这样采用极大似然就能很好地估计模型参数。
Memory Bank
即将所有的图片128维特征保存到一个矩阵里面。每次和backbone产生的特征 v 相乘的 v_j 来自于这个矩阵，每次计算完后通过随机梯度下降更新backbone和这个矩阵。这样无论是训练还是测试就都来自于一个度量空间了。 当然，word2vec中，是在一定语境下预测目标单词，这里则是利用memory和backbone提取的特征时间差来更新，所以必须要有这样一个存储的数据结构。否则只有backbone的特征来自己乘自己，不能训练网络。
Noise-Contrastive Estimation(NCE)
NCE更换采样方式，将原先求多元问题转化成求二元问题，即softmax——sigmoid，之后根据经验分布的最大似然计算损失函数。
由上式可知，计算瓶颈在于分母，需要枚举所有图片，这样的计算复杂度是无法接受的。为了解决这一问题，我们不再采用原先的采样方式，而是用随机负采样，即从噪音分布当中进行采样，真实样本和噪音分布的数据比为 m，噪音分布当中采样 n 个数据，那么真实样本就采样 n/m 个数据（一般就为1个）这样原先的多元问题就转化为了二元问题，我们有如下式子：
\qquad P(i|v)=\frac{exp(v^Tf^i/\tau)}{Z_i}
\qquad Z_i=\sum_{j=1}^{n}{exp(v^T_jf_i/\tau)}
其中将 Z_i 当作一个归一化常数来处理，噪音分布采样概率为 1/n 那么D=1代表来自真实数据的采样分布：
\qquad P(D=1|i,v)=\frac{1}{m+1}P(i|v)
\qquad P(D=0|i,v)=\frac{m}{m+1}P_n(i)
总样本分布为：
\qquad p(i,v)=P^h(D=1|i,v)+P^h(D=0|i,v)
事实证明 m 越大，越准确。即两种似然估计能够对同一模型达到近似的效果。
则 v 属于第i个个体的后验概率为：
\qquad h(i,v)=P(D=1|i,v)=\frac{P(i|v)}{P(i|v)+mP_n(i)}
注意这里的 P(i|v) 是根据网络计算得出，而非真实分布，只有在充分优化，即NCE采样形式符合原分布时才可等价。
此时的最大似然函数更改为：
\qquad J_{NCE}(\theta)=-E_{p_d}[logh(i,v)]-mE_{p_n}[log(1-h(i,v'))]
Proximal Regularization
作者发现当以每个个体作为类别的时候，训练会有非常大的抖动，为了使训练更加平滑即将目标函数改为：
\quad J_{NCE}(\theta)=-E_{p_d}[logh(i,v^{(t-1)}_i)-\lambda||v^{(t)}_i-v^{(t-1)}_i||^2_2]-mE_{p_n}[log(1-h(i,v'^{(t-1)}))]
其中 v^{(t)}_i 来自于backbone， v^{(t-1)}_i 来自于memory bank。这样随着多次迭代，由于 v^{(t)}_i-v^{(t-1)}_i 的加入，backbone和memory bank存储的特征就逐渐相同了，回到了原始的损失，加速了收敛。
同时注意这里的memory bank的更新在代码中是通过动量的方式实现的。
Weighted k-Nearest Neighbor classifier
最后还是要回到分类问题上来。我们获得了训练好的模型后，对于一张图片提取他的特征，将他和memorybank中所有的存储图片特征计算相似度，然后采用k近邻算法，返回最相似的k张图片 \aleph_k ，然后根据权重投票，类别c会获得一个权重：
\qquad w_c=\sum_{i\in{\aleph_k}}^{}{\alpha_i*1(c_i=c)}
其中 \alpha_i 来自于相似度 s_i=cos(v_i,\bar{f})
\qquad \alpha_i=exp(s_i/\tau)
Experiment:
实验就不放了，比较经典的论文。大家可以自行查看
Code: 地址（git clone https://github.com/zhirongw/lemniscate.pytorch）
数据预处理：
# Data loading code traindir = os.path.join(args.data, 'train') valdir = os.path.join(args.data, 'val') normalize = transforms.Normalize(mean=[0.485, 0.456, 0.406], std=[0.229, 0.224, 0.225]) train_dataset = datasets.ImageFolderInstance( traindir, transforms.Compose([ transforms.RandomResizedCrop(224, scale=(0.2,1.)), transforms.RandomGrayscale(p=0.2), transforms.ColorJitter(0.4, 0.4, 0.4, 0.4), transforms.RandomHorizontalFlip(), transforms.ToTensor(), normalize, ])) if args.distributed: train_sampler = torch.utils.data.distributed.DistributedSampler(train_dataset) else: train_sampler = None train_loader = torch.utils.data.DataLoader( train_dataset, batch_size=args.batch_size, shuffle=(train_sampler is None), num_workers=args.workers, pin_memory=True, sampler=train_sampler) val_loader = torch.utils.data.DataLoader( datasets.ImageFolderInstance(valdir, transforms.Compose([ transforms.Resize(256), transforms.CenterCrop(224), transforms.ToTensor(), normalize, ])), batch_size=args.batch_size, shuffle=False, num_workers=args.workers, pin_memory=True)NCE采样，构造memory bank：（这里继承了一个Function来手动更新memory的梯度）
import torchfrom torch.autograd import Functionfrom torch import nnfrom .alias_multinomial import AliasMethodimport math#版本替换不用data了class NCEFunction(Function): @staticmethod def forward(self, x, y, memory, idx, params): K = int(params[0].item()) T = params[1].item() Z = params[2].item() momentum = params[3].item() batchSize = x.size(0) outputSize = memory.size(0) inputSize = memory.size(1) # sample positives & negatives idx.select(1,0).copy_(y.data) # 这里把y都给粘贴过去了，这是把第一列看作标签列[32, 65] # sample correspoinding weights 获得初始化权重 weight = torch.index_select(memory, 0, idx.view(-1)) weight.resize_(batchSize, K+1, inputSize) # [32, 65, 128] # inner product out = torch.bmm(weight, x.data.resize_(batchSize, inputSize, 1)) # -->[32, 65, 1] out.div_(T).exp_() # batchSize * self.K+1 x.data.resize_(batchSize, inputSize) # [32, 128] if Z < 0: params[2] = out.mean() * outputSize Z = params[2].item() # 这里的Z设置为了常数 print("normalization constant Z is set to {:.1f}".format(Z)) out.div_(Z).resize_(batchSize, K+1) self.save_for_backward(x, memory, y, weight, out, params) return out @staticmethod def backward(self, gradOutput): x, memory, y, weight, out, params = self.saved_tensors K = int(params[0].item()) T = params[1].item() Z = params[2].item() momentum = params[3].item() batchSize = gradOutput.size(0) # gradients d Pm / d linear = exp(linear) / Z gradOutput.data.mul_(out.data) # add temperature gradOutput.data.div_(T) gradOutput.data.resize_(batchSize, 1, K+1) # gradient of linear gradInput = torch.bmm(gradOutput.data, weight) gradInput.resize_as_(x) # update the non-parametric data weight_pos = weight.select(1, 0).resize_as_(x) weight_pos.mul_(momentum) weight_pos.add_(torch.mul(x.data, 1-momentum)) ## w_norm = weight_pos.pow(2).sum(1, keepdim=True).pow(0.5) ## updated_weight = weight_pos.div(w_norm) memory.index_copy_(0, y, updated_weight) return gradInput, None, None, None, None class NCEAverage(nn.Module): def __init__(self, inputSize, outputSize, K, T=0.07, momentum=0.5, Z=None): super(NCEAverage, self).__init__() self.nLem = outputSize self.unigrams = torch.ones(self.nLem) self.multinomial = AliasMethod(self.unigrams) # 别名采样法 self.multinomial.cuda() self.K = K self.register_buffer('params',torch.tensor([K, T, -1, momentum])); stdv = 1. / math.sqrt(inputSize/3) self.register_buffer('memory', torch.rand(outputSize, inputSize).mul_(2*stdv).add_(-stdv)) def forward(self, x, y): batchSize = x.size(0)# 32 idx = self.multinomial.draw(batchSize * (self.K+1)).view(batchSize, -1) # 通过别名采样的方式采样数据后获得的序号 out = NCEFunction.apply(x, y, self.memory, idx, self.params) return outNCE损失：
from torch import nneps = 1e-7class NCECriterion(nn.Module): def __init__(self, nLem): # 假设1000个类别 super(NCECriterion, self).__init__() self.nLem = nLem def forward(self, x, targets): batchSize = x.size(0) K = x.size(1)-1 Pnt = 1 / float(self.nLem) Pns = 1 / float(self.nLem) # eq 5.1 : P(origin=model) = Pmt / (Pmt + k*Pnt) Pmt = x.select(1,0) Pmt_div = Pmt.add(K * Pnt + eps) lnPmt = torch.div(Pmt, Pmt_div) # eq 5.2 : P(origin=noise) = k*Pns / (Pms + k*Pns) Pon_div = x.narrow(1,1,K).add(K * Pns + eps) Pon = Pon_div.clone().fill_(K * Pns) lnPon = torch.div(Pon, Pon_div) # equation 6 in ref. A lnPmt.log_() lnPon.log_() lnPmtsum = lnPmt.sum(0) lnPonsum = lnPon.view(-1, 1).sum(0) loss = - (lnPmtsum + lnPonsum) / batchSize return lossKNN：
def kNN(epoch, net, lemniscate, trainloader, testloader, K, sigma, recompute_memory=0): net.eval() net_time = AverageMeter() cls_time = AverageMeter() total = 0 testsize = testloader.dataset.__len__() trainFeatures = lemniscate.memory.t() if hasattr(trainloader.dataset, 'imgs'): trainLabels = torch.LongTensor([y for (p, y) in trainloader.dataset.imgs]).cuda() else: trainLabels = torch.LongTensor(trainloader.dataset.train_labels).cuda() C = trainLabels.max() + 1 if recompute_memory: transform_bak = trainloader.dataset.transform trainloader.dataset.transform = testloader.dataset.transform temploader = torch.utils.data.DataLoader(trainloader.dataset, batch_size=100, shuffle=False, num_workers=1) for batch_idx, (inputs, targets, indexes) in enumerate(temploader): targets = targets.cuda(async_=True) batchSize = inputs.size(0) features = net(inputs) trainFeatures[:, batch_idx*batchSize:batch_idx*batchSize+batchSize] = features.data.t() trainLabels = torch.LongTensor(temploader.dataset.train_labels).cuda() trainloader.dataset.transform = transform_bak top1 = 0. top5 = 0. end = time.time() with torch.no_grad(): retrieval_one_hot = torch.zeros(K, C).cuda() for batch_idx, (inputs, targets, indexes) in enumerate(testloader): end = time.time() targets = targets.cuda(async_=True) batchSize = inputs.size(0) features = net(inputs) net_time.update(time.time() - end) end = time.time() dist = torch.mm(features, trainFeatures) yd, yi = dist.topk(K, dim=1, largest=True, sorted=True) candidates = trainLabels.view(1,-1).expand(batchSize, -1) retrieval = torch.gather(candidates, 1, yi) retrieval_one_hot.resize_(batchSize * K, C).zero_() retrieval_one_hot.scatter_(1, retrieval.view(-1, 1), 1) yd_transform = yd.clone().div_(sigma).exp_() probs = torch.sum(torch.mul(retrieval_one_hot.view(batchSize, -1 , C), yd_transform.view(batchSize, -1, 1)), 1) _, predictions = probs.sort(1, True) # Find which predictions match the target correct = predictions.eq(targets.data.view(-1,1)) cls_time.update(time.time() - end) top1 = top1 + correct.narrow(1,0,1).sum().item() top5 = top5 + correct.narrow(1,0,5).sum().item() total += targets.size(0) print('Test [{}/{}]\t' 'Net Time {net_time.val:.3f} ({net_time.avg:.3f})\t' 'Cls Time {cls_time.val:.3f} ({cls_time.avg:.3f})\t' 'Top1: {:.2f} Top5: {:.2f}'.format( total, testsize, top1*100./total, top5*100./total, net_time=net_time, cls_time=cls_time)) print(top1*100./total) return top1/totalConclusion:
①提出了个体判别的代理任务。
②通过NCE做对比学习取得不错的无监督效果。
③提出一个新的数据结构存储负样本，并用动量方式更新特征。
但从代码上看，memory bank是一整个epoch才完成全部更新，每次迭代train_loader只能更新其中部分特征，但backbone却一直在更新，两者间会产生迭代时间上的矛盾，限制效率。而且每次更新完的特征只有一部分，这就导致memory bank存储的特征在时间上是不一致的，于是后来的MoCo采用队列的方式对其进行了改进。当然作者自身也意识到了这个方法的局限性，所以采用了Proximal Regularization来改进损失函数。
