全書總評

• 書本印刷質(zhì)量：4 星。印刷清楚，排版合適，錯誤很少。
• 著作編寫質(zhì)量：4 星。自學(xué)機器學(xué)習(xí)的必備。
  • 優(yōu)點
    • 全書一直圍繞著統(tǒng)計學(xué)習(xí)中的有監(jiān)督學(xué)習(xí)描述，內(nèi)容不深，基本算法都有所介紹；
    • 內(nèi)容的組織是從抽象到具體的思維模式，比國外的教材易于理解；
    • 是自學(xué)統(tǒng)計學(xué)習(xí)和機器學(xué)習(xí)的推薦用書。
  • 缺點
    • 基礎(chǔ)部分講解缺少理論，學(xué)完后無法理解，不利用學(xué)以致用。例如：感知器的損失函數(shù)，應(yīng)該是統(tǒng)計學(xué)習(xí)的核心思想，那么損失函數(shù)在整個算法中的位置，以及如何選擇損失函數(shù)都需要說明清楚，才能夠指導(dǎo)后面各種其他機器學(xué)習(xí)方法的理解。
    • 使用的方法沒有導(dǎo)入的原因和出處，學(xué)習(xí)過程中會產(chǎn)生比較大的跳躍感，延續(xù)性不足。例如：隨機梯度下降法，只是說明用于神經(jīng)網(wǎng)絡(luò)的優(yōu)化需要用隨機梯度下降，而實際上隨機梯度下降是為了滿足在線學(xué)習(xí)的需要，如果是批量學(xué)習(xí)可以直接使用梯度學(xué)習(xí)算法實現(xiàn)。
  • 總結(jié)：瑕不掩瑜，建議結(jié)合 “西瓜書” [周志華，2018] 一起看。
• 筆記目的：記錄重點，方便回憶。

C01. 統(tǒng)計學(xué)習(xí)方法概論

• 這一章都是概念和結(jié)論，如果讀者能夠透過概念就明白里面實際操作的內(nèi)容，那就可以快速瀏覽此書，否則準(zhǔn)備紙和筆認真精讀方能收獲。
• 后面的各章內(nèi)容相對獨立，讀者既可以連續(xù)學(xué)習(xí)，也可以僅選擇自己感興趣的內(nèi)容。

統(tǒng)計學(xué)習(xí)

統(tǒng)計學(xué)習(xí)導(dǎo)言

• 統(tǒng)計學(xué)習(xí) (statistical learning): 計算機基于數(shù)據(jù)構(gòu)建概率統(tǒng)計模型，并運用模型對數(shù)據(jù)進行預(yù)測與分析的一門學(xué)科。
  • 因此統(tǒng)計學(xué)習(xí)也稱為統(tǒng)計機器學(xué)習(xí) (statistical machine learning).
• 統(tǒng)計學(xué)習(xí)的主要特點
  • 理論基礎(chǔ)
    • 數(shù)學(xué)基礎(chǔ)：微積分、線性代數(shù)、概率論、統(tǒng)計學(xué)、計算理論、最優(yōu)化理論
    • 其他基礎(chǔ)：信息論、計算機科學(xué)及應(yīng)用相關(guān)的科學(xué)等多個領(lǐng)域的交叉學(xué)科
    • 在發(fā)展中形成自己獨立的理論體系與方法論。
  • 應(yīng)用基礎(chǔ)：計算機及網(wǎng)絡(luò)；
  • 研究對象：數(shù)據(jù)，是數(shù)據(jù)驅(qū)動的學(xué)科；
  • 研究目的：對數(shù)據(jù)進行分類和預(yù)測；
  • 研究手段：通過統(tǒng)計學(xué)習(xí)方法構(gòu)建模型，并應(yīng)用模型進行分類和預(yù)測；

統(tǒng)計學(xué)習(xí)的對象

• 統(tǒng)計學(xué)習(xí)的對象是數(shù)據(jù) (data)
  • 從數(shù)據(jù)出發(fā)，提取數(shù)據(jù)的 “特征” ，抽象出數(shù)據(jù)的 “模型” ，發(fā)現(xiàn)數(shù)據(jù)中的 “知識” ，又回到對數(shù)據(jù)的 “分類” 與 “預(yù)測” 中。
  • 數(shù)據(jù)的基本假設(shè)：同類數(shù)據(jù)具有一定的統(tǒng)計規(guī)律性，所以可以用概率統(tǒng)計方法加以處理。
  • 數(shù)據(jù)分類有 “連續(xù)型” 和 “離散型” 兩種，本書主要關(guān)注的是 “離散型” 數(shù)據(jù)。

統(tǒng)計學(xué)習(xí)的目的

• 模型：學(xué)習(xí)什么樣的模型
• 策略：如何學(xué)習(xí)模型 → 使模型能夠?qū)?shù)據(jù)進行準(zhǔn)確地分類和預(yù)測
• 算法：如何提高模型的學(xué)習(xí)效率

統(tǒng)計學(xué)習(xí)的方法

• 統(tǒng)計學(xué)習(xí)的方法分類
  • 有監(jiān)督學(xué)習(xí) (supervised learning) （全書重點）
    • 從給定的、有限的、用于學(xué)習(xí)的訓(xùn)練數(shù)據(jù) (training data) 集合出發(fā)；
      • 假設(shè)數(shù)據(jù)是獨立同分布產(chǎn)生的；
    • 假設(shè)要學(xué)習(xí)的模型屬于某個函數(shù)的集合，稱為假設(shè)空間 (hypothesis space);
    • 基于某個評價標(biāo)準(zhǔn) (evaluation criterion), 從假設(shè)空間中選取一個最優(yōu)的模型
      • 使模型在給定的評價準(zhǔn)則下，對已知訓(xùn)練數(shù)據(jù)及未知測試數(shù)據(jù) (test data) 都有最優(yōu)的預(yù)測；
    • 最優(yōu)模型的選取都由算法實現(xiàn)。
  • 無監(jiān)督學(xué)習(xí) (unsupervised learning):
  • 半監(jiān)督學(xué)習(xí) (semi-supervised learning):
  • 強化學(xué)習(xí) (reinforcement learning):
• 統(tǒng)計學(xué)習(xí)方法的三個要素
  • 模型 (model): 模型的假設(shè)空間；
  • 策略 (strategy): 模型選擇的準(zhǔn)則；
  • 算法 (algorithm): 模型學(xué)習(xí)的算法。
• 實現(xiàn)統(tǒng)計學(xué)習(xí)方法的步驟
  • 得到一個有限的、用于訓(xùn)練的數(shù)據(jù)集合；
  • 模型的集合：確定包含所有可能的模型的假設(shè)空間；
  • 學(xué)習(xí)的策略：確定模型選擇的準(zhǔn)則；
  • 學(xué)習(xí)的算法：確定求解最優(yōu)模型的算法；
  • 通過學(xué)習(xí)的方式選擇出最優(yōu)模型；
  • 利用學(xué)習(xí)的最優(yōu)模型對新數(shù)據(jù)進行分類或預(yù)測。
• 統(tǒng)計學(xué)習(xí)中的有監(jiān)督學(xué)習(xí)根據(jù) “解決的問題” 主要包括
  • 分類問題：判別模型，處理離散數(shù)據(jù)
  • 預(yù)測問題：回歸模型，處理連續(xù)數(shù)據(jù)
  • 標(biāo)注問題：既是分類問題的推廣，又是預(yù)測問題的簡化。

統(tǒng)計學(xué)習(xí)的研究

• 統(tǒng)計學(xué)習(xí)方法 (statistical learning method): 開發(fā)新的學(xué)習(xí)方法；
• 統(tǒng)計學(xué)習(xí)理論 (statistical learning theory): 探求統(tǒng)計學(xué)習(xí)方法的有效性與效率，以及統(tǒng)計學(xué)習(xí)的基本理論問題；
• 統(tǒng)計學(xué)習(xí)應(yīng)用 (application of statistical learning): 將統(tǒng)計學(xué)習(xí)方法應(yīng)用到實際問題中去，解決實際問題。

統(tǒng)計學(xué)習(xí)的重要性

• 是處理海量數(shù)據(jù)的有效方法；
• 是計算機智能化的有效手段；
• 是計算機科學(xué)發(fā)展的重要組成。

監(jiān)督學(xué)習(xí)

• 監(jiān)督學(xué)習(xí)的任務(wù)：是學(xué)習(xí)一個模型，使模型能夠?qū)θ我饨o定的輸入，及其相應(yīng)的輸出做出一個好的預(yù)測

基本概念

• 輸入空間：輸入數(shù)據(jù)所有可能取值的集合；集合中元素的個數(shù)可以有限，也可以是整個空間；
• 輸出空間：輸出數(shù)據(jù)所有可能取值的集合；集合中元素的個數(shù)可以有限，也可以是整個空間；
• 假設(shè)空間：由輸入空間到輸出空間的映射的集合，即可供選擇的模型構(gòu)成的空間；
• 特征空間：所有特征向量存在的空間。
  • 每個具體的輸入是一個實例 (instance), 通常由特征向量 (feature vector) 表示。
