機(jī)器學(xué)習(xí)筆記3_Adaboost

一般來說痹愚，Ensemble模型適合于過擬合的模型，包括bagging和boosting.

3.1 Bagging

其中Bagging是單獨(dú)訓(xùn)練每個分類器古劲，然后用平均或者投票的方法組合袱贮，boosting的方法則是分類器之前存在強(qiáng)依賴腮鞍，前一個分類器預(yù)測的解構(gòu)會影響后一個分類器。隨機(jī)森林就是DT的bagging耗跛。
在相同的深度下吆寨，隨機(jī)森林并不會比決策樹好很多，但會讓分類的結(jié)果更平滑

3.2 Boosting

boosting的目的是用迭代的方法提高弱分類器的性能(improving weak classifier)

boosting的架構(gòu)如下：
首先獲取到第一個分類器 $f_1(x)$ 拧廊，然后用第二個分類器 $f_2(x)$ 去help $f_1(x)$ ,如果 $f_2(x)$ 與 $f_1(x)$ 很像监徘，則可能對幫助的有限，我們更希望 $f_2(x)$ 是 $f_1(x)$ 的補(bǔ)充吧碾。bagging的時候不同分類器用的dataset的原有數(shù)據(jù)集重采樣得到的凰盔，而在boosting時，不同dataset用到的數(shù)據(jù)集則是原數(shù)據(jù)集然后乘一個weight $u^{(i)}$ ,這樣總的損失函數(shù)就是

$L(f) = \sum_{i=1}^{m} u^{(i)} l(f(x^{(i)}),\hat{y}^{(i)})$

其中 $l(f(x^{(i)}),\hat{y}^{(i)})$ 代表任意一種衡量預(yù)測值和真實(shí)值的損失函數(shù)倦春。
adaboost的思路就是户敬，假設(shè)有k個弱分類器 $f_1,f_2,...,f_k$ ，先用一組帶權(quán)重的數(shù)據(jù)集 $\{x^{(i)},\hat{y}^{(i)},u^{(i)}_1\}$ 訓(xùn)練 $f_1$ ,然后更改每組訓(xùn)練數(shù)據(jù)的權(quán)重得到 $u^{(i)}_2$ 睁本，這時新的帶權(quán)重的數(shù)據(jù)集 $\{x^{(i)},\hat{y}^{(i)},u^{(i)}_2\}$ 在 $f_1$ 上的performance會變差尿庐，這時候訓(xùn)練 $f_2$ 使得新的數(shù)據(jù)集在 $f_2$ 上的performance變好。所謂表現(xiàn)差呢堰，就是正確率低抄瑟，錯誤率高，用下邊的式子來計(jì)算錯誤率：

$\epsilon_1 = \frac{ \sum_{i=1}^{m}u^{(i)}_1\delta(f_1(x^{(i)})\not=\hat{y}^{(i)})}{Z_1}$

其中 $\delta(f_1(x^{(i)})\not=\hat{y}^{(i)})$ 為符號函數(shù)枉疼，即兩者不相等時取1皮假，否則取0, $Z_1$ 則表示歸一化權(quán)重：
$Z_1 = \sum_{i=1}^{m}u^{(i)}_1$
這是因?yàn)槊看斡?xùn)練的數(shù)據(jù)集所用的權(quán)重加起來并不為1，因此需要?dú)w一化骂维。這個式子看起來并不太好理解惹资，為什么能表示錯誤率呢？我們舉個簡單的例子航闺，假設(shè)權(quán)重為1褪测，這時候 $Z_1=m$ ，也就是 $m$ 個樣本潦刃，上式的分母就是 $m$ 侮措，假設(shè)分類器 $f_1$ 讓 $t$ 個樣本分類錯誤，這時上邊 $\epsilon_1$ 表達(dá)式的分子就是 $t$ 福铅， $\frac{t}{m}$ 當(dāng)然就是錯誤率啦萝毛。另一個角度也可以從概率的角度理解， $\frac{u^{(i)}_1}{Z_1}$ 可以表示對于每個樣本預(yù)測錯誤的概率滑黔，然后加權(quán)平均就是第一個分類器的錯誤率啦（這種解釋有點(diǎn)粗糙笆包，僅幫助理解）环揽。
注意，對于二分類庵佣，錯誤率 $\epsilon_1<0.5$ 歉胶，多分類的話 $\epsilon_1<1/K$ ，下邊的公式也只介紹二類的情況巴粪。接下來把數(shù)據(jù)集從權(quán)重從 $u^{(i)}_1$ 變到 $u^{(i)}_2$ 通今，使得
$\frac{ \sum_{i=1}^{m}u^{(i)}_2\delta(f_1(x^{(i)})\not=\hat{y}^{(i)})}{Z_2}=0.5$
這是因?yàn)椋顮€的二分類器肛根，隨機(jī)猜也有50%的準(zhǔn)確率辫塌，我們要使 $f_1$ 的性能變差，就讓 $f_1$ 對 $u^{(i)}_2$ 權(quán)重的訓(xùn)練數(shù)據(jù) $\{x^{(i)},\hat{y}^{(i)},u^{(i)}_2\}$ 的錯誤率升到0.5即可派哲。

