精华内容
下载资源
问答
  • “海内存知己,天涯若比邻”,古人用心理距离辨证了时空距离,机器学习何尝不是,看似毫不相关或者毫无头绪的分类问题,由于采用了合适的数学距离,就将它们在高维度空间分开了,展现在三维空间里,很多神奇的事情令...

    “海内存知己,天涯若比邻”,古人用心理距离辨证了时空距离,机器学习何尝不是,看似毫不相关或者毫无头绪的分类问题,由于采用了合适的数学距离,就将它们在高维度空间分开了,展现在三维空间里,很多神奇的事情令人难以置信。现实中,我们做神经网络分类或者编码时,loss函数往往需要根据‘distance’来设计,这些distance理解起来是比较烧脑的,下面这个笔记整理些常用的距离,系统的分析一下这些距离的前世今生,看看哪些距离美到令人窒息,还有哪些距离令人痛苦的不能自拔?本文整理的主线来自向量的相似性度量-距离计算方法总结这篇博文,在此感谢作者的总结,为我点亮了一盏明灯。

    向量的显式距离

    向量的显式距离是根据对向量中相同索引的变量进行直观的分析、计算得出的。

    汉明距离-Hamming distance:变量差异计数器

    汉明距离是以理查德·卫斯里·汉明的名字命名的。在信息论中,两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数【3】。汉明距离是我(做通信工程师)最早接触的一类数学距离,信道纠错码里对汉明距离有非常深的理解和使用。还是举个百度的例子:1011101 与 1001001 之间的汉明距离是 2。正如我的定义,这就是两个向量相同索引的变量差异计数器,简单直观,但是很多信息量损失掉了,所以汉明距除了在二进制编解码中的应用,其他地方用的不多。

    曼哈顿距离-Manhattan Distance:变量差异累加器

    曼哈顿距离也称为城市街区距离(City Block distance),是变量差异的绝对值累加,比较形象的理解就是曼哈顿要从一个十字路口开车到另外一个十字路口,驾驶距离是两点间的直线距离吗?显然不是,除非你能穿越大楼。实际驾驶距离就是这个“曼哈顿距离”。【1】,这个距离在比汉明距的进步就是对变量的细节在权重上给与的保留,但是放弃了变量的方向(正负关系),在“曼哈顿问题”上有实际的用途,对于多维空间两个维度相同的向量 X ( x 1 , x 2 , . . . x n ) X(x_1,x_2,...x_n) X(x1,x2,...xn) Y ( y 1 , y 2 , . . . y n ) Y(y_1,y_2,...y_n) Y(y1,y2,...yn),定义两个向量在n维空间的曼哈顿距离公式如下:
    D i s t a n c e M a n h = ∑ i = 1 n ∣ x i − y i ∣ Distance_{Manh}={\sum_{i=1}^n|x_i-y_i|} DistanceManh=i=1nxiyi
    显而易见,二进制的世界里,曼哈顿距离=汉明距离,那么就可以说曼哈顿距离是汉明距离在多进制世界中的版本。

    欧氏距离-Euclidean Distance:几何距离的多维思考

    Euclidean翻译成汉语就是“欧几里得”,古希腊数学家,被称为“几何之父”。这个名字被我和18世纪的伟大数学家欧拉(Eular)搞混了,罪过。欧氏距离实际上就是在二维和三维空间上的直线距离进而推广到多维空间的距离定义。这应该是最容易被我们理解和接受的一种距离定义,同时也被机器学习和模式识别等领域广泛采用。
    二维空间的定义:
    D i s t a n c e e u c l i − 2 = ( x 2 − x 1 ) 2 + ( y 2 − y 1 ) 2 Distance_{eucli-2}= \sqrt{(x_2-x_1)^2+(y_2-y_1)^2} Distanceeucli2=(x2x1)2+(y2y1)2
    三维空间的定义:
    D i s t a n c e e u c l i − 3 = ( x 2 − x 1 ) 2 + ( y 2 − y 1 ) 2 + ( z 2 − z 1 ) 2 Distance_{eucli-3}= \sqrt{(x_2-x_1)^2+(y_2-y_1)^2+(z_2-z_1)^2} Distanceeucli3=(x2x1)2+(y2y1)2+(z2z1)2
    对于多维空间两个维度相同的向量 X ( x 1 , x 2 , . . . x n ) X(x_1,x_2,...x_n) X(x1,x2,...xn) Y ( y 1 , y 2 , . . . y n ) Y(y_1,y_2,...y_n) Y(y1,y2,...yn),定义两个向量在n维空间的欧氏距离为:
    D i s t a n c e e u c l i − n = ∑ i = 1 n ( x i − y i ) 2 Distance_{eucli-n}= \sqrt{\sum_{i=1}^n(x_i-y_i)^2} Distanceeuclin=i=1n(xiyi)2
    向量表示法:
    D i s t a n c e e u c l i − n = ( X − Y ) T ( X − Y ) Distance_{eucli-n}= \sqrt{(X-Y)^T(X-Y)} Distanceeuclin=(XY)T(XY)

    闵可夫斯基距离-Minkowski Distance:变量的高阶差异累加

    在曼哈顿距离和欧氏距离的基础上,闵氏距离从二阶推广到n阶,对于多维空间两个维度相同的向量 X ( x 1 , x 2 , . . . x n ) X(x_1,x_2,...x_n) X(x1,x2,...xn) Y ( y 1 , y 2 , . . . y n ) Y(y_1,y_2,...y_n) Y(y1,y2,...yn),定义两个向量在n维空间的闵氏距离为:
    D i s t a n c e M i n k o = k ∑ i = 1 n ∣ x i − y i ∣ k Distance_{Minko}= ^k\sqrt{\sum_{i=1}^n|x_i-y_i|^k} DistanceMinko=ki=1nxiyik
    显然k=1和k=2是之前提到的,而高阶的话无法直观理解其功用。

    切比雪夫距离-Chebyshev Distance:最大的就是最好的

    切比雪夫距离是向量空间中的一种度量,二个向量点之间的距离定义是其各坐标数值差绝对值的最大值。对于多维空间两个维度相同的向量 X ( x 1 , x 2 , . . . x n ) X(x_1,x_2,...x_n) X(x1,x2,...xn) Y ( y 1 , y 2 , . . . y n ) Y(y_1,y_2,...y_n) Y(y1,y2,...yn),定义两个向量在n维空间的切比雪夫距离为:
    D i s t a n c e C h e b y = max ⁡ i ( ∣ x i − y i ∣ ) = lim ⁡ k − > ∞ ( ∑ i = 1 n ∣ x i − y i ∣ k ) 1 / k Distance_{Cheby}= \max_i{(|x_i-y_i|)}=\lim_{k->\infty}(\sum_{i=1}^n|x_i-y_i|^k)^{1/k} DistanceCheby=imax(xiyi)=k>lim(i=1nxiyik)1/k
    极限表达式没太理解。这个距离很多例子来自于国际象棋,或者仓储机器人的使用。

    显式距离的罪与罚

    显式距离只考虑向量相同下标索引到的变量差异,用法相对死板,在博文【1】中提到了两个缺点:

    1. 将各个分量的量纲(scale),也就是“单位”当作相同的看待了。
    2. 没有考虑各个分量的分布(期望,方差等)可能是不同的。

    举一个小栗子,把一个向量循环移位之后的新向量与原向量比较,显式距离可能特别的大,那就说明这两个向量没有关系吗?

    向量的隐式(归一化)距离

    向量之间除了对标变量差异外,还需要考虑不对标的变量之间有什么联系,另外还要考虑量纲,分布的影响,这样normalize(归一化)后的距离统统归到隐式距离,这类问题经常用相似度similarity来取代normalized距离,毕竟二次处理,升华了,因为similarity亦或归一化距离的取值大都(-1,1)或者(0,1),所以可以将两者做简单的互换:
    D i s t a n c e N o r m a l i z e d = 1 − s i m i l a r i t y Distance_{Normalized} = 1 - similarity DistanceNormalized=1similarity

    归一化欧氏距离 -Standardized Euclidean distance

    假设向量X的均值(mean)为m,标准差(standard deviation)为s,那么X的“归一(标准)化变量”表示为:
    X ∗ = X − m s X^*=\frac{X-m}{s} X=sXm

    那么再次假设一组向量集合,每个维度(下标)的向量X是独立(不相关)的,则求归一化后的向量的欧氏距离
    D i s t a n c e S − e u c l i − n = ∑ i = 1 n ( x i ∗ − y i ∗ ) 2 = ∑ i = 1 n ( x i − y i s i ) 2 Distance_{S-eucli-n}= \sqrt{\sum_{i=1}^n(x_i^*-y_i^*)^2}= \sqrt{\sum_{i=1}^n(\frac{x_i-y_i}{s_i})^2} DistanceSeuclin=i=1n(xiyi)2 =i=1n(sixiyi)2
    其实这个公式是对数据集合同下标的变量做了归一化,感觉还是怪怪的,假设条件很重要。将每个维度方差的倒数看成是一个权重,这个公式可以看成是一种加权欧氏距离(WeightedEuclidean distance)。​但多维向量不同维度之间往往是有联系的,所以这种归一化只是为了研究而已。

    马氏距离-Mahalanobis Distance

    上面的归一化欧氏距离实在太牵强,强行把各维度做归一化之后的空间特征肯定有了很大变化。马氏距离可以看作是欧氏距离的一种修正,修正了欧式距离中各个维度尺度不一致且相关的问题,比归一化欧氏距离合理的多,也得到了很多应用。对于多维空间(协方差矩阵为 S S S,均值向量为 μ \mu μ)两个维度相同的向量 X ( x 1 , x 2 , . . . x n ) X(x_1,x_2,...x_n) X(x1,x2,...xn) Y ( y 1 , y 2 , . . . y n ) Y(y_1,y_2,...y_n) Y(y1,y2,...yn),定义单个向量到 μ \mu μ的马氏距离为:
    D i s t a n c e M a h a l = ( X − μ ) T S − 1 ( X − μ ) Distance_{Mahal}= \sqrt{(X-\mu)^TS^{-1}(X-\mu)} DistanceMahal=(Xμ)TS1(Xμ)

    定义两个向量在n维空间的马氏距离为:
    D i s t a n c e M a h a l = ( X − Y ) T S − 1 ( X − Y ) Distance_{Mahal}= \sqrt{(X-Y)^TS^{-1}(X-Y)} DistanceMahal=(XY)TS1(XY)
    可以看出马氏距离较之归一化欧氏距离进步的地方就是用协方差矩阵代替了简单的方差,进而消除了变量之间相关性的干扰。如果各样本之间独立同分布,那么就变成了了标准欧拉距离:
    D i s t a n c e e u c l i − n = ( X − Y ) T ( X − Y ) Distance_{eucli-n}= \sqrt{(X-Y)^T(X-Y)} Distanceeuclin=(XY)T(XY)
    马氏距离更加深入的了解请参考附录的链接。马氏距离一直在scikit工具里作为度量学习的主要判据【8】,有兴趣可以读读来研究。

    皮尔逊相关系数-Pearson’s Correlation coefficient

    皮尔逊相关系数广泛用于度量两个变量之间的相关程度,其值介于-1与1之间,又称皮尔逊积矩相关系数(Pearson product-moment correlation coefficient,简称 PPMCC或PCCs)。两个变量之间的皮尔逊相关系数定义为两个变量之间的协方差和标准差的商:
    ρ X , Y = c o v ( X , Y ) σ X , σ Y \rho_{X,Y}= \frac{cov(X,Y)}{\sigma_X,\sigma_Y} ρX,Y=σX,σYcov(X,Y)
    皮尔逊相关系数有一个重要的数学特性是,因两个变量的位置和尺度的变化并不会引起该系数的改变。

    余弦相似度-Cosine Similarity

    两个向量间的余弦值可以通过使用欧几里得点积公式求出:
    a ⋅ b = ∣ ∣ a ∣ ∣ ⋅ ∣ ∣ b ∣ ∣ c o s θ a \cdot b= ||a|| \cdot ||b|| cos\theta ab=abcosθ
    由此得出余弦夹角相似度
    s i m i l a r i t y c o s = c o s θ = a ⋅ b ∣ ∣ a ∣ ∣ ⋅ ∣ ∣ b ∣ ∣ = ∑ i = 1 n ( x i ∗ y i ) ∑ i = 1 n ( x i ) 2 ∗ ∑ i = 1 n ( y i ) 2 similarity_{cos}= cos\theta =\frac{a \cdot b}{||a|| \cdot ||b||}=\frac{\sum_{i=1}^n(x_i*y_i)}{\sqrt{\sum_{i=1}^n(x_i)^2}*\sqrt{\sum_{i=1}^n(y_i)^2}} similaritycos=cosθ=abab=i=1n(xi)2 i=1n(yi)2 i=1n(xiyi)
    余弦相似性通过测量两个向量的夹角的余弦值来度量它们之间的相似性。0度角的余弦值是1,而其他任何角度的余弦值都不大于1;并且其最小值是-1。这是个非常nice的取值范围,所以最近的很多训练都采用了这个作为度量。

    隐式度量的秘密

    介绍了这么多隐式距离,他们有什么关系呢?翻了翻网站,看到一个惊人的结论:在数据标准化( μ = 0 , σ = 1 \mu=0, \sigma=1 μ=0,σ=1)后,Pearson相关性系数、Cosine相似度、欧式距离的平方可认为是等价的【6】,虽然看着几个公式眼熟,但是说他们等价实在让人难以接受,慢慢研究,慢慢流泪吧。而实际应用中,欧氏距离和余弦相似性还是比较普遍的,虽然等价,但效果还是不一样的。

    其他度量

    熵和距离到底有么有关系

    Entropy熵的概念最早由统计热力学,学过大学物理的童鞋都曾经被这个概念深深的熵害过,信息熵是香农提出来表达随机变量的不确定性度量的一个概念,想想两者都是衡量分布的混乱程度或分散程度的一种度量。分布越分散(或者说分布越平均),(信息)熵就越大。分布越有序(或者说分布越集中),(信息)熵就越小。用历史打个比方,中国的春秋战国、魏晋南北朝和五代十国是(历史)熵最大的时期,因为乱嘛!秦汉唐宋元明清等王朝则是(历史)熵最小的时期,这就好理解了一些吧。对于样本集合X,定义它信息熵的通用表达
    E n t r o p y ( X ) = ∑ x ∈ X − p ( x ) ⋅ l o g ⋅ p ( x ) Entropy(X)= \sum_{x\in X} -p(x)\cdot log\cdot p(x) EntropyX=xXp(x)logp(x)
    对于分类问题的样本集合,如果n是该集合的类别总和,p是在某一类的概率,则可以写成下面的形式
    E n t r o p y ( X ) = ∑ i = 1 n − p i ⋅ l o g 2 ⋅ p i Entropy(X)= \sum_{i=1}^n -p_i\cdot log_2\cdot p_i EntropyX=i=1npilog2pi
    log ( 1/P )来衡量不确定性。P是一件事情发生的概率,概率越大,不确定性越小。可以看到信息熵的公式,其实就是log ( 1/P )的期望,就是不确定性的期望,它代表了一个系统的不确定性,信息熵越大,不确定性越大【7】。信息熵是为了衡量信息本身靠不靠谱的程度,最后怎么就跟神经网络搭上关系,是因为出现了两个衍生概念,交叉熵和KL散度。出现这两个概念是因为现实生活中我们无法获得全部样本,所以的机器学习问题都是以偏概全的瞎猜,最后看谁猜的准,所以定义真是分布概率为p,而经过模型猜测(估计)出来的分布为q,我们在学习(train)的过程就是希望p和q能相等,或者相近,KL散度就是评价这两个抽象分布距离的办法,divergence这个词和distance就联系在一起了。先来看看KL散度的公式:
    D K L ( p ∣ ∣ q ) = ∑ i = 1 n p i ⋅ l o g ⋅ p i q i D_{KL}(p||q)= \sum_{i=1}^n p_i\cdot log\cdot \frac{p_i}{q_i} DKL(pq)=i=1npilogqipi
    D K L D_{KL} DKL的值越小,表示q分布和p分布越接近。将上式log中的分号打开:
    D K L ( p ∣ ∣ q ) = ∑ i = 1 n p i ⋅ l o g 2 ⋅ p i − ∑ i = 1 n p i ⋅ l o g ⋅ q i D_{KL}(p||q)= \sum_{i=1}^n p_i\cdot log_2\cdot p_i-\sum_{i=1}^n p_i\cdot log\cdot {q_i} DKL(pq)=i=1npilog2pii=1npilogqi
    第一项恰巧是信息熵的定义(在确定的训练集合里,这部分是常数),那么第二部分就是交叉熵的定义了:
    C r o s s E n t r o p y ( X ) = ∑ i = 1 n − p i ⋅ l o g 2 ⋅ q i CrossEntropy(X)= \sum_{i=1}^n -p_i\cdot log_2\cdot q_i CrossEntropyX=i=1npilog2qi
    看看
    D K L ( p ∣ ∣ q ) = C r o s s E n t r o p y ( X ) − E n t r o p y ( X ) D_{KL}(p||q)= CrossEntropy(X)-Entropy(X) DKL(pq)=CrossEntropyXEntropyX
    换句话说,交叉熵在集合训练过程中的趋势可以作为散度(Distance-divergence)距离,这个值越小,说明估计的概率越接近集合的真是分布。就这样交叉熵完美的实现了loss函数的功能,以后碰到交叉熵应该不会太难过了,详细的推荐一下透彻理解熵(包括信息熵和交叉熵)这篇博文,有例子和推导。

    杰卡德相似系数-Jaccard similarity coefficient

    两个集合A和B的交集元素在A,B的并集中所占的比例,称为两个集合的杰卡德相似系数,用符号J(A,B)表示。公式列在下面,暂时我还真没接触过哪里用得上。
    J ( A , B ) = A ∩ B A ∪ B J(A,B)=\frac{A\cap B}{A\cup B} J(A,B)=ABAB
    这是衡量两个集合相似程度的指标。目测短期内看不到使用场景,不展开讨论了

    信噪比也是距离-Signal-to-Noise Ratio: A Robust Distance Metric for Deep Metric Learning

    这来自于CVPR论文Signal-to-Noise Ratio: A Robust Distance Metric for Deep Metric Learning,Mark一下后面有机会再看看吧。

    Hausdorff 距离

    豪斯多夫距离:度量空间中真子集之间的距离。Hausdorff距离是另一种可以应用在边缘匹配算法的距离,它能够解决SED方法不能解决遮挡的问题(百度摘抄),Hausdorff distance这篇博文有比较详细的介绍。

    参考

    距离计算方法总结
    Python: Numpy: 两个形状不同的矩阵作计算的广播机制
    汉明距离
    马氏距离(Mahalanobis Distance)介绍与实例
    马氏距离(Mahalanobis Distance)
    如何理解皮尔逊相关系数(Pearson Correlation Coefficient)
    信息熵,交叉熵和相对熵
    What is Metric Learning
    度量学习中的pair-based loss
    Signal-to-Noise Ratio: A Robust Distance Metric for Deep Metric Learning

    展开全文
  • 在做海量高维向量相似度快速计算比赛时,对最近邻搜索方法做了一些泛读和总结。主要以下分为几大类。 一是基于树形的高维索引,如kd-tree,R-tree等,但当维度较高时,查询性能急剧下降。 二是基于map-reduce方法...

        在做海量高维向量相似度快速计算比赛时,对最近邻搜索方法做了一些泛读和总结。主要以下分为几大类。

        一是基于树形的高维索引,如kd-tree,R-tree等,但当维度较高时,查询性能急剧下降。

        二是基于map-reduce方法,选择合适个数的中心点,相当于一个聚类操作,将一个中心点定义为一个cell。使用多个计算节点将查找集和被查找集同时映射到距离最近的中心点,也就是对应的cell中。对每个cell中的点进行reduce,计算cell内部的一些数据用于后续处理,如cell内向量总数等。为了减少错误率,与查找向量最近的向量可能不在同一个cell中,采用启发式复制的方式,从相邻的cell中复制向量进行距离计算。更多的优化细节见论文

    Comparing MapReduce-Based k-NN Similarity Joins on Hadoop for High-Dimensional Data

    这种方法适合查找集规模很大时,并行计算会产生较优的效果。

        三是facebook提出的矢量量化方法faiss具有比较好的效果且支持数据集的动态增删。

        四是哈希方法,即本文的重点,局部敏感散列(LSH),其核心思想是:设计一种特殊的hash函数,使得2个相似度很高的数据以较高的概率映射成同一个hash值,而令2个相似度很低的数据以极低的概率映射成同一个hash值。我们把这样的函数,叫做LSH。根据这次比赛的数据规模我们最终选择这个方法。网上对于LSH介绍的博客已经有很多,以及对于欧式距离量度的p-stable哈希都有了比较详细的介绍(可参考这篇文章LSH(Locality Sensitive Hashing)原理与实现),但对于我们想要使用的cross-polytope LSH却鲜少有中文资料可供参考,因此写下这篇博客用于记录。如读者发现其中的什么问题可指正于我。

        该哈希函数使用了这样一个结论,向量归一化后,欧式距离等价于余弦距离。

        将cross-polytope用通俗的语言解释即为,将所有向量归一化到一个单位球面上,每次对球做一个随机旋转相当于一个哈希函数,将球面上的向量按区域分割,映射为不同的哈希函数值,相当于做完了一次哈希。接下来与LSH思想相同,k个哈希函数构成一个哈希表,使用独立的L个哈希表进行相似性查询。

        所使用的哈希函数如下:

        x为归一化后的向量,G为独立同分布的随机高斯矩阵(相当于一次随机旋转)。u为1到d维度中某维度为正负1的基向量,选择最近的基向量作为哈希函数值。可用以下方法简化计算,得到的结果等价。

        即计算出x随机旋转后绝对值最大的数所在的维度,若为负则+=d。至此,这个哈希函数将所有向量映射为2d个不同的哈希值。

        而对于一个随机高斯矩阵与向量相乘时间复杂度为,有一个可以降低时间复杂度的方法,即使用伪随机旋转。,其中H表示哈达玛变换,有实现好的库可供调用。D为对角线为+1或-1的对角矩阵。即对x做三次这样的变换以达到随机旋转的效果。时间复杂度为

        以上提到的cross-polytope LSH在已经在FALCONN开源工具包中实现,可点击链接查看文档及github中的代码。另外,在FALCONN中实现了两个哈希函数,另一个是hyperplane LSH。刚才我们提到,在计算哈希函数值时从所有d个维度中选择最近邻,实际上使用代替d得到的哈希函数也可使用。而当时得到的哈希函数即为hyperplane LSH。

        下面对单个表中哈希函数个数k和哈希表数L做一个简单的总结。对于单表哈希,希望k取得足够大,使得每个桶中点的数量较少,获得较优的查询效率,而LSH实际上是一个概率性映射,查询样本与最近邻落入同一桶中的可能性变得很微弱,即漏报率增加(本来相近的两条数据认为是不相近的)。对于这个问题,我们重复这个过程L次,构建L个独立的哈希表,从而增加最近邻的召回率。

        处理大数据集时往往需要很多个独立的哈希表以获得较好的召回率,这样会带来很高的内存代价。因此提出了multiprobe LSH概念,即在单表中选择查询向量最有可能落入的T个桶中,在这T个桶中进行线性搜索。对于其上三个参数的选取可采取以下原则:首先,根据可使用的内存大小选取L,然后在K和T之间做出折中:哈希函数数目K越大,相应地,近邻哈希桶的数目的数目T也应该设置得比较大,反之K越小,L也可以相应的减小。获取K和L最优值的方式可以按照如下方式进行:对于每个固定的K,如果在查询样本集上获得了我们想要的精度,则此时T的值即为合理的值。在对T进行调参的时候,我们不需要重新构建哈希表,甚至我们还可以采用二分搜索的方式来加快T参数的选取过程。也是FALCONN中实现的方式。





    展开全文
  • Tensorboard高维向量可视化

    千次阅读 2018-07-18 16:03:39
    Tensorflow高维向量可视化 觉得有用的话,欢迎一起讨论相互学习~Follow Me 参考文献 强烈推荐Tensorflow实战Google深度学习框架 实验平台: Tensorflow1.4.0 python3.5.0 MNIST数据集将四个文件下载后...

    Tensorboard高维向量可视化

    觉得有用的话,欢迎一起讨论相互学习~

    我的微博我的github我的B站

    参考文献
    强烈推荐Tensorflow实战Google深度学习框架
    实验平台:
    Tensorflow1.4.0
    python3.5.0
    MNIST数据集将四个文件下载后放到当前目录下的MNIST_data文件夹下

    高维向量表示

    • 为了更加直观的了解embedding 向量的效果,TensorBoard 提供了PROJECTOR 界面来可视化高维向量之间的关系。PROJECTOR 界面可以非常方便地可视化多个高维向量之间的关系。比如在图像迁移学习中可以将一组目标问题的图片通过训练好的卷积层得到瓶颈层 ,这些瓶颈层向量就是多个高维向量。如果在目标问题图像数据集上同一种类的图片在经过卷积层之后得到的瓶颈层向量在空间中比较接近,那么这样迁移学习得到的结果就有可能会更好。类似地,在训练单词向量时,如果语义相近的单词所对应的向量在空间中的距离也比较接近的话,那么自然语言模型的效果也有可能会更好。

    • 为了更直观地介绍TensorBoard PROJECTOR 的使用方法,本节将给出一个MNIST的样例程序。这个样例程序在MNIST 数据上训练了一个简单的全连接神经网络。本节将展示在训练100轮和10000轮之后,测试数据经过整个神经网络得到的输出层向量通过PROJECTOR 得到的可视化结果。为了在PROJECTOR中更好地展示MNIST 图片信息以及每张图片对应的真实标签,PROJECTOR 要求用户准备一个sprite 图像(所谓sprite 图像就是将一组图片组合成一整张大图片)和一个tsv文件给出每张图片对应的标签信息。以下代码给出了如何使用MNIST测试数据生成PROJECTOR所需要的这两个文件。

    示例代码

    # get_ipython().run_line_magic('matplotlib', 'inline')
    import matplotlib.pyplot as plt
    import tensorflow as tf
    import numpy as np
    import os
    from tensorflow.examples.tutorials.mnist import input_data
    
    # PROJECTOR需要的日志文件名和地址相关参数
    LOG_DIR = 'log'
    SPRITE_FILE = 'mnist_sprite.jpg'
    META_FIEL = "mnist_meta.tsv"
    
    
    # 使用给出的MNIST图片列表生成sprite图像
    def create_sprite_image(images):
        """Returns a sprite image consisting of images passed as argument. Images should be count x width x height"""
        if isinstance(images, list):
            images = np.array(images)
        img_h = images.shape[1]
        img_w = images.shape[2]
        # sprite图像可以理解成是小图片平成的大正方形矩阵,大正方形矩阵中的每一个元素就是原来的小图片。于是这个正方形的边长就是sqrt(n),其中n为小图片的数量。
        n_plots = int(np.ceil(np.sqrt(images.shape[0])))
    
        # 使用全1来初始化最终的大图片。
        spriteimage = np.ones((img_h*n_plots, img_w*n_plots))
    
        for i in range(n_plots):
            for j in range(n_plots):
                # 计算当前图片的编号
                this_filter = i*n_plots + j
                if this_filter < images.shape[0]:
                    # 将当前小图片的内容复制到最终的sprite图像
                    this_img = images[this_filter]
                    spriteimage[i*img_h:(i + 1)*img_h,
                    j*img_w:(j + 1)*img_w] = this_img
    
        return spriteimage
    
    
    # 加载MNIST数据。这里指定了one_hot=False,于是得到的labels就是一个数字,表示当前图片所表示的数字。
    mnist = input_data.read_data_sets("./MNIST_data", one_hot=False)
    
    # 生成sprite图像
    to_visualise = 1 - np.reshape(mnist.test.images, (-1, 28, 28))
    sprite_image = create_sprite_image(to_visualise)
    
    # 将生成的sprite图片放到相应的日志目录下
    path_for_mnist_sprites = os.path.join(LOG_DIR, SPRITE_FILE)
    plt.imsave(path_for_mnist_sprites, sprite_image, cmap='gray')
    plt.imshow(sprite_image, cmap='gray')
    
    # 生成每张图片对应的标签文件并写道相应的日志目录下
    path_for_mnist_metadata = os.path.join(LOG_DIR, META_FIEL)
    with open(path_for_mnist_metadata, 'w') as f:
        f.write("Index\tLabel\n")
        for index, label in enumerate(mnist.test.labels):
            f.write("%d\t%d\n"%(index, label))
    
    • 运行以上代码可以得到两个文件, 一个是MNIST 测试数据sprite图像,这个图像包含了所有的MNIST测试数据图像。另一个是mnist meta.tsv ,下面给出了这个tsv 文件的前面几行。可以看出,这个文件的第一行是每一列的说明,以后的每一行代表一张图片,在这个文件中给出了每一张图对应的真实标签。

    • 在生成好辅助数据之后,以下代码展示了如何使用TensorFlow 代码生成PROJECTOR
      所需要的日志文件来可视化MNIST测试数据在最后的输出层向量。
    import tensorflow as tf
    import mnist_inference
    import os
    import tqdm
    
    # 加载用于生成PROJECTOR日志的帮助函数
    from tensorflow.contrib.tensorboard.plugins import projector
    from tensorflow.examples.tutorials.mnist import input_data
    
    BATCH_SIZE = 100
    LEARNING_RATE_BASE = 0.8
    LEARNING_RATE_DECAY = 0.99
    REGULARIZATION_RATE = 0.0001
    TRAINING_STEPS = 10000
    MOVING_AVERAGE_DECAY = 0.99
    
    LOG_DIR = 'log_2'
    SPRITE_FILE = 'mnist_sprite.jpg'
    META_FIEL = "mnist_meta.tsv"
    TENSOR_NAME = "FINAL_LOGITS"
    
    
    # 这里需要返回最后测试数据经过整个神经网络得到的输出层矩阵,因为有多张测试图片,每张图片对应了一个输出层向量。所以返回的结果是这些向量组成的矩阵。
    def train(mnist):
        #  输入数据的命名空间。
        with tf.name_scope('input'):
            x = tf.placeholder(tf.float32, [None, mnist_inference.INPUT_NODE], name='x-input')
            y_ = tf.placeholder(tf.float32, [None, mnist_inference.OUTPUT_NODE], name='y-input')
        regularizer = tf.contrib.layers.l2_regularizer(REGULARIZATION_RATE)
        y = mnist_inference.inference(x, regularizer)
        global_step = tf.Variable(0, trainable=False)
    
        # 处理滑动平均的命名空间。
        with tf.name_scope("moving_average"):
            variable_averages = tf.train.ExponentialMovingAverage(MOVING_AVERAGE_DECAY, global_step)
            variables_averages_op = variable_averages.apply(tf.trainable_variables())
    
        # 计算损失函数的命名空间。
        with tf.name_scope("loss_function"):
            cross_entropy = tf.nn.sparse_softmax_cross_entropy_with_logits(logits=y, labels=tf.argmax(y_, 1))
            cross_entropy_mean = tf.reduce_mean(cross_entropy)
            # 由于使用L2正则化,此处需要加上'losses'集合
            loss = cross_entropy_mean + tf.add_n(tf.get_collection('losses'))
    
        # 定义学习率、优化方法及每一轮执行训练的操作的命名空间。
        with tf.name_scope("train_step"):
            learning_rate = tf.train.exponential_decay(
                LEARNING_RATE_BASE,
                global_step,
                mnist.train.num_examples/BATCH_SIZE, LEARNING_RATE_DECAY,
                staircase=True)
    
            train_step = tf.train.GradientDescentOptimizer(learning_rate).minimize(loss, global_step=global_step)
            # 由于使用了滑动平均方法,所以在反向传播时也要更新可训练变量的滑动平均值
            with tf.control_dependencies([train_step, variables_averages_op]):
                train_op = tf.no_op(name='train')
    
        # 训练模型。
        with tf.Session() as sess:
            tf.global_variables_initializer().run()
            for i in tqdm.tqdm(range(TRAINING_STEPS)):
                xs, ys = mnist.train.next_batch(BATCH_SIZE)
                _, loss_value, step = sess.run([train_op, loss, global_step], feed_dict={x: xs, y_: ys})
    
                if i%1000 == 0:
                    print("After %d training step(s), loss on training batch is %g."%(i, loss_value))
            # 计算MNIST测试数据对应的输出层矩阵
            final_result = sess.run(y, feed_dict={x: mnist.test.images})
        # 返回输出层矩阵的值
        return final_result
    
    
    # 生成可视化最终输出层向量所需要的日志文件
    def visualisation(final_result):
        # 使用一个新的变量来保存最终输出层向量的结果,因为embedding是通过Tensorflow中变量完成的,所以PROJECTOR可视化的都是TensorFlow中的变哇。
        # 所以这里需要新定义一个变量来保存输出层向量的取值
        y = tf.Variable(final_result, name=TENSOR_NAME)
        summary_writer = tf.summary.FileWriter(LOG_DIR)
    
        # 通过project.ProjectorConfig类来帮助生成日志文件
        config = projector.ProjectorConfig()
        # 增加一个需要可视化的bedding结果
        embedding = config.embeddings.add()
        # 指定这个embedding结果所对应的Tensorflow变量名称
        embedding.tensor_name = y.name
    
        # Specify where you find the metadata
        # 指定embedding结果所对应的原始数据信息。比如这里指定的就是每一张MNIST测试图片对应的真实类别。在单词向量中可以是单词ID对应的单词。
        # 这个文件是可选的,如果没有指定那么向量就没有标签。
        embedding.metadata_path = META_FIEL
    
        # Specify where you find the sprite (we will create this later)
        # 指定sprite 图像。这个也是可选的,如果没有提供sprite 图像,那么可视化的结果
        # 每一个点就是一个小困点,而不是具体的图片。
        embedding.sprite.image_path = SPRITE_FILE
        # 在提供sprite图像时,通过single_image_dim可以指定单张图片的大小。
        # 这将用于从sprite图像中截取正确的原始图片。
        embedding.sprite.single_image_dim.extend([28, 28])
    
        # Say that you want to visualise the embeddings
        # 将PROJECTOR所需要的内容写入日志文件。
        projector.visualize_embeddings(summary_writer, config)
    
        # 生成会话,初始化新声明的变量并将需要的日志信息写入文件。
        sess = tf.InteractiveSession()
        sess.run(tf.global_variables_initializer())
        saver = tf.train.Saver()
        saver.save(sess, os.path.join(LOG_DIR, "model"), TRAINING_STEPS)
    
        summary_writer.close()
    
    
    # 主函数先调用模型训练的过程,再使用训练好的模型来处理MNIST测试数据,
    # 最后将得到的输出层矩阵输出到PROJECTOR需要的日志文件中。
    def main(argv=None):
        mnist = input_data.read_data_sets("./MNIST_data", one_hot=True)
        final_result = train(mnist)
        visualisation(final_result)
    
    
    if __name__ == '__main__':
        main()
    

    实验结果

    # 使用cmd命令行定位到py项目文件夹启动tensorboard
    tensorboard --logdir=项目绝对地址
    
    • 使用T-SNE方式显示高维向量,这是一个动态的过程,其中随着iteration的增加,会发现结果向量会逐渐分开。相同类别的会聚拢在一起,我们可以选择不同颜色作为区分,发现不同颜色的预测结果的区分度逐渐拉大。

    • 其中我们使用Label作为color map的区分,Label by index

    • 在PROJECTOR 界面的左上角有三个选项,第一个"FINAL LOGITS"选项是选择需要可视化的Tensor,这里默认选择的是通过ProjectorConfig 中指定的tensor_name,也就是名为FINAL LOGITS 的张量。虽然PROJECTOR也可以可视化这些向量,但是在这个场景下意义不大。中间的"Label by"选项可以控制当鼠标移到一个向量上时鼠标附近显示的标签。比如这里选定的是"Index",那么当鼠标移到某个点上之后显示的就是这个点对应的编号。

    • 在PROJECTOR界面的左下角提供了不同的高维向量的可视化方法,目前主要支持的就是T-SNE和PCA。无论是T-SNE还是PCA都可以将一个高维向量转化成一个低维向量,井尽量保证转化后向量中的信息不受影响。
    • 在PROJECTOR 的右侧还提供了高亮功能。
    • 下图展示了搜索所有代表数字3的图片,可以看出所有代表数字33的图片都被高亮标出来了,而且大部分的图片都集中在一个比较小的区域,只有少数离中心区域比较远。通过这种方式可以很快地找到每个类别中比较难分的图片,加速错误案例分析的过程。
    展开全文
  • 编者按: 以图搜图、商品推荐、社交推荐等社会场景中潜藏了大量非结构化数据,这些数据被工程师们表达为具有隐式语义的高维向量。为了更好应对高维向量检索这一关键问题,杭州电子科技大学计算机专业硕士王梦召等人...

    编者按: 

    以图搜图、商品推荐、社交推荐等社会场景中潜藏了大量非结构化数据,这些数据被工程师们表达为具有隐式语义的高维向量。为了更好应对高维向量检索这一关键问题,杭州电子科技大学计算机专业硕士王梦召等人探索并实现了「效率和精度最优权衡的近邻图索引」,并在数据库顶会 VLDB 2021 上发表成果。

    作为连接生产和科研的桥梁,Zilliz 研究团队一直与学界保持交流、洞察领域前沿。此次,王梦召来到 Z 星,从研究动机、算法分析、实验观测和优化讨论等维度展开讲讲最新的科研成果。

    以下是他的干货分享,点击这里可获得论文全文 。

    高维数据检索:基于近邻图的近似最近邻搜索算法实验综述

    导言

    向量检索是很多 AI 应用必不可少的基础模块。近年来,学术界和工业界提出了很多优秀的基于近邻图的ANNS 算法以及相关优化,以应对高维向量的检索问题。但是针对这些算法,目前缺乏统一的实验评估和比较分析。

    为了优化算法设计、进一步落地工业应用,我们完成了论文《A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search》。该论文聚焦实现了效率和精度最优权衡的近邻图索引,综述了 13 种具有代表性相关算法,实验在丰富的真实世界数据集上执行。我们的贡献可总结如下:

    1. 根据图索引的特征,我们将基于近邻图的 ANNS 算法划分为四类,这给理解现存算法提供了一个新的视角。在此基础上,我们阐述了算法间的继承和发展关系,从而梳理出算法的发展脉络;

    2. 我们分解所有算法为 7 个统一的细粒度组件,它们构成一个完整的算法执行流程,从而实现了算法的原子级分析。我们可以公平评估当前工作在某一组件的优化通过控制其它组件一致;

    3. 我们采用多样的数据集(包括 8 个真实世界数据集,它们包括视频、语音、文本和图像生成的高维向量)和指标评估当前算法的全面性能;

    4. 我们提供了不同场景下最优算法推荐、算法优化指导、算法改进示例、研究趋势和挑战的分析讨论。

    研究动机

    根据以下观测,我们对 13 种基于近邻图的 ANNS 算法进行了比较分析和实验综述:

    • 目前,学术界和工业界提出 10 余种常见的近邻图算法,但对于这些算法的合理分类和比较分析较为缺乏。根据我们的研究,这些算法的索引结构可归结为 4 种基础的图结构,但这些图存在着非常多的问题,如复杂度太高等。所以,在这 4 种图结构基础上有多种优化,如对相对邻域图(RNG)优化就包含 HNSW、DPG、NGT、NSG、SPTAG 等算法。

    • 很多现有的论文从“分子”角度评估基于近邻图的 ANNS 算法(宏观角度)。然而,我们发现,这些算法有一个统一的“化学表达式”,它们还可再向下细分为“原子”(微观角度),从“原子”角度分析可以产生一些新发现,比如很多算法都会用到某一“原子”(HNSW,NSG,KGraph,DPG的路由是相同的)。

    • 除了搜索效率和精度的权衡之外,基于近邻图的 ANNS 算法的其它特征(包含在索引构建和搜索中)也间接影响了最终的搜索性能。在搜索性能逐渐达到瓶颈的情况下,我们对于索引构建效率、内存消耗等指标给予了重视。

    • 一个算法的优越性并不是一成不变的,数据集的特征在其中起着至关重要的作用。比如,在 Msong(语音生成的向量数据集)上NSG 的加速是 HNSW 的 125 倍;然而,在 Crawl(文本生成的向量数据集)上 HNSW 的加速是 NSG 的 80 倍。我们在多样的数据集上执行实验评估,从而对算法形成更全面的认识。

    近邻图算法“分子”级分析

    在分析基于近邻图的 ANNS 算法之前,首先给大家介绍下 4 个经典的图结构,即:德劳内图(DG)、相对领域图(RNG)、K 近邻图(KNNG)、最小生成树(MST)。如图1所示,这四种图结构的差异主要体现在选边过程,简单总结如下:DG 确保任意 3 个顶点 x, y, z 形成的三角形 xyz 的外接圆内部及圆上不能有除了 x, y, z 之外的其它顶点;RNG 要确保(b)中月牙形区域内不能有其它点,这里的月牙形区域是分别以x和y为圆心,x 与 y 之间的距离为半径的两个圆的交集区域;KNNG 每个顶点连接 K 个最近的邻居;MST 在保证联通性的情况下所有边的长度(对应两个顶点的距离)之和最小。

    e8eef6416fe143ff937f5958f0730e6b.png

    图1 四种图结构在相同的数据集上的构建结果

    接下来,我将基于图1 中的 4 个图结构来梳理 13 个基于近邻图的ANNS算法。为了避免翻译造成了理解偏差,算法名使用英文简称,算法的原论文链接、部分高质量的中文介绍、部分代码请见参考资料。各算法之间更宏观的联系可参考论文中的表2 和图3。

    算法1:NSW

    NSW 是对 DG 的近似,而 DG 能确保从任意一个顶点出发通过贪婪路由获取精确的结果(即召回率为 1 )。NSW 是一个类似于“交通枢纽”的无向图,这会导致某些顶点的出度激增,从论文的表11 可知,NSW 在某些数据集上的最大出度可达几十万。NSW 通过增量插入式的构建,这确保了全局连通性,论文表4 中可知,NSW的连通分量数均为1。NSW 具有小世界导航性质:在构建早期,形成的边距离较远,像是一条“高速公路”,这将提升搜索的效率;在构建后期,形成的边距离较近,这将确保搜索的精度。

    原文:https://www.sciencedirect.com/science/article/abs/pii/S0306437913001300

    中文介绍:https://blog.csdn.net/u011233351/article/details/85116719

    代码:https://github.com/kakao/n2

    算法2:HNSW

    HNSW 在 NSW 的基础上有两个优化:“层次化”和“选边策略”。层次化的实现较为直观:不同距离范围的边通过层次呈现,这样可以在搜索时形成类似于跳表结构,效率更高。选边策略的优化原理是:如果要给某个顶点连接 K 个邻居的话,NSW 选择 K 个距离最近的,而 HNSW 从大于 K 个最近的顶点里面选出更离散分布的邻居(见参考资料1)。因此,从选边策略考虑,HNSW 是对 DG 和 RNG 的近似。

    原文:https://ieeexplore.ieee.org/abstract/document/8594636

    中文介绍:https://blog.csdn.net/u011233351/article/details/85116719

    代码:https://github.com/kakao/n2

    算法3:FANNG

    FANNG 的选边策略与 HNSW 是一样的,都是对RNG近似。FANNG 比 HNSW 更早提出,不过当前 HNSW 得到更普遍的应用,可能的原因是:

    (1)FANNG 的选边策略是在暴力构建的近邻图的基础上实现的,构建效率很低;

    (2)HNSW 通过增量式构建且引入分层策略,构建和搜索效率都很高;

    (3)HNSW 开源了代码,FANNG 则没有。

    原文:https://www.cv-foundation.org/openaccess/content_cvpr_2016/html/Harwood_FANNG_Fast_Approximate_CVPR_2016_paper.html

    算法4:NGT

    NGT 是雅虎日本开源的向量检索库,核心算法基于近邻图索引。NGT 在构建近邻图时类似于 NSW,也是对 DG 的近似,后续有一些度调整优化,其中最有效的路径优化也是对 RNG 的近似(论文的附件B 也给出了证明)。

    原文1:https://link.springer.com/chapter/10.1007/978-3-319-46759-7_2

    原文2:https://arxiv.org/abs/1810.07355

    代码:https://github.com/yahoojapan/NGT

    算法5:SPTAG

    SPTAG 是微软发布的向量检索库,它的构建过程基于分治策略,即迭代地划分数据集,然后在每个子集上构建近邻图,接着归并子图,最后通过邻域传播策略进一步优化近邻图。上述过程旨在构建一个尽可能精确的 KNNG。在搜索时,SPTAG 采用树索引和图索引交替执行的方案,即先从树上获取距查询较近的点作为在图上搜索的起始点执行路由,当陷入局部最优时继续从树索引上获取入口点,重复上述操作直至满足终止条件。

    原文1:https://dl.acm.org/doi/abs/10.1145/2393347.2393378

    原文2:https://ieeexplore.ieee.org/abstract/document/6247790

    原文3:https://ieeexplore.ieee.org/abstract/document/6549106

    中文介绍1:https://blog.csdn.net/whenever5225/article/details/108013045

    中文介绍2:https://cloud.tencent.com/developer/article/1429751

    代码:https://github.com/microsoft/SPTAG

    代码使用:https://blog.csdn.net/qq_40250862/article/details/95000703

    算法6:KGraph

    KGraph 是对 KNNG 的近似,是一种面向一般度量空间的近邻图构建方案。基于邻居的邻居更可能是邻居的思想,KGraph 能够快速构建一个高精度的 KNNG。后续的很多算法(比如 EFANNA、DPG、NSG、NSSG)都是在该算法的基础上的进一步优化。

    原文:https://dl.acm.org/doi/abs/10.1145/1963405.1963487

    中文介绍:https://blog.csdn.net/whenever5225/article/details/105598694

    代码:https://github.com/aaalgo/kgraph

    算法7:EFANNA

    EFANNA 是基于 KGraph 的优化。两者的差别主要体现在近邻图的初始化:KGraph 是随机初始化一个近邻图,而 EFANNA 是通过 KD 树初始化一个更精确的近邻图。此外,在搜索时,EFANNA 通过 KD 树获取入口点,而 KGraph 随机获取入口点。

    原文:https://arxiv.org/abs/1609.07228

    中文介绍:https://blog.csdn.net/whenever5225/article/details/104527500

    代码:https://github.com/ZJULearning/ssg

    算法8:IEH

    类比 EFANNA,IEH 暴力构建了一个精确的近邻图。在搜索时,它通过哈希表获取入口点。

    原文:https://ieeexplore.ieee.org/abstract/document/6734715/

    算法9:DPG

    在 KGraph 的基础上,DPG 考虑顶点的邻居分布多样性,避免彼此之间非常接近的邻居重复与目标顶点连边,最大化邻居之间的夹角,论文的附件4 证明了 DPG 的选边策略也是对 RNG 的近似。此外,DPG 最终添加了反向边,是无向图,因此它的最大出度也是非常高的(见论文附件表11)。

    原文:https://ieeexplore.ieee.org/abstract/document/8681160

    中文介绍:https://blog.csdn.net/whenever5225/article/details/106176175

    代码:https://github.com/DBW

    算法10:NSG

    NSG 的设计思路与 DPG 几乎是一样的。在 KGraph 的基础上,NSG 通过 MRNG 的选边策略考虑邻居分布的均匀性。NSG 的论文中将 MRNG 的选边策略与 HNSW 的选边策略做了对比,例证了 MRNG 的优越性。论文中的附件1 证明了NSG的这种选边策略与 HNSW 选边策略的等价性。NSG 的入口点是固定的,是与全局质心最近的顶点。此外,NSG 通过 DFS 的方式强制从入口点至其它所有点都是可达的。

    原文:http://www.vldb.org/pvldb/vol12/p461-fu.pdf

    中文介绍:https://zhuanlan.zhihu.com/p/50143204

    代码:https://github.com/ZJULearning/nsg

    算法11:NSSG

    NSSG 的设计思路与 NSG、DPG 几乎是一样的。在 KGraph 的基础上,NSSG 通过 SSG 选边策略考虑邻居分布的多样性。NSSG 认为,NSG 过度裁边了(见论文表4),相比之下 SSG 的裁边要松弛一些。NSG 与 NSSG 另一个重要的差异是,NSG 通过贪婪路由获取候选邻居,而 NSSG 通过邻居的一阶扩展获取候选邻居,因此,NSSG 的构建效率更高。

    原文:https://ieeexplore.ieee.org/abstract/document/9383170

    中文介绍:https://zhuanlan.zhihu.com/p/100716181

    代码:https://github.com/ZJULearning/ssg

    算法12:Vamana

    简单来说,Vamana 是 KGraph、HNSW 和 NSG 三者的结合优化。在选边策略上,Vamana 在 HNSW (或 NSG)的基础上增加了一个调节参数,选边策略为 HNSW 的启发式选边,取不同的值执行了两遍选边。

    原文:http://harsha-simhadri.org/pubs/DiskANN19.pdf

    中文介绍:https://blog.csdn.net/whenever5225/article/details/106863674

    算法13:HCNNG

    HCNNG 是目前为止唯一一个以 MST 为基本构图策略的向量检索算法。类似SPTAG,HCNNG 的构建过程基于分治策略,在搜索时通过 KD 树获取入口点。

    原文:https://www.sciencedirect.com/science/article/abs/pii/S0031320319302730

    中文介绍:https://whenever5225.github.io/2019/08/17/HCNNG/

    近邻图算法“原子”级分析

    我们发现所有的基于近邻图的 ANNS 算法都遵循统一的处理流程框架,该流程里面有多个公共模块(如图2 的 C1->C7)。当一个近邻图算法按照该流程被解构后,我们可以很容易了解该算法是如何设计组装的,这将给后续近邻图向量检索算法的设计带来很大的便利性。此外,我们也可固定其它模块,保持其他模块完全相同,从而更公平地评估不同算法在某一模块实现上的性能差异。

    d8d032f227b437b484a934312868cd52.png

    图2 近邻图向量检索算法遵循的统一流程框架图

    接下来,我们以 HNSW 和 NSG 为例,说明如何实现图2 的流程框架分析算法。在此之前,我们要先熟悉这两个算法的索引构建和搜索过程。

    首先是 HNSW 分解,HNSW 的构建策略是增量式的。因此,每插入一个数据点都要执行一遍 C1->C3 过程。

    HNSW 分解流程:

    模块

    HNSW 具体实现

    C1

    生成新插入点所处的最大层;获取搜索入口点

    C2

    新插入点作为查询点,从入口点开始,贪婪搜索,返回新插入点一定量最近邻作为邻居候选

    C3

    启发式选边策略

    C4

    无额外步骤,最高层中的顶点作为入口

    C5

    无额外步骤,增量式构建已隐式确保连通性(启发式选边有一定程度破坏连通性)

    C6

    最高层的顶点作为入口

    C7

    最佳优先搜索

    NSG 分解流程:

    模块

    NSG 具体实现

    C1

    NN-Descent 初始化近邻图

    C2

    顶点作为查询,贪婪搜索获取邻居候选

    C3

    MRNG 选边策略

    C4

    全局质心作为查询,贪婪搜索获取最近顶点作为入口

    C5

    从入口开始,DFS 确保连通性

    C6

    C4 获取的入口

    C7

    最佳优先搜索

    由于 HNSW 的 C3 与 NSG 的 C3 是等价的,因此,从上面两个表格可知,HNSW 与 NSG 这两个算法差别并不大。其实,论文涉及到的 13 种算法中很多算法之间都是很相似的,详见论文第 4 章。

    实验观测和讨论

    具体的实验评估请参考论文第 5 章,接下来将概括介绍一下实验的观测结果和讨论:

    不同场景下的算法推荐

    NSG 和 NSSG 普遍有最小的索引构建时间和索引尺寸,因此,它们适用于有大量数据频繁更新的场景;如果我们想要快速构建一个精确的 KNNG(不仅用于向量检索),KGraph、EFANNA 和 DPG 更适合;DPG 和 HCNNG 有最小的平均搜索路径长度,因此,它们适合需要 I/O 的场景;对于 LID 值高的较难数据集,HNSW、NSG、HCNNG 比较适合;对于 LID 值低的简单数据集,DPG、NSG、HCNNG 和 NSSG 较为适合;NGT 有更小的候选集尺寸,因此适用于 GPU 加速(考虑到 GPU 的内存限制);当对内存消耗要求较高时,NSG 和 NSSG 适合,因为它们内存占用更小。

    算法设计向导

    一个实用的近邻图向量检索算法一般满足以下四个方面:

    1. 高构建效率

    2. 高路由效率

    3. 高搜索精度

    4. 低内存负载

    针对第一方面,我们不要在提升近邻图索引质量(即一个顶点的邻居中真实的最近邻居所占的比例)上花费太多的时间。因为最好的图质量(可通过图中与距它最近的顶点有边相连的顶点所占比例度量)不一定实现最佳搜索性能(结合论文中表4 和图7、8)。

    针对第二方面,我们应当控制适当的平均出度,多样化邻居的分布,减少获取入口点的花费,优化路由策略,从而减少收敛到查询点的邻域所需的距离计算次数。

    针对第三方面,我们应当合理设计邻居的分布,确保连通性,从而提升对陷入局部最优的"抵抗力"。

    针对第四方面,我们应当优化邻居选择策略和路由策略,从而减小出度和候选集尺寸。

    优化算法示例

    基于上面的向导,我们组装了一个新的近邻图算法(图3 中的 OA),该算法在图2 中的 7 个组件中每个组件选中现存算法的一个具体实现,即 C1 采用 KGraph 算法的实现;C2 采用 NSSG 算法的实现;C3 采用 NSG 算法的实现;C4 采用 DPG 算法的实现;C5 采用 NSSG 算法的实现;C6 采用 DPG 算法的实现;C7 采用 HCNNG 和 NSW 算法的实现。

    OA 算法实现了当前最优的综合性能,详见论文原文。因此,我们甚至不用优化当前算法,仅仅把现存算法的不同部分组装起来就可以形成一个新算法。

    d76165220a7acf6ef6f100e69d78eb43.png

    图3  OA 算法与当前最优的近邻图算法的搜索性能对比

    趋势与挑战

    基于 RNG 的选边策略设计在当前近邻图向量检索算法的效率提升中起到了关键作用。在论文的评估中,唯一一个基于 MST 的算法 HCNNG 也表现出来很好的综合性能。

    在上述纯近邻图算法基础上,后续发展有三个主要方向:

    1. 硬件优化;

    2. 机器学习优化;

    3. 更高级的查询需求,比如结构化和非结构化混合查询。

    我们未来面对这三个挑战:

    1. 数据编码技术与图索引如何有机结合以解决近邻图向量检索算法高内存消耗问题;

    2. 硬件加速近邻图索引构建减少近邻图索引构建时间;

    3. 根据不同场景的特征自适应选择最优的近邻图算法。

    参考资料

    https://blog.csdn.net/whenever5225/article/details/106061653?spm=1001.2014.3001.5501

    ✏️ 关于作者:

    王梦召,杭州电子科技大学计算机专业硕士。主要关注基于近邻图的向量相似性检索、多模态检索等研究内容,并在相关方向申请发明专利三项,在数据库顶会 VLDB 和 SCI 一区 top 期刊 KBS 等发表论文两篇。

    日常爱好弹吉他、打乒乓球、跑步、看书,他的个人网站是 http://mzwang.top,Github主页是 http://github.com/whenever5225

    ●  ●  ●  

    Arch Meetup 深圳站开始报名啦,点击查看活动议程! 

    4ef7a6db744b49b65927f8a92f988c6f.png

    ed829a6abdeeb103cabf40d65e32a679.png

    GitHub @Milvus-io|CSDN @Zilliz Planet|Bilibili @Zilliz-Planet

    Zilliz 以重新定义数据科学为愿景,致力于打造一家全球领先的开源技术创新公司,并通过开源和云原生解决方案为企业解锁非结构化数据的隐藏价值。

    Zilliz 构建了 Milvus 向量数据库,以加快下一代数据平台的发展。Milvus 数据库是 LF AI & Data 基金会的毕业项目,能够管理大量非结构化数据集,在新药发现、推荐系统、聊天机器人等方面具有广泛的应用。

    展开全文
  • 放在全文开头,这次去南京的感受。  这一届软件杯组委会安排的酒店很舒适,志愿者小姐姐偏多很养眼,很热心,咨询的时候讲解也很周到。...假设如下数据集D里有N个1024维的向量, N=1百万,向量中各个维度上的数据...
  • 1 高维向量检索问题 高维向量检索主要解决由数据维数增加所引发检索速度急剧下降的的问题。高维空间中数据的特点主要包括以下三个方面:(1) 稀疏性。随着维度增长,数据在空间分布的稀疏性增强;(2) 空空间现象。...
  • TSNE高维向量降维3D可视化

    千次阅读 2019-03-23 11:02:04
    搞深度学习时可能会遇到想可视化神经网络某一层的输出...TSNE和PCA两种方法都可以实现高维向量可视化,两者原理不同,速度也差很多,TSNE会慢一些。 这里主要还是用到了python里的matplotlib库进行图形绘制。 ...
  • 高维聚类

    千次阅读 2018-05-31 17:05:18
    高维空间下,几乎所有的点对之间的距离都差不多相等 考虑一个d维欧式空间,假设在一个单位立方体内随机选择n个点。首先,如果d为1,那么久相当于在一个长度为1的线段上随机放置点,那么将会有两类点连续点(距离...
  • 数学概念嘛,在不同的应用场景下意义是不大一样的,比如说对于机械或者物理的同学,向量是有长度有方向的一个指向空间的带箭头的线段,而对于从事计算机工作的我们来说,向量定义可以是非常简单粗暴的—— ...
  • 高维空间中点到超平面的距离可以表示为一个约束优化问题: {min ∥x−x0∥2s.t. wTx+b=0 \left \{ \begin{aligned} &min \quad\ \|x-x_{0}\|^{2}\\ &s.t. \quad\ w^{T}x+b=0\\ \end{aligned}...
  • UA MATH567 高维统计II 随机向量2 各向同性
  • 向量高维思考

    热门讨论 2020-11-15 21:13:34
    首先要知道什么是向量. 向量是数学,物理学,工程学科学等多个自然科学中的基本概念.。指一个同时具有大小方向,且...此处向量定义向量空间的元素,要注意这些抽象意义上的向量不一定以数对表示,大小和方向的概念
  • 一、向量大小 首先一个向量的长度或者大小一般记为。上图中的平面向量的大小计算如下: 空间向量的大小计算如下: 维复向量的大小计算如下: 二、向量归一化 向量归一化即将向量的方向保持不变,大小...
  • 高维数据异常检测

    2021-01-24 21:51:20
    一、概述 ...例如,基于距离相似度的方法通过在所有维度上使用距离函数来定义局部性。然而,某些维度可能与特定的测试点无关,这也会影响基础距离函数的质量。例如,在高维空间中,所有的点对几乎等距。这
  • 向量外积的应用

    千次阅读 2017-09-26 17:45:49
    基本概念定义: |a x b| = |a|*|b| *sinθ 方向:右手法则,叉乘后的向量的方向与这两个向量所在的平面垂直 理解:|c|=|a×b|=|a| |b|sinθ c的长度在数值上等于以a,b夹角θ组成的平行四边形的面积应用决定点在...
  • 超平面详解-SVM支持向量

    千次阅读 2018-08-13 10:03:26
    研究了半天,终于对“超平面”有了个初步了解。...其中,w 和 x 都是 n 维列向量,x 为平面上的点,w 为平面上的法向量,决定了超平面的方向,b 是一个实数,代表超平面到原点的距离。且  ...
  • 向量 模(module) 范数(norm)

    万次阅读 2019-02-14 16:52:46
    1,向量的模和范数的计算结果都是一个实数,这个数字对应着单个向量的长度或者两个向量之间的距离。 2,在空间几何中(经常是2或3维空间),常用模来表示向量的长度或两个向量间的距离,符号为||x⃗\vec{x}x||。 ...
  • 高维信息降维可视化常用算法比较

    千次阅读 2019-07-17 21:08:52
    此外,t-SNE 是一种非线性降维算法,非常适用于高维数据降维到2维或者3维,进行可视化。 我们先介绍SNE的基本原理,之后再扩展到t-SNE。最后再看一下t-SNE的实现以及一些优化。 2.1.1 流行学习 总觉得即使...
  • 向量范数

    千次阅读 2019-03-20 15:15:55
    向量范数的定义: 具有“长度”概念的函数,是向量空间到实数的映射:Rn→RR^n\to RRn→R ,并满足一下三个性质: 1)正定性:∣∣x∣∣≥0,∣∣x∣∣=0iffx=0||x||\ge 0,\quad ||x||=0 \quad iff\quad x=0∣∣x∣...
  • 降维相关

    千次阅读 2017-12-04 22:54:09
    所以,简单地说,降维就是将一个高维向量映射为一个低维的向量。形象地说,降维可以看作一个函数,输入是一个D为的向量,输出是一个M维的向量。那怎么样才算是一个好的降维结果呢?直观地说,就是要既能降低维度,...
  • 大规模特征向量检索算法总结 ... 汉明距离:一般作用于二值化向量,二值化的意思是向量的每一列只有 0 或者 1 两种取值。 汉明距离的值就两个向量每列数值的异或和,值越小说明越相似,一般用于图片识别; 杰卡.
  • 支持向量机(SVM)简介

    万次阅读 2017-10-24 10:25:29
    支持向量机(SVM)简介
  • 在数据挖掘中,我们经常需要计算样本之间的相似度,通常的做法是计算样本之间的距离。在本文中,数据科学家 Maarten Grootendorst 向我们介绍了 9 种距离度量方法,其中包括欧氏距离、余弦相似度等。 许多算法...
  • 详解支持向量

    千次阅读 2020-06-15 12:01:44
    我们将在此博客中讨论的一种这样的模型是支持向量机,简称为SVM。我的目的是为你提供简单明了的SVM内部工作。 假设我们正在处理二分类任务。 可能有无限多的超平面可以将这两个类分开。你可以选择其中任何一个。...
  • 切比雪夫距离定义为两个向量在任意坐标维度上的最大差值。换句话说,它就是沿着一个轴的最大距离。切比雪夫距离通常被称为棋盘距离,因为国际象棋的国王从一个方格到另一个方格的最小步数等于切比雪夫距离。 缺点:...
  • 本文介绍了向量定义向量的模、负向量、单位向量、零向量以及向量加减法的三种实现方法。
  • 1. 支持向量 1.1 线性可分 首先我们先来了解下什么是线性可分。 在二维空间上,两类点被一条直线完全分开叫做线性可分。 严格的数学定义是: 1.2 最大间隔超平面 从二维扩展到多维空间中时,将 d0 和 d1...
  • 支持向量机原理讲解(一)

    千次阅读 2019-03-29 08:38:30
    支持向量机(Support Vector Machine,以下简称SVM),作为传统机器学习的一个非常重要的分类算法,它是一种通用的前馈网络类型,最早是由Vladimir N.Vapnik 和 Alexey Ya.Chervonenkis在1963年提出,目前的版本(soft ...
  • 基于支持向量机的图像分类(上篇)

    万次阅读 多人点赞 2018-03-31 21:25:39
    摘要:本文通过图文详细介绍如何利用支持向量机对图像进行分类。这篇文章从什么是图像分类任务开始一步步详细介绍支持向量机原理,以及如何用它解决图像多分类任务。将这部分内容分为上下两篇:上篇重点详细介绍实现...
  • shaderforge 向量运算 Append数据维度的附加 Component Mask数据维度的分解 Channel Blend通道混合 ...distance距离 Dot Product点积 Length计算向量长度 Normalize归一化 Normal Blend法线混合 Reflection反射 T

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 15,745
精华内容 6,298
关键字:

高维向量距离定义