《機(jī)器學(xué)習(xí)》 周志華

第一章 緒論

機(jī)器學(xué)習(xí)的定義

關(guān)于“學(xué)習(xí)算法”的學(xué)問(wèn)。

機(jī)器學(xué)習(xí)的一些基本術(shù)語(yǔ)

假設(shè)我們收集了一批西瓜的數(shù)據(jù)紊册，例如：（色澤=青綠;根蒂=蜷縮;敲聲=濁響)， (色澤=烏黑;根蒂=稍蜷;敲聲=沉悶)素邪， (色澤=淺自;根蒂=硬挺;敲聲=清脆)……每對(duì)括號(hào)內(nèi)是一個(gè)西瓜的記錄揭朝，定義：?

1. 所有記錄的集合為：數(shù)據(jù)集。

2. 每一條記錄為：一個(gè)實(shí)例（instance）或樣本（sample）欣除。

3. 色澤或敲聲住拭，單個(gè)的特點(diǎn)為特征（feature）或?qū)傩裕╝ttribute）。

4. 對(duì)于一條記錄，如果在坐標(biāo)軸上表示滔岳，每個(gè)西瓜都可以用坐標(biāo)軸中的一個(gè)點(diǎn)表示杠娱，一個(gè)點(diǎn)也是一個(gè)向量，例如（青綠谱煤，蜷縮摊求，濁響），即每個(gè)西瓜為：一個(gè)特征向量（feature vector）刘离。

5. 一個(gè)樣本的特征數(shù)為：維數(shù)（dimensionality）室叉，該西瓜的例子維數(shù)為3，當(dāng)維數(shù)非常大時(shí)硫惕，也就是現(xiàn)在說(shuō)的“維數(shù)災(zāi)難”茧痕。

在計(jì)算機(jī)程序?qū)W習(xí)經(jīng)驗(yàn)數(shù)據(jù)生成算法模型的過(guò)程中，每一條記錄稱為一個(gè)“訓(xùn)練樣本”疲憋，同時(shí)在訓(xùn)練好模型后凿渊，我們希望使用新的樣本來(lái)測(cè)試模型的效果，則每一個(gè)新的樣本稱為一個(gè)“測(cè)試樣本”缚柳。定義：

1. 所有訓(xùn)練樣本的集合為：訓(xùn)練集（trainning set）埃脏，[特殊]。

2. 所有測(cè)試樣本的集合為：測(cè)試集（test set）秋忙，[一般]彩掐。?

3. 機(jī)器學(xué)習(xí)出來(lái)的模型適用于新樣本的能力為：泛化能力（generalization），即從特殊到一般灰追。

在西瓜的例子中堵幽，我們預(yù)測(cè)的是：西瓜是好是壞，即好瓜與差瓜兩種弹澎，是離散值朴下。同樣地，也有通過(guò)歷年的人口數(shù)據(jù)苦蒿，來(lái)預(yù)測(cè)未來(lái)的人口數(shù)量殴胧，人口數(shù)量則是連續(xù)值。因此我們定義：?

1. 預(yù)測(cè)值為離散值的問(wèn)題為：分類（classification）佩迟。

2. 預(yù)測(cè)值為連續(xù)值的問(wèn)題為：回歸（regression）团滥。

在我們預(yù)測(cè)西瓜是否是好瓜的過(guò)程中，我們事先已經(jīng)知道了訓(xùn)練集中瓜的好壞报强，學(xué)習(xí)器通過(guò)學(xué)習(xí)這些好瓜或差瓜的特征灸姊，從而總結(jié)出規(guī)律，即訓(xùn)練集中的西瓜我們都做了標(biāo)記秉溉，稱為標(biāo)記信息力惯。但也有沒(méi)有標(biāo)記信息的情形：我們想將一堆西瓜根據(jù)特征分成兩個(gè)小堆碗誉，使得某一堆的西瓜盡可能相似，即都是好瓜或差瓜夯膀，對(duì)于這種問(wèn)題诗充，我們事先并不知道西瓜的好壞，樣本沒(méi)有標(biāo)記信息诱建。因此蝴蜓，我們定義：

