第一章 緒論
機器學習的定義
關于“學習算法”的學問。
機器學習的一些基本術語
假設我們收集了一批西瓜的數(shù)據(jù)，例如：（色澤=青綠;根蒂=蜷縮;敲聲=濁響)， (色澤=烏黑;根蒂=稍蜷;敲聲=沉悶)， (色澤=淺自;根蒂=硬挺;敲聲=清脆)……每對括號內是一個西瓜的記錄，定義：?
1. 所有記錄的集合為：數(shù)據(jù)集。
2. 每一條記錄為：一個實例（instance）或樣本（sample）。
3. 色澤或敲聲，單個的特點為特征（feature）或屬性（attribute）。
4. 對于一條記錄，如果在坐標軸上表示，每個西瓜都可以用坐標軸中的一個點表示，一個點也是一個向量，例如（青綠，蜷縮，濁響），即每個西瓜為：一個特征向量（feature vector）。
5. 一個樣本的特征數(shù)為：維數(shù)（dimensionality），該西瓜的例子維數(shù)為3，當維數(shù)非常大時，也就是現(xiàn)在說的“維數(shù)災難”。
在計算機程序學習經驗數(shù)據(jù)生成算法模型的過程中，每一條記錄稱為一個“訓練樣本”，同時在訓練好模型后，我們希望使用新的樣本來測試模型的效果，則每一個新的樣本稱為一個“測試樣本”。定義：
1. 所有訓練樣本的集合為：訓練集（trainning set），[特殊]。
2. 所有測試樣本的集合為：測試集（test set），[一般]。?
3. 機器學習出來的模型適用于新樣本的能力為：泛化能力（generalization），即從特殊到一般。
在西瓜的例子中，我們預測的是：西瓜是好是壞，即好瓜與差瓜兩種，是離散值。同樣地，也有通過歷年的人口數(shù)據(jù)，來預測未來的人口數(shù)量，人口數(shù)量則是連續(xù)值。因此我們定義：?
1. 預測值為離散值的問題為：分類（classification）。
2. 預測值為連續(xù)值的問題為：回歸（regression）。
在我們預測西瓜是否是好瓜的過程中，我們事先已經知道了訓練集中瓜的好壞，學習器通過學習這些好瓜或差瓜的特征，從而總結出規(guī)律，即訓練集中的西瓜我們都做了標記，稱為標記信息。但也有沒有標記信息的情形：我們想將一堆西瓜根據(jù)特征分成兩個小堆，使得某一堆的西瓜盡可能相似，即都是好瓜或差瓜，對于這種問題，我們事先并不知道西瓜的好壞，樣本沒有標記信息。因此，我們定義：
1. 訓練數(shù)據(jù)有標記信息的學習任務為：監(jiān)督學習（supervised learning），容易知道上面所描述的分類和回歸都是監(jiān)督學習的范疇。
2. 訓練數(shù)據(jù)沒有標記信息的學習任務為：無監(jiān)督學習（unsupervised learning），常見的有聚類和關聯(lián)規(guī)則。
模型的評估
所有模型都不是完美的！每種模型都有自己的歸納偏好，只適用于特定情況。要談論算法的相對優(yōu)劣，必須要針對具體的學習問題。
第二章 模型評估與選擇
誤差與過擬合
一般來說，學習器的預測輸出和實際真實的輸出是有差異的，稱為誤差。我們定義：
1. 在訓練集上的誤差稱為訓練誤差（training error）或經驗誤差（empirical error）。
2. 在測試集上的誤差稱為測試誤差（test error）。
3. 學習器在所有新樣本上的誤差稱為泛化誤差（generalization error）。
如果學習器學的太差，對訓練樣本的一般性質沒學好，則稱為欠擬合underfitting。相反，如果學的「太好」，把訓練樣本自身的一些特點當成了所有潛在樣本都具有的一般性質，這種情況稱為過擬合overfitting。欠擬合比較容易克服，往往因為學習器學習能力太強大導致的過擬合很難處理，實際上過擬合是機器學習面臨的關鍵障礙。首先必須認識到，過擬合無法避免，我們需要做的是降低或者緩解：
機器學習面臨的問題通常是NP難或者更難，而有效的學習算法必然是在多項式時間內運行完成，若可徹底避免過擬合，則通過經驗誤差最小化就能獲得最優(yōu)解，這就意味著我們構造性地證明了P=NP。因此只要相信P≠NP，過擬合就不可避免。
評估方法
通常我們采用一個“測試集”來測試學習器對新樣本的判別能力，然后以“測試集”上的“測試誤差”作為“泛化誤差”的近似。顯然：我們選取的測試集應盡可能與訓練集互斥。
訓練集與測試集的劃分方法
一、留出法
將數(shù)據(jù)集D劃分為兩個互斥的集合，一個作為訓練集S，一個作為測試集T，滿足D=S∪T且S∩T=?，常見的劃分為：大約2/3-4/5的樣本用作訓練，剩下的用作測試。需要注意的是：訓練/測試集的劃分要盡可能保持數(shù)據(jù)分布的一致性，以避免由于分布的差異引入額外的偏差，常見的做法是采取分層抽樣。同時，由于劃分的隨機性，單次的留出法結果往往不夠穩(wěn)定，一般要采用若干次隨機劃分，重復實驗取平均值的做法。
二、交叉驗證法
將數(shù)據(jù)集D劃分為k個大小相同的互斥子集，滿足D=D1∪D2∪…∪Dk，Di∩Dj=?（i≠j），同樣地盡可能保持數(shù)據(jù)分布的一致性，即采用分層抽樣的方法獲得這些子集。交叉驗證法的思想是：每次用k-1個子集的并集作為訓練集，余下的那個子集作為測試集，這樣就有K種訓練集/測試集劃分的情況，從而可進行k次訓練和測試，最終返回k次測試結果的均值。交叉驗證法也稱“k折交叉驗證”，k最常用的取值是10，下圖給出了10折交叉驗證的示意圖。
與留出法類似，將數(shù)據(jù)集D劃分為K個子集的過程具有隨機性，因此K折交叉驗證通常也要重復p次，稱為p次k折交叉驗證，常見的是10次10折交叉驗證，即進行了100次訓練/測試。特殊地，當劃分的k個子集的每個子集中只有一個樣本時，稱為“留一法”，顯然，留一法的評估結果比較準確，但對計算機的消耗也是巨大的。
三、自助法
我們希望評估的是用整個D訓練出的模型。但在留出法和交叉驗證法中，由于保留了一部分樣本用于測試，因此實際評估的模型所使用的訓練集比D小，這必然會引入一些因訓練樣本規(guī)模不同而導致的估計偏差。留一法受訓練樣本規(guī)模變化的影響較小，但計算復雜度又太高了?！白灾ā闭墙鉀Q了這樣的問題。自助法的基本思想是：給定包含m個樣本的數(shù)據(jù)集D，每次隨機從D 中挑選一個樣本，將其拷貝放入D’，然后再將該樣本放回初始數(shù)據(jù)集D 中，使得該樣本在下次采樣時仍有可能被采到。重復執(zhí)行m 次，就可以得到了包含m個樣本的數(shù)據(jù)集D’?？梢缘弥趍次采樣中，樣本始終不被采到的概率取極限為：
這樣，通過自助采樣，初始樣本集D中大約有36.8%的樣本沒有出現(xiàn)在D’中，于是可以將D’作為訓練集，D-D’作為測試集。自助法在數(shù)據(jù)集較小，難以有效劃分訓練集/測試集時很有用，但由于自助法產生的數(shù)據(jù)集（隨機抽樣）改變了初始數(shù)據(jù)集的分布，因此引入了估計偏差。在初始數(shù)據(jù)集足夠時，留出法和交叉驗證法更加常用。
性能度量
性能度量就是建立衡量模型泛化能力的評價標準。不同的度量標準往往會導致不同的評判結果。因此模型的好壞是相對的，它不僅取決于算法和數(shù)據(jù)，還取決于任務需求。
回歸任務最常用的性能度量是均方誤差
E(f;D)=1/m*∑(f(xi)?yi)^2
以下介紹分類任務常用的性能度量。?
1. 錯誤率與精度?
2. 查準率precision、查全率recall與F1?
3. ROC與AUC?
4. 代價敏感錯誤率與代價曲線
錯誤率與精度
錯誤率是分類錯誤的樣本數(shù)占樣本總數(shù)的比例，精度則是分類正確的樣本占樣本總數(shù)的比例。
查準率、查全率與F1
所謂的查準率P和查全率R分別定義為：?
????????????????????????????????????????????????????P=TPTP+FP, ? ?R=TPTP+FN
變量是分類結果的混淆矩陣confusion matrix，表示為下表：
查準率是在所有預測結果為正例的情況下的真實比例。查全率是所有真實情況為正例的情況下預測正確的比例。
P和R是一對矛盾度量，所以一般會綜合兩方面考量學習器的好壞，找到最佳平衡點BEP（Break-Even Point）。衡點定義是查全率等于查準率時的取值。
BEP過于簡化，更常用的是F1變量，本質上是P和R的調和平均。?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1/F1=1/2*(1/P+1/R)
具體應用中可能對P和R有不同的倚重。比如商品推薦中，為了盡可能少打擾用戶，更希望推薦內容確是用戶感興趣的，這時候查準率更重要。而在逃犯檢索系統(tǒng)中，更希望盡可能少漏掉逃犯，此時查全率更重要。F1度量的一般形式Fβ就可以表達這種偏好。?
????????????????????????????????????????????????????1/Fβ=1/(1+β^2)(1/P+β^2/R)
也即是Fβ=(1+β^2)PR/(β^2P+R)
當β>1意味著P占比重更大，反之則是R。
ROC與AUC
ROC為受試者工作特征（Receiver Operating Characteristic)曲線，ROC曲線的縱軸是”真正例率“（True Positive Rate），橫軸是”假正例率“（False Positive Rate）。AUC是ROC曲線下的面積（Area Under ROC Curve），用來在兩個學習器的ROC曲線沒有發(fā)生交叉時，衡量比較兩個學習器的優(yōu)劣。
更詳細的公式、推導和圖例請翻看p.33-p.35。
代價敏感錯誤與代價曲線
不同的錯誤帶來的后果嚴重程度不一樣，因此我們需要為錯誤賦予一個“非均等代價”（unequal cost）。以二分類為例，我們可根據(jù)任務的領域知識設定一個“代價矩陣”（cost matrix）。(p.35 表2.2)
在非均等代價下，ROC曲線不能直接反應出學習器的期望總體代價，而代價曲線則可以達到目的（p.36）
注意！
本書將代價進行了歸一化處理，出來的代價曲線也全部是直線。事實上這并不完全正確，歸一化處理代價后，代價曲線也可以是曲線。具體的證明寫在了p.36頁，也可以參考知乎答主對代價曲線的理解：
https://www.zhihu.com/question/63492375
比較檢驗
機器學習中性能比較這件事情比大家想象的復雜得多，同一個學習方法在同一個測試集上多次運行，其結果都可能不同。而統(tǒng)計假設檢驗為我們進行學習器性能比較提供了重要依據(jù)
簡單來說，若在測試集上觀察到學習器A比B好，基于假設檢驗結果則能知道A的泛化性能是否在統(tǒng)計意義上優(yōu)于B，以及這個結論的把握有多大。
本書列出了四種統(tǒng)計檢驗方法：假設檢驗、交叉驗證t檢驗、McNemar檢驗、Friedman檢驗與Nemenyi后續(xù)檢驗。
公式圖表太多啦，參見p.38~p.44
偏差與方差
通過實驗，我們可以估計學習算法的泛化性能，另一方面通過偏差與方差，我們可以了解算法為什么具有這樣的性能，偏差-方差分解（bias-variance decomposition）就是用來解釋學習算法泛化性能的一種工具，試圖拆解期望泛化錯誤率：
書中對偏差、方差和噪聲三個概念進行了定義：
1. 偏差：度量學習算法的期望預測與真實結果的偏離程度，即刻畫了學習算法本身的擬合能力?
2. 方差：度量了同樣大小的訓練集的變動所導致的學習性能的變化，即刻畫了數(shù)據(jù)擾動所造成的影響?
3. 噪聲：表達了當前任務下任何學習算法所能達到的期望泛化誤差的下限，即刻畫了學習問題本身的難度
一般來說，偏差與方差是有沖突的，這稱為偏差-方差窘境（bias-variance dilemma）。當學習器剛開始學習時，因為學習程度不足，偏差會主導泛化錯誤率，隨著學習器擬合能力逐漸增強，數(shù)據(jù)集發(fā)生的擾動會被學習到，這時方差開始主導泛化錯誤率。在最后擬合能力非常強的情況下訓練數(shù)據(jù)自身的、非全局的特性被學習器學到了，則將發(fā)生過擬合。
第三章 線性模型
基本形式
1. 假定示例有d個屬性，x=(x1,x2,...,xd)? 2. 試圖通過屬性的線性組合進行預測
用向量形式表示就是：?
線性模型雖然簡單，但卻是基礎。先研究線性、單屬性的線性回歸問題，便可以進一步研究非線性、多屬性的回歸和分類問題。本章介紹了幾種經典的線性模型，從回歸任務開始，然后討論二分類和多分類問題。
線性回歸
根據(jù)已有的數(shù)據(jù)確定一個函數(shù)然后預測，怎樣衡量函數(shù)的準確度呢，均方誤差是常用的，幾何意義上是求得一條線使得所有的樣本到直線的歐式距離之和最小，基于均方誤差最小化進行模型求解的方法稱為最小二乘法，以單變量為例，求解w和b，有
我們要將均方差最小化，即：
將求解公式等于0可求得w和b的最優(yōu)封閉解：
多元線性回歸的參數(shù)求解以同樣的思路求解，多參數(shù)轉為矩陣涉及到矩陣逆的計算，在不滿秩的時候經常會出現(xiàn)不止一組解使得均方誤差最??；涉及到選擇偏好，處理時可加入正則化。也可以使用線性回歸的衍生物，即讓得到的模型和另外的函數(shù)產生關系lny=wx+b，這其實是輸入空間到輸出的一個非線性預測，對數(shù)線性回歸。
一般的，考慮單調可微函數(shù)g(·),令
這樣得到的模型稱為廣義線性模型（generalizeed linear model）。其中，g(·)成為聯(lián)系函數(shù)（link function）。顯然，對數(shù)線性回歸是廣義線性模型在g(·)=ln(·)時的特例。
對數(shù)幾率回歸
線性回歸討論了如何使用線性模型進行回歸學習，但若要做的是分類任務該怎么辦？式（3.15）可以給我們一個答案：只需找出一個單調可微函數(shù)，將分類任務的真實標記y與線性回歸模型的預測值聯(lián)系起來。
考慮二分類任務，其輸出標記y屬于{0,1}，而線性回歸模型產生的預測值z=wTx+b是實值，于是，我們需將實值z轉換為0/1值，最理想的是單位介躍函數(shù)（unit-step function）
但是單位介躍函數(shù)并不連續(xù)，因此不能用做g(·)，此時我們希望找到能在一定程度上近似單位介躍函數(shù)的替代函數(shù)(surrogate function），并希望他單調可微。對數(shù)幾率函數(shù)正是這樣一個常用的替代函數(shù)：
做一下變換可得：lny/(1?y)=wTx+b。y/1?y含義就是比率，為正例的可能性與為反例的可能性比值。
從本質上講，對數(shù)幾率回歸模型logistic regression就是在用線性回歸模型的預測結果去逼近真實標記的對數(shù)幾率。
對數(shù)幾率回歸模型雖然還是回歸模型，但卻是一種分類學習方法。之前普遍翻譯為邏輯回歸，意義相去甚遠，還是用對數(shù)幾率回歸比較符合一些。它的好處在于：?
1. 將分類進行建模，無需事先假設數(shù)據(jù)分布，避免假設分布不準確所帶來的問題?
2. 不僅分類，還可得到近似概率預測，可利用概率輔助決策?
3. 對率函數(shù)是任意階可導的凸函數(shù)，可方便求取最優(yōu)解
確定模型之后，接下來自然要做的就是確定w和b。這里要使用到的方法是極大似然法maximum likelihood method。過程省略，最后我們需要最小化：
上式為關于β的高階可導連續(xù)凸函數(shù)，根據(jù)凸優(yōu)化理論，利用經典的數(shù)值優(yōu)化算法如梯度下降法、牛頓法都可求得最優(yōu)解。
線性判別分析
線性判別分析Linear Discriminant Analysis是一種經典的線性學習方法，應用于分類任務中。
LDA的思想非常簡單，將訓練集的樣本投影到一條直線上，同一類的盡量互相靠近，而不同類之間盡可能相隔的遠。使用數(shù)學語言，投影即是向量乘積， 同一類盡量靠近，就是協(xié)方差要小，不同類相隔遠，就是類中心距離遠，也就是均值投影的差要大。如圖所示：
基于這樣的考慮，LDA定義了兩個散度矩陣：類內散度矩陣（越小越好）?類間散度矩陣(越大越好)，最后得到了LDA的最大化目標：“廣義瑞利商”。
為了確定w的曲直，書中采用了拉格朗日乘子法求解，具體見p.61-p.62。
LDA同樣可應用于多分類任務中，方法類似于二分類，具體可見p.62-p.63。
最后補充兩點：?
1. 從貝葉斯決策理論的角度可以證明LDA在兩類數(shù)據(jù)同先驗、滿足高斯分布且協(xié)方差相等時，LDA可達到最優(yōu)分類。?
2. LDA核心是投影，這樣往往實現(xiàn)了降維，因而LDA也常被視為一種經典的監(jiān)督降維技術。
多分類問題
多分類的問題常常是使用差分策略，通過二分類學習來解決多分類問題，即將多分類問題拆解為多個二分類訓練二分類學習器最后通過繼承得到結果，最經典拆分策略有三種：“一對一”（OvO）、“一對其余”（OvR）和“多對多”（MvM），核心思想與示意圖如下所示：
具體選擇哪一種，要看具體情況下的存儲和時間開銷，以及性能高低。
一對一OvO
假設訓練集有四類樣本，C1,C2,C3,C4，訓練時兩兩組合為二分類進行訓練，新樣本通過這C2N個分類器后會得到N(N?1)/2個分類結果，最終結果可根據(jù)這些分類結果投票產生。
一對其余OvR
訓練時一個類作為正例，其余所有類作為反例。這樣共有N個二分類器進行訓練，新樣本通過分類器時預測結果為正例的即為最終結果。
多對多MvM
本質上講前兩種情況都是MvM的特殊情況?；舅悸肥怯柧毤恳活愅ㄟ^多個分類器訓練會產生一組編碼結果，新樣本通過分類器產生的編碼結果與每個分類器的結果求距離，距離最短者即為最終結果。
這里常用的MvM編碼技術是：糾錯輸出碼ECOC Error Correcting Output Codes，其關鍵在于：?
1. 如何劃分類別形成二分類訓練集，也就是編碼?
2. 解碼，選擇如海明距離、歐式距離作為衡量，同時糾錯能力強，能容錯
類別不平衡問題
類別不平衡就是指分類任務中，不同類別的訓練樣例數(shù)目差別很大的情況。舉個很簡單的例子，1000個樣本，有998個是反例，2個是正例，那么一個對樣本永遠只預測為反例的學習器也能實現(xiàn)99.8%的正確率，但這種學習器顯然是沒有用的。
本節(jié)假定了正類樣例較少，反類樣例較多。在現(xiàn)實的分類學習任務中，我們經常會遇到類別不平衡。因此我們必須了解類別不平衡性處理的基本方法。
一個基本策略是再縮放rescaling。
在之前的比率回歸問題上，y1?y代表正例可能性與反例可能性的比值，那么如果y/(1?y)>1就可預測為正例。而在類別不平衡的樣本中，假設正例數(shù)目為m+，反例數(shù)目為m?（一般正例數(shù)目小于反例數(shù)目）。我們可設定學習器的決策條件為：當y/(1?y)>m+/m?即可預測為正例。那么比率即可重改為y′/(1?y′)=[y/(1?y)][m?/m+]。
在實際操作中，再縮放卻沒那么容易，主要原因是不一定能有效的基于訓練集觀測幾率去推斷真實幾率。因而往往有三類做法：?
1.?欠采樣undersampling：去除一些反例數(shù)目，使得正例數(shù)目接近于反例數(shù)目，再進行學習。需要注意，若直接丟棄反例，可能會造成重要信息丟失，一種方法是利用集成學習機制，將反例劃分為若干個集合供不同學習器使用，這樣每個學習器就相當于欠采樣，而全局看則沒有丟失重要信息?
2.?過采樣oversampling：增加正例數(shù)目，為防止過擬合，可對訓練集正例進行插值產生額外正例，而不是直接重復采樣初始正例樣本?
3.?閾值移動threshold-moving：直接基于原訓練集進行學習，但用訓練好的分類器進行預測時，將y′/(1?y′)=[y/(1?y)][m?/m+]嵌入決策中
