彈力理論傳播的半監督學習新方法*

劉瑩瑩，王士同

1.江南大學 數字媒體學院，江蘇 無錫 214122

2.江南大學 江蘇省媒體設計與軟件技術重點實驗室，江蘇 無錫 214122

1 引言

許多實際的工作中，例如對象識別、多媒體檢索和文本分類等任務，標記的示例通常是少量的且需要花費昂貴的代價才能獲取，但大量的未標記的示例又是可以利用的。雖然這些大量的未標記示例沒有標簽，但它們可能提供了數據分布的先驗信息，使其在標記示例很少的情況下能夠進行準確的分類。半監督學習（semi-supervised learning，SSL）[1-4]就是這樣的一種學習策略，目的是利用這些大量的未標記示例來提高學習性能。SSL 已經被許多研究者從不同的角度進行了深入的研究。眾所周知，SSL 算法應該在正確的假設下進行，否則未標記的示例可能會顯著影響其性能。通常情況基于圖形的SSL 算法使用的兩個基本假設是聚類假設和流形假設[5]，大多數流行的SSL 算法也都是基于這兩個假設之一進行的研究[6-7]。

本文目標是基于流形假設的前提下設計一種新的基于圖形的SSL 算法。與現有的基于圖形的直接從統計學中推導出來的線性近鄰傳遞（linear neighborhood propagation，LNP）[8]算法不同，本文結合物理學中彈性力理論提出了一種新的SSL 標簽傳播方案——基于彈力理論傳播的半監督學習新方法（novel semi-supervised learning method by elastic-force theory based propagation，EFTP）。EFTP 算法一方面模擬了節點之間的作用力，使得標記節點的標簽在傳播中擴散。把標記節點可以看作是標簽信息高度集中的擴散源，表現在彈力理論中就是標記節點對未標記節點的彈力很大，而對于未標記節點來說它對于其他節點的彈力幾乎為0。當擴散過程開始時，標簽信息將從標記節點轉移到剩余的未標記節點。當傳播過程完成后，圖中所有的節點都會得到一定量的標簽信息，為最終的分類提供基礎。另一方面考慮到不同節點被其他節點同化和同化其他節點的能力是不同的，使得EFTP 算法比菲克定律協助傳播（Fick's law assisted propagation，FLAP）[9]算法更加逼真。在EFTP 算法中，一個示例接收或者傳輸標簽信息的時間和數量和應該將這些標簽傳播到哪里，都直接受彈力理論的約束。

本文主要專注于設計彈力理論傳播的半監督學習新算法。在人造數據集、圖像以及真實數據集上進行實驗，EFTP 方法都獲得了比LNP、FLAP 更好的效果。

2 理論基礎

2.1 相關介紹

半監督學習算法的目標是將標記節點的信息傳到未標記節點中去，在本文中用如下符號表示：一組標記節點記作，一組未標記的節點記作，xi∈Rm,1 ≤i≤n(n=p+w)且都是從未知的邊際分布中取樣，1 ≤i≤p，yi從{-1,1}中取值，目的是將標簽信息從P傳播到W。文獻[10]中開發了局部學習穩定器來預測每個樣本標簽來自其鄰居的標簽。文獻[8]中提出了線性鄰域傳播（LNP），即假設圖上的每一個例子都可以由其鄰域進行最優重構。這些算法通常假設鄰居對于測試示例的標簽是確定的。文獻[9]中提出了菲克定律協助傳播（FLAP），模擬流體的擴散進行標簽傳播，設定流體分子的同化與被同化能力是相等的。然而，這些算法中假設并不總是適用于各種數據分布，因此上述方法有時可能會得到不滿意的結果。

本文對SSL 方法進行探索，從一個新的角度研究傳播的過程。傳播是社會生活中一種很常見的現象，舉個很常見的例子：在人口遷移中，起初每個人都居住在自己的領域，但是在個人因素和社會因素共同作用下，人們會選擇遷徙。這個過程中，人口遷移可以看成是由一系列的“力”引起的。這就是社會學中的著名的人口遷移推拉力模型（參見文獻[11-12]）。當然，由于個體的差異性，一個區域對個體的排斥力和吸引力參數都是不同的。這就可以類比成在實際工作中每個節點它的同化與被同化的系數是不一樣的。可以把此現象看成人口的流動傳播。除此之外，很多社會學家還為推拉理論引入很多量化模型。例如文獻[13]把物理學中的重力模型以及統計學中馬爾科夫鏈模型引入遷移理論。目的就是為了使人口遷移的定量分析成為可能。受這種想法的啟發，利用彈力模型，使得本文的傳播算法更具有兼容性，讓本文的標簽傳播在處理多種數據分布的數據集時更具有魯棒性。下面將介紹本文所提出的SSL模型——彈力模型。

