「emd」EMD - seo实验室

emd

EMD算法简介

该部分引用自[1]

Earth Mover’s distance (EMD)，和欧氏距离一样，他们都是一种距离度量的定义，可以用来测量某分布之间的距离。EMD主要应用在图像处理和语音信号处理领域。

EMD问题如下图所示

给定两个签名(或者叫分布、特征量集合)P和Q，P为m个特征量Pi和其权重wPi的集合，记作P={(P1,wP1),(P2,wP2),...(Pm,wPm)}，如图左侧部分。同样的，还有一个分布Q，Q=(Q1,wQ1),(Q2,wQ2),...(Qn,wQn)，即上图右侧部分。在计算这个这两个签名的Earth Mover's Distance(EMD)前，我们要先定义好P、Q中任意取一个特征量( Pi and Qj )之间的距离（这个距离叫ground distance，两个签名之间EMD依赖于签名中特征量之间的ground distance）。当这两个特征量是向量时得到的是欧式距离，当这两个特征量是概率分布时得到的是相对熵(KL距离/Kullback–Leibler pergence)。现在，给定两个签名(P和Q)，只要计算好每两个特征量之间的距离，系统就能给出这两个签名之间的距离了。

EMD 实际上是线性规划中运输问题的最优解。首先，简要描述下运输问题。我们假设这个例子是从多个工厂运输货物到多个仓库。在上图左侧，P从在P1 到 Pm代表m座工厂，工厂Pi有重量为wPi的货物。在上图右侧，Q从Q1到Qn代表n个仓库，仓库Qj最大容量为wQj。货物之间没有什么区别，都是同一类东西。每个仓库都希望装尽可能多的货物。如何尽可能高效把所有货物(实际上不一定是所有货物，部分也OK)从P运送到Q，就是运输问题的优化目标。在本例中，P、Q都是离散的，那么EMD可以用运输问题的Hungarian算法来计算它们之间的距离。挖个坑而已，这里不具体讨论。

这里定义，货物从工厂Pi运到仓库Qj，距离是，运送货物的重量为。这样一次运输需要的工作量为∗。显然，距离越远、或货物越重，工作量就越大。(注：运输可能是多对多的，即一个工厂运输货物到多个仓库，或者一个仓库接收多个工厂的货物。)货物从工厂运到仓库需要很多次这样的运输，经过一些计算和优化，这时我们得到了工作量总和的最小值W。

W =

距离是事先定义的，所以运输量fij是式中唯一的变量，对作如下4个约束：

(1) 运输过程从工厂P到仓库Q，不能反向。

≥ 0 (1≤i≤m,1≤j≤n)

(2) 从工厂Pi一次次运出去的所有货物重量的和不可能超过该工厂中所有货物的总重量wPi

≤ wPi (1≤i≤m)

(3) 仓库Qj接收的所有货物总重量不可能超过其总容量wQj。

≤ wQj (1≤j≤n)

(4) 总运输量的上限是工厂中货物总重、仓库总容量中的最小值。

当仓库的总容量和工厂货物总重不一样时，我们才需要上述第4个限制条件。仓库总容量比货物总量大的话就可以全部运输了，所以这时候呢，运输量的上限就是货物总量。但如果货物总量比仓库总容量大的话，就不能全部运输了，这时候，运输量的上限就是仓库的总容量啦。方便起见，本例中当仓库的总容量和工厂货物总重是一样的。

运输问题的具体解答此处省略不讨论，假设这个时候我们已经得到了最优解。为了使EMD不会随着总运输量的变化而变化，每一次的运输量还要除以总运输量，以达到归一化的目的。（in order to avoid favoring smaller signatures in the case of partial matching.）在后面的具体例子中会对它进行详细描述。

很自然可以想到，给定两个签名，把一个变成另一个所需要的最小工作量，就是EMD对距离的定义，这里的「工作量」要基于用户对ground distance的定义，即特征量之间的距离的定义。然而，当特征量非常多的时候，由于要做一一匹配，其计算量是非常大的。因此，有人提出了一种将多个特征量组合起来做向量量化编码(vector Quantization)后再组成签名的方法。

EMD算法在自然语言处理领域的应用

通过词嵌入（word embedding），我们可以得到词语的分布式低维实数向量表示，我们可以计算词语之间的距离，即我们可以得到dij，因此可以将EMD引入自然语言处理领域。

Matt等人[2]将词嵌入与EMD相联系，用来度量文档距离。提出了WMD（word mover’s distance）算法，以及WCD（word centroid distance）、RWMD（relaxed word mover’s distance）两种牺牲精度降低复杂度的算法。

如何将一个文档变为分布P这种形式？

用归一化的词袋模型（nBOW， normalized bag-of-words）表示。其中P1表示词语，用计算该词的权重，其中表示词语i在文档中出现了次，P1的特征量用该词语的词向量表示。一个nBOW文档向量是比较稀疏的，因为大部分的词语不会出现在该文档中，且在生成文档向量时，去掉的停用词。用欧式距离计算词语与词语之间的距离。