基于多注釋器標注下的標簽排序學習方法

陳華燁 汪海濤 姜 瑛 陳 星

(昆明理工大學信息工程與自動化學院 云南 昆明 650500)

0 引 言

近年來，排序學習作為計算機領域內相對較新的研究課題迅速發展。在許多計算機應用中扮演著重要的角色，例如信息檢索、數據挖掘、自然語言處理和語音識別等應用[1]。在有關排序學習的研究中，實例是一組對象，標簽是在實例上應用的排序。通常每個標簽都假定為客觀且可靠的，可用于其他常規監督設置，例如分類[2]。但在現實世界的任務中，生成準確的訓練標簽是很難實現的，或者代價太高。

對于標簽的生成，現有的解決方法是讓各種專家或注釋器提供多個(可能是主觀的或嘈雜的)標簽[3]。例如，AMT(Amazon Mechanical Turk)允許任務發布者雇擁來自世界各地的工作者執行眾包式數據標注。任何AMT工作者都可以根據自己的選擇來完成標簽任務。因此，這使得AMT任務發布者可以輕松快速地雇傭多個標注者。由于AMT工作者在進行標簽任務時有一定的主觀性，所以無法保證客觀準確的標簽。因此，可以基于多個注釋器進行研究學習。目前研究的列表排序學習算法涉及多個注釋器。此外，將有關注釋器的專業知識的信息作為輔助信息，例如：注釋器的信用評分、專業成績、歷史注釋記錄等[4]，運用在標注任務中，作為排序函數的約束函數，得到更精確的標簽。

本文嘗試了一種新的標簽排序方法，結合了兩個經典的概率排序模型[5]，即Mallows模型和Plackett-Luce(P-L)模型。在這個新提出的排序模型中，要學習排序函數、真值標簽、注釋器的專業知識程度的參數，以及關于注釋器的專業知識與其相關輔助信息的自然整合。隨后，列表排序學習的具體算法根據所提出的條件，加入帶有注釋器的輔助信息，進行概率排序。在每個學習算法中，使用最大似然估計方法，并且引入新的期望最大化(EM)程序迭代更新真值標簽、專業知識程度的參數以及要學習的排序函數的參數[6]。具體技術思路如圖1所示。

圖1 技術思路

1 基于概率排序模型的標簽排序學習算法

1.1 Mallows模型

Mallows模型是Mallows在20世紀50年代首次引入的基于距離的概率模型，標準的Mallows模型是屬于指數族的雙參數模型[8]：

(1)

(2)

(3)

對于歸一化常數Z：

(4)

(5)

式中：Θ為注釋器的專業知識程度的參數集，Θ={θ1,θ2,…,θG}∈RG，P(y(i))是先驗的。

(6)

Mallows模型屬于等級聚合模型，該聚合將許多觀察到的不同排名列表，組合在同一組成員上，以推斷出“更好的”排名。所以Mallows模型可以直接擴展到聚合排名中。如果式(5)中的距離是右不變的[9]，則實現如下表達：

(7)

1.2 Plackett-Luce模型

(8)

Mallows模型和P-L模型之間的區別在于前者指的是排序之間的關系，而后者指的是單個排序的概率。

2 列表排序學習

排序學習研究可以分為三類，即逐點、成對和列表[1]。本文通過列表排序學習來定義關于真值標簽排序和預測標簽排序的損失函數，并根據訓練損失最小化來學習排序函數的參數。將所有訓練集的可能性損失之和最小化，似然損失函數定義如下：

l(〈w,x〉〗=wTx,y)=-logP(y|x,w)

(9)

式中：〈w,x〉=wTx=f(x)是具有線性特征的排序函數，P(y|x,w)可以通過P-L模型計算。給定訓練實例x(i)∈X，X為輸入空間，其元素為實例，假設真值標簽y(i)∈Y存在，Y為輸出空間，其元素是X中實例的排名標簽，構造兩者之間的關系：

(10)

式中：w∈Rnf×1是排序函數的參數向量，nx(i)是實例x(i)中的對象數，l、k是計數變量。

