前言

如果你能找到這里锨侯，真是我的幸運~這里是藍白絳的學習筆記嫩海，本集合主要針對《百面機器學習——算法工程師帶你去面試》這本書。主要記錄我認為重要的知識點囚痴，希望對大家有幫助叁怪。

第八章 采樣

4、高斯分布的采樣

1. 高斯分布用逆變換法采樣深滚，基本操作步驟為：
   (1) 產生上的均勻分布隨機數奕谭。
   (2) 令，則服從標準正態(tài)分布成箫。其中是高斯誤差函數展箱，它是標準正態(tài)分布的累積分布函數經過簡單平移和拉伸變換后的形式，定義如下:上述變換法需要求解的逆函數蹬昌，但這并不是一個初等函數混驰，沒有顯式解，計算起來比較麻煩皂贩。
   為了避免這種非初等函數的求逆操作栖榨，Box-Muller算法提出了如下解決方案：單個高斯分布的累積分布函數不好求逆，那么嘗試兩個獨立的高斯分布的聯合分布明刷。假設是兩個服從標準正態(tài)分布的獨立隨機變量婴栽，他們的聯合概率密度為：考慮在圓盤上的概率，通過極坐標變換將轉化為辈末，可以很容易求得二重積分愚争，上式變?yōu)椋?img class="math-block" src="https://math.jianshu.com/math?formula=F(R)%3D1-e%5E%7B%5Cfrac%7BR%5E2%7D%7B2%7D%7D%2CR%5Cgeq0." alt="F(R)=1-e^{\frac{R^2}{2}},R\geq0." mathimg="1">這里可以看作是極坐標中的累積分布函數，計算公式簡單挤聘，逆函數容易求轰枝，可以用逆變換方法對進行采樣，在上對進行均勻采樣组去，這樣就得到了鞍陨，對它進行坐標變換就可以得到符合標準正態(tài)分布的。采樣過程如下：
   (1) 產生[0,1]上的兩個獨立的均勻分布隨機數从隆。
   (2) 令诚撵，則服從標準正態(tài)分布缭裆，并且相互獨立。
   Box-Muller算法由于需要計算三角函數寿烟，相對來說比較耗時澈驼，Marsaglia polar method方法可以避開三角函數計算，更快筛武。
2. 高斯分布用拒絕采樣法采樣：考慮到高斯分布的特性盅藻，這里用指數分布來作為參考分布。指數分布的累積分布及其逆函數都比較容易求解畅铭。
   由于指數分布的樣本空間為，而標準正態(tài)分布的樣本空間為勃蜘，因此還需要利用正態(tài)分布的對稱性來在半坐標軸和全坐標軸之間轉化硕噩。取的指數分布作為參考分布，其密度函數為累積分布函數為：密度函數的逆函數為利用逆變換法很容易得到指數分布的樣本缭贡，然后再根據拒絕采樣法來決定是否接受該樣本炉擅，接受概率為其中是標準正態(tài)分布壓縮到正半軸后的概率密度，常數因子需要滿足如下條件：實際應用中需要盡可能小阳惹，這樣每次接受的概率大谍失，采樣效率更高∮ㄌ溃可取計算后得到的接受概率具體采樣過程如下：
   (1) 產生上的均勻分布隨機數快鱼，計算得到指數分布的樣本。
   (2) 再產生上的均勻分布隨機數纲岭，若抹竹，則接受，進入下一步止潮；否則拒絕窃判，到(1)步驟重新采樣。
   (3) 最后再產生上的均勻分布隨機數喇闸，若袄琳，則將轉化為，否則保持不變燃乍；由此最終得到標準正態(tài)分布的一個樣本唆樊。
   拒絕采樣法的效率取決于接受概率的大小，參考分布與目標分布越接近橘沥，則采樣效率越高窗轩。Ziggurat算法本質也是拒絕采樣，但采用多個階梯矩形來逼近目標分布座咆，更高效痢艺。

5仓洼、馬爾可夫蒙特卡洛采樣法

