Tag Archives: Lagrange 乘數法

Karush-Kuhn-Tucker (KKT) 條件

Posted on 02/07/2017 by ccjou

本文的閱讀等級：中級 在優化理論，Karush-Kuhn-Tucker (KKT) 條件是非線性規劃 (nonlinear programming) 最佳解的必要條件[1]。KKT 條件將 Lagrange 乘數法 (Lagrange multipliers) 所處理涉及束縛等式的約束優化問題推廣至不等式。在實際應用上，KKT 條件 (方程組) 一般不存在代數解，許多優化算法可供數值計算選用[2]。這篇短文從 Lagrange 乘數法推導 KKT 條件並舉一個簡單的例子說明解法。

Posted in 特別主題 | Tagged , , | 7 Comments

高斯混合模型與最大期望算法

Posted on 01/18/2017 by ccjou

本文的閱讀等級：高級 假設你知道一個連續型隨機向量 的機率密度函數 (以下簡稱密度函數) 受一組參數 制約。譬如，常態分布 (高斯分布) 的密度函數 受期望值 與共變異數矩陣 制約，常態分布的參數為 (見“多變量常態分布”)。為了估計機率模型的參數，你需要取得該機率分布的樣本。假設我們有一筆大小為 的樣本 ，這些數據點是獨立的，而且服從相同的機率分布 。最大似然估計 (maximum likelihood estimation) 是一種常用的參數估計法。對於給定的樣本 ，參數 的似然函數 (likelihood) 定義為 ， 也就是說似然函數是給定參數後，樣本的條件密度函數。在樣本 固定的情形下，我們將似然函數看作 的一個函數。顧名思義，最大似然估計的目標要找出 使得 有最大值： 。 對數 是一個單調遞增函數，可知 的最大值與 的最大值發生在同一個 。在實際應用時，我們通常考慮較易於計算的 。對於某些機率分布，最大似然估計很容易求得，譬如常態分布，計算 對 和 的偏導數並設為零，可得代數解 (見“多變量常態分布的最大似然估計”)。不過，對於一些形式較為複雜的機率分布，最大似然估計未必存在代數解，這時我們必須使用迭代法計算。

Posted in 機器學習 | Tagged , , , , , | 4 Comments

極小範數解

Posted on 05/21/2014 by ccjou

本文的閱讀等級：中級 令 為一個 階實矩陣。我們用 表示 的行空間 (column space)，即 。注意， 是向量空間 的一個子空間。對於任一 ，線性方程 必定存在解，但解集合只有兩種可能的情況：唯一解或無限多組解。在解集合中，有一個解最為特別，該特解位於 的列空間 (row space)，即 的行空間 ，並具有最小的2-範數 (歐氏範數，見“向量範數”)，稱為極小範數解 (minimum norm solution)，記為 。如果解集合僅有唯一解，則該解即為極小範數解。這篇短文介紹極小範數解的性質與表達式。

Posted in 線性代數專欄, 內積空間 | Tagged , , , , | 14 Comments

正交 Procrustes 問題

Posted on 11/21/2013 by ccjou

本文的閱讀等級：高級 普洛克路斯忒斯 (Procrustes) 是希臘神話中海神波塞頓 (Poseidon) 的兒子。他在雅典到埃萊夫西納 (Eleusis) 的神聖之路 (The Sacred Way) 上開設一間黑店，向路過的旅人謊稱店內設有一張適合所有人的鐵床。旅客投宿時，普洛克路斯忒斯將身高者截斷雙足，身矮者則強行拉長，使之與床的長短相同。從來沒有一個人的身長與鐵床的長度相同而免於凌遲，因為他暗地裡準備了兩張床[1]。後人於是以 Procrustean 表示「削足適履，殺頭便冠」，意思是將不同的長度、大小或屬性安裝到一個任意的標準。 正交 Procrustes 問題：給定兩個 階實矩陣 和 ，求一個 階實正交矩陣 ，，使得 具有最小值[2]，其中 是 Frobenius 範數。   正交 Procrustes 問題是一個最小平方矩陣近似問題，可以這麼解讀： 是旅人， 是鐵床，正交 Procrustean 變換 (包含旋轉和鏡射) 即為施予旅人的肢體酷刑。我們的問題是求出一酷刑使旅人變形後的身長與鐵床的長度最為吻合。以下討論限定於實矩陣。

Posted in 線性代數專欄, 二次型 | Tagged , , , , , , | 8 Comments

主成分分析

Posted on 04/15/2013 by ccjou