2.2 彈力模型

自然界中每個物體在外力作用下都會發生形變。如果撤回這些外力，物體就會恢復原來狀態，把這些外力稱作“彈力”。在彈性限度內，彈簧發生彈性形變時，彈力的大小跟彈簧形變量成正比。具體表達式如下：

其中，Δx表示彈簧的形變量，k稱為彈簧的倔強系數（也稱作勁度系數或彈性系數），大小與其自身的性質有關。如彈力理論所描述的形式一樣，現在把彈簧形變量Δx類比成標簽信息量在節點之間的擴散距離d。倔強系數k大小在本文中除了與節點之間傳播時單個節點的輸入系數λ1和輸出系數γ1有關之外，還與當前時刻互相傳播的兩個節點標簽數值有一定關系。后期會對這兩個參數進行適當調整來實現滿意的分類結果。因此，在標簽傳播和力學中彈力理論之間畫一個平行關系是很自然的。接下來詳細解說節點之間的傳播。類比圖如圖1 所示。

從圖1 可以看出標簽信息在節點之間的傳播過程和結果。顏色偏重的圓類比于較多標簽信息的示例。同理具有較少標簽信息的示例，則用顏色偏淡的圓來類比。以xw節點為例來分析傳播過程。圖1中藍色箭頭和綠色箭頭分別代表其他節點中的標簽信息流向節點xw的過程和節點xw傳播自己的標簽信息的過程。顏色較重的圖形傳播的標簽信息較多，用重色箭頭表示；顏色較淺的圖形傳播的標簽信息較少，用淡色箭頭表示。在綜合輸入輸出圖之后，畫出了最后標簽信息的流向用紅色箭頭表示。紅色箭頭顯示的是xw與外界所有節點標簽交流之后的合力方向，也就是標簽傳播總方向。自然的，設?v∈{1,2,…,n}，可以用如下彈力模型公式解釋標簽傳播過程：

Fig.1 Elastic force mode圖1 彈力模型

這里設置λ1是xw被其他節點傳播的系數，形象地說是輸入系數。γ1是xw節點對其他節點的同化能力系數，也是其輸出系數。除此之外，定義節點xw在t時刻的軟標簽為。這里軟標簽意味著l從一個實際范圍[-1,1]中取一個值，借助式（1）、式（2）可以變成如下表達式：

式（3）意味著xw在擴散距離dvw=exp(-‖xv-xw‖2/(2σ2))上將其標簽信息傳播到其他節點和接收其他節點的標簽信息。根據牛頓第二定律，粒子運動的加速度等于作用力與粒子質量的比值：

在時間Δt內標簽信息的傳播距離S有如下表達式：

因此過Δt時間后，結合式（4）、式（5），xw節點在Δt時間段內將標簽信息在擴散的過程中散布了一個路徑的總信息量。可以得到如下表達式：

式（4）、式（5）中的Δt、m可以簡單地設為1，同時令2-1λ1=λ,2-1γ1=γ，為了后續證明，這里令λ1=γ1μ。結合式（3）、式（4）、式（5）、式（6），整個數據集的傳播過程用如下式子表達：

考慮到xw的初始狀態，式（7）可以變換為：

如果xw分別是一個正的、負的或未標記的例子，那么分別取1，-1 或0。α∈(0,1)是xw從外界接收到的信息以及輸出去的標簽信息和xw的初始狀態之間的平衡系數。式（8）模擬了節點之間的標簽傳播過程。與最初的彈力定律稍有不同，在實際任務中，如圖1 所示xw除了接收其他節點的傳播信息之外，同時它也在向其他節點傳輸標簽信息。換句話說，一個節點從數據集中的所有其他節點接收標簽信息能力系數和其輸出系數是不同的。

式（8）說明數據集中一個節點與另一個節點之間的傳播過程，表示未標記節點的接收標簽信息可以理解為其他節點發出的信息的集成。

根據前面的介紹，在半監督學習中，將彈力模型應用于無標記和有標記的節點。EFTP 算法允許任意兩個節點之間的標簽信息交換，而不考慮它們當前的標簽值。因此，在傳播過程中可以更改節點的標簽。幸運的是，文獻[9]中定理1 表明被標記的示例的標簽在迭代過程之后不會改變，也就意味著被標記示例的原始標簽，即1 或-1，不會從1 轉成-1。

