分布的相似度（距离）用什么模型比较好？

理由

举报取消

如果在处理的数据中，有的是分布：比如工厂内分贝值的分布，或者电机转速的分布。一般一个分布（一维的）就是一个向量，满足每一个维度都大于0且L^1(V)=1，平时我们也直接当成向量进行处理，求欧氏距离，但是觉得这样做并不科学，因为作为向量就默认了“维度”这一坐标是没有意义的，可是实际上，分布里的横坐标有着很实际的意义，比如分贝或者转速。请问用什么方法可以更好地衡量两个分布之间的相似度（或者距离）？

2017年10月17日 10 条回复 1533 次浏览

分布,学习,数据挖掘,机器,距离

回复 ( 10 )

子元初入职场
0
举报回复
理由

举报取消

用什么距离取决于你关心什么类型的差别。举几个例子。

1. Kullback-Leibler divergence和，KL散度定义为 $D_{KL}(p\|q)=\int_xp(x)\ln\frac{p(x)}{q(x)}\,\mathrm{d}x$ 。可以看出，如果要 $D_{KL}(p\|q)$ 小，那么大的地方必须要大（否则会很大）；而在小的地方，KL-divergence 的值对的大小就没那么敏感。相应地，如果要 $D_{KL}(q\|p)$ 小，那么小的地方必须也要小；而在大的地方，同样地，KL-divergence 的值对的大小也没那么敏感。

下图来自 Machine Learning: A Probabilistic Perspective（蓝色）是一个二分量的高斯混合分布，（红色）是最小化 $D_{KL}(p\|q)$ （图a）或 $D_{KL}(q\|p)$ （图b-c）的高斯分布。感受一下区别。

下图来自 Information Retrieval Perspective to Nonlinear Dimensionality Reduction for Data Visualization

2. 其他 f-divergence，如果取 $f(t)=t\log t$ 或者 $f(t)=-\log t$ 就能得到KL-divergence。除了KL-divergence，常用的 f-divergence 有 Hellinger distance，也就是说，对任意边缘分布为和的联合分布 $P_{XY}$ ，我们可以求出 $E_{P_{XY}}\left[\|x-y\|_2^2\right]$ ，而和的 Wasserstein distance 则定义为当 $P_{XY}$ 取遍可能的分布时，这个期望的最小值的平方根。

Wasserstein distance 衡量了把数据从分布“移动成”分布时所需要移动的平均距离的最小值（类似于把一堆土从一个形状移动到另一个形状所需要做的功的最小值）。下图出自 Principal Differences Analysis: Interpretable Characterization of Differences between Distributions

4. 其他。见 Statistical distance。

还是那句话：先问自己关心分布之间怎样的不同，有没有什么特殊约束或要求，再据此作相应的选择。至于题主的例子……我不太清楚“分布里的横坐标有着很实际的意义，比如分贝或者转速”这句话对“衡量两个分布之间的相似度（或者距离）”有着什么样的具体约束。题主可以先厘清一下。
豆豆叶初入职场
0
举报回复
理由

举报取消

是时候放大招了，今天我要谈谈什么是Wasserstein distance，以及为什么它那么有用。之前子元已经给了一个初步的介绍，我这个回答谈的更多的会是这个distance背后的直觉，抽象，和未被完全挖掘的潜在应用价值，并不想涉及太多公式。这也是我本人博士论文方向的重要课题。

Wasserstein distance的定义

很多人对Wasserstein distance的数学定义感觉很陌生，其实它是我们很熟悉的东西，先听我讲个啰嗦一点的小故事。假设你是一个做木材运输的，你要运送木材从若干个木材生产地到若干个木材需求地，假设每个生产地有固定数量的木材，每个需求地也有固定数量木材的需求，他们的总和（恰好）彼此相等，你要指定一个运输计划，把所有木材从生产地分别运送到需求地，使得供需刚好平衡，也就是每个生产地的木材都刚好运送走了，每个需求地都得到了预期的木材量。你将碰到这样一个问题：假设你事先已经计算好从每个生产地运送木材到每个需求地的单位木材运费，你该怎样合理的指定运输计划使得总开支最小呢？

这个问题实际上也是很好解释“optimal transport” （OT）这个名字的由来，在学术界被称为Kantorovich-Wasserstein problem/theorem，这个formulation最早也是在统计和数学领域被广发分析和理解。在计算机学界，Wasserstein distance很多时候都叫Earth Mover’s distance（EMD），在最早的EMD论文（2000）里给出的也是类似 Kantorovich-Wasserstein 的数学形式，也就是说这个东西数学上并不是新东西，我私下觉得这样取个新名字是不好的。除了常见的Kantorovich-Wasserstein形式，Wasserstein distance本身是有几个等价的数学定义，optimal transport之所以能在数学上独立成一个方向，正是因为它本身有着各种奇幻的数学等价表达，把看似不想关的东西联系起来。

