模式識別與機器學習第四講（附錄E、第2章序言）

01-28

關鍵詞：拉格朗日乘子法、KKT條件、密度估計、適定問題/不適定問題、參數分布/非參數分布。

題圖為雅各布·伯努利（Jacob Bernoulli，1654-1705），概率論的先驅者。著名的伯努利分布就是以他的名字命名的。

Appendix E. Lagrange Multipliers

在開始第二章前，我還是想先講一下拉格朗日乘子（Lagrange multiplier），又稱為待定乘子（undetermined multiplier）。這一方法在包括第二章在內的多個地方都有涉及。

拉格朗日乘子法可以用來找到在一個或多個約束條件下多元函數的駐點（stationary point）。

約束問題根據約束條件的不同可以分為兩類，我們首先考慮第一類問題。

考慮這樣一個問題：對於一個關於兩個變數 $x_{1}, x_{2}$ 的函數 $f(x_{1},x_{2})$ ，有一個約束條件 $g(x_{1},x_{2})=0$ ，要求找到 $f(x_{1},x_{2})$ 的最大值。

對於這個問題有兩種做法。

第一種比較初級的做法是我們可以嘗試解約束條件 $g(x_{1},x_{2})=0$ 來用一個函數 $x_{2}=h(x_{1})$ 表示兩個函數之間的關係。我們可以把這個函數代入 $f(x_{1},x_{2})$ ，通過對 $f(x_{1},x_{2})$ 關於 $x_{1}$ 求導來得到駐值 $x_{1}^{star }$ ，並且進一步得到 $x_{2}^{star}=h(x_{1}^{star })$ 。

這種做法有兩個問題。首先，我們可能找不到約束條件 $g(x_{1},x_{2})$ 的解析解，無法找到 $h(cdot)$ 使得 $x_{2}=h(x_{1})$ 。其次，這種做法對兩個變數區別對待，打破了兩個變數之間的對稱性。

另一種相對不那麼初級、更加優雅的做法就是拉格朗日乘子法。

我們主要從幾何的角度試圖給出一個直觀的解釋。對於一個 $D$ 維變數 $mathbf{x}=(x_{1},cdots,x_{D})$ ， $g(mathbf{x})=0$ 的幾何意義是 $D$ 維空間里一個 $D-1$ 維的曲面（surface）。

關於為什麼 $g(mathbf{x})$ 代表的曲面少了一個維度，這是因為對於 $D$ 個維度里任何一個維度，根據 $g(mathbf{x})=0$ ，我們都可以用剩下的 $D-1$ 個維度來表示它。

下圖中給出了一個三維空間里二維曲面（矩形）的例子。棕色曲面代表了約束曲面，紫色球體的表面可以理解為使得函數 $f(mathbf{x})$ 取值相等的點的集合，被稱為 $f(mathbf{x})$ 等於某一定值的等值面（level set）。紫色箭頭代表這個球可以不斷變大，隨著球半徑的增大，在球表面的點所取得的 $f(mathbf{x})$ 值也越來越大。

考慮約束曲面 $g(mathbf{x})$ 上的一點 $mathbf{x}$ 以及它附近的曲面上另一點 $mathbf{x}+mathbf{epsilon}$ 。在 $mathbf{x}$ 點附近進行泰勒展開（Taylor expansion）可以得到 $g(mathbf{x}+epsilon)simeq g(mathbf{x})+epsilon^{T} nabla g(mathbf{x})$ 。由於 $mathbf{x}, mathbf{x}+epsilon$ 都在曲面上因此 $g(mathbf{x})=0, g(mathbf{x}+epsilon)=0$ ， $epsilon^{T} nabla g(mathbf{x})simeq0$ 。 $lim_{||epsilon||rightarrow 0}epsilon^{T} nabla g(mathbf{x})=0$ ，因此 $nabla g(mathbf{x})$ 正交（orthogonal）於 $epsilon$ 。由 $mathbf{x}, mathbf{x}+epsilon$ 均在曲面 $g(mathbf{x})=0$ 上可知 $epsilon$ 平行於曲面 $g(mathbf{x})=0$ ，因此 $nabla g(x)$ 正交於曲面 $g(mathbf{x})=0$ 。在上圖的例子中我們可以看到棕色箭頭正交於棕色平面。

