集成學(xué)習(xí)（

）計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院理論出發(fā)點(diǎn)和Boosting算法AdaBoost算法Bagging算法選擇性集成總結(jié)課程內(nèi)容No

Free

Lunch

TheoremSuppose

we

make

no

prior

assumptions

aboutthe

nature

of

the

classification

task.

Can

weexpect

any

classification

method

to

be

superioror

inferior

overall?No

Free

Lunch

Theorem:

Answer

to

abovequestion:

NOIf

goal

is

to

obtain

good

generalizationperformance,

there

is

no

context-independentor

usage-independent

reasons

to

favor

oneNo

Free

Lunch

TheoremIf

one

algorithm

seems

to

outperform

another

ina

particular

situation,

it

is

a

consequenceof

its

fitto

a

particular

pattern

recognition

problem.For

a

new

classification

problem,

what

mattersmost:

prior

information,

data

distribution,

size

oftraining

set,

cost

fn.No

Free

Lunch

TheoremIt

is

the

assumptions

about

the

learningalgorithm

that

are

importantEven

popular

algorithms

will

perform

poorlyon

some

problems,

where

the

learningalgorithm

and

data

distribution

do

not

matchwellIn

practice,

experience

with

a

broad

range

oftechniques

is

the

best

insurance

for

solvingarbitrary

new

classification

problemsBias

and

VarianceNo

“best

classifier”

in

generalNecessity

for

exploring

a

variety

of

methodsHow

to

evaluate

if

the

learning

algorithm

“matches”

theclassification

problemBias:

measures

the

quality

of

thematchHigh-bias

implies

poor

matchVariance:

measures

the

specificity

of

the

matchHigh-variance

implies

a

weak

matchBias

and

variance

arenot

independent

of

each

otherBias

and

VarianceGiven

true

function

F(x)Estimated

function

g(x;

D)

from

a

training

set

DDependence

of

function

g

on

training

set

D.Each

training

setgives

an

estimate

of

error

in

the

fitTaking

average

over

all

training

sets

of

size

n,

MSE

isAverage

error

that

g(x;D)makes

in

fitting

F(x)Difference

between

expectedDifference

between

observedvalue

and

expected

valueLow

bias:

o age,

we

willaccura y

estimate

F

from

DLow

variance:

Estimate

of

F

doesnot

change

much

with

different

DMotivation泛化能力是機(jī)器學(xué)習(xí)關(guān)注的一個(gè)根本問(wèn)題泛化能力(generalization ability)表征了學(xué)習(xí)系統(tǒng)對(duì)新事件的適用性泛化能力越強(qiáng)越好提高泛化能力是機(jī)器學(xué)習(xí)的追求決策，便是部分的日常生活中，所謂的利用了這種想法。譬如選總統(tǒng)，每個(gè)人都以自己的考慮，投下自己的一票，但最后由多數(shù)人選出的總統(tǒng)，似乎應(yīng)該好于由一個(gè)人指定的總統(tǒng)。28【集成學(xué)習(xí)：

】在機(jī)器學(xué)習(xí)中，直接建立一個(gè)高性能的分類(lèi)器是很

的。但是，如果能找到一系列性能較差的分類(lèi)器，并把它們集成起來(lái)的話(huà)，也許就能得到更好的分類(lèi)器。集成學(xué)習(xí)，就是一種把輸入送入多個(gè)學(xué)習(xí)器，再通過(guò)某種辦法把學(xué)習(xí)的結(jié)果集成起來(lái)的辦法。這每一個(gè)學(xué)習(xí)器，也就相應(yīng)的被稱(chēng)為“弱學(xué)習(xí)器”。集成學(xué)習(xí)最早也叫做“Committee

VotingMethod”，也就是因?yàn)樗屯镀钡倪^(guò)程相似。29【集成學(xué)習(xí)：】Classifier

ensembleΣαihi(x)hn(x)h2(x)h1(x)InputvectorClassifier

1Classifier

2……Classifier

NCombine

ClassifiersOutputx【集成學(xué)習(xí)：圖示】問(wèn)題問(wèn)題集成學(xué)習(xí)集成學(xué)習(xí)(Ensemble

Learning)是一種機(jī)器學(xué)習(xí)范式，它使用多個(gè)學(xué)習(xí)器來(lái)解決同一個(gè)問(wèn)題…

...…

...由于集成學(xué)習(xí)可以有效地提高學(xué)習(xí)系統(tǒng)的泛化能力，因此它成為國(guó)際機(jī)器學(xué)習(xí)界的研究熱點(diǎn)“當(dāng)前機(jī)器學(xué)習(xí)四大研究方向之首”[T.G.

Dietterich,AIMag97]Example:

Weather

ForecastReality1XXX2XXX3XXX4XX5XXCombine期望結(jié)果1(精度33.3%)2(精度33.3%)3(精度33.3%)集成(精度33.3%)投票期望結(jié)果1(精度33.3%)2(精度33.3%)3(精度33.3%)集成(精度0%)投票必須有差異 精度不能太低E

E

A

[A.

Krogh

&

J.

Vedelsby,NIPS94]學(xué)習(xí)器越精確、差異越大，集成越好【如何構(gòu)建好的集成】【集成學(xué)習(xí)：如何構(gòu)造？】辦法就是改變訓(xùn)練集。通常的學(xué)習(xí)算法，根據(jù)訓(xùn)練集的不同，會(huì)給出不同的學(xué)習(xí)器。這時(shí)就可以通過(guò)改變訓(xùn)練集來(lái)構(gòu)造不同的學(xué)習(xí)器。然后再把它們集成起來(lái)。【帶權(quán)的采樣:

】通過(guò)給訓(xùn)練數(shù)據(jù)賦以不同的權(quán)，實(shí)際上使得每個(gè)學(xué)習(xí)器關(guān)注訓(xùn)練集中的某一部分，這也符合

最初

