各種向量與矩陣的范數(shù)的意義

1、向量和矩陣的范數(shù)向量和矩陣的范數(shù)馬玉玲馬玉玲2017年年03月月08日日1Outline1.相關概念相關概念學習、誤差和目標函數(shù)學習、誤差和目標函數(shù)2.范數(shù)概念范數(shù)概念3.向量的范數(shù)及含義向量的范數(shù)及含義4.矩陣的范數(shù)及含義矩陣的范數(shù)及含義2Outline1.相關概念相關概念學習、誤差和目標函數(shù)學習、誤差和目標函數(shù)2.范數(shù)概念范數(shù)概念3.向量的范數(shù)及含義向量的范數(shù)及含義4.矩陣的范數(shù)及含義矩陣的范數(shù)及含義3Basis knowledge相關概念相關概念學習學習 A computer program is said to learn from experience E with respect

2、to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E.4利用經驗，改善執(zhí)行某任務時的系統(tǒng)性能。Basis knowledge相關概念相關概念學習學習5Basis knowledge相關概念相關概念學習學習6Basis knowledge相關概念相關概念學習學習備注：表來自周老師西瓜書課件7Basis knowledge相關概念相關概念學習學習函數(shù)函數(shù)y=f(x)備注：本頁ppt來自周老師西

3、瓜書課件8Basis knowledge相關概念相關概念學習學習線性模型y=wTx+b備注：表來自周老師西瓜書課件x(1)x(2)x(3)插值法9Basis knowledge相關概念相關概念學習學習備注：表來自周老師西瓜書課件xY=10Basis knowledgeEmpirical error:Generalization error:Error parameter:Predict wronglyDI(a): 1 if a=true 0 else相關概念相關概念誤差誤差假定數(shù)據集假定數(shù)據集DThe value of is dependant on the task 11相關概念相關概念目標

4、函數(shù)目標函數(shù) 一般來說，監(jiān)督學習可以看做最小化下面的目標函數(shù)：誤差項誤差項正則化項正則化項正則化項可以約束模型的特性。這樣就可以將人對這個模型的先驗知識融入到模型的學習當中。范數(shù)范數(shù)是正則化是正則化的常用方法的常用方法12Outline1.相關概念相關概念誤差和目標函數(shù)誤差和目標函數(shù)2.范數(shù)概念范數(shù)概念3.向量的范數(shù)及含義向量的范數(shù)及含義4.矩陣的范數(shù)及含義矩陣的范數(shù)及含義13范數(shù)的概念范數(shù)的概念范數(shù)的目的：對向量及矩陣的“大小”進行度量14向量的范數(shù)向量的范數(shù)XRn 為一實向量，為一實向量，X的范式定義如下：的范式定義如下：L1-normL2-normL-norm統(tǒng)稱為統(tǒng)稱為p pL0范數(shù)：

5、指向量中范數(shù)：指向量中非非0的元素的個數(shù)的元素的個數(shù) X=-1 2 -2 |X|0= 3|X|1= 5|X|= 2|X|2= 315范數(shù)的含義范數(shù)的含義L0范數(shù)：指向量中非范數(shù)：指向量中非0的元素的個數(shù)的元素的個數(shù)最小化最小化L0范數(shù)范數(shù)數(shù)據稀疏的好處：1. 存儲成本低2. 自動實現(xiàn)特征選擇(Feature Selection)3. 可解釋性強(Interpretability)應用：病因分析應用：病因分析但是，L0范數(shù)很難很難優(yōu)化求解，是一個NP-Hard問題。稀疏稀疏16范數(shù)的含義范數(shù)的含義L1范數(shù)：范數(shù)：L1范數(shù)是L0范數(shù)的最優(yōu)凸近似，而且它比L0范數(shù)要容易優(yōu)化求解。所以L1范數(shù)被稱為“

6、稀疏規(guī)則算子”（Lasso ）taxicab Norm，也叫Manhattan Norm稀疏編碼特征選擇壓縮感知17范數(shù)的含義（范數(shù)的含義（ 續(xù)續(xù)）L2范數(shù)：又稱“嶺回歸”（Ridge Regression），“權值衰減（weight decay）”， Euclidean Norm最小化L2范數(shù)，可以使得X的元素值都很小，大都接近于018范數(shù)的含義（范數(shù)的含義（L2-norm）L L2 2范數(shù)的好處：范數(shù)的好處： 1. 1.改善改善“過擬合過擬合（overfittingoverfitting）” 欠擬合欠擬合underfitting：訓練集上誤差很大，：訓練集上誤差很大，即模型即模型不能很好地

