度量學習筆記(一) | Metric Learning for text categorization

作者| Walker

編輯| 安可

出品| 磐創AI技術團隊

目前，機器學習中的K近鄰(KNN)分類算法和支持向量機(SVM)算法被認為是處理文本分類的最好方法。但KNN分類算法有以下的缺陷：

KNN是基於近鄰度量的一種模式分類算法，它高度依賴於數據間的相似度度量，簡單的歐式距離在實際應用時，由於不考慮不同維度之間對分類的影響以及輸入數據數據維數高的問題，往往不能取得良好的分類效果。

KNN 分類算法雖然可以一定情況下克服數據偏斜帶來的分類誤差，但是這也是造成它對樣本密度分布敏感的主要原因，當類間密度高度分布不均時，分類效果會有較大的影響。

解決方案：要想提高KNN文本分類的準確率，首先要解決的是距離度量的問題，於是我們就要用到距離度量算法，其中的大邊界最近鄰算法(Large Margin Nearest Neighbor, LMNN)是一類專門改進K 近鄰分類算法的距離度量算法。

那麼什麼是度量學習呢？度量學習(Metric Learning) 是人臉識別中常用的傳統機器學習方法，由Eric Xing在NIPS 2002提出，可以分為兩種：一種是通過線性變換的度量學習，另一種是通過非線性變化的度量。其基本原理是根據不同的任務來自主學習出針對某個特定任務的度量距離函數。後來度量學習又被遷移至文本分類領域，尤其是針對高維數據的文本處理，度量學習有很好的分類效果。

LMNN是最常使用的一種度量學習算法，其可以通過對訓練集學習來得到一種原始數據的新度量，這種方法可以在一定程度上對原始數據分布進行重構，得到一個更加合理的數據分類空間。其次，要解決的就是樣本密度分布不均的問題，在應用LMNN 算法時我們注意到可能會加劇樣本的密度分布不均衡，我們通常採用裁剪或是填充的方案。

大邊界最近鄰算法（LMNN）是用於度量學習的統計機器學習算法。它學習了為k近鄰分類設計的偽測量，是以監督方式學習該全局（偽）度量的算法，以提高k最近鄰規則的分類準確性。該算法基於半定規劃，是凸優化的子類。LMNN背後的主要直覺是學習偽測量，在該偽測量下，訓練集中的所有數據實例被至少k個共享相同類標籤的實例包圍，該算法學習該類型的偽測量：

矩陣M 需要是正半正定的。歐幾裡德度量是一個特例，其中M是單位矩陣。這種概括通常被稱為Mahalanobis度量。

LMNN樣本訓練前後的示意圖如下所示：

基於LMNN 算法的文本分類：文本分類首先要對文本進行特徵提取將待測試文本和訓練文本表示成向量空間模型(Vector Space Model, VSM)，定義

表示訓練文本集合，

為類別集合，其中

表示第i篇文章，di表示文本向量的第i維，此處採用IG算法作為特徵提權算法，然後採用LMNN方法對訓練數據集進行重構，最後使用K 近鄰分類器來實現文本分類，評價標準使用F1值和查準率、查全率。

算法流程：

（1）首先，對中文文本文本進行分詞、去停用詞等預處理。

（2）對文本進行特徵選擇，本文選用了IG 這種常用的的特徵提取算法來對文本進行特徵提取。

（3）構造向量空間模型(Vector SpaceModel，VSM)，本文所採用的是經典TF*IDF 法。

（4）對訓練樣本以歐氏距離用留一法計算出訓練集中每個數據點的先驗知識K近鄰，並做好標籤，設定此K 值為Kp 。

（5）利用LMNN 算法對訓練集進行學習，求出映射矩陣L。

（6）對訓練樣本和測試樣本分別作映射。

（7）跟據上一節中所提出的基於LMNN 的文本分類算法對測試集進行分類。

此外，在LMNN的基礎上，又有人提出了基於密度加權的LMNN 分類算法（DLMNNC）：這是因為在將LMNN 算法與KNN 結合時由於LMNN 算法的特點在很大程度上可能會增加樣本密度分布不均勻，在應用於文本分類仍然會有較大的誤差。