Wasserstein distance的其他数学定义

Wasserstein distance一个比较常见的等价定义是Kantorovich-Rubinstein对偶原理。对偶形式在应用中也是存在现实解释的，比较经典的是在金融领域robust hedging中的例子，实际上在这个方向上optimal transport理论有了新的发展，提出了martingale OT。除此之外，Wasserstein distance在欧式距离为cost function的假设下还存在一个流体力学的解释。还是在之前的例子，假设这些木材的生产地和需求地都是海面上的一个一个小岛，运送木材的方式只能靠随着洋流漂，如果洋流场的总能量固定，那么洋流应该怎么流才能使得木材恰好从生产地漂到需求地并且时间最少？这个等价定义叫Benamou-Brenier theorem。在这个原理下，optimal transport还可以有很多unbalanced OT的变体。OT还有其他表达，比如PDE形式的等价定义Evans–Gangbo定理，比如Monge-Brenier定理。

Wasserstein distance的基本特性

正是因为OT本身的丰富数学内涵，导致每个等价定义实际上在不同的领域和方向上发展。而它对机器学习的作用实际上也是最近几年才真正开始被人挖掘。

首先，Wasserstein distance本身是刻画两个distribution之间的距离的，这个distribution必须是具有几何内蕴的，比如欧式空间上的分布，而不是比如掷骰子或者红黄球概率问题。对欧式空间里的分布，通常选择的cost function都是p次欧式距离（但是也有不一样的。比如可以选择Coulomb cost这种近大远小的cost function）在一般的应用中，cost函数还可以选取利用一些先验知识，比如在multiclass classification中不同category之间的dissimilarity，比如在document clustering 和 comparison中word和word之间的word embedding distance。

其次，Wasserstein distance的一个良好性质是，只要选取的cost function是metric，那么Wasserstein distance就是一个true metric。这点比KL divergence以及其变体来说是一大优势。

再次，2nd order Wasserstein distance对两个Gaussian distribution是有closed form的。WD对1D的分布是有简单办法的，简单来说就是把生产地和需求地排序，然后顺次匹配。所以也有人提出先把高维分布project到多个direction上然后在分别算WD然后求和（Sliced Wasserstein distance）。

再再次，OT 对任何一对连续分布都输出一个deterministic 的mapping，在这个mapping下，一个分布的mass被push forward 到另一个分布。真是因此，Wasserstein distance实际上对数据分布提供了一个天然的几何空间。但是我要强调的是这个几何空间不是Hilbert space，不存在原点，也不存在子流形（manifold），没有内积，但它可以是一个测度空间，包含合适的代数结构。

最后，我想说Wasserstein distance和RHKS MMD之间的关系，虽然两者在数学上很不一样，但是从机器学习应用的角度出发，两者是殊途同归的。细心的观众可能已经发现Wasserstein distance的对偶形式和MMD非常接近，不同点只是在先验的数学表达上选择了不同的形式。MMD需要定义事先kernel，而Wasserstein distance需要定义ground metric。从某种程度上说，我个人觉得MMD对先验的形式要求更高，因而也更不容易用。

Wasserstein distance的计算方法

虽然Wasserstein distance数学形式上非常漂亮，它在机器学习领域还是一个小学生。主要原因还是它比较庞大的计算量导致的。

没错，OT是一个bipartite graph上的minimal cost flow的问题，它既是一个离散的问题，也可以是一个数值的问题。说它是离散的问题是因为有很多离散算法专门用于解决minimal cost flow，相关的文献可以从这篇文章往后找：Tang, Yu, et al. “Earth mover’s distance based similarity search at scale.”Proceedings of the VLDB Endowment 7.4 (2013): 313-324. 说它是一个数值问题，是因为它本身是一个线性规划问题，可以用线性规划的成熟算法求解，比如对小规模问题适合用simplex，对大规模问题适合用interior point method （IPM）。特别的如果每个生产地都生产相同数量的木材，每个需求地也需要相同数量的木材，生产地数量等于需求地数量，那么这个问题就退化成一个assignment problem，解决此类问题的经典方法有Hungarian algorithm和auction algorithm。

但是无论是什么算法，想要精确求解OT，其计算复杂度都超过N的三次方（N为问题复杂度）。相比之下KL divergence这类的计算都是线性的。这样的巨大差别导致很长一段时间内，没有人真的用Wasserstein distance来取代KL divergence的地位。但是近几年这个情况出现了转机，首先是Cuturi在NIPS 2013上提出了Wasserstein distance的近似Sinkhorn distance，引入了正则化的Wasserstein distance，使用一个迭代算法，其每次迭代的计算复杂度为N的平方。之后Wang在NIPS 2014又提出了Bregman ADMM的迭代算法直接求解精确的Wasserstein，速度远超商用的linear programming solver。前者在圈内收到了广泛的应用，后者虽然知道的人不多，但是也被证明十分有效。