定理1 被標記節點的標簽在迭代過程之后不會改變。

3 彈性理論傳播算法

3.1 算法傳播進程介紹

彈力理論傳播的半監督學習新方法需要對樣本中的每個節點進行傳播，隨著時間的推移，越來越多的節點加入傳播行列，進行反復迭代計算，直至收斂。在傳播過程中同時更新所有示例的標簽，用標簽向量來表示，初始狀態用向量y=(y1y2…yn)T來表示。各個示例的標簽值用如下公式表示：

把迭代矩陣D定義為：

由式（9）可知，一個示例的標簽是其初始狀態與包括其自身在內的所有示例標簽的線性組合。迭代計算式（9）直到其收斂，收斂判定由如下公式表示：

式中，δ是預定義的一個極小的正數。通過迭代過程可得到收斂向量L*。給定一個硬閾值0，若則確定xw為正（是L*向量中的第w個元素），否則為負數。

雖然式（9）是為二元分類推導出來的，但是可以通過將標簽向量L和初始狀態向量y替換為標簽向量矩陣L和初始狀態矩陣Y，式（9）可以直接擴展到多類分類。具體表達式如下：

式（12）中矩陣L和Y的規格是n×m，m表示類別的總數。若xw被標記，則yw=m1那么。反之如果xw沒有標記，那么=0 (1 ≤m1≤m)，最后xw屬于種類。

由文獻[14-15]中定理2 可知式（12）以線性速率收斂。定理2 的內容直接適用于式（9）。

定理2 由式（12）生成的序列{L(t)},t=1,2,…最終收斂到如下式子：

此時也對標簽傳播的停止準則進行了相應的修改：

這里‖· ‖L表示范數。因為式（12）是一個根據示例之間的相似性傳遞標簽信息的傳播算法，所以它可以處理任何類型的數據分布。此外，EFTP 是一種基于圖形的算法，可以有效地利用隱藏在數據集中的流形結構[16-17]，因此它總能得到滿意的分類結果。

3.2 算法收斂性證明

為了直觀地比較EFTP、FLAP、LNP，并顯示其優越性，在經典正則化理論背景下重新構造了EFTP 算法，具體表達式如下：

式中，Dkj是矩陣D中的第(k,j)個元素。式（15）右側的第一項形成了特定的先驗知識，使示例標簽在L中平穩變化。這表明類似示例的軟標簽之間不應該有太大的差別。第二個擬合項表示所確定的標簽應與示例原始標簽狀態保持一致。而正則化參數φ＞0控制平滑項和擬合項之間的權衡。

定理3 正則式(15)是一個凸優化問題。

證明Q(L)對L進行求導的過程步驟如下：

在式（17）中Q(L)對L求導后變成如下形式：

將式（17）右邊設為0，因此式（18）可以被重新表述如下：

變形得到與式（13）相同的閉合式，表達式如下：

因此式（15）是式（9）的迭代結果，在式（15）中迭代矩陣D可變換成如下形式：

為了保證D是非負隨機矩陣以及D1每行和為1，設置。

從文獻[14]中的Gerschgorin 圓定理得到D1所有特征值都在范圍內，這表明D1是正定矩陣。

而對于對角矩陣D2其特征值就是對角線，為使得其為正定矩陣設置u＞1。

根據正定矩陣的性質可知正定矩陣的和仍是正定矩陣。由此可以證明本文的迭代矩陣D也是正定矩陣。因此，式（15）是凸優化問題，收斂結果也是全局的最優的。 □

定理3 表明，EFTP 算法式（15）的收斂點對應全局最優解。這些處理方式差異使得EFTP的收斂精度更高。至此以上內容即為本文所提算法的主要內容。

4 實驗分析

本章采用不同形狀的人造數據、圖像數據以及真實數據分別對EFTP、LNP、FLAP 算法進行評估。重點討論這三個算法中的兩個問題：（1）對每個數據集只給出很少的標記示例的情況下，算法對未標記示例的分類精度；（2）算法的穩定性。實驗軟硬件環境為Intel Corei3-2130 3.4 GHz CPU，4.0 GB RAM，Windows 7，Matlab R2016b。

4.1 參數設置和評價標準

本節將說明實驗中的參數設置情況和使用的評價標準。

兩個參數k、u是EFTP 算法獲得令人滿意結果的關鍵。k控制一個既定的稀疏圖，u在平衡算法準確性和穩定性中起著重要的作用。