• 統(tǒng)計學(xué)習(xí)中的有監(jiān)督學(xué)習(xí)根據(jù) “輸入變量” 和 “輸出變量” 的不同主要包括
  • 分類問題：輸出變量為有限個離散變量的預(yù)測問題；
  • 回歸問題：輸入變量與輸出變量均為連續(xù)變量；
  • 標(biāo)注問題：輸入變量與輸出變量均為變量序列的預(yù)測問題；
• 聯(lián)合概率分布：輸入變量與輸出變量遵循聯(lián)合分布；

問題的形式化描述

• 在學(xué)習(xí)過程中，學(xué)習(xí)系統(tǒng)（也就是學(xué)習(xí)算法）試圖通過給定的訓(xùn)練數(shù)據(jù)集合中的樣本帶來的信息來學(xué)習(xí)得到模型。

統(tǒng)計學(xué)習(xí)三個要素

• 統(tǒng)計學(xué)習(xí)方法 = 模型 + 策略 + 算法

模型

• 主要問題：學(xué)習(xí)什么樣的模型？
• 模型的假設(shè)空間：包含所有可能的條件概率分布或決策函數(shù)，即由一個參數(shù)向量決定的函數(shù)族，也稱為參數(shù)空間 (parameter space)。
• 模型分類
  • 非概率模型：由決策函數(shù)表示的模型；
  • 概率模型：由條件概率表示的模型；

策略

• 主要問題：按照什么樣的準(zhǔn)則，學(xué)習(xí)得到最優(yōu)的模型，或者從假設(shè)空間中選擇最優(yōu)的模型。
• 基本概念
  • 損失函數(shù) (loss function) 或代價函數(shù) (cost function): 度量模型一次預(yù)測的好壞；
  • 風(fēng)險函數(shù) (risk function) 或期望損失 (expected loss): 度量平均意義下模型預(yù)測的好壞。
  • 經(jīng)驗風(fēng)險 (empirical risk) 或經(jīng)驗損失 (empirical loss): 表示模型與訓(xùn)練數(shù)據(jù)的破例程度，即模型訓(xùn)練樣本集的平均損失，當(dāng)樣本容量趨于無窮時，經(jīng)驗風(fēng)險逼近期望風(fēng)險；
  • 結(jié)構(gòu)風(fēng)險 (structural risk): 表示模型先驗知識，例如：模型復(fù)雜度的正則化項 (regularizer) 或懲罰項 (penalty term)。
• 常用的損失函數(shù)
  • 0-1 損失函數(shù)
  • 平方損失函數(shù)
  • 絕對值損失函數(shù)
  • 對數(shù)損失函數(shù)或?qū)?shù)似然損失函數(shù)
• 學(xué)習(xí)目標(biāo)
  • 理想狀態(tài)：就是選擇期望風(fēng)險或期望損失最小的模型，希望可以提供無限的數(shù)據(jù)訓(xùn)練；
  • 現(xiàn)實狀態(tài)：就是選擇經(jīng)驗風(fēng)險或經(jīng)驗損失最小的模型，因為只能提供有限的數(shù)據(jù)訓(xùn)練；
• 經(jīng)驗風(fēng)險矯正：當(dāng)樣本容量過小時，容易出現(xiàn) “過擬合” 問題，所以需要對經(jīng)驗風(fēng)險進行矯正，經(jīng)驗風(fēng)險最小化 + 結(jié)構(gòu)風(fēng)險最小化
  • 經(jīng)驗風(fēng)險最小化 (empirical risk minimization, ERM): 極大似然估計
  • 結(jié)構(gòu)風(fēng)險最小化 (structural risk minimization, SRM): 最大后驗估計

算法

• 統(tǒng)計學(xué)習(xí)是基于訓(xùn)練數(shù)據(jù)集，根據(jù)學(xué)習(xí)策略，從假設(shè)空間中選擇最優(yōu)模型，最后需要考慮用什么樣的計算方法求解最優(yōu)模型。
• 算法 即計算方法。統(tǒng)計學(xué)習(xí)的算法就轉(zhuǎn)化為求解最優(yōu)化問題的算法。
  • 有顯式的解析解的最優(yōu)化問題；
  • 無顯式的解析解的最優(yōu)化問題，需要用數(shù)值計算的方法求解。
    • 如何保證找到全局最優(yōu)解；
    • 如何保證求解的過程高效。

模型的評估與選擇

• 1.4~1.7, 與模型選擇有關(guān)的問題。
• 1.8~1.10, 與模型應(yīng)用有關(guān)的問題。

模型評估

• 學(xué)習(xí)方法評估的標(biāo)準(zhǔn)
  • 基于損失函數(shù)的模型的訓(xùn)練誤差 (training error): 用來評估一個學(xué)習(xí)問題是否容易學(xué)習(xí)
  • 基于損失函數(shù)的模型的測試誤差 (test error): 用來評估一個模型是否具備更有效的預(yù)測
• 泛化能力 (generalization ability): 學(xué)習(xí)方法對未知數(shù)據(jù)的預(yù)測能力

模型選擇

• 過擬合 (over-fitting): 學(xué)習(xí)時選擇的模型所包含的參數(shù)過多，以至于模型對已知數(shù)據(jù)預(yù)測較好，未知數(shù)據(jù)預(yù)測較差的問題
• 模型選擇的常用方法
  • 正則化
  • 交叉驗證

正則化與交叉驗證

正則化

• 正則化 (regularization): 結(jié)構(gòu)風(fēng)險最小化策略的實現(xiàn)，是在經(jīng)驗風(fēng)險上加一個正則化項或懲罰項。
  • 正則化項一般是模型復(fù)雜度的單調(diào)遞增函數(shù)。
    • 復(fù)雜度定義可以參考 Kolmogorov 復(fù)雜性理論 (complexity theory) [Haykin, 2011] P48
  • Occam 剃刀原理：應(yīng)用于模型選擇時符合正則化的想法，即所有能夠解釋數(shù)據(jù)的模型中，復(fù)雜度越小越好。
  • Bayes 估計：正則化項對應(yīng)于模型的先驗概率。數(shù)據(jù)較少時先驗概率就可以抑制數(shù)據(jù)中噪聲的干擾，防止出現(xiàn)過擬合問題。數(shù)據(jù)很多時，先驗概率就讓位于數(shù)據(jù)對模型的解釋。
  • 正則化是優(yōu)化學(xué)習(xí)算法，調(diào)整目標(biāo)函數(shù)，增加先驗知識的重要手段，是機器學(xué)習(xí)的核心之一。
    • 簡單了解：[周志華，2018] P133
    • 深入理解：[Haykin, 2011] C07

交叉驗證

• 交叉驗證 (cross validation)
  • 在數(shù)據(jù)充足時，隨機地將數(shù)據(jù)切分成三個部分：訓(xùn)練集、驗證集和測試集。
    • 選擇對驗證集有最小預(yù)測誤差的模型。
  • 訓(xùn)練集 (training set): 用來訓(xùn)練模型；
  • 驗證集 (validation set): 用來選擇模型；
  • 測試集 (test set): 用來評估模型。