投票的想法。直觀上，每個(gè)學(xué)習(xí)器關(guān)注訓(xùn)練集中的某一部分，很多個(gè)訓(xùn)練集應(yīng)該可以覆蓋訓(xùn)練集中的大部分，只要巧妙的選擇平均的權(quán)，就可以得到更好的學(xué)習(xí)效果。【用多個(gè)學(xué)習(xí)器覆蓋樣本空間】【分類(lèi)設(shè)計(jì)的重采樣技術(shù)】分類(lèi)器設(shè)計(jì)的重采樣技術(shù)也被稱(chēng)為“自適應(yīng)的權(quán)值重置和組合（arcing,adaptive

reweightingand

combining）；這類(lèi)方法的主要思想是利用同一個(gè)訓(xùn)練樣本集合構(gòu)造多個(gè)分類(lèi)器，然后以某種方式將這些分類(lèi)器組一個(gè)分類(lèi)器；主要方法包括：bagging算法和boosting算法【集成學(xué)習(xí)：如何構(gòu)造？】

一般選定

平均的方法來(lái)構(gòu)造集成學(xué)習(xí)的最終學(xué)習(xí)器。但是里面的每一個(gè)Classifier

i怎樣做呢？有一些研究，是針對(duì)每個(gè)學(xué)習(xí)器都不同構(gòu)的情況，比如識(shí)別一個(gè)人，一個(gè)學(xué)習(xí)器考慮臉，另一個(gè)考慮步態(tài)，另一個(gè)考慮

。這種研究通常稱(chēng)為Information

Fusion，不在

今天

的范疇。

今天

的，是用同樣的學(xué)習(xí)算法來(lái)構(gòu)造不同的弱學(xué)習(xí)器的方法。3839【集成學(xué)習(xí)：如何構(gòu)造？】辦法就是改變訓(xùn)練集。通常的學(xué)習(xí)算法，根據(jù)訓(xùn)練集的不同，會(huì)給出不同的學(xué)習(xí)器。這時(shí)就可以通過(guò)改變訓(xùn)練集來(lái)構(gòu)造不同的學(xué)習(xí)器。然后再把它們集成起來(lái)。40【隨機(jī)采樣】在原來(lái)的訓(xùn)練集上隨機(jī)采樣，可以得到新的訓(xùn)練集。41可以給訓(xùn)練集里的每個(gè)元素不采樣時(shí)，同的權(quán)。權(quán)值可以通過(guò)上一次訓(xùn)練的結(jié)果來(lái)確定。【帶權(quán)的采樣】42通過(guò)給訓(xùn)練數(shù)據(jù)賦以不同的權(quán)，實(shí)際上使得每個(gè)學(xué)習(xí)器關(guān)注訓(xùn)練集中的某一部分，這也符合最初投票的想法。直觀上，每個(gè)學(xué)習(xí)器關(guān)注訓(xùn)練集中的某一部分，很多個(gè)訓(xùn)練集應(yīng)該可以覆蓋訓(xùn)練集中的大部分，只要巧妙的選擇平均的權(quán)，就可以得到更好的學(xué)習(xí)效果。【帶權(quán)的采樣:】43【集成學(xué)習(xí)：評(píng)述】集成學(xué)習(xí)實(shí)際上代表了一種與傳統(tǒng)不同的思維理念。傳統(tǒng)的機(jī)器學(xué)

般都自認(rèn)為是單模型的，對(duì)于模型的分析總是在整體上完成。Rosenblatt：PerceptronRumelhart:

BPVapnik:

SVM但是，所有這些模型其實(shí)都可以看作是一種平均的多模型。44【集成學(xué)習(xí)：評(píng)述】所以，當(dāng)然應(yīng)該考慮研究一般的多模型。實(shí)際上，從90年始，對(duì)集成學(xué)習(xí)的研究取得了一系列突破進(jìn)展。在算法上，集成學(xué)習(xí)的典型代表AdaBoost算法，已經(jīng)成為與SVM并立的方法。而且，集成學(xué)習(xí)比SVM更為一般，可能可以有更廣闊的前景。45【泛化能力】泛化：generalization泛化能力越強(qiáng)，處理新數(shù)據(jù)的能力越好泛化能力是機(jī)器學(xué)習(xí)關(guān)注的基本問(wèn)題之一提高泛化能力是 的追求46集成學(xué)習(xí)（Ensemble

Learning）是一種機(jī)器學(xué)習(xí)范式，它使用多個(gè)（通常是同質(zhì)的）學(xué)習(xí)器來(lái)解決同一個(gè)問(wèn)題問(wèn)題…...…...問(wèn)題集成學(xué)習(xí)中使用的多個(gè)學(xué)習(xí)器稱(chēng)為

學(xué)習(xí)器當(dāng) 學(xué)習(xí)器均為決策樹(shù)時(shí)，稱(chēng)為“決策樹(shù)集成”當(dāng) 學(xué)習(xí)器均為神經(jīng)網(wǎng)絡(luò)時(shí)，稱(chēng)為“神經(jīng)網(wǎng)絡(luò)集成”……

……【集成學(xué)習(xí)】47由于集成學(xué)習(xí)技術(shù)可以有效地提高學(xué)習(xí)系統(tǒng)的泛化能力，因此它成為國(guó)際機(jī)器學(xué)習(xí)界的研究熱點(diǎn)，并被國(guó)際T.G.

Dietterich