那如何讓 $f_1$ 錯誤率提升呢臼氨，也就是讓 $f_1$ 分類效果變差呢？很簡單的方法就是芭届，讓分類器 $f_1$ 對于分類正確的那些數(shù)據(jù)储矩，我們給它更少的權(quán)重，對于分類錯誤的數(shù)據(jù)則給更大的權(quán)重褂乍。一個形象的例子如下：

在這里插入圖片描述

假設(shè)剛開始的權(quán)重都是1持隧，其中第1，3逃片，4組訓(xùn)練數(shù)據(jù)分類正確屡拨，那的錯誤率就是0.25，然后呢褥实，對于分類正確的數(shù)據(jù)洁仗，我們把訓(xùn)練集數(shù)據(jù)要乘的權(quán)重調(diào)低到，把分類錯誤的第二組數(shù)據(jù)的權(quán)重調(diào)高到這時候的錯誤率就升高到0.5了性锭。總結(jié)規(guī)律就是：

如果 $f_1$ 能正確分類某個數(shù)據(jù)叫胖，也就是 $f_1(x^{i})\not =\hat{y}^{(i)}$ 草冈，則把新訓(xùn)練數(shù)據(jù)的權(quán)重 $u^{(i)}_2$ 減小為原來的權(quán)重除以 $d_1$ : $u^{(i)}_2=u^{(i)}_1/d_1$
如果 $f_1$ 錯誤分類某個數(shù)據(jù)，也就是 $f_1(x^{i})=\hat{y}^{(i)}$ 瓮增，則把新訓(xùn)練數(shù)據(jù)的權(quán)重 $u^{(i)}_2$ 增大為原來的權(quán)重乘 $d_1$ : $u^{(i)}_2=u^{(i)}_1 d_1$
那 $d_1$ 怎么求呢怎棱？
$\frac{ \sum_{i=1}^{m}u^{(i)}_2\delta(f_1(x^{(i)})\not=\hat{y}^{(i)})}{Z_2}=0.5$
其實(shí)就是把上式中 $u^{(i)}_2$ 分類錯誤的展開成 $u^{(i)}_1d_1$ ，分類正確的展開乘 $u^{(i)}_1/d_1$ 然后解方程即可绷跑，經(jīng)過一系列化簡可以得到：
$\sum_{f_1(x^{(i)})=\hat{y}^{(i)}} u^{(i)}_1/d_1=\sum_{f_1(x^{(i)})\not=\hat{y}^{(i)}} u^{(i)}_1d_1$

也就是那些分類錯誤的數(shù)據(jù)的權(quán)重的和要等于分類正確的數(shù)據(jù)的權(quán)重的和拳恋，在經(jīng)過推導(dǎo)得到 $d_1$ 為：
$d_1 = \sqrt{\frac{1-\epsilon_1}{\epsilon_1}}>1$
從上邊可以看出，要更新數(shù)據(jù)的權(quán)重時砸捏，對于上一輪迭代分類錯誤的數(shù)據(jù)谬运，我們要增加權(quán)重也就是乘一個數(shù)隙赁，對于上一輪迭代分類正確的數(shù)據(jù)，我們要減小權(quán)重也就是除一個數(shù)梆暖，有沒有辦法都用乘法表示呢伞访？只需要把權(quán)重取對數(shù)即可，因?yàn)槿?shù)后原來的函數(shù)仍然保持之前的單調(diào)性轰驳，除此之外厚掷，取完對數(shù)，之前的乘除運(yùn)算就可以變成加減運(yùn)算级解。上述 $d_1$ 取對數(shù)后就變成：
$a_1 = \log d_1 = \log (\sqrt{\frac{1-\epsilon_1}{\epsilon_1}})= \frac{1}{2}\log \frac{1-\epsilon_1}{\epsilon_1}$
這樣更新的權(quán)重就都可以用乘法來表示

如果 $f_1$ 能正確分類某個數(shù)據(jù)冒黑，權(quán)重 $u^{(i)}_2$ 減小為 $u^{(i)}_2=u^{(i)}_1 e^{-a_1}$
如果 $f_1$ 錯誤分類某個數(shù)據(jù)，權(quán)重 $u^{(i)}_2$ 增加為 $u^{(i)}_2=u^{(i)}_1 e^{a_1}$
用一個式子表示 $u^{(i)}_2$ 的更新就是
$u^{(i)}_2 = u^{(i)}_1 \times \exp(-\hat{y}^{(i)}f_1(x^{(i)})a_1)$

當(dāng)預(yù)測值和真實(shí)值相同時勤哗， $-\hat{y}^{(i)}f_1(x^{(i)})=-1$ 否則取1