• 交叉驗證的常用方法
  • 簡單交叉驗證：隨機地將數(shù)據(jù)分成兩個部分，70% 的數(shù)據(jù)為訓(xùn)練集，30% 的數(shù)據(jù)為測試集，選擇測試誤差最小的模型；
  • S 折交叉驗證
    • 隨機地將數(shù)據(jù)分成 S 個互不相交的大小相同的部分
    • 然后利用 S-1 個部分的數(shù)據(jù)訓(xùn)練，1 個子集測試模型，
    • 再將這一個過程對所有可能的選擇重復(fù)進行，
    • 最后選擇 S 次評測中平均測試誤差最小的模型。
  • 留一交叉驗證：當(dāng) S=N 時采用的 S 折交叉驗證，適用于數(shù)據(jù)極度缺乏的情況下。(N 為給定數(shù)據(jù)集的容量）

泛化能力

泛化誤差

• 泛化能力 (generalization ability): 是指學(xué)習(xí)方法學(xué)習(xí)到的模型對未知數(shù)據(jù)的預(yù)測能力
• 泛化誤差 (generalization error): 是指學(xué)到的模型對未知數(shù)據(jù)預(yù)測產(chǎn)生的誤差，反映了學(xué)習(xí)方法的泛化能力。

泛化誤差的上界

• 泛化誤差的上界 (generalization error bound): 泛化誤差的概率上界，通過比較兩種學(xué)習(xí)方法的泛化誤差概率上界來確定優(yōu)劣
• 泛化誤差上界的性質(zhì)
  • 是樣本容量的函數(shù)，當(dāng)樣本容量增加時，泛化上界趨向于 0;
  • 是假設(shè)空間的函數(shù)，當(dāng)假設(shè)空間容量增加時，泛化誤差上界就會變大，表示模型就更加難學(xué)。
• 泛化誤差上界定理及證明（建議跳過）

生成模型與判別模型

• 生成模型 (generative model): 模型表示了給定輸入 X 產(chǎn)生輸出 Y 的生成關(guān)系。
  • 特點
    • 還原出聯(lián)合概率分布；
    • 學(xué)習(xí)收斂速度快；
    • 樣本容量增加時，能夠更好地逼近真實模型；
    • 存在隱變量時，仍然可以使用。
  • 應(yīng)用：樸素 Bayes 方法和隱馬爾可夫模型 (Hidden Markov Model, HMM);
  • 注：生成模型是比較難理解的概念，HMM 是理解生成模型比較好的途徑，如果對 HMM 感興趣可以參考
    • 簡單了解：[周志華，2018] P320
    • 深入理解：[Rabiner, 1989]
• 判別模型 (discriminative model): 由數(shù)據(jù)直接學(xué)習(xí)決策函數(shù)或者條件概率分布作為預(yù)測的模型
  • 特點
    • 直接學(xué)習(xí)得到條件概率分布或者決策函數(shù)；
    • 直接面對預(yù)測，學(xué)習(xí)的準(zhǔn)確率更高；
    • 基于參數(shù)是直接學(xué)習(xí)得到的，因此可以對數(shù)據(jù)進行各種程度上的抽象、定義和使用特征，簡化學(xué)習(xí)問題。
  • 應(yīng)用：k 近鄰法、感知機、決策樹、Logistic 回歸模型、最大熵模型、支持向量機、提升方法和條件隨機場等

分類問題

• 分類器 (classifier): 監(jiān)督學(xué)習(xí)從數(shù)據(jù)中學(xué)習(xí)得到的分類模型或分類決策函數(shù)。
• 分類 (classification): 利用分類器對新輸入的數(shù)據(jù)進行輸出的預(yù)測。
• 解決分類問題的兩個過程
  • 學(xué)習(xí)過程：根據(jù)已知的訓(xùn)練數(shù)據(jù)集利用有效的“學(xué)習(xí)方法”得到一個分類器；
  • 分類過程：利用學(xué)習(xí)得到的分類器對新輸入的實例進行分類。
• 評價分類器性能的指標(biāo)：分類準(zhǔn)確率 (accuracy), 即對于給定的測試數(shù)據(jù)集，分類器正確分類的樣本數(shù)與總樣本數(shù)之比。
  • 二類分類問題常用的評價指標(biāo)：精確率 (precision) 與召回率 (recall)。
• 解決分類問題的常用方法：k 近鄰法、感知機、樸素 Bayes 法，決策樹、決策列表、Logistc 回歸模型、支持向量機、提升方法等

標(biāo)注問題

• 標(biāo)注問題：是分類問題的推廣，也是更復(fù)雜的結(jié)構(gòu)預(yù)測問題的簡單形式。
  • 輸入是一個觀測序列；
  • 輸出是一個標(biāo)記序列或狀態(tài)序列。
  • 目標(biāo)是通過學(xué)習(xí)得到能夠?qū)τ^測序列給出標(biāo)記序列作為預(yù)測的模型。
• 解決標(biāo)注問題的兩個過程：學(xué)習(xí)過程 和 標(biāo)注過程
• 評價標(biāo)注問題的指標(biāo)：準(zhǔn)確率、精確率和召回率。
• 解決標(biāo)注問題的常用方法：隱 Markov 模型和條件隨機場。

回歸問題

• 回歸 (regression): 用于預(yù)測輸入變量（自變量）和輸出變量（因變量）之間的關(guān)系。
• 回歸模型：表示從輸入變量到輸出變量之間的映射關(guān)系的函數(shù)。
  • 等價于：函數(shù)擬合。
• 解決回歸問題的兩個過程：學(xué)習(xí)過程和預(yù)測過程。
• 回歸問題的分類
  • 按輸入變量的個數(shù)：一元回歸和多元回歸；
  • 按輸入變量和輸出變量之間的關(guān)系：線性回歸和非線性回歸。
• 回歸學(xué)習(xí)最常用的損失函數(shù)：平方損失函數(shù)，求解平方損失函數(shù)可以用最小二乘法。

C02. 感知機

• 模型
  • 感知機，是根據(jù)輸入實例的特征向量對其進行二類分類的線性分類模型，屬于判別模型；
  • 模型參數(shù)包括：權(quán)值或權(quán)值向量，偏置。
  • 模型對應(yīng)于輸入空間（特征空間）中的分離超平面；
• 策略
  • 假設(shè)：感知機學(xué)習(xí)的訓(xùn)練數(shù)據(jù)集是線性可分的；
  • 目標(biāo)：求得一個能夠?qū)⒂?xùn)練集正實例點和負實例點完全正確分開的分離超平面；
  • 策略：即定義（經(jīng)驗）損失函數(shù)，并將損失函數(shù)極小化；
    • 損失函數(shù)定義為：誤分類點的總數(shù)，不易優(yōu)化；
    • 損失函數(shù)定義為：誤分類到分離超平面的總距離；
• 算法
  • 感知機學(xué)習(xí)算法是基于誤差 - 修正的學(xué)習(xí)思想，是由誤分類驅(qū)動的；
  • 學(xué)習(xí)算法的優(yōu)化方法
    • 批量學(xué)習(xí)可以基于進行優(yōu)化
      • 一階：最速下降法或梯度下降法；
      • 二階：牛頓法、共軛梯度法等等
    • 在線學(xué)習(xí)：基于隨機梯度下降法的對損失函數(shù)進行最優(yōu)化 [Goodfellow, 2017] P95, P180
      • 原始形式：算法簡單且易于實現(xiàn)。先任意選取一個超平面，然后隨機選擇一個誤分類點使其用梯度下降法極小化目標(biāo)函數(shù)
        • 例 2.1（比較簡單，可以了解）
        • 定理 2.1（過于簡略，建議跳過）
      • 對偶形式 （沒看出與原始形式有何區(qū)別，也沒從別的書上看到過這種說明方式，建議跳過）
  • 當(dāng)訓(xùn)練數(shù)據(jù)集線性可分時，感知機學(xué)習(xí)算法是收斂的，且有無窮多個解。
• 學(xué)習(xí)總結(jié)
  • 感知機是神經(jīng)網(wǎng)絡(luò)的基礎(chǔ)，本章只有單個神經(jīng)元模型，深入學(xué)習(xí)參考 [Haykin, 2011]
  • 神經(jīng)網(wǎng)絡(luò)是深度學(xué)習(xí)的基礎(chǔ)，深度學(xué)習(xí)參考 [Goodfellow, 2017]
  • 距離度量是幾何的概念，理論可參考 [Duda, 2003] P154
  • 學(xué)習(xí)算法的優(yōu)化是最優(yōu)化理論，基本優(yōu)化方法可參考 [Hyvarinen, 2007] P42

C03. k 近鄰法

• k 近鄰法 (k-nearest neighbor, k-NN) 是一個基本且簡單的方法，用于分類與回歸。
  • 輸入為實例的特征向量，對應(yīng)于特征空間的點；
  • 輸出為實例的類別，可以取多個類。
• 基本思想
  • 假設(shè)給定一個訓(xùn)練數(shù)據(jù)集，其中的實例類別已經(jīng)確定；
  • 對新輸入的實例分類時，根據(jù)其 k 個最近鄰的訓(xùn)練實例的類別，通過多數(shù)表決等方式進行預(yù)測。
  • 不具有顯式的學(xué)習(xí)過程。
  • 實際上利用訓(xùn)練數(shù)據(jù)集對特征向量空間進行切分，并作為其分類的 “模型”。
• k 近鄰的模型
  • 對應(yīng)于基于訓(xùn)練數(shù)據(jù)集對特征空間的一個劃分。
  • 當(dāng)訓(xùn)練集、距離度量、k 值及分類決策規(guī)則確定后，輸入實例所屬類別也唯一確定。
• k 近鄰法的三個要素
  • 學(xué)習(xí)準(zhǔn)則：距離度量，常用歐氏距離；（距離定義）[Duda, 2003]
  • k 值的選擇：反映了近似誤差與估計誤差之間的權(quán)衡。
    • k 值越大時，近似誤差會增大，估計誤差會減小，模型也越簡單；
    • k 值越小時，近似誤差會減少，估計誤差會增大，模型也越復(fù)雜。
    • 可以用交叉驗證的方式選擇最優(yōu) k 值。
  • 分類決策規(guī)則：多數(shù)表決規(guī)則 (marjority voting rule), 等價于 經(jīng)驗風(fēng)險最小化。
• k 近鄰法的實現(xiàn)基于 kd 樹。（了解即可，實際應(yīng)用中大多使用的是已經(jīng)成熟的軟件包）
  • kd 樹是一種便于對 k 維空間中的數(shù)據(jù)進行快速檢索的數(shù)據(jù)結(jié)構(gòu)；
  • kd 樹是二叉樹，表示對 k 維空間的一個劃分；
  • kd 樹的每個圣戰(zhàn)對應(yīng)于 k 維空間劃分中的一個超矩形區(qū)域；
  • 利用 kd 樹可以省去對大部分數(shù)據(jù)點的搜索，從而減少搜索的計算量。