稱(chēng)為當(dāng)前機(jī)器學(xué)習(xí)四大研究方向之首[T.G.Dietterich,

AIMag97]問(wèn)題：對(duì)20維超立方體空間中的區(qū)域分類(lèi)左圖中縱軸為錯(cuò)誤率從上到下的四條線(xiàn)分別表示：平均神經(jīng)網(wǎng)絡(luò)錯(cuò)誤率最好神經(jīng)網(wǎng)絡(luò)錯(cuò)誤率兩種神經(jīng)網(wǎng)絡(luò)集成的錯(cuò)誤率令人驚奇的是，集成的錯(cuò)誤率比最好的 還低[L.K.

Hansen

&P.

Salamon,

TPAMI90]【集成學(xué)習(xí)的重要性】48只要能用到機(jī)器學(xué)習(xí)的地方，就能用到集成學(xué)習(xí)【集成學(xué)習(xí)的應(yīng)用】集成學(xué)習(xí)技術(shù)已經(jīng)在行星探測(cè)、 波分析、Web信息過(guò)濾、生物特征識(shí)別、計(jì)算機(jī)輔助醫(yī)療等眾多領(lǐng)域得到了廣泛的應(yīng)用49的在意味著：時(shí)需要更大的計(jì)算開(kāi)銷(xiāo)，因?yàn)橐?jì)算的更大的

開(kāi)銷(xiāo)，因?yàn)橛?/p>

的

需要保存的增加將使得

間的差異越來(lái)越難以獲得【

越多越好嗎？】既然多個(gè)

的集成比單個(gè)

更好，那么是不是 越多越好?50【分類(lèi)設(shè)計(jì)的重采樣技術(shù)】分類(lèi)器設(shè)計(jì)的重采樣技術(shù)也被稱(chēng)為“自適應(yīng)的權(quán)值重置和組合（arcing,adaptive

reweightingand

combining）；這類(lèi)方法的主要思想是利用同一個(gè)訓(xùn)練樣本集合構(gòu)造多個(gè)分類(lèi)器，然后以某種方式將這些分類(lèi)器組一個(gè)分類(lèi)器；主要方法包括：bagging算法和boosting算法理論出發(fā)點(diǎn)和Boosting算法AdaBoost算法bagging算法選擇性集成總結(jié)課程內(nèi)容研究背景1988年,Kearns等在研究PAC學(xué)習(xí)模型時(shí)提出了一個(gè)有趣的問(wèn)題:“弱可學(xué)習(xí)是否等價(jià)

可學(xué)習(xí)?”即Boosting問(wèn)題。如果這一問(wèn)題有肯定的回答,意味著只要找到比隨機(jī)猜測(cè)略好的弱學(xué)習(xí)算法,以將其提升為強(qiáng)學(xué)習(xí)算法,而不必直接去尋找通常情況下很難獲得的強(qiáng)學(xué)習(xí)算法,這對(duì)學(xué)習(xí)算法的設(shè)計(jì)有著重要的意義。可以通過(guò)一弱學(xué)習(xí)定理：只要找到比隨機(jī)猜測(cè)略好的學(xué)習(xí)算法，那么定的方式，構(gòu)造出強(qiáng)學(xué)習(xí)算法。意義：不用直接尋找通常情況下很難獲得的強(qiáng)學(xué)習(xí)算法，迂回

，通過(guò)找弱學(xué)習(xí)算法來(lái)集成。Boosting背景來(lái)源于:PAC-Learning

ModelValiant 1984

-11提出問(wèn)題:強(qiáng)學(xué)習(xí)算法:準(zhǔn)確率很高的學(xué)習(xí)算法弱學(xué)習(xí)算法:準(zhǔn)確率不高,僅比隨機(jī)猜測(cè)略好是否可以將弱學(xué)習(xí)算法提升為強(qiáng)學(xué)習(xí)算法Boosting背景最初的boosting算法Schapire

1989AdaBoost算法Freund

and

Schapire

1995Boosting—concepts(3)Boosting弱學(xué)習(xí)機(jī)（weak

learner):對(duì)一定分布的訓(xùn)練樣本給出假設(shè)（僅僅強(qiáng)于隨機(jī)猜測(cè)）根據(jù)有云猜測(cè)可能會(huì)下雨強(qiáng)學(xué)習(xí)機(jī)（strong

learner):根據(jù)得到的弱學(xué)習(xí)機(jī)和相應(yīng)的權(quán)重給出假設(shè)（最大程度上符合實(shí)際情況：almost

perfect

expert)根據(jù)CNN,ABC,CBS以往的 表現(xiàn)及實(shí)際天氣情況作出綜合準(zhǔn)確的天氣弱學(xué)習(xí)機(jī)強(qiáng)學(xué)習(xí)機(jī)Boosting流程(loop1)強(qiáng)學(xué)習(xí)機(jī)弱學(xué)習(xí)機(jī)原始訓(xùn)練集后的訓(xùn)練集后的假設(shè)X>1?1:-1弱假設(shè)Boosting流程(loop2)強(qiáng)學(xué)習(xí)機(jī)弱學(xué)習(xí)機(jī)原始訓(xùn)練集后的訓(xùn)練集后的假設(shè)Y>3?1:-1弱假設(shè)2020/11/16高級(jí)人工智能58Boosting流程(loop3)強(qiáng)學(xué)習(xí)機(jī)弱學(xué)習(xí)機(jī)原始訓(xùn)練集后的訓(xùn)練集后的假設(shè)Z>7?1:-1弱假設(shè)Boosting過(guò)程:在一定的權(quán)重條件下訓(xùn)練數(shù)據(jù)，得出分類(lèi)法Ct根據(jù)Ct的錯(cuò)誤率調(diào)整權(quán)重Set

ofweightedinstancesClassifier

Cttrain

classifieradjust

weights流程描述Step1:原始訓(xùn)練集輸入，帶有原始分布Step2:給出訓(xùn)練集中各樣本的權(quán)重Step3:

將改變分布后的訓(xùn)練集輸入已知的弱學(xué)習(xí)機(jī)，弱學(xué)習(xí)機(jī)對(duì)每個(gè)樣本給出假設(shè)Step4:

對(duì)此次的弱學(xué)習(xí)機(jī)給出權(quán)重Step5:

轉(zhuǎn)到Step2,

直到循環(huán)到達(dá)一定次數(shù)或者某度量標(biāo)準(zhǔn)符合要求Step6:

