編譯：琰琰
第一性原理是一個物理學概念，可以簡單理解為一個定理，或者定理的推論。
同為評價事物的依據，第一性原理和經驗引數代表兩個極端。經驗引數是透過大量例項得出的規律性的資料，而第一性原理是某些硬性規定或推演得出的結論。
在深度學習理論中，經驗性學習是學者們常常使用的研究方法，它為深度學習的發展提供了有價值的指導。然而，這種基於“經驗引數”的方法並沒有解決神經網路可解釋性差的問題。
而在近期，已經有一些深度學習的理論性工作開始受到關注。比如今年4月，UC Berkeley馬毅教授發表報告Deep Networks from First Principle，從第一性原理的角度，闡述了最大編位元速率衰減（Maximal Coding Rate Reduction， MCR^2）作為深度模型最佳化的系列工作。
近日，來自巴黎INRIA研究中心的Francis Bach教授也分享了他對第一性原理在深度學習領域應用的思考。這篇新書稿名為“learning Theory from Fist Principles”，在這本書中，Francis Bach展示了學習框架的最新研究成果，以及第一性原理在學習理論中的證明結果。
書稿連結：https：//www。di。ens。fr/~fbach/ltfp_book。pdf
根據作者介紹，這本書稿摘自Francis Bach在2020年秋季學期一堂課的講稿。這堂課採取的是線上授課，他希望撰寫書稿對課堂內容進行一個更詳盡的整理。
本書的目標是展示學習理論中被廣泛使用的學習架構的最新研究成果，主要面向以理論為導向的學生，以及希望對機器學習演算法和相關領域中的基礎數學有更好理解的學生，他們是對計算機視覺或自然語言處理等學習方法感興趣的主要群體。
在書中，作者以簡化的語言闡述了第一性原理的諸多證明結果，並透過簡單且相關的示例展示了學習理論的重要概念。即使在沒有證明的情況下，書中也呈現了一般結果。考慮到第一性原理的概念是主觀的，讀者在學習之前需要對線性代數、機率論和微積分等基礎知識有一定的瞭解。
學習理論部分是本書的核心章節。考慮到演算法的實踐性，書中描述的所有演算法框架都是經常使用的。此外，大多數學習方法都提供了簡單的說明性實驗，並附上了部分程式碼（Matlab、Julia和Python），以便學生在綜合實驗中看到演算法是簡單且有效的。
本書在章節設定上是任意的，也是基於個人興趣的，因此，如強化學習、無監督學習等許多重要的演算法框架可能並未出現。以下是作者目前正在擴充的一些附加章節：
– 整合學習（Ensemble learning）
– Bandit最佳化（Bandit optimization ）
–機率方法（ Probabilistic methods ）
– 結構化預測（Structured prediction）
目前本書主要分為三個部分：基礎（Preliminaries ）、學習演算法的一般化界限（Generalization bounds for learning algorithms）以及專題（Special topics）
Part 1
基礎
第一章：數學基礎
線性代數：避免冗長和錯誤計算的技巧。
集中不等式：對於n個獨立的隨機變數，經驗平均值與期望值之間的偏差為O（1/√ n），那麼O是什麼含義？
這一章主要回顧了本書中所使用的非初等數學工具：先是線性代數技巧，後是集中不等式。讀者可暫時跳過這部分內容，因為相關結果會在需要時引用。
第二章：自監督學習
決策理論（損失、風險、最優預測）：給定足夠大的資料和計算資源，最優預測和效能是什麼？
統計學習理論：演算法何時“一致”？
沒有免費的午餐定理（NFL）：沒有假設，學習是不可能的。
第三章：線性最小二乘迴歸
普通最小二乘估計：最小二乘迴歸與線性引數化預測導致線性系統的大小為d（預測的數量）。
在固定設定下的保證：當假定輸入為確定性的，且d>n時，過度風險等於
嶺迴歸：隨著ℓ2 正則化，過度風險邊界變得與維數無關，並允許高維特徵向量，其中d>n。
隨機設計環境中的保證：雖然很難表現出來，但它們有相似的形式。
效能下限：在規範下，比率不可再提高。
Part 2
學習演算法的一般化界限
第四章：經驗風險最小化
風險的凸化：對於二元分類，可以透過凸代理實現最優預測。
風險分解：風險可以分解為近似誤差和估計誤差之和。
Rademacher complexities：用於研究估計誤差和計算期望之間均勻偏差的強大工具。
與統計量漸近分佈的關係：經典的漸近結果提供了經驗風險最小化行為的精細描述，它們提供了效能的漸近極限作為一個定義良好的常數乘以1/n，但它們不具有小樣本效應的特徵。
本章主要介紹基於經驗風險最小化的方法。在研究必要的機率工具之前，首先探討了輸出空間不是向量空間的問題，例如Y={−1，1}，可以用所謂的損失函式的凸代理重新表示。
第五章：最佳化機器學習
梯度下降：對於條件良好的凸問題，一階最佳化演算法收斂速度呈指數級增長。
隨機梯度下降（SGD）：大規模機器學習的一階演算法，收斂為1/t或1/√ t、 其中t是迭代次數。
透過SGD的泛化邊界：只需對資料進行一次傳遞，就會避免出現過擬合的風險，並獲得未見過資料的泛化邊界。
方差縮減：當最小化強凸有限和時，這類演算法以指數級速度收斂，但迭代複雜度很小。
本章主要提出一種基於梯度下降的最佳化演算法，並分析了其在凸函式上的效能。作者表示將考慮應用於機器學習之外的通用演算法，以及專用於機器學習的演算法（例如隨機梯度方法）。
第六章：區域性平均法
“線性”估計器：為每個觀測值分配權重函式，以便每個觀測值可以用相應的權重為標籤投票。
分割槽估計：將輸入空間分割成不重疊的單元，預測值是分段常數。
Nadaraya-Watson估計：又稱kernel regression，核迴歸，它為每個觀測值分配一個與其在輸入空間中的距離成比例的權重。
k近鄰：每個觀測值為其k個近鄰分配相等的權重。
一致性：所有這些方法都可以證明學習複雜非線性函式的收斂速度為，其中d是基本維度，並導致維度詛咒。
第七章：核方法（Kernel methods）
核與再生核定理：利用核函式和觀測值可以及時地對無限維線性模型進行學習。
R的d次冪上的核：這類模型包括多項式和經典Sobolev空間（具有平方可積偏導數的函式）。
演算法：凸最佳化演算法可以應用於理論保證和許多專門的發展，以避免計算核矩陣的二次複雜性。
規範模型的分析：當目標函式在相關函式空間中時，可以用與維數無關的速率進行學習。
錯誤規範模型的分析：如果目標不在RKHS中，且目標函式存在少量導數的最壞情況下，維數災難無法避免，但該方法可以適應任何數量的中間平滑。
嶺迴歸的sharp分析：對於平方損失，一個不必要的分析引起Rd中各種情況下的最佳速率。
第八章：稀疏方法（Sparse methods）
ℓ0 penalty：對於線性迴歸，如果最優預測器有k個非零值，那麼可以在平方損失中用ℓ0 penalty替換速率（這在計算上很難）。
ℓ1 penalty：在較少的假設下，可以得到一個與成比例的慢速率ℓ1 penalty和有效演算法，而快速率需要非常強大的設計矩陣的假設。
第九章：神經網路（Neural networks）
單隱層神經網路：使用簡單仿射函式與附加非線性的組合。
估計誤差：引數量不是估計誤差的驅動因素，各權重的範數都發揮著重要作用。
逼近性質和普適性：由於“ReLU”啟用函式對線性結構的適應性，逼近性質可以被表徵，並且優於核方法。
Part 3
專題
第10章：Implicit bias of gradient descent
梯度下降的隱式正則化：對於線性模型，當存在多個極小值時，梯度下降技術往往收斂到最小歐氏範數的一個。
雙下降：對於用梯度下降技術學習的非正則化模型，當範圍擴大，且引數量超過觀測值數時，測試誤差擴大，效能出現第二次下降。
兩層神經網路梯度下降的全域性收斂性：在沒有寬度的限制下，梯度下降對一個非凸問題具有全域性收斂性。
在本章主要介紹學習理論中的三個最新主題，它們都在一定程度上與“過度引數化”區域中的高維模型（如神經網路）有關，其中引數值大於觀測值。
第11章：Lower bounds on performance
統計下界：對於最小二乘迴歸，目標函式在某些特徵向量中是線性的，或者在R的d次冪上的Sobolev空間中是線性的，監督學習的最佳效能恰好是透過本書前面介紹的幾種演算法實現的。下界可以透過資訊理論或貝葉斯分析得到。
最佳化下界：針對第5章中的經典問題可以設計硬函式，證明基於梯度下降的線性組合的梯度演算法是最優的。
隨機梯度下降的下界：與 對於凸函式和為了µ-強凸問題是最優的。
對於凸函式，速率與成正比，用求解µ-strongly凸問題是最優的。
作者簡介
個人主頁：https：//www。di。ens。fr/~fbach/
Francis Bach是巴黎INRIA研究中心成員，自2011年起領導SIERRA專案團隊，該團隊隸屬於高等師範學院計算機科學系以及CNRS、ENS和INRIA的聯合團隊。
Francis Bach自2016年起擔任Ecole Normale Supérieure教授。此前，他就讀於加州大學伯克利分校，並獲得了計算機科學博士學位。博士畢業後，他與Michael Jordan教授合作，在巴黎礦業大學數學形態學小組工作兩年，後來加入INRIA/Ecole Normale Superieure/CNRS至2010年，2007年他主要負責WILLOW專案組，2009年至2014年負責ERC專案SIERRA，現在是負責ERC紅杉專案。2020年他當選為法國科學院院士。
Francis Bach對統計機器學習，特別是圖形模型、稀疏方法、基於核的學習、凸最佳化視覺和訊號處理等方向感興趣。相關研究成果的谷歌引用次數近五萬。
PDG下載：https：//www。di。ens。fr/~fbach/ltfp_book。pdf
由於微信公眾號試行亂序推送，您可能不再能準時收到AI科技評論的推送。為了第一時間收到AI科技評論的報道， 請將“AI科技評論”設為星標賬號，以及常點文末右下角的“在看”。