1. 訓(xùn)練數(shù)據(jù)有標(biāo)記信息的學(xué)習(xí)任務(wù)為：監(jiān)督學(xué)習(xí)（supervised learning），容易知道上面所描述的分類和回歸都是監(jiān)督學(xué)習(xí)的范疇俺猿。

2. 訓(xùn)練數(shù)據(jù)沒(méi)有標(biāo)記信息的學(xué)習(xí)任務(wù)為：無(wú)監(jiān)督學(xué)習(xí)（unsupervised learning）茎匠，常見(jiàn)的有聚類和關(guān)聯(lián)規(guī)則。

模型的評(píng)估

所有模型都不是完美的押袍！每種模型都有自己的歸納偏好诵冒，只適用于特定情況。要談?wù)撍惴ǖ南鄬?duì)優(yōu)劣谊惭，必須要針對(duì)具體的學(xué)習(xí)問(wèn)題汽馋。

第二章 模型評(píng)估與選擇

誤差與過(guò)擬合

一般來(lái)說(shuō)，學(xué)習(xí)器的預(yù)測(cè)輸出和實(shí)際真實(shí)的輸出是有差異的圈盔，稱為誤差豹芯。我們定義：

1. 在訓(xùn)練集上的誤差稱為訓(xùn)練誤差（training error）或經(jīng)驗(yàn)誤差（empirical error）。

2. 在測(cè)試集上的誤差稱為測(cè)試誤差（test error）驱敲。

3. 學(xué)習(xí)器在所有新樣本上的誤差稱為泛化誤差（generalization error）铁蹈。

如果學(xué)習(xí)器學(xué)的太差，對(duì)訓(xùn)練樣本的一般性質(zhì)沒(méi)學(xué)好众眨，則稱為欠擬合underfitting握牧。相反，如果學(xué)的「太好」娩梨，把訓(xùn)練樣本自身的一些特點(diǎn)當(dāng)成了所有潛在樣本都具有的一般性質(zhì)沿腰，這種情況稱為過(guò)擬合overfitting。欠擬合比較容易克服狈定，往往因?yàn)閷W(xué)習(xí)器學(xué)習(xí)能力太強(qiáng)大導(dǎo)致的過(guò)擬合很難處理颂龙，實(shí)際上過(guò)擬合是機(jī)器學(xué)習(xí)面臨的關(guān)鍵障礙。首先必須認(rèn)識(shí)到掸冤，過(guò)擬合無(wú)法避免厘托，我們需要做的是降低或者緩解：

機(jī)器學(xué)習(xí)面臨的問(wèn)題通常是NP難或者更難友雳，而有效的學(xué)習(xí)算法必然是在多項(xiàng)式時(shí)間內(nèi)運(yùn)行完成稿湿，若可徹底避免過(guò)擬合，則通過(guò)經(jīng)驗(yàn)誤差最小化就能獲得最優(yōu)解押赊，這就意味著我們構(gòu)造性地證明了P=NP饺藤。因此只要相信P≠NP包斑，過(guò)擬合就不可避免。

評(píng)估方法

通常我們采用一個(gè)“測(cè)試集”來(lái)測(cè)試學(xué)習(xí)器對(duì)新樣本的判別能力涕俗，然后以“測(cè)試集”上的“測(cè)試誤差”作為“泛化誤差”的近似罗丰。顯然：我們選取的測(cè)試集應(yīng)盡可能與訓(xùn)練集互斥。

訓(xùn)練集與測(cè)試集的劃分方法

一再姑、留出法

將數(shù)據(jù)集D劃分為兩個(gè)互斥的集合萌抵，一個(gè)作為訓(xùn)練集S，一個(gè)作為測(cè)試集T元镀，滿足D=S∪T且S∩T=?绍填，常見(jiàn)的劃分為：大約2/3-4/5的樣本用作訓(xùn)練，剩下的用作測(cè)試栖疑。需要注意的是：訓(xùn)練/測(cè)試集的劃分要盡可能保持?jǐn)?shù)據(jù)分布的一致性讨永，以避免由于分布的差異引入額外的偏差，常見(jiàn)的做法是采取分層抽樣遇革。同時(shí)卿闹，由于劃分的隨機(jī)性，單次的留出法結(jié)果往往不夠穩(wěn)定萝快，一般要采用若干次隨機(jī)劃分锻霎，重復(fù)實(shí)驗(yàn)取平均值的做法。

