课件l2优化基础

优化基础基本逻辑推理单元的实现W.S.McCullochandW.Pitts.Alogicalcalculusoftheideasimmanentinnervousactivity.Thebulletinofmathematicalbiophysics,5(4):115–133,1943.1943Mcculoch-Pitts人类基本推理OR/AND/NOT最简单的逻辑单元Howtobeadaptative?DonaldHebble的突破1949发现生物神经元的学习机制意义：复杂推理成为可能Rosenblatt：感知机1957人工神经元诞生感知机（Perceptron）对分类问题的两种不同观点1.学习一个离散函数；2.在特征空间中学习一个分界面(decisionboundary)数学知识准备：1.如何刻画一个高维空间中的线性分界面（即超平面,hyperplane）;2.梯度、向量求导、矩阵求导3.基本优化方法数学基础1：Hyperplane两个要素：方向+位置位置r：相对于原点：signeddistancemargin点与超平面的关系：点x与超平面的signed距离d：positive、negative、zero（ontheplane）如何计算d？先算x在w方向的投影然后减去r超平面方程d(x)=w’x–bmarginScalingw是否会影响这个距离？ifw’=bw,d(w’)=d(w’)ornot?Margin：mi=yi*dishouldalwaysbepositiveifthepredictioniscorrectcheckthis!!Thelarger,thebetter=>LargeMarginPrinciple.Point-NormalFormGivenorientationw，以及超平面上一点a此时如何计算d？可见，f(x)=w’x–b中，b的含义是超平面与原点的距离。w=?a=?朴素贝叶斯分类器NaïveBayesdecisionboundary:线性平面贝叶斯分类器：如果x为正的概率大于为负的概率，那么就预测为正。称为：loglikelihoodratio.所谓朴素贝叶斯，就是假定：给定标号，每个特征彼此条件独立,so，把视为wi，xi视为Indicator变量，则f(x)=w’x+b是一个线性模型。例子：Multi-instanceLearning

orhowtobackpropagatelabels?poolingdetectionYesNoNIPS’91手写体识别:先分割还是先识别？线性模型\eta_{xy}^i理解为在xy处发现字符类型i的log似然率。x_{xy}^i：取指数后，为似然率，即在xy处发现字符i的证据。Si：累计第i类的证据（位置无关），线性模型，仍然理解为似然率。Pi：在图片上发现第i类的概率，why？Summarysofar…要定义一个超平面，需要指定一个方向w，以及指定一个相对位置：与原点的signeddistance，或任意一个唯一超平面上的点。Margin可以用来指示超平面是否对样本的类别做出了正确的预测。线性超平面理解为log似然比。数学基础2：gradient梯度是函数定义域中的一个向量，指向函数变化最大的方向。也可理解为一个函数，给定一个位置，输出一个方向，沿该方向函数变化最大。Whywecareaboutthis?Providesvaluablehintsonlocalpropertyofthefunction.

Hessian矩阵的直观含义：表示函数在某处的“曲率”：即函数表面在某处的弯曲程度，常用于逼近函数的局部性质。Summarization梯度1.梯度计算2.最陡梯度下降3.牛顿法4.随机梯度下降向量和矩阵求导1.向量关于标量求导=》一个列向量2.标量关于向量求导=》一个行向量3.向量关于向量求导=》当作一系列标量关于向量求导，得到一个矩阵。问题：梯度是哪种方式？例子第一步，按element-wise重写目标函数