我們想要在約束平面 $g(mathbf{x})$ 上找到一點 $mathbf{x}^{star}$ 使得 $f(mathbf{x})$ 的值最大化。滿足這一條件的點 $mathbf{x}^{star}$ 必定有 $nabla f(mathbf{x}^{star})$ 正交於約束平面 $g(mathbf{x})$ 。否則我們可以從這一點出發在約束平面上找到另一點使得得到的 $f(mathbf{x})$ 值更大。

由於 $nabla g(mathbf{x}^{star}), nabla f(mathbf{x}^{star})$ 均正交於約束平面，因此它們互相平行於對方。所以存在標量 $lambda neq 0$ 使得 $nabla f(mathbf{x}) + lambda nabla g(mathbf{x}) = 0$ 。 $lambda$ 被稱為拉格朗日乘子。如果在 $mathbf{x}^{star}$ 我們能取到 $f(mathbf{x})$ 的最大值，則必然有 $nabla f(mathbf{x}^{star})+lambda nabla g(mathbf{x}^{star})=0$ 。

為了方便起見，我們通常會引入拉格朗日函數（Langrange function）： $L(mathbf{x},lambda)equiv f(mathbf{x})+lambda g(mathbf{x})$ 。這個函數妙的地方在於 $mathbf{x}^{star}$ 所需要滿足的條件都可以用拉格朗日函數來表達，即① $nabla_{mathbf{x}} L(mathbf{x}, lambda)=0$ ，② $frac{partial L}{partial lambda}=0$ 。

如果我們需要的話，我們可以找到 $L(mathbf{x}, lambda)$ 同時關於 $mathbf{x}$ 和 $lambda$ 的駐點。在拉格朗日乘子法里，我們通常並不在意 $lambda$ 的值，這就是待定乘子法里「待定」二字的來源。

書中給出了一個拉格朗日乘子法的應用例子，寫得很清楚了，在此不做贅述。

在上面這個問題中約束曲面 $g(mathbf{x})$ 恆等於 $0$ ，不難發現對於所有的 $g_{1}(mathbf{x})=c$ 這樣形式的問題我們都可以通過 $g_{2}(mathbf{x})=g_{1}(mathbf{x})-c=0$ 把它們變成同一類約束條件。這類約束條件被稱為等式約束（equality constraint）。

另一類約束條件為不等式約束（inequality constraint），即 $g(mathbf{x})geq 0$ 。

根據具體的駐點 $mathbf{x}^{star}$ 有 $g(mathbf{x}^{star})>0$ 和 $g(mathbf{x}^{star})=0$ 兩種情況。兩種情況導致了兩種可能的解。

第一種情況下，我們稱呼約束條件為不活躍的（inactive）。在這種情況下我們只需要 $nabla f(x) = 0$ 。同樣我們可以用拉格朗日函數來表達需要滿足的條件，只需要令 $lambda=0$ 。

第二種情況下，我們稱呼約束條件為活躍的（active）。這種情況下問題類似於等式約束，我們可以用 $lambdaneq 0$ 的拉格朗日函數來表達需要滿足的條件。然而這種情況下拉格朗日乘子的符號變得非常重要。 $f(mathbf{x})$ 在 $g(mathbf{x})=0$ 區域的最大值只有在梯度 $nabla f(mathbf{x})$ 指離 $g(mathbf{x})>0$ 所在區域情況下（見下圖）才能得到，否則我們總能在 $g(mathbf{x})>0$ 區域找到一個 $mathbf{x}$ 使得 $f(mathbf{x})>f(mathbf{x}^{star})$ 。因為這樣的原因， $nabla f(mathbf{x})=- lambdanabla g(mathbf{x}), lambda > 0$ 。所以我們可以用 $lambda > 0$ 情況下的拉格朗日函數來表示需要滿足的條件。

不管約束條件是否活躍，我們都有 $lambda g(mathbf{x})=0$ 。因此我們可以把原問題（在滿足 $g(mathbf{x})geq 0$ 的情況下找到 $f(mathbf{x})$ 的最大值）轉換成如下的一個新問題：

在滿足 $g(mathbf{x})geq 0, lambda geq 0, lambda g(mathbf{x})=0$ 的情況下找到拉格朗日函數的最大值。

上述約束條件被稱為KKT條件（Karush-Kuhn-Tucker conditions）。

如果我們要做的是在滿足不等式約束 $g(mathbf{x})geq 0$ 的情況下找到 $f(mathbf{x})$ 的最小值，那麼過程是一樣的，只是問題變成了在滿足KKT條件的情況下找到拉格朗日函數的最小值。