將弱學(xué)習(xí)機(jī)按其相應(yīng)的權(quán)重 組合形成強(qiáng)學(xué)習(xí)機(jī)思想樣本的權(quán)重沒(méi)有先驗(yàn)知識(shí)的情況下，初始的分布應(yīng)為等概分布，也就是訓(xùn)練集如果有N個(gè)樣本，每個(gè)樣本的分布概率為1/N每次循環(huán)一后提高錯(cuò)誤樣本的分布概率，分錯(cuò)樣本在訓(xùn)練集中所占權(quán)重增大，使得下一次循環(huán)的弱學(xué)習(xí)機(jī)能夠集中力量對(duì)這些錯(cuò)誤樣本進(jìn)行判斷。弱學(xué)習(xí)機(jī)的權(quán)重準(zhǔn)確率越高的弱學(xué)習(xí)機(jī)權(quán)重越高循環(huán)控制：損失函數(shù)達(dá)到最小在強(qiáng)學(xué)習(xí)機(jī)的組合中增加一個(gè)的弱學(xué)習(xí)機(jī)，使準(zhǔn)確率提高，損失函數(shù)值減小。簡(jiǎn)單問(wèn)題演示（Boosting訓(xùn)練過(guò)程）++--+--

+-++-++--++--++--loop1Weak

learner1(y=0.5)loop2

Weak

learner2(x=0.7)loop3Weak

learner3(y=0.4)loop4

Weak

learner4(x=0.6)training

set等概分布strong

learnerw1*(y>0.5?1:-1)

+

w2*(x<0.7?1:-1)

+

w3*(y<0.4?1:-1)

+

w4*(x>0.6?1:-1)算法—問(wèn)題描述訓(xùn)練集{(x1,y1),(x2,y2),…,(xN,yN)}xi

Rm,

yi

{-1,+1}Dt為第t次循環(huán)時(shí)的訓(xùn)練樣本分布（每個(gè)樣本在訓(xùn)練集中所占的概率，Dt總和應(yīng)該為1）ht:X{-1,+1}

為第t次循環(huán)時(shí)的Weak

learner，對(duì)每個(gè)樣本給出相應(yīng)的假設(shè)，應(yīng)該滿(mǎn)足強(qiáng)于隨機(jī)猜測(cè)：為t次循環(huán)得到的Strong

learner12[

y

h

(x)]

Pt(

x,

y)Dtwt為ht的權(quán)重t?i1Ht

(i

)

sign

(

wi

ht

(i

))算法—樣本權(quán)重思想：提高分錯(cuò)樣本的權(quán)重?反映了strong

learner對(duì)樣本的假設(shè)是否正確采用什么樣的函數(shù)形式？yi

Ht(i

)i

t

iright

0

wrongy

H

(

)

0exp

yi

Ht(i

)算法—弱學(xué)習(xí)機(jī)權(quán)重思想：錯(cuò)誤率越低，該學(xué)習(xí)機(jī)的權(quán)重應(yīng)該越大為學(xué)習(xí)機(jī)的錯(cuò)誤概率采用什么樣的函數(shù)形式？和指數(shù)函數(shù)遙相呼應(yīng)：tt

P

[

y

h

(x)](

x,

y)D?t

t

1

t

wt

ln12Boosting算法的發(fā)展歷史Boosting算法(提升算法)是一種把若干個(gè)弱分類(lèi)器整合為一個(gè)強(qiáng)分類(lèi)器的方法。Boosting算法存在的幾個(gè)問(wèn)題：如何調(diào)整訓(xùn)練集，使得在訓(xùn)練集上訓(xùn)練的弱分類(lèi)器得以進(jìn)行。如何將訓(xùn)練得到的各個(gè)弱分類(lèi)器

形成強(qiáng)分類(lèi)器。需要預(yù)先知道弱學(xué)習(xí)算法學(xué)習(xí)正確率的下限。即弱分類(lèi)器的誤差。理論出發(fā)點(diǎn)和Boosting算法AdaBoost算法Bagging算法隨機(jī)森林選擇性集成總結(jié)課程內(nèi)容AdaBoost算法的引入AdaBoost算法簡(jiǎn)介AdaBoost算法流程圖AdaBoost實(shí)例：二元分類(lèi)缺點(diǎn)和不足總結(jié)匯報(bào)提綱針對(duì)以上幾個(gè)問(wèn)題，AdaBoost算法進(jìn)行了調(diào)整：使用

后選取的訓(xùn)練數(shù)據(jù)代替隨機(jī)選取的訓(xùn)練樣本，這樣將訓(xùn)練的焦點(diǎn)集中在比較難分的訓(xùn)練數(shù)據(jù)樣本上。將弱分類(lèi)器 ，使用

的投票機(jī)制代替平均投票機(jī)制。讓分類(lèi)效果好的弱分類(lèi)器具有較大的權(quán)重，而分類(lèi)效果差的分類(lèi)器具有較小的權(quán)重。不需預(yù)估弱學(xué)習(xí)器的正確下限。AdaBoost算法的引入AdaBoost(AdaptiveBoost)算法是一種把若干個(gè)弱分類(lèi)器整合為一個(gè)強(qiáng)分類(lèi)器的自適應(yīng)提升算法。自適應(yīng)體現(xiàn)一輪分類(lèi)器分錯(cuò)的樣本會(huì)被增強(qiáng)，用來(lái)訓(xùn)練下一個(gè)分類(lèi)器AdaBoost算法簡(jiǎn)介AdaBoost算法流程圖循環(huán)迭代多次：尋找當(dāng)前分布下的最優(yōu)弱分類(lèi)器計(jì)算弱分類(lèi)器帶權(quán)分類(lèi)誤差更新樣本分布聚合多次訓(xùn)練的弱分類(lèi)器

t=PrxDt,yI[ht(x)

y];Input:數(shù)據(jù)集D={(x1,y1),(x2,y2),……,xm,ym)};循環(huán)次數(shù)：T；基學(xué)習(xí)算法；for

t

1，……，T

:ht=