第二步，按基本求导方式求导第三步，重写结果。f(x)=w’x+b,求f(x)关于w的导数例子Lowrank：realcoreisnotsocomplexasitlookslike.用户和题材(genres)都可分成几大类。可能包含噪声数据。第一步，第二步，第三步，矩阵=groupofvectors/objectsinthesamesubspace，butarrangedinroworcolumn.2.两个矩阵相乘，第i行j列元素是i行j列相应向量的内积。LearningLatentfactorModelASimplerMethod第一步，把所有的矩阵、向量都当作变量第二步，标量函数对单变量求导第三步，重构，e.g.,uv,涉及两个nxk,mxk矩阵=》UV’是唯一满足矩阵乘法的选择。whynotVU’？因为后面还要乘以V！计算目标函数J(w)关于向量w的导数。梯度可视化及其应用某层神经元输出关于输入图像的梯度图像Whatdoesthisredcolormean?增强红色部分可以增强该神经元对该种输入信号（人脸）的响应。L3输出关于输入信号的梯度梯度1.梯度计算可视化及应用2.最陡梯度下降–无约束优化方法3.牛顿法4.随机梯度下降无约束优化Min_xf(x)1.优化难度与目标函数f(x)有关2.一阶优化必要条件：在最优点处梯度为0.如何搜索梯度为0的位置？函数局部性质的利用：一阶近似：最陡梯度下降二阶近似：牛顿法最简单的优化目标函数最简单？计算量小？函数形式简单？No，1）只有一个全局最优点；2）没有其他局部最优点。如何刻画这种最简单的目标函数？什么样的目标函数满足上面两条性质？直觉：已知任意两个点，用线性插值的方式来估计之间的点，这些点的函数值一定会被“高估”！f(interiorofdomain[a,b])<=image(a)+image(b)区域中每个点x都映射到f(x),这些映射的箭头：总是“外向”发散不交叉Likea吹满了气的气球发散性质：x周围的映射总是比线性发散快！二阶性质：即从任意点开始运动，其运动速度（梯度）在到达0之前不会改变方向。凸函数与机器学习的关系Convexlearningproblem:假设集为convexset,且损失函数为凸函数的学习问题。两类基本的可学习问题：Convex-lipschitz-boundedConvex-smooth-boundedLipschitzness:粒子沿函数表面的运动速度可控Smoothness：运动速度的改变（梯度改变）可控0-1损失的surrogateloss：有约束优化-几何理解问题：如何在这个约束线上移动搜索，以找到令目标函数最小的点？Step1：考察可行集条件。Step2：结合目标函数考察最优点条件。可行集：1.“运动方向”=》切线方向=》梯度方向与可行集（搜索区）C正交的平面定义为等式约束Step2.原问题：在C上搜索令f最小的位置。=>沿f的梯度搜索，but同时受可行域约束

=》在最优位置，C与最低的f水平线相切。此时，a=0，即，一般而言，f的梯度可分解为：与C正交的方向b+与C切线平行的方向a=》只要a不为0，便可不断改变目标函数值构造函数得到，最优化条件：一阶梯度为0的最优化条件：以上两者等价！意义：约束优化转化为了无约束优化！L(x,alpha)称为拉格朗日函数。不等式约束可行集：扁豆内部。a处：完全满足约束，等同于无约束优化。c处：等同于等式约束:g_i(x)=0。b处：从扁豆内部一点开始，朝目标梯度的反方向搜索，到达某个扁豆壳（active）后，我们只能在这个表面搜索而不能离开它，此时同等式约束搜索。而对另外那个没有起作用的扁豆壳，我们说它是inactive的。如果令inactive的约束的系数ai=0，最优点处只有等价约束，可统一写为：虽然有多个约束，但在最优点处，只有部分起作用（active）,对应等式约束gi=0;而对于inactive约束，其在优化条件中的系数为0.,因此，对所有约束及其系数，有，KKT优化条件：KKT优化条件：等价于：Why？对active约束，其系数ai总是小于0！因为，最优点位于可行集外部，故f的梯度指向可行集内部；而约束表面的梯度总是指向外。有约束优化-代数理解拉格朗日对偶函数对偶函数是对原始目标函数的线性逼近：用线性函数逼近违反约束的“displeasure”（线性系数越大，逼近越精确）Minimax不等式解释：设X对应primary变量，目的是令loss最小；Y对应对偶变量，目标令当前setting下的对偶函数取最大值。1）若X先走，则Y的策略很简单，就是根据X的结果，选择最优策略：既然我们知道Y的策略如此，那么X能做的，就是选择这样的x，使得Y的策略收益最小：2）若X后走，则其策略是，根据Y的结果，选择：因此对Y而言，最佳的策略为：Minimax不等式告诉我们：先走更吃亏。算法：1.形成拉格朗日函数；2.保持对偶系数不变，优化目标函数；3.保持原参数不变，优化对偶系数。写出拉格朗日函数；写出拉格朗日对偶函数；解之。写出原优化问题的对偶问题；解之。对偶问题右边的损失函数的含义？给出拉格朗日函数；给出更新梯度表达式；给出拉格朗日系数表达式根据一阶优化条件，解出w=？代入拉格朗日函数得到：————————————根据一阶优化条件，解出\tao=？优化算法优化点的必要条件：在最优点处梯度为0.如何搜索梯度为0的位置？函数局部性质的利用：一阶近似：最陡梯度下降二阶近似：牛顿法梯度学习方法的核心思想目标：寻找参数模型的最优参数取值。先转化为：寻找最优模型：再转化为：求最优的搜索方向1）一阶近似；2）二阶近似；实践中，通常不搜索，按经验设置，逐渐减小。梯度下降应用Howtocomputegradientforthis?在图像上按梯度方向更新鸵鸟豪华超长轿车Idea：扫描大脑，