• 學(xué)習(xí)總結(jié)
  • 了解即可，因為面對高維問題效果很差，需要考慮降維操作。[周志華，2018] P225

C04. 樸素 Bayes 法

• 樸素 (naive) Bayes 法：是基于 Bayes 定理與所有特征都遵循條件獨立性假設(shè)的分類方法。
  • 樸素 Bayes 法是 Bayes 分類法的一種，遵循 Bayes 定理建模。[Mitchell, 2003] P112
  • 樸素 Bayes 法基于的條件獨立性假設(shè)是說用于分類的特征在類別確定的條件下都是條件獨立的。簡化了計算復(fù)雜度，犧牲了分類準(zhǔn)確率。
  • 樸素 Bayes 法是生成學(xué)習(xí)方法。
    • 先驗概率分布；
    • 條件概率分布；
    • 后驗概率分布。后驗概率最大化準(zhǔn)則等價于期望風(fēng)險最小化準(zhǔn)則。
    • 目標(biāo)：由訓(xùn)練數(shù)據(jù)學(xué)習(xí)聯(lián)合概率分布；
  • 樸素 Bayes 方法的概率參數(shù)估計方法：
    • 極大似然估計 : 概率估計常用的方法；
    • Bayes 估計 : 重點在于了解與極大似然估計的差別，才可以正確使用。
• 學(xué)習(xí)總結(jié)
  • 雖然不需要自己估計參數(shù)，但是對估計的理解很重要，書中的描述過于簡單，具體內(nèi)容請參考 [Duda, 2003] P67
  • 對于概念上的理解還可以參考 [周志華，2018] C07

C05. 決策樹 (decision tree)

• 決策樹模型
  • 決策樹是一種基本方法，用于分類與回歸。
    • 本章主要討論的是分類決策樹。
  • 分類決策樹模型
    • 定義：是基于特征對實例進行分類的樹形結(jié)構(gòu)。
    • 模型的組成結(jié)構(gòu)
      • 結(jié)點 (node)
        • 內(nèi)部結(jié)點 (internal node)
        • 葉結(jié)點 (leaf node)
      • 有向邊 (directed edge)
    • 分類決策樹可以轉(zhuǎn)換成一個 if-then 規(guī)則的集合；
      • 決策樹的根結(jié)點到葉結(jié)點的每一條路徑構(gòu)建一條規(guī)則；
      • 路徑上內(nèi)部結(jié)點的特征對應(yīng)著規(guī)則的條件，而葉結(jié)點的類對應(yīng)著規(guī)則的結(jié)論。
      • 重要的性質(zhì)：互斥并且完備，即全覆蓋。
        • 覆蓋是指實例的特征與路徑上的特征一致或?qū)嵗凉M足規(guī)則的條件。
    • 也可以看作是定義在特征空間與類空間上的條件概率分布。
      • 這個條件概率分布定義在特征空間的一個劃分上，
      • 將特征空間劃分為互不相交的單元或區(qū)域，
      • 并在每個單元定義一個類的概率分布就構(gòu)成了一個條件概率分布。
      • 決策樹分類時，將結(jié)點的實例分到條件概率大的類中。
    • 主要優(yōu)點：可讀性強，分類速度快。
• 決策樹學(xué)習(xí)
  • 學(xué)習(xí)目的
    • 根據(jù)給定的訓(xùn)練數(shù)據(jù)集，構(gòu)建一個與訓(xùn)練數(shù)據(jù)擬合很好，并且復(fù)雜度小的決策樹，使之能夠?qū)嵗M行正確的分類。
    • 決策樹與訓(xùn)練數(shù)據(jù)的矛盾較小，同時還具有較好的泛化能力。
    • 也可以看作由訓(xùn)練數(shù)據(jù)集估計條件概率模型
      • 模型對訓(xùn)練數(shù)據(jù)擬合的效果很好；
      • 模型對未知數(shù)據(jù)有很好的預(yù)測。
    • 從所有可能的決策樹中選取最優(yōu)決策樹是 NP 完全問題；
      • 現(xiàn)實中采用啟發(fā)式方法學(xué)習(xí)次優(yōu)的決策樹。
  • 學(xué)習(xí)準(zhǔn)則：損失函數(shù)最小化。
    • 損失函數(shù)是一種正則化的極大似然函數(shù)
  • 學(xué)習(xí)算法
    • 遞歸地選擇最優(yōu)特征，并根據(jù)該特征對訓(xùn)練數(shù)據(jù)進行分割，使之對各個數(shù)據(jù)集有一個最好的分類的過程。
• 決策樹的學(xué)習(xí)算法包括 3 個部分
  • 特征選擇
    • 特征選擇的目的在于選取對訓(xùn)練數(shù)據(jù)能夠分類的特征，提高決策樹學(xué)習(xí)的效率；
    • 特征選擇的關(guān)鍵是其準(zhǔn)則
      • 樣本集合 D 對特征 A 的信息增益 最大
        • 信息增益定義為集合 D 的經(jīng)驗熵與特征 A 在給定條件下 D 的經(jīng)驗條件熵之差。
          • 熵：表示隨機變量不確定性的度量。也稱為經(jīng)驗熵。
          • 條件熵：定義為 X 給定條件下 Y 的條件概率分布的熵對 X 的數(shù)學(xué)期望。也稱為經(jīng)驗條件熵。
        • 信息增益表示得知特征 X 的信息而使得類 Y 的信息的不確定性減少的程度。
        • 信息增益等價于訓(xùn)練數(shù)據(jù)集中類與特征的互信息。
        • 信息增益依賴于特征，信息增益大的特征具有更強的分類能力。
      • 樣本集合 D 對特征 A 的信息增益比 最大
        • 為了避免信息增益對取值較多的特征的偏重，使用信息增益比來代替；
        • 信息增益比：特征 A 對訓(xùn)練數(shù)據(jù)集 D 的信息增益與訓(xùn)練數(shù)據(jù)集 D 關(guān)于特征 A 的值的熵之比。
      • 樣本集合 D 的基尼指數(shù) 最小
  • 樹的生成
    • 計算指標(biāo)，再根據(jù)準(zhǔn)則選取最優(yōu)切分點，從根結(jié)點開發(fā)，遞歸地產(chǎn)生決策樹。
    • 通過不斷地選擇局部最優(yōu)的特征，得到可能是全局次優(yōu)的結(jié)果。
  • 樹的剪枝：將已經(jīng)生成的樹進行簡化的過程。
    • 目的：由于生成的決策樹存在過擬合問題，需要對它進行剪枝，以簡化學(xué)到的決策樹。
    • 剪枝的準(zhǔn)則：極小化決策樹整體的損失函數(shù)或代價函數(shù)，等價于正則化的極大似然估計。
    • 剪枝的分類
      • 預(yù)剪枝：也叫分支停止準(zhǔn)則。在決策樹生成過程中，對每個結(jié)點在劃分前先進行估計，若當(dāng)前結(jié)點的劃分不能帶來決策樹泛化性能提升，則停止劃分并將當(dāng)前結(jié)點標(biāo)記為葉結(jié)點；
      • 后剪枝：先從訓(xùn)練集生成一棵完整的決策樹，然后自底向上地對非葉結(jié)點進行考察，若將該結(jié)點對應(yīng)的子樹替換為葉結(jié)點能帶來決策樹泛化性能提升，則將該子樹替換為葉結(jié)點。
  • 常用的學(xué)習(xí)算法
    • ID3: 在決策樹的各個結(jié)點上應(yīng)用信息增益準(zhǔn)則選擇特征，遞歸地構(gòu)建決策樹。相當(dāng)于用極大似然法進行概率模型的選擇。
    • C4.5: 在決策樹的各個結(jié)點上應(yīng)用信息增益比準(zhǔn)則選擇特征，遞歸地構(gòu)建決策樹。
    • CART: 既可用于分類，也可用于回歸。
      • 等價于遞歸地二分每個特征，將輸入空間即特征空間劃分為有限個單元，并在這些單元上確定預(yù)測的概率分布，也就是在輸入給定的條件下輸出的條件概率分布。
      • CART 算法的兩個過程
        • 決策樹生成：基于訓(xùn)練數(shù)據(jù)集生成決策樹，要盡量大；
          • 回歸樹生成
            • 用平方誤差最小準(zhǔn)則求解每個單元上的最優(yōu)輸出值。
            • 回歸樹通常稱為最小二乘回歸樹。
          • 分類樹生成
            • 用基尼指數(shù)選擇最優(yōu)特征，并決定該特征的最優(yōu)二值切分點。
            • 算法停止計算的條件
              • 結(jié)點中的樣本個數(shù)小于預(yù)定閾值；
              • 樣本集的基尼小于預(yù)定閾值；
        • 決策樹剪枝
          • 用驗證數(shù)據(jù)集對已經(jīng)生成的樹進行剪枝，剪枝的標(biāo)準(zhǔn)為損失函數(shù)最小，基于標(biāo)準(zhǔn)選擇最優(yōu)子樹。
          • 可以通過交叉驗證法對用于驗證的獨立數(shù)據(jù)集上的子樹序列進行測試，從中選擇最優(yōu)子樹。
        • [Duda, 2003] P320, CART 作為通用的框架，定義了 6 個問題