1. 在高維空間中，拒絕采樣和重要性重采樣經常難以尋找合適的參考分布堤舒，采樣效率低下(樣本的接受概率小或重要性權重低)色建，此時可以考慮馬爾可夫蒙特卡洛(Markov Chain Monte Carlo，MCMC)采樣法舌缤。
2. MCMC采樣法主要包括兩個MC箕戳，即蒙特卡洛法(Monte Carlo)和馬爾可夫鏈(Markov Chain)。蒙特卡洛法是指基于采樣的數值型近似求解方法国撵，而馬爾可夫鏈則用于采樣陵吸。
3. MCMC采樣法的基本思想：針對待采樣的目標分布，構造一個馬爾可夫鏈介牙，使得該馬爾可夫鏈的平穩(wěn)分布就是目標分布壮虫；然后從任何一個初始狀態(tài)出發(fā)，沿著馬爾可夫鏈進行狀態(tài)轉移环础，最終得到的狀態(tài)轉移序列會收斂到目標分布囚似，由此可以得到目標分布的一系列樣本。
4. 在實際操作中线得，核心點是如何構造合適的馬爾可夫鏈饶唤，即確定馬爾可夫鏈的狀態(tài)轉移概率，涉及馬爾可夫鏈的相關知識贯钩，如時齊性募狂、細致平衡條件、可遍歷性角雷、平穩(wěn)分布等熬尺。不同的馬爾可夫鏈對應著不同的MCMC采樣法，常見的有Metropolis-Hastings采樣法和吉布斯采樣法谓罗。
5. 與一般的蒙特卡洛算法不同粱哼，MCMC采樣法得到的樣本序列中相鄰的樣本不是獨立的，因為后一個樣本是由前一個樣本根據特定的轉移概率得到的檩咱，或者有一定概率就是前一個樣本揭措。如果僅僅是采樣，并不需要樣本之間相互獨立刻蚯。如果確實需要產生獨立同分布的樣本绊含，可以同時運行多條馬爾可夫鏈，這樣不同鏈上的樣本是獨立的炊汹」洌或者在同一條馬爾可夫鏈上每隔若干個樣本才取一個，這樣的樣本也是近似獨立的。

6充甚、貝葉斯網絡的采樣

1. 概率圖模型經常被用來描述多個隨機變量的聯合概率分布以政。貝葉斯網絡又稱信念網絡或有向無環(huán)圖模型。它是一種概率圖模型伴找，利用有向無環(huán)圖來刻畫一組隨機變量之間的條件概率分布關系盈蛮。
2. 對沒有觀測變量的貝葉斯網絡進行采樣，最簡單的方法是祖先采樣(Ancestral Sampling)技矮，核心思想是根據有向圖的順序抖誉，先對祖先節(jié)點進行采樣，只有當某個節(jié)點的所有父節(jié)點都已完成采樣衰倦，才對該節(jié)點進行采樣袒炉。根據貝葉斯網絡的全概率公式可以看出祖先采樣得到的樣本服從貝葉斯網絡的聯合概率分布。
   
   8-6 祖先采樣示意圖
   
   如果只需要對貝葉斯網絡中一部分隨機變量的邊緣分布進行采樣樊零，可以用祖先采樣先對全部隨機變量進行采樣梳杏，然后直接忽視那些不需要的變量的采樣值即可。
   例如淹接，如果需要對邊緣分布進行采樣，先用祖先采樣得到全部變量的一個樣本叛溢，如(Cloudy=T, Sprinkler=F, Rain=T, WetGrass=T)塑悼，然后忽略掉無關變量，直接把這個樣本看成Cloudy=T即可楷掉。
3. 對有觀測變量的貝葉斯網絡進行采樣厢蒜，最直接的方法是邏輯采樣，還是利用祖先采樣得到所有變量的取值烹植。如果這個樣本在觀測變量上的采樣值與實際觀測值相同斑鸦，則接受，否則拒絕草雕，重新采樣巷屿。
   
   8-6 含有觀測變量的貝葉斯網絡
   
   這種方法的缺點是采樣效率非常低，隨著觀測變量個數增加墩虹，每個變量狀態(tài)數目的上升嘱巾，邏輯采樣的效率急劇下降，實際中基本不可用诫钓。
   在實際中可以參考重要性采樣的思想旬昭，不再對觀測變量進行采樣，只對非觀測變量采樣菌湃，但是最終得到的樣本需要附一個重要性權值：其中是觀測變量集合问拘。則中采樣方法稱作似然加權采樣(Likelihood Weighted Samping)，產生的樣本權值可以用于后續(xù)的積分操作。
   
   8-7 似然加權采樣實例圖
4. 除此之外還可以用MCMC采樣法進行采樣骤坐。
   (1) 如果用Metropolis-Hastings采樣法绪杏，只需要在隨機向量(Cloudy,Rain)上選擇一個概率轉移矩陣，然后按照概率轉移矩陣不斷進行狀態(tài)轉換或油，每次轉移有一定概率的接受或拒絕寞忿，最終得到的樣本序列會收斂到目標分布。最簡單的概率轉移矩陣可以是：每次獨立地隨機選擇(Cloudy, Rain)的四種狀態(tài)之一顶岸。
   
   8-7 Metropolis-Hastings采樣法
   
   (2) 如果用吉布斯采樣法腔彰，根據條件概率(Clody|Rain, Sprinkler, WetGrass)和(Rain|Cloudy, Sprinkler, WetGrass)，每次只對(Cloudy, Rain)中的一個變量進行采樣辖佣，交替進行即可霹抛。