這種目標可以直接通過兩個階段策略來實現。應用Mallows模型將注釋器提供的排序標簽融合在一起，以估計注釋器的真實值和專業程度；基于估計的真值標簽訓練排序函數，使用常規排序學習算法來訓練。將這種方法稱為Method1。但這種直接的方法并不穩健，因為如果第一階段估計的真值不好，第二階段就會失敗。所以，可以將這兩個階段整合為一體。

3 一種新的概率排序學習模型

3.1 模型提出

給出一種新的概率排序學習模型，該生成過程可以通過圖2描述。設真值標簽排序y(i)由v(=〈w,x〉)調節，其中v(v>0)是標簽分數的參數化，y(i)的值現在從先前P(y|v)中抽取，實現了以下表達：

(11)

圖2 概率排序模型

3.2 最大似然估計方法

設Ω=(w,Θ)是基于觀測集D的參數的似然函數：

P(y(i)|x(i),w)]

(12)

(13)

參數θ表示注釋器的專業知識程度，在此將引入注釋器的輔助信息，這些輔助信息可以預先獲得[12]，在數學上，輔助信息可以描述為：

θj≤θh

(14)

式(14)表示第j個注釋器比第h個注釋器更專業，標注的準確度越高。將注釋器的輔助信息代入式(13)，即：

(15)

s.t.θj≤θh,j,h∈[1,2，…,G]

在此考慮一個特殊情況：存在一個注釋器具有比其他所有注釋器更高的專業程度。 在不失一般性的情況下，假設第一個注釋器具有最高的專業程度。在此情況下，式(15)可以變為：

(16)

s.t.θ1≤θh,h∈[2,3，…,G]

將式(15)中的約束由S形函數代替：

(17)

式中：η(≥0)表示輔助信息的置信度。若置信度趨于零，則輔助信息失效。若置信度區域正無窮，則置信度相當高，并且可以滿足輔助信息。如果給出置信度，則需等式(15)進行改進，以便通過最大化對數似然來獲得最大似然估計量，即:

(18)

在此將基于注釋器輔助信息的排序學習算法稱為Method3。

3.3 方法推理

(19)

式中：y={y(1),y(2)，…,y(K)}。

E-步驟：該過程計算觀測集D和真值標簽y(i)相對于觀測集D和從中獲得的估計參數集Ω′的對數似然的期望值(E(·))：

Q(Ω,Ω′)=Q(w,Θ;w′,Θ′)=

(20)

根據Method3中注釋器的輔助信息的加入，相應的E-步驟為：

Q(Ω,Ω′)=Q(w,Θ;w′,Θ′)=

lnfη(θ)

為此使用以下引理：

引理1

Q(Ω,Ω(t))=Q(w,Θ;w(t),Θ(t))=

(21)

式中：

(22)

(23)

M-步驟：通過解決式(21)的最大化問題來更新參數集。

引理2對于任何w，通過Θ=(θ1,θ2，…,θG)實現Q乘以Θ的最大化，即：

(24)

引理3對于任何Θ，Q乘以w的最大值等于交叉熵CE(Cross Entropy)，其公式如下：

(25)

證明：

Q(w,Θ;w(t),Θ(t))=

λ(w(t),Θ(t),Θ)

(26)

在EM的每次迭代中，通過求解式(24)來更新Θ，同時通過最小化式(25)來更新w。 在式(24)中，Eθj(d)是：

(27)

在實踐中，計算式(24)比較困難。本文采用抽樣方法來獲得式(24)右邊的近似解。通過二分搜索法獲得Θ，步驟如算法1所示。

算法1更新Θ

輸出：Θ(t+1)

步驟

使用最大化對數似然估計更新w，算法2的步驟如下：

算法2更新w,Θ

輸入：D,w(0),Θ(0),ε1,ε2

輸出：w,Θ

步驟

1. 使用算法1計算Θ(t+1)。

2. 在算法1中重復采樣步驟1和步驟2，以獲得每個實例的排序集。

3. 從采樣集中為每個實例選擇最大元素。這些最大元素是該特定迭代的估計真值排序。

4. 使用最大化似然估計更新w與估計的真值標簽。

