機(jī)器學(xué)習(xí)? 經(jīng)驗(yàn) 數(shù)據(jù)
數(shù)據(jù)中產(chǎn)生模型model 的算法? 學(xué)習(xí)算法? learning algorithm
數(shù)據(jù)集 data set 示例instance? 樣本 sample
屬性attribute? 特征feature 屬性值 attribute value
屬性空間attribute space? 樣本空間 sample space
特征向量? feature vector
維數(shù) dimensionality
學(xué)習(xí)learning? 訓(xùn)練 training
訓(xùn)練數(shù)據(jù) training data 訓(xùn)練樣本 training sample
訓(xùn)練集 training set
假設(shè) hypothesis
真實(shí) 真相 ground-truth
學(xué)習(xí)器learner
預(yù)測(cè) prediction
label 標(biāo)記 example 樣例
標(biāo)記空間 label space 輸出空間
classification 分類
回歸 regression
binary classification 二分類
positive class 正類? negative class 反類
多分類 multi-class classification
測(cè)試 testing? 測(cè)試樣本 testing sample
clustering 聚類 cluster 簇
監(jiān)督學(xué)習(xí) supervised learning? 分類和回歸
無(wú)監(jiān)督學(xué)習(xí) unsupervised learning? 聚類
泛化 generalization 樣本空間 測(cè)試空間
分布 distribution
獨(dú)立同分布 independent and identically distributed i.i.d.
假設(shè)空間：
歸納 induction? ? 泛化 generation? inductive learning
演繹 deduction? 特化 specilization
歸納學(xué)習(xí) = 樣例中學(xué)習(xí) + 數(shù)據(jù)中學(xué)習(xí) 概念 concept? 概念學(xué)習(xí)
假設(shè)空間搜索 hypothesis space? fit匹配假設(shè)
學(xué)習(xí)過(guò)程是基于優(yōu)先樣本訓(xùn)練集進(jìn)行的? 存在一個(gè)假設(shè)集合? 版本空間 version space
歸納偏好 機(jī)器學(xué)習(xí)算法在學(xué)習(xí)過(guò)程中對(duì)某種類型假設(shè)的偏好 歸納偏好
歸納偏好 學(xué)習(xí)算法自身在一個(gè)可能很龐大的假設(shè)空間中對(duì)假設(shè)進(jìn)行選擇的啟發(fā)式或價(jià)值觀
奧卡姆剃刀? 若有多個(gè)假設(shè)與觀察一致 選擇最簡(jiǎn)單的那個(gè)
沒(méi)有免費(fèi)的午餐 NoFreeLaunch Theorem
NFL定理：學(xué)習(xí)算法的期望值都會(huì)相同。? 問(wèn)題均勻分布
前提：所有 問(wèn)題出現(xiàn)的機(jī)會(huì)相同 或所有問(wèn)題同等重要
脫離具體問(wèn)題 空談 什么學(xué)習(xí)算法 更好? 毫無(wú)意義。
任何一個(gè)算法都是有適用范圍的。
機(jī)器學(xué)習(xí)的發(fā)展史：
artificial intelligence -> 邏輯理論家：邏輯推理就是智能
（通用問(wèn)題求解）? -> 知識(shí)? 知識(shí)就是力量? 知識(shí)工程 專家系統(tǒng) ->
基于神經(jīng)網(wǎng)絡(luò)的 連接主義 connectionism
基于邏輯表示的符號(hào)主義 symbolism學(xué)習(xí)
以決策理論為基礎(chǔ)的學(xué)習(xí)技術(shù)和強(qiáng)化學(xué)習(xí)技術(shù)
->? 機(jī)器學(xué)習(xí) 劃分為
從樣例中學(xué)習(xí) 在問(wèn)題求解和規(guī)劃中學(xué)習(xí)
通過(guò)觀察和發(fā)現(xiàn)學(xué)習(xí)? 從指令中學(xué)習(xí)
機(jī)械學(xué)習(xí)? 示教學(xué)習(xí) 類比學(xué)習(xí)? 和 歸納學(xué)習(xí)
-> 樣例中學(xué)習(xí) 符號(hào)主義學(xué)習(xí)
主要有決策樹和基于邏輯的學(xué)習(xí)（基于歸納邏輯程序設(shè)計(jì) Inductive Logic Programming ILP）
基于神經(jīng)網(wǎng)絡(luò)的連接主義學(xué)習(xí)? BP算法? 連接主義最大的局限是其試錯(cuò)性
統(tǒng)計(jì)學(xué)習(xí)? statistical? learning
支持向量機(jī)? Support Vector Machine? (文本分類)
核方法 kernel method
支持向量 VC維 結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則
深度學(xué)習(xí) 多層的神經(jīng)網(wǎng)絡(luò)
過(guò)擬合? 欠擬合
理論 + 實(shí)驗(yàn)? = 理論 + 實(shí)驗(yàn) + 計(jì)算? = 計(jì)算科學(xué)
計(jì)算目的 數(shù)據(jù)分析 素具科學(xué)核心是通過(guò)分析數(shù)據(jù)獲取價(jià)值
機(jī)器學(xué)習(xí)? 云計(jì)算 眾包 crowdsourcing
統(tǒng)計(jì)學(xué)主要是通過(guò)機(jī)器學(xué)習(xí)對(duì)數(shù)據(jù)挖掘發(fā)揮影響 機(jī)器學(xué)習(xí)領(lǐng)域和數(shù)據(jù)庫(kù)領(lǐng)域則是數(shù)據(jù)挖掘的兩大支撐
transfer learning? 遷移學(xué)習(xí)? 類比學(xué)習(xí) learning by analogy
國(guó)際機(jī)器學(xué)習(xí)會(huì)議ICML
國(guó)際神經(jīng)信息處理系統(tǒng)會(huì)議 NIPS
國(guó)際學(xué)習(xí)理論會(huì)議 COLT
歐洲機(jī)器學(xué)習(xí)會(huì)議 ECML
亞洲機(jī)器學(xué)習(xí)會(huì)議 ACML
Journal of Machine Learning Research? ? Machine Learning
人工智能：IJCAI AAAI? Artificial Intelligence Journal Of Artificial Intelligence Research
數(shù)據(jù)挖掘：KDD ICDM Data Mining and Knowledge Discovery
ACM Transactions on Knowledge Discovery from Data
計(jì)算視覺(jué)和模式識(shí)別：CVPR IEEE Transaction on Pattern Analysis and Machine Intelligence
神經(jīng)網(wǎng)絡(luò)：Neural Computation IEEE Transaction on Neural Networks and Learning Systems
中國(guó)機(jī)器學(xué)習(xí)大會(huì) CCML? 機(jī)器學(xué)習(xí)及其應(yīng)用 研討會(huì)? MLA
模型評(píng)估與選擇：
錯(cuò)誤率? error rate 精度 accuracy
誤差 error
訓(xùn)練誤差 training error? 經(jīng)驗(yàn)誤差 empirical error
泛化誤差 generalization error
過(guò)擬合 overfitting? 訓(xùn)練樣本自身的一些特點(diǎn)當(dāng)做所有潛在樣本都會(huì)具有的一般性質(zhì) 泛化能力下降
欠擬合 underfitting
過(guò)擬合 學(xué)習(xí)能力過(guò)于強(qiáng)大 訓(xùn)練樣本的不太一般的特性也包含在內(nèi)
欠擬合學(xué)習(xí)能力低下造成的? 欠擬合解決方法：決策樹擴(kuò)展分支 神經(jīng)網(wǎng)絡(luò)中增加訓(xùn)練輪數(shù)
過(guò)擬合：無(wú)法徹底避免 緩解或者減小其風(fēng)險(xiǎn)
機(jī)器學(xué)習(xí)面臨的是NP難和更難? 有效的算法必須在多項(xiàng)式時(shí)間內(nèi)解決
模型選擇? model selection
測(cè)試集 testing set? 測(cè)試誤差 testing error
作為泛化誤差的近化
測(cè)試樣本也是從樣本真實(shí)分布中獨(dú)立同分布采樣而得
測(cè)試集盡可能與訓(xùn)練集互斥
留出法? hold-out? 數(shù)據(jù)集劃分為兩個(gè)互斥的集合 一個(gè)是訓(xùn)練集s 測(cè)試集t
測(cè)試集訓(xùn)練集的劃分要保持?jǐn)?shù)據(jù)分布的一致性
采樣sampling 中的分層采樣 stratified sampling
若干次隨機(jī)劃分 重復(fù)進(jìn)行實(shí)驗(yàn)評(píng)估后取平均值作為留出法的評(píng)估結(jié)果
三分之二 至? 五分之四 樣本用于訓(xùn)練? 剩余樣本用于測(cè)試
交叉驗(yàn)證法 cross validation
將數(shù)據(jù)集D劃分為k個(gè)大小相似的互斥子集 每個(gè)子集盡量保持?jǐn)?shù)據(jù)分布的一致性
從D中通過(guò)分層采樣得到? k-1個(gè)子集并集作為訓(xùn)練集? 余下的子集作為測(cè)試集
k組訓(xùn)練/測(cè)試集? k次訓(xùn)練和測(cè)試
交叉驗(yàn)證評(píng)估結(jié)果穩(wěn)定性和保真性 很大程度上取決于k
k折交叉驗(yàn)證 k-fold cross validation? k通常取10
為減少因樣本劃分不同而引起的差別 k折交叉驗(yàn)證通常要隨機(jī)使用不同的劃分p次
p次k折交叉驗(yàn)證結(jié)果的均值? 10次10折交叉驗(yàn)證
留一法? Leave-One-Out LOO
不受隨機(jī)樣本劃分方式的影響 因?yàn)閙個(gè)樣本只有唯一的方式劃分為m個(gè)子集
每個(gè)子集包含一個(gè)樣本 過(guò)擬合? 也會(huì)導(dǎo)致模型計(jì)算開銷過(guò)大
自助法：bootstrapping
自助采樣法 bootstrap sampling
自助法在數(shù)據(jù)集較小 難以有效劃分訓(xùn)練 測(cè)試集時(shí)很有用
自助法從初始數(shù)據(jù)集中產(chǎn)生多個(gè)不同的訓(xùn)練集
調(diào)參與最終模型
參數(shù) parameter? 參數(shù)配置不同? 學(xué)得模型性能不同
選擇學(xué)習(xí)算法? 算法參數(shù)進(jìn)行設(shè)定 參數(shù)調(diào)節(jié)? parameter tuning
對(duì)每個(gè)參數(shù)選定一個(gè)范圍和變化步長(zhǎng)
驗(yàn)證集 validation set 模型評(píng)估和選擇中用于評(píng)估測(cè)試的數(shù)據(jù)集
性能度量 performance measure
回歸任務(wù)：均方誤差 mean squared error
分類任務(wù)：
錯(cuò)誤率和精度? 二分類和多分類
錯(cuò)誤率：分類錯(cuò)誤的樣本數(shù)占樣本總數(shù)的比例
精度：分類正確的樣本數(shù)占樣本總數(shù)的比例
查準(zhǔn)率：precision TP/(TP + FP)
查全率：recall? ? TP/(TP+FN)
預(yù)測(cè)結(jié)果為正例? 預(yù)測(cè)結(jié)果為反例
真實(shí)情況正例? TP真正例? ? ? ? ? FN假反例
真實(shí)情況反例? FP假正例? ? ? ? ? TN真反例
查準(zhǔn)率和查全率比較矛盾? 查準(zhǔn)率高 查全率偏低
查全率高 查準(zhǔn)率偏低
查準(zhǔn)率和查全率 p-r 曲線圖
F1值 = （2*p*R） / (P + R)
ROC 曲線
縱軸是 真正例率 True Positive Rate TPR
橫軸是 假正例率 False Positive Rate FPR
一個(gè)學(xué)習(xí)器的ROC曲線被另一個(gè)學(xué)習(xí)器的曲線完全包住 后者性能優(yōu)于前者
交叉的話 AUC Area Under ROC Curve? 比較ROC曲線下的面積
代價(jià)敏感錯(cuò)誤和代價(jià)曲線：
不同類型的錯(cuò)誤所造成的后果不同 ，
為權(quán)衡不同類型錯(cuò)誤所造成的不同損失 為錯(cuò)誤賦予 非均等代價(jià) unequal cost
以二分類任務(wù)為例，根據(jù)任務(wù)的領(lǐng)域知識(shí)設(shè)定一個(gè) 代價(jià)矩陣 cost matrix
之前的性能度量中 隱式的假設(shè)了均等代價(jià) 直接計(jì)算錯(cuò)誤次數(shù) 未考慮不同錯(cuò)誤造成的不同后果
在非均等代價(jià)下 不再是簡(jiǎn)單的最小化錯(cuò)誤次數(shù) 而是最小化 總體代價(jià) total cost
代價(jià)曲線 cost curve
比較檢驗(yàn)：
比較泛化性能，測(cè)試集上的性能與測(cè)試集關(guān)系很大，機(jī)器學(xué)習(xí)算法本身具有一定的隨機(jī)性
統(tǒng)計(jì)假設(shè)檢驗(yàn) hypothesis test
假設(shè)檢驗(yàn)? ? 根據(jù)測(cè)試錯(cuò)誤率推出泛化的錯(cuò)誤率的分布
對(duì)單個(gè)學(xué)習(xí)器泛化性能的假設(shè)進(jìn)行檢驗(yàn)
交叉驗(yàn)證t檢驗(yàn)：不同學(xué)習(xí)器的性能進(jìn)行檢驗(yàn)
McNemar檢驗(yàn) 一個(gè)數(shù)據(jù)集上比較兩個(gè)算法的性能
基于算法排序的Friedman檢驗(yàn)
偏差-方差分解 bias-variance decomposition
解釋學(xué)習(xí)算法泛化性能的一種重要工具
偏差-方差分解 對(duì)學(xué)習(xí)算法的期望泛化錯(cuò)誤率 進(jìn)行拆解
算法在不同訓(xùn)練集上學(xué)得的結(jié)果很可能不同
泛化誤差可分為偏差、方差與噪聲之和
偏差度量了學(xué)習(xí)算法的期望預(yù)測(cè)與真實(shí)結(jié)果的偏離程度 刻畫了學(xué)習(xí)算法本身的擬合問(wèn)題
方差度量了同樣大小訓(xùn)練集變動(dòng)所導(dǎo)致的學(xué)習(xí)性能的變化，刻畫了數(shù)據(jù)擾動(dòng)所造成的影響
噪聲表達(dá)了當(dāng)前任務(wù)上任何學(xué)習(xí)算法所能達(dá)到的期望泛化誤差的下界，刻畫了學(xué)習(xí)問(wèn)題本身的難度。
偏差-方差分解說(shuō)明 泛化性能是由學(xué)習(xí)算法的性能、數(shù)據(jù)的充分性以及學(xué)習(xí)任務(wù)本身的難度所共同決定的。
給定學(xué)習(xí)任務(wù)，為了取得好的泛化性能，需使偏差較小，
即能夠充分?jǐn)M合數(shù)據(jù)，并且使方差較小，即數(shù)據(jù)擾動(dòng)產(chǎn)生的影響小。
偏差—方差窘境 bias-variance dilemma
訓(xùn)練不足時(shí) 欠擬合 訓(xùn)練數(shù)據(jù)的擾動(dòng)不足以使學(xué)習(xí)器產(chǎn)生顯著變化
此時(shí)偏差主導(dǎo)了泛化錯(cuò)誤率；
學(xué)習(xí)器的擬合能力增強(qiáng)，訓(xùn)練數(shù)據(jù)擾動(dòng) 被學(xué)習(xí)器學(xué)習(xí)到 方差主導(dǎo)了泛化錯(cuò)誤率。
自助采樣法很有用，代價(jià)曲線 2006 發(fā)明，誤分類代價(jià) 測(cè)試代價(jià) 標(biāo)記代價(jià) 屬性代價(jià)
線性模型：? 形式簡(jiǎn)單 易于建模
Linear mode
線性回歸 Linear regression
均方誤差? 歐幾里得距離
基于均方誤差最小化進(jìn)行模型求解的方法 成為最小二乘法 least square method
線性回歸中 最小二乘法視圖找到一條直線 使所有樣本到直線上的歐氏距離之和最小
對(duì)數(shù)幾率回歸：Sigmoid函數(shù)
分類學(xué)習(xí)方法
線性判別分析 Linear Discriminant Analysis LDA
給定訓(xùn)練樣例集 設(shè)法將樣例投影到一條直線上，使得同類樣例的投影點(diǎn)盡可能近、
異類樣例的投影點(diǎn)盡可能遠(yuǎn)；在對(duì)新樣本進(jìn)行分類時(shí)，將其投影到同樣的這條直線上，
再根據(jù)投影點(diǎn)的位置確定新樣本的類別。
同類樣例投影點(diǎn)的協(xié)方差盡可能小，異類樣例的投影點(diǎn)盡可能遠(yuǎn)離，類中心之間的舉例盡可能大
類內(nèi)散度矩陣? within-class scatter matrix
類間散度矩陣? between-class scatter matrix
LDA 可從貝葉斯決策理論的角度闡釋 當(dāng)兩類數(shù)據(jù)同先驗(yàn)、滿足高斯分布且協(xié)方差相等時(shí)，LDA可達(dá)到最優(yōu)分類
多分類LDA可以將樣本投影到N-1維空間，N-1通常遠(yuǎn)小于數(shù)據(jù)原有的屬性數(shù)，
通過(guò)投影減小樣本點(diǎn)的維數(shù)，且投影過(guò)程中使用了類別信息。
LDA常被視為經(jīng)典的監(jiān)督將維技術(shù)
多分類學(xué)習(xí)：
利用二分類學(xué)習(xí)器解決多分類問(wèn)題
拆解法? 將多分類任務(wù)拆分為若干個(gè)二分類任務(wù)求解
先對(duì)問(wèn)題進(jìn)行拆分，然后為拆出的每個(gè)二分類任務(wù)訓(xùn)練一個(gè)分類器
最經(jīng)典的拆分策略有：一對(duì)一? OvO? 一對(duì)其余 OvR? 多對(duì)多 MvM
假定數(shù)據(jù)集合有N個(gè)類別，OvO將這N個(gè)類別兩兩配對(duì)，從而產(chǎn)生N(N-1)/2 個(gè)二分類任務(wù)，
例子：
OvO將為區(qū)分類別Ci 和 Cj 訓(xùn)練一個(gè)分類器，該分類器把數(shù)據(jù)集中的Ci類樣例當(dāng)做正例，
Cj類樣例作為反例，在測(cè)試階段，新樣本將同時(shí)提交給所有分類器，得到了N(N-1)/2
個(gè)分類結(jié)果，最終結(jié)果根據(jù)投票產(chǎn)生，即把被預(yù)測(cè)的最多的類別作為分類結(jié)果。
OvR 每次將一個(gè)類的樣例作為正例，所有其他類的樣例作為反例來(lái)訓(xùn)練N個(gè)分類器，在測(cè)試時(shí)若僅有一個(gè)分類器預(yù)測(cè)為正類，
則對(duì)應(yīng)的類別標(biāo)記為最終分類結(jié)果，若有多個(gè)分類器預(yù)測(cè)為正類，
則通?？紤]各分類器的預(yù)測(cè)置信度，選擇置信度大的類別標(biāo)記作為分類結(jié)果。
OvR只需訓(xùn)練N個(gè)分類器，OvO訓(xùn)練N(N-1)/2 個(gè)分類器，OvO存儲(chǔ)開銷和測(cè)試時(shí)間開銷
通常比OvR更大，但在訓(xùn)練時(shí)，OvR的每個(gè)分類器均使用全部訓(xùn)練樣例，而OvO的每個(gè)分類器僅用到兩個(gè)類的樣例，
預(yù)測(cè)性能，取決于數(shù)據(jù)分布，多數(shù)情形下，兩者差不多。
MvM 每次將若干類作為正類，其他類作為反類，
糾錯(cuò)輸出碼 Error Correcting Output Codes ECOC
編碼：對(duì)N個(gè)類別做M次劃分，每次劃分將一部分類別劃分為正類，
一部分劃分為反類，從而形成一個(gè)二分類訓(xùn)練集；一共產(chǎn)生多個(gè)M個(gè)訓(xùn)練集
，可訓(xùn)練出M個(gè)分類器。
解碼：M個(gè)分類器分別對(duì)測(cè)試樣本進(jìn)行預(yù)測(cè)，這些預(yù)測(cè)標(biāo)記組成一個(gè)編碼，
將這個(gè)預(yù)測(cè)編碼與每個(gè)類別各自的編碼進(jìn)行比較，
返回其中距離最小的類別作為最終預(yù)測(cè)結(jié)果。
類別不平衡問(wèn)題
類別不平衡class-imbalance 是指分類任務(wù)中
不同類別的訓(xùn)練樣例數(shù)目差別很大的情況，
通常在預(yù)測(cè)分類時(shí)，我們會(huì)得到一個(gè)預(yù)測(cè)值y，將這個(gè)值與一個(gè)閾值進(jìn)行比較，
通常是0.5，大于0.5稱為正例，否則為反例，y實(shí)際上表達(dá)了正例的可能性，
幾率y/(1-y) 則反映了正例可能性和反例可能性之間的比值，閾值設(shè)置為0.5則默認(rèn)
正反例之間的可能性相同，分類器決策規(guī)則為： y/(1-y) 》 1 預(yù)測(cè)為正例
訓(xùn)練集中正反例數(shù)目不同時(shí)，m+表示正例數(shù)目? m-? 表示反例數(shù)目，則觀測(cè)幾率是
m+ / m-,? 通常假設(shè)：訓(xùn)練集是真實(shí)樣本總體的無(wú)偏采樣，因此觀測(cè)幾率就是代表了
真實(shí)幾率。
于是 只要分類器預(yù)測(cè)幾率高于觀測(cè)幾率就應(yīng)判定為正例，
y/(1-y) > m+/m-? 預(yù)測(cè)為正例
yy / (1-yy) = y/(1-y) * (m-/m+)
類別不平衡的一個(gè)基本策略 -- 再縮放
再縮放 思路簡(jiǎn)單，但是實(shí)際操作很難：訓(xùn)練集是真實(shí)樣本總體的無(wú)偏采樣
直接對(duì)訓(xùn)練集里的反類樣例進(jìn)行
欠采樣 undersampling： 去除一些反例 使得正反例數(shù)目接近 然后再進(jìn)行學(xué)習(xí)
對(duì)訓(xùn)練集里正類樣例進(jìn)行過(guò)采樣? oversampling? 增加一些正使得正反例數(shù)目接近，
然后再進(jìn)行學(xué)習(xí)
直接基于原始訓(xùn)練集進(jìn)行學(xué)習(xí)，用訓(xùn)練好的分類器進(jìn)行預(yù)測(cè)時(shí)，將再縮放公式
嵌入到?jīng)Q策過(guò)程中，成為"閾值移動(dòng)" threshold-moving
過(guò)采樣法不能簡(jiǎn)單的對(duì)初始正例樣本進(jìn)行重復(fù)采樣，否則會(huì)招致嚴(yán)重的過(guò)擬合，
過(guò)采樣法代表性算法是SMOTE 是通過(guò)對(duì)訓(xùn)練集里的正例進(jìn)行插值來(lái)產(chǎn)生額外的正例；
另一方面，欠采樣法不能隨機(jī)丟棄反例，可能會(huì)丟失一些重要信息。
欠采樣法的代表性算法EasyEnsemble 利用集成學(xué)習(xí)機(jī)制，將反例劃分為若干個(gè)集合供不同的學(xué)習(xí)器使用。
這樣對(duì)于每個(gè)學(xué)習(xí)器來(lái)看都是欠采樣，但在全局來(lái)看卻不會(huì)丟失重要信息。
再縮放，也是代價(jià)敏感學(xué)習(xí) cost-sensitive learning
m-/m+? 用 cost-/cost+? 代替即可，cost+ 是將正例誤分為反例的代價(jià)
cost- 將反例誤分為正例的代價(jià)
稀疏表示? sparse representation
多分類學(xué)習(xí) 雖然有多個(gè)類別 但是每個(gè)樣本僅屬于一個(gè)類別
一個(gè)樣本同時(shí)預(yù)測(cè)出多個(gè)類別標(biāo)記 多標(biāo)記學(xué)習(xí) multi-lable learning
決策樹： decision tree
從給定訓(xùn)練數(shù)據(jù)集學(xué)得一個(gè)模型 用以對(duì)新示例進(jìn)行分類
決策樹基于樹結(jié)構(gòu)進(jìn)行決策 人類在面臨決策問(wèn)題時(shí)一種很自然的處理機(jī)制
一顆決策樹包含一個(gè)根節(jié)點(diǎn) 若干個(gè)內(nèi)部結(jié)點(diǎn)和若干個(gè)葉節(jié)點(diǎn) 葉節(jié)點(diǎn)對(duì)應(yīng)于決策結(jié)果，
其他每個(gè)結(jié)點(diǎn)則對(duì)應(yīng)于一個(gè)屬性測(cè)試
每個(gè)結(jié)點(diǎn)包含的樣本集合 根據(jù)屬性測(cè)試的結(jié)果被劃分到子結(jié)點(diǎn)中
根節(jié)點(diǎn)包含樣本全集 從根節(jié)點(diǎn)到每個(gè)葉結(jié)點(diǎn)的路徑對(duì)應(yīng)了一個(gè)判定測(cè)試序列
決策樹學(xué)習(xí)為了產(chǎn)生一顆泛化能力強(qiáng)? 處理未見示例能力強(qiáng)的決策樹
基本流程遵循簡(jiǎn)單且直觀的 分而治之 divide-and-conquer
決策樹的生成是一個(gè)遞歸過(guò)程，決策樹基本算法中，三種情形導(dǎo)致遞歸返回，
當(dāng)前節(jié)點(diǎn)包含的樣本全屬于一個(gè)類別，無(wú)需劃分
當(dāng)前屬性集為空，或是所有樣本在所有屬性上取值相同，無(wú)法劃分
-- 當(dāng)前結(jié)點(diǎn)標(biāo)記為葉子結(jié)點(diǎn)，其類別設(shè)置為該結(jié)點(diǎn)所含樣本最多的類別
-- 利用當(dāng)前結(jié)點(diǎn)的后驗(yàn)分布
當(dāng)前節(jié)點(diǎn)包含的樣本集合為空 不能劃分
-- 當(dāng)前結(jié)點(diǎn)標(biāo)記為葉子結(jié)點(diǎn) 其類別設(shè)定為其父節(jié)點(diǎn)所含樣本最多的類別
-- 父節(jié)點(diǎn)的樣本分布作為當(dāng)前結(jié)點(diǎn)的先驗(yàn)分布
決策樹的學(xué)習(xí)關(guān)鍵是如何選擇最優(yōu)劃分屬性，
一般而言，隨著劃分過(guò)程不斷進(jìn)行，決策樹的分支結(jié)點(diǎn)所包含的樣本盡可能屬于同一類別，
即結(jié)點(diǎn)的“純度” purity? 越來(lái)越高
信息增益
信息熵 information entropy 度量樣本集合度常用的指標(biāo)
信息熵越小 集合純度越高
樣本數(shù)越多的分支結(jié)點(diǎn)影響越大，計(jì)算屬性a對(duì)樣本集D進(jìn)行劃分的
“信息增益” information gain
信息增益越大，意味著使用屬性a進(jìn)行劃分所獲得的 “純度提升” 越大
使用信息增益進(jìn)行決策樹的劃分屬性選擇 ID3決策樹算法以信息增益為準(zhǔn)則來(lái)劃分屬性
信息增益準(zhǔn)則對(duì)可取值數(shù)據(jù)較多的屬性有所偏好，（編號(hào)為屬性的話，N樣本N編號(hào)屬性值，編號(hào)的信息增益最大）
為減少這種偏好可能帶來(lái)的不利影響 C4.5算法 不直接使用信息增益，而是
使用增益率? gain rate選擇 最優(yōu)劃分屬性
增益率準(zhǔn)則可能對(duì)取值數(shù)目較少的屬性有所偏好，
C4.5并不是直接選擇增益率的最大候選劃分屬性，
而是使用一個(gè)啟發(fā)式：
先從候選劃分屬性中找出信息增益高于平均水平的屬性 再?gòu)闹羞x擇增益率最高的
基尼指數(shù)：
CART決策樹：分類和回歸任務(wù)都可用
基尼指數(shù)反映了從數(shù)據(jù)集中隨機(jī)抽取兩個(gè)樣本，其類別標(biāo)記不一致的概率 因此
基尼指數(shù)越小? 數(shù)據(jù)集合的純度越高
所以在選擇屬性劃分時(shí)? 基尼指數(shù)最小的屬性作為最優(yōu)劃分屬性
剪枝處理：
剪枝pruning 是決策樹學(xué)習(xí)中對(duì)付過(guò)擬合的主要手段
在決策樹學(xué)習(xí)中為了盡可能正確分類訓(xùn)練樣本，
節(jié)點(diǎn)劃分過(guò)程將不斷重復(fù) 有時(shí)會(huì)造成決策樹分支過(guò)多
訓(xùn)練樣本學(xué)習(xí)的太好了 把訓(xùn)練集當(dāng)中一些自身特點(diǎn)
當(dāng)作所有數(shù)據(jù)都具有的一般性質(zhì)而導(dǎo)致過(guò)擬合
可通過(guò)主動(dòng)去掉一些分支降低過(guò)擬合的風(fēng)險(xiǎn)
決策樹剪枝：
預(yù)剪枝 prepruning
后剪枝 post-pruning
預(yù)剪枝是在決策樹生成過(guò)程中，對(duì)每個(gè)結(jié)點(diǎn)在劃分前后進(jìn)行估計(jì)，
若當(dāng)前結(jié)點(diǎn)的劃分不能帶來(lái)決策樹泛化能力的提升，則
停止劃分并將當(dāng)前結(jié)點(diǎn)標(biāo)記為葉結(jié)點(diǎn)。
后剪枝是從訓(xùn)練集生成一棵完整的決策樹，然后自底向上地
對(duì)非葉節(jié)點(diǎn)進(jìn)行考察，若該結(jié)點(diǎn)所對(duì)應(yīng)的子樹替換為
葉結(jié)點(diǎn)能夠帶來(lái)決策樹泛化能力的性能提升，則將該字?jǐn)?shù)替換為葉子結(jié)點(diǎn)。
如何判斷決策樹泛化能力是否提升？
留出法
預(yù)剪枝使得決策樹很多分支都沒(méi)有“展開”，這不僅降低了過(guò)擬合的風(fēng)險(xiǎn)，
還顯著減少了決策樹的訓(xùn)練時(shí)間開銷和預(yù)測(cè)時(shí)間開銷，但另一方面，有些分支的
當(dāng)前劃分雖不能提升泛化性能、甚至可能導(dǎo)致泛化性能的暫時(shí)下降，但在其基礎(chǔ)上進(jìn)行的后續(xù)劃分卻
有可能導(dǎo)致性能顯著提高；預(yù)剪枝基于“貪心”本質(zhì)禁止這些分支展開，
給預(yù)剪枝決策樹帶來(lái)了欠擬合的風(fēng)險(xiǎn)。
后剪枝：
后剪枝先從訓(xùn)練集生成一顆決策樹。
后剪枝決策樹通常比預(yù)剪枝決策樹保留了更多的分支，
一般情形下，后剪枝決策樹的欠擬合風(fēng)險(xiǎn)很小，泛化性能往往優(yōu)于預(yù)剪枝決策樹，
但后剪枝過(guò)程是在生成完全決策樹之后進(jìn)行的，并且要自底向上地對(duì)樹中的
所有非葉結(jié)點(diǎn)進(jìn)行逐一考察，因此其訓(xùn)練時(shí)間開銷比未剪枝預(yù)測(cè)數(shù)和預(yù)剪枝決策樹
都要大得多。
對(duì)連續(xù)屬性進(jìn)行離散化? 二分法 對(duì)連續(xù)屬性進(jìn)行處理? C4.5
與離散屬性不同，若當(dāng)前結(jié)點(diǎn)劃分屬性為連續(xù)屬性，
該屬性還可作為其后代結(jié)點(diǎn)的劃分屬性。
缺失值處理：
不完整樣本，樣本的某些屬性值缺失
在屬性數(shù)目比較多的情況下，往往會(huì)有大量樣本出現(xiàn)缺失值
如果簡(jiǎn)單的放棄不完整樣本，僅使用無(wú)缺失值得樣本進(jìn)行學(xué)習(xí)，
顯然是對(duì)數(shù)據(jù)信息的極大浪費(fèi)。
如何在屬性值缺失情況下進(jìn)行劃分屬性選擇？
A:根據(jù)哪些屬性值沒(méi)有缺失的樣本來(lái)判斷屬性之間的優(yōu)劣
給定劃分屬性，若樣本在該屬性上的值缺失，如何對(duì)樣本進(jìn)行劃分？
A:若樣本x 在劃分屬性a上的取值未知，將x同時(shí)劃入所有子結(jié)點(diǎn)，
且樣本權(quán)值在于屬性值a-v 對(duì)應(yīng)的子結(jié)點(diǎn)中調(diào)整為 r-v? * Wx
直觀地說(shuō)，讓同一個(gè)樣本以不同的概率劃入到不同的子結(jié)點(diǎn)中去
將每個(gè)屬性視為坐標(biāo)空間中的一個(gè)坐標(biāo)軸，則d個(gè)屬性描述的樣本就
對(duì)應(yīng)了d維空間中的一個(gè)數(shù)據(jù)點(diǎn)，對(duì)樣本分類則意味著在這個(gè)坐標(biāo)空間中
尋找不同類樣本之間的分類邊界，決策樹所形成的分類邊界有一個(gè)明顯的特點(diǎn)：
軸平行 axis-parallel? 它的分類邊界由若干個(gè)與坐標(biāo)軸平行的分段組成
分類邊界的每一段都是與坐標(biāo)軸平行的，這樣的分類邊界使得學(xué)習(xí)結(jié)果有較好的
可解釋性，每一段劃分都直接對(duì)應(yīng)了某個(gè)屬性取值，但在學(xué)習(xí)任務(wù)的真實(shí)分類邊界比較復(fù)雜時(shí)，
必須使用很多段劃分才能獲得較好的近似。
多變量決策樹（斜決策樹）實(shí)現(xiàn)斜劃分 甚至更復(fù)雜劃分的決策樹，
此類決策數(shù)中，非葉子結(jié)點(diǎn)不再是僅對(duì)某個(gè)屬性，而是對(duì)屬性的線性組合進(jìn)行測(cè)試，
每個(gè)非葉結(jié)點(diǎn)都是一個(gè)線性分類器，，
在對(duì)變量決策樹學(xué)習(xí)中，不是為每個(gè)非葉結(jié)點(diǎn)尋找一個(gè)最優(yōu)化分屬性，而是
試圖創(chuàng)建一個(gè)合適的線性分類器。
決策樹學(xué)習(xí)算法 ID3? C4.5? ? CART
C4.5Rule是一個(gè)將C4.5決策樹轉(zhuǎn)化為符號(hào)規(guī)則的算法，
決策樹的每個(gè)分支可以容易地重寫為一條規(guī)則，
但C4.5Rule算法在轉(zhuǎn)化過(guò)程中，會(huì)進(jìn)行規(guī)則前件合并、刪減等操作，
因此，最終規(guī)則集的泛化性能甚至可能優(yōu)于原決策樹。
決策樹劃分選擇準(zhǔn)則對(duì)決策樹的尺寸有較大影響，但是對(duì)泛化性能的影響是有限的。
剪枝方法和程度對(duì)決策樹泛化性能的影響相當(dāng)顯著，實(shí)驗(yàn)研究表明：
在數(shù)據(jù)帶有噪聲時(shí)通過(guò)剪枝甚至可將決策樹的泛化性能提高25%
多變量決策樹算法先貪心地尋找每個(gè)屬性的最有權(quán)值，在局部?jī)?yōu)化的基礎(chǔ)上
再對(duì)分類邊界進(jìn)行隨機(jī)擾動(dòng)以試圖找到更好的邊界
引入線性分類器的最小二乘法；決策樹的葉子結(jié)點(diǎn)上嵌入神經(jīng)網(wǎng)絡(luò)，感知機(jī)樹
“增量學(xué)習(xí)”接收到新樣本后對(duì)已學(xué)得的模型進(jìn)行重新調(diào)整，
而不用完全重新學(xué)習(xí)，主要通過(guò)調(diào)整分支路徑上的劃分屬性次序
來(lái)對(duì)樹進(jìn)行部分重構(gòu)。? ID4，ID5R，
增量學(xué)習(xí)可以有效地降低每次接收到新樣本后的訓(xùn)練時(shí)間開銷，
但多不增量學(xué)習(xí)后的模型會(huì)與基于全部數(shù)據(jù)訓(xùn)練而得的模型有較大差別。
C4.5? J4.8(weka)? Classifier 4.0
神經(jīng)網(wǎng)絡(luò)：neural networks
由具有適應(yīng)性的簡(jiǎn)單單元組成的廣泛并行互連網(wǎng)絡(luò)，
它的組織能夠模擬生物神經(jīng)系統(tǒng)對(duì)真實(shí)世界物體所作出的交互反應(yīng)。
神經(jīng)元 模型? neuron == 簡(jiǎn)單單元
M-P神經(jīng)元模型：
神經(jīng)元接收到來(lái)自n個(gè)其他神經(jīng)元傳遞過(guò)來(lái)的輸入信號(hào)，
這些輸入信號(hào)通過(guò)帶權(quán)重的連接connection進(jìn)行傳遞，
神經(jīng)元接收到的總輸入值將與神經(jīng)元的閾值進(jìn)行比對(duì)，
然后通過(guò) 激活函數(shù) activation function 處理以產(chǎn)生神經(jīng)元的輸出
理想中的激活函數(shù)是階躍函數(shù)，將輸入值映射為輸出值0或者1，
1對(duì)應(yīng)于神經(jīng)元興奮，0對(duì)應(yīng)于神經(jīng)元抑制。
階躍函數(shù)不連續(xù)且不光滑，Sigmoid函數(shù)作為激活函數(shù)。
在較大范圍內(nèi)變化的輸入值擠壓到（0,1）輸出值范圍內(nèi)，
也成為擠壓函數(shù)（squashing function）
把許多個(gè)這樣的神經(jīng)元按一定層次結(jié)構(gòu)連接起來(lái)，得到了神經(jīng)網(wǎng)絡(luò)。
一個(gè)神經(jīng)網(wǎng)絡(luò)視為包含了許多參數(shù)的數(shù)學(xué)模型。這個(gè)模型是若干個(gè)函數(shù)
相互帶入嵌套而得。
感知機(jī)Perceptron 由兩層神經(jīng)元組成，輸入層接收外界輸入信號(hào)后傳遞給輸出層，
輸出層是M-P神經(jīng)元，閾值邏輯單元 threshold logic unit
給定訓(xùn)練數(shù)據(jù)集，權(quán)重Wi以及閾值可通過(guò)學(xué)習(xí)得到。
閾值可看做一個(gè)固定輸入為-1.0的啞結(jié)點(diǎn) dummy node所對(duì)應(yīng)的連接權(quán)重W（n+1）
這樣，權(quán)重和閾值的學(xué)習(xí)可統(tǒng)一為權(quán)重的學(xué)習(xí)。
若感知機(jī)對(duì)訓(xùn)練樣例預(yù)測(cè)準(zhǔn)確，則感知機(jī)不發(fā)生變化，否則將根據(jù)
錯(cuò)誤的程度進(jìn)行權(quán)重調(diào)整。
感知機(jī)只有輸出層神經(jīng)元進(jìn)行激活函數(shù)處理，即只擁有一層功能神經(jīng)元。
與或非都是線性可分的問(wèn)題，
若兩類模型是線性可分的，即存在一個(gè)線性超平面能將他們分開，
感知機(jī)的學(xué)習(xí)過(guò)程一定會(huì)收斂converge，否則感知機(jī)學(xué)習(xí)過(guò)程中會(huì)發(fā)生
震蕩（fluctuation），其權(quán)重難以穩(wěn)定，不能求得合適解。
感知機(jī)無(wú)法解決異或此類的非線性可分問(wèn)題。
解決非線性可分問(wèn)題，需要考慮使用多層功能神經(jīng)元，
簡(jiǎn)單的兩層感知機(jī)能解決異或問(wèn)題，輸出層與輸入層之間存在一層神經(jīng)元，
隱含層 hidden layer，
多層前饋神經(jīng)網(wǎng)絡(luò)：
每層神經(jīng)元與下一層神經(jīng)元全互連，神經(jīng)元之間不存在同層連接，也不存在夸層連接。
前饋不是指網(wǎng)絡(luò)中信號(hào)不能向后傳遞，而是指網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)上不存在環(huán)或回路。
其中輸入層神經(jīng)元接收外界輸入，隱層與輸出層神經(jīng)元對(duì)信號(hào)進(jìn)行加工，
最終結(jié)果由輸出層神經(jīng)元輸出，輸入層神經(jīng)元僅是接收輸入，
不進(jìn)行函數(shù)處理，隱層與輸出層包含功能神經(jīng)元。
神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)過(guò)程，根據(jù)訓(xùn)練數(shù)據(jù)來(lái)調(diào)整神經(jīng)元之間的連接全 connection weight，
以及每個(gè)功能神經(jīng)元的閾值，神經(jīng)網(wǎng)絡(luò)學(xué)到的東西，蘊(yùn)涵在連接權(quán)與閾值中 。
誤差逆向傳播算法：error BackPropagation BP算法
多指用于多層前饋神經(jīng)網(wǎng)絡(luò)
BP是一個(gè)迭代學(xué)習(xí)學(xué)習(xí)算法，在迭代的每一輪中采用廣義的
感知機(jī)學(xué)習(xí)規(guī)則對(duì)參數(shù)進(jìn)行更新估計(jì)，
BP算法基于梯度下降gradient descent 策略，以目標(biāo)的負(fù)梯度方向?qū)?/p>
參數(shù)進(jìn)行調(diào)整。
BP算法的目標(biāo)是最小化訓(xùn)練集D上的累計(jì)誤差
基于累計(jì)誤差最小化的更新規(guī)則，得到累積誤差逆?zhèn)鞑ニ惴ā?/p>
標(biāo)準(zhǔn)BP算法每次更新只針對(duì)單個(gè)樣例，參數(shù)更新的非常頻繁，
而且對(duì)不同樣例進(jìn)行更新的效果可能出現(xiàn)“抵消”現(xiàn)象，
為達(dá)到同樣的累計(jì)誤差極小點(diǎn)，標(biāo)準(zhǔn)BP需進(jìn)行更多次數(shù)的迭代。
累計(jì)BP算法直接針對(duì)累計(jì)誤差最小化，在讀取整個(gè)訓(xùn)練集一遍后才對(duì)參數(shù)進(jìn)行更新，
其參數(shù)更新頻率低，，但很多任務(wù)中，累計(jì)誤差下降到一定程度后，
進(jìn)一步下降會(huì)非常緩慢，標(biāo)準(zhǔn)BP會(huì)更快獲得較好的解，
尤其是訓(xùn)練集D非常大時(shí)更明顯。
只需一個(gè)包含足夠多神經(jīng)元的隱層，多層前饋網(wǎng)絡(luò)就能以任意精度逼近
任意復(fù)雜度的連續(xù)函數(shù)，通過(guò)試錯(cuò)法調(diào)整隱層神經(jīng)元的個(gè)數(shù)。
BP經(jīng)常過(guò)擬合。訓(xùn)練誤差持續(xù)降低，但測(cè)試誤差可能上升。
緩解BP網(wǎng)絡(luò)的過(guò)擬合，早停 early stopping 將數(shù)據(jù)分成訓(xùn)練集和驗(yàn)證集
訓(xùn)練集用來(lái)計(jì)算 梯度、更新連接權(quán)和閾值? 驗(yàn)證集用來(lái)估計(jì)誤差
若訓(xùn)練集誤差降低 但驗(yàn)證集誤差升高 停止訓(xùn)練，同時(shí)返回具有
最小驗(yàn)證集誤差的連接權(quán)和閾值
正則化，在誤差目標(biāo)函數(shù)中增加一個(gè)用于描述網(wǎng)絡(luò)復(fù)雜度的部分，
增加連接權(quán)與閾值平方和，訓(xùn)練過(guò)程將會(huì)偏好比較小的連接權(quán)和閾值，
使網(wǎng)絡(luò)輸出更加 光滑，對(duì)過(guò)擬合有所緩解。
引入正則化的神經(jīng)網(wǎng)絡(luò)與SVM十分相似。
