分布的相似度（距離）用什麼模型比較好？

11-23

如果在處理的數據中，有的是分布：比如工廠內分貝值的分布，或者電機轉速的分布。
一般一個分布（一維的）就是一個向量，滿足每一個維度都大於0且L^1(V)=1，平時我們也直接當成向量進行處理，求歐氏距離，但是覺得這樣做並不科學，因為作為向量就默認了「維度」這一坐標是沒有意義的，可是實際上，分布里的橫坐標有著很實際的意義，比如分貝或者轉速。請問用什麼方法可以更好地衡量兩個分布之間的相似度（或者距離）？

用什麼距離取決於你關心什麼類型的差別。舉幾個例子。

1. Kullback-Leibler divergence
對於兩個分布 $p(x)$ 和 $q(x)$ ，KL散度定義為 $D_{KL}(p|q)=int_xp(x)lnfrac{p(x)}{q(x)},mathrm{d}x$ 。可以看出，如果要 $D_{KL}(p|q)$ 小，那麼 $p(x)$ 大的地方 $q(x)$ 必須要大（否則 $p(x)/q(x)$ 會很大）；而在 $p(x)$ 小的地方，KL-divergence 的值對 $q(x)$ 的大小就沒那麼敏感。相應地，如果要 $D_{KL}(q|p)$ 小，那麼 $p(x)$ 小的地方 $q(x)$ 必須也要小；而在 $p(x)$ 大的地方，同樣地，KL-divergence 的值對 $q(x)$ 的大小也沒那麼敏感。

下圖來自 Machine Learning: A Probabilistic Perspective p734，演示了上述兩種情況。圖中 $p$ （藍色）是一個二分量的高斯混合分布， $q$ （紅色）是最小化 $D_{KL}(p|q)$ （圖a）或 $D_{KL}(q|p)$ （圖b-c）的高斯分布。感受一下區別。

下圖來自 Information Retrieval Perspective to Nonlinear Dimensionality Reduction for Data Visualization 的圖2。作者在裡面提出了一種非線性降維演算法，目標函數（差不多）是兩個方向的 KL-divergence 的加權平均。調整這個權值的話，三維球面上的點在二維平面上的降維結果會從A變化到B。這也是類似的原理。

2. 其他 f-divergence
KL-divergence 的壞處在於它是無界的。事實上KL-divergence 屬於更廣泛的 f-divergence 中的一種。一般性的 f-divergence 定義為 $D_{f}(p|q)=int_xq(x)fleft(frac{p(x)}{q(x)} ight),mathrm{d}x$ ，如果取 $f(t)=tlog t$ 或者 $f(t)=-log t$ 就能得到KL-divergence。除了KL-divergence，常用的 f-divergence 有 Hellinger distance、total variation distance 等等。這兩種 f-divergence 都是有界並且對稱的。

3. Wasserstein distance
只討論最簡單的一種情形，一般情形見維基鏈接。定義 $W_2(p,q)=sqrt{min_{P_{XY}}E_{P_{XY}}left[|x-y|_2^2 ight]} mathrm{s.t.} P_Xsim p,P_Ysim q$ ，也就是說，對任意邊緣分布為 $p$ 和 $q$ 的聯合分布 $P_{XY}$ ，我們可以求出 $E_{P_{XY}}left[|x-y|_2^2 ight]$ ，而 $p$ 和 $q$ 的 Wasserstein distance 則定義為當 $P_{XY}$ 取遍可能的分布時，這個期望的最小值的平方根。

Wasserstein distance 衡量了把數據從分布 $p$ 「移動成」分布 $q$ 時所需要移動的平均距離的最小值（類似於把一堆土從一個形狀移動到另一個形狀所需要做的功的最小值）。下圖出自 Principal Differences Analysis: Interpretable Characterization of Differences between Distributions 的圖S2。文章目的是找出能解釋兩個維數一樣的總體分布不同的最小特徵集。他們找了個例子，說明有時候使用 Wasserstein distance 來刻畫分布之間的不同是必要的：右邊的那個 gene expression 的分布，看上去十分像是把左邊那個分布往上擠了之後的結果。所以如果要刻畫這種「原因」導致的區別，用 Wasserstein distance 比其他要更合理。

4. 其他。見 Statistical distance。還是那句話：先問自己關心分布之間怎樣的不同，有沒有什麼特殊約束或要求，再據此作相應的選擇。至於題主的例子……我不太清楚「分布里的橫坐標有著很實際的意義，比如分貝或者轉速」這句話對「衡量兩個分布之間的相似度（或者距離）」有著什麼樣的具體約束。題主可以先釐清一下。

是時候放大招了，今天我要談談什麼是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) http://arxiv.org/abs/1510.00012

2. aggregated Wasserstein distance + HMM （ECCV 2016）https://arxiv.org/abs/1608.01747

3. 據我所知，第三個快速計算Wasserstein loss minimization的通用優化框架（前兩個是Sinkhorn和Bregman ADMM），利用了一個上古時代的思想（模擬退火）(ICML 2017) http://arxiv.org/abs/1608.03859

