lagrange
- 格式：pdf
- 大小：1.04 MB
- 文档页数：35
我们定义一般化的拉格朗日公式
这里的 和 都是拉 格朗日算子。如果按这个公式求解，会出现问题，因为我们求解的是最小值，
而这里的 已经不是0了，我们可以将 调整成很大的正值，来使最后的函数 结果是负无穷。因此我们需要排除这种情况，我们定义下面的函数：
这 里 的 P 代 表 primal 。 假 设
或者
首先求解
的最小值，对于固定的 ，
和 b 有关。对 w 和 b 分别求偏导数。
的最小值只与 w
并得到
将上式带回到拉格朗日函数中得到，此时得到的是该函数的最小值（目标函数 是凸函数）代入后，化简过程如下
ቤተ መጻሕፍቲ ባይዱ 最后得到
由于最后一项是0，因此简化为
这里我们将向量内积
表示为
此时的拉格朗日函数只包含了变量 。然而我们求出了 才能得到 w 和 b。
用 来表示对偶问题如下：
下面解释在什么条件下两者会等价。假设 f 和 g 都是凸函数，h 是仿射的（affine， ）。并且存在 w 使得对于所有的 i，
。在这种假设下，一定存在
使得 是原问题的解， 是对偶
问题的解。还有
另外，
满足库恩-塔克条件
（Karush-Kuhn-Tucker, KKT condition），该条件如下：
用向量的形式来表达的话，我们说相切的性质在此意味着 和 的斜率在某 点上平行。此时引入一个未知标量λ，并求解：
且λ ≠ 0. 一旦求出λ的值，将其套入下式，易求在无约束极值和极值所对应的点。
=
新方程 在达到极值时与 相等，因为 达到极值时 总等于零。
拉格朗日乘数的运用方法[编辑]
如 f 定义为在 Rn 上的方程，约束为 gk（x）= ck（或将约束左移得到 gk(x) − ck = 0）。定义拉格朗日Λ为
介绍[编辑]
微积分中最常见的问题之一是求一个函数的极大极小值（极值）。但是很多时候 找到极值函数的显式表达是很困难的，特别是当函数有先决条件或约束时。拉格 朗日乘数则提供了一个非常便利方法来解决这类问题，而避开显式地引入约束和 求解外部变量。
先看一个二维的例子：假设有函数： 足条件
，要求其极值（最大值/最小值），且满
.注意每
看下面的图：
实线是最大间隔超平面，假设×号的是正例，圆圈的是负例。在虚线上的点就
是函数间隔是1的点，那么他们前面的系数 称作支持向量。构造拉格朗日函数如下：
，其他点都是
。这三个点
注意到这里只有 没有 是因为原问题中没有等式约束，只有不等式约束。 下面我们按照对偶问题的求解步骤来一步步进行，
最大化 受限于
引入新变量拉格朗日乘数 ，即可求解下列拉格朗日方程
此方法的证明牵涉到偏微分，全微分或链法，从而找到能让设出的隐函数的微分 为零的未知数的值。
目录
[隐藏]
1 介绍 2 拉格朗日乘数的运用方法
3 例子
o 3.1 很简单的例子 o 3.2 另一个例子 4 经济学 5 参考 6 对外链接
注意极值的条件和约束现在就都被记录到一个式子里了：
和 拉格朗日乘数常被用作表达最大增长值。原因是从式子：
中我们可以看出λk 是当方程在被约束条件下，能够达到的最大增长率。拉格朗 日力学就使用到这个原理。 拉格朗日乘数法在 Karush-Kuhn-Tucker 最优化条件被推广。
例子[编辑]
很简单的例子[编辑] 求此方程的最小值：
1/3*6^(1/2) -1/3*6^(1/2) 1/3*6^(1/2) -1/3*6^(1/2)
y= 1
-1 1/3*3^(1/2) 1/3*3^(1/2) -1/3*3^(1/2) -1/3*3^(1/2) 因此，f(x,y)的最小值为-0.3849 另一个例子[编辑]
求此离散分布的最大熵： 所有概率的总和是1，因此我们得到的约束是 g（p）= 1即可以使用拉格朗日乘 数找到最高熵（概率的函数）。对于所有的 k 从1到 n，要 由此得到 计算出这 n 个等式的微分，我们得到：这说明 pi 都相等 (因为它们都只是λ的 函数). 解出约束∑k pk = 1，得到 因此，使用均匀分布可得到最大熵的值。
SVM(二）拉格朗日对偶问题 2 拉格朗日对偶（Lagrange duality）
先抛开上面的二次规划问题，先来看看存在等式约束的极值问题求法，比如下 面的最优化问题：
目标函数是 f(w)，下面是等式约束。通常解法是引入拉格朗日算子，这里使用 来表示算子，得到拉格朗日公式为
L 是等式约束的个数。 然后分别对 w 和 求偏导，使得偏导数等于0，然后解出 w 和 。至于为什么引 入拉格朗日算子可以求出极值，原因是 f(w)的 dw 变化方向受其他不等式的约 束，dw 的变化方向与 f(w)的梯度垂直时才能获得极值，而且在极值处，f(w) 的梯度与其他等式梯度的线性组合平行，因此他们之间存在线性关系。（参考《最 优化与 KKT 条件》） 然后我们探讨有不等式约束的极值问题求法，问题如下：
所以如果
满足了库恩-塔克条件，那么他们就是原问题和对偶问题的解。
让我们再次审视公式（5），这个条件称作是 KKT dual complementarity 条
件。这个条件隐含了如果
，那么
。也就是说，
时，w
处于可行域的边界上，这时才是起作用的约束。而其他位于可行域内部（
的）点都是不起作用的约束，其 来解释支持向量和 SMO 的收敛测试。
关于上面的对偶问题如何求解，将留给下一篇中的 SMO 算法来阐明。
这里考虑另外一个问题，由于前面求解中得到
我们通篇考虑问题的出发点是
，根据求解得到的 ，我们代入前式得到
也就是说，以前新来的要分类的样本首先根据 w 和 b 做一次线性运算，然后看 求的结果是大于0还是小于0,来判断正例还是负例。现在有了 ，我们不需要求 出 w，只需将新来的样本和训练数据中的所有样本做内积和即可。那有人会说， 与前面所有的样本都做运算是不是太耗时了？其实不然，我们从 KKT 条件中得 到，只有支持向量的 ，其他情况 。因此，我们只需求新来的样本和 支持向量的内积，然后运算即可。这种写法为下面要提到的核函数（kernel） 做了很好的铺垫。这是上篇，先写这么多了。
。这个 KKT 双重补足条件会用
这部分内容思路比较凌乱，还需要先研究下《非线性规划》中的约束极值问题， 再回头看看。KKT 的总体思想是将极值会在可行域边界上取得，也就是不等式 为0或等式约束里取得，而最优下降方向一般是这些等式的线性组合，其中每个 元素要么是不等式为0的约束，要么是等式约束。对于在可行域边界内的点，对 最优解不起作用，因此前面的系数为0。
同时未知数满足
因为只有一个未知数的限制条件，我们只需要用一个乘数 .将所有 方程 的偏微分设为零，得到一个方程组，最大值是以下方程组的解中的一个： 求解方程组，结果如下： lambda =
0 0 -1/3*3^(1/2) -1/3*3^(1/2) 1/3*3^(1/2) 1/3*3^(1/2)
x= 0 0
，那么我们总是可以调整 和 来使得 有最大值为正无穷。而只有
g 和 h 满足约束时， 大值。
为 f(w)。这个函数的精妙之处在于
，而且求极
因此我们可以写作
这样我们原来要求的 min f(w)可以转换成求
了。
我们使用 来表示
。如果直接求解，首先面对的是两个参数，而 也
是不等式约束，然后再在 w 上求最小值。这个过程不容易做，那么怎么办呢？
c 为常数。对不同 的值，不难想像出的等高线。而方程 的可行集所构成 的线正好是 。想像我们沿着 的可行集走；因为大部分情况下 的等高 线和 的可行集线不会重合，但在有解的情况下，这两条线会相交。想像此时 我们移动 上的点，因为 是连续的方程，我们因此能走到 更高或更低 的等高线上，也就是说 可以变大或变小。只有当 和 相切，也就是说， 此时，我们正同时沿着 和 走。这种情况下，会出现极值或鞍点。 气象图中就很常出现这样的例子，当温度和气压两列等高线同时出现的时候，切 点就意味着约束极值的存在。
又有很长的一段时间没有更新博客了，距离上次更新已经有两个月的 时间了。其中一个很大的原因是，不知道写什么好-_-，最近一段时 间看了看关于 SVM(Support Vector Machine)的文章，觉得 SVM 是一个非常有趣，而且自成一派的方向，所以今天准备写一篇关于关 于 SVM 的文章。 关于 SVM 的论文、书籍都非常的多，引用强哥的话“SVM 是让应 用数学家真正得到应用的一种算法”。SVM 对于大部分的普通人来 说，要完全理解其中的数学是非常困难的，所以要让这些普通人理解， 得要把里面的数学知识用简单的语言去讲解才行。而且想明白了这些 数学，对学习其他的内容也是大有裨益的。我就是属于绝大多数的普 通人，为了看明白 SVM，看了不少的资料，这里把我的心得分享分 享。
其实现在能够找到的，关于 SVM 的中文资料已经不少了，不过个 人觉得，每个人的理解都不太一样，所以还是决定写一写，一些雷同 的地方肯定是不可避免的，不过还是希望能够写出一点与别人不一样 的地方吧。另外本文准备不谈太多的数学（因为很多文章都谈过了）， 尽量简单地给出结论，就像题目一样-机器学习中的算法（之前叫做 机器学习中的数学），所以本系列的内容将更偏重应用一些。如果想 看更详细的数学解释，可以看看参考文献中的资料。
接着是极大化的过程
，
前面提到过对偶问题和原问题满足的几个条件，首先由于目标函数和线性约束
都是凸函数，而且这里不存在等式约束 h。存在 w 使得对于所有的 i，
。
因此，一定存在 使得 是原问题的解， 是对偶问题的解。在这里，求 就
是求 了。如果求出了 ，根据 题的解）。然后
即可求出 w（也是 ，原问
即可求出 b。即离超平面最近的正的函数间隔要等于离超平面最近的负的函数 间隔。
最优间隔分类器（optimal margin classifier）
这里的 和 都是拉 格朗日算子。如果按这个公式求解，会出现问题，因为我们求解的是最小值，
而这里的 已经不是0了，我们可以将 调整成很大的正值，来使最后的函数 结果是负无穷。因此我们需要排除这种情况，我们定义下面的函数：
这 里 的 P 代 表 primal 。 假 设
或者
首先求解
的最小值，对于固定的 ，
和 b 有关。对 w 和 b 分别求偏导数。
的最小值只与 w
并得到
将上式带回到拉格朗日函数中得到，此时得到的是该函数的最小值（目标函数 是凸函数）代入后，化简过程如下
ቤተ መጻሕፍቲ ባይዱ 最后得到
由于最后一项是0，因此简化为
这里我们将向量内积
表示为
此时的拉格朗日函数只包含了变量 。然而我们求出了 才能得到 w 和 b。
用 来表示对偶问题如下：
下面解释在什么条件下两者会等价。假设 f 和 g 都是凸函数，h 是仿射的（affine， ）。并且存在 w 使得对于所有的 i，
。在这种假设下，一定存在
使得 是原问题的解， 是对偶
问题的解。还有
另外，
满足库恩-塔克条件
（Karush-Kuhn-Tucker, KKT condition），该条件如下：
用向量的形式来表达的话，我们说相切的性质在此意味着 和 的斜率在某 点上平行。此时引入一个未知标量λ，并求解：
且λ ≠ 0. 一旦求出λ的值，将其套入下式，易求在无约束极值和极值所对应的点。
=
新方程 在达到极值时与 相等，因为 达到极值时 总等于零。
拉格朗日乘数的运用方法[编辑]
如 f 定义为在 Rn 上的方程，约束为 gk（x）= ck（或将约束左移得到 gk(x) − ck = 0）。定义拉格朗日Λ为
介绍[编辑]
微积分中最常见的问题之一是求一个函数的极大极小值（极值）。但是很多时候 找到极值函数的显式表达是很困难的，特别是当函数有先决条件或约束时。拉格 朗日乘数则提供了一个非常便利方法来解决这类问题，而避开显式地引入约束和 求解外部变量。
先看一个二维的例子：假设有函数： 足条件
，要求其极值（最大值/最小值），且满
.注意每
看下面的图：
实线是最大间隔超平面，假设×号的是正例，圆圈的是负例。在虚线上的点就
是函数间隔是1的点，那么他们前面的系数 称作支持向量。构造拉格朗日函数如下：
，其他点都是
。这三个点
注意到这里只有 没有 是因为原问题中没有等式约束，只有不等式约束。 下面我们按照对偶问题的求解步骤来一步步进行，
最大化 受限于
引入新变量拉格朗日乘数 ，即可求解下列拉格朗日方程
此方法的证明牵涉到偏微分，全微分或链法，从而找到能让设出的隐函数的微分 为零的未知数的值。
目录
[隐藏]
1 介绍 2 拉格朗日乘数的运用方法
3 例子
o 3.1 很简单的例子 o 3.2 另一个例子 4 经济学 5 参考 6 对外链接
注意极值的条件和约束现在就都被记录到一个式子里了：
和 拉格朗日乘数常被用作表达最大增长值。原因是从式子：
中我们可以看出λk 是当方程在被约束条件下，能够达到的最大增长率。拉格朗 日力学就使用到这个原理。 拉格朗日乘数法在 Karush-Kuhn-Tucker 最优化条件被推广。
例子[编辑]
很简单的例子[编辑] 求此方程的最小值：
1/3*6^(1/2) -1/3*6^(1/2) 1/3*6^(1/2) -1/3*6^(1/2)
y= 1
-1 1/3*3^(1/2) 1/3*3^(1/2) -1/3*3^(1/2) -1/3*3^(1/2) 因此，f(x,y)的最小值为-0.3849 另一个例子[编辑]
求此离散分布的最大熵： 所有概率的总和是1，因此我们得到的约束是 g（p）= 1即可以使用拉格朗日乘 数找到最高熵（概率的函数）。对于所有的 k 从1到 n，要 由此得到 计算出这 n 个等式的微分，我们得到：这说明 pi 都相等 (因为它们都只是λ的 函数). 解出约束∑k pk = 1，得到 因此，使用均匀分布可得到最大熵的值。
SVM(二）拉格朗日对偶问题 2 拉格朗日对偶（Lagrange duality）
先抛开上面的二次规划问题，先来看看存在等式约束的极值问题求法，比如下 面的最优化问题：
目标函数是 f(w)，下面是等式约束。通常解法是引入拉格朗日算子，这里使用 来表示算子，得到拉格朗日公式为
L 是等式约束的个数。 然后分别对 w 和 求偏导，使得偏导数等于0，然后解出 w 和 。至于为什么引 入拉格朗日算子可以求出极值，原因是 f(w)的 dw 变化方向受其他不等式的约 束，dw 的变化方向与 f(w)的梯度垂直时才能获得极值，而且在极值处，f(w) 的梯度与其他等式梯度的线性组合平行，因此他们之间存在线性关系。（参考《最 优化与 KKT 条件》） 然后我们探讨有不等式约束的极值问题求法，问题如下：
所以如果
满足了库恩-塔克条件，那么他们就是原问题和对偶问题的解。
让我们再次审视公式（5），这个条件称作是 KKT dual complementarity 条
件。这个条件隐含了如果
，那么
。也就是说，
时，w
处于可行域的边界上，这时才是起作用的约束。而其他位于可行域内部（
的）点都是不起作用的约束，其 来解释支持向量和 SMO 的收敛测试。
关于上面的对偶问题如何求解，将留给下一篇中的 SMO 算法来阐明。
这里考虑另外一个问题，由于前面求解中得到
我们通篇考虑问题的出发点是
，根据求解得到的 ，我们代入前式得到
也就是说，以前新来的要分类的样本首先根据 w 和 b 做一次线性运算，然后看 求的结果是大于0还是小于0,来判断正例还是负例。现在有了 ，我们不需要求 出 w，只需将新来的样本和训练数据中的所有样本做内积和即可。那有人会说， 与前面所有的样本都做运算是不是太耗时了？其实不然，我们从 KKT 条件中得 到，只有支持向量的 ，其他情况 。因此，我们只需求新来的样本和 支持向量的内积，然后运算即可。这种写法为下面要提到的核函数（kernel） 做了很好的铺垫。这是上篇，先写这么多了。
。这个 KKT 双重补足条件会用
这部分内容思路比较凌乱，还需要先研究下《非线性规划》中的约束极值问题， 再回头看看。KKT 的总体思想是将极值会在可行域边界上取得，也就是不等式 为0或等式约束里取得，而最优下降方向一般是这些等式的线性组合，其中每个 元素要么是不等式为0的约束，要么是等式约束。对于在可行域边界内的点，对 最优解不起作用，因此前面的系数为0。
同时未知数满足
因为只有一个未知数的限制条件，我们只需要用一个乘数 .将所有 方程 的偏微分设为零，得到一个方程组，最大值是以下方程组的解中的一个： 求解方程组，结果如下： lambda =
0 0 -1/3*3^(1/2) -1/3*3^(1/2) 1/3*3^(1/2) 1/3*3^(1/2)
x= 0 0
，那么我们总是可以调整 和 来使得 有最大值为正无穷。而只有
g 和 h 满足约束时， 大值。
为 f(w)。这个函数的精妙之处在于
，而且求极
因此我们可以写作
这样我们原来要求的 min f(w)可以转换成求
了。
我们使用 来表示
。如果直接求解，首先面对的是两个参数，而 也
是不等式约束，然后再在 w 上求最小值。这个过程不容易做，那么怎么办呢？
c 为常数。对不同 的值，不难想像出的等高线。而方程 的可行集所构成 的线正好是 。想像我们沿着 的可行集走；因为大部分情况下 的等高 线和 的可行集线不会重合，但在有解的情况下，这两条线会相交。想像此时 我们移动 上的点，因为 是连续的方程，我们因此能走到 更高或更低 的等高线上，也就是说 可以变大或变小。只有当 和 相切，也就是说， 此时，我们正同时沿着 和 走。这种情况下，会出现极值或鞍点。 气象图中就很常出现这样的例子，当温度和气压两列等高线同时出现的时候，切 点就意味着约束极值的存在。
又有很长的一段时间没有更新博客了，距离上次更新已经有两个月的 时间了。其中一个很大的原因是，不知道写什么好-_-，最近一段时 间看了看关于 SVM(Support Vector Machine)的文章，觉得 SVM 是一个非常有趣，而且自成一派的方向，所以今天准备写一篇关于关 于 SVM 的文章。 关于 SVM 的论文、书籍都非常的多，引用强哥的话“SVM 是让应 用数学家真正得到应用的一种算法”。SVM 对于大部分的普通人来 说，要完全理解其中的数学是非常困难的，所以要让这些普通人理解， 得要把里面的数学知识用简单的语言去讲解才行。而且想明白了这些 数学，对学习其他的内容也是大有裨益的。我就是属于绝大多数的普 通人，为了看明白 SVM，看了不少的资料，这里把我的心得分享分 享。
其实现在能够找到的，关于 SVM 的中文资料已经不少了，不过个 人觉得，每个人的理解都不太一样，所以还是决定写一写，一些雷同 的地方肯定是不可避免的，不过还是希望能够写出一点与别人不一样 的地方吧。另外本文准备不谈太多的数学（因为很多文章都谈过了）， 尽量简单地给出结论，就像题目一样-机器学习中的算法（之前叫做 机器学习中的数学），所以本系列的内容将更偏重应用一些。如果想 看更详细的数学解释，可以看看参考文献中的资料。
接着是极大化的过程
，
前面提到过对偶问题和原问题满足的几个条件，首先由于目标函数和线性约束
都是凸函数，而且这里不存在等式约束 h。存在 w 使得对于所有的 i，
。
因此，一定存在 使得 是原问题的解， 是对偶问题的解。在这里，求 就
是求 了。如果求出了 ，根据 题的解）。然后
即可求出 w（也是 ，原问
即可求出 b。即离超平面最近的正的函数间隔要等于离超平面最近的负的函数 间隔。
最优间隔分类器（optimal margin classifier）
