全書總評(píng)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

基本概念

• 輸入空間：輸入數(shù)據(jù)所有可能取值的集合；集合中元素的個(gè)數(shù)可以有限，也可以是整個(gè)空間；
• 輸出空間：輸出數(shù)據(jù)所有可能取值的集合；集合中元素的個(gè)數(shù)可以有限，也可以是整個(gè)空間；
• 假設(shè)空間：由輸入空間到輸出空間的映射的集合，即可供選擇的模型構(gòu)成的空間；
• 特征空間：所有特征向量存在的空間。
  • 每個(gè)具體的輸入是一個(gè)實(shí)例 (instance), 通常由特征向量 (feature vector) 表示。
• 統(tǒng)計(jì)學(xué)習(xí)中的有監(jiān)督學(xué)習(xí)根據(jù) “輸入變量” 和 “輸出變量” 的不同主要包括
  • 分類問題：輸出變量為有限個(gè)離散變量的預(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)計(jì)學(xué)習(xí)三個(gè)要素

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

模型

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

策略

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

算法

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

模型的評(píng)估與選擇

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

模型評(píng)估

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

模型選擇

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

正則化與交叉驗(yàn)證

正則化

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

交叉驗(yàn)證

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

泛化能力

泛化誤差

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

泛化誤差的上界

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

生成模型與判別模型

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

分類問題

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

標(biāo)注問題

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

回歸問題

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

C02. 感知機(jī)

• 模型
  • 感知機(jī)，是根據(jù)輸入實(shí)例的特征向量對(duì)其進(jìn)行二類分類的線性分類模型，屬于判別模型；
  • 模型參數(shù)包括：權(quán)值或權(quán)值向量，偏置。
  • 模型對(duì)應(yīng)于輸入空間（特征空間）中的分離超平面；
• 策略
  • 假設(shè)：感知機(jī)學(xué)習(xí)的訓(xùn)練數(shù)據(jù)集是線性可分的；
  • 目標(biāo)：求得一個(gè)能夠?qū)⒂?xùn)練集正實(shí)例點(diǎn)和負(fù)實(shí)例點(diǎn)完全正確分開的分離超平面；
  • 策略：即定義（經(jīng)驗(yàn)）損失函數(shù)，并將損失函數(shù)極小化；
    • 損失函數(shù)定義為：誤分類點(diǎn)的總數(shù)，不易優(yōu)化；
    • 損失函數(shù)定義為：誤分類到分離超平面的總距離；
• 算法
  • 感知機(jī)學(xué)習(xí)算法是基于誤差 - 修正的學(xué)習(xí)思想，是由誤分類驅(qū)動(dòng)的；
  • 學(xué)習(xí)算法的優(yōu)化方法
    • 批量學(xué)習(xí)可以基于進(jìn)行優(yōu)化
      • 一階：最速下降法或梯度下降法；
      • 二階：牛頓法、共軛梯度法等等
    • 在線學(xué)習(xí)：基于隨機(jī)梯度下降法的對(duì)損失函數(shù)進(jìn)行最優(yōu)化 [Goodfellow, 2017] P95, P180
      • 原始形式：算法簡單且易于實(shí)現(xiàn)。先任意選取一個(gè)超平面，然后隨機(jī)選擇一個(gè)誤分類點(diǎn)使其用梯度下降法極小化目標(biāo)函數(shù)
        • 例 2.1（比較簡單，可以了解）
        • 定理 2.1（過于簡略，建議跳過）
      • 對(duì)偶形式 （沒看出與原始形式有何區(qū)別，也沒從別的書上看到過這種說明方式，建議跳過）
  • 當(dāng)訓(xùn)練數(shù)據(jù)集線性可分時(shí)，感知機(jī)學(xué)習(xí)算法是收斂的，且有無窮多個(gè)解。
• 學(xué)習(xí)總結(jié)
  • 感知機(jī)是神經(jīng)網(wǎng)絡(luò)的基礎(chǔ)，本章只有單個(gè)神經(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) 是一個(gè)基本且簡單的方法，用于分類與回歸。
  • 輸入為實(shí)例的特征向量，對(duì)應(yīng)于特征空間的點(diǎn)；
  • 輸出為實(shí)例的類別，可以取多個(gè)類。