二杠巡、交叉驗(yàn)證法

將數(shù)據(jù)集D劃分為k個(gè)大小相同的互斥子集量窘，滿足D=D1∪D2∪…∪Dk，Di∩Dj=?（i≠j）氢拥，同樣地盡可能保持?jǐn)?shù)據(jù)分布的一致性蚌铜，即采用分層抽樣的方法獲得這些子集。交叉驗(yàn)證法的思想是：每次用k-1個(gè)子集的并集作為訓(xùn)練集嫩海，余下的那個(gè)子集作為測(cè)試集冬殃，這樣就有K種訓(xùn)練集/測(cè)試集劃分的情況，從而可進(jìn)行k次訓(xùn)練和測(cè)試叁怪，最終返回k次測(cè)試結(jié)果的均值审葬。交叉驗(yàn)證法也稱“k折交叉驗(yàn)證”，k最常用的取值是10奕谭，下圖給出了10折交叉驗(yàn)證的示意圖睛驳。

10折交叉驗(yàn)證

與留出法類似步脓，將數(shù)據(jù)集D劃分為K個(gè)子集的過(guò)程具有隨機(jī)性，因此K折交叉驗(yàn)證通常也要重復(fù)p次，稱為p次k折交叉驗(yàn)證丹喻，常見(jiàn)的是10次10折交叉驗(yàn)證卧斟，即進(jìn)行了100次訓(xùn)練/測(cè)試囚聚。特殊地，當(dāng)劃分的k個(gè)子集的每個(gè)子集中只有一個(gè)樣本時(shí)鸦难，稱為“留一法”，顯然员淫，留一法的評(píng)估結(jié)果比較準(zhǔn)確合蔽，但對(duì)計(jì)算機(jī)的消耗也是巨大的。

三介返、自助法

我們希望評(píng)估的是用整個(gè)D訓(xùn)練出的模型拴事。但在留出法和交叉驗(yàn)證法中，由于保留了一部分樣本用于測(cè)試圣蝎，因此實(shí)際評(píng)估的模型所使用的訓(xùn)練集比D小挤聘，這必然會(huì)引入一些因訓(xùn)練樣本規(guī)模不同而導(dǎo)致的估計(jì)偏差。留一法受訓(xùn)練樣本規(guī)模變化的影響較小捅彻，但計(jì)算復(fù)雜度又太高了组去。“自助法”正是解決了這樣的問(wèn)題步淹。自助法的基本思想是：給定包含m個(gè)樣本的數(shù)據(jù)集D从隆，每次隨機(jī)從D 中挑選一個(gè)樣本，將其拷貝放入D’缭裆，然后再將該樣本放回初始數(shù)據(jù)集D 中键闺，使得該樣本在下次采樣時(shí)仍有可能被采到。重復(fù)執(zhí)行m 次澈驼，就可以得到了包含m個(gè)樣本的數(shù)據(jù)集D’辛燥。可以得知在m次采樣中缝其，樣本始終不被采到的概率取極限為：

樣本始終不被采樣的概率極限

這樣挎塌，通過(guò)自助采樣，初始樣本集D中大約有36.8%的樣本沒(méi)有出現(xiàn)在D’中内边，于是可以將D’作為訓(xùn)練集榴都，D-D’作為測(cè)試集。自助法在數(shù)據(jù)集較小漠其，難以有效劃分訓(xùn)練集/測(cè)試集時(shí)很有用嘴高，但由于自助法產(chǎn)生的數(shù)據(jù)集（隨機(jī)抽樣）改變了初始數(shù)據(jù)集的分布，因此引入了估計(jì)偏差和屎。在初始數(shù)據(jù)集足夠時(shí)拴驮，留出法和交叉驗(yàn)證法更加常用。

性能度量

性能度量就是建立衡量模型泛化能力的評(píng)價(jià)標(biāo)準(zhǔn)柴信。不同的度量標(biāo)準(zhǔn)往往會(huì)導(dǎo)致不同的評(píng)判結(jié)果套啤。因此模型的好壞是相對(duì)的，它不僅取決于算法和數(shù)據(jù)颠印，還取決于任務(wù)需求纲岭。