选择一组特定神经元，

根据这组神经元的触发模式，以及它们对”云”图像的编码，重构你看见的图像

呈现重构的图像。如果你看见一片云，能否告诉我这片云在你大脑中是什么样子？演示视频Basedonwhatyou'veseen/whatyouknow,whatdoyouthinkthisis?"Googledeepdream:某层神经元对所见图像的编码.演示视频-1演示视频-2把activation(编码)直接当作梯度反馈.如何定义风格、内容、空间关系？ECCV‘16高层重构-保持内容和大体空间关系，但是丢失细节（颜色、纹理、准确形状）低层重构-保持风格特征、丢失空间信息。Idea：搜索一张图像y，使得其风格和内容与制定的样本尽量一致。优化算法优化点的必要条件：在最优点处梯度为0.如何搜索梯度为0的位置？函数局部性质的利用：一阶近似：最陡梯度下降二阶近似：牛顿法Recall…方向曲率图中曲线是函数在输入空间中的levelcurve；H是其二阶导数；将H进行特征分解，得到函数的“内在坐标”系统。可见，函数在任意方向d的弯曲程度，都可用内在坐标系统的“基”及其权重来刻画。函数的二阶近似用二阶逼近来估计梯度步长问：e多大时目标函数下降最大？共轭梯度法正交梯度方向可以提高搜索效率！已知A，b，求解线性方程Ax=b，可转化为一个二次优化问题!最陡梯度下降（梯度=残差）易于验证，r_{i+1}与r_{i}正交，r_{i}是残差，也是梯度反方向！（对梯度的另外一种重要理解！）因此，最陡梯度下降法本质上是产生了一系列彼此正交的移动方向！共轭梯度法共轭梯度法：自动高效产生一系列关于A的共轭向量d1,d2,…dn，按这一系列向量进行搜索，最多n步可得线性方程的解。（A是nxn矩阵）A-共轭：d1’Ad2=0d注意：1.梯度本身并不共轭；2.共轭的方向并非梯度。此过程可视为一个函数：输入：d0，A，输出：d0的共轭向量d1Hessian-free共轭梯度法避免了牛顿法中的H求逆。BFGS/Limited–BFGS：牛顿法的近似Hessian-free方法：如果可以近似出Hv，那么直接可利用CG方法给出V的共轭梯度，无需估计H。。Insight:用当前梯度g_n，及Hg_n的估计方法，可以快速计算g_n的共轭梯度，而不必计算Hessian矩阵。过大和过小的梯度下降步长都不理想。红色方向：考虑了局部曲率的HF方向。ICML’10优化算法优化点的必要条件：在最优点处梯度为0.如何搜索梯度为0的位置？函数局部性质的利用：一阶近似：最陡梯度下降二阶近似：牛顿法Applications基本的Lucas-kanade算法假定所有像素都以相同速度（u,v)运动下一步：关于deltap求导下一步，令此为0，解deltap其中H是Hessian矩阵，为，高斯牛顿法近似注意：这里是关于每个像素位置x优化参数。残差梯度组合warp：就是连续warp一个object的operator，其结果是一个新的warp。一个逆warp也是一个warp：其作用是从解除上次warp的效果。H只与template有关，可以事先计算。当前位置X0，如何设计一个目标函数，通过它可得一个更好移动位置deltaX？Idea:残差学习：一个好的移动，应该满足什么条件？