首先，向量也可以認為有多個維度，每一個向量的元素對應一維。
其次，參考其他答案，你可以根據需求選擇多種相似度，推薦先用 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.

寫過一篇關於 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 散度（從動力系統到推薦系統）

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之間是很容易進行比較的
公式如下：
${{ m {JSD}}}(Pparallel Q)={frac {1}{2}}D(Pparallel M)+{frac {1}{2}}D(Qparallel M)$
其中
$M={frac {1}{2}}(P+Q)$ $Kullback–Leibler divergence 為 {displaystyle D(Pparallel Q)}$

3. 具體的應用
計算多元高斯分布之間的距離，文檔之間的距離(不是cos，因此cos假設的文檔滿足的分布並不清晰，而JS－divergence則需要滿足multinomial分布)
Beyond Cosine Similarity

4. wiki的解釋
https://en.wikipedia.org/wiki/Jensen%E2%80%93Shannon_divergence

一直在用最大均值差異MMD：maximum mean discrepancy：http://alex.smola.org/teaching/iconip2006/iconip_3.pdf

好像好多人都說了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.

K-L Divergence實際上並不是一個真正的距離度量，因為它不滿足距離定義中的對稱性、三角不等式等性質。題主可以參考一下目前學界比較火的信息幾何學( Information Geometry)，這一學科將概率分布處理為流形上的點，然後利用流形上的測地線來表徵不同分布之間的距離。這一測地距離叫做Fisher Information Distance，是一個真正的距離度量，相比K-L散度更為精準，但由於涉及到變分問題的求解，計算量也非常巨大。
目前信息幾何方興未艾，但僅僅引入了微分幾何的一些基本概念，更深一層的東西比如李群、纖維叢在其中如何體現還有待研究，個人感覺是未來發展潛力巨大的一門學科。

這裡有一篇衡量兩個圖片相似性的文章：
https://mp.weixin.qq.com/s?__biz=MzA3NDU3MTc1Ng==mid=2651165921idx=1sn=459c6b8e230221484610e09ff90f3c14
數據挖掘和圖像分析我都做過，這個相似性的文章雖然說的是圖像領域的，但是對於所有相似性的衡量都非常有啟發。

----------------------------------------------------------------------------------------------------------

P.S. 組織了一個計算機視覺的開發者交流微信群，目標是彙集【計算機視覺，圖像處理，3D圖像，視頻處理，深度學習，機器學習】的開發者，一起分享開發經驗，共同探討技術，有興趣入群的可以加我微信（WeChat: LaurenLuoYun），請註明「姓名-公司/學校-技術方向」，謝謝。

題主的數據是一維的，而且不知道具體的分布形式，不一定是高斯，當然如果是高斯就更簡單。
我覺得用Non-parametric的方法很好啊，用density estimation估計下分布，然後算下overlapping不就行了。overlap越大越相似，越小越不同。分布估計得準確的話，就是很tight的bayes error的bound了。

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

一篇師弟一作的文章，寫得比較詳細：【技術】相似性度量學習及其在計算機視覺中的應用 https://mp.weixin.qq.com/s?__biz=MzA3NDU3MTc1Ng==mid=2651165921idx=1sn=459c6b8e230221484610e09ff90f3c14scene=1srcid=0824lN4DXcF0blVN3kgjTdJ2key=cf237d7ae24775e8542a87961bf0c01a60239e8399a8904666170eb0f3aa51af458ba0ff424caaf6e0fef7aa63596398ascene=0uin=NDk3MDc4OTAydevicetype=iMac+MacBookPro12%2C1+OSX+OSX+10.10.5+build(14F1713)version=11020201pass_ticket=GXHYYAW4CxN9J1MBdBsFSiiKwHgronQ0gbjJ4ra3kZft5h815vGx1wShWnl7KaQV

KL距離，計算的時候設計好基準，因為XY的KL距離和YX的KL距離是不一樣的。

我的理解是，求兩個或者多個形如 [1,3,4,5,0] 之類的vector的similarity。可以選擇的方法很多，關鍵看樓主的關於「好」的標準是什麼。

如樓主所言，其實，在很多case中，橫坐標可能有重要的物理，金融或者商業意義。所以，衡量「好」的時候，必須要對其背景知識有理解才行。比如，發動機轉速在3000-5000轉可能是正常，過了8000可能就不正常；因此每個element的權重很可能不同。另外，某些值向某個方向變化可能正常，而向另外方向的變化可能是指示重大不同。

如果缺少背景知識，很難給出所謂的「好」的方法。對於1 dimentional sequence，可以用做similarity比較的方法也很多，歐式距離，weighted歐式距離，變異罰分，相關性比較等等，在bioinformatics和search engine等很多領域都有應用。

建議先了解更多的需求背景知識，定義「好」的標準，再由易到難嘗試各種方法的效果。從engineering和business的角度來看，簡單好用是王道，複雜花哨的數學工具在一些特定場合不一定真的好用。

GAN模型-分析角度 - 知乎專欄分析了幾種度量

Don"t use KL divergence, which is very sensitive, two arbitrarily close (w.r.t other metric) distributions can have arbitrarily large KL divergence.