各种向量与矩阵的范数的意义

1、向量和矩阵的范数向量和矩阵的范数马玉玲马玉玲2017年年03月月08日日1Outline1.相关概念相关概念学习、误差和目标函数学习、误差和目标函数2.范数概念范数概念3.向量的范数及含义向量的范数及含义4.矩阵的范数及含义矩阵的范数及含义2Outline1.相关概念相关概念学习、误差和目标函数学习、误差和目标函数2.范数概念范数概念3.向量的范数及含义向量的范数及含义4.矩阵的范数及含义矩阵的范数及含义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利用经验，改善执行某任务时的系统性能。Basis knowledge相关概念相关概念学习学习5Basis knowledge相关概念相关概念学习学习6Basis knowledge相关概念相关概念学习学习备注：表来自周老师西瓜书课件7Basis knowledge相关概念相关概念学习学习函数函数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相关概念相关概念误差误差假定数据集假定数据集DThe value of is dependant on the task 11相关概念相关概念目标

4、函数目标函数 一般来说，监督学习可以看做最小化下面的目标函数：误差项误差项正则化项正则化项正则化项可以约束模型的特性。这样就可以将人对这个模型的先验知识融入到模型的学习当中。范数范数是正则化是正则化的常用方法的常用方法12Outline1.相关概念相关概念误差和目标函数误差和目标函数2.范数概念范数概念3.向量的范数及含义向量的范数及含义4.矩阵的范数及含义矩阵的范数及含义13范数的概念范数的概念范数的目的：对向量及矩阵的“大小”进行度量14向量的范数向量的范数XRn 为一实向量，为一实向量，X的范式定义如下：的范式定义如下：L1-normL2-normL-norm统称为统称为p pL0范数：

5、指向量中范数：指向量中非非0的元素的个数的元素的个数 X=-1 2 -2 |X|0= 3|X|1= 5|X|= 2|X|2= 315范数的含义范数的含义L0范数：指向量中非范数：指向量中非0的元素的个数的元素的个数最小化最小化L0范数范数数据稀疏的好处：1. 存储成本低2. 自动实现特征选择(Feature Selection)3. 可解释性强(Interpretability)应用：病因分析应用：病因分析但是，L0范数很难很难优化求解，是一个NP-Hard问题。稀疏稀疏16范数的含义范数的含义L1范数：范数：L1范数是L0范数的最优凸近似，而且它比L0范数要容易优化求解。所以L1范数被称为“

6、稀疏规则算子”（Lasso ）taxicab Norm，也叫Manhattan Norm稀疏编码特征选择压缩感知17范数的含义（范数的含义（ 续续）L2范数：又称“岭回归”（Ridge Regression），“权值衰减（weight decay）”， Euclidean Norm最小化L2范数，可以使得X的元素值都很小，大都接近于018范数的含义（范数的含义（L2-norm）L L2 2范数的好处：范数的好处： 1. 1.改善改善“过拟合过拟合（overfittingoverfitting）” 欠拟合欠拟合underfitting：训练集上误差很大，：训练集上误差很大，即模型即模型不能很好地

7、不能很好地拟拟合合已有已有数据；数据；关于关于“过拟合过拟合”： 在数学上称为“病态”（ill-condition):即函数的输入改变一点点，输出却改变非常大。 过拟合过拟合（overfitting）：模型：模型很好地很好地拟合训拟合训练数据，然而在练数据，然而在新样新样本本上表现却很差。上表现却很差。 L2范数限制了参数都很小，实际上就限制了多项式各分量的影响很小，一定程度上避免了模型出现“病态”的情况。 2. 2.利于利于优化优化19范数的含义（范数的含义（L2-norm）L L2 2范数的好处：范数的好处： 1. 1.改善改善“过拟合过拟合（overfittingoverfitting）

8、” 2. 2.利于利于优化优化机器学习中有时候损失函数是非凸的，例如：神经网络。采用梯度下降之类的优化方法时，容易卡住（Stuck in），导致很差的解。非凸的损失函数加入L2范数后20知识扩展知识扩展稀疏性分析：稀疏性分析：模型空间限制在w的一个L-ball 中。在(w1, w2)平面上可以画出目标函数的等高线，而约束条件则成为平面上半径为C的一个 norm ball 。等高线与 norm ball 首次相交首次相交的地方就是最优解。与L2范数相比，L1范数更有可能得到值为0的解，所以导致稀疏。21优化求解：优化求解： 由于L1范数并没有平滑的函数（non-smooth）表示，起初L1最优化