回歸任務(wù)最常用的性能度量是均方誤差

E(f;D)=1/m*∑(f(xi)?yi)^2

以下介紹分類任務(wù)常用的性能度量。?

1. 錯(cuò)誤率與精度?

2. 查準(zhǔn)率precision线罕、查全率recall與F1?

3. ROC與AUC?

4. 代價(jià)敏感錯(cuò)誤率與代價(jià)曲線

錯(cuò)誤率與精度

錯(cuò)誤率是分類錯(cuò)誤的樣本數(shù)占樣本總數(shù)的比例止潮，精度則是分類正確的樣本占樣本總數(shù)的比例。

查準(zhǔn)率钞楼、查全率與F1

所謂的查準(zhǔn)率P和查全率R分別定義為：?

????????????????????????????????????????????????????P=TPTP+FP, ? ?R=TPTP+FN

變量是分類結(jié)果的混淆矩陣confusion matrix喇闸，表示為下表：

confusion matrix

查準(zhǔn)率是在所有預(yù)測(cè)結(jié)果為正例的情況下的真實(shí)比例。查全率是所有真實(shí)情況為正例的情況下預(yù)測(cè)正確的比例询件。

P和R是一對(duì)矛盾度量燃乍，所以一般會(huì)綜合兩方面考量學(xué)習(xí)器的好壞，找到最佳平衡點(diǎn)BEP（Break-Even Point）宛琅。衡點(diǎn)定義是查全率等于查準(zhǔn)率時(shí)的取值刻蟹。

BEP

BEP過(guò)于簡(jiǎn)化，更常用的是F1變量嘿辟，本質(zhì)上是P和R的調(diào)和平均舆瘪。?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1/F1=1/2*(1/P+1/R)

具體應(yīng)用中可能對(duì)P和R有不同的倚重。比如商品推薦中红伦，為了盡可能少打擾用戶英古，更希望推薦內(nèi)容確是用戶感興趣的，這時(shí)候查準(zhǔn)率更重要昙读。而在逃犯檢索系統(tǒng)中召调，更希望盡可能少漏掉逃犯，此時(shí)查全率更重要蛮浑。F1度量的一般形式Fβ就可以表達(dá)這種偏好唠叛。?

????????????????????????????????????????????????????1/Fβ=1/(1+β^2)(1/P+β^2/R)

也即是Fβ=(1+β^2)PR/(β^2P+R)

當(dāng)β>1意味著P占比重更大，反之則是R沮稚。

ROC與AUC

ROC為受試者工作特征（Receiver Operating Characteristic)曲線玻墅，ROC曲線的縱軸是”真正例率“（True Positive Rate），橫軸是”假正例率“（False Positive Rate）壮虫。AUC是ROC曲線下的面積（Area Under ROC Curve）澳厢，用來(lái)在兩個(gè)學(xué)習(xí)器的ROC曲線沒(méi)有發(fā)生交叉時(shí)，衡量比較兩個(gè)學(xué)習(xí)器的優(yōu)劣囚似。

更詳細(xì)的公式剩拢、推導(dǎo)和圖例請(qǐng)翻看p.33-p.35。

代價(jià)敏感錯(cuò)誤與代價(jià)曲線

不同的錯(cuò)誤帶來(lái)的后果嚴(yán)重程度不一樣饶唤，因此我們需要為錯(cuò)誤賦予一個(gè)“非均等代價(jià)”（unequal cost）徐伐。以二分類為例，我們可根據(jù)任務(wù)的領(lǐng)域知識(shí)設(shè)定一個(gè)“代價(jià)矩陣”（cost matrix）募狂。(p.35 表2.2)

在非均等代價(jià)下办素，ROC曲線不能直接反應(yīng)出學(xué)習(xí)器的期望總體代價(jià)角雷，而代價(jià)曲線則可以達(dá)到目的（p.36）

注意！

本書(shū)將代價(jià)進(jìn)行了歸一化處理性穿，出來(lái)的代價(jià)曲線也全部是直線勺三。事實(shí)上這并不完全正確，歸一化處理代價(jià)后需曾，代價(jià)曲線也可以是曲線吗坚。具體的證明寫(xiě)在了p.36頁(yè)，也可以參考知乎答主對(duì)代價(jià)曲線的理解：

