半監(jiān)督學(xué)習(xí)綜述

引言

傳統(tǒng)的機(jī)器學(xué)習(xí)技術(shù)一般都是只利用有標(biāo)簽樣本集或者只利用無(wú)標(biāo)簽樣本集合匹厘，只利用有標(biāo)簽樣本的算法我們稱為“有監(jiān)督學(xué)習(xí)”现拒，比如邏輯回歸媳纬、樸素貝葉斯剧辐、支持向量機(jī)道媚、隨機(jī)森林憔狞、梯度提升樹以及梯度提升樹的增強(qiáng)版本Xgboost等送淆；只利用無(wú)標(biāo)簽樣本的算法我們稱為“無(wú)監(jiān)督學(xué)習(xí)”嫌蚤，比如聚類就是一種典型的無(wú)監(jiān)督學(xué)習(xí)挠蛉。而在實(shí)際問題中一般是有標(biāo)簽和無(wú)標(biāo)簽數(shù)據(jù)共存祭示，但是標(biāo)簽數(shù)據(jù)集過少，無(wú)標(biāo)簽數(shù)據(jù)集大量存在谴古，為了更好的利用無(wú)標(biāo)簽數(shù)據(jù)集以提升模型性能质涛，從而帶來(lái)了另外一種著名的學(xué)習(xí)：半監(jiān)督學(xué)習(xí)。

半監(jiān)督學(xué)習(xí)分類

無(wú)圖無(wú)真相掰担，先爆圖汇陆，下面這張圖能夠很清晰的說明學(xué)習(xí)半監(jiān)督的意義何在。

Paste_Image.png

在不考慮無(wú)標(biāo)簽數(shù)據(jù)時(shí)带饱，只有1和2兩個(gè)有標(biāo)簽數(shù)據(jù)毡代，此時(shí)的決策邊界是圖中的虛線阅羹，當(dāng)我們將無(wú)標(biāo)簽數(shù)據(jù)考慮以后，兩類樣本所服從的分布發(fā)生改變教寂，從而導(dǎo)致決策邊界向右偏移捏鱼，變成黑色實(shí)線。上述過程的直觀理解就是隨著我們能夠拿到的樣本集的增多酪耕，我們對(duì)于正負(fù)兩類樣本的信息掌握更加充分导梆，從而使我們做出更好的決策。

傳統(tǒng)意義上的半監(jiān)督學(xué)習(xí)一般可以分為以下四類（想看詳細(xì)材料的小伙伴請(qǐng)戳這里半監(jiān)督學(xué)習(xí)綜述）：

semi_supervised_learning.png

其中迂烁，生成式模型主要是將生成式模型如GMM和HMM等引入到半監(jiān)督學(xué)習(xí)中看尼；低密度劃分算法就是要盡量讓分類邊界通過密度較低區(qū)域，是在傳統(tǒng)支持向量機(jī)基礎(chǔ)上了很多改進(jìn)以更好利用無(wú)標(biāo)簽來(lái)提升模型性能盟步，比如常見的半監(jiān)督支持向量機(jī)S3VM藏斩、S4VM等等；不一致性算法是指在整個(gè)訓(xùn)練過程中建立兩個(gè)或兩個(gè)以上的分類器并讓他們協(xié)同工作的范式址芯；圖正則化這類算法基于流型假設(shè)灾茁，假設(shè)所有的樣本點(diǎn)（包括已標(biāo)記與未標(biāo)記）以及之間的關(guān)系可以表示為一個(gè)無(wú)向圖的形式 g =<V,E >，其中圖的結(jié)點(diǎn)為數(shù)據(jù)樣本點(diǎn)谷炸，而邊則體現(xiàn)了兩個(gè)樣本點(diǎn)之間的相似度關(guān)系北专，基于圖的半監(jiān)督算法的優(yōu)化目標(biāo)就是要保證在已標(biāo)記點(diǎn)上的結(jié)果盡量符合而且要滿足流型假設(shè)。

