PU learning論文閱讀。

本文從基本的分類損失出發(fā)，推導了PU的分類問題其實就是Cost-sensitive classi?cation的形式，同時，通過實驗證明了如果使用凸函數(shù)作為loss function，例如hinge loss會導致錯誤的分類邊界（有bias），因此需要使用例如ramp loss之類的凹函數(shù)。同時，論文還對先驗存在偏差的情況進行了討論，說明了如果樣本中大部分都是正樣本，那么就算先驗差距比較大，但對總體的分類效果沒有太大影響。最后對分類邊界進行討論，證明了使用PU進行分類的誤差小于監(jiān)督學習誤差的倍。

基本概念和定義

1. Ordinary classification
   • Bayes optimal classi?er的目標是最小化misclassi?cation rate，這在Introduction to Statistical Machine Learning By Masashi Sugiyama 書里有定義，直觀理解就是最小化期望錯分率：
   • 
   • 這里的表示false negative rate，也就是分錯正類的概率，乘以先驗正類的概率
   • 表示false positive rate，也就是分錯負類的概率，乘以先驗負類的概率
   • 這樣，對分錯樣本的概率分別乘以其先驗概率，就是其錯分概率的期望。
2. Cost-sensitive classi?cation
   • 如果對于某種錯誤我們的敏感程度不一樣，那么就乘以不同的權重，重新定義為：
   • 
   • 這里用和分別表示對兩種錯分的代價
3. PU classification
   • 定義在未標記數(shù)據(jù)集 中的分布：
     • 
     • 注意，這里的可以理解為樣本的分布：
     • 也就是說，
     • 論文認為兩個數(shù)據(jù)集的分布不同：
       • 對于positive sample：
       • 對于unlabel sample：
   • 對于PU問題，我們沒有辦法直接得到負類的信息，因此我們想要把目標函數(shù)中的去掉。定義表示在分布下預測為正類的風險risk：
     • 
   • 這樣，我們就可以將替換為：
     • 
   • 我們可以定義是與的占比，也就是在我們正類數(shù)據(jù)集樣本數(shù)占所有樣本數(shù)的比例，因此可進一步寫成：
     • 
     • 其中
   • 這樣，我們就把PU分類問題轉換為了Cost-sensitive classi?cation問題。通過設置不同的閾值并最小化分類錯誤率，就可以使用SVM等分類器進行訓練。

Necessity of non-convex loss functions

論文認為，如果在PU分類問題中使用常見的凸函數(shù)作為loss function，可能導致結果有biased，因此需要選擇非凸函數(shù)。

1. Loss functions in ordinary classi?cation
   • 在分類器上定義一個符號函數(shù)：
   • 使用01損失，仿照之前的期望錯分率定義損失函數(shù)：
     • 
     • 在大于0的時候取0，小于0時取1
   • 由于01損失在實際中很難優(yōu)化，因此用ramp loss代替：
     • 
   • 而為了保證凸性，因此一般使用hinge loss：
     • 
   • image-20190329204755315
   • 可以發(fā)現(xiàn)，ramp loss 在大于1時沒有損失，在-1到1之間為線性損失，而大于1以后損失恒定為1
   • 而hinge loss在小于1時也依然為線性損失（在SVM中使用）
2. Ramp loss function in PU classi?cation
   • 將ramp loss帶入之前定義的PU目標函數(shù)中，同時根據(jù)ramp loss的特殊性質：，我們可以得到
   • 
   • 這個形式和最初的分類損失相同，也就是說，它們會有相同的分類邊界
3. Hinge loss function in PU classi?cation
   • 如果用hinge loss，同樣的道理我們可以得到：
     • image-20190329211244615
   • 除了最初分類損失的項，還有另外的一項懲罰
   • 作者認為，這個懲罰會導致分類邊界的改變，及時很好的區(qū)分了數(shù)據(jù)，由于懲罰項的存在，目標函數(shù)可能并不會是最小值
4. 論文做了一個簡單的實驗，說明了如果使用hinge loss，那么在先驗增大的情況下，閾值增大的非常快，也就是說，會將所有的樣本都標記為正樣本（閾值為1），因此false positive概率為1。這樣會導致總的分類錯誤率為：
   • image-20190329212345496
5. 因此，作者用實驗和公式說明了，光光最小化分類錯誤率不夠（因為當很大時，會將所有類標記為正類以獲得最小的損失，因此需要使用ramp loss對其進行懲罰

Effect of inaccurate class-prior estimation

現(xiàn)實中有很多方法來估計先驗，但如果估計值離實際值很大（有偏），那么會對我們的PU問題造成什么樣的影響？

1. Ordinary classification
   • 考慮普通分類的情形。我們的目標函數(shù)時最小化
   • 注意，這是一個凹函數(shù)。
   • 如果我們的先驗為，最小化后得到的分類器為，這時候固定，真實的先驗為，可以發(fā)現(xiàn)當靠近時兩個risk 的差距最小，隨著的變化而逐漸增大：
     • image-20190329213643994
2. PU classification
   • 通過變量替換，我們同時定義當前的先驗為，真實的先驗為，可以得到risk為：
     • 
   • 可以發(fā)現(xiàn)，如果 時，該分類就完全失效了（risk 的符號改變）
   • 將其進行歸一化，定義effective class prior為：
     • image-20190329214636202
   • image-20190329214702001
   • 觀察圖片可以發(fā)現(xiàn)，當真實的很大，那么估計的先驗就算相差大一點，影響也不大（頂部較為平緩），這與現(xiàn)實相符。例如，如果我們在異常檢測中，正類遠遠大于負類，那么估計的閾值稍微小優(yōu)點，也不會對risk造成太大的改變。
   • 同樣，如果真實的正類并不多，那么對正類的估計如果不準的話，會對結果造成較大改變。

Generalization error bounds for PU classi?cation

待完成。。。

Reference

1. Analysis of Learning from Positive and Unlabeled Data
2. Introduction to Statistical Machine Learning By Masashi Sugiyama
3. Why are the popular loss functions convex?