上述討論都是基於單個約束條件，我們可以把拉格朗日乘子法用於多個約束條件。

假設我們要在滿足等式約束 $g_{j}(mathbf{x})=0, j=1,cdots,J$ 以及不等式約束 $h_{k}(mathbf{x})geq 0,k=1,cdots,K$ 的情況下找到 $f(mathbf{x})$ 的最大值，那麼我們可以把問題轉化為：在滿足

$mu_{k}geq 0, mu_{k}h_{k}(mathbf{x})=0, k=1,cdots,K$

的情況下優化拉格朗日函數

$L(mathbf{x},{lambda_{j}}, {mu_{k}})=f(mathbf{x})+sum_{j=1}^{J}lambda_{j}g_{j}(mathbf{x})+sum_{k=1}^{K}mu_{k}h_{k}(mathbf{x})$ 。

我們也可以把拉格朗日乘子法的應用拓展到泛函導數約束的情況，在此不做討論。

Nocedal和Wright寫的《數值優化》（Numerical Optimization）一書中對拉格朗日乘子法做了更加詳細的介紹。

2. Probability Distributions

上圖描繪了許多不同的概率分布以及它們之間的關係。在這一章節里我們會介紹伯努利分布（Bernoulli distribution）、貝塔分布（beta distribution）、多項分布（multinomial distribution）、狄利克雷分布（Dirichlet distribution），並且更加深入地學習高斯分布。

伴隨重要統計概念的引入，我們希望能深入了解這些分布的動機和性以及分布與分布之間的聯繫。

這些概率分布的一個重要作用是密度估計（density estimation）：給定一個集合的數據點 ${mathbf{x}_{1}, cdots, mathbf{x}_{N}}$ ，我們想要對於隨機變數 $mathbf{x}$ 的概率分布 $p(mathbf{x})$ 進行建模。為了方便起見，如沒有另行聲明，我們假設數據點 $mathbf{x}_{1}, cdots, mathbf{x}_{N}$ 服從獨立一致分布。

數學家阿達馬（Jacques Solomon Hadamard，他和另一個數學家普森在1896年分別獨立給出了一個素數定理的證明，對黎曼猜想有關的工作做出了突出貢獻。傳說證明了黎曼猜想的人能獲得永生。阿達馬活了97歲，普森活了95歲。）提出對物理現象的數學模型應該具備以下三個特點：

存在一個解（存在性）
解是唯一的（唯一性）
解的行為連續依賴於初始條件（穩定性）

滿足上述三個條件的問題被稱為適定問題（well-posed problem），否則被稱為不適定問題（ill-posed problem）。

我們需要注意密度估計這個問題在根本上是不適定問題。對於有限數據點的集合 ${mathbf{x}_{1}, cdots, mathbf{x}_{N}}$ ，有無限的概率分布可能會產生這個數據集。事實上對於一個概率分布來說，只要它在 $mathbf{x}_{1}, cdots, mathbf{x}_{N}$ 這 $N$ 個數據點的概率不為 $0$ ，就可能是產生數據點的概率分布。

當我們預先假設產生數據點的概率分布為高斯分布、均勻分布、伯努利分布等等的時候，我們所做的其實無異於模型選擇。

我們可以把概率分布分為兩類：參數分布（parametric distribution）和非參數分布（nonparametric distribution）。

參數分布是指由少量自適應參數決定的概率分布。如高斯分布完全由期望和方差來決定。否則就叫費參數分布。

對於如何決定參數分布的參數我們有頻率論和貝葉斯論兩種截然不同的途徑。

從頻率論的角度來說我們可以根據數據集優化目標來決定參數的具體值。在第二講里對於似然函數最大化的極大似然估計就是這樣一個例子。

從貝葉斯論的角度來說我們先給出一個參數的先驗分布，然後基於觀察到的數據集通過貝葉斯公式做後驗更新。

參數分布的局限性在於它假設了一個分布的具體泛函形式（如假設數據分布為一個高斯分布），而在某些應用里這可能是不適合的。我們因此有時候會用到非參數分布，做非參數估計。

在非參數分布里分布的形式通常依賴於數據集的大小。我們用的模型里仍然包含參數，但它們不再是具體某一概率分布的參數（如高斯分布的期望和方差），而被用於控制模型的複雜度（complexity）。在2.5里我們會對非參數估計做進一步深入的討論。