https://www.zhihu.com/question/63492375

比較檢驗(yàn)

機(jī)器學(xué)習(xí)中性能比較這件事情比大家想象的復(fù)雜得多呆万，同一個(gè)學(xué)習(xí)方法在同一個(gè)測(cè)試集上多次運(yùn)行商源，其結(jié)果都可能不同。而統(tǒng)計(jì)假設(shè)檢驗(yàn)為我們進(jìn)行學(xué)習(xí)器性能比較提供了重要依據(jù)

簡(jiǎn)單來(lái)說(shuō)谋减，若在測(cè)試集上觀察到學(xué)習(xí)器A比B好牡彻，基于假設(shè)檢驗(yàn)結(jié)果則能知道A的泛化性能是否在統(tǒng)計(jì)意義上優(yōu)于B，以及這個(gè)結(jié)論的把握有多大出爹。

本書(shū)列出了四種統(tǒng)計(jì)檢驗(yàn)方法：假設(shè)檢驗(yàn)讨便、交叉驗(yàn)證t檢驗(yàn)、McNemar檢驗(yàn)以政、Friedman檢驗(yàn)與Nemenyi后續(xù)檢驗(yàn)霸褒。

公式圖表太多啦，參見(jiàn)p.38~p.44

偏差與方差

通過(guò)實(shí)驗(yàn)盈蛮，我們可以估計(jì)學(xué)習(xí)算法的泛化性能废菱，另一方面通過(guò)偏差與方差，我們可以了解算法為什么具有這樣的性能抖誉，偏差-方差分解（bias-variance decomposition）就是用來(lái)解釋學(xué)習(xí)算法泛化性能的一種工具殊轴，試圖拆解期望泛化錯(cuò)誤率：

偏差-方差分解

書(shū)中對(duì)偏差、方差和噪聲三個(gè)概念進(jìn)行了定義：

1. 偏差：度量學(xué)習(xí)算法的期望預(yù)測(cè)與真實(shí)結(jié)果的偏離程度袒炉，即刻畫(huà)了學(xué)習(xí)算法本身的擬合能力?

2. 方差：度量了同樣大小的訓(xùn)練集的變動(dòng)所導(dǎo)致的學(xué)習(xí)性能的變化旁理，即刻畫(huà)了數(shù)據(jù)擾動(dòng)所造成的影響?

3. 噪聲：表達(dá)了當(dāng)前任務(wù)下任何學(xué)習(xí)算法所能達(dá)到的期望泛化誤差的下限，即刻畫(huà)了學(xué)習(xí)問(wèn)題本身的難度

一般來(lái)說(shuō)我磁，偏差與方差是有沖突的孽文，這稱為偏差-方差窘境（bias-variance dilemma）。當(dāng)學(xué)習(xí)器剛開(kāi)始學(xué)習(xí)時(shí)夺艰，因?yàn)閷W(xué)習(xí)程度不足芋哭，偏差會(huì)主導(dǎo)泛化錯(cuò)誤率，隨著學(xué)習(xí)器擬合能力逐漸增強(qiáng)郁副，數(shù)據(jù)集發(fā)生的擾動(dòng)會(huì)被學(xué)習(xí)到减牺，這時(shí)方差開(kāi)始主導(dǎo)泛化錯(cuò)誤率。在最后擬合能力非常強(qiáng)的情況下訓(xùn)練數(shù)據(jù)自身的、非全局的特性被學(xué)習(xí)器學(xué)到了拔疚，則將發(fā)生過(guò)擬合肥隆。

第三章 線性模型

基本形式

1. 假定示例有d個(gè)屬性，x=(x1,x2,...,xd)? 2. 試圖通過(guò)屬性的線性組合進(jìn)行預(yù)測(cè)

線性模型的基本形式

用向量形式表示就是：?

向量化的基本形式

