最近在看半監督學習演算法的時候看到一個比較新（15年發表）的演算法思想，叫做Contrastive Pessimistic Likelihood Estimation，論文地址：Contrastive Pessimistic Likelihood Estimation for Semi-Supervised Classification

由於很多半監督演算法的有效性建立在一定的前提假設上，但現實中的數據分佈往往較難滿足這樣的條件，比如s3vm，基於「低密度分隔」的假設。當數據不符合這樣的假設時，往往會使得半監督演算法的效果反而不如直接用少量的有標籤樣本建立的完全有監督模型。

基於此，該演算法提出了兩個原則，分別是contrast and pessimism，前者表示會將有標籤樣本的效果納入考慮，言外之意是首先要保證這部分樣本的效果不會比直接用有監督模型差；後者則是在給無標籤樣本賦值標籤時是悲觀的，在這種悲觀的情況下再去迭代，這樣不論無標籤樣本的真實標籤是如何分佈的，都能取得不差於原完全有監督模型的效果。

上面的說法有點繞，直接看幾個公式會更直覺，文章的公式其實很簡單，不需要新的知識。

先假設所有的樣本都拿到了真實標籤，則有全標籤的樣本：

式1

其中 X 代表有標籤的樣本， u_i(U) 代表無標籤的樣本 i ，其中 v_i^* 無標籤 i 樣本的真實標籤， M 代表樣本數量。

式2

上式中的 L 代表log-likelihood，如果我們在全標籤樣本上建模，那麼得到的估算參數 heta_{opt} 則是最佳的參數。

式3

而 heta_{sup} 則是基於有標籤樣本 X 估算出來的，那麼它生成likelihood要比全標籤樣本的likelihood要小，則是由於缺失一部分無標籤樣本的標籤導致的。

式4

如果我們能利用一定無標籤樣本的信息，得到的估算參數為 heta_{semi} ，那麼它得到的likelihood則是位於 sup 和 opt 之間。

那麼 CPLE 的演算法就要保證 heta_{semi} 的估算至少要優於 heta_{sup} ，那麼這其實也意味著我們要將兩者生成的likelihood的差值納入考慮。

為了可以計算無標籤樣本的likelihood，我們引入一個類別的後驗概率 q_{ki} ，代表無標籤 i 樣本屬於 k 類的概率，也被稱作soft-label，先假設這個值是給定的，因此，可計算likelihood：

式5

主要注意上式的最後那部分，正是無標籤樣本在給定後驗概率 q 下的likelihood。

式6

上式則是表示在任何 heta 下與 heta_{sup} 的likelihood的差值，這個差值越大，說明相比用有標籤樣本單獨建模，無標籤樣本帶來的信息更多，模型的效果就越好。

但是由於式5中的 q 是未知的，所以不能直接求解 maxCL 。由於 CPLE 對無標籤樣本真實標籤的預估抱悲觀的態度，那麼它總是會取比較糟糕的 q ，使得 CL 最小：

式7

那麼最後，在糟糕的 q 裡面我們選取一個 heta 使得 CL 最大：

式8

演算法步驟：

1、先利用有標籤的樣本 X 建模，得到估算的 heta_{sup} ；

2、初始化 q ;3、在這個 q 下計算 得到 CPL ;4、最大化 CPL 得到估算的 heta ;5、將 heta 代入 CL ，並最小化 CL ，得到估算的 q ；6、重複3-5，直到 CPL 收斂，最終得到估算的 heta_{semi}

其實這個步驟有點像EM演算法，先優化 q 再優化 heta ，原文是利用LDA做的，屬於生成式的模型。

目前github上沒有具體的實現，只找到了一個github.com/tmadl/semisu，

但是上面這個實現有一個錯誤，它把 CL 寫錯了，另外這個實現是用判別式模型實現的，採用的 q 也不是soft-label，而是hard-label。所以至於效果怎麼樣，也比較難評判。

將上面的實現進行修改後的代碼：github.com/Shuilongyin/

我自己的工程能力有點弱，所以有興趣的可以用生成式模型進行實現，否則求解最優的 q 時總會取到邊界，即非0即1，這是因為單調的原因（見github.com/Shuilongyin/）。


推薦閱讀：
相關文章