=

=》最小化模型输出与真实目标之间的残差？=

=》如何形式化?CVPR’13关于deltaX求导，等于0，由（5）知，更新模型是一个线性模型：问题：如何估计线性模型参数Ro,bo?需要关于Deltax的训练样本！Learningthemodel构造训练样本：利用标注样本的x*，随机初始化X0，则训练示例为：利用这些示例，进行线性模型拟合：更新形状估计：两种基本方法：回归：学习从LR到HR的转换模型；重构：一个样本在LR空间和HR空间中的重构系数保持不变利用高低分辨率patch之差deltaz，学习一系列线性模型，逐步逼近高精度图像。类似方法CVPR’04Idea：1.事先准备好低图像块和高图像块之间的对应关系；2.对待处理低精度图像块，寻找其低精度邻域块，学习重构系数。3.用学到的重构系数来组合对应的高精度块，得到高精度图像。优化算法优化点的必要条件：在最优点处梯度为0.函数局部性质的利用：一阶近似：最陡梯度下降二阶近似：牛顿法回到一阶近似：SGD高级梯度计算技术自然梯度蒙特卡洛梯度估计强化梯度学习不可微：L1-norm,Nuclear-Norm牛顿法的不足Hessianmaybetoolargetouse.复杂目标函数（e.g.,神经网络）下，充满了局部最小，与其花大力气准确找到一个局部最小位置，不如用粗糙的方法多找几个，从中挑个好的。Goodtraining<>Goodtesting.寻找globaloptimum,orgoodlocaloptima,stochastic方法更适合，why?Bettertohandleacomplexproblemwithmany,manysmallsteps,insteadofafewbigones.SGDStochasticGradientDecentNOT:SteepestGradientDecentSGDNoise–why?wecannotseeallthedata,helpful!Helptojumpoutofbadlocation.最陡梯度随机梯度，全部样本轮一次算一个epoch；训练按epoch迭代。

Otheroptimizationtricks因为计算梯度时是“近视”的，所以不要太相信它.runningaverage/momentumMomentumupdate参考前一次的梯度（惯性）来决定当前更新方向：惯性+当前估计。将与上次更新方向d_{i-1}与当前梯度结合产生新的更新方向。等价于相比动量方式，考虑了目标函数的二阶导数信息，因此收敛更快。AdaGrad–是一种搜索时的ExplorationandExploitation的权衡机制，鼓励探索“尝试不足”区域，i.e.,即能量累积小的区域。可视为一种牛顿法变体butmuchsimpler（按维度加权）.RMSPropWhat’stheproblemofAdaGrad?训练久了会爆掉why?能量累积过大Simplesolution：forgetting/leakingmechanism：runningaverage而不是一直累积某个参数（维度）的能量。SGD的其他常用tricks1.ShufflingandCurriculumLearning：每轮训练都重新洗牌，或把样本按“难易程度”排列。2.EarlyStopping:beautifulfreelunch!3.GradientNoise:givemorechancestootherdirection.4.BatchNormalization：每训练一段时间，把参数(不是数据！)重新“归拢”一次。Why？相当于正则化，让模型倾向于高斯分布，然后用一个简单的线性模型去让它们“恢复原状”。SummarysofarStochasticGradientDescentSometricksofSGD大规模SGD克服“随机”：curriculumlearning、batchnormalization动量、