本文主要跟大家分享交流的是生成式模型中GMM和EM算法在半監(jiān)督學(xué)習(xí)中的應(yīng)用旬陡，其余模塊后續(xù)和大家交流分享拓颓。主要從期望最大化算法、混合高斯模型以及混合高斯模型在半監(jiān)督學(xué)習(xí)中的應(yīng)用三個(gè)部分進(jìn)行展開描孟。

期望最大化EM算法

EM算法

EM算法本質(zhì)是一種迭代算法驶睦，用于求解含有隱變量的概率模型參數(shù)的極大似然估計(jì)，概率模型有時(shí)既含有觀測(cè)變量匿醒，同時(shí)含有隱含變量或者潛在變量场航，如果概率模型的變量都是觀測(cè)變量，那么對(duì)于給定的數(shù)據(jù)廉羔，直接使用極大似然估計(jì)就可以求解得到對(duì)應(yīng)的參數(shù)（可以在本文的混合高斯模型在有監(jiān)督二分類學(xué)習(xí)中的應(yīng)用 章節(jié)看到）溉痢，但是當(dāng)概率模型含有隱變量時(shí)，就沒有辦法直接使用極大似然估計(jì)方法憋他，從而提出能夠求解隱變量的EM算法（可以在本文的混合高斯模型在半監(jiān)督二分類學(xué)習(xí)中的應(yīng)用 章節(jié)看到）孩饼。

該部分參考資料主要來(lái)源于七月在線的機(jī)器學(xué)習(xí)班課程，詳情請(qǐng)戳這里七月在線

具體來(lái)說竹挡，EM算法包含E步和M步镀娶，E步首先在隨機(jī)給出參數(shù)θ的前提下，求得關(guān)于隱變量的后驗(yàn)概率揪罕；M步是在已知后驗(yàn)概率的前提下梯码，通過已知觀測(cè)樣本的參與求得使得期望最大化時(shí)的參數(shù)宝泵，從而使得參數(shù)得以更新，然后重復(fù)E步和M步直至算法收斂忍些。

em.png

里面涉及到的兩步：

• E步中為什么是關(guān)于隱變量的后驗(yàn)概率鲁猩？
• M步中所謂期望最大化由何處來(lái)？

為了說明上述兩個(gè)問題罢坝，我們首先引入目標(biāo)函數(shù)（對(duì)數(shù)似然函數(shù)）廓握，并且為了方便求解隱含變量z，讓其在目標(biāo)函數(shù)中顯性的表示出來(lái)：

Paste_Image.png

z是隱隨機(jī)變量嘁酿，不方便直接找到參數(shù)估計(jì)隙券，所以我們的策略是利用Jensen不等式計(jì)算l(θ)下界，然后求該下界的最大值闹司；重復(fù)該過程娱仔，直到收斂到局部最大值。具體地游桩，令Qi是隱含變量z的某一個(gè)分布牲迫，Qi≥0，有

Paste_Image.png

為了使Jensen不等式對(duì)于任何樣本點(diǎn)而言都能取得等號(hào)借卧，必須有

Paste_Image.png

從而有下式存在盹憎，也證明了剛才提到的兩個(gè)問題。

Paste_Image.png

EM算法與熟悉的K-means是什么關(guān)系

兩者都可以看做迭代算法铐刘，對(duì)于K-means來(lái)說就是我們一開始不知道每個(gè)樣例對(duì)應(yīng)的隱含變量也就是最佳類別c(i)陪每，最開始可以隨便指定一個(gè)類別c(i)給樣例，然后為了讓目標(biāo)函數(shù)J最小化镰吵，我們求出在給定c(i)情況下檩禾，J最小時(shí)的質(zhì)心參數(shù)u(j)（EM算法中第一步時(shí)需要初始化的未知參數(shù)），得到新質(zhì)心參數(shù)u(j)以后發(fā)現(xiàn)可以有更好的類別c(i)指定給樣例使得目標(biāo)函數(shù)J 更小疤祭，那么c(i)得到重新調(diào)整盼产，上述過程就開始重復(fù)了，直到?jīng)]有更好的c(i)指定勺馆。這樣從K-means里我們可以看出它其實(shí)就是EM的體現(xiàn)辆飘，E步是確定隱含類別變量，M步更新其他參數(shù)來(lái)使J最小化谓传。這里的隱含類別變量指定方法比較特殊，屬于硬指定芹关，從k個(gè)類別中硬選出一個(gè)給樣例续挟，而不是對(duì)每個(gè)類別賦予不同的概率〗某模總體思想還是一個(gè)迭代優(yōu)化過程诗祸，有目標(biāo)函數(shù)跑芳，也有參數(shù)變量，只是多了個(gè)隱含變量直颅，確定其他參數(shù)估計(jì)隱含變量博个，再確定隱含變量估計(jì)其他參數(shù)，直至目標(biāo)函數(shù)最優(yōu)功偿。