(D,Dt);//從D中利用分布Dt訓(xùn)練學(xué)習(xí)器ht2

t=

Ln(

tif

t>0.5,

then

break;1

1

t

);exp(

t)exp(

t)Dt+1(i)=Dt

(i)

//計(jì)算學(xué)習(xí)器ht的帶權(quán)分類(lèi)誤差//如果此學(xué)習(xí)器誤差大于0.5，算法失敗//計(jì)算此學(xué)習(xí)器的權(quán)重endTmif

ht(xi)=yi

if

ht(xi)

yi//更新樣本分布Zt

Dt

1(i);

Dt

1(i)

Dt

1(i)

/

Zt；i1//歸一化樣本分布Output：H(x)=sign（t

ht

(x)）t

1AdaBoost的一種偽代碼描述)2t=

Ln(

t1

1

t“弱分類(lèi)器權(quán)重-帶權(quán)分類(lèi)誤差”函數(shù)圖像誤差越低，分類(lèi)器權(quán)重越高誤差大于0.5，權(quán)重為負(fù)，實(shí)際已退出關(guān)鍵步驟：計(jì)算學(xué)習(xí)器權(quán)重關(guān)鍵步驟：更新樣本分布Dt

1(i)

Dt

(i)

exp(t

)

ht得到新的弱分類(lèi)器后，需要對(duì)樣本分布進(jìn)行更新：分類(lèi)錯(cuò)誤，提高該樣本的權(quán)值。分類(lèi)正確，降低該樣本的權(quán)值。mZt

Dt

1(i)i1Dt

1(i)

t（歸一化）AdaBoost實(shí)例：二元分類(lèi)序號(hào)12345678910X0123456789Y111-1-1-1111-1注：這里假設(shè)Xi為二元分類(lèi)，即對(duì)于X->Y,有Y={-1,+1}Q:已知如下學(xué)習(xí)樣本及其對(duì)應(yīng)的分類(lèi)，構(gòu)造分類(lèi)器，對(duì)樣本X進(jìn)行準(zhǔn)確分類(lèi)(也就是要求一個(gè)分類(lèi)函數(shù)F(x)，其對(duì)樣本X能進(jìn)行準(zhǔn)確的分類(lèi))X0123456789Y111-1-1-1111-1D10.10.10.10.10.10.10.10.10.10.1這里

要訓(xùn)練得到一個(gè)弱分類(lèi)器。嚴(yán)格來(lái)講，應(yīng)在給定的權(quán)重樣本和分類(lèi)方法上窮舉分類(lèi)器，選擇帶權(quán)誤差最小的弱分類(lèi)器作為本輪訓(xùn)練得到的分類(lèi)器。選擇的分類(lèi)方法為：y=1

(X<分界值)y=-1(X>分界值)1

x2.51

x2.5G1(x)

分界值0.51.52.53.54.55.56.57.58.5帶權(quán)誤差0.50.40.30.40.50.60.50.40.3不同值作為分界時(shí)分類(lèi)器帶權(quán)誤差在此分類(lèi)方法下，選擇2.5或8.5作為分界值，得到的帶權(quán)分類(lèi)誤差最小。這里選擇2.5。故本輪

訓(xùn)練得到的分類(lèi)器為：X0123456789Y111-1-1-1111-1D10.10.10.10.10.10.10.10.10.10.1

11

x2.51

x2.5G1(x)

1=0.5ln(1

1

)=0.4236分類(lèi)函數(shù)取：有：

1=0.1+0.1+0.1=0.3更新Di;F1(x)=1*G1(x)=0.4236*G1(x)Q:為什么G1(x)要取這種形式呢？分錯(cuò)了x7，x8,x9X0123456789Y111-1-1-1111-1D20.0710.0710.0710.0710.0710.0710.1660.1660.1660.0714444447774選擇的分類(lèi)方法為：y=1

(X<分界值)y=-1(X>分界值)1

x8.51

x8.5G2(x)

分界值0.51.22.53.54.55.56.57.58.5帶權(quán)誤差0.64290.57150.50010.57150.64290.71430.54760.38090.2142不同值作為分界時(shí)分類(lèi)器帶權(quán)誤差在當(dāng)前選取的分類(lèi)方法下，選擇8.5作為分界值，得到的帶權(quán)分類(lèi)誤差最小。故本輪

訓(xùn)練得到的分類(lèi)器為：

21

x8.51

x8.5G2(x)

2

=0.5ln(1

2

)=0.6499;分類(lèi)函數(shù)取：有：

2=0.0714+0.0714+0.0714=0.2142;更新Di;F2(x)=1*G1(x)+

2*G2(x)=0.4236*G1(x)+0.6499*G2(x)X0123456789YD210.071410.071410.0714-10.0714-10.0714-10.071410.166710.166710.1667-10.0714Q:為什么G2(x)要取這種形式呢？分錯(cuò)了x4、x5、x6X0123456789Y111-1-1-1111-1D30.0450.0450.0450.1660.1660.1660.1060.1060.1060.0454447771114選擇的分類(lèi)方法為：y=-1(X<分界值)y=1(X>分界值)-1

x5.5+1

x5.5G3(x)

分界值0.51.52.53.54.55.56.57.58.5帶權(quán)誤差0.59090.63630.68170.51500.34830.18160.28770.34840.4545不同值作為分界時(shí)分類(lèi)器帶權(quán)誤差在當(dāng)前選取的分類(lèi)方法下，選擇5.5作為分界值，得到的帶權(quán)分類(lèi)誤差最小。故本輪

訓(xùn)練得到的分類(lèi)器為：)=0.7528;

