機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘

1、機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘數(shù)學(xué)方法與理論（3）2022年2月16日Machine Learning2概率分類器n貝葉斯定理在分類問題中的應(yīng)用Nave Bayes問題n分布不一定是高斯的n用多個正態(tài)分布的和擬合樣本分布jjjjiXNXcP,|如何獲得參數(shù)？2022年2月16日Machine Learning3概率分類器n混合高斯模型GMM: Gaussian Mixture Model jjjjjjjjcEPcEXPXPcEPcEXPXcEPXE|maxarg|maxarg|maxargiiiijNcEXP,|2022年2月16日Machine Learning4混合高斯模型n假設(shè)：所有樣本來自多個潛在

2、高斯分量樣本來自某高斯分量的概率正比其權(quán)重2022年2月16日Machine Learning5混合高斯模型n假設(shè)：所有樣本來自多個潛在高斯分量樣本來自某高斯分量的概率正比其權(quán)重n樣本（觀察）產(chǎn)生過程：按權(quán)重隨機(jī)選擇一個高斯分量以該高斯分量的參數(shù)產(chǎn)生樣本迭代產(chǎn)生更多樣本2022年2月16日Machine Learning6混合高斯模型n問題描述觀察：樣本集目標(biāo)：描述樣本集的分布函數(shù)n估計(jì)模型的參數(shù)n難點(diǎn)：樣本來自哪個高斯分量是未知的niiii1|,2022年2月16日Machine Learning7混合高斯模型n參數(shù)估計(jì)高斯分量參數(shù)估計(jì)n如果已知每個樣本來自哪個分量直接計(jì)算權(quán)重估計(jì)n如果已知

3、每個分量的參數(shù)最大相似度準(zhǔn)則計(jì)算樣本所屬分量然后計(jì)算權(quán)重ii,雞生蛋？蛋生雞？2022年2月16日Machine Learning8混合高斯模型n數(shù)學(xué)表述設(shè)類ci的訓(xùn)練樣本集為S：個正態(tài)分布產(chǎn)生由第假設(shè)jkkkIsSs:jjjjijkXNXcPI,|可計(jì)算通過已知假設(shè)jjjjiXNXcP,|jkIjjjjjksNI,maxarg觀察量隱變量2022年2月16日Machine Learning9混合高斯模型nEM算法|, yxp xX 觀察量已知求隱變量參數(shù)優(yōu)化目標(biāo)較好的解：最大似然估計(jì)iyiiiiiiiyxpxpxpXL|,log|log|log|YYXpXpXL|,log|log|http:

4、/ Learning10混合高斯模型nEM算法求極值n梯度下降，牛頓迭代，拉格朗日乘數(shù)n對數(shù)函數(shù)導(dǎo)數(shù)難求即使不用對數(shù)，常常需要面對e的指數(shù)函數(shù)及其求和n高斯分布n往往沒有顯式的導(dǎo)數(shù)YYXpXL|,logmaxarg|maxarg2022年2月16日Machine Learning11混合高斯模型nEM算法Jensen不等式n對凸函數(shù)有：n凹函數(shù)不等式反向log是凹的 XEfXfE YqYXpEYqYXpYqYXpYY|,logmaxarg|,logmaxarg|,logmaxarg YqYXpEYqYXpE|,log|,log下界：逐次抬高下界，則可求得最大值 YqYXpE|,logmaxar

5、g2022年2月16日Machine Learning12混合高斯模型nEM算法算法步驟n求期望(E-step)不等式取等號的條件（X=EX）n最大化期望(M-step)所有不可觀察量已有估計(jì)值，則參數(shù)的最大相似度估計(jì)即可最大化期望 YqYXpE|,logmaxarg ,|,|,|,XYpXpYXpYqXpYqYXpEYqYXp2022年2月16日Machine Learning13混合高斯模型nEM算法收斂證明 XLYqYXpEYqYXpEYqYXpEXLnnnnnnn|,log|,log|,log|111Jensen不等式M-step2022年2月16日Machine Learning14