該部分的參考資料來(lái)源于JerryLead同學(xué)的博客盆佣，在此表示感謝！

注：K-means中的目標(biāo)函數(shù)稱為畸變函數(shù)（distortion function）（如下式所示）械荷，J目標(biāo)函數(shù)表示每個(gè)樣本點(diǎn)到其質(zhì)心的距離平方和共耍，所以K-means的目標(biāo)是要將J函數(shù)調(diào)整到最小。

目標(biāo)函數(shù)J.png

混合高斯模型

問題背景

首先來(lái)個(gè)簡(jiǎn)單小栗子讓大家找點(diǎn)感覺吨瞎，比如說：
我們對(duì)1000名學(xué)生進(jìn)行身高數(shù)據(jù)測(cè)量（PS：如老師所說痹兜，反正像我肯定是不會(huì)讓你測(cè)試的，O(∩_∩)O哈哈~）颤诀，假設(shè)樣本中存在男性和女性（第三種性別不考慮在內(nèi)）字旭，身高數(shù)據(jù)分別服從正態(tài)分布N(μ1,σ1)和和N(μ2,σ2)，如何利用已觀測(cè)到的身高數(shù)據(jù)估計(jì)對(duì)應(yīng)參數(shù)μ1,σ1,μ2,σ2崖叫。
將上述例子抽象為數(shù)學(xué)表示：
觀測(cè)到得隨機(jī)變量X（對(duì)應(yīng)于例子中的身高）是有K（對(duì)應(yīng)于例子中的男性和女性遗淳，值為2）個(gè)高斯分布混合而成，取各個(gè)高斯分布的概率為φ1φ2... φK归露，第i個(gè)高斯分布的均值為μi洲脂，方差為Σi。若觀測(cè)到隨機(jī)變量X的一系列樣本x1,x2,...,xn（對(duì)應(yīng)于例子中已觀測(cè)到的身高數(shù)據(jù)）剧包，試估計(jì)參數(shù)π恐锦，μ，Σ疆液。

EM求解過程

對(duì)于所有的數(shù)據(jù)點(diǎn)一铅，可以看作組份k生成了這些點(diǎn)。組份k是一個(gè)標(biāo)準(zhǔn)的高斯分布堕油，具體的算法步驟會(huì)在本文最后講解混合高斯模型在半監(jiān)督分類中的應(yīng)用 時(shí)給出潘飘，本質(zhì)還是嚴(yán)格遵守了EM算法的兩步來(lái)進(jìn)行。

混合高斯模型在半監(jiān)督中的應(yīng)用

該部分的參考資料來(lái)源于Xiaojin Zhu and Andrew B. Goldberg的書籍：Introduction to Semi-Supervised Learning

一般的掉缺，對(duì)于二分類問題而言卜录，混合高斯模型中高斯模型的個(gè)數(shù)此時(shí)就是確定的2，即正樣本和負(fù)樣本兩類樣本各自所服從的密度函數(shù)眶明；對(duì)于一個(gè)示例（instance）艰毒，我們想知道它可能的預(yù)測(cè)標(biāo)簽y是什么，我們通常會(huì)使用如下概率公式來(lái)計(jì)算哪一類對(duì)應(yīng)的概率最大搜囱。

Paste_Image.png

上述式子中丑瞧，分母相當(dāng)于歸一化因子柑土，重點(diǎn)在于如何求解分子的乘積項(xiàng)，其中绊汹，p(x|y)稱為類的條件概率稽屏，其實(shí)就是正類和負(fù)類樣本各自所服從的概率密度函數(shù)；p(y)是每一類的先驗(yàn)概率西乖，如果全部是有標(biāo)簽的時(shí)候狐榔，p(y)直接通過計(jì)數(shù)求頻率即可得到。

