不均衡数据集的分类模型学习方法

简介

不均衡数据集指的是在分类问题中,数据集的两个类别之间的数量差别到达100:1,1000:1甚至10000:1的情况。当然,有些时候在多分类问题(multiclass classification)中也会出现。

如何在不均衡的数据集(imbalanced data)下进行学习,是一个很重要的问题,原因是这样的数据集会很大程度上限制我们的分类模型的准确性,正如文章所说——

“大部分标准的分类算法都期待一个均衡的类别分布,以及相近的误分类损失”。

在不均衡数据集的研究中,主要的领域有医疗分析、欺诈检测、网络入侵识别、溢油检测等。一个非常经典的数据集是乳腺摄影数据集(Mammography Data Set),在这个数据集中,有若干医学摄影图片以及其对应的二分类标签「健康」,「癌性」。

Image result for mammography data set
Mammography Data Set

在这个数据集中,有10923例阴性以及260例阳性。使用传统分类算法,非常容易出现的情况就是,阴性以几乎100%的正确率被成功分类,但是阳性的分类正确性却低至10%以下,在这个情境下,就是多达234例阳性样本被误诊。

在这一类数据集下,我们的目标就变成了在不严重损害大类(major class)的准确性的基础上,尽量让小类(minor class)的分类准确性提高。

不均衡问题的特性

内在不均衡和外在不均衡

数据集不均衡的成因可能是内在的(intrinsic)或者外在的(extrinsic),如之前所述的肿瘤识别,由于样本在真实世界的分布本身就是不均匀的,所以是内在不均衡。

另一方面,还会有一些情况,原本均匀分布的样本数据,由于采样偏差,导致最终进入数据集的时候样本不均匀了,这种情况则被称之为外在不均衡。这个情况最为著名的就是“欺诈检测”数据集。因为真实世界中,那些欺诈者,基本在申请阶段就已经被拒贷了,而我们无法获取到“如果他们借了钱,会不会逾期”,进而无法进入我们的训练数据集。

类间不均衡和类中不均衡

类间不均衡与类中不均衡同样值得注意,正如下图所示,在一些比较复杂的数据上,不仅不同的类别个数相差巨大,同一类样本之间,也会有不同的概念。对于小类别中间的小样本,样本数极少(underrepresented),分类器非常难以学习到完整的分类函数。

图a)只包含了类间不均衡,即五角星表示的“小类”样本个数远小于“圆圈”代表的“大类”,
图b)则同时包含了类间不均衡、类中不均衡、重叠、噪音等等……

小样本问题(small sample size problem)是传统不均衡问题之外的新兴研究方向,讲的是数据的维度和样本的个数显著不均衡。比较有代表性的有人脸识别、基因序列分析等。对于单纯的小样本问题,传统的做法有数据降维等措施。但是倘若小样本问题和类别不均衡同时存在,不仅小类中的样本数量过于稀缺,而且也会导致传统的解决算法无法归纳出有效的分类函数。是以后的研究重点。

不均衡数据集学习的state-of-art算法

当标准的学习算法遇上不均衡数据时,归纳出来的用于描述小类的规则通常比描述大类的规则要少要弱。这既是由于标签数量上的差别,又是由于小类的样本由于数量少本身可信度就较低。

基于采样的算法

Random Sampling

分为随机过采样(random oversampling)和随机欠采样(random undersampling),随机过采样的思路是从小类里面,随机复制若干样本点,加到原来的集合中,使数据集均衡。而随机欠采样则是从大类里面,随机删除若干样本点,使得数据集分布均衡。

随机欠采样可能导致遗失某些重要的信息,而随机过采样则有过拟合风险。

Informed Undersampling

首先讲讲Easy Ensemble算法,这个算法很简单,使用多次随机欠采样,每次都训练一个分类器,然后再将每次欠采样训练出来的分类器组合到一起,形成最终的分类器。

接着是Balance Cascade算法,这个算法是一个迭代算法。

  1. 在大类样本集合S_{maj}中选择一个子集E满足|E| = |S_{min}|
  2. 使用N = {E \cup S_{min}}进行训练,得到分类器
  3. 过滤出N中所有被正确归类的大类中的样本N_{maj}^*
  4. N_{maj}^*中的样本点剔除S_{maj},回到第1步

还有基于KNN的采样算法,该算法使用的四个规则来筛选出比较重要的大类样本点,用这些重要的样本点进行模型的训练。

  • NearMiss-1方法选择与“三个最接近的小类样本”的平均距离最小的大类样本点;
  • NearMiss-2方法选择与“三个最远的少数类样本”的平均距离最小的大类样本点;
  • NearMiss-3方法为每个小类样本选择给定数量的最接近的大类样本点,以确保每个小类样本点都被一些大类样本点包围;
  • “最大距离”方法选择了大多数类的样本点,这些样本点与“平均距离是最近的三个少数类”距离最大。

研究发现,其中NearMiss-2获得的结果较好。

Synthetic Sampling With Data Generation

合成少数子过采样技术(the synthetic minority oversampling technique, SMOTE)对于每个小类样本,寻找同为小类的K近邻,并使用插值法随机选取其连线中间的一个点最为一个新的过采样点。

(1)   \begin{equation*}x_{new} = x_i + (\hat{x_i} - x_i) \times \delta\end{equation*}

具体来说,上式中x_i为小类中的一个样本点,\hat{x_i}x_i的位于小类集合中的K近邻之一,\delta是一个随机[0,1]区间内实数。

Adaptive Synthetic Sampling

先介绍Borderline-SMOTE算法,和普通SMOTE算法不同的是,Borderline-SMOTE算法对于每一个小类样本点,都统计了其最近邻居中大类和小类的样本点个数。

  • 如果小类邻居多于一半,则该点是内部点,记为SAFE
  • 如果小类邻居少于一半,则该点是边界点,记为DANGER
  • 如果小类邻居为0,则该点为噪声,记为NOISE

统计完成后,使用DANGER集合点进行SMOTE的过采样算法。

ADASYN算法在此基础上又做了优化,去掉了“一半”这个人为的常数。使得过采样更加的自然。

(2)   \begin{equation*}G = (|S_{maj}| - |S_{min}|) \times \beta\end{equation*}

这里面\beta \in [0,1]是一个人为设计的常数,G是描述了“究竟小类需要补充多少个样本点?”

接下来,对于每一个小类样本点计算

(3)   \begin{equation*}\Gamma_i = \frac{\Delta_i / K}{Z}\end{equation*}

其中\Delta_i表示样本点的K近邻中有多少属于大类S_{maj}KZ用于归一化,使得\sum_{\Gamma_i} = 1

最终,每一个点按照下面式子,计算需要生成的点的个数,并使用SMOTE算法的方式进行过采样

(4)   \begin{equation*}g_i = \Gamma_i \times G\end{equation*}

Sampling With Data Clean Technique