• 決策樹的預(yù)測
  • 對新的數(shù)據(jù)，利用決策樹模型進行分類。
• 學(xué)習(xí)總結(jié)
  • 算法 (5.1, 5.2, 5.6) + 例題 ( 5.1, 5.2, 5.3, 5.4 ) 通過算法和例題可以增強理解；
  • 損失函數(shù)的定義可以進一步參考 “不純度” 指標(biāo) [Duda, 2003] P320, 或 “純度” 指標(biāo) [周志華，2018] P75
    • “不純度” 指標(biāo)是求極小值，可以跟梯度下降法等最優(yōu)化理論結(jié)合。

C06. Logistic 回歸與最大熵模型

• 模型
  • Logistic 回歸模型，也稱為對數(shù)幾率回歸模型，輸入是的線性函數(shù)，輸出的是對數(shù)幾率模型
    • 基于 Logistic 分布建立的，表示條件概率的分類模型
      • Logistic 分布是 Sigmoid 函數(shù)，定義 6.1
    • 對數(shù)幾率 (log odds) 或 logit 函數(shù)
      • 一個事件的幾率 (odds) 是指該事件發(fā)生的概率與該事件不發(fā)生的概率的比值。
    • 二項 Logistic 回歸模型是二類分類模型，定義 6.2
    • 多項 Logistic 回歸模型是多類分類模型
    • 模型參數(shù)估計
      • 極大似然估計法
  • 最大熵模型
    • 基于最大熵原理推導(dǎo)的，表示條件概率分布的分類模型，可以用于二類或多類分類。
      • 最大熵原理認為，在所有可能的概率模型（分布）的集合中，熵最大的模型是最好的模型。
      • 準(zhǔn)則：最大熵原理是概率模型學(xué)習(xí)或估計的一個準(zhǔn)則。
    • 最大熵模型的學(xué)習(xí)
      • 最大熵模型的學(xué)習(xí)過程就是求解最大熵模型的過程
      • 最大熵模型的學(xué)習(xí)可以形式化為有約束的最優(yōu)化問題（對偶問題）
        • 拉格朗日乘子參考附錄 C
    • 例 6.1, 6.2 方便理解最大熵模型的算法原理。
• 算法
  • 學(xué)習(xí)采用極大似然估計或者正則化極大似然估計
    • 形式化為無約束最優(yōu)化問題
  • 求解無約束最優(yōu)化問題的算法
    • 迭代尺度法
    • 梯度下降法
    • 擬牛頓法
• 學(xué)習(xí)總結(jié)
  • Logistic 模型與最大熵模型都屬于對數(shù)線性模型。[周志華，2018] C03
  • 極大似然估計：書里寫的比較簡單，沒有原理性的說明，推薦（[周志華，2018] P149, [Duda, 2003] P67）
  • 模型學(xué)習(xí)的最優(yōu)化算法：書里寫的不太好理解。各種機器學(xué)習(xí)和模式識別的書里面都有介紹，推薦（[周志華，2018] P403, [Hagan, 2006] C09）

C07. 支持向量機

• 支持向量機（Support Vector Machine， SVM）是一種二類分類模型。
  • 基本模型是定義在特征空間上的間隔最大的線性分類器
  • 基本概念
    • 支持向量決定了最優(yōu)分享超平面
      • 最終判別時，只需要很少的“重要”訓(xùn)練樣本，大幅減少計算量。
    • 間隔（看懂?dāng)?shù)學(xué)公式就可以理解間隔，判別在數(shù)據(jù)的維度上又增加了一個維度）
  • 與其他模型的比較
    • 與感知機的區(qū)別：間隔最大化產(chǎn)生最優(yōu)超平面；
    • 與線性模型的區(qū)別：使用核技巧成為非線性分類器。
  • 分類
    • 線性可分支持向量機，硬間隔支持向量機。
    • 線性支持向量機，軟間隔支持向量機，是最基本的支持向量機。
    • 非線性支持向量機
  • 學(xué)習(xí)
    • 學(xué)習(xí)在特征空間進行的
    • 學(xué)習(xí)策略是間隔最大化
• 線性可分支持向量機 (linear support vector machine in linearly separable case)
  • 條件：訓(xùn)練數(shù)據(jù)線性可分；
  • 學(xué)習(xí)策略：硬間隔最大化
    • 求解能夠正確劃分訓(xùn)練數(shù)據(jù)集并且?guī)缀伍g隔最大的分離超平面
    • 對訓(xùn)練數(shù)據(jù)集找到幾何間隔最大的超平面意味著以充分大的確信度對訓(xùn)練數(shù)據(jù)進行分類
    • 這樣的超平面對未知原新實例有很好的分類預(yù)測能力
  • 解的特征
    • 最優(yōu)解存在且唯一；（唯一性證明，建議跳過）
    • 支持向量由位于間隔邊界上的實例點組成；
• 線性支持向量機 (linear support vector machine)
  • 條件
    • 訓(xùn)練數(shù)據(jù)近似線性可分；
    • 訓(xùn)練數(shù)據(jù)中存在一些特異點 (outlier)
  • 學(xué)習(xí)策略：軟間隔最大化
    • 懲罰參數(shù) C * 替代損失函數(shù) f，表示誤判的代價；
      • hinge 損失（合頁損失函數(shù)）：保持了稀疏性
      • 指數(shù)損失
      • 對率損失：相似于對率回歸模型
    • 目標(biāo)是使間隔盡量大，誤分類點盡量少。
  • 解的特征
    • 權(quán)值唯一，偏置不唯一；
    • 支持向量由位于間隔邊界上的實例點、間隔邊界與分離超平面之間的實例點、分離超平面誤分一側(cè)的實例點組成；
    • 最優(yōu)分享超平面由支持向量完全決定。
• 非線性支持向量機 (non-linear support vector machine)
  • 基本概念
    • 線性空間：滿足線性性質(zhì)的空間
    • 距離：是一種度量
      • 距離的集合 ? 度量空間 + 線性結(jié)構(gòu) ? 線性度量空間
    • 范數(shù)：表示某點到空間零點的距離
      • 范數(shù)的集合 ? 賦范空間 + 線性結(jié)構(gòu) ? 線性賦范空間
    • 內(nèi)積空間：添加了內(nèi)積運算的線性賦范空間
      • 線性賦范空間 + 內(nèi)積運算 ? 內(nèi)積空間
    • 歐氏空間：有限維的內(nèi)積空間
    • 希爾伯特空間：內(nèi)積空間滿足完備性，即擴展到無限維
      • 內(nèi)積空間 + 完備性 ? 希爾伯特空間
    • 巴拿赫空間：賦范空間滿足完備性
      • 賦范空間 + 完備性 ? 巴拿赫空間
  • 條件：
    • 訓(xùn)練數(shù)據(jù)非線性可分；
    • 通過非線性變換（核函數(shù)）將輸入空間（歐氏空間或離散集合）轉(zhuǎn)化為某個高維特征空間（希爾伯特空間）中的線性可分；
    • 在高維特征空間中學(xué)習(xí)線性支持向量機。
  • 學(xué)習(xí)策略：核技巧 + 軟間隔最大化
• 最大間隔法
  • 間隔概念
    • 函數(shù)間隔：表示分類的正確性及確信度
    • 幾何間隔：規(guī)范化后的函數(shù)間隔，實例點到超平面的帶符號的距離
  • 分類
    • 硬間隔最大化 (hard margin maximization)
    • 軟間隔最大化 (soft margin maximization)
  • 間隔最大化的形式化
    • 求解凸二次規(guī)劃問題
      • 最優(yōu)化算法
    • 正則化的合頁損失函數(shù)的最小化問題
  • 求解過程
    • 原始最優(yōu)化問題應(yīng)用拉格朗日對偶性；
    • 通過求解對偶問題得到原始問題的最優(yōu)解。
    • 中間也可以根據(jù)需要自然引入核函數(shù)。
• 核技巧 (kernel method) 通用的機器學(xué)習(xí)方法
  • 應(yīng)用條件
    • 非線性可分訓(xùn)練數(shù)據(jù)可以變換到線性可分特征空間；
    • 目標(biāo)函數(shù)中的內(nèi)積可以使用非線性函數(shù)的內(nèi)積替換；
    • 非線性函數(shù)的內(nèi)積可以使用核函數(shù)替換；
    • 核函數(shù)使非線性問題可解。
  • 常用的核函數(shù)
    • 線性核：對應(yīng)于線性可分問題
    • 多項式核函數(shù)
    • 高斯核函數(shù)
    • Sigmoid 核函數(shù)
    • 函數(shù)組合得到的核函數(shù)
      • 兩個核函數(shù)的線性組合仍然是核函數(shù)，k1(x,z) 和 k2(x,z) 是核函數(shù)，c1 和 c2 是任意正數(shù)，則 k(x,z)=c1k1(x,z)+c2k2(x,z) 也是核函數(shù)。
      • 兩個核函數(shù)的直積仍然是核函數(shù)，k1(x,z) 和 k2(x,z) 是核函數(shù)，則 k(x,z)=k1(x,z)k2(x,z) 也是核函數(shù)。
      • k1(x,z) 是核函數(shù)，g(z) 是任意函數(shù)，則 k(x,z)=g(z)k1(x,z)g(z) 也是核函數(shù)。
