CS229T/STAT231 是由史丹福大學開設的統計學習理論課程，著重於對機器學習算法統計特性的理論理解，涉及機器學習算法何時起作用和原因、如何形式化算法從數據中學習的含義、如何使用數學思維來設計更好的機器學習方法等基本課題。今天要介紹由史丹福大學計算機系教授 Percy Liang 近期公布的 CS229T/STAT231 的學習筆記。
筆記地址：https://github.com/percyliang/cs229t/blob/master/lectures/notes.pdf
課程 topic
預備知識
筆記目錄
1 課程概述
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：在線學習遊戲。