針對此，我們又提出了基於密度加權的K 近鄰分類算法和LMNN 文本分類算法相結合，稱之為DLMNNC 算法.可以一定程度上解決上述由於LMNN 的引入所造成的密度分布更加不均勻問題。例如某網站中娛樂類新聞明顯要比歷史類新聞要多的多，這就有可能造成經特徵提取後的數據點在某種度量意義下密度分布不均衡，特別地在應用LMNN算法來對樣本點進行距離度量學習時：

描述了了在目標樣本i x 在其K 個近鄰中噪聲點(impostor)的標準,並且以此定義非等價約束條件，對近鄰中的異類點有一個推力作用，使其在馬氏距離度量意義下遠離目標樣本。

密度公式：

其中，i x 為j x 的K 近鄰點，(,) Dx c i i 表示K 近鄰中類標籤為i y 向量的密度，K 為最近鄰數，i n 為類標籤為i y 的K 近鄰中向量個數，K近鄰決策公式表示為：

基於餘弦的距離度量學習(CS-LMNN)算法：對於文本數據餘弦距離度量要比歐式距離度量要好一些，這主要因為：對於不同向量，方向性要比數值更加重要，而傳統的歐氏距離度量標準只對數值敏感，並沒有利用向量之間的方向性。而餘弦相似度和歐式距離度量相比較，更加注重兩個向量在方向上的差異，而非距離或長度。

根據類標籤相同的點應儘量相近，類標籤不同的點應儘量遠離這兩個條件我們提出了一種新的基於餘弦的距離度量學習算法，稱之為CS-LMNN 算法。該算法和LMNN 算法類似，也需要訓練集的K 近鄰先驗知識同樣以Kp表示，它根據餘弦夾角的性質，即任意夾角的餘弦值不可能大於1，這一條件來構造非等價性約束，然後，在最優化表達式中，通過最小化近鄰同類標籤樣本的餘弦距離來構造等價性條件。最終，將兩條件改寫為一個最優化問題進行求解。具體算法流程如下:首先，定義餘弦距離度量,在訓練集D中任意兩點,i j x x 間的餘弦距離度量表達式：

目標樣本i x 具有類標籤i c 在其K 近鄰點中有l x 類標籤為l c ，定義噪聲點為對任意目標樣本i x 有l i c c ≠，滿足：

損失函數：

基於餘弦距離度量(CS-LMNN)的文本分類算法的具體流程如下：

PFLMNN:Parameter Free Large Margin Nearest Neighbor for DistanceMetric Learning：PFLMNN（無參數大邊界最近鄰）是一種新的度量學習算法，不同於LMMN將目標鄰居拉到一起，同時將冒名頂替者推開，我們的方法只考慮將冒名頂替者推出鄰居的行為。這種方式與LMNN相比，我們簡化了我們的優化問題的任務。

為了提高k個最近鄰之間的距離和查詢的能力，PFLMN是一種利用LMNN忽略的冒名者之間的幾何信息推送冒名者的新方法。簡而言之，僅考慮每個查詢的最近活動冒名頂替者。根據距離度量，當最近的冒名頂替者不在附近時，所有其他冒名頂替者都不在。通過這種方式，減少了由冒名頂替者顯示的需要被推動的約束，使得所提出的模型在不削弱其約束能力的情況下將更加簡單。

因此，與LMNN相比，PFLMNN模型更容易被優化。此外，由於模型只包含一個項，因此不需要調整成本函數中的參數，使得該方法更便於使用。我們比較一下LMNN與PFLMNN的異同，LMNN是k=3鄰域在小半徑內被拉在一起，而具有不同標記的輸入被從小半徑內拉出有限邊距。

LMNN原理圖

PFLMNN原理圖

如圖所示，與LMNN不同的是，PFLMNN只採取拉不同標記輸入的動作。以有限的餘量從小半徑中拉出來，這樣模型更加簡單，易被優化。