混合高斯模型在有監(jiān)督二分類學(xué)習(xí)中的應(yīng)用

有監(jiān)督學(xué)習(xí)中浴栽，所有數(shù)據(jù)都是已知標(biāo)簽的荒叼，此時(shí)可以直接使用最大似然估計(jì)求解三組參數(shù)

Paste_Image.png

然后對(duì)上式引入拉格朗日乘子beta，轉(zhuǎn)化為如下式子：

拉格朗日函數(shù).png

直接對(duì)上式分別求偏導(dǎo)典鸡，就能得到每一類的先驗(yàn)概率被廓、高斯分布的均值以及高斯分布的方差。

混合高斯模型在半監(jiān)督分類中的應(yīng)用

在半監(jiān)督學(xué)習(xí)中萝玷，數(shù)據(jù)包含有標(biāo)簽和無(wú)標(biāo)簽數(shù)據(jù)兩部分 嫁乘，對(duì)數(shù)似然函數(shù)變?yōu)?/p>

半監(jiān)督中的似然函數(shù).png

該似然函數(shù)和前面有監(jiān)督學(xué)習(xí)中似然函數(shù)相比，最大的不同點(diǎn)就在于針對(duì)無(wú)標(biāo)簽數(shù)據(jù)多出的第二項(xiàng)式子球碉，我們通常稱p(x|θ)為邊緣概率蜓斧，

Paste_Image.png

邊緣概率表示對(duì)于無(wú)標(biāo)簽數(shù)據(jù)我們已知其樣本和特征信息，但是不知道每個(gè)樣本歸屬的類別y是什么睁冬，無(wú)標(biāo)簽樣本所對(duì)應(yīng)的類別此時(shí)相當(dāng)于隱含變量挎春，該隱變量的存在會(huì)使得上述似然函數(shù)非凸和難求解，為此我們將剛才提到的期望最大化算法EM引入進(jìn)來(lái)豆拨，來(lái)求解θ的局部最優(yōu)值直奋。

Paste_Image.png

上面的算法步驟里面，首先初始化參數(shù)θ(0)施禾，θ(0)就是利用MLE在有標(biāo)簽數(shù)據(jù)上所求得值（注：在半監(jiān)督算法里面脚线，很多地方都會(huì)出現(xiàn)類似的身影，就是參數(shù)的初值都是現(xiàn)在有標(biāo)簽數(shù)據(jù)上求得弥搞，然后逐步將無(wú)標(biāo)簽數(shù)據(jù)引入進(jìn)來(lái)邮绿，之后跟大家分享一篇利用牛頓法求解S3VM的算法，初值選取的手法類似）攀例，第E步就是得到關(guān)于隱變量（無(wú)標(biāo)簽數(shù)據(jù)對(duì)應(yīng)的標(biāo)簽）的后驗(yàn)概率（所以γij取值為0和1船逮，當(dāng)?shù)趇個(gè)樣本屬于第j類時(shí)，γij=1粤铭，否則為0傻唾，這兒稍微和前面提到的混合高斯模型有所區(qū)別，前面提到的混合高斯模型中，γij可以理解為第j個(gè)成分對(duì)于觀測(cè)到的第i個(gè)樣本的貢獻(xiàn)程度冠骄，是一個(gè)真正意義上的0-1之間的概率值，而此時(shí)的γij取值只能是0和1）加袋，得到隱變量的后驗(yàn)概率以后凛辣，求得期望最大化時(shí)對(duì)應(yīng)的參數(shù)θ，然后將新的θ會(huì)帶到E步中职烧，求得新的γij扁誓，不斷重復(fù)直至收斂。

好啦~上述就是今天要跟大家分享的所有內(nèi)容蚀之，第一次以博客的形式跟大家交流蝗敢，難免會(huì)有疏漏，有任何建議和意見隨時(shí)都?xì)g迎大家給我留言（本人QQ：1104409598）足删！