正是由于计算方法的突破，近两年基于Wasserstein distance的机器学习模型层出不穷，传统的PCA，LDA，NMF，Kmeans，RBM等都出现了基于Wasserstein distance的针对分布数据建模的扩展。相关论文有的已经发表在顶会上，有的还在投。我相信随着计算方法的逐渐成熟，Wasserstein distance将会成为机器学习的又一主流方向，就像当年玩kernel methods的那样。Wasserstein distance之所以非常重要，是因为它本身能够incorporate 一些复杂的先验，这对机器学习领域的问题来说是至关重要的，传统的机器学习模型很多时候太过数据driven，能用的先验非常有限，比如sparse，比如dimension reduction，比如各种regularization，对一些特定structure的复杂问题缺少合适的方案，常见的基于PGM的办法也不是特别有效，使用起来也很麻烦。

最后给点私货

推荐三个我们组最近在Wasserstein distance上的工作。

1. Wasserstein distance + Kmeans (TSP)

2. aggregated Wasserstein distance + HMM （ECCV 2016）

3. 据我所知，第三个快速计算Wasserstein loss minimization的通用优化框架（前两个是Sinkhorn和Bregman ADMM），利用了一个上古时代的思想（模拟退火）
张戎初入职场
0
举报回复
理由

举报取消

写过一篇关于 KL 散度的理论＋运用的文章：KL 散度（从动力系统到推荐系统）

在信息论和动力系统里面，Kullback-Leibler 散度（简称 KL 散度，KL divergence）是两个概率分布 P 和 Q 的一个非对称的度量公式。这个概念是由 Solomon Kullback 和 Richard Leibler 在 1951 年引入的。从概率分布 Q 到概率分布 P 的 KL 散度用 D_{KL}(P||Q) 来表示。尽管从直觉上看 KL 散度是一个度量或者是一个距离，但是它却不满足度量或者距离的定义。例如，从 Q 到 P 的 KL 散度就不一定等于从 P 到 Q 的 KL 散度。本文即将介绍如何将动力系统的概念运用到实际推荐系统的工作中，从而达到更佳的推荐效果。

详细请见：KL 散度（从动力系统到推荐系统）
潘俊初入职场
0
举报回复
理由

举报取消

首先，向量也可以认为有多个维度，每一个向量的元素对应一维。

其次，参考其他答案，你可以根据需求选择多种相似度，推荐先用 KL 散度再比较使用Wasserstein 距离。

最后，介绍下我现在做的研究，metric learning（距离度量学习）。

首先要明确的是，metric learning 是半监督学习，所以在没有已有的supervised information 数据库的支持下，请不用继续看了。

metric learning 的核心是指，运用机器学习的手段，根据已有的 supervised information 学习一个新的自定义 metric，使 new metric 比original distance 更好更符合数据特征。其中运用的手段就是最小化损失函数。

以Euclidean
distance为例， d(x,y)=||x-y||2, 新的 metric 可以表示为 d(f(x),f(y))
=
||Gx-Gy||2
,G 为映射矩阵，也就是我们需要学习的对不同特征维度的偏移权重。

可以定义的损失函数如下：

其中 r(G)是正则化因子，InsNum 是指的可以提供的实例信息数量。而 c（）是指的supervised information constraints。

一般有2种表达supervised information constraints 的方法：

similarity or dissimilarity constraints:

简单说就是同类 object 的距离要小于阈值u，而不同类的距离要大于阈值 l.

relative distance constraints:

是指同类 object 的距离要大于不同类的距离。

当然除了以上形式也有些其他的变换，从这里我们也可以看出来supervised information可以是类别标签，也可以是其他的相似度啊排名啊关联度啊等等。

举一个具体的例子：

Large-Margin Nearest Neighbors，大余量临近算法：

就是运用了权重的线性表达和relative distance constraints 的经典距离学习算法。

另一个和 KL 散度有关联的算法：

Information-Theoretic Metric Learning，信息论距离学习算法：

是运用 similarity or dissimilarity constraints 对优化前后的权重信息分布的 KL 散度最小化的算法。

说起来也是有点好玩。。。有时候为了优化 KL 散度，我们用 KL 散度来评判优化程度。。。

然而，这些算法因为只学习了 G矩阵，所以都只是基于单维和维度两两间的交集进行了权重学习。我的研究则是扩展到任意数量维度的交集进行学习。下午答辩，搞完了有人看再回来更新。。

基本只是对度量学习的简单介绍，若有错漏还望指正，转载注明出处就 OK。

关于度量学习，更多信息可以参考：