線性模型雖然簡(jiǎn)單稚失，但卻是基礎(chǔ)栋艳。先研究線性、單屬性的線性回歸問(wèn)題墩虹，便可以進(jìn)一步研究非線性、多屬性的回歸和分類問(wèn)題憨琳。本章介紹了幾種經(jīng)典的線性模型诫钓，從回歸任務(wù)開(kāi)始，然后討論二分類和多分類問(wèn)題篙螟。

線性回歸

根據(jù)已有的數(shù)據(jù)確定一個(gè)函數(shù)然后預(yù)測(cè)菌湃，怎樣衡量函數(shù)的準(zhǔn)確度呢，均方誤差是常用的遍略，幾何意義上是求得一條線使得所有的樣本到直線的歐式距離之和最小惧所，基于均方誤差最小化進(jìn)行模型求解的方法稱為最小二乘法，以單變量為例绪杏，求解w和b下愈，有

我們要將均方差最小化，即：

將求解公式等于0可求得w和b的最優(yōu)封閉解：

多元線性回歸的參數(shù)求解以同樣的思路求解蕾久，多參數(shù)轉(zhuǎn)為矩陣涉及到矩陣逆的計(jì)算势似，在不滿秩的時(shí)候經(jīng)常會(huì)出現(xiàn)不止一組解使得均方誤差最小僧著；涉及到選擇偏好履因，處理時(shí)可加入正則化。也可以使用線性回歸的衍生物盹愚，即讓得到的模型和另外的函數(shù)產(chǎn)生關(guān)系lny=wx+b栅迄，這其實(shí)是輸入空間到輸出的一個(gè)非線性預(yù)測(cè)，對(duì)數(shù)線性回歸皆怕。

一般的毅舆，考慮單調(diào)可微函數(shù)g(·),令

這樣得到的模型稱為廣義線性模型（generalizeed linear model）。其中愈腾，g(·)成為聯(lián)系函數(shù)（link function）朗兵。顯然，對(duì)數(shù)線性回歸是廣義線性模型在g(·)=ln(·)時(shí)的特例顶滩。

對(duì)數(shù)幾率回歸

線性回歸討論了如何使用線性模型進(jìn)行回歸學(xué)習(xí)余掖，但若要做的是分類任務(wù)該怎么辦？式（3.15）可以給我們一個(gè)答案：只需找出一個(gè)單調(diào)可微函數(shù)，將分類任務(wù)的真實(shí)標(biāo)記y與線性回歸模型的預(yù)測(cè)值聯(lián)系起來(lái)盐欺。

考慮二分類任務(wù)赁豆，其輸出標(biāo)記y屬于{0,1}，而線性回歸模型產(chǎn)生的預(yù)測(cè)值z(mì)=wTx+b是實(shí)值冗美，于是魔种，我們需將實(shí)值z(mì)轉(zhuǎn)換為0/1值，最理想的是單位介躍函數(shù)（unit-step function）

單位介躍函數(shù)

單位介躍函數(shù)與對(duì)數(shù)幾率函數(shù)

