1、Boosting1. 判斷題（1）Boosting和Bagging都是組合多個分類器投票的方法，二者都是根據單個分類器的正確率決定其權重。（2）在Boosting中，當訓練誤差為0時必須停止迭代，否則會發生過擬合。（3）Boosting和Bagging都可以視為是對訓練數據的重采樣，但二者的重采樣方式不同。（4）在AdaBoost算法中，所有被錯分的樣本的權重更新比例相同。（T）（5）Boosting的一個優點是不會過擬合。2. Boosting。（20分，每小題10分）考慮如圖3所示的訓練樣本，其中+和O分別表示正樣本和負樣本。圖中還給出了采用AdaBoost算法經過若干次迭代后每個樣本的權

2、重。同時圖中還給出了3個弱分類器：A、B和C。則圖3：訓練樣本及其權重，A、B和C為3個可能的弱分類器（1） 下次將選擇A、B和C等3個弱分類器的哪個弱分類器？為什么？弱分類器B的加權錯誤率最小。（2） 圖中所示權重最可能是上次采用A、B和C哪個弱分類器得到的？為什么？上一輪選擇的弱分類器在本輪中的加權錯誤率為0.5，因此上一輪的分類器是弱分類器C.3Boosting與特征選擇考慮一個文本分類問題。每個文檔用一些二值特征表示為，其中表示單詞j出現在文檔i中，否則的話。現采用AdaBoost算法進行分類，其中弱分類器為，其中j為選擇的單詞索引，為對應的文檔標簽。即每個弱分類器為每個單詞與類別的關

3、系。如有單詞”足球”，類別有運動，非運動，則我們有兩個弱分類器：l 如果文檔中出現單詞”足球”，判定該文檔為“運動”；l 如果文檔中不出現單詞”足球”，判定該文檔為“運動”；(1) 一共有多少個弱分類器？每個單詞對應兩個弱分類器，D個單詞共有2D個弱分類器。(2) Boosting可以實現特征選擇，即運行算法，被選擇的特征按其被算法選中的順序加入最終的模型。有些弱分類器可能會被選擇多次嗎？可能。Boosting算法是在假定之前的投票權重不變的情況下優化當前的，因此不是對所有的系數一起優化。因此只能通過再重新將弱分類器加入來修正之前的投票權重。(3) 互信息也可以用來特征選擇。如果我們對每個特征

4、根據其與標簽之間的互信息來排序，那么該排序會比AdaBoost的排序更有信息量嗎？不會。AdaBoost是多個弱分類器（特征）的線性組合，新的弱分類器是在考慮之前已有預測的基礎上的。而單個特征與標簽的互信息只考慮該特征本身的信息，不能發現多個特征隊線性預測的交互作用。4. 現采用AdaBoost算法來集成多個弱分類器。圖2給出了帶標簽的數據，其中輸入特征為2維，同時還給出了第一個弱分類器。每個弱分類器根據某維特征預測輸出。小箭頭為決策邊界的法線方向。初始時各樣本的權重相同。圖2: 帶標簽的數據及第一個弱分類器。箭頭方向為決策邊界的正方向。(1) 在圖2中標出根據第一個弱分類器權重會增大的樣本點

5、。錯分樣本的權重會增加。，權重更新：，錯誤分類樣本的權重：（1個），正確分類樣本的權重為：（5個）.(2) 在圖中畫出下一輪選擇的弱分類器。請給出決策邊界及其方向。如圖。(3) 第二輪弱分類器的系數會比第一次的大嗎，即? 是的。因為被第二個弱分類器分錯的樣本的權重較小（因為被第一個弱分類器分對了）5Boosting考慮下述分類問題。我們打算采用boosting來學習分類器，其中弱分類器為平行兩個坐標軸的線性分類器。請給出AdaBoost前3輪迭代的弱分類器、其對應的加權錯誤率、弱分類器的權重、樣本權重的更新。為了統一，第一輪弱分類器選擇特征x1，即為豎直線。并請給出每輪結束后的強分類器的訓練誤

6、差。6AdaBoost的損失函數(1) AdaBoost可視為最小化指數損失函數，其中為類別標簽，為弱分類器的權重。證明指數損失是0-1損失函數的上界。證明：(2) 指數損失對outliers敏感。請給出一個簡單的解決方案。由于每個被錯分的樣本的權重會增加，一種忽略outliers的方法是對樣本權重設置一個閾值，當樣本的權重超過該閾值時，認為樣本是outlier，去掉該樣本。7下圖給出了8個數據點，其中正負樣本各4個。圖中也給出了AdaBoost第一輪選擇的弱分類器h1 （弱分類器為平行坐標軸的直線）。(1) AdaBoost給弱分類器h1的權重1為多少？ (各樣本的初始權重相等，即 1/8.)(2) 不管弱分類器是什么類型，AdaBoost的訓練誤