Brian Kulis.
Metric learning: A survey. Foundations and Trends in Machine Learning,

5(4):287–364, 2012.
寒蝉鸣泣初入职场
0
举报回复
理由

举报取消

1. KL divergence的问题

KL divergence 存在2个问题：

(1) 它并不是对称的。往往我们算距离的时候需要满足对称性。KL( P || Q ) != KL( Q || P )

(2) 它算出的值并不是有限的，因此无法作相对对比。比如3个分布, P, Q, R 如果 KL(P||Q) > KL(R || Q), 并不能说明分布P比R更接近Q。

不过存在更好的分布距离计算方法，叫 Jensen-Shanno divergence.

2. JS－divergence 的特征

它的结果是对称的且计算的距离在0到1之间。因此如果做相似性的度量，在0～1之间是很容易进行比较的

公式如下：

${{\rm {JSD}}}(P\parallel Q)={\frac {1}{2}}D(P\parallel M)+{\frac {1}{2}}D(Q\parallel M)$

其中

$M={\frac {1}{2}}(P+Q)$ $Kullback–Leibler divergence 为 {\displaystyle D(P\parallel Q)}$

3. 具体的应用

计算多元高斯分布之间的距离，文档之间的距离(不是cos，因此cos假设的文档满足的分布并不清晰，而JS－divergence则需要满足multinomial分布)

Beyond Cosine Similarity

4. wiki的解释
罗韵初入职场
0
举报回复
理由

举报取消

这里有一篇衡量两个图片相似性的文章：

https://mp.weixin.qq.com/s?__biz=MzA3NDU3MTc1Ng==&mid=2651165921&idx=1&sn=459c6b8e230221484610e09ff90f3c14

数据挖掘和图像分析我都做过，这个相似性的文章虽然说的是图像领域的，但是对于所有相似性的衡量都非常有启发。

———————————————————————————————————-

P.S. 组织了一个计算机视觉的开发者交流微信群，目标是汇集【计算机视觉，图像处理，3D图像，视频处理，深度学习，机器学习】的开发者，一起分享开发经验，共同探讨技术，有兴趣入群的可以加我微信（WeChat: LaurenLuoYun），请注明“姓名-公司/学校-技术方向”，谢谢。
匿名用户管理大师
0
举报回复
理由

举报取消

K-L Divergence实际上并不是一个真正的距离度量，因为它不满足距离定义中的对称性、三角不等式等性质。题主可以参考一下目前学界比较火的信息几何学( Information Geometry)，这一学科将概率分布处理为流形上的点，然后利用流形上的测地线来表征不同分布之间的距离。这一测地距离叫做Fisher Information Distance，是一个真正的距离度量，相比K-L散度更为精准，但由于涉及到变分问题的求解，计算量也非常巨大。

目前信息几何方兴未艾，但仅仅引入了微分几何的一些基本概念，更深一层的东西比如李群、纤维丛在其中如何体现还有待研究，个人感觉是未来发展潜力巨大的一门学科。
曲晓峰初入职场
0
举报回复
理由

举报取消

Metric Learning （度量学习）应该是回答这个问题的关键点。

度量学习要解决的基本问题，就是欧式距离的问题。但就像题主所说，不同维度的权重、不同特征的相关性、数据点的空间分布，有着种种不同。都按照一个僵硬的标准来统计距离实在是不科学的。

而度量学习，就是学习一种映射（或者说是一种距离的度量方法，又或者说寻找一个新的空间及对应的投影方法），在该映射下，可以达到期望的功能。而这个功能，根据问题的不同，自然有不同的定义方式。所以度量学习，基本就是定义一个优化问题，如何从数据中学习一个距离计算的方法，让这个距离计算的方法最为符合期望的目的。

度量学习的具体方法很多，可以参考如下 survey：

Distance Metric Learning: A Comprehensive Survey (2006) by Liu Yang

A Survey on Metric Learning for Feature Vectors and Structured Data (2014) by Aurélien Bellet, Amaury Habrard, Marc Sebban

一篇师弟一作的文章，写得比较详细：【技术】相似性度量学习及其在计算机视觉中的应用
Eastdog 初入职场
0
举报回复
理由

举报取消

KL距离，计算的时候设计好基准，因为XY的KL距离和YX的KL距离是不一样的。
jz wang 管理专家
0
举报回复
理由

举报取消

好像好多人都说了KL divergence，就不仔细说了，补两个：

1, Hellinger Distance:

Hellinger distance

好处是可以bound TVD(total variation distance)，而且一些标准的分布之间有closed form表达式。

具体的东西《Testing Statistical Hypotheses》这本书里有。

2. Information Distance:

Information distance

其中一个好处是比Hellinger Distance的bound更紧。其他的好处只能对应问题对应说了。比如可以用一个已知的process去fake一个brownian motion.