• SMO 算法
  • 支持向量機學(xué)習(xí)的啟發(fā)式快速算法
  • 流程
    • 將原二次規(guī)劃問題分解為只有兩個變量的二次規(guī)劃子問題；
      • 第一個變量是違反 KKT 條件最嚴重的變量；
      • 第二個變量是使目標(biāo)函數(shù)增長最快的變量；
      • 目標(biāo)是使兩個變量所對應(yīng)樣本之間的間隔最大。
    • 對子問題進行解析分解；
    • 直到所有變量滿足 KKT 條件為止。
• 學(xué)習(xí)總結(jié)
  • 支持向量機與神經(jīng)網(wǎng)絡(luò)是兩大重要的機器學(xué)習(xí)算法；
  • 結(jié)合周老師的書一起看，對于理解支持向量機會有較大幫助。[周志華，2018] C06
  • 深入了解支持向量機的理論分析。[Haykin, 2011] C06

C08. 提升方法（集成學(xué)習(xí)）

提升方法是一種統(tǒng)計學(xué)習(xí)方法，也是一種提升模型學(xué)習(xí)能力和泛化能力的方法，還是一種組合學(xué)習(xí)（集成學(xué)習(xí)）的方法，是統(tǒng)計學(xué)習(xí)中最有效的方法之一。

• 為什么要將各種學(xué)習(xí)方法組合起來？
  • 強可學(xué)習(xí)方法與弱可學(xué)習(xí)方法的等價性；
  • 將各種弱可學(xué)習(xí)方法組合起來就可以提升 (boost) 為強可學(xué)習(xí)方法
• 如何將各種學(xué)習(xí)方法組合起來？
  • AdaBoost 算法
    • 是一種通用的組合算法，可以將各種分類算法進行組合。
  • 提升樹
    • 以分類樹或回歸樹為基本分類器的提升方法（組合算法）
    • 提升樹是統(tǒng)計學(xué)習(xí)中性能最好的方法之一
  • Bagging 算法（本章無介紹，了解請參考[周志華，2018] C8.3）
    • 隨機森林
• AdaBoost 算法
  • 模型：加法模型
    • 如何改變訓(xùn)練數(shù)據(jù)的權(quán)值和概率分布：采用 “分而治之” 的方法。提高那些被前一輪弱分類器錯誤分類的樣本的權(quán)值，從而保證后一輪的弱分類器在學(xué)習(xí)過程中能夠更多關(guān)注它們。
    • 如何將弱分類器組合成一個強分類器：采用 “加權(quán)多數(shù)表決” 的方法。加大分類誤差率小的弱分類器的權(quán)值，從而保證它們在表決中起較大的作用。
  • 策略：指數(shù)損失函數(shù)極小化，即經(jīng)驗風(fēng)險極小化。
  • 算法：前向分步算法來優(yōu)化分步優(yōu)化指數(shù)損失函數(shù)的極小化問題。
  • 算法的訓(xùn)練誤差分析
    • AdaBoost 能夠在學(xué)習(xí)過程中不斷減少訓(xùn)練誤差，即減少訓(xùn)練數(shù)據(jù)集上的分類誤差率。
      • AdaBoost 的訓(xùn)練誤差是以指數(shù)速率下降的。定理與證明建議跳過
  • 算法的優(yōu)化過程分析
    • 因為學(xué)習(xí)的是加法模型，所以能夠從前向后，每一步只學(xué)習(xí)一個基函數(shù)及基系數(shù)，逐步逼近優(yōu)化目標(biāo)函數(shù)，簡化優(yōu)化的復(fù)雜度。
    • 前向分步算法與 AdaBoost 的關(guān)系：定理與證明建議跳過。
• 提升樹模型
  • 模型：加法模型，以決策樹為基函數(shù)
  • 策略：損失函數(shù)
    • 分類問題：指數(shù)損失函數(shù)
    • 回歸問題：平方誤差函數(shù)
    • 一般決策問題：一般損失函數(shù)
  • 算法：前向分步算法
    • 梯度提升算法（GBDT）：解決離散數(shù)據(jù)的優(yōu)化問題，原理參考、[Friedman, 2001]
• 學(xué)習(xí)總結(jié)
  • 學(xué)習(xí)基礎(chǔ)
    • 熟悉重要的分類算法：神經(jīng)網(wǎng)絡(luò)和支持向量機
    • 熟悉常用的分類算法：k 近鄰法和決策樹
  • 學(xué)習(xí)目標(biāo)
    • 組合各種分類算法，從而產(chǎn)生質(zhì)量更好的學(xué)習(xí)能力和泛化能力模型
  • 胡思亂想
    • 全連接的深度神經(jīng)網(wǎng)絡(luò)就是理論上最完美的組合模型，問題在于維度災(zāi)難帶來的計算復(fù)雜度問題。
    • 為了解決計算復(fù)雜度問題，就需要了解其他分類模型，因為其他分類模型就是具備了先驗知識的神經(jīng)網(wǎng)絡(luò)模型，將那些分類模型轉(zhuǎn)化為神經(jīng)網(wǎng)絡(luò)模型后就可以大幅減少連接的數(shù)量。
    • 概率近似正確 (probably approximately correct, PAC) 來自計算學(xué)習(xí)理論，可參考[周志華，2018] C12, [Mitchell, 2003] C07
    • 集成學(xué)習(xí) (ensemble learning) 也被稱為多分類器系統(tǒng)、基于委員會的學(xué)習(xí)等，可參考[周志華，2018] C08

C09. EM 算法及推廣

• 學(xué)習(xí)基礎(chǔ)
  • 概率論：期望
  • 最大似然估計或極大后驗估計
  • 梯度下降
• EM 算法是對含有隱變量的概率模型進行極大似然估計或者極大后驗估計的迭代算法。
  • E 步，求期望；利用數(shù)據(jù)和假設(shè)的初值，求得一個隱變量的條件概率分布的期望，即 “Q 函數(shù)”。（因為無法求得條件概率分布的具體值）
  • M 步，求極值。利用 “Q 函數(shù)” 來求極值，這個極值可以幫助擬合的概率分布更加逼近真實分布。
  • Q 函數(shù)的定義（理解 Q 函數(shù)的涵義可以更好地推廣到應(yīng)用中，開始不理解也沒關(guān)系，可以在應(yīng)用中慢慢加深）
  • EM 算法的推導(dǎo)（如果書上的無法理解，還可以參考本文中的其他文獻）
    • EM 算法是收斂的，但是有可能收斂到局部最小值。
    • EM 算法可以看成利用凸函數(shù)進行概率密度逼近；
    • 如果原概率密度函數(shù)有多個極值，初值的不同就可能逼近到不同的極值點，所以無法保證全局最優(yōu)。
  • EM 算法的應(yīng)用（下面的兩個應(yīng)用都是重點，但是無法從本書中完全理解，可以在未來的應(yīng)用繼續(xù)探索）
    • 高斯混合模型
    • HMM（隱 Markov 模型） 參考 C10
  • EM 算法的推廣（建議跳過，對了解 EM 算法幫助不大，只有深入理解和研究 EM 算法才需要）
    • F 函數(shù)的極大 - 極大算法
    • 廣義 EM 算法（GEM）
• 學(xué)習(xí)總結(jié)
• EM算法的詳細推導(dǎo)。[Borman, 2004], 或者Determined22的EM算法簡述及簡單示例（三個硬幣的模型）
• EM算法的概率分析。[Friedman, 2001], 或者蘇劍林的梯度下降和EM算法
• EM算法的深入理解?？梢詤⒖际反浩娴?a >Hinton和Jordan理解的EM算法

C10. 隱 Markov 模型（HMM）的算法及推廣

• 學(xué)習(xí)基礎(chǔ)
  • 隨機過程：用于理解 Markov 鏈的數(shù)學(xué)含義
  • EM 算法：用于計算 HMM 的學(xué)習(xí)問題
