分布數(shù)據(jù)缺失的最優(yōu)傳輸研究*

阮一鳴， 楊建斌

(河海大學 理學院,江蘇 南京 211100)

1 引言

最優(yōu)傳輸本質是刻畫分布與分布之間的最優(yōu)距離,在圖像處理、機器學習和經(jīng)濟學等各個方面都有應用[1-7]. 在實踐中受各種因素的影響,獲取的分布數(shù)據(jù)會出現(xiàn)缺失的情形,例如在圖像處理領域,圖像在存儲過程中由于硬件或軟件的原因會造成像素或灰度值缺失等,此時利用最優(yōu)傳輸理論及其模型會出現(xiàn)求解較為困難且計算結果誤差較大的問題.如何在數(shù)據(jù)缺失情形下得到最優(yōu)傳輸問題的相應結果,同時求解估算缺失的數(shù)據(jù),是最優(yōu)傳輸領域中的一個關鍵問題.

相對于給定的代價函數(shù)，最優(yōu)傳輸問題則是尋求把一種分布轉化為另一種分布的最有效的方式，其主要可分為蒙日(Monge)問題和康塔洛維奇(Kantorovich)問題. 其中蒙日型最優(yōu)傳輸問題的一般形式如下：

考慮X和Y是完備可分的度量空間,給定概率測度μ∈P(X),v∈P(Y),其中P(X)和P(Y)代表X和Y上所有概率測度所構成的空間,給定代價函數(shù)c(x,y)∶X×Y→[0,+∞),蒙日型最優(yōu)傳輸問題則是求解

(1)

T#μ=v為約束條件,T為一個推前算子,由映射T誘導的推前測度T#μ定義為(T#μ)(A)∶=μ(T-1(A)),其中A?Y是任意可測集合. 由于空間∑(μ,v)∶={T∶X→Y|T#μ=v}在弱收斂下不是封閉的，這導致了求解蒙日型最優(yōu)傳輸問題的內(nèi)在困難性[8].

康塔洛維奇則將蒙日問題中的傳輸映射松弛成傳輸方案，即轉換為聯(lián)合概率分布γ(x,y)∈P(X×Y),其邊際概率分布分別為μ(x)和v(y),即滿足

(2)

給定兩個概率測度μ∈P(X)和v∈P(Y)以及相應的代價函數(shù)c(x,y)∶X×Y→[0,+∞)，其中X和Y是完備可分的度量空間，則康塔洛維奇型最優(yōu)傳輸問題則是求解

(3)

其中聯(lián)合概率測度γ屬于傳輸方案空間

(4)

考慮(X,d)為完備可分的度量空間，P(X)為度量空間(X,d)上所有概率測度構成的空間，對任意概率測度μ、v∈P(X)，μ和v的s階Wasserstein距離定義為

(5)

其中，s∈[1,+∞)，Π(μ,v)為對應上述的傳輸方案空間.當s=1時，W(μ,v)稱為EMD距離(Earth Mover′s distance)，即推土機距離或陸地移動距離.康塔洛維奇問題解除完全確定性傳輸?shù)南拗芠4]，其模型更簡捷有效，因此在實際中具有更為廣泛的應用與研究.

近年來，對于最優(yōu)傳輸問題的求解也逐漸成為優(yōu)化領域的一個熱點.但從匈牙利算法[9]和拍賣算法[10]到經(jīng)典的線性規(guī)劃算法[11],均存在較高的時間復雜度，對于大規(guī)模的問題仍具有較大的局限性，而熵正則化算法[12-13]的提出則加速了最優(yōu)傳輸問題的計算求解.本文在模型中加入熵正則項來平滑數(shù)據(jù)缺失的最優(yōu)傳輸問題，提出了一種求解數(shù)據(jù)缺失情形下的最優(yōu)傳輸問題的熵正則化算法，同時將其應用于運輸問題與圖像檢索問題，并給出相應的實例，數(shù)值算例表明了算法對于求解數(shù)據(jù)缺失的最優(yōu)傳輸問題的有效性.

2 數(shù)據(jù)缺失的最優(yōu)傳輸問題

2.1 離散最優(yōu)傳輸問題

考慮如下兩個離散分布：

(6)

給定相應的代價矩陣C=(cij)∈Rn×m,則離散最優(yōu)傳輸問題可描述為

(7)

其中，W(μ,v)即EMD距離,γ為耦合矩陣,γij=γ(xi,yj)為傳輸方案,表示從xi運輸?shù)統(tǒng)j的質量,cij=c(xi,yj)表示xi運輸?shù)統(tǒng)j所花費的代價.pi=p(xi)和qj=q(yj)分別代表分布數(shù)據(jù)xi和yj所對應的概率權重向量.則問題(7)所對應的優(yōu)化模型可表示為

(8)

其中

b=.

2.2 分布數(shù)據(jù)缺失的最優(yōu)傳輸問題

假定離散分布μ對應的點云數(shù)據(jù)已知,分布v對應的點云數(shù)據(jù)有k個數(shù)據(jù)缺失,設缺失的數(shù)據(jù)為y1,y2,…yk，且其所對應的概率權重向量為q1,q2,…qk,此時與經(jīng)典的最優(yōu)傳輸問題相比，目標分布增加了k個自由度,需同時考慮最優(yōu)傳輸方案γ以及對應缺失的數(shù)據(jù)y1,y2,…yk.與問題(7)相比,增加了k個未知量,則此問題可表述為

(9)

則問題(9)所對應的優(yōu)化模型可表示為

(10)

其中，

3 數(shù)據(jù)缺失情形下的最優(yōu)傳輸?shù)那蠼馑惴?/h2>