9、问题解决起来非常困难，但随着计算机技术的发展，目前已有很多凸优化算法(例如：线性规划/非线性规划等）使得L1最优化。L1范数：范数：22优化求解：优化求解：L1范数：范数：虽然，L1范数并没有平滑的函数（non-smooth）表示，但比L2范数更容易找到最优解。23优化求解：优化求解：L1范数：范数：目前，已经有很多工具箱，例如 l1-magic, SparseLab, ISAL1,24优化求解：优化求解：因为L2-范数本身具有平滑（smooth）的属性，找到单一的最优解比较困难。L2范数：范数：25Basis knowledgeL2范数最小二乘优化：范数最小二乘优化：xY=*1()TTXXX

10、yw加入一个加入一个L2范数范数|w|2X y伪逆26优化求解：优化求解：在不能求得解析解的情况下，具体分析目标函数的性质（凸否？连续否？光滑否？）还可以使用凸优化方法进行求解，例如：牛顿法、最速下降法、共轭梯度法、高斯牛顿法等等，大规模数据情况下的随机梯度下降（SGD）, 交替方向乘子交替方向乘子法法(ADMM)L2范数：范数：红色：牛顿法绿色：梯度下降法27Outline1.相关概念相关概念误差和目标函数误差和目标函数2.范数概念范数概念3.向量的范数及含义向量的范数及含义4.矩阵的范数及含义矩阵的范数及含义28矩阵的范数矩阵的范数29矩阵的范数（续矩阵的范数（续）设设A A为为n n行行

11、n n列的矩阵，矩阵的范数定义如下：列的矩阵，矩阵的范数定义如下：列范数列范数行范数行范数谱范数谱范数56530举例：举例：31矩阵的范数（续矩阵的范数（续）设设A A为为n n行行n n列的矩阵，矩阵的范数定义如下：列的矩阵，矩阵的范数定义如下：谱范数（不好优化）谱范数（不好优化）以上为数学上范数的定义，只有F-范数在“机器学习”中常用，此处1-范数在机器学习中一般称为“l1范数”。矩阵范数最好参考相关论文中的定义。常用常用32矩阵的范数矩阵的范数- -机器学习领域机器学习领域常用范数：常用范数：按列向量按列向量先求先求2-范数，范数，再求再求1-范数范数矩阵矩阵先扩展为先扩展为向量，再求范

12、数向量，再求范数 njmiijaA112/122, 1)|)|(|njmiijnjjaaA112/12121 , 2)|(|minjppijPpaAvecA11/1)|(|)(|英文为英文为Nuclear norm，指矩阵，指矩阵奇奇异值异值的和（迹的和（迹trace），故又称），故又称为为trace-normtrA|minjijFaAF112/12)(|范数：,min1*)(trace|nmiiTAAA核范数：按列向量按列向量先求先求1-范数，范数，再求再求2-范数范数33矩阵范数的含义矩阵范数的含义 最小化矩阵的F范数，会使得矩阵的每个元素都很小，接近于0|A-B|F的含义？的含义？|A-

13、B|F可度量可度量A，B之间的差异，之间的差异，最小化最小化可使得两者可使得两者尽可能的相等。尽可能的相等。34举例举例F范数应用范数应用 35矩阵范数的含义（续矩阵范数的含义（续）核范数核范数|W|W|* * ：指：指矩阵奇异值矩阵奇异值的和，英文为的和，英文为Nuclear norm最小化核范数可以导致矩阵最小化核范数可以导致矩阵低秩（低秩（Low-RankLow-Rank）。http:/ 如果如果X X是一个是一个m m行行n n列的数值矩阵，列的数值矩阵，rank(X)rank(X)是是X X的秩，的秩，假如假如rank (X)rank (X)远小于远小于m m和和n n，则我们称，则

14、我们称X X是是低秩矩阵低秩矩阵。冗余信息冗余信息矩阵的矩阵的秩秩：矩阵的：矩阵的行列之间的相关性行列之间的相关性的度量。如果矩的度量。如果矩阵的各行或列是阵的各行或列是线性无关线性无关的，矩阵就是的，矩阵就是满秩的满秩的，也就，也就是秩等于行数。是秩等于行数。http:/ Completion)：例如：例如-推荐系统推荐系统2）鲁棒）鲁棒PCA3）背景建模）背景建模4）变换不变低秩纹理（）变换不变低秩纹理（TILT）应用举例核范数稀疏噪声稀疏噪声低秩结构低秩结构信息信息鲁棒PCA:40矩阵范数的含义矩阵范数的含义/wiki/Matrix_norm

15、p=1p=1时，为矩阵的时，为矩阵的1-1-范数，范数，最小化最小化|A|A|1 1范数能让范数能让矩阵矩阵A A元素元素稀疏稀疏minjppijPpaAvecA11/1)|(|)(|p=2p=2时，为矩阵的时，为矩阵的2-2-范数，即范数，即F F范数范数稀疏矩阵的优点： 计算速度更快 存储成本低 可解释性强（例如：文本分类中，可知哪些词对类别起重要作用）41矩阵范数的含义矩阵范数的含义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范数能让矩阵范数能让矩阵A A不同行之间（列向不同行之间（列向量）量）稀疏稀疏Group LassonjmiijnjjaaA112/12121 , 2)|(|c1c2cn221112121.cmaaa42矩阵范数的含义矩阵范数的含义LassoGroup LassoHierarchical Lasso文本分类中的应用：找出关键词找出关键句子找出关键段43矩阵范数的含义矩阵范数的含义Kong D, Fujimaki R, Liu J, et al. Exclusive feature learning on a