本文的閱讀等級：高級 美國作家梭羅 (Henry D. Thoreau) 在《湖濱散記》談到他的幽居生活時，說道[1]： 我們的生活消耗在瑣碎之中。一個老實的人除了十指之外，便不必有更大的數字了，頂多加上十個足趾，其餘不妨勉強一下。簡單，簡單，簡單啊！我說，最好你的事祇兩三件，不要一百件或一千件；不必一百萬一百萬地計算，半打不夠計算嗎？總之，賬目可以記在大拇指甲上就好了。 我們也許不能複製梭羅在瓦爾登湖 (Walden) 的簡單生活，但是我們永遠可以通過化繁為簡來改善現況。處於資訊爆炸的時代，我們不免要面對變數很多且樣本數很大的資料。在分析高維度 (變數很多) 數據時，降維 (dimension reduction) 常是一個必要的前處理工作。主成分分析 (principal components analysis，簡稱 PCA) 由英國統計學家皮爾生 (Karl Pearson) 於1901年提出[2]，是一種降低數據維度的有效技術。主成分分析的主要構想是分析共變異數矩陣 (covariance matrix) 的特徵性質 (見“共變異數矩陣與常態分布”)，以得出數據的主成分 (即特徵向量) 與它們的權值 (即特徵值)；透過保留低階主成分 (對應大特徵值)，捨棄高階主成分 (對應小特徵值)，達到減少數據集維度，同時保留最大數據集變異的目的。本文從線性代數觀點介紹主成分分析，並討論實際應用時可能遭遇的一些問題。

Posted in 機器學習 | Tagged , , , , , , , , , | 20 Comments

實對稱矩陣特徵值變化界定的典型問題

Posted on 10/19/2012 by ccjou

本文的閱讀等級：中級 線性代數所處理的最佳化問題可概分為兩大類：一是線性方程 的最小平方近似解問題，即求出 使得誤差平方 具有最小值。內積空間理論導出最佳解須滿足正規方程式 (normal equation) (見“ 從線性變換解釋最小平方近似”)。二是特徵分析推衍的二次型約束最佳化問題，即求單位向量 (unit vector) 使得 有最大值，其中 是實對稱矩陣。二次型 的極值產生條件是特徵方程式 ，極值大小則由 的特徵值決定 (見“二次型與正定矩陣”)。因為這個緣故，二次型約束最佳化也稱為實對稱矩陣的特徵值變化界定，下面我們討論兩個典型問題並說明完整的解法。   問題一 (取自 2012年台大資訊所碩士班入學試題)：令 為實數，且 ，求 的最大值。

Posted in 線性代數專欄, 二次型 | Tagged , , , , , | Leave a comment

Lagrange 乘數法

Posted on 05/30/2012 by ccjou

本文的閱讀等級：中級 約束最佳化 (constrained optimization) 是指在一個或多個束縛條件下，尋找一個多變數函數的極值 (極大值或極小值)。舉例來說，我們希望得到 的極小值，但前提是 與 必須滿足束縛條件 。最直截了當的作法是解出束縛條件，如此 可表示為 的函數，譬如 。將上式代入 可得單變數無約束目標函數 ，求導並設為零即得極值的必要條件 。這個方法的主要缺點在於束縛條件未必存在代數解，也就是說 無法寫成 的函數。此外，當變數的數量增多或有多個束縛條件時，縱使能夠得到代數解，無約束目標函數的表達式也可能相當複雜。與上述作法比較，拉格朗日乘數法 (method of Lagrange multipliers) 或稱未定乘數法 (undetermined multipliers) 不須解出束縛條件，因而保留了變數之間的對稱性。由於兼具簡單與典雅兩個優點，Lagrange 乘數法是目前最常被使用於約束最佳化問題的方法。令 Lagrangian 函數為 ， 其中 稱為 Lagrange 乘數。計算 對所有變數的偏導數並設為零： ， 這個方程組即為最佳解的必要條件。本文採用較富直覺的幾何觀點解說 Lagrange 乘數法的基本原理，預備知識包括正交補餘和正交投影 (見“正交補餘與投影定理”)。

Posted in 特別主題 | Tagged , , , , , | 9 Comments

答levinc417──關於約束二次型極值

Posted on 02/07/2012 by ccjou

網友levinc417留言： 設 是 中標準內積，且 ，。令 是 實方陣，且考慮 ，。假設 ，存在一正數 ，使得 ，對所有 滿足 。那麼我們可以說： 對所有 成立嗎？ Prove or disprove it. 找到一個反例： 且 。 這樣可以嗎？ 有誤解題目意思嗎？

Posted in 答讀者問, 二次型 | Tagged , | 2 Comments

仿射投影

Posted on 04/19/2011 by ccjou

本文的閱讀等級：中級 令 為一個有限維內積空間。考慮 的平移變換 ， 其中 是一個非零向量。平移變換 並非線性變換，而是一個仿射變換 (見“仿射變換”)。設 為 的一個子空間， 自原點平移 後所構成的集合稱為仿射空間 (affine space)，表示為 。 除非 ，否則 不包含零向量，因此 不是 的子空間。雖然如此，在仿射空間中仍可以實現正交投影，這篇短文解說如何將一般子空間投影轉換至仿射空間投影，另外並介紹一個基於最佳化理論的計算方法。(本文源於網友 Liang Dai 留言，以下的例子也是由他所提供。)

Posted in 線性代數專欄, 仿射幾何 | Tagged , , , , , | 4 Comments

二次型與正定矩陣

Posted on 10/21/2009 by ccjou

本文的閱讀等級：中級 令 為一個 階實矩陣， 為 維實向量，具有以下形式的實函數稱為二次型 (quadratic form)： 。

Posted in 線性代數專欄, 二次型 | Tagged , , , , , , , | 12 Comments