5. 如果t<150，或‖Θ(t)-Θ(t+1)‖<ε1并且‖w(t)-w(t+1)‖<ε2，返回w(t+1)和Θ(t+1); 否則t=t+1，轉到步驟1。

4 實 驗

4.1 實驗準備

實驗采用OHSUMED測試數據集，將此數據集作為排序學習的基準集[13]。此數據語料庫有106個查詢，每個查詢數據由查詢-文檔對組成，每對都有45維特征，并在其上進行相關性判斷。相關程度分為：強相關、弱相關和不相關。將提出的三種方法在訓練集和測試集上實現，以訓練出最佳參數。提出的新模型用于對測試數據進行排序。最后，將實驗通過評估標準作為對比，使用的評估標準：平均精度(MAP)和歸一化折現累積增益(NDCG)，記錄每個方法的評估結果。實驗中它們的評估值越高，結果越好。

此實驗在完全排序中使用本文提出的三種方法進行評估。在每個實驗中，將算法2中的ε1和ε2分別設置為0.01×G和0.01×n，n=45是特征維度；w(0)的每個條目設置為1/n；Θ(0)隨機初始化；在Method3中的參數η設置為20；注釋器G∈[5,10]。

4.2 實驗結果及分析

根據實驗結果，圖3分別顯示了Method1和Method2在OHSUMED數據集上NDCG@3和NDCG@5的性能結果。提出的方法Method2的性能在大多數G值上明顯優于Method1，由此可以看出，本文提出的方法明顯優于常規排序學習算法，其方法統一了真值估計和模型學習。我們還注意到在圖4中顯示了MAP的結果，Method2比Method1對注釋器數量的變化更強，部分原因是在Method1中，模型學習在第一步對真值估計非常敏感，而在Method2中，模型學習可以在下一次迭代中的反饋值代入到真值估計。所以由此可見Method2比常規排序學習算法Method1更穩健。圖5顯示了在NDCG@5中模擬了根據注釋器的輔助信息估計專業知識程度的結果，在大多數G值上Method3略好于Method2，都優于Method1。通過利用輔助信息所提出的算法，提高排序學習能力。

(a) NDCG@3

(b) NDCG@5圖3 Method1和Method2在OHSUMED數據集上 的性能比較

圖4 OHSUMED數據集的性能(MAP)比較

圖5 三種方法在OHSUMED數據集上的性能比較

為了比較所涉及方法的收斂速度，在每次EM迭代結束時，我們根據每個EM迭代為每個算法定義的概率選擇最佳排序樣本，并計算所選最佳排序樣本與真值排序標簽之間的平均Kendall-Tau距離。圖6為三種算法在每次EM迭代時所選擇的最佳排序樣本與真值排序標簽之間的(平均)Kendall-Tau距離(d)的收斂。圖中Method3的收斂速度比算法Method2快得多，由此可以得出，Method3中的輔助信息可以降低優化過程的計算復雜度，Method1的收斂性明顯差了很多。

圖6 三種算法在Kendall-Tau距離方面的收斂性

5 結 語

本文研究了在多個注釋器下進行標簽排序的學習，這些注釋器提供的標簽不是絕對準確的。通過將Mallows模型和P-L模型結合作為概率排序模型中的新學習模型，對測試數據進行排序。提出了新的學習方法對排序模型進行參數估計，Method2迭代地估計真值標簽，使用傳統算法來訓練基于真值標簽的排序函數，將真值標簽和排序函數與最大似然估計框架結合。在許多眾包標簽任務中可獲得關于注釋器的輔助信息(例如，信用記錄、專業等級和注釋準確性的歷史)。因此，提出方法Method3，此方法在Method2的基礎上加入注釋器的輔助信息。實驗結果表明，方法Method2優于直接方法Method1，在考慮輔助信息的情況下，算法Method3同樣可以獲得比算法Method1更好的結果。如果將一些真實標簽注入訓練集，則可以進一步提高性能。并且通過Method3的實驗結果可知，注釋器的輔助信息有助于提高標簽的準確性，降低學習優化過程中的計算復雜度。