3=0.5ln(

31

x5.51

x5.5G3(x)

1

3分類(lèi)函數(shù)取：有：

3=0.0454+0.0454+0.0454+0.0454=0.1816;更新Di;F3(x)=1*G1(x)+

2*G2(x)+

3*G3(

x)

0.4236*G1(x)+0.6499*G2(x)

0.7528

*

G

3(

x)X0123456789YD310.045410.045410.0454-10.1667-10.1667-10.166710.106110.106110.1061-10.0454Q:為什么G3(x)要取這種形式呢？通過(guò)弱學(xué)習(xí)算法生產(chǎn)的，具體到本例：通過(guò)窮舉算法來(lái)獲得分錯(cuò)了x1,x2,x3,x10H(x)=sig=sign[1*G1(x)+

2*G2(x

sign[0.4236*G1(x)+0.6499*G2(x)

0.7528

*1

x2.51

x2.5G1(x)

1

x8.51

x8.5G2(x)

1

x5.51

x5.5G3(x)

X0123456789Y111-1-1-1111-1F3(X)0.32070.32070.3207-0.5265-0.5265-0.52650.97910.97910.9791-0.3207H(x)111-1-1-1111-1AdaBoost算法得到的分類(lèi)器分類(lèi)效果優(yōu)點(diǎn)和不足優(yōu)點(diǎn)：精度很高只是框架，弱學(xué)習(xí)算法(弱分類(lèi)器的構(gòu)造生成方法)可以多樣不會(huì)產(chǎn)生過(guò)渡擬合缺點(diǎn)：難以估計(jì)訓(xùn)練次數(shù)效果與弱分類(lèi)器選擇有關(guān)樣本多時(shí)效率較低離散AdaBoost-AdaBoost.M1AdaBoost.M1

和AdaBoost.M2

是用來(lái)解決多分類(lèi)單

問(wèn)題AdaBoost.M1算法(x1,

y1),(x2

,

y2

),...,

(xn

,

yn

)Step

1:訓(xùn)練集Step

2:初始化權(quán)值1,iiw2n

1for

y

0,1,For

t

=

1,

…

,

T1.

歸一化權(quán)值,2.

對(duì)于第j個(gè)特征,在給定權(quán)值條件下訓(xùn)練若分類(lèi)器hj

，若分類(lèi)器的分類(lèi)錯(cuò)誤率為：3.

更新權(quán)值:End最終的強(qiáng)分類(lèi)器：t

,it

,

jwt

,iwnj

1w

j

wi

|

hj

(xi

)

yi

|i如果t

1/2,設(shè)T

t

1,退出循環(huán)it

,i

tt

,i

twt

,i1et

1,iw

w

w

,

如果樣本被正確分類(lèi)其他tt

t1

th(x)=arg

maxyYlogt

1...TFloatboost

算法向前增加一個(gè)弱分類(lèi)器之后，就需要向后回饋r。r的取值取決于當(dāng)前分類(lèi)性能的穩(wěn)定性。這種弱分類(lèi)器選擇的方法相對(duì)于前向搜索來(lái)說(shuō)具有更大的靈活性，因此，增加弱分類(lèi)器組合的多樣性，相比AdaBoost中的單調(diào)搜索有更優(yōu)的解集合。mT

(x1,

y1

),

(x2

,

y2

),

...

,

(xm

,

ym

)J

(Hm

)為此特征集合的目標(biāo)函數(shù)值，J

min是目前m個(gè)特征構(gòu)成的集合中目標(biāo)函數(shù)的最小值。圖像正樣本=1負(fù)樣本=-1Step

1:訓(xùn)練集Step

2:初始化權(quán)值t

mmw

(i)

1

,

i

1,...m;

J

min

=max-value(t=1,...,Max),

M=01.

每個(gè)弱分類(lèi)器h,在權(quán)值下進(jìn)行訓(xùn)練，得到 函數(shù)ht.2.

計(jì)算誤判率，選取參數(shù)at：3.

更新權(quán)值:4.最終的函數(shù)：i

j

wi

|

hj

(xi

)

yi

|選擇有最小錯(cuò)誤率t的若分類(lèi)器ht。MtZi

1Wt

(xi

)

exp(t

yi

ht

(xi

))Wt

1

(xi

)

,Zt是使Wt

1

(xi

)的歸一化因子。Step

3:弱分類(lèi)器訓(xùn)練For

t

=1,

…

,

TM

M

mhHm設(shè)h'arg

min,為

最小特征集合，若J(H)(為漏檢率與虛警率的和)<Jmin

,則刪掉此特征，當(dāng)J(HM

)低于值或循環(huán)次數(shù)大于預(yù)定值M時(shí)，停止循環(huán)。MH

(x)

sign(

hm

(x))m1總結(jié)AdaBoost算法是一種自適應(yīng)性的提升類(lèi)算法。通過(guò)前一個(gè)分類(lèi)器的分類(lèi)結(jié)果對(duì)樣本分布進(jìn)行更新，用來(lái)訓(xùn)練下一個(gè)弱分類(lèi)器，最后將弱分類(lèi)器組合得到強(qiáng)的分類(lèi)器。AdaBoost算法能得到分類(lèi)精度高的強(qiáng)分類(lèi)器。AdaBoost算法只是一個(gè)框架，容易拓展應(yīng)用。理論出發(fā)點(diǎn)和Boosting算法AdaBoost算法Bagging算法隨機(jī)森林選擇性集成總結(jié)課程內(nèi)容03

Bagging算法通過(guò)自助采樣始終數(shù)據(jù)集D中約有36.8%的樣本未出現(xiàn)在采樣數(shù)據(jù)集D’中。自助法在數(shù)據(jù)集較小、難以有效劃分訓(xùn)練/測(cè)試集時(shí)很有用；此外，自助法能從初始數(shù)據(jù)集中產(chǎn)生多個(gè)不同的訓(xùn)練集，這對(duì)集成學(xué)習(xí)等方法有很大好處。Bagging是并行式集成學(xué)習(xí)最著名的代表。它直接基于自助采樣法。自助采樣法：給定包含m個(gè)樣本的數(shù)據(jù)集D，對(duì)它采樣產(chǎn)生數(shù)據(jù)集D’，每次隨機(jī)從

D中挑選一個(gè)樣本，將其拷貝放入D’，然后再將該樣本放回?cái)?shù)據(jù)集D中，使得該樣本在下次采樣時(shí)仍有可能被采到；這個(gè)過(guò)程重復(fù)執(zhí)行m次后，就得到了包含m個(gè)樣本的數(shù)據(jù)集D’，這就是自助采樣的結(jié)果。顯然，D中有一部分樣本會(huì)在D’中多次出現(xiàn)，而另一部分樣本不出現(xiàn)樣本在m次采樣中始終不被采到的概率是(1

1

)m

，取極限得到mm

emlim(1

1

)m

1

0.368bagging算法Bagging算法的主要思想：給定訓(xùn)練集 和弱學(xué)習(xí)算法，對(duì)該學(xué)習(xí)算法進(jìn)行T次調(diào)用，每次調(diào)用時(shí)只使用訓(xùn)練集S中的某個(gè)子集作為當(dāng)前訓(xùn)練集，每一個(gè)訓(xùn)練例在某輪訓(xùn)練集中可以多次或根本不出現(xiàn)。經(jīng)過(guò)T次調(diào)用后，可得到T個(gè)不同的分類(lèi)器啊，當(dāng)對(duì)于一個(gè)測(cè)試實(shí)例工進(jìn)行分類(lèi)時(shí)，分別調(diào)用這T個(gè)分類(lèi)器，得到T個(gè)分類(lèi)結(jié)果。最后對(duì)分類(lèi)問(wèn)題把這T個(gè)分類(lèi)結(jié)果中出現(xiàn)次數(shù)多的類(lèi)賦予測(cè)試實(shí)例x。2S

((x1,

y1),(x203

Bagging算法Bagging算法的主要思想：通過(guò)自助采樣法得到含有m個(gè)樣本的采樣集；進(jìn)行T輪，可以采樣出T個(gè)含m個(gè)訓(xùn)練樣本的訓(xùn)練集；基于每個(gè)采樣訓(xùn)練集訓(xùn)練出一個(gè)基學(xué)習(xí)器hi(x)；對(duì)T個(gè)基學(xué)習(xí)器進(jìn)行結(jié)合得到最終分類(lèi)器H(x)；對(duì)于 輸出進(jìn)行結(jié)合時(shí)，采用簡(jiǎn)單投票法，對(duì)回歸任務(wù)使用簡(jiǎn)單平均法。圖1

Bagging算法流程圖Bagging算法(x1,

y1),(x2

,y2

),...,(xn

,yn

)Step

1:訓(xùn)練Step

2:初始化權(quán)值For

t

=1,

…

,

TS’為從給定訓(xùn)練集S中，隨機(jī)抽樣（有放回）.在S’

上訓(xùn)練弱學(xué)習(xí)器，得到第t

輪的

函數(shù)ht

.t

=

t

+

1

.End最終輸出：

對(duì)未知樣本X分類(lèi)時(shí)，每個(gè)模型ht得到一個(gè)分類(lèi)器，得票最高的未知樣本x

的分類(lèi)輸入：訓(xùn)練集；3：若t<T，回到1，并令t=t+1，否則轉(zhuǎn)4；函4：將各 集合生成最終數(shù)：D={(x1,

y1),(x2

,

y2

),,(xm

,

ym

)}基學(xué)習(xí)算法h(x)；訓(xùn)練輪數(shù)T輸出：集成

模型過(guò)程：1：從初始的訓(xùn)練集中采用boostrap方法抽取出m個(gè)訓(xùn)練例組成子集S’；2：在S’上訓(xùn)練基學(xué)習(xí)器

h1,h2

,

,hT

，得到第t輪的 函數(shù)ht(x)；函數(shù)H

(x)

signhi

(x)03

Bagging算法圖2

Bagging算法描述03

Bagging算法Bagging與Boosting的區(qū)別：Bagging的訓(xùn)練集的選擇是隨機(jī)的，各訓(xùn)練集之間相互獨(dú)立；而B(niǎo)oosting的訓(xùn)練集的選擇不獨(dú)立，各輪訓(xùn)練集的選擇與前面各輪的學(xué)習(xí)有關(guān)；Bagging的各個(gè) 函數(shù)沒(méi) 重，而B(niǎo)oosting各訓(xùn)練集

重；Bagging各個(gè)函數(shù)可以并行生成，Boosting只能順序生成。（對(duì)于像神經(jīng)網(wǎng)絡(luò)這種比較耗時(shí)的學(xué)習(xí)方法，

Bagging可通過(guò)并行訓(xùn)練節(jié)省大量的時(shí)間）Bagging

和AdaBoost

區(qū)別Bagging的訓(xùn)練集是隨機(jī)的，各訓(xùn)練集是獨(dú)的，而

Boosting訓(xùn)練集的選擇不是獨(dú)立的，每一次選擇的訓(xùn)練集都依賴(lài)于上一次學(xué)習(xí)的結(jié)果。Bagging的每個(gè)

函數(shù)(即弱假設(shè))沒(méi)重，而B(niǎo)oosting根據(jù)每一次訓(xùn)練的訓(xùn)練誤差得到該次函數(shù)的權(quán)重。Bagging的各個(gè)

函數(shù)可以并行生成，而B(niǎo)oosting的只能順序生成。對(duì)于像神經(jīng)網(wǎng)絡(luò)這樣極為耗時(shí)的學(xué)習(xí)方法，Bagging可通過(guò)并行訓(xùn)練節(jié)省大量時(shí)間開(kāi)銷(xiāo)。理論出發(fā)點(diǎn)和Boosting算法AdaBoost算法Bagging算法隨機(jī)森林選擇性集成總結(jié)課程內(nèi)容04

隨機(jī)森林--Random

Forest隨機(jī)森林（RandomForest，簡(jiǎn)稱(chēng)RF）是Bagging的一個(gè)擴(kuò)展變體。隨機(jī)森林由許多的決策樹(shù)組成，因?yàn)檫@些決策樹(shù)的形成采用了隨機(jī)的方法，因此也叫做隨機(jī)決策樹(shù)。隨機(jī)森林中的樹(shù)之間是沒(méi)有關(guān)聯(lián)的。當(dāng)測(cè)試數(shù)據(jù)進(jìn)入隨機(jī)森林時(shí)，其實(shí)就是讓每一顆決策樹(shù)進(jìn)行分類(lèi)，最后取所有決策樹(shù)中分類(lèi)結(jié)果最多的那類(lèi)為最終的結(jié)果。RF在以決策樹(shù)為基學(xué)習(xí)器構(gòu)建Bagging集成的基礎(chǔ)上，進(jìn)一步在決策樹(shù)的訓(xùn)練過(guò)程中引入隨機(jī)屬性選擇。傳統(tǒng)決策樹(shù)在選擇劃分屬性時(shí)是在當(dāng)前結(jié)點(diǎn)的屬性集合（假定有d個(gè)屬性）中選擇一個(gè)最優(yōu)屬性；在RF中，對(duì)決策樹(shù)的每個(gè)結(jié)點(diǎn)，先從該結(jié)點(diǎn)的屬性集合中隨機(jī)選擇一個(gè)包含k個(gè)屬性的子集，然后再?gòu)倪@個(gè)子集中選擇一個(gè)最優(yōu)屬性用于劃分；這里的參數(shù)k控制了隨機(jī)性的引入程度：若令k=d，則基決策樹(shù)的構(gòu)建與傳統(tǒng)決策樹(shù)相同；若令k=1，則是隨機(jī)選擇一個(gè)屬性用于劃分；一般情況下， 值k=log2d。04

隨機(jī)森林--Random

Forest決策樹(shù)復(fù)習(xí)：決策樹(shù)實(shí)際上是將空間用超平面進(jìn)行劃分的

法，每次分割的時(shí)候，都將當(dāng)前的空間一分為二，比如說(shuō)下面的決策樹(shù)（其屬性的值都是連續(xù)的實(shí)數(shù)）：圖3 決策樹(shù)圖4 空間劃分后04

隨機(jī)森林--Random

Forest隨機(jī)森林的構(gòu)造過(guò)程：假N個(gè)樣本，則有放回的隨機(jī)選擇N個(gè)樣本（每次隨機(jī)選擇一個(gè)樣本，然后放回繼續(xù)選擇），用選擇好的N個(gè)樣本來(lái)訓(xùn)練決策樹(shù)。當(dāng)每個(gè)樣本有d個(gè)屬性時(shí)，在決策樹(shù)的每個(gè)節(jié)點(diǎn)需要時(shí)，隨機(jī)從這k個(gè)屬性中選取出k個(gè)屬性，滿(mǎn)足條件k<<d。然后從這k個(gè)屬性中采用某種策略（比如說(shuō)信息增益）來(lái)選擇1個(gè)屬性作為該節(jié)點(diǎn)的屬性。決策樹(shù)形成過(guò)程中每個(gè)節(jié)點(diǎn)都要按照步驟2來(lái)，一直到不能夠再 為止。注意整個(gè)決策樹(shù)形成過(guò)程中沒(méi)有進(jìn)行剪枝。按照步驟1~3建立大量的決策樹(shù)，這樣就構(gòu)成了隨機(jī)森林。隨機(jī)森林的隨機(jī)性體現(xiàn)在：每顆數(shù)的訓(xùn)練樣本是隨機(jī)的；樹(shù)中每個(gè)節(jié)點(diǎn)的分類(lèi)屬性是隨機(jī)選擇的。04

隨機(jī)森林--Random

Forest隨機(jī)森林的優(yōu)點(diǎn)：在數(shù)據(jù)集上表現(xiàn)良好，兩個(gè)隨機(jī)性的引入，使得隨機(jī)森林不容易陷入過(guò)擬合，具有很好的抗噪聲能力。它能夠處理很高維度（feature很多）的數(shù)據(jù)，并且不用做特征選擇，對(duì)數(shù)據(jù)集的適應(yīng)能力強(qiáng)：既能處理離散型數(shù)據(jù)，也能處理連續(xù)型數(shù)據(jù)，數(shù)據(jù)集無(wú)需規(guī)范化。能夠并行處理，訓(xùn)練速度快。隨機(jī)森林的缺點(diǎn)：算法傾向于觀測(cè)值較多的類(lèi)別隨機(jī)森林中水平較多的分類(lèi)屬性的自變量（如土地利用類(lèi)型>20個(gè)類(lèi)別）比水平較少的分類(lèi)屬性的自變量（氣候區(qū)類(lèi)型<10個(gè)類(lèi)別）對(duì)模型的影響大。理論出發(fā)點(diǎn)和Boosting算法AdaBoost算法Bagging算法隨機(jī)森林選擇性集成總結(jié)課程內(nèi)容的在意味著：時(shí)需要更大的計(jì)算開(kāi)銷(xiāo)，因?yàn)橐?jì)算的選擇性集成既然多個(gè)學(xué)習(xí)器的集成比單個(gè)學(xué)習(xí)器更好，那么是不是學(xué)習(xí)器越多越好?更大的

開(kāi)銷(xiāo)，因?yàn)橛?/p>

的 需要保存E

E

A [A.Krogh

&

J.

Vedelsby,

NIPS94]的增加將使得 間的差異越來(lái)越難以獲得104Many

Could

be

Better

Th

l：在有一組

學(xué)習(xí)器可用時(shí)，從中選擇一部分進(jìn)行集成，可能比用所有學(xué)習(xí)器進(jìn)行集成更好[Z.-H.

Zhou

et

al.,

AIJ02]【選擇性集成】選擇性集成提出了選擇性集成(Selective

Ensemble)證明了

“Many

Could

be

Better

Th l”

Theorem在有一組 學(xué)習(xí)器可用時(shí)，從中選擇一部分進(jìn)行集成，可能比用所