u選擇：u對EFTP 算法性能的影響是雙重的。直觀上，從式（3）觀察到u代表從xv同化xw的效果，xv同化xw的概率越大，u的值就越大，xw的標簽就越容易受到xv的影響。并且在第3 章中證明此算法的收斂性是在u>1 的情況下。但是u的取值并不是無限大，因為在一個數據集之中不同類的數據可能會相似，所以u的取值要在一定的范圍內。同時為了此算法可以適用于大樣本高維的數據集，對數據集選取一定的代表點以此來反映數據集的整體情況。在這種情況下用文獻[18]中的參數尋優方法找到合適的u。利用最優的u帶入到原數據集中得到最高的分類精度。

簡而言之，u>1 會收斂，在保證收斂的情況下，趨于無限大時或者取值太小都會降低算法穩定性和精度。因此，u的選擇應該在保證其準確性和穩定性前提下作一個適中的權衡。下面的參數敏感性實驗信息圖將闡述這一點。在Wine 數據集中通過固定L=18，EFTP 的精度和穩定性的變化如圖2（a）和圖2（b）。顯然在Wine 數據集里，設置u=1.4 精度相對較高，該設置下的穩定性也是可以接受的。

Fig.2 Sensitivity test analysis diagram of parameter u圖2 參數u 的敏感性實驗分析圖

k選擇：一個合適的圖形對提高算法性能非常重要，k是決定已建立圖的鄰域數目和稀疏性的一個關鍵參數。在DS1、DS2、DS3、DS4 數據集上讓k從小到大取值。一般情況下，如果圖太稀疏（例如k=2），EFTP 達不到令人滿意的性能。然而，當k在某值（k=6）左右取值時，EFTP 分類性能就是正常的，效果令人滿意。綜合實驗表明k的選擇對穩定性和精度影響不大，很容易調優。具體參數敏感性實驗分析如圖3 所示。

Fig.3 Sensitivity test analysis diagram of parameter k圖3 參數k 的敏感性實驗分析圖

為了公平比較，下列所有實驗中EFTP 參數設置為a=0.99,，η設置在[0,1]內。在FLAP 中a也設置為0.99。為所有算法構造了相同的K近鄰（K-NN）圖。σ、u在不同數據集中會進行相應調整，以達到最佳性能。

采 用NMI（normal mutual information）、RI（rand index）[19]指標對算法進行評估。NMI 與RI 的定義如下：

首先給出包含n個對象的數據集，X定義了已知標簽的原始數據，Y定義了對已知標簽原始數據的聚類效果，a定義了X、Y任意兩個具有相同類標簽并且屬于同一個樣本的個數，b定義了X、Y中任意兩個具有不同標簽并且屬于不同類樣本的個數。兩種指標對算法進行評估，指標越高，說明聚類效果越好。

4.2 人造數據集實驗

本節使用人造平面數據集DS1、DS2、DS3、DS4將EFTP、FLAP 以及LNP 三種算法的傳播過程可視化，以此來進行三種算法的驗證和比較。由于LNP與FLAP 算法的分類效果相近，限于篇幅，LNP 的分類效果可視圖不再給出。算法中所用到的四個數據集為了在精度和穩定性上形成對比，都采用了較多數據點。除此之外，為了證明EFTP 算法的魯棒性，本節的數據集的選取也具有不同的類別形式，數據量由簡單到復雜，覆蓋面較為廣泛，具體信息如表1所示。

Table 1 Synthetic datasets表1 人造數據集

DS1、DS2 數據集與使用雙月數據集進行實驗的文獻[7]和文獻[20]相比，減少了類間距離。分別讓兩個類盡可能地鑲嵌與靠近，使月、正方、圓形態不規則增加分類難度。DS3、DS4 數據樣本量大于10 000的數據集也分別進行EFTP、FLAP、LNP 算法實驗。本節依次在圖4、圖5、圖6、圖7 中給出了其原圖、代表點圖以及運行FLAP 及EFTP 算法后的圖解。

Fig.4 Original graph and experimental graph of DS1圖4 DS1 原圖及實驗圖

Fig.5 Original graph and experimental graph of DS2圖5 DS2 原圖及實驗圖

Fig.6 Original graph and experimental graph of DS3圖6 DS3 原圖及實驗圖

Fig.7 Original graph and experimental graph of DS4圖7 DS4 原圖及實驗圖

從圖4～圖7 中可以看出，相對于FLAP 算法，EFTP 算法對于各種形狀數據集傳播分類的效果都非常好。為了在DS1、DS2、DS3、DS4 數據集上更好地實現分類效果，為EFTP 算法構建了5-NN、6-NN、8-NN 和10-NN 圖。

