CS229T/STAT231 是由斯坦福大學開設的統計學習理論課程，著重於對機器學習演算法統計特性的理論理解，涉及機器學習演算法何時起作用和原因、如何形式化演算法從資料中學習的含義、如何使用數學思維來設計更好的機器學習方法等基本課題。今天要介紹由斯坦福大學計算機系教授 Percy Liang 近期公佈的 CS229T/STAT231 的學習筆記。

筆記地址：https://github.com/percyliang/cs229t/blob/master/lectures/notes.pdf

課程 topic

一致收斂（VC 維度，Rademacher 複雜性等）

隱式/演算法正則化，神經網路的泛化理論

核心方法

線上學習和 bandits 問題

無監督學習：指數族，矩方法，GAN 的統計理論

預備知識

熟悉線性代數、實分析、機率論和進行數學證明的基本能力

機器學習（CS229）或統計學（STATS315A）

推薦學習凸最佳化（EE364A）

筆記目錄

1.1 這門課程是關於什麼的？

機器學習已成為許多應用領域中不可或缺的一部分，包括科學（生物學、神經科學、心理學、天文學等）和工程學（自然語言處理、計算機視覺、機器人學等）。但機器學習不是一種單一的方法；相反，它包含一系列看似完全不同的框架和範例，包括分類、迴歸、聚類、矩陣分解、貝葉斯網路、馬爾可夫隨機場等。本課程旨在揭示這些不同技術背後的共同統計學原理。

本課程是關於學習演算法的理論分析。課程中介紹的許多分析技術（包括機率、線性代數和最最佳化的完美結合）值得研究，並且在機器學習之外也是有用的。

更深入的理論理解可以提供新的視角，並且可以幫助對現有演算法進行修改和最佳化，也有助於提出新的演算法。如果沒有理論提供的概念性分析，這些新演算法可能很難發現。

理論依賴的假設可能同時太強（例如，資料服從獨立同分布條件）又太弱（例如，任何分佈）。實際上，理論的目的不是為了簡化成只需插入數字的公式。相反，理論應該改變思維方式。

本課程分為四個部分：漸近性、一致性收斂、核方法和線上學習。我們將從非常強的假設（假設資料是高斯的、漸近的）轉變為非常弱的假設（假設資料可以對抗地在線上學習中生成）。在這方面，核方法有點不同；它更重要的在於提供表達能力，而不是統計學習。

1.2 漸近

給定基於一些未知引數向量θ*提取的資料，我們從資料中計算出θ hat，θ hat 和θ*有多接近？

對於簡單的模型例如高斯均值估計和固定設計的線性迴歸，我們可以求出θ hat -θ*的閉式解。

對於大多數模型，例如 logistic 迴歸，我們不能這樣做。但我們可以使用統計學中的常用工具即漸近分析。其基本思想是做泰勒級數展開以得到漸近正態性：即，sqrt(n)*(θ^−θ*) 的分佈隨著樣本數量 n 的增加逼近於高斯分佈。漸近的意義是即使θ hat 很複雜，我們也可以得到簡單的結果。

我們的大多數分析都將使用最大似然估計，這種估計具有很好的統計特性（它們具有所有估計量中最小的漸近方差）。但是對於大多數隱變數模型而言，最大似然在計算上很困難，並且需要進行非凸最佳化。這些最佳化問題通常由 EM 演算法解決，只能保證收斂到區域性最優。我們將展示矩方法（一種可以追溯到 Pearson（1894）的引數估計經典方法）如何解決這個問題，得到能夠產生全域性最優解的有效演算法（Anandkumar et al.，2012b）。

圖 1：在漸近分析中，我們研究當一個引數估計θ hat 接近真實引數θ*時，θ hat 的行為。

1.3 一致性收斂

漸進線提供了一個很好的初值分析，並且適用於許多場景。但它有兩個主要的缺點：它需要目標函式是平滑的；在漸進線開始逼近前無法確定要選擇多大的樣本數量 n。

一致性收斂提供了另一種視角，若考慮一個標準的監督學習問題：給定訓練集 (x, y)，學習演算法會從所有假設 H 中選擇一個最優的預測器 h : X → Y，然後我們在測試資料評估該預測器。現在有一個簡單的問題：訓練誤差 Lˆ(h) 和測試誤差 L(h) 之間的關係是什麼樣的？

圖 2：我們希望最小化期望風險 L 以獲得最優的 h*，但是我們實際上只能最小化經驗風險 L ^以獲得 h^。

對於固定的 h ∈ H，訓練誤差 Lˆ(h) 為獨立同分布隨機變數（每一個樣本的損失）的均值，它將收斂到測試誤差 L(h)，且收斂率由 Hoeffding 不等式或中心極限定理決定。

但問題是我們假設基於訓練資料選擇一個最佳的假設，並不是使用固定的 h。具體而言，如果考慮經驗風險最小化（ERM），我們需要最小化訓練誤差，從而獲得最優的經驗預測器：

直觀而言，訓練誤差應該比測試誤差小，因此可靠性也低一些。我們可以使用一致性收斂將這一直觀理解形式化為：

這些泛化邊界在某種意義上是統計學習理論的核心。但是在這個過程中，我們可以發展出廣泛有用的不等式，它的應用範圍甚至超越了機器學習。

1.4 核方法

現在我們先繞過學習演算法的誤差分析，並考慮我們到底應該學習什麼樣的模型。現實資料非常複雜，所以我們需要極具表達能力的模型。核方法提供了一種嚴格的數學框架，它可以構建複雜、非線性的模型，而且還只需要基於線性模型的機制。

核方法提供了另一種方法定義函式。我們一般定義一個半正定的核函式 k(x, x" )，它將捕捉 x 和 x"之間的相似性，並透過對比一組樣本而定義整個函式：

核方法允許我們構建複雜的非線性函式，例如高斯核函式和徑向基核函式等。它們是通用的方法，且能逼近任意連續的函式。而對於序列、樹型及圖等資料結構，我們可以定義核函式以利用動態規劃實現高效計算。

最後，核方法都是在函式層面上進行操作的，我們可以定義函式的整體空間為再生核希爾伯特空間（RKHS），它允許我們將函式視為向量並執行線性代數的計算規則。

事實證明，所有這三個概念都在描述相同的東西，它們之間相互有聯絡：

圖 3：核方法中的三個關鍵數學概念。

1.5 線上學習（Lecture 1）

真實世界是動態的，使用基於漸近和一致性收斂的早期分析會錯失某些重要性質。線上學習試圖以兩種方式解決這個問題：

目前為止，為了分析一個學習演算法的誤差，我們必須假設訓練樣本是獨立同分布的。然而在實踐中，資料點可能是互相依賴的，甚至更糟，即它們可能是對抗生成的。

此外，我們目前考慮的都是批次學習設定，即拿到一個訓練集，學習一個模型，然後部署模型。但在實踐中，資料可能是以流的形式存在的，此時我們需要交替學習和預測。

圖 4：線上學習遊戲。