綜上抡爹，二分類的Adaboost算法就可以概況為：
輸入： $\{(x^{(1)},\hat{y}^{(1)},u^{(1)}_1),（x^{(2)},\hat{y}^{(2)},u^{(2)}_1),...,（x^{(m)},\hat{y}^{(m)},u^{(m)}_1)\}$
其中 $y^{(i)}=\pm 1$ , 初始權(quán)重為 $u^{(i)}_1=1$

對于弱分類器 $t=1,2,...,T$
a. 用帶權(quán)重 $\{u^{(1)}_1,u^{(2)}_1,...,u^{(m)}_1\}$ 的數(shù)據(jù)訓(xùn)練弱分類器t
b. 計(jì)算第t個弱分類器的分類錯誤率 $\epsilon_t$ (公式見上)
c. 用分類錯誤率計(jì)算權(quán)重要乘的數(shù) $a_t$
d. 用 $u^{(i)}_2 = u^{(i)}_1 \times \exp(-\hat{y}^{(i)}f_1(x^{(i)})a_1)$ 更新數(shù)據(jù)集的權(quán)重
訓(xùn)練得到一系列的弱分類器 $f_1,f_2,...,f_T$
最后的強(qiáng)分類器就為：
$H(x) = sign(\sum_{t=1}^T a_t f_t(x))$
這里的 $a_t$ 就是前邊用錯誤率計(jì)算出的 $a_t$

組合的策略從直觀上解釋就是錯誤率低的分類器權(quán)重更高，反之權(quán)重更低俺陋。

至此adaboost講完

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末豁延，一起剝皮案震驚了整個濱河市，隨后出現(xiàn)的幾起案子腊状，更是在濱河造成了極大的恐慌诱咏，老刑警劉巖，帶你破解...
沈念sama閱讀 206,214評論 6贊 481
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件缴挖，死亡現(xiàn)場離奇詭異袋狞，居然都是意外死亡，警方通過查閱死者的電腦和手機(jī)映屋，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 88,307評論 2贊 382
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門苟鸯，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人棚点，你說我怎么就攤上這事早处。” “怎么了瘫析？”我有些...
開封第一講書人閱讀 152,543評論 0贊 341
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵砌梆，是天一觀的道長。經(jīng)常有香客問我贬循，道長咸包，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 55,221評論 1贊 279
?港島之戀（遺憾婚禮）
正文為了忘掉前任杖虾，我火速辦了婚禮烂瘫，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘奇适。我一直安慰自己坟比，他們只是感情好芦鳍，可當(dāng)我...
茶點(diǎn)故事閱讀 64,224評論 5贊 371
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布。她就那樣靜靜地躺著温算，像睡著了一般怜校。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上注竿，一...
開封第一講書人閱讀 49,007評論 1贊 284
城市分裂傳說
那天茄茁，我揣著相機(jī)與錄音，去河邊找鬼巩割。笑死裙顽，一個胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的宣谈。我是一名探鬼主播愈犹，決...
沈念sama閱讀 38,313評論 3贊 399
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼闻丑！你這毒婦竟也來了漩怎？” 一聲冷哼從身側(cè)響起，我...
開封第一講書人閱讀 36,956評論 0贊 259
萬榮殺人案實(shí)錄
序言：老撾萬榮一對情侶失蹤嗦嗡，失蹤者是張志新（化名）和其女友劉穎勋锤，沒想到半個月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體侥祭，經(jīng)...
沈念sama閱讀 43,441評論 1贊 300
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡叁执，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 35,925評論 2贊 323
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時候發(fā)現(xiàn)自己被綠了矮冬。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片谈宛。...
茶點(diǎn)故事閱讀 38,018評論 1贊 333
活死人
序言：一個原本活蹦亂跳的男人離奇死亡，死狀恐怖胎署，靈堂內(nèi)的尸體忽然破棺而出吆录，到底是詐尸還是另有隱情，我是刑警寧澤琼牧，帶...
沈念sama閱讀 33,685評論 4贊 322
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布径筏，位于F島的核電站，受9級特大地震影響障陶，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜聊训，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,234評論 3贊 307
男人毒藥：我在死后第九天來索命
文/蒙蒙一抱究、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧带斑，春花似錦鼓寺、人聲如沸勋拟。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,240評論 0贊 19
一樁弒父案妈候，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽敢靡。三九已至，卻和暖如春苦银，著一層夾襖步出監(jiān)牢的瞬間啸胧，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 31,464評論 1贊 261
情欲美人皮
我被黑心中介騙來泰國打工幔虏，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留纺念，地道東北人。一個月前我還...
沈念sama閱讀 45,467評論 2贊 352
代替公主和親
正文我出身青樓想括，卻偏偏與公主長得像陷谱，于是被迫代替她去往敵國和親。傳聞我的和親對象是個殘疾皇子瑟蜈，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 42,762評論 2贊 345

機(jī)器學(xué)習(xí)筆記3_Adaboost

3.1 Bagging

3.2 Boosting

推薦閱讀更多精彩內(nèi)容