在運行EFTP 算法時，各數據集的代表點數為525、750、812 和1 250，其傳播分類結果與直接使用FLAP、LNP 算法精確度都有顯著提升。為了進行定量比較，本文通過更多實驗對比三種算法分類精度，具體情況如表2 所示。

在實驗中，由于選標記示例點時存在隨機的情況，則會造成每次實驗結果出現小范圍內波動。為此，實驗數據則選取均值作為數據結果。以上每組實驗所記錄數據都是在運行數十次之后計算均值得到。從實驗數據可以明顯看出，同預想一樣，本文提出的EFTP 算法同FLAP、LNP 算法相比較，在標記示例很少的情況下都能取得較高的精度。當然，隨著標記示例l逐漸增大，算法的分類精度也會相應提高。從以上實驗結果來看，本文算法在精度、穩定性方面都有了很大的提升，完全達到預期目標。

4.3 圖像分割實驗

本文選取4 幅圖像（http://www.eecs.berkeley.edu/Research/Projects/CS/vision/grouping/segbench）用于圖像分割實驗中，名稱分別是Horse、Elephant、Sky、Grassland，每幅圖的分辨率均為320×320 像素。限于版面，本文的示意圖都進行了一定比例的縮放，如圖8 所示。

本節為了說明EFTP 的有效性，與FLAP、LNP 算法分類結果進行對比。4 幅圖的類別數分別為2、2、3、3，圖9、圖10 分別為本文算法和FLAP 算法的圖像分割效果，LNP 與FLAP 的分類效果相似，不再給出。本實驗采用NMI、RI[19]指標進行評估，目的是為了可以定量地分析圖像分割的效果。該指標進行評估之前首先要對像素點劃分類標，方法見文獻[19]。EFTP 算法分別在4 幅圖片上運行10 次，求得平均NMI、RI指標記錄在表3、表4 中。

從實驗結果中可以看出：在Horse、Elephant 中，兩種算法的指標相近，都能有效地分割出目標物體。但是在Sky、Grassland 圖片中，EFTP 明顯優于FLAP、LNP 算法，因此EFTP 更具有實用性。

Table 2 Experimental results on synthetic datasets表2 人造數據集的實驗結果

Fig.8 Images used in segmentation圖8 分割實驗的圖像

4.4 真實數據集

采用4 個UCI（http://archive.ics.uci.edu/ml/datasets.html）數據集Iris、Wine、BreastCancer 以及National Clas-sification of Economic Activities-9 (CNAE-9)來比較EFTP 與FLAP、LNP 算法的分類精度。數據集具體信息如表5 所示。

Table 3 NMI of 3 algorithms on 4 images表3 3 類算法在4 幅圖片上的NMI

Table 4 RI of 3 algorithms on 4 images表4 3 類算法在4 幅圖片上的RI

Fig.9 Segmentation results of EFTP on each image圖9 EFTP 算法在圖像上的分割效果

Table 5 Real datasets表5 真實數據集

本節中對標記集L在不同大小下的分類精度進行了實驗。算法在每個L下獨立實現10次，隨機選取標記示例，表6 列出了10 次運行輸出的精度平均值以及方差。請注意，在生成標記集時，每個類中至少保證有一個標記示例。分別為Iris、Wine、Breast Cancer和CNAE-9 構建了10-NN、6-NN、7-NN 和10-NN 圖。

從表6 可以看出，當L由小變大時，EFTP 一般可以達到比較算法中最高的精度。可以看出，在大多數情況下，EFTP 算法的效果優于FLAP 和LNP 算法。因此本文提出的算法EFTP的結果是滿足期望的。

Fig.10 Segmentation results of FLAP on each image圖10 FLAP 算法在圖像上的分割效果

5 結束語

采用物理力學中彈力基本理論，本文提出了用于SSL 標簽傳播的EFTP 算法。EFTP 也可以在傳統正則化理論的背景下推導出來，將EFTP 算法與已有的算法相聯系，意味著EFTP 的收斂點是全局最優的。同時也證明了參數u在決定分類性能和穩定性方面扮演了重要的角色。綜合實驗結果表明，與FLAP、LNP 算法相比，EFTP 具有很大優勢。

與大多數標簽傳播算法相似，直接將EFTP 應用于大數據問題在計算上并不容易，這是因為圖結構的復雜度是O(n3)。然而，超圖技術的最新發展，如文獻[21]和文獻[22]，可以解決這個問題。并且EFTP 算法所提出的模型在u＞1 情況下進行，u＜1 是否依舊收斂找到優解是今后擬探討的課題。

Table 6 Experimental results on real datasets表6 真實數據集的實驗結果