百科生活 投稿
关于【kkt是什么意思】:224是什么意思啊，今天涌涌小编给您分享一下，如果对您有所帮助别忘了关注本站哦。
- 内容导航：
- 1、kkt是什么意思：224是什么意思啊
- 2、支持向量机（第四章）
1、kkt是什么意思：224是什么意思啊
224是指在2月24号这一天，内涵段子不知道为什么出现了各种涉黄的图片以及文章，似乎是内涵段子的终端服务器，受到了黑客的攻击。管理员在不断的进行删帖的过程当中，与黑客不断的进行较量，最后是管理员获得了最终的胜利。
内涵段子是一款包含各类短视频、脑洞神评论、图片、段子、精华等多主题多体裁的社交软件，搞笑娱乐社区。创立于2012年，运营商为北京字节跳动科技有限公司。内涵段子APP衍生出了段友、段友暗号、内涵段子车贴等段友文化。2018年4月10日，广播电视总局责令“今日头条”网站永久关停“内涵段子”客户端软件及公众号，并全面清理类似视听节目产品。
2、支持向量机（第四章）
第四章 解最优化问题
译/吴天晖
按语：请多批评。
拉格朗日乘
意大利-法国数学家Giuseppe Lodovico Lagrangia，也就是大家知道的JosephLouis Lagrange，他发明了一个策略来寻找一个有等式约束的函数的局部最大值和最小值。这个方法叫拉格朗日乘。
拉格朗日乘数法
拉格朗日注意到当我们求如下最优化问题时：
找到f的最小值也就是找到一个同一方向的梯度点同时符合条件g。可以写成，当：
所以我们想要找到f在约束g下的最小值，也就是要求出：
这里，常数a称为拉格朗日乘子。
简化这个方法，我们发现如果我们定义一个方程(x, a)=f(x)- ag(x)，这时他们的梯度是(x, a)=f(x)-ag(x)。之后，(x, a)=0的解就是我们找到这个最小值。
拉格朗日乘数法能总结为以下三步：
1．通过每一个带乘子的约束条件来构造拉格朗日函数
2．给出拉格朗日函数的梯度
3．解函数(x, a)=0
SVM 拉格朗日问题
我们看到上一章介绍的SVM优化问题是：
让我们回到这个问题。我们有一个需求最小值的目标函数：
和约束条件函数m:
我们得出拉格朗日函数：
注意在这里我们给每一个约束函数配了一个拉格朗日乘子ai。
我们可以尝试去求(w,b, a)=0,但是这个问题仅能在用例少的情况下能分析求出（Tyson Smith,2004）。所以我们不得不用对偶原理重写这个问题。
要解答这个原问题，我们需要去解下面的拉格朗日问题：
有意思的是我们在这里要得到w和b的最小时值同时要得到a的最大值。
提示：你可能注意到拉格朗日乘数法是用来解决带等式约束的问题的，但在这儿我们用它来处理不等式约束，用这个方法来处理不等式约束，还需要附加一些条件（KKT条件）。我们之后将介绍这些条件。
乌尔夫对偶问题
拉格朗日问题有一个不等式约束m（m是指训练用例），他的典型解法是用对偶形。对偶原理告诉我们一个优化问题可以看成是两个透视图。第一个是原问题，我们关心的优化问题，另一个是对偶问题，一个求最大值的问题。有意思的是对偶问题中的最大值常常小于或等同于原问题的最小值（我们说它提供一个降低解原问题难度的方法）。
在我们这里，我们试着去解决一个凸优化问题，和仿射约束下的斯莱德条件（Gretton,2016）, 斯莱德定理告诉我们强对偶问题成立。意思是对偶问题中的求最大值等价于原问题中的求最小值。求对偶问题也就是求原问题，但是更简单。
重新列出拉格朗日函数：
这个拉格朗日原问题是：
求这个最小值问题演化为在的偏导数中求w和b。
从第一个式子中，我们发现：
让我们用下面的值代替w：
我们成功的去掉了w,但是b还是留在了式子的最后部分：
我们注意到
意味着
，因此上式的最后部分等于0,于是我们可以写成：
这就是乌尔夫拉格朗日对偶函数。
优化问题至此就被称为乌尔夫对偶问题：
通常乌尔夫对偶拉格朗日问题会强制梯度等于0。理论上，我们需增加约束
和
。然而，我们仅仅增加后面的项。就是我们增加约束
因为它能在函数中去掉b。
无论如何，我们可以在没有约束
下来解决问题。
基于乌尔夫对偶的拉格朗日问题的优势是目标函数W现在仅仅只依赖拉格朗日乘子。并且，这个公式将帮我们在下一节里用Python来解决问题而且当我们之后学习核方式时也非常有用。
Karush-Kuhn-Tucker 条件
因为我们要解决不等式约束，有一个附加条件：解决方法中必须满足Karush-Kuhn-Tucker (KKT)条件。
KKT条件首先需要的条件是能解优化问题的最值。进而，这个问题要满足一些规则条件。幸运的是，规则条件中有一个叫斯莱特条件，我们可以看到它能支持SVMs。因为我们的原问题是要试着去解决一个凸问题，KKT条件能充分满足求原问题和对偶问题的最值，他们是零对偶间隙。
总之，如果一个解法满足KKT条件，我们可以认为它是最优的解法。
这个KKT条件是：
稳定条件：
原可行条件：
对偶可行条件：
互补松驰条件：
提示：……解决支持向量机的问题等价于寻找一个KKT条件。
到此我们找到了所有的必要条件。让我们来一点一点实践吧。
稳定条件
这个稳定条件告诉我们被选点必须是一个驻点。它是一个函数递增或递减的停止点。如果没有约束，稳定条件下的驻点就是目标函数梯度为0的点。如果我们有约束，我们将把梯度用在拉格朗日函数上。
原可行条件
盯着这个条件，你应该看出来这就是原问题的约束。它要使我们必须求出这个函数在约束下的最小值。
对偶可行条件
同样，这个条件代表的是对偶问题的约束。
互补松驰条件
从互补松驰条件中，我们可以看到
或
。
支持向量是一个正拉格朗日乘子的示例。它们是约束
其中之一。（我们看见这个约束
是可用的）。
技巧：从互补松驰条件中，我们看到支持向量是正拉格朗日乘子的示例。
我们如何使用这个乘子？
当我们解乌尔夫对偶问题时，我们得到一个向量a包含所有的拉格朗日乘子。可是，当我们首先提到原问题时，我们的目标是寻找w和b。让我们看我们怎样去从拉格朗日乘子中提取这些数值。
计算w
计算w是相当简单的，从梯度
得到公式：
。
计算b
一量我们已知w,我们可以从原问题的约束中计算b：
事实上，这个约束一直是正确的，因为这新的公式是与原问题等价的一种变形。它说明这些临近超平面的点将被一个函数限制在1内（这个值1是我们选的用来让我们决定如何去变形W）：
到这里，我们知道所有的其他变量,求b就变得很容易开始了。我们在等式两边都乘以yi，又因为
，我们得到：
然而，在文献模式识别与机器学习（Pattern Recognition and Machine Learning (Bishop, 2006)）中，我们用提供的支持向量的平均值来代替随机支持向量xi是更稳健的方法：
这里S是支量向量的个数。
其他作者，像(Cristianini & Shawe-Taylor, 2000) 和(Ng),用另一个公式：
它们都主要是取最近的正支持向量和最近的负支持向量的平均值。最后的公式最初是统计学习理论（Statistical Learning Theory (Vapnik V. N., 1998)）用来定义最优超平面的。
假设函数
SVMs用与感知器得到的相同的假设函数。分类示例点xi 函数：
当我们使用对偶公式，它可以仅用支持向量计算：
用QP方法来处理SVMs
QP方法是一个用来处理二次型编程问题的程序。在接下来的例子中，我们将wgket用一个叫CVXOPT的Python包。
这个软件包提供一个方法来解决类似下面的二次型问题：
这看起来不像我们的优化问题，所以我们将要去改写它，让它能用这个软件包来处理。
首先，我们注意到乌尔夫对偶优化问题中，我们要去最小化a，所以我们可以改写二次型问题，用a来代替x，看来会让两个问题的关系近一些。
这里的
符号代表分量式不等式。意思是矩阵Gλ的每一行都必须满足不等关系。
我们来改变乌尔夫对偶问题。首先，我们转化最大值问题：
乘以-1转化成最小值问题。
然后我们让向量
和
及克莱姆矩阵K都与向量xi作点积运算：
我们用它们构造一个向量化的乌尔夫对偶问题，
表示y的外积。
我们现在可以求用CVXOP qp函数求出P，q，G，h，A和b等等所有参数的值。如代码表24所示。
代码表24# See Appendix A for more information about the dataset from succinctly.datasets import get_dataset, linearly_separable as lsimport cvxopt.solvers X, y = get_dataset(ls.get_training_examples) m = X.shape[0] # Gram matrix - The matrix of all possible inner products of X. K = np.array([np.dot(X[i], X[j]) for j in range(m) for i in range(m)]).reshape((m, m)) P = cvxopt.matrix(np.outer(y, y) * K) q = cvxopt.matrix(-1 * np.ones(m)) # Equality constraints A = cvxopt.matrix(y, (1, m)) b = cvxopt.matrix(0.0) # Inequality constraints G = cvxopt.matrix(np.diag(-1 * np.ones(m))) h = cvxopt.matrix(np.zeros(m)) # Solve the problem solution = cvxopt.solvers.qp(P, q, G, h, A, b) # Lagrange multipliers multipliers = np.ravel(solution['x']) # Support vectors have positive multipliers. has_positive_multiplier = multipliers > 1e-7 sv_multipliers = multipliers[has_positive_multiplier] support_vectors = X[has_positive_multiplier] support_vectors_y = y[has_positive_multiplier]
代码表24初始化所有要求的参数并且将其传给qp方法，它会给我们一个结果。这个结果包含很多无素，但是我们只关心x，它在我们这里相当于就是拉格朗日乘子。
当我看到上面，我们可以用拉格朗日乘子重算w：
。代码表25显示计算w的函数代码。
代码表25def compute_w(multipliers, X, y): return np.sum(multipliers[i] * y[i] * X[i] for i in range(len(y)))
因为拉格朗日乘子对于非支持向量的结果近似为零，所以我们只用支持向量数据来计算w，见代码表26。
代码表26w = compute_w(multipliers, X, y) w_from_sv=compute_w(sv_multipliers, support_vectors, support_vectors_y) print(w) # [0.44444446 1.11111114] print(w_from_sv) # [0.44444453 1.11111128]
当我们用均值方法计算b时：
代码表27def compute_b(w, X, y): return np.sum([y[i] - np.dot(w, X[i]) for i in range(len(X))])/len(X)代码表28b = compute_b(w, support_vectors, support_vectors_y) # -9.666668268506335
当我们将结果用图32来表示时，我们发现这个超平面就是最优超平面。与感知器不同，SVM总能得到相同的结果。
图32: 用CVXOPT求出超平面
我们介绍的这种SVM被称为硬边界SVM。它面对非线性可分的数据不能工作。有几个时髦的支持向量机的方法。在下一章我们将介绍另一种被称为软边界SVM的方法，它能够在有非线性可分的异常据数据下工作。
小结
w的范式的最小值是一个凸优化问题，它可以用拉格朗日乘数法解决。当我们有更多的这类问题时，我喜欢用凸优化包，它可以帮我们做这些艰苦的工作。
我们发现原优化问题可以用拉格朗日函数来改写成，谢谢对偶规则，我们可以将拉格朗日问题转成乌尔夫对偶问题。我们还用了CVXOPT包来求解乌尔夫对偶。
本文关键词：2242啥意思，2243是什么意思，2244是什么意思啊，22422是什么意思，224的含义是什么意思。这就是关于《kkt是什么意思，224是什么意思啊（支持向量机<第四章>）》的所有内容，希望对您能有所帮助！
- 最近发表