7、不均衡樣本集的重采樣

1. 基于數據的方法處理樣本不均衡問題卷谈，最簡單的方法是隨機采樣杯拐。采樣一般分為過采樣(Over-sampling)和欠采樣(Under-Sampling)。隨機過采樣是從少數類樣本集中隨機重復抽取樣本(有放回)以得到更多樣本世蔗；隨機欠采樣是從多數類樣本集中隨機選取較少的樣本(有放回或無放回)端逼。
   
   8-7 SMOTE算法
   
   過采樣的缺點：對少數類樣本進行了多次復制，擴大了數據規(guī)模污淋，增加了模型訓練的復雜度顶滩，容易造成過擬合。
   欠采樣的缺點：會丟棄一些樣本寸爆，可能損失部分有用信息礁鲁，造成模型只學到了整體模式的一部分。
2. SMOTE算法在過采樣時不是簡單地復制樣本赁豆，而是采用一些方法生成新樣本仅醇。SMOTE算法對少數類樣本集中的每個樣本，從它在的少數類樣本集中的近鄰中隨機選一個樣本魔种，然后在的連線上隨機選取一點作為新合成的樣本析二。
   SMOTE算法的缺點：為每個少數類樣本合成相同數量的新樣本，可能會增大類間重疊度节预，并且會生成一些不能提供有益信息的樣本甲抖。
   SMOTE算法的改進算法：Borderline-SMOTE、ADASYN等心铃。Borderline-SMOTE只給那些處在分類邊界上的少數類樣本合成新樣本准谚。ADASYN則給不同的少數類樣本合成不同個數的新樣本。此外去扣，還可以采用一些數據清理方法(如基于Tomek Links)來進一步降低合成樣本帶來的類間重疊柱衔，以得到更加良定義的類簇樊破，從而更好地訓練分類器。
3. Informed Undersampling可以解決欠采樣帶來的數據丟失問題唆铐。常見的Informed Undersampling算法有：Easy Ensemble哲戚、Balance Cascade、NearMiss艾岂、One-sided Selection等算法顺少。
   (1) Easy Ensemble：每次從多數類樣本集中隨機抽取一個子集，然后用和訓練一個分類器王浴，重復若干次脆炎，將多個分類器結果融合。
   (2) Balance Cascade：級聯結構氓辣，在每一級中從多數類中隨機抽取子集秒裕，然后用和訓練該級分類器；然后將中能夠被當前分類器正確判斷的樣本剔除掉钞啸，繼續(xù)下一級操作几蜻，重復若干次得到級聯結構，將分類器結果融合体斩。
   (3) NearMiss：利用近鄰信息挑選具有代表性的樣本梭稚。
   (4) One-sided Selection：采用數據清理技術。
   實際應用中絮吵，具體的采樣操作可能并不總是如上述幾個算法一樣弧烤，但是思路一致。例如源武，基于聚類的采樣方法，利用數據的類簇信息來指導過采樣或欠采樣操作想幻；數據擴充方法也是一種過采樣粱栖，對少數類樣本進行一些噪聲擾動或變換以構造出新樣本；Hard Negative Mining則是一種欠采樣脏毯，把比較難的樣本抽出來用于迭代分類器闹究。
4. 基于算法的處理樣本不均衡問題的方法：可以通過改變模型訓練時的目標函數(如代價敏感學習中不同類別有不同的權重)來矯正這種不平衡性；當樣本數據及其不均衡時食店，也可以將問題轉化為單類學習(one-class learning)渣淤、異常檢測(anomaly detection)等。

小結

這是本章的第二部分吉嫩，講了高斯分布的逆變換采樣和拒絕采樣价认、馬爾可夫蒙特卡洛采樣、貝葉斯網絡的采樣以及處理不均衡數據集的各種采樣方法自娩。除了SMOTE算法比較熟以外用踩，其余的又是把書抄了一遍。

結尾

如果您發(fā)現我的文章有任何錯誤，或對我的文章有什么好的建議脐彩，請聯系我碎乃！如果您喜歡我的文章，請點喜歡~*我是藍白絳惠奸，感謝你的閱讀梅誓！