• Markov 鏈的定義
  • 隨機過程
    • 研究對象是隨時間演變的隨機現(xiàn)象。[盛驟，2015] C12
    • 設(shè) T 是一無限實數(shù)集，對依賴于參數(shù) t（t 屬于 T）的一族（無限多個）隨機變量稱為隨機過程。
    • 我的理解
      • 隨機過程在任一個時刻 t, 被觀測到的狀態(tài)是隨機的，但是這個隨機狀態(tài)是由一個確定的函數(shù)控制的。
      • 例如：有 3 塊金屬放在箱子里面，任一個時刻 t 取出的金屬是隨機的，但是每塊金屬衰退的速度是由這塊金屬自身的函數(shù)控制的。
      • 隨機變量刻畫的是數(shù)值的隨機性（某個數(shù)出現(xiàn)的概率），隨機過程刻畫的是函數(shù)的隨機性（某個函數(shù)出現(xiàn)的概率）
  • Markov 過程
    • Markov 性或無后效性：過程（或系統(tǒng)）在時刻 t_0 所處的狀態(tài)為已知的條件下，過程在時刻 t>t_0 所處狀態(tài)的條件分布與過程在時刻 t_0 之前所處的狀態(tài)無關(guān)。即在已經(jīng)知道過程“現(xiàn)在”的條件下，其“將來”不依賴于“過去”。[盛驟，2015] C13
    • Markov 過程：具有 Markov 性的隨機過程，稱為 Markov 過程。
  • Markov 鏈
    • 時間和狀態(tài)都是離散的 Markov 過程稱為 Markov 鏈，簡稱馬氏鏈。
    • 深入理解可參考 [Rabiner, 1989]
  • HMM
    • 關(guān)于時序的概率模型
    • 用于描述一個被觀測到的隨機序列，這個隨機序列是由不可觀測的狀態(tài)隨機序列生成的，這個狀態(tài)隨機序列是由隱藏的 Markov 鏈隨機生成的。
      • 狀態(tài)序列 Q：隱藏的 Markov 鏈隨機生成的狀態(tài)序列；
      • 觀測序列 O：每個狀態(tài)生成一個觀測，一個狀態(tài)序列就會生成一個觀測序列。
      • 序列的每一個位置都可以看作一個時刻。
• HMM 的基本假設(shè)
  • 齊次 Markov 假設(shè)，即假設(shè)隱藏的 Markov 鏈在任意時刻 t 的狀態(tài)只依賴于前一個時刻的狀態(tài)，而與其他時刻的狀態(tài)及觀測無關(guān)，也與時刻 t 無關(guān)；
  • 觀測獨立性假設(shè)，即假設(shè)任意時刻 t 的觀測只依賴于該時刻的 Markov 鏈的狀態(tài)，與其他觀測與狀態(tài)無關(guān)。
• HMM 的基本元素
  • N，模型的狀態(tài)數(shù)；
  • M，每個狀態(tài)生成的可觀測的標(biāo)志數(shù)；
  • A，轉(zhuǎn)移概率矩陣，a_{ij} 表示從狀態(tài) i 轉(zhuǎn)移到狀態(tài) j 的概率；
  • B，觀測概率矩陣，b_{j} (k) 表示狀態(tài) j 產(chǎn)生標(biāo)志 k 的概率；
  • π，初始狀態(tài)分布，π_i 表示一開始系統(tǒng)在狀態(tài) i 的概率。
  • HMM 參數(shù)的數(shù)學(xué)表示：λ=(A, B, π)
• HMM 的三個基本問題
  • 概率計算問題
    • 給定觀測序列 O 和模型參數(shù) λ，計算基于這個模型下觀測序列出現(xiàn)的概率 P(O|λ) ；
  • 預(yù)測問題
    • 給定觀測序列 O 和模型參數(shù) λ，尋找能夠解釋這個觀測序列的狀態(tài)序列，這個狀態(tài)序列的可能性最大；
    • 除非是退化的模型，否則不會有“正確”的狀態(tài)序列，因為每個狀態(tài)序列都有可以生成觀測序列；
    • 只可能是依據(jù)某個優(yōu)化準(zhǔn)則，使找到的狀態(tài)序列盡可能的逼近真實的狀態(tài)序列。
  • 學(xué)習(xí)問題
    • 給定觀測序列 O，尋找能夠解釋這個觀測序列的模型參數(shù) λ，使得 P(O|λ) 最大。
    • 評測哪個模型能最好地解釋觀測序列。
• HMM 的三個基本問題的解決方案
  • 概率計算問題：前向算法；
    • 先了解直接計算法，理解 HMM 需要計算的概率的方法和目的，同時明白直接計算法存在的問題；
    • 再了解前向算法，如果利用柵格方法疊加前面計算的成果，從而降低直接計算法的龐大計算量。
  • 預(yù)測問題：Viterbi 算法；
  • 學(xué)習(xí)問題：前向 + 后向算法 +EM 算法。
    • 利用前向 + 后向算法計算轉(zhuǎn)移概率矩陣；
    • 再基于 MLE 理論構(gòu)造 P(O|λ) 函數(shù)；
    • 因為函數(shù)中有三個參數(shù)不可知，無法直接計算得到，因為采用 EM 算法迭代求解。
• HMM 的基本類型
  • 基本的 HMM 類型
    • 4 狀態(tài)遍歷 HMM；其他類型都是遍歷 HMM 的特例。
    • 4 狀態(tài)從左到右 HMM；
    • 6 狀態(tài)從左到右并行路徑 HMM。
  • 觀測序列的密度是連續(xù)函數(shù)的 HMM：增加了混合高斯作為約束；
  • 自回歸的 HMM：很適合語音處理；
  • 無輸出的 HMM：即某些狀態(tài)轉(zhuǎn)移時無觀測輸出，主要用于語音識別；
  • 一組狀態(tài)到另一組狀態(tài)轉(zhuǎn)換：組內(nèi)狀態(tài)無轉(zhuǎn)移；
  • 優(yōu)化準(zhǔn)則：利用概率理論（ML）或信息理論（MMI，MDI）刻畫；
  • 比較 HMM 模型：用于模型的測度和選擇，常用的測度（交叉熵或散度或判別信息）
• HMM 算法的具體實現(xiàn)方法
  • 觀測數(shù)據(jù)的尺度化，方便計算機處理，防止溢出；
  • HMM 模型的訓(xùn)練：通過多個觀測序列進行訓(xùn)練，估計模型的參數(shù)；
  • HMM 模型參數(shù)的初始值設(shè)定，沒有形式化方法，只能憑借經(jīng)驗；
  • 觀測數(shù)據(jù)數(shù)量過少，或者觀測數(shù)據(jù)不完整
    • 擴大用于訓(xùn)練的觀測集的大?。ìF(xiàn)實不可操作）；
    • 減少 HMM 模型的參數(shù)個數(shù)，即減小 HMM 模型的規(guī)模；
    • 利用插值的方法補齊或者增加數(shù)據(jù)。
  • HMM 模型的選擇
    • 確定 HMM 模型的狀態(tài)（模型狀態(tài)數(shù)，模型路徑數(shù)）
    • 確定 HMM 觀測的標(biāo)志（連續(xù)還是離散，單個還是混合）
    • 無形式化方法，依賴于具體的應(yīng)用。
• 學(xué)習(xí)總結(jié)
  • 隨機過程和 HMM 算法的基本概念的理解，特別是語音識別和語言處理方向的研究極為重要；
  • HMM 算法的計算過程的了解，雖然可以調(diào)用成熟的模塊，但是了解這個計算過程對于 HMM 計算的調(diào)優(yōu)可能會有幫助；
  • HMM 算法的學(xué)習(xí)極力推薦 [Rabiner, 1989]，本章的框架就是基于這篇文章寫的。

C11. 條件隨機場（CRF）的算法及推廣

• 條件隨機場（Conditional Random Field, CRF）的基本概念
  • 概率模型
    • 提供了一種描述框架，將學(xué)習(xí)任務(wù)歸結(jié)于計算變量的概率分布。
    • 推斷：利用已知變量推測未知變量的分布，核心是如何基于可觀測變量推測出未知變量的條件分布。
  • 生成模型與判別模型
    • 生成 (generative) 模型
      • 考慮聯(lián)合分布，是所有變量的全概率模型；
      • 由狀態(tài)序列決定觀測序列，因此可以模擬（“生成”）所有變量的值。
      • 具有嚴格的獨立性假設(shè)；
      • 特征是事先給定的，并且特征之間的關(guān)系直接體現(xiàn)在公式中。
      • 優(yōu)點
        • 處理單類問題比較靈活；
        • 模型變量之間的關(guān)系比較清楚；
        • 模型可以通過增量學(xué)習(xí)獲得；
        • 可以應(yīng)用于數(shù)據(jù)不完整的情況。
      • 缺點：模型的推導(dǎo)和學(xué)習(xí)比較復(fù)雜。
      • 應(yīng)用
        • n 元語法模型
        • HMM
        • Markov 隨機場
        • Naive Bayes 分類器
        • 概率上下文無關(guān)文法
    • 判別 (discriminative) 模型
      • 考慮條件分布，認為由觀測序列決定狀態(tài)序列，直接對后驗概率建模；
      • 從狀態(tài)序列中提取特征，學(xué)習(xí)模型參數(shù)，使得條件概率符合一定形式的最優(yōu)。
      • 特征可以任意給定，一般利用函數(shù)進行表示。
      • 優(yōu)點：模型簡單，容易建立與學(xué)習(xí)；
      • 缺點：描述能力有限，變量之間的關(guān)系不清晰，只能應(yīng)用于有監(jiān)督學(xué)習(xí)。
      • 應(yīng)用
        • 最大熵模型
        • 條件隨機場
        • 最大熵 Markov 模型 (maximum-entropy Markov model, MEMM)
        • 感知機
  • 概率圖模型：是一類用圖來表達變量相關(guān)關(guān)系的概率模型，
    • 有向圖模型（Bayes 網(wǎng)）：使用有向無環(huán)圖表示變量間的依賴關(guān)系，如：推導(dǎo)關(guān)系
      • 靜態(tài) Bayes 網(wǎng)絡(luò)
      • 動態(tài) Bayes 網(wǎng)絡(luò)：適合處理一般圖問題
        • 隱 Markov 模型：結(jié)構(gòu)最簡單的動態(tài) Bayes 網(wǎng)，適合處理線性序列問題，可用于時序數(shù)據(jù)建模，主要應(yīng)用領(lǐng)域為語音識別、自然語言處理等。
    • 無向圖模型（Markov 網(wǎng)）：使用無向圖表示變量間的依賴關(guān)系，如：循環(huán)關(guān)系
      • Markov 隨機場：典型的 Makrov 網(wǎng)
      • Boltzman 機
      • 通用條件隨機場：適合處理一般圖問題
        • 線性鏈?zhǔn)綏l件隨機場：適合處理線性序列問題
  • 隨機場：
