全書總評

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

C01. 統計學習方法概論

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

統計學習

統計學習導言

• 統計學習 (statistical learning): 計算機基于數據構建概率統計模型，并運用模型對數據進行預測與分析的一門學科。
  • 因此統計學習也稱為統計機器學習 (statistical machine learning).
• 統計學習的主要特點
  • 理論基礎
    • 數學基礎：微積分、線性代數、概率論、統計學、計算理論、最優化理論
    • 其他基礎：信息論、計算機科學及應用相關的科學等多個領域的交叉學科
    • 在發展中形成自己獨立的理論體系與方法論。
  • 應用基礎：計算機及網絡；
  • 研究對象：數據，是數據驅動的學科；
  • 研究目的：對數據進行分類和預測；
  • 研究手段：通過統計學習方法構建模型，并應用模型進行分類和預測；

統計學習的對象

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

統計學習的目的

• 模型：學習什么樣的模型
• 策略：如何學習模型 → 使模型能夠對數據進行準確地分類和預測
• 算法：如何提高模型的學習效率

統計學習的方法

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

統計學習的研究

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

統計學習的重要性

• 是處理海量數據的有效方法；
• 是計算機智能化的有效手段；
• 是計算機科學發展的重要組成。

監督學習

• 監督學習的任務：是學習一個模型，使模型能夠對任意給定的輸入，及其相應的輸出做出一個好的預測

基本概念

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

問題的形式化描述

• 在學習過程中，學習系統（也就是學習算法）試圖通過給定的訓練數據集合中的樣本帶來的信息來學習得到模型。

統計學習三個要素

• 統計學習方法 = 模型 + 策略 + 算法

模型

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

策略

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

算法

• 統計學習是基于訓練數據集，根據學習策略，從假設空間中選擇最優模型，最后需要考慮用什么樣的計算方法求解最優模型。
• 算法 即計算方法。統計學習的算法就轉化為求解最優化問題的算法。
  • 有顯式的解析解的最優化問題；
  • 無顯式的解析解的最優化問題，需要用數值計算的方法求解。
    • 如何保證找到全局最優解；
    • 如何保證求解的過程高效。

模型的評估與選擇

• 1.4~1.7, 與模型選擇有關的問題。
• 1.8~1.10, 與模型應用有關的問題。

模型評估

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

模型選擇

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

正則化與交叉驗證

正則化

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

交叉驗證

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

泛化能力

泛化誤差

• 泛化能力 (generalization ability): 是指學習方法學習到的模型對未知數據的預測能力
• 泛化誤差 (generalization error): 是指學到的模型對未知數據預測產生的誤差，反映了學習方法的泛化能力。

泛化誤差的上界

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

生成模型與判別模型

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

分類問題

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

標注問題

• 標注問題：是分類問題的推廣，也是更復雜的結構預測問題的簡單形式。
  • 輸入是一個觀測序列；
  • 輸出是一個標記序列或狀態序列。
  • 目標是通過學習得到能夠對觀測序列給出標記序列作為預測的模型。
• 解決標注問題的兩個過程：學習過程 和 標注過程
• 評價標注問題的指標：準確率、精確率和召回率。
• 解決標注問題的常用方法：隱 Markov 模型和條件隨機場。

回歸問題

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

C02. 感知機

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

C03. k 近鄰法

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

C04. 樸素 Bayes 法

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

C05. 決策樹 (decision tree)

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

C06. Logistic 回歸與最大熵模型

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

C07. 支持向量機

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

C08. 提升方法（集成學習）

提升方法是一種統計學習方法，也是一種提升模型學習能力和泛化能力的方法，還是一種組合學習（集成學習）的方法，是統計學習中最有效的方法之一。

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

C09. EM 算法及推廣

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

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

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

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

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

C12. 統計學習方法總結

10 種統計學習方法特點的概括總結

參考文獻

• [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]. 機械工業出版社。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. 深度學習 [M]. 人民郵電出版社。2017.
• [Hagan, 2006] Martin T. Hagan. 戴葵等譯。神經網絡設計 [M]. 2002.
• [Haykin, 2011] Haykin S . 神經網絡與機器學習 [M]. 機械工業出版社。2011.
• [Hyvarinen, 2007] Aapo Hyvarinen, Juha Karhunen. 周宗潭譯 獨立成分分析 [M]. 電子工業出版社。2007.
• [Mitchell, 2003] Tom M.Mitchell. 肖華軍等譯。機器學習 [M]. 機械工業出版社。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] 周志華 機器學習 [M]. 清華大學出版社。2018
• [蘇劍林，2017] 蘇劍林，https://spaces.ac.cn/archives/4277 , 2017.
• [盛驟，2015] 盛驟等編，概率論與數理統計（第四版）。 [M]. 高等教育出版社。 2015.
• [宗成慶，2018] 宗成慶著，統計自然語言處理（第二版）。 [M]. 清華大學出版社。 2018.

符號說明

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