但是單位介躍函數(shù)并不連續(xù)粉洼，因此不能用做g(·)节预，此時(shí)我們希望找到能在一定程度上近似單位介躍函數(shù)的替代函數(shù)(surrogate function），并希望他單調(diào)可微属韧。對(duì)數(shù)幾率函數(shù)正是這樣一個(gè)常用的替代函數(shù)：

對(duì)數(shù)幾率函數(shù)（Sigmoid函數(shù)）

做一下變換可得：lny/(1?y)=wTx+b安拟。y/1?y含義就是比率，為正例的可能性與為反例的可能性比值宵喂。

從本質(zhì)上講糠赦，對(duì)數(shù)幾率回歸模型logistic regression就是在用線性回歸模型的預(yù)測(cè)結(jié)果去逼近真實(shí)標(biāo)記的對(duì)數(shù)幾率。

對(duì)數(shù)幾率回歸模型雖然還是回歸模型锅棕，但卻是一種分類學(xué)習(xí)方法拙泽。之前普遍翻譯為邏輯回歸，意義相去甚遠(yuǎn)裸燎，還是用對(duì)數(shù)幾率回歸比較符合一些顾瞻。它的好處在于：?

1. 將分類進(jìn)行建模，無(wú)需事先假設(shè)數(shù)據(jù)分布德绿，避免假設(shè)分布不準(zhǔn)確所帶來(lái)的問(wèn)題?

2. 不僅分類朋其，還可得到近似概率預(yù)測(cè)，可利用概率輔助決策?

3. 對(duì)率函數(shù)是任意階可導(dǎo)的凸函數(shù)脆炎，可方便求取最優(yōu)解

確定模型之后梅猿，接下來(lái)自然要做的就是確定w和b。這里要使用到的方法是極大似然法maximum likelihood method秒裕。過(guò)程省略袱蚓，最后我們需要最小化：

（3.27）

上式為關(guān)于β的高階可導(dǎo)連續(xù)凸函數(shù)，根據(jù)凸優(yōu)化理論几蜻，利用經(jīng)典的數(shù)值優(yōu)化算法如梯度下降法喇潘、牛頓法都可求得最優(yōu)解。

線性判別分析

線性判別分析Linear Discriminant Analysis是一種經(jīng)典的線性學(xué)習(xí)方法梭稚，應(yīng)用于分類任務(wù)中颖低。

LDA的思想非常簡(jiǎn)單，將訓(xùn)練集的樣本投影到一條直線上弧烤，同一類的盡量互相靠近忱屑，而不同類之間盡可能相隔的遠(yuǎn)。使用數(shù)學(xué)語(yǔ)言，投影即是向量乘積莺戒， 同一類盡量靠近伴嗡，就是協(xié)方差要小，不同類相隔遠(yuǎn)从铲，就是類中心距離遠(yuǎn)瘪校，也就是均值投影的差要大。如圖所示：

LDA示意圖

基于這樣的考慮名段，LDA定義了兩個(gè)散度矩陣：類內(nèi)散度矩陣（越小越好）?類間散度矩陣(越大越好)阱扬，最后得到了LDA的最大化目標(biāo)：“廣義瑞利商”。

類內(nèi)散度矩陣

類間散度矩陣

最大化目標(biāo)

將3.33和3.34式帶入3.32所得的廣義瑞利商

為了確定w的曲直伸辟，書(shū)中采用了拉格朗日乘子法求解麻惶，具體見(jiàn)p.61-p.62。

LDA同樣可應(yīng)用于多分類任務(wù)中自娩，方法類似于二分類用踩，具體可見(jiàn)p.62-p.63渠退。

最后補(bǔ)充兩點(diǎn)：?

1. 從貝葉斯決策理論的角度可以證明LDA在兩類數(shù)據(jù)同先驗(yàn)忙迁、滿足高斯分布且協(xié)方差相等時(shí)，LDA可達(dá)到最優(yōu)分類碎乃。?

2. LDA核心是投影姊扔，這樣往往實(shí)現(xiàn)了降維，因而LDA也常被視為一種經(jīng)典的監(jiān)督降維技術(shù)梅誓。

多分類問(wèn)題

多分類的問(wèn)題常常是使用差分策略恰梢，通過(guò)二分類學(xué)習(xí)來(lái)解決多分類問(wèn)題，即將多分類問(wèn)題拆解為多個(gè)二分類訓(xùn)練二分類學(xué)習(xí)器最后通過(guò)繼承得到結(jié)果梗掰，最經(jīng)典拆分策略有三種：“一對(duì)一”（OvO）嵌言、“一對(duì)其余”（OvR）和“多對(duì)多”（MvM），核心思想與示意圖如下所示：

OvO與OvR示意圖

具體選擇哪一種及穗，要看具體情況下的存儲(chǔ)和時(shí)間開(kāi)銷摧茴，以及性能高低。

一對(duì)一OvO

假設(shè)訓(xùn)練集有四類樣本埂陆，C1,C2,C3,C4苛白，訓(xùn)練時(shí)兩兩組合為二分類進(jìn)行訓(xùn)練，新樣本通過(guò)這C2N個(gè)分類器后會(huì)得到N(N?1)/2個(gè)分類結(jié)果焚虱，最終結(jié)果可根據(jù)這些分類結(jié)果投票產(chǎn)生购裙。

一對(duì)其余OvR

訓(xùn)練時(shí)一個(gè)類作為正例，其余所有類作為反例鹃栽。這樣共有N個(gè)二分類器進(jìn)行訓(xùn)練躏率，新樣本通過(guò)分類器時(shí)預(yù)測(cè)結(jié)果為正例的即為最終結(jié)果。

多對(duì)多MvM

本質(zhì)上講前兩種情況都是MvM的特殊情況『檀福基本思路是訓(xùn)練集每一類通過(guò)多個(gè)分類器訓(xùn)練會(huì)產(chǎn)生一組編碼結(jié)果私股，新樣本通過(guò)分類器產(chǎn)生的編碼結(jié)果與每個(gè)分類器的結(jié)果求距離，距離最短者即為最終結(jié)果恩掷。

以(a)的海明距離為例倡鲸，C3的海明距離最小，所以最終結(jié)果是C3

這里常用的MvM編碼技術(shù)是：糾錯(cuò)輸出碼ECOC Error Correcting Output Codes黄娘，其關(guān)鍵在于：?

1. 如何劃分類別形成二分類訓(xùn)練集峭状，也就是編碼?

2. 解碼，選擇如海明距離逼争、歐式距離作為衡量优床，同時(shí)糾錯(cuò)能力強(qiáng)，能容錯(cuò)

類別不平衡問(wèn)題

類別不平衡就是指分類任務(wù)中誓焦，不同類別的訓(xùn)練樣例數(shù)目差別很大的情況胆敞。舉個(gè)很簡(jiǎn)單的例子，1000個(gè)樣本杂伟，有998個(gè)是反例移层，2個(gè)是正例，那么一個(gè)對(duì)樣本永遠(yuǎn)只預(yù)測(cè)為反例的學(xué)習(xí)器也能實(shí)現(xiàn)99.8%的正確率赫粥，但這種學(xué)習(xí)器顯然是沒(méi)有用的观话。

本節(jié)假定了正類樣例較少，反類樣例較多越平。在現(xiàn)實(shí)的分類學(xué)習(xí)任務(wù)中频蛔，我們經(jīng)常會(huì)遇到類別不平衡。因此我們必須了解類別不平衡性處理的基本方法秦叛。

一個(gè)基本策略是再縮放rescaling晦溪。

在之前的比率回歸問(wèn)題上，y1?y代表正例可能性與反例可能性的比值挣跋，那么如果y/(1?y)>1就可預(yù)測(cè)為正例三圆。而在類別不平衡的樣本中，假設(shè)正例數(shù)目為m+浆劲，反例數(shù)目為m?（一般正例數(shù)目小于反例數(shù)目）嫌术。我們可設(shè)定學(xué)習(xí)器的決策條件為：當(dāng)y/(1?y)>m+/m?即可預(yù)測(cè)為正例。那么比率即可重改為y′/(1?y′)=[y/(1?y)][m?/m+]牌借。

在實(shí)際操作中度气，再縮放卻沒(méi)那么容易，主要原因是不一定能有效的基于訓(xùn)練集觀測(cè)幾率去推斷真實(shí)幾率膨报。因而往往有三類做法：?

1.?欠采樣undersampling：去除一些反例數(shù)目磷籍，使得正例數(shù)目接近于反例數(shù)目适荣，再進(jìn)行學(xué)習(xí)。需要注意院领，若直接丟棄反例弛矛，可能會(huì)造成重要信息丟失，一種方法是利用集成學(xué)習(xí)機(jī)制比然，將反例劃分為若干個(gè)集合供不同學(xué)習(xí)器使用丈氓，這樣每個(gè)學(xué)習(xí)器就相當(dāng)于欠采樣，而全局看則沒(méi)有丟失重要信息?

2.?過(guò)采樣oversampling：增加正例數(shù)目强法，為防止過(guò)擬合万俗，可對(duì)訓(xùn)練集正例進(jìn)行插值產(chǎn)生額外正例，而不是直接重復(fù)采樣初始正例樣本?

3.?閾值移動(dòng)threshold-moving：直接基于原訓(xùn)練集進(jìn)行學(xué)習(xí)饮怯，但用訓(xùn)練好的分類器進(jìn)行預(yù)測(cè)時(shí)闰歪，將y′/(1?y′)=[y/(1?y)][m?/m+]嵌入決策中