• 概率圖模型
  • 在概率模型的基礎(chǔ)上，使用了基于圖的方法來表示概率分布（或者概率密度、密度函數(shù)），是一種通用化的不確定性知識表示和處理的方法。
  • 圖是表示工具
    • 結(jié)點表示一個或者一組隨機變量
    • 結(jié)點之間的邊表示變量間的概率依賴關(guān)系，即“變量關(guān)系圖”。
• Bayes 網(wǎng)絡(luò)（信念網(wǎng)，信度網(wǎng)，置信網(wǎng)）
  • 目的：通過概率推理處理不確定性和不完整性問題
  • 構(gòu)造 Bayes 網(wǎng)絡(luò)的主要問題
    • 表示：在某一隨機變量的集合上給出其聯(lián)合概率分布。
    • 推斷：因為模型完整描述了變量及其關(guān)系，可以推斷變量的各種問題。
      • 精確推理方法：變量消除法和團樹法
      • 近似推理方法：重要性抽樣法、MCMC 模擬法、循環(huán)信念傳播法和泛化信念傳播法等
    • 學(xué)習(xí)：決定變量之間相互關(guān)聯(lián)的量化關(guān)系，即儲存強度估計。
      • 參數(shù)學(xué)習(xí)常用方法：MLE、MAP、EM 和 Bayes 估計法。
      • 結(jié)構(gòu)學(xué)習(xí)：
• Markov 隨機場 (Markov Random Field, MRF)
  • 定義
    • 是一組有 Markov 性質(zhì)的隨機變量的聯(lián)合概率分布模型，
    • 聯(lián)合概率分布滿足成對、局部和全局 Markov 性。
    • 由一個無向圖 G 和定義 G 上的勢函數(shù)組成。
  • 基本概念
    • 團 (clique)：是圖中結(jié)點的一個子集，團內(nèi)任意兩個結(jié)點都有邊相連。也稱為完全子圖 (complete subgraph)。
    • 極大團 (maximal clique)：若在一個團 C 中加入任何一個結(jié)點都不再形成團，就說那個團 C 是最大團。極大團就是不能被其他團所包含的團。
    • 因子分解 (factorization)：將概率無向圖模型的聯(lián)合概率分布表示為其最大團上的隨機變量的函數(shù)的乘積形式的操作。
    • 分離集 (separating set)：若從結(jié)點集 A 中的結(jié)點到結(jié)點集 B 中的結(jié)點都必須經(jīng)過結(jié)點集 C 中的結(jié)點，則稱結(jié)點集 A 和 B 被結(jié)點集 C 所分離。
    • 全局 Markov 性：給定兩個變量子集的分離集，則這兩個變量子集條件獨立
      • 局部 Markov 性：給定某變量的鄰接變量，則該變量獨立于其他變量
      • 成對 Markov 性：給定所有其他變量，兩個非鄰接變量條件獨立 。
    • 勢函數(shù)
      • 用于將模型進行參數(shù)化的參數(shù)化因子，稱為團勢能或者團勢能函數(shù)，簡稱勢函數(shù)。
      • 定義在變量子集上的非負實函數(shù)，主要用于定義概率分布函數(shù)，亦稱“因子”。
      • 多個變量之間的聯(lián)合概率可以基于團分解為多個因子的乘積。
      • 指數(shù)函數(shù)經(jīng)常被用于定義勢函數(shù)。
• 條件隨機場 (Conditional Random Field, CRF)
  • 用來處理標(biāo)注和劃分序列結(jié)構(gòu)數(shù)據(jù)的概率化結(jié)構(gòu)模型。
  • 是給定一組輸入隨機變量條件下另一組輸出隨機變量的條件概率分布模型
    • 假設(shè)輸出隨機變量構(gòu)成 Makrov 隨機場。
  • 線性鏈條件隨機場
    • 輸入序列對輸出序列預(yù)測的判別模型
    • 形式為對數(shù)線性模型
  • 構(gòu)造 CRF 的主要問題
    • 特征的選取
    • 參數(shù)訓(xùn)練
    • 解碼
  • 優(yōu)點：相比于 HMM 沒有獨立性要求，相比于條件 Markov 模型沒有標(biāo)識偏置問題。
• 學(xué)習(xí)總結(jié)
  • 本書的描述概念性內(nèi)容過少，不利于理解，建議閱讀 [周志華，2018] C14
  • 以概率圖模型為基礎(chǔ)來理解條件隨機場會更加容易，也能夠保證知識相互之間的聯(lián)系，還可以加深對 HMM 的理解。
  • CRF 的主要應(yīng)用是自然語言處理，因此結(jié)合自然語言處理來理解概念也會更加深刻。 [宗成慶，2018] C06
  • 雖然國內(nèi)幾本書都寫的不錯，但是 CRF 都不是他們書中的重點，若想深入學(xué)習(xí) CRF 還是請參考 [Sutton, 2012]

C12. 統(tǒng)計學(xué)習(xí)方法總結(jié)

10 種統(tǒng)計學(xué)習(xí)方法特點的概括總結(jié)

參考文獻

• [Borman, 2004] Borman S. The expectation maximization algorithm-a short tutorial [J]. Submitted for publication, 2004, 41.
• [Charles, 2011] Charles Sutton and Andrew McCallum, An Introduction to Conditional Random Fields [J]. Machine Learning 4.4 (2011): 267-373.
• [Determined22, 2017] Determined22, http://www.cnblogs.com/Determined22/p/5776791.html , 2017.
• [Duda, 2003] Duda R O, Peter E Hart, etc. 李宏東等譯。模式分類 [M]. 機械工業(yè)出版社。2003.
• [Friedman, 2001] Friedman, Jerome H. “Greedy Function Approximation: A Gradient Boosting Machine.” Annals of Statistics, vol. 29, no. 5, 2001, pp. 1189–1232.
• [Friedman, 2001] Friedman J, Hastie T, Tibshirani R. The elements of statistical learning [M]. New York: Springer series in statistics, 2001.
• [Goodfellow, 2017] Goodfellow I, Bengio Y, Courville A. 深度學(xué)習(xí) [M]. 人民郵電出版社。2017.
• [Hagan, 2006] Martin T. Hagan. 戴葵等譯。神經(jīng)網(wǎng)絡(luò)設(shè)計 [M]. 2002.
• [Haykin, 2011] Haykin S . 神經(jīng)網(wǎng)絡(luò)與機器學(xué)習(xí) [M]. 機械工業(yè)出版社。2011.
• [Hyvarinen, 2007] Aapo Hyvarinen, Juha Karhunen. 周宗潭譯 獨立成分分析 [M]. 電子工業(yè)出版社。2007.
• [Mitchell, 2003] Tom M.Mitchell. 肖華軍等譯。機器學(xué)習(xí) [M]. 機械工業(yè)出版社。2003
• [Rabiner, 1989] Rabiner L R. A tutorial on hidden Markov models and selected applications in speech recognition [J]. Proceedings of the IEEE, 1989, 77(2): 257-286.
• [Samuel, 2007] Samuel Karlin M.Taylor 著，莊興無等譯。 隨機過程初級教程。 [M]. 人民郵電出版社， 2007.
• [Sutton, 2012] Sutton, Charles, and Andrew McCallum. “An introduction to conditional random fields.” Foundations and Trends? in Machine Learning 4.4 (2012): 267-373.
• [周志華，2018] 周志華 機器學(xué)習(xí) [M]. 清華大學(xué)出版社。2018
• [蘇劍林，2017] 蘇劍林，https://spaces.ac.cn/archives/4277 , 2017.
• [盛驟，2015] 盛驟等編，概率論與數(shù)理統(tǒng)計（第四版）。 [M]. 高等教育出版社。 2015.
• [宗成慶，2018] 宗成慶著，統(tǒng)計自然語言處理（第二版）。 [M]. 清華大學(xué)出版社。 2018.

符號說明

• Pxx，代表第 xx 頁；
• Cxx，代表第 xx 章；
• [M]，代表圖書；
• [J]，代表雜志；