Tomek link是一个基于数据清洗的技术,适用于一个经过过采样之后的数据集。其目的是为了解决“由于过采样导致的类别存在边界覆盖,进而影响分类器训练”这个问题。

其核心思想是找到两个离的很近的x_i \in  S_{maj}x_j \in S_{min},令d(x_i, x_j)表示x_ix_j的距离,那么(x_i, x_j)被称为Tomek link当且仅当不存在x_k,满足d(x_i, x_k) < d(x_i, x_j)d(x_j, x_k) < d(x_i, x_j)

Tomek link的出现意味着x_ix_j要不然有一个是噪音,要不然就是他们两个位于分类的交界处。将他们同时删除(或删除大类的那一个),可以有效的防止出现类别边界模糊,有利于提高分类器效果。

Cluster-Based Sampling Method

基于聚类的采样算法可以保证类间的不均衡也被关注。

具体来说,该算法首先使用迭代的方式,找到不同的团,这里使用了经典的KNN算法——

  1. 在两个类别中,分别随机选择K个团中心;
  2. 对于每个样本点,都被归类到最近的团中心;
  3. 团中心进行重新计算,用当前所有归类到该团的样本的坐标均值作为新一轮迭代的团中心;
  4. 跳至第2步

接着,将不同的团使用过采样的方式放大到同等规模。如下图所示——

Integration of Sampling and Boosting

SMOTEBoost 算法分为若干轮,每一轮都涉及到重新采样,使用递增的方式建立模型。每一轮,都着重采样哪些不能被上一轮模型所解释的样本。这样,分类器会逐渐习惯去拟合哪些少数的样本,因为他们更大概率会不能被上一轮的模型分类。

对于DataBoost-IM算法来说,则依照一定的比例来采样那些不容易被学习的样本。

基于修改成本函数的算法

一些对于成本敏感的学习算法,使用成本(cost)函数来量化误分类的程度。与其像基于采样的算法构造均衡的数据分布,不如直接设计一个不同的算是度量,使之能够适应不均衡的数据。

Cost-Sensitive Learning Framework

我们定义C(Min, Maj)表示将大类样本误分类为小类的成本,C(Maj, Min)则相反。那么成本敏感(cost-sensitive)学习的目标就是最小化训练集的总体成本,也就是所谓的贝叶斯条件风险(Bayes Conditional Risk)。

这个函数也可以非常容易的扩充到多标签的分类中,具体C矩阵定义如下——

此时,条件风险被定义为

(5)   \begin{equation*}R(i|x) = \sum_i{P(j|x)C(i,j)}\end{equation*}

这里P(j|x)被定义为给定样本x,实际上为类别j的概率。

通常的分类器,都默认分类错误有1的代价,而分类正确没有代价——