3.1 熵正則化

(11)

其中，ε表示正則化系數(shù),此時的近似最優(yōu)傳輸問題便成為ε-強凸函數(shù),故其具有唯一解.

3.2 數(shù)據(jù)缺失情形下的最優(yōu)傳輸?shù)那蠼馑惴?/h3>

對于問題(11),可將其等價地轉化為相應的投影問題,且投影度量為KL散度[13],定義為

(12)

(13)

γ=diag(u)Kdiag(v)，

(14)

從而可得本文算法.

1：l=0,v(0)=1m

2：whilel

3:u(l+1)=p./Kv(l)

4：A=KTu(l+1)

8：l=l+1

9：end while

4 實際應用

4.1 基于運輸問題的應用

考慮若干個貨物從倉庫運到工廠,其中X=(x1,x2,…,xn-1,xn)代表n個工廠,工廠xi的需求量為wxi,Y=(y1,y2,…,ym)代表m個倉庫,倉庫yj的儲存量為wyj,貨物從工廠xi運送至倉庫yj的代價為cij=c(xi,yj).若工廠的需求量WX=(wx1,…,wxn-1,wxn)已知,倉庫儲存量WY=(wy1,wy2…,wym-1,wym)有部分數(shù)據(jù)wy1,wy2…,wyk未知,此時運輸問題可表示為基于問題(9)的最優(yōu)傳輸問題，即

(15)

其中γij=γ(xi,yj)代表相應的傳輸方案.下面給出一個實例.

其中缺失的數(shù)據(jù)[wy1,wy2…,wy4]=[107.049 4,18.958 0,19.017 2,159.975 4].

4.2 基于圖像檢索問題的應用

圖像檢索,本質用一個圖片去和數(shù)據(jù)集中的圖片一一匹配,從而檢索出滿足條件的圖片.在2000年Rubner[16]提出EMD距離的定義并將其應用于圖像檢索領域.基于最優(yōu)傳輸理論,圖像檢索通常分為兩步,首先提取圖像的特征從而得到一個高維的直方圖或向量來表示圖像;其次計算兩幅圖像的特征間的EMD距離來度量圖像特征間的相似度.以上方法對于圖像數(shù)據(jù)未缺失的情形具有較好的效果,若待檢索圖片即目標圖片存在部分未知(即圖像特征存在未知或缺失),此時利用上述方法進行處理則較為困難.

考慮圖像為灰度圖像,對于給定的灰度圖像則其對應的直方圖在中的離散分布滿足(6)式.在離散意義下,圖像可看成從圖像中提取的特征直方圖,此時若兩幅圖像直方圖的組數(shù)分別為N和M,直方圖之間的傳輸可用N×M的聯(lián)合概率矩陣γ表示,其中γij=γ(xi,yj)代表對應位置所傳輸?shù)馁|量.假定目標圖片分布直方圖部分缺失即對應圖像特征或灰度值有所缺失,檢索數(shù)據(jù)集圖片直方圖未缺失.給定兩張圖片P和Q,其中P為檢索數(shù)據(jù)集中圖片,Q為目標圖片,則P和Q特征可用灰度直方圖描述.其特征集合：P={(p1,wp1),(p2,wp2),…,(pn,wpn)},Q={(q1,wq1),(q2,wq2),…,(qm,wqm)},其中pi是檢索數(shù)據(jù)集中圖片的第i個特征,qj是目標圖片的第j個特征,wpi是特征pi的權重，即其對應直方圖塊值,設目標圖片特征wqk+1,…,wqm缺失,代價矩陣cij=‖pi-qj‖2.給定分布直方圖缺失的目標圖片與檢索數(shù)據(jù)庫中的圖片,兩張圖片的相似程度則可用EMD距離來衡量，即此圖像特征缺失的圖像檢索問題可轉換為基于問題(9)的最優(yōu)傳輸問題，即

(16)

基于上述理論以及本文算法,需求解圖片直方圖之間的最優(yōu)傳輸方案γ從而求出圖片間的EMD距離.

下面給出一個實例.選取10張256*256圖片構成檢索數(shù)據(jù)集,選取圖片特征數(shù)量為50，即直方圖塊數(shù)量為50,目標圖片為灰度值缺失圖像,特征有20個缺失,其中目標圖片直方圖及其缺失部分與對應特征缺失的目標圖片見圖1,圖片黑色部分為圖像特征缺失部分,檢索數(shù)據(jù)集見圖2.

圖1 目標圖片特征分布直方圖、特征缺失的目標圖片

圖2 檢索數(shù)據(jù)集圖片

設定目標圖片為圖片0，檢索數(shù)據(jù)集圖片為圖片1-10，分別計算圖片0與數(shù)據(jù)集圖片1-10之間的EMD距離見表1.

表1 目標圖片與數(shù)據(jù)集圖片特征分布的距離(20特征缺失)

從表1得到,目標圖片與圖片3的EMD距離為0.008 5,小于與其他圖片的EMD距離，即目標圖片與圖片3最為相似,也與先驗保持一致.

5 結語

探究了分布數(shù)據(jù)缺失情形下的最優(yōu)傳輸問題,給出其基本理論以及對應優(yōu)化模型,針對模型的較大稀疏性，在問題中加入熵正則項來平滑數(shù)據(jù)缺失情形下的最優(yōu)傳輸問題，從而提出了一種數(shù)據(jù)缺失情形下的最優(yōu)傳輸?shù)撵卣齽t化算法,將其應用于運輸問題以及圖像檢索問題,結果驗證了模型及算法的有效性.