7、不能很好地擬擬合合已有已有數(shù)據；數(shù)據；關于關于“過擬合過擬合”： 在數(shù)學上稱為“病態(tài)”（ill-condition):即函數(shù)的輸入改變一點點，輸出卻改變非常大。 過擬合過擬合（overfitting）：模型：模型很好地很好地擬合訓擬合訓練數(shù)據，然而在練數(shù)據，然而在新樣新樣本本上表現(xiàn)卻很差。上表現(xiàn)卻很差。 L2范數(shù)限制了參數(shù)都很小，實際上就限制了多項式各分量的影響很小，一定程度上避免了模型出現(xiàn)“病態(tài)”的情況。 2. 2.利于利于優(yōu)化優(yōu)化19范數(shù)的含義（范數(shù)的含義（L2-norm）L L2 2范數(shù)的好處：范數(shù)的好處： 1. 1.改善改善“過擬合過擬合（overfittingoverfitting）

8、” 2. 2.利于利于優(yōu)化優(yōu)化機器學習中有時候損失函數(shù)是非凸的，例如：神經網絡。采用梯度下降之類的優(yōu)化方法時，容易卡?。⊿tuck in），導致很差的解。非凸的損失函數(shù)加入L2范數(shù)后20知識擴展知識擴展稀疏性分析：稀疏性分析：模型空間限制在w的一個L-ball 中。在(w1, w2)平面上可以畫出目標函數(shù)的等高線，而約束條件則成為平面上半徑為C的一個 norm ball 。等高線與 norm ball 首次相交首次相交的地方就是最優(yōu)解。與L2范數(shù)相比，L1范數(shù)更有可能得到值為0的解，所以導致稀疏。21優(yōu)化求解：優(yōu)化求解： 由于L1范數(shù)并沒有平滑的函數(shù)（non-smooth）表示，起初L1最優(yōu)化