(6)   \begin{equation*} C(i,j) = \left\{ \begin{aligned} 1 & (i \neq j) \\ 0 & (i=j) \end{aligned} \right.\end{equation*}

而在非均衡学习中,我们需要保证有C(Maj, Min) > C(Min, Maj),以使得分类器能够更好地分辨大类小类。而接下来的算法,一大特点就是都使用了不同的办法,来讲我们认为定义的成本矩阵放到具体算法实现中——

  • 第一类技术将误分类成本作为数据空间权重应用于数据集;
  • 第二类将成本最小化成本的技巧运用在模型组合上;
  • 最后一类技术将对成本敏感的函数或特性直接纳入分类模型中,以便将对成本敏感的框架拟合到这些分类器的结果中。

Cost-Sensitive Dataspace Weighting with Adaptive Boosting

这里涉及了AdaBoost系列算法,包括AdaBoost.M1,AdaC1,AdaC2,AdaCost,CSB1,CSB2。以AdaBoost.M1为例讲解这类算法的核心思路——

对于数据集迭代,每一轮拥有不同的权值D_{t}(i)

(7)   \begin{equation*}D_{t+1}(i) = D_t(i) exp(-\alpha_t h_t(x_i) y_i) / Z_t\end{equation*}

其中\alpha_t = \frac{1}{2} ln(\frac{1-\epsilon_t}{\epsilon_t})。这个式子的粗略理解是如果一个样本被误分类,那么下一轮迭代将拥有更大的权值。

Cost-Sensitive Decision Trees

决策树的叶子节点是类别,非叶子节点是规则。建立决策树的过程是从上到下,逐层挑选一个最有分类性的规则,并将样本按照这个规则递归到两个子树处理。

Contact-lens decision tree
决策树

决策树有两个步骤,第一个是从上到下的分裂,第二个是从下到上的修建。

决策树的分裂使用了不纯度函数(impurity function),这个函数是否超过特定阈值决定了一个节点的分裂与否。不同的不纯度函数对于不均衡数据有不同的敏感度,比如传统的准确率函数就非常敏感,而Gini函数、熵函数(Entropy)、DKM函数就不那么敏感。其中,DKM函数生成的未修剪决策树相对较小。

决策树的修剪有利于增加其普遍性,但是对于不均衡数据,决策树的修剪可能会减掉小类的样本,降低模型准确度。类似于Laplace修剪技术也被提出用于让决策树的修剪不那么糟糕。

Cost-Sensitive Neural Networks

一个神经网络,会构造基于模型输出与目标距离的损失函数

(8)   \begin{equation*}E(\omega) = \frac{1}{2} \sum(t_k - o_k)^2\end{equation*}

其中\omega是模型权值,t_k,o_k分别是模型的目标与输出。在每一轮迭代,神经网络都会计算每个权值对于损失函数的梯度,用这个梯度更新权值,使得网络误差函数更小。

(9)   \begin{equation*}\Delta \omega_n = -\eta \nabla_{\omega} E(\omega_n)\end{equation*}

其中\eta是学习速率,\nabla_{\omega}是梯度算子。

成本敏感学习可以以下面四种方式引入模型——

  1. 成本敏感可以体现在对最终估计概率的修正上面
  2. 模型输出o_k可以被修正为成本敏感
  3. 学习速率可以被修正为成本敏感
  4. 误差函数最小化中的误差可以是成本敏感的

这四种方式都各有非常多的研究成果,这里就略去不谈。

基于核函数的算法和主动学习

Kernel-Based Learning Framework

这里讨论支持向量机(SVM)在不均衡数据集下的研究。由于支持向量机试图最小化总误差,因此它们天生就有优化大类样本的偏好。在一个理想模型里面,大类小类通过一条直线分隔,SVM分类的界限将远远偏离实际的界限。

Integration of Kernel Methods with Sampling Methods

大量研究都尝试将采样算法与SVM结合,其中比较有代表性的是GSVM-RU,将GSVM与欠采样算法结合。通过迭代的算法,每一轮迭代,都将大类中被定为支持向量的样本点移出。实现欠采样的目标。

位于最大间隔超平面边界上的点被称为支持向量

Kernel Modification Methods for Imbalanced Learning

直接修改核函数也是很多研究者研究的方向,这些研究的共同点是尝试向原来的SVM添加一个模块或替换一个模块,实现对不平衡数据的支持。包括了LOO-AUC、PSVM、P2PKNNC等等算法

Active Learning Methods for Imbalanced Learning

主动学习通过某种策略找到未进行类别标注的样本数据中最有价值的数据,交由专家进行人工标注后,将标注数据及其类别标签纳入到训练集中迭代优化分类模型,改进模型的处理效果。

在主动学习领域,文章指出,主动学习和基于核函数的学习算法有共通之处,所以有必要放在一起讨论。比如说,一个在SVM算法中靠近超平面的样本点就是比较有意义的。当然,如果遇到了数据不均衡,主动学习也会有很多需要研究的问题。

Additional Methods for Imbalanced Learning

不均衡数据的处理方式还有很多无法被分类到之前类别的算法。比如所有的多标签算法、小样本数量的处理算法、基于单个标签的学习算法等等。

评价指标

使用下表来定义正/负样本被模型正确/错误分类的个数,是后续统计指标的基本依赖变量——

True positives(TP):  被正确地划分为正例的个数,即实际为正例且被分类器划分为正例的实例数;
False positives(FP): 被错误地划分为正例的个数,即实际为负例但被分类器划分为正例的实例数;
False negatives(FN):被错误地划分为负例的个数,即实际为正例但被分类器划分为负例的实例数;
True negatives(TN): 被正确地划分为负例的个数,即实际为负例且被分类器划分为负例的实例数。 

单数值指标

这里假设小类为正类(positive),大类为负类(negative),有准确率(accuracy)和错误率(error rate)

(10)   \begin{equation*}Accuracy = \frac{TP+TN}{P_C+N_C}\end{equation*}

(11)   \begin{equation*}ErrorRate = 1 - Accuracy\end{equation*}

(12)   \begin{equation*}Precesion = \frac{TP}{TP+FP}\end{equation*}

(13)   \begin{equation*}Recall = \frac{TP}{TP+FN}\end{equation*}

(14)   \begin{equation*}F\_{Measure} = \frac{(1+\beta)^2 \cdot Recall \cdot Precesion}{\beta^2 \cdot Recall + Precesion}\end{equation*}

(15)   \begin{equation*}G\_{Mean} = \sqrt{\frac{TP}{TP+FN} \times \frac{TN}{TN+FP}}\end{equation*}

对于(1)(2)来说,虽然比较符合常理,但是容易被欺骗,比如对于5%正类,95%负类的数据,全部分类为负类可以达到95%正确率。这类“对于分布敏感”的指标不是用于不均衡数据集的算法效果评估。

对于精准率(3)来说,描述了“对于所有被分类器预测为正的样本,有多少预测对了?”
对于召回率(4)来说,描述了“有多少真正是正的类别,被正确预测了?”
通过观察公式,可以发现,精准率(3)是数据分布敏感的,而召回率(4)是数据分布不敏感的。
如果使用恰当的话,精准率和召回率已经足以描述用以评价分类器好坏的所有信息了。

F-Measures(5)是精准率率和召回率的合并,并用参数\beta调整双方的权重

G-Mean(6)则使用了正类准确率和负类准确率的比例来刻画分类器的偏好。

上面这些单变量指标虽然已经足够好了,但是还是没法解决一个问题“如何比较两个分类器孰好孰坏?”

ROC曲线

定义真阳性率(TPRate)和假阳性率(FPRate)

(16)   \begin{equation*}TP\_Rate = \frac{TP}{P_C}; FP\_Rate = \frac{FP}{N_C}\end{equation*}

ROC曲线的空间是一个二维平面,横坐标为假阳性率,纵坐标为真阳性率。

对于硬标签分类器(hard-type classifier),输出是类别标签,其效率可以用一个坐标点(FPR, TPR)画在ROC空间上。我们知道完美分类是A(0,1),也就是说越靠近A,分类器的效果越好,而灰色部分则是表示分类器没有随机分类好。

一个软标签分类器(soft-type classifier),输出是类别属于“正类”的概率,这种情况下,我们可以画出一条ROC曲线,在这种情况下,我们可以用曲线下方的面积来衡量分类器的效果。

PR曲线

研究发现ROC曲线有些时候会把模型的结果看的过于乐观,而PR曲线(Precession-Recall Curve)则是为了弥补这一缺憾的。

曲线和ROC曲线的唯一区别在于,ROC曲线使用(FPR, TPR)刻画分类器的效果,而PR曲线则用(Precesion, Recall)来刻画分类器效果。

比较两个曲线的公式,我们会发现FP_Rate在N_C非常大的时候,无法捕捉到FP的数量变化。

代价曲线

代价曲线(Cost Curve)尝试解释的问题是“一个分类器在处理先验概率不同样本表现如何?”。在ROC曲线中的每一个点都对应了代价曲线里面的一条线。

在ROC曲线中的坐标(FP, TP),都可以计算出期望的代价

(17)   \begin{equation*}E(C) = (1-TP-FT)\times PCF(+)+FP\end{equation*}

其中E(C)是期望代价,PCF(+)是样本为正的先验概率。

我们可以将手中若干可用的分类器的代价直线下方区域求交,获得的面积就是代价曲线,该曲线的含义是在“已知先验概率的条件下选择分类器,能够达到的最小期望代价是多少?”

多分类问题的拓展指标

上述的很多指标都可以拓展到多标签分类问题中,包括多标签ROC,M-Measures,Misclassification Cost……

未来我们该怎么做?

了解不均衡分类算法的本质

现在的很多研究都是偏技术的,为某个问题设计了一个巧妙地算法,能够优化某一个评价指标。但是这些算法究竟如何优化了模型表现,并没有人能够说清楚。

  1. 与从原始分布学习相比,什么样的假设会使不平衡学习算法更好地工作?
  2. 应该在多大程度上平衡原始数据集?
  3. 不平衡的数据分布如何影响学习算法的计算复杂度?
  4. 在数据分布不平衡的情况下,普遍的误差范围是多少?
  5. 对于特定的算法和应用领域,是否有一种通用的理论方法可以减轻学习不平衡数据集的障碍?

需要一个标准化的评价体系

上面讲的那些基于曲线的评价指标非常重要,需要行业能够有意识的将其纳入评价指标,这样才能有助于模型的迭代比较。

增量数据上的不均衡学习

在网络监控,流媒体,网络挖掘领域,数据往往是增量到达的,在增量学习如果存在不平衡该怎么办,有以下几个问题需要思考:

  1. 如果在学习期间的中间引入不平衡,我们如何自主调整学习算法?
  2. 我们是否应该考虑在增量学习期间重新平衡数据集?如果是这样,我们怎么能做到这一点呢?
  3. 我们如何积累经验并利用这些知识自适应地改进从新数据中的学习?
  4. 当新引入的概念也不平衡时(即概念漂移的不平衡问题),我们如何处理这种情况?

半监督学习与不均衡数据集

半监督学习中,同时存在带标注和不带标注的数据,这个时候,如果存在不平衡又改如何处理,思考如下问题:

  1. 如何识别未标记的数据示例是来自平衡的还是不平衡的底层分布?
  2. 给定一个带有标签的不平衡训练数据,有哪些有效的方法来恢复未标记的数据示例?
  3. 在给定不平衡标记数据的恢复过程中(通过传统的半监督学习技术),可能会引入什么样的偏差?

参考资料

原始论文:He, H., & Garcia, E. A. (2009). Learning from imbalanced data. IEEE Transactions on knowledge and data engineering21(9), 1263-1284.

机器学习模型性能评估二:代价曲线与性能评估方法总结:https://zhuanlan.zhihu.com/p/53781144

机器学习基础(1)- ROC曲线理解:https://www.jianshu.com/p/2ca96fce7e81

adaboost.M1与adaboost.M2差别比较:https://blog.csdn.net/tyh70537/article/details/76675098

浅析文本摘要算法(Document Summarization)

概述

文本摘要算法,指的是在一篇文章中,摘要出核心观点的算法。主流的文本摘要算法生成一篇文章的摘要,摘要长度在3~4句话左右。

历史

在深度学习算法出现之前,人们使用了贪心算法、图算法来研究文本摘要。同时,为了衡量一段生成的摘要是否和标准摘要(gold summary)相似,学术界提出了一系列标准,这些标准现在广泛用于文本摘要算法的模型评价,其中最为常用的就是ROUGE – A Package for Automatic Evaluation of Summarieszz中提到的ROUGE-x系列算法。

深度学习提出后,LSTM/GRU作为摘要生成的强有力工具,一举打破传统算法的效果。最为主流的摘要生成模型是基于抽取式和生成式的,这两种模型将在后面详述。

随着深度学习的发展,很多其他算法也被引入。如一些文章使用强化学习,直接尝试训练一个能够获得最高ROUGE得分的模型。一些文章借助机器视觉方向的研究,优化模型结构。也有文章训练模型,判断句子相对于文章的重要性,进而间接实现摘要提取。

抽取式和生成式文本摘要

既然是摘要,那么显然,摘要中很大一部分都应该是原文中出现过的词语。同时,基于语法的考虑,也需要引入一些没有在原文中出现的词。

这时,就引出了文本摘要算法的两大学派—— 抽取式(extractive)和生成式(abstractive)。

  • extractive算法希望直接从文本中,抽出若干词语,连成一句话。词汇的抽取通常使用循环神经网络,配合注意力机制。得到“下一个词”可能是谁的概率分布。
  • abstractive算法希望从词汇表中,直接选出“下一个词”。

不论是abstractive的文本摘要,还是extractive的文本摘要,模型都由两个部分构成的,即一个编码器(encoder)和一个解码器(decoder)。

  • 对于编码器来说,通常都是将输入文本导入一个循环神经网络,生成出一个上下文特征向量c
  • 对于解码器来说,通常也是使用一个循环神经网络。以编码器生成的表征原文的上下文特征向量c,和之前生成的词汇{y_1, y_2, \dots, y_t},生成出摘要的下一个词y_t

数据集

当前研究人员多使用CNN/DailyMail作为数据集,在该数据集中,每一组数据是一个新闻稿,平均每篇文章39句话。同时还有一个“多句”的摘要。

著名论文

Get To The Point: Summarization with Pointer-Generator Networks

这篇文章提出了一个Pointer-Generator模型,既可以通过Pointer拷贝原文的文字,也可以通过Generator生成不存在原文中的文本。这两个模型通过一个开关p_{gen}进行选择——

P(w) = p_{gen} P_{vocab}(w) + (1-p_{gen})\sum_{i:w_i=w} a_i^t

其中P_{vocab}表示从词汇表中选择一个单词的概率分布,而a_i则是从原文选择第i个词汇的概率分布。

在此基础上,本文还提出了一种称之为覆盖率机制(coverage mechanism)的方式,用以解决抽取式摘要中最容易出现的内容重复的问题。

SummaRuNNer: A Recurrent Neural Network based Sequence Model for Extractive Summarization of Documents

这篇文章核心目标是仅仅是在“句子级别”进行摘要,即从原文中选择若干适合作为摘要的句子。该文章使用两层GRU,依次在“词语”级别和“句子”级别总结信息,最终获得一个可以表征全局性质的向量d。接着,再参考句子级别的特征向量s_i、全局特征向量d、以及RNN的隐状态h_i,生成对于句子的评分。

Ranking Sentences for Extractive Summarization with Reinforcement Learning

这篇文章的核心目标是给一篇文章的句子按照与主题的相关度进行排序,文章指出,在之前的方法中,通常是训练模型,使得对于每一个句子的估价尽量靠近一个指定的ground-true。但提升对于ground-true的近似并不一定能够提高模型的ROUGE评分。因此,文章提出使用强化学习的方式,直接学习句子的label,进一步最大化ROUGE评分(注意,这里ROUGE评价指标是不可导的,因此才需要用到强化学习)。

Neural Document Summarization by Jointly Learning to Score and Select Sentences

这篇文章仍然是句子级别摘要的算法,其思想借鉴了MMR算法,在MMR算法中,借助一个建立在语句集合中的评分函数r(S),迭代选择能够最大化加入后r(S')值的句子。即

g(S_i) = r(S_{t-1} \cap {S_i}) - r(S_{t-1})

g(S_i)可以看做在选择了S_{t-1}后,第i篇文章S_i的评分。使用神经网络结构去学习g(S_i)即可实现——能够参考之前选取句子集合信息的语句选择算法。

BanditSum: Extractive Summarization as a Contextual Bandit

这篇文章也是借助强化学习尝试拟合文本的ROUGE得分,并且提出了新的结构用于防止摘要倾向于前面的句子。

Bottom-Up Abstractive Summarization

这篇文章与Pointer-Generator相似,不过为了解决前文中文本拷贝倾向于拷贝整句话的bug。在输入给Pointer-Generator模型之前,先给输入的文本加了一个mask,过滤掉其中一部分,这样就导致文本不再倾向于拷贝连续的内容。

DeepChannel: Salience Estimation by Contrastive Learning for Extractive Document Summarization

这篇文章训练模型,拟合P(D|S),即给定摘要S,能够恢复原文D的概率。而函数P(D|S)的训练,可以借助文章D,摘要S,一句不重要的话S_2这三部分进行训练。生成P(D|S)后,再使用贪心算法构造摘要集合。

一句话解析最大边缘相关性算法(MMR, Maximal Marginal Relevance)

随着网络资源的丰富,找到和询问(query)最相关的一系列文本成为了学者们研究的问题。

之前的做法通常是直接计算逐个候选文本与询问的相关度。将前K大值对应的文档作为“最相关文档”输出出来。但是这种做法适用于那些候选文本集合较小,且只有少量文本与询问存在关联的情况。

但实际上,我们还有另一种场景,以搜索引擎为首的这类环境中,潜在的相关文档非常多,我们需要非常高的召回率(recall),并且尽量降低结果的冗余性(redundance)。在这种情况下,MMR就有用武之地了。

实际上MMR的算法核心思想可以用一句话解释——

A document has high mariginal relevance if it is both relevant to the query and contains minimal similarity to previously selected documents.

一个文章拥有高边缘相关性(MMR)当且仅当它与询问相关性高,而且与之前已经选出来的文章集合相关性低。

而使用公式化的表达如下——

MMR \overset{def}{=}  \underset{D_i \in R \backslash S}{Arg max} \left[ \lambda (Sim_1(D_i, Q) - (1-\lambda) \underset{D_j \in S}{max} Sim(D_i, D_j) \right]

其中,Q表示询问,D_i表示文档,S表示选择出来的相关文档集合,Sim表示任意一种文档相关性计算函数。

以上就是MMR的解释,MMR在文档摘要方面有很多应用。想要更细了解,可以参考文献 The Use of MMR, Diversity-Based Reranking for Reordering Documents and Producing Summaries

Learning Convolutional Neural Networks for Graphs

图卷积网络(Graph Convolutional Network),顾名思义,就是把图像处理中的卷积层运用到图上,图卷积网络能够处理如下两类问题[1]——

  • 给定一系列图作为训练集,可以训练出一个函数,该函数能够对未知的图进行分类或回归。
  • 给一张很大的图,学习图的表示函数(representation),并对于未知的图,推导出一些性质,诸如判断一个节点的类型,或是消失的边权等等。

回顾卷积神经网络,一个像素的特征值,来自于该层输入中,这个像素空间上临近点的像素特征。卷积神经网络的成功,从某种意义上来说,正式借助了这种隐含的空间特征。对于NLP也是同理

但是,对于大部分图而言,并没有这么好的特征可以利用,要将CNN迁移到图上面,需要解决这两个问题——

  • 找到一部分中间点,这些中间点将各自总结其邻域节点的特征。
  • 计算每个中间点临近图的正则化表示,即向量空间中的一个可以编码这个图的表示

定义术语

首先,需要定义图的节点的标号(labeling)和排名(ranking)。标号是一个给图上每个节点赋予一个权值的映射l(u)。而排序是将图上每一个节点权值从小到大排名后的排名映射r(u)。即满足对于任意u, v \in Vr(u)<r(v)当且仅当l(u)>l(v)

倘若r(u)函数和l(u)函数都是单射的,那么使用r(u)对于图中的节点编号进行置换,可以得到A^l(G)

上述定义其实是有道理的,假设l(u)是一个能够描述节点位置的函数,那么使用r(u)映射后的图G'可以用来当做一个图的标准化(Canonicalization)结构,这个结构能够用来比较两个图是否同构(Isomorphism)。

l(u)的最优化是NP的,但是可以构造出相对有效的l(u)——用距离“中心节点”的距离函数作为l(u),这里的“中心节点”是Node Sequence Selection函数的结果。

算法流程

Node Sequence Selection

为了对图进行卷积操作,我们需要定义卷积的stride和width。实际的算法非常简单,既然我们假设了r(u)函数能够有效刻画节点空间位置,那么在按照r(u)排序后的节点序列中,使用一个width大小stride步长的滑动窗口就可以完成节点的选择了。

Neighborhood Assembly

这一个步骤,试图对于上一步得到的若干个节点,分别找到一个大小为k的领域,这里用了简单的广度优先搜索算法。

Graph Normalization

图的规范化操作使用上一步得到的中心节点及其领域,重新对于领域中的节点进行标号,进而通过标号的排名进行置换,此时的图就相对规范了。由于距离不是单射函数,所以文中引用了NAUTY的方法,对于同样距离的节点进行区分。

Convolutional Architecture

文中的模型能够同时处理点权和边权,仅需要改变CNN的stride参数即可,具体实现略

评价

  • 没有公开代码,可复现性存疑
  • 适合作为GCN的入门论文,但和现在主流的GCN不一样。

引用

  1. Niepert M, Ahmed M, Kutzkov K. Learning convolutional neural networks for graphs[C]//International conference on machine learning. 2016: 2014-2023.

FaceNet: A Unified Embedding for Face Recognition and Clustering 阅读笔记

简介

该论文试图去解决人脸识别的课题,人脸识别有三个研究方向,分别为

  1. 验证(verification),用于判断两个图像是否为同一个人
  2. 识别(recognition),用于识别一个图像是哪个人
  3. 聚类(clustering),在一系列图片中,找到一个经常出现的人

通常的人脸识别算法流程是这样的——

先训练一个可以用于在训练集中分类的网络,然后将该网络的中间某一层输出(一般而言是一个作为瓶颈的向量)作为测试集的人脸特征向量。

与之相反,论文提出的模型,以直接生产特征向量为目标,也就是说,特征向量不再作为一个中间信息,而是一个模型实实在在优化的目标。论文中的这种损失函数称为Triplet Loss。

模型

我们希望构造函数f(x),将图片x映射到特征空间\mathbb{R}^d,使得所有相同身份的人脸拥有较小的欧几里得距离,反之不同人脸的距离较大。在Triplet Loss的构造中,为了满足尺度的恒定,还额外规定f(x)位于单位球体上,即|f(x)| = 1

模型希望相同人脸特征距离近,不同人脸特征距离远,量化到数学公式上就是

|f(x_i^a)-f(x_i^p)|^2 + \alpha < |f(x_i^a)-f(x_i^n)|^2

其中x_i^a为基准图片(anchor),x_i^p为同一身份的不同图片(positive),x_i^n为不同身份的不同图片(negative). 而\alpha被称为TripletLoss的边缘距离(margin)

由于算力的原因,不能计算出所有可能的x_i^ax_i^px_i^n组合,即所有Triplet。因此,选择有代表性的Triplet是非常有必要的。一种非常暴力的做法是,找到上述不等式中前半部分的最大值以及后半部分的最小值,即argmax|f(x_i^a)-f(x_i^p)|^2argmin|f(x_i^a)-f(x_i^n)|^2,他们的组合一定是优化的瓶颈部分。我们将他们作为Hard Triplet,单纯优化他们就可以较快收敛。

由于图片画质以及误标记等原因,全局的argmax和argmin表现并不好,不过将其改成mini-batch内部的argmax与argmin就好了。

Identity-Aware Convolutional Neural Network for Facial Expression Recognition 阅读笔记

这篇论文核心目标是提高人脸表情识别的精度。经典的表情识别算法,会将表情图片映射到特征空间(feature space)中的特征向量,而两个特征向量的欧几里得距离来衡量两个表情的相似度。

作者发现常规模型容易将“同一个人(indentity)”的特征向量放在一起而非“同一个表情(expression)”。这个问题表现在模型训练的时候,模型容易“偷偷”记录下训练数据中人物的面貌,并基于此进行判断。倘若随便换一个测试集,模型的准确度就有非常大的下降。(比如模型会记录下某黑人胖子A的吃惊的表情特征,但是之后测试集中,倘若是一个黑人瘦子B吃惊的表情,那么模型就不怎么容易判别出来了)

如下图,现有的模型的特征向量如图(a)所示依赖于人物,而作者的模型能挖掘和人物无关的表情特征,反映到特征空间中如图(b)所示。

文章提出的模型称为identity-aware convolutional neural network (IACNN) ,其核心思想是学习与表情有关(expression-related)的特征,并在同时,故意学习一个和人物有关(identity-related)的特征,后者虽然不利于网络的实际识别,但是却有利于让前者变得与身份无关(identity-invariant).

同时,该文章提出了一种距离的计算法则,能够让相似的表情的特征向量相距较近,而不相似的表情的特征向量相距较远。(不过这个计算法则感觉并不算亮点或是创新)

首先定义欧几里得距离作为接下来的距离公式——

D(f^E(I_1), f^E(I_2)) = |f^E(I_1), f^E(I_2)|^2

下面是一个自定义的损失函数公式——

L^{exp}_{Contrastive} = \frac{z_i^E}{2} * D(f^E(I_{i, 1}), f^E(I_{i,2})) + \frac{1-z_i^E}{2} * max(0, \alpha^E - D(f^E(I_{i, 1}), f^E(I_{i,2})))

这个公式看着很长,实际上非常简单,当两个图片属于同一个表情(exp),那么z_i=1 ,优化损失函数倾向于让他们的特征向量靠近;而倘若不属于同一个表情,z_i=0,优化损失函数倾向于让他们至少有\alpha^E的距离。这个损失函数可以用于训练提取表情特征的网络f^E(x)。顺便一提f^E是一个基于CNN的网络。

与上面相似,我们也可以创造一个L^{ID}_{Contrastive}专门用来训练提取身份特征的网络F^{ID}

L^{ID}_{Contrastive} = \frac{z_i^E}{2} * D(f^{ID}(I_{i, 1}), f^{ID}(I_{i,2})) + \frac{1-z_i^{ID}}{2} * max(0, \alpha^{ID} - D(f^{ID}(I_{i, 1}), f^{ID}(I_{i,2})))

通过上述的网络f^{ID}f^E,我们对于一个图片能够生成表情相关的特征FC_{exp}和身份相关特征FC_{ID},令他们的组合特征为FC_{feat}.

使用FC_{feat}进行预测,得到损失函数L^1_{softmax}L^2_{softmax}(1和2分别是两张图片),使用FC_{exp}进行预测,得到L^{exp1}_{softmax}L^{exp2}_{softmax}

最终损失函数如下

L = \lambda_1 L^{ID}_{Contrastive} + \lambda_2 L^{Exp}_{Contrastive} + \lambda_3 L^1_{softmax}+ \lambda_4 L^2_{softmax}+ \lambda_5 L^{exp1}_{softmax}+ \lambda_6 L^{exp2}_{softmax}

可以发现,优化损失函数L,身份特征相关的信息倾向于聚集在FC_{ID}中,从而使FC_{Exp}的信息是纯粹的面部无关信息。那么最后测试集上,单纯使用FC_{Exp}进行预测,就不会存在模型对于训练集人物过于依赖的问题了。

An Introduction To Compressive Sampling 阅读笔记

通常我们讲的采样都要求采样率至少两倍于带宽,这是香农在1948年就提出了的。而本文讲的则恰恰相反,本文试图介绍如何使用压缩感知(Compressive Sampling/Sencing)的方式,使用尽量少的样本,刻画出信号本身。

从实用性角度来看,尽管本文的所有算法都可以拓展至连续信号,但是本文将单纯讲述离散信号在欠采样时的CS,毕竟这才是对工业界最有意义的。因为在离散前采样的信号中,有一个很重要的问题——

压缩感知的原理

假设有一个离散信号f \in R^n,是否有可能构造出m \ll n个波形,能够“几乎”完整刻画原来f所携带的信息?

首先向讲一讲关于稀疏性(Sparsity)的问题,令f =  \Psi x,其中\Psi是一个n\times n的矩阵。我们可以理解为将f使用特征x进行表征,而倘若我们提取x中前S大的值,而将其他位置强行置0(这样便于压缩,且不会显著对于结果产生影响),则称呼得到的向量x_S为S稀疏向量(S-sparse). 此时,我们可以通过x_S计算出f_S  = \Psi x_S

那么,接下来,m的取指大概为多少可以保证信号能够被“几乎”完整恢复呢?论文通过一系列推导,给出了一个式子

m \geq C \cdot \mu^2(\Phi, \Psi) \cdot S \cdot log n

其中\mu函数表征了感知基\Phi和表征基\Psi的相关程度,S是指x是S-sparse向量,C是某个常数。

而上述公式带入实际的图像压缩中,每一个缺失项倘若对应至少四个不连续的采样点,就能准确恢复原来的图像。

若干难题

文中提出并解决了基于上述算法的两个问题——

  1. 对于极其欠采样的样本,是否可以恢复如此高的分辨率?
  2. 实际的检测设备都存在噪音,噪音将如何影响该算法?

为了解决上述两个问题,作者提出了一个叫做restricted isometry property(RIP)的限制条件,倘若条件满足,不仅欠采样样本可以被完整恢复,而且还可以将误差限制在一个较小的区间中。而RIP的细节这里不叙述。

感知基的选择

感知基选择非常随便,只要满足RIP准则就可以。而文中提到了在单位球体上面随机取点,或者使用标准正交基与一个随机矩阵的乘积生成。

应用

  1. 数据压缩
  2. 信道编码
  3. 数据获取

等等

参考文献

  • E. J. Candès and M. B. Wakin, An introduction to compressive sampling, IEEE Signal Processing Magazine, 21-30, March 2008.

Structural Deep Embedding for Hyper-Networks 阅读笔记

所谓的Network Embedding就是指,对于一个网络(或者简单地说,图),给每个节点一个特征向量X_i,而该特征向量能够表征网络中节点的结构信息。这篇文章是Network-Embedding中的一篇较为重要的文章。


Abstract

网络嵌入(Network Embedding)近年来吸引了很多人的注意,传统的方法多局限于由点与点二元组关系形成的图,但是,在实际生活中,图本身很难是标准的二元组关系,在有些情况下,一条关系(relationship)会涉及到三个甚至更多的主体,我们可以称之为超边(hyperedge)。当超边成为一个不可分割的独立整体,则传统算法会遇到不少困难。本文将介绍一种算法,用于对于超网络(hyper-network)的嵌入。并且证明,传统算法不可能成功Embedding存在不可分割超边的网络。

Introduction

对于hyper-network的embedding,一个非常简单的方式是将其转化为普通图,这里有两种常用做法,一种是直接将图中的超边转化为一个“团(clique)”,另一种是为超边本身分配一个虚拟节点,并向其包含的所有元素连边。他们分别被称作clique expansion和star expansion。在这些算法中,我们都假设了超边是可分的,即,一个超边包含的点集的子集仍然是有意义的,这在实际生活中是不存在的。上述的算法的诸多问题便是这篇文章需要解决的——

  • 节点的不可分解性:如电影的推荐中的<user, moive, tag>三元组的子集 <user,tag>是不合法的。
  • 结构保留特性:实现局部细节的embed是相对简单的,但是网络整体结构的embed却相对复杂。而我们还需要解决同时embed局部、全局的特征。

对于第一个问题,文章设计了不可分解的多元组相似性函数,这种函数本身的结构保证了超边的子集不会存在。我们从理论上证明该函数是非线性性的,如果使用带非线性层的神经网络实现,则可以实现强力的非线性性。

对于第二个问题,我们使用自编码器来保证相似的节点拥有相似的embedding。

Related Work

早期的图Embedding使用了线性代数的方式,使用图的主特征向量来作为图的编码。由于线性代数中的特征向量分解是一个相对昂贵的方式,因此实际上这种做法并不常用

近年来,一个叫做RamdomWalk的算法提出新的思路,通过刻画一系列随机游走的路径来Embed一个图。在此之后,很多学者都在其基础上进行了创新,诸如使用更好的刻画函数,或者引入深度学习来优化。

然而,上述所有的算法,假设了图是标准的由边的二元组构成的。在存在超边的途中,现有的算法不是无法保证超边的不可分解性,就是过于低效。

Notations and Definitions

术语

如右图所示,相比于图论中的“无向图”,我们的超图更类似于

一个“有向图”。也可类比于之前提到的<user,movie,tag>三元组,节点本身是有类别的。我们定义点集

V = \{V_t\}_{t=1}^{T}

表示所有节点可以按照类别分为T类。

超边边集则可以表示为

E=\{(v_1,v_2,\dots,v_{n_i})\} (n_i \geq 2)

最终第j类的第i个节点的Embedding可以计算为

X_i^j

对于N个节点,我们可以定义相似性函数

\mathcal{S}(X_1,X_2,\dots,X_n)

相似性

节点的一阶相似性(First-order Proximity)刻画了N个节点的直接相似性,其定义非常简单,只要这N个节点组成一个超边,则这N个节点的一阶相似性是1。当然,这里就隐含定义了这N个节点的任意子集都不存在一阶相似性。

显然,单纯的一阶相似性定义是不完善的,这时,我们可以进一步定义二阶相似性。

二阶相似性定义在任意两个节点上,当两个节点x_ix_j共有邻居时,他们应该是二阶相似的。这也应该反映到节点的Embedding上面。举一个例子,在上面那张图上,A_1的邻居应该是\{(L_2,U_1),(L_1,U_2)\},而由于A_1A_2拥有共同的邻居(L_1,U_2)则他们应该是二阶相似的。

Deep Hyper-Network Embedding

模型设计

我们计算的网络Embedding需要保证一阶相似性,即对于模型生成的Embedding值X_i,倘若一个点集组成了超边,则他们的X_i的一阶相似性函数应该尽可能大,反之尽可能小——

特征1:我们令X_i为模型生成的Embedding值,则

  • (v_1, v_2, \dots , v_n) \in E, \mathcal(S)(X_1, X_2, \dots, X_n)应该尽可能大(或者说至少得大于某个比较大的阈值)
  • (v_1, v_2, \dots , v_n) \notin E, \mathcal(S)(X_1, X_2, \dots, X_n)应该尽可能小(或者说至少得小于某个比较小的阈值)

有了上述定义,文章进一步通过列举反例,证明了倘若\mathcal(S)仅仅是依赖于X_1,X_2,\dots, X_n的一个线性函数\mathcal(S) = \sum_i W_i X_i,是无法正确刻画特征1的。当然,了解过深度学习的读者应该就能发现,这恰好是深度学习中的非线性层引入的动机。

后续讨论我们默认N=3,更大的N对应算法很容易在N=3的情况修改得到。下图是网络的结构图——

在输入节点Embeding (X_i, X_j, X_k),我们可以通过非线性函数将他们映射到一个非线性空间L中。

L_{ijk} = \sigma(W_a^{(2)} X_i^a + W_b^{(2)} X_j^b + W_c^{(2)} X_k^c + b^{(2)})

而我们进一步将L映射到一个概率空间S

S_{ijk} = \mathcal{S} (X_i^a, X_j^b, X_k^c) =  \sigma(W^{(3)} * L_{ijk} + b^{(3)})

上面两层共同构成了我们的非线性相似性函数\mathcal{S},最终的目标函数定义如下

\mathcal{L}_1 = -(R_{ijk} \log S_{ijk} + (1-R_{ijk}) \log (1-S_{ijk}))

上式中的R_{ijk}被定义为“节点i,j,k是否组成一个超边”的0\1值函数。

接下来,我们考虑如何生成二阶相似性。之前我们介绍了模型中的第二层和第三层,而模型的第一层就是用来保证二阶相似性的。从图中,我们可以发现,模型使用了一个AutoEncoder,那么任何AutoEncoder都需要一个可供编码的东西,我们这里使用AutoEncoder编码什么呢?作者设计了一个编码矩阵A_i.

H表示在图G(V,E)的关联矩阵,h(v,e)=1当且仅当v \in e,而D表示图的度数矩阵。令A = H H^T -D。在离散数学中,可以证明,A矩阵的第i行A_i刻画了节点i的邻居的信息。而AutoEncoder就可以如下构造——

X_i = \sigma(W^{(1)} * A_i + b_i)

\hat{A}_i = \sigma(\hat{W}^{(1)} * X_i + b_i)

对于AutoEncoder的损失函数,我们有一个小优化,即只计算A_i不等于0的项。

\mathcal{L}_2 = \sum_t ||sign(A_i^t) \cdot (A_i^t-\hat{A}_i) ||_F^2

最终模型的损失为

\mathcal{L} = \mathcal{L}_1 + \alpha \mathcal{L}_2

模型训练

使用SGD算法训练。

Experiment

Conclusion

 

Efficient Large-scale Approximate Nearest Neighbor Search on the GPU 阅读笔记 – 实现与分析

由于篇幅太长,这篇文章的Introduction和Related Work在另一篇文章里。


PQT的简介

乘积量化树(Product Quantization Tree)是基于多层倒排表(Inverted Multi-Index)和分层PQ算法形成的。其核心思想将之前的一个码书(Codebook)修改为基于层次化的树形结构。树形结构可以加速实时的查询,以及离线的排序。相比于之前的多层倒排表,PQT拥有更多地簇(Bins)。最后PQT还巧妙地运用一些技巧在重排序中服用之前计算过的距离值。

右图阐述了一个PQT查询的例子。查询向量[x]_1[x]_2的各个部分一次经过4个Cluster的粗排序和5个Cluster的精排序。对于第一层而言,只有w个最佳的Cluster可以到下一层继续搜索,如图中阴影部分所示(w=2)。

PQT的结构

将样本集合中所有的向量x \in \mathcal{X}归类为簇B_l从而形成若干个互不相交的子集,\mathcal{X} = \bigcup_{k=1}^{K} B_k。接下来,我们将详述如何将一个向量映射到簇中,即如何构造映射m : \mathcal{X} \rightarrow \mathcal{I}_1 \times \mathcal{I}_2 \times \dots \times \mathcal{I}_P

索引树包含两层量化器,第一层是传统的P部分(P part)的PQ量化器,在这个量化器中,每一部分的码表含有k_1个码字。在第一层量化器之后,选出的簇进一步使用第二层k_2个码字的量化器量化。这种方法中,总共存在的簇有K = (k_1 \cdot k_2)^P个。

对于码书的训练,每一部分独立生成码书,首先量化器使用Lloyd Iteration中的Linde-Buzo-Gray算法生成,所有第一层量化器分出的簇进一步使用第二层量化。

对比在多层倒排表中,使用了两级的乘积量化,其中第二级用于排序,我们也用两级索引,至于为什么是两级,只是从经验上来看,两级能够最好得平衡簇的总个数。

PQT的询问操作

一个实际的询问操作包含四个步骤——

  • tree traversal
  • bin proposal
  • vector proposal
  • re-ranking

在tree-traversal步骤中,正如之前对PQT结构的叙述,每一个向量都能归类为一个level-2的簇中。通过剪枝的策略,tree-traversal步骤使用的向量比较次数实际上是相对较少的。在比较了所有k_1个level-1簇后,询问向量距离每一个簇的距离被排序,并且只有最近的w个簇被进一步计算。在提取出了最近的w个level-1簇,接下来这些level-1簇所对应的level-2簇的中心再和询问向量进行比较。在标准参数下,在四百万簇的数据集下,只需要80次向量比较。具体细节可参见论文。

在bin-proposal步骤中,从我们获取的“最好的”簇i=(i_{1,1},i_{2,1},\dots,i_{P,1})开始,我们仍然需要一系列临近的簇,以保证在后续的处理中,有足够多的向量可供选择。正如右图所示,我们需要找到一个顺序,合理组织“次好”的向量,使得遍历完所有较近向量的这组合。着这种便利,通常来说,可以看做是一个斜线从左下向右上方移动维护的下方区域。具体的实现方式,绿线是Dijkstra-based traverse,但是无法再GPU上面实现,而红色、绿色线则是可行的。对于每一个簇,我们都可以在离线阶段预处理出最近的簇。

使用Line Quantization进行重排序

通过上述的索引,每一个询问向量都被归类于最近的簇,并获得了一个量化损失(quantization loss)。在传统方法中,我们就需要依次对于簇所包含的所有向量进行比较,但是显然这样会有巨大的花销。而在我们的算法中,我们重用了一些信息以达到更优的效率。

离线预处理

在传统方法中,一个簇所包含的所有向量是不可分的,这就导致了我们必须花巨大的计算力去依次比较所有的向量。 文中提出的Line Quantization巧妙地解决了向量不可分的问题。即,虽然每一个向量【黑点】相对于level-2簇中心【红点】是不可区分。但是他却可以被投影到两个最近level-1簇中心的连线上【紫点】。巧妙的是,对于所有level-1中心,询问的x_1点与他们的距离都是已经算过的!

右图描述了如何计算对于任意询问向量y距离某一个数据库样本x的距离。其中,c_i,c_j为两个距离x很近的level-1簇中心。

 

(1)   \begin{align*} d(y,x) &= \sum_{p=1}^{P} d([y]_p, [x]_p)^2 \\ & \apporx \sum_{p=1}^{P} h_p(y,x)^2 \\ & \apporx \sum_{p=1}^{P} (b_p^2 + \lambda_p^2 \cdot c_p^2 + \lambda_p \cdot (a_p^2-b_p^2-c_p^2)) \end{align*}

通过这个式子,我们可以用我们之前计算过的,询问向量距离level-1簇中心的距离信息,为x找到一个更加精确的距离估计值。

在GPU上实现

这个模型非常适合在GPU上面实现,不过由于我并不太了解GPU的实现,顾就不在这里赘述,读者可以对照论文自行理解。

The Design Philosophy of the DARPA Internet Protocols 论文阅读报告

本文介绍了Internet中最基本的协议——TCP/IP协议的设计思想。由David.D Clack所著,他作为整个TCP/IP协议设计的参与者,见证了协议从1973年最初的版本,逐渐被改进,到最终成型的一系列尝试。在文章中,作者总结了设计中的一系列目标,以及存在的问题。让我们得以窥见这一段艰辛的摸索之路。

各种协议的设计,其基本目标无非两个: 1) 能够尽可能的兼容协议发布之前已存在的硬件设施; 2)能够尽可能的有利于协议发布之后的因特网发展。这些基本目标不仅为我们理解TCP/IP的后续发展有帮助,也能够让我们知道,为什么在计算机科学领域,很多的实现都是建立在“协议”上的。

在基本目标之上,人们基于对于因特网的畅想,设计出了一系列有严格层次关系的次级目标,如稳定性,经济性,可解释性等。由于Internet协议的设计流程过于复杂,常常会遇到两种不同实现方式的权衡取舍,由于实现确立了稳定性、经济性这一类不同目标的重要性排序,故可以基于此进行取舍。这种目标导向的协议构建,一方面确实省去了非常多的试错的时间,另一方面,却会缺少一些长远的考虑(例如由于对性能的要求并没有卸载目标中,导致性能在早期完全没有被重视等等,又例如一对多的信息传递没有在早期协议中支持,导致在长时间无法实现)。

互联网协议的稳定性作为最重要的目标,毫无疑问来自于互联网历史上的军方背景。也在之后的普及中发现其局限性,报文协议(UDP)的诞生或多或少的解决了这个尴尬的境地。不过UDP能够成功诞生还是算非常幸运的了,通常来说协议的修改总是耗时耗力,有时还会和原来的协议冲突,诸如一对多的广播就一直没有能够成功的引入。总之,协议设计者的远见与用心真的是非常的重要。而TCP/IP协议的设计流程,从文中提到的寥寥几句可以推测出,确实不是设计者拍脑袋的结果,而是无数次试验,并用一篇篇论文推动而来的。反观现在良莠不齐的学术论文,我觉得在协议设计中的这种,基于某个具体目标驱动的研究,才是能让学术界向前推进的正确方法。

由于网络的协议的更改需要兼容之前的功能,而论文写作至今又过去了接近30年,TCP/IP协议在30年前存在的缺陷,随着互联网体量的增大,在现在解决更需要花费巨大的人力财力。IPV6协议的创立可能会解决少量表层问题,但是很多结构上的缺陷仍然无从修复。可能这是计算机网络领域的一大难题。期待在未来,能有技术上的爆炸性突破,其力量,能够足以颠覆计算机领域坚守了三十余年的TCP/IP协议。也许量子通信就是这样的潜力吧。