6、混合高斯模型nEM算法問題n收斂到局部極值本質(zhì)上是梯度下降法n鞍點(diǎn)鞍點(diǎn)梯度為0，任何方向都不可下降n分量個數(shù)如何確定？個數(shù)越多，最大相似度估計(jì)越大不可能把分量個數(shù)一起作為待估計(jì)參數(shù)n訓(xùn)練中與分類問題無關(guān)?。?022年2月16日Machine Learning15混合高斯模型nEM算法分量個數(shù)對性能有顯著影響性能對于分量個數(shù)不是凸函數(shù)n但大體上是凸的2022年2月16日Machine Learning16混合高斯模型n分量操作引進(jìn)類似遺傳算法/模擬退火的機(jī)制對分量進(jìn)行分裂、合并、生、死等操作n跳出局部極值，向更大的參數(shù)空間搜索n如何選擇操作？n如何執(zhí)行操作？2022年2月16日Machine L

7、earning17混合高斯模型n執(zhí)行操作（對參數(shù)空間的修改）死：把相應(yīng)分量消去即可n對應(yīng)樣本以最大相似度準(zhǔn)則分配給別的分量生：加入相應(yīng)分量n計(jì)算合適的初始參數(shù)啟發(fā)式規(guī)則：一次迭代中所有死的分量如足夠，對應(yīng)的樣本合為一個新分量n迭代中可能多個分量擁擠占據(jù)一個地方，則所有分量都無法生存2022年2月16日Machine Learning18混合高斯模型n執(zhí)行操作合并jikkjjiik2kTjijijikjjiik原分量內(nèi)方差分量間方差2022年2月16日Machine Learning19混合高斯模型n執(zhí)行操作分裂n增加參數(shù)的操作要“制造”未知的信息EM算法：局部樣本進(jìn)行EM迭代n運(yùn)算量大n整個算

8、法后續(xù)步驟有EM迭代n如何“制造”有一定合理性的參數(shù)2022年2月16日Machine Learning20混合高斯模型n執(zhí)行操作分裂n假設(shè)分裂后的兩分量中心間矢量為a基本原理：把分裂出的分量按合并格公式應(yīng)計(jì)算出原來的分量sss2121ass211Tsssaa4121ass212a2022年2月16日Machine Learning21混合高斯模型n執(zhí)行操作分裂n計(jì)算a方法1：沿主軸方向n理由：方差最大n缺點(diǎn)：不一定合理方法2：最不“高斯”的方向n理由：我們使用的是高斯分量，如該方向不符合高斯分布，則該方向最適合分裂n如何計(jì)算？2022年2月16日Machine Learning22混合高斯模

9、型n執(zhí)行操作分裂n投影追蹤(Projection Pursuit)對高維數(shù)據(jù)，尋找“最有吸引力”的方向，把所有數(shù)據(jù)投影到該方向并作圖，則可揭示最有意義的信息“最有吸引力”如何定義？n非高斯性n“高斯”是最平常的分布，無人喜歡如何尋找該方向？n最優(yōu)化/search/wrapper.jsp?arnumber=16726442022年2月16日Machine Learning23混合高斯模型n投影追蹤投影追蹤指數(shù)（ Projection Pursuit Index）n度量分布的“非高斯”性Kurtosis（峰度）3442242order n cumu

10、lant (n階積累量？)4階中心矩把高斯分布?xì)w一化到0/doconnor/PEP6305/Topic%20002%20Organizing%20Data2.3.htm2022年2月16日Machine Learning24混合高斯模型n投影追蹤投影追蹤指數(shù)n度量分布的“非高斯”性Skewness（偏度？）332/3231/wiki/Skewness2022年2月16日Machine Learning25混合高斯模型n投影追蹤投影追蹤指數(shù)n度量分布的“非高斯”性Kurtosis和Skewness的

11、問題n高階統(tǒng)計(jì)量，對誤差敏感基于熵的度量n在相同方差的假設(shè)下，高斯分布的熵最大，任何其余分布的熵都要小n熵最小的方向最偏離高斯分布2022年2月16日Machine Learning26混合高斯模型n投影追蹤投影追蹤指數(shù)n度量分布的“非高斯”性微分熵 2222122explogXEkXXEkHdxxfxfXH/14425 2log121,621,9383621Hkk2022年2月16日Machine Learning27混合高斯模型n投影追蹤追蹤方法n對整個空間進(jìn)行一定程度的搜索由于目標(biāo)函數(shù)復(fù)雜，沒有什么好方法GMM中的簡化n分裂的候