• 基本思想
  • 假設(shè)給定一個(gè)訓(xùn)練數(shù)據(jù)集，其中的實(shí)例類別已經(jīng)確定；
  • 對(duì)新輸入的實(shí)例分類時(shí)，根據(jù)其 k 個(gè)最近鄰的訓(xùn)練實(shí)例的類別，通過多數(shù)表決等方式進(jìn)行預(yù)測。
  • 不具有顯式的學(xué)習(xí)過程。
  • 實(shí)際上利用訓(xùn)練數(shù)據(jù)集對(duì)特征向量空間進(jìn)行切分，并作為其分類的 “模型”。
• k 近鄰的模型
  • 對(duì)應(yīng)于基于訓(xùn)練數(shù)據(jù)集對(duì)特征空間的一個(gè)劃分。
  • 當(dāng)訓(xùn)練集、距離度量、k 值及分類決策規(guī)則確定后，輸入實(shí)例所屬類別也唯一確定。
• k 近鄰法的三個(gè)要素
  • 學(xué)習(xí)準(zhǔn)則：距離度量，常用歐氏距離；（距離定義）[Duda, 2003]
  • k 值的選擇：反映了近似誤差與估計(jì)誤差之間的權(quán)衡。
    • k 值越大時(shí)，近似誤差會(huì)增大，估計(jì)誤差會(huì)減小，模型也越簡單；
    • k 值越小時(shí)，近似誤差會(huì)減少，估計(jì)誤差會(huì)增大，模型也越復(fù)雜。
    • 可以用交叉驗(yàn)證的方式選擇最優(yōu) k 值。
  • 分類決策規(guī)則：多數(shù)表決規(guī)則 (marjority voting rule), 等價(jià)于 經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化。
• k 近鄰法的實(shí)現(xiàn)基于 kd 樹。（了解即可，實(shí)際應(yīng)用中大多使用的是已經(jīng)成熟的軟件包）
  • kd 樹是一種便于對(duì) k 維空間中的數(shù)據(jù)進(jìn)行快速檢索的數(shù)據(jù)結(jié)構(gòu)；
  • kd 樹是二叉樹，表示對(duì) k 維空間的一個(gè)劃分；
  • kd 樹的每個(gè)圣戰(zhàn)對(duì)應(yīng)于 k 維空間劃分中的一個(gè)超矩形區(qū)域；
  • 利用 kd 樹可以省去對(duì)大部分?jǐn)?shù)據(jù)點(diǎn)的搜索，從而減少搜索的計(jì)算量。
• 學(xué)習(xí)總結(jié)
  • 了解即可，因?yàn)槊鎸?duì)高維問題效果很差，需要考慮降維操作。[周志華，2018] P225

C04. 樸素 Bayes 法

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

C05. 決策樹 (decision tree)

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

C06. Logistic 回歸與最大熵模型

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

C07. 支持向量機(jī)

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

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

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

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

C09. EM 算法及推廣

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

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

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

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

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

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

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

參考文獻(xiàn)

• [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]. 機(jī)械工業(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è)計(jì) [M]. 2002.
• [Haykin, 2011] Haykin S . 神經(jīng)網(wǎng)絡(luò)與機(jī)器學(xué)習(xí) [M]. 機(jī)械工業(yè)出版社。2011.
• [Hyvarinen, 2007] Aapo Hyvarinen, Juha Karhunen. 周宗潭譯 獨(dú)立成分分析 [M]. 電子工業(yè)出版社。2007.
• [Mitchell, 2003] Tom M.Mitchell. 肖華軍等譯。機(jī)器學(xué)習(xí) [M]. 機(jī)械工業(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 著，莊興無等譯。 隨機(jī)過程初級(jí)教程。 [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] 周志華 機(jī)器學(xué)習(xí) [M]. 清華大學(xué)出版社。2018
• [蘇劍林，2017] 蘇劍林，https://spaces.ac.cn/archives/4277 , 2017.
• [盛驟，2015] 盛驟等編，概率論與數(shù)理統(tǒng)計(jì)（第四版）。 [M]. 高等教育出版社。 2015.
• [宗成慶，2018] 宗成慶著，統(tǒng)計(jì)自然語言處理（第二版）。 [M]. 清華大學(xué)出版社。 2018.

符號(hào)說明

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