各种向量和矩阵的范数的意义.ppt

向量和矩阵的范数,马玉玲2017年03月08日,1,Outline,1.相关概念学习、误差和目标函数2.范数概念3.向量的范数及含义4.矩阵的范数及含义,2,Outline,1.相关概念学习、误差和目标函数2.范数概念3.向量的范数及含义4.矩阵的范数及含义,3,Basisknowledge,相关概念学习,AcomputerprogramissaidtolearnfromexperienceEwithrespecttosomeclassoftasksTandperformancemeasureP,ifitsperformanceattasksinT,asmeasuredbyP,improveswithexperienceE.,4,利用经验，改善执行某任务时的系统性能。,Basisknowledge,相关概念学习,5,Basisknowledge,相关概念学习,6,Basisknowledge,相关概念学习,备注：表来自周老师西瓜书课件,7,Basisknowledge,相关概念学习,函数y=f(x),备注：本页ppt来自周老师西瓜书课件,8,Basisknowledge,相关概念学习,线性模型y=wTx+b,备注：表来自周老师西瓜书课件,x(1),x(2),x(3),插值法,9,Basisknowledge,相关概念学习,备注：表来自周老师西瓜书课件,10,Basisknowledge,Empiricalerror:Generalizationerror:Errorparameter:,Predictwrongly,D,I(a):1ifa=true0else,相关概念误差,假定数据集D,Thevalueofisdependantonthetask,11,相关概念目标函数,一般来说，监督学习可以看做最小化下面的目标函数：,误差项,正则化项,正则化项可以约束模型的特性。这样就可以将人对这个模型的先验知识融入到模型的学习当中。,范数是正则化的常用方法,12,Outline,1.相关概念误差和目标函数2.范数概念3.向量的范数及含义4.矩阵的范数及含义,13,范数的概念,范数的目的：对向量及矩阵的“大小”进行度量,14,向量的范数,XRn为一实向量，X的范式定义如下：,L1-norm,L2-norm,L-norm,统称为p,L0范数：指向量中非0的元素的个数,X=-12-2,|X|0=3,|X|1=5,|X|=2,|X|2=3,15,范数的含义,L0范数：指向量中非0的元素的个数,最小化L0范数,数据稀疏的好处：存储成本低2.自动实现特征选择(FeatureSelection)3.可解释性强(Interpretability),应用：病因分析,但是，L0范数很难优化求解，是一个NP-Hard问题。,稀疏,16,范数的含义,L1范数：,L1范数是L0范数的最优凸近似，而且它比L0范数要容易优化求解。所以L1范数被称为“稀疏规则算子”（Lasso）,taxicabNorm，也叫ManhattanNorm,稀疏编码,特征选择,压缩感知,17,范数的含义（续）,L2范数：又称“岭回归”（RidgeRegression），“权值衰减（weightdecay）”，EuclideanNorm,最小化L2范数，可以使得X的元素值都很小，大都接近于0,18,范数的含义（L2-norm）,L2范数的好处：1.改善“过拟合（overfitting）”,欠拟合underfitting：训练集上误差很大，即模型不能很好地拟合已有数据；,关于“过拟合”：在数学上称为“病态”（ill-condition):即函数的输入改变一点点，输出却改变非常大。,过拟合（overfitting）：模型很好地拟合训练数据，然而在新样本上表现却很差。,L2范数限制了参数都很小，实际上就限制了多项式各分量的影响很小，一定程度上避免了模型出现“病态”的情况。,2.利于优化,19,范数的含义（L2-norm）,L2范数的好处：1.改善“过拟合（overfitting）”,2.利于优化,机器学习中有时候损失函数是非凸的，例如：神经网络。采用梯度下降之类的优化方法时，容易卡住（Stuckin），导致很差的解。,非凸的损失函数,加入L2范数后,20,知识扩展稀疏性分析：,模型空间限制在w的一个L-ball中。在(w1,w2)平面上可以画出目标函数的等高线，而约束条件则成为平面上半径为C的一个normball。等高线与normball首次相交的地方就是最优解。,与L2范数相比，L1范数更有可能得到值为0的解，所以导致稀疏。,21,优化求解：,由于L1范数并没有平滑的函数（non-smooth）表示，起初L1最优化问题解决起来非常困难，但随着计算机技术的发展，目前已有很多凸优化算法(例如：线性规划/非线性规划等）使得L1最优化。,L1范数：,22,优化求解：,L1范数：,虽然，L1范数并没有平滑的函数（non-smooth）表示，但比L2范数更容易找到最优解。,23,优化求解：,L1范数：,目前，已经有很多工具箱，例如l1-magic,SparseLab,ISAL1,24,优化求解：,因为L2-范数本身具有平滑（smooth）的属性，找到单一的最优解比较困难。,L2范数：,25,Basisknowledge,L2范数最小二乘优化：,加入一个L2范数,|w|2,伪逆,26,优化求解：,在不能求得解析解的情况下，具体分析目标函数的性质（凸否？连续否？光滑否？）还可以使用凸优化方法进行求解，例如：牛顿法、最速下降法、共轭梯度法、高斯牛顿法等等，大规模数据情况下的随机梯度下降（SGD）,交替方向乘子法(ADMM),L2范数：,红色：牛顿法绿色：梯度下降法,27,Outline,1.相关概念误差和目标函数2.范数概念3.向量的范数及含义4.矩阵的范数及含义,28,矩阵的范数,29,矩阵的范数（续）,设A为n行n列的矩阵，矩阵的范数定义如下：,列范数,行范数,谱范数,5,6,5,30,举例：,31,矩阵的范数（续）,设A为n行n列的矩阵，矩阵的范数定义如下：,谱范数（不好优化）,以上为数学上范数的定义，只有F-范数在“机器学习”中常用，此处1-范数在机器学习中一般称为“l1范数”。矩阵范数最好参考相关论文中的定义。,常用,32,矩阵的范数-机器学习领域,常用范数：,按列向量先求2-范数，再求1-范数,矩阵先扩展为向量，再求范数,英文为Nuclearnorm，指矩阵奇异值的和（迹trace），故又称为trace-norm,按列向量先求1-范数，再求2-范数,33,矩阵范数的含义,最小化矩阵的F范数，会使得矩阵的每个元素都很小，接近于0,|A-B|F的含义？,|A-B|F可度量A，B之间的差异，最小化可使得两者尽可能的相等。,34,举例F范数应用,矩阵范数的含义（续）,核范数|W|*：指矩阵奇异值的和，英文为Nuclearnorm,最小化核范数可以导致矩阵低秩（Low-Rank）。,36,矩阵范数的含义（续）,低秩矩阵：如果X是一个m行n列的数值矩阵，rank(X)是X的秩，假如rank(X)远小于m和n，则我们称X是低秩矩阵。,冗余信息,矩阵的秩：矩阵的行列之间的相关性的度量。如果矩阵的各行或列是线性无关的，矩阵就是满秩的，也就是秩等于行数。,37,矩阵范数的含义（续）,25*15的图像,组成元素,但是rank()是非凸的，在优化问题里面很难求解，那么就需要寻找它的凸近似。rank(w)的凸近似就是核范数|W|*,手工求矩阵的秩：通过矩阵初等变换把A化为阶梯型矩阵，若该阶梯型矩阵有r个非零行，那A的秩rank(A)就等于r。,38,应用举例核范数,39,矩阵低秩的用处：1）矩阵填充(MatrixCompletion)：例如-推荐系统2）鲁棒PCA3）背景建模4）变换不变低秩纹理（TILT）,应用举例核范数,稀疏噪声,低秩结构信息,鲁棒PCA:,40,矩阵范数的含义,https:/en.wikipedia.org/wiki/Matrix_norm,p=1时，为矩阵的1-范数，最小化|A|1范数能让矩阵A元素稀疏,p=2时，为矩阵的2-范数，即F范数,稀疏矩阵的优点：计算速度更快存储成本低可解释性强（例如：文本分类中，可知哪些词对类别起重要作用）,41,矩阵范数的含义,KongD,FujimakiR,LiuJ,etal.Exclusivefeaturelearningonarbitrarystructuresvial1,2-normJ.AdvancesinNeuralInformationProcessingSystems,2014,2:1655-1663.,最小化|A|2,1范数能让矩阵A不同行之间（列向量）稀疏,GroupLasso,c1,c2,cn,42,矩阵范数的含义,Lasso,GroupLasso,HierarchicalLasso,文本分类中的应用：,找出关键词,找出关键句子,找出关键段,43,矩阵范数的含义,KongD,FujimakiR,LiuJ,etal.Exclusivefeaturelearningonarbitrarystructuresvial1,2-normJ.AdvancesinNeuralInformationProcessingSystems,2014,2:1655-1663.,最小化|A|1,2范数能让矩阵行内元素互斥,互斥：行内存在0元素且不能全为0.,用途：特征选择的时候不同的类别可以选择互斥的特征,44,Thanks,45,