9、問題解決起來非常困難，但隨著計算機技術的發(fā)展，目前已有很多凸優(yōu)化算法(例如：線性規(guī)劃/非線性規(guī)劃等）使得L1最優(yōu)化。L1范數(shù)：范數(shù)：22優(yōu)化求解：優(yōu)化求解：L1范數(shù)：范數(shù)：雖然，L1范數(shù)并沒有平滑的函數(shù)（non-smooth）表示，但比L2范數(shù)更容易找到最優(yōu)解。23優(yōu)化求解：優(yōu)化求解：L1范數(shù)：范數(shù)：目前，已經有很多工具箱，例如 l1-magic, SparseLab, ISAL1,24優(yōu)化求解：優(yōu)化求解：因為L2-范數(shù)本身具有平滑（smooth）的屬性，找到單一的最優(yōu)解比較困難。L2范數(shù)：范數(shù)：25Basis knowledgeL2范數(shù)最小二乘優(yōu)化：范數(shù)最小二乘優(yōu)化：xY=*1()TTXXX

10、yw加入一個加入一個L2范數(shù)范數(shù)|w|2X y偽逆26優(yōu)化求解：優(yōu)化求解：在不能求得解析解的情況下，具體分析目標函數(shù)的性質（凸否？連續(xù)否？光滑否？）還可以使用凸優(yōu)化方法進行求解，例如：牛頓法、最速下降法、共軛梯度法、高斯牛頓法等等，大規(guī)模數(shù)據情況下的隨機梯度下降（SGD）, 交替方向乘子交替方向乘子法法(ADMM)L2范數(shù)：范數(shù)：紅色：牛頓法綠色：梯度下降法27Outline1.相關概念相關概念誤差和目標函數(shù)誤差和目標函數(shù)2.范數(shù)概念范數(shù)概念3.向量的范數(shù)及含義向量的范數(shù)及含義4.矩陣的范數(shù)及含義矩陣的范數(shù)及含義28矩陣的范數(shù)矩陣的范數(shù)29矩陣的范數(shù)（續(xù)矩陣的范數(shù)（續(xù)）設設A A為為n n行行

11、n n列的矩陣，矩陣的范數(shù)定義如下：列的矩陣，矩陣的范數(shù)定義如下：列范數(shù)列范數(shù)行范數(shù)行范數(shù)譜范數(shù)譜范數(shù)56530舉例：舉例：31矩陣的范數(shù)（續(xù)矩陣的范數(shù)（續(xù)）設設A A為為n n行行n n列的矩陣，矩陣的范數(shù)定義如下：列的矩陣，矩陣的范數(shù)定義如下：譜范數(shù)（不好優(yōu)化）譜范數(shù)（不好優(yōu)化）以上為數(shù)學上范數(shù)的定義，只有F-范數(shù)在“機器學習”中常用，此處1-范數(shù)在機器學習中一般稱為“l(fā)1范數(shù)”。矩陣范數(shù)最好參考相關論文中的定義。常用常用32矩陣的范數(shù)矩陣的范數(shù)- -機器學習領域機器學習領域常用范數(shù)：常用范數(shù)：按列向量按列向量先求先求2-范數(shù)，范數(shù)，再求再求1-范數(shù)范數(shù)矩陣矩陣先擴展為先擴展為向量，再求范

12、數(shù)向量，再求范數(shù) njmiijaA112/122, 1)|)|(|njmiijnjjaaA112/12121 , 2)|(|minjppijPpaAvecA11/1)|(|)(|英文為英文為Nuclear norm，指矩陣，指矩陣奇奇異值異值的和（跡的和（跡trace），故又稱），故又稱為為trace-normtrA|minjijFaAF112/12)(|范數(shù)：,min1*)(trace|nmiiTAAA核范數(shù)：按列向量按列向量先求先求1-范數(shù)，范數(shù)，再求再求2-范數(shù)范數(shù)33矩陣范數(shù)的含義矩陣范數(shù)的含義 最小化矩陣的F范數(shù)，會使得矩陣的每個元素都很小，接近于0|A-B|F的含義？的含義？|A-

13、B|F可度量可度量A，B之間的差異，之間的差異，最小化最小化可使得兩者可使得兩者盡可能的相等。盡可能的相等。34舉例舉例F范數(shù)應用范數(shù)應用 35矩陣范數(shù)的含義（續(xù)矩陣范數(shù)的含義（續(xù)）核范數(shù)核范數(shù)|W|W|* * ：指：指矩陣奇異值矩陣奇異值的和，英文為的和，英文為Nuclear norm最小化核范數(shù)可以導致矩陣最小化核范數(shù)可以導致矩陣低秩（低秩（Low-RankLow-Rank）。http:/ 如果如果X X是一個是一個m m行行n n列的數(shù)值矩陣，列的數(shù)值矩陣，rank(X)rank(X)是是X X的秩，的秩，假如假如rank (X)rank (X)遠小于遠小于m m和和n n，則我們稱，則

14、我們稱X X是是低秩矩陣低秩矩陣。冗余信息冗余信息矩陣的矩陣的秩秩：矩陣的：矩陣的行列之間的相關性行列之間的相關性的度量。如果矩的度量。如果矩陣的各行或列是陣的各行或列是線性無關線性無關的，矩陣就是的，矩陣就是滿秩的滿秩的，也就，也就是秩等于行數(shù)。是秩等于行數(shù)。http:/ Completion)：例如：例如-推薦系統(tǒng)推薦系統(tǒng)2）魯棒）魯棒PCA3）背景建模）背景建模4）變換不變低秩紋理（）變換不變低秩紋理（TILT）應用舉例核范數(shù)稀疏噪聲稀疏噪聲低秩結構低秩結構信息信息魯棒PCA:40矩陣范數(shù)的含義矩陣范數(shù)的含義/wiki/Matrix_norm

15、p=1p=1時，為矩陣的時，為矩陣的1-1-范數(shù)，范數(shù)，最小化最小化|A|A|1 1范數(shù)能讓范數(shù)能讓矩陣矩陣A A元素元素稀疏稀疏minjppijPpaAvecA11/1)|(|)(|p=2p=2時，為矩陣的時，為矩陣的2-2-范數(shù)，即范數(shù)，即F F范數(shù)范數(shù)稀疏矩陣的優(yōu)點： 計算速度更快 存儲成本低 可解釋性強（例如：文本分類中，可知哪些詞對類別起重要作用）41矩陣范數(shù)的含義矩陣范數(shù)的含義Kong D, Fujimaki R, Liu J, et al. Exclusive feature learning on arbitrary structures via l1,2-normJ. Adv

16、ances in Neural Information Processing Systems, 2014, 2:1655-1663.最小化最小化|A|A|2,12,1范數(shù)能讓矩陣范數(shù)能讓矩陣A A不同行之間（列向不同行之間（列向量）量）稀疏稀疏Group LassonjmiijnjjaaA112/12121 , 2)|(|c1c2cn221112121.cmaaa42矩陣范數(shù)的含義矩陣范數(shù)的含義LassoGroup LassoHierarchical Lasso文本分類中的應用：找出關鍵詞找出關鍵句子找出關鍵段43矩陣范數(shù)的含義矩陣范數(shù)的含義Kong D, Fujimaki R, Liu J, et al. Exclusive feature learning on a