12、選方向基本上都在主分量上計(jì)算每個主分量方向上的指數(shù)，選取最小者n主分量方向是高斯分量協(xié)方差矩陣的特征矢量n協(xié)方差矩陣做KL分解，獲得候選方向2022年2月16日Machine Learning28混合高斯模型n投影追蹤局部密度估計(jì)n分裂是局部操作，只能使用局部密度每個樣本用局部密度為權(quán)重，計(jì)算加權(quán)的指數(shù)n計(jì)算分裂參數(shù) iiisssXPXPX|jjeva特征值投影追蹤指數(shù)最小的特征矢量2022年2月16日Machine Learning29混合高斯模型n操作選擇準(zhǔn)則死n如果分量小到訓(xùn)練樣本難以估計(jì)出合理的參數(shù)，則該分量可以去除生n與死同llnn2參數(shù)個數(shù)分量中樣本數(shù)2022年2月16日Machi

13、ne Learning30混合高斯模型n操作選擇準(zhǔn)則分裂n局部樣本分布偏離高斯分布分布復(fù)制，須用更多參數(shù)擬合n分量覆蓋大量非本類樣本類邊界區(qū)分式方法的思想到目前為止GMM-EM尚未利用樣本所屬類的信息！n目標(biāo)是分類，則優(yōu)化類邊界有好處類類1類類22022年2月16日Machine Learning31混合高斯模型n操作選擇準(zhǔn)則分裂/合并ijijiCXPXCXPXovjCjC|,|,dxxpxpHiii|log|iiiHwovw1類間覆蓋局部匹配度二者加權(quán)2022年2月16日Machine Learning32混合高斯模型n帶分量操作的EM訓(xùn)練算法EM迭代去除過小分量分裂/合并大分量模型選擇MD

14、L/MML?類間信息并未被EM充分利用020406080100satfacebloodletterpenspamAccuracyNewMMLEM算法可用訓(xùn)練集做模型選擇2022年2月16日Machine Learning33混合高斯模型n帶分量操作的EM訓(xùn)練算法同時使用分裂合并優(yōu)于單獨(dú)使用分裂或合并使用類間信息有助于分類性能的提高0.860.880.900.920.940.96SM+NegSMMergeSplitletter0.930.940.950.960.970.98SM+NegSMMergeSplitpen0.840.860.880.900.92SM+NegSMMergeSplitsat

15、image0.880.890.900.910.920.93SM+NegSMMergeSplitspam0.930.940.950.960.97SM+NegSMMergeSplitblood0.900.910.920.930.940.95SM+NegSMMergeSplitface2022年2月16日Machine Learning34混合高斯模型nGMM-EM算法問題描述整個空間的樣本分布n可以避免局部特征空間過匹配n需要更多參數(shù)需要大量訓(xùn)練樣本GMM-EM算法并關(guān)注樣本的所屬類n天然具有集成未標(biāo)注樣本的能力2022年2月16日Machine Learning35混合高斯模型n未標(biāo)注樣本集成把

16、未標(biāo)注樣本類屬作為未觀察到的量nEM算法可以迭代計(jì)算未觀察到的量n多幾個未觀察到的量并不影響EM算法分裂/合并大分量EM迭代去除過小分量模型選擇未標(biāo)注樣本分類？2022年2月16日Machine Learning36混合高斯模型n未標(biāo)注樣本集成并不是所以未標(biāo)注樣本都有同等效果n有分歧的樣本可能導(dǎo)致反作用2022年2月16日Machine Learning37混合高斯模型n未標(biāo)注樣本集成賦予未標(biāo)注樣本置信度n未標(biāo)注樣本以置信度為權(quán)重加入訓(xùn)練過程后驗(yàn)概率對數(shù)相似度二者的結(jié)合Class 1Class 2Unlabeled0102030-150-130-110-90-70-50-30 log(P1)N

17、egative SamplesPositive Samples%),|(jCujXCPjC),(log11jCjCujVXCPe2022年2月16日Machine Learning38混合高斯模型n完整過程OperationSelectionSplitMergeEMIterationDeathOperationConfidenceComputationConvergence?ModelSelectionEndNoYesStart2022年2月16日Machine Learning39混合高斯模型n實(shí)驗(yàn)結(jié)果一定量的未標(biāo)注樣本對分類有所幫助過多未標(biāo)注樣本性能可能下降分類效果已經(jīng)很好的，標(biāo)注樣本可能沒有幫助letter0.630.640.650.660.670.6805101520pen0.840.850.860.870.880.8905101520satimage0.700.720.740.760.780.8005101520spam0.820.