- VisualStudio2022插件的安装及使用-编程手把手系列文章
- pprof-在现网场景怎么用
- C#实现的下拉多选框,下拉多选树,多级节点
- 【学习笔记】基础数据结构:猫树
拉格朗日乘数法可用于解决带条件优化问题,其基本形式为:
该问题的拉格朗日函数为 。
定义 。
容易看出,若\(w\)打破了原问题的某个限制条件,则\(\mathcal P(w)=+\infty\),否则\(\mathcal P(w)=f(w)\),因此原始问题可以表示为\(\min_w\mathcal P(w)\);对应地,对偶问题可以表示为\(\max_{\alpha\ge 0,\beta}\mathcal D(\alpha,\beta)\),也就是 。
这就是原始问题对应的对偶问题,从上面可以得到原始问题与对偶问题最优解之间的关系:
一般不能肯定原始问题与对偶问题具有相同的解,然而已有证明表明在一定条件下原始问题与对偶问题具有同一组解\((w^*,\alpha^*,\beta^*)\),使得\(p^*=d^*=L(w^*,\alpha^*,\beta^*)\),并且这组解满足KKT条件:
其中,第三条\(\alpha_i^*g_i(w^*)=0\)被称为互补松弛性. 。
支持向量机的训练集\(D=\{(x_i,y_i)\}\)中,\(y_i\in\{1,-1\}\),正例标签为\(1\),负例标签为\(-1\). 在几何直观上,支持向量机试图找到一个超平面\(w'x+b=0\),使得所有样本在正确分类的前提下,所有点到超平面的直线距离的最小值最大. 。
综合以上三点,支持向量机意图找到一个\(\gamma >0\)作为所有点到超平面的最小距离,并最大化这个\(\lambda\),因此支持向量机的初始优化问题是 。
此时约束条件是非凸的,令\(\gamma :=\frac{\gamma}{\|w\|}\),上述问题就转化成 。
此时目标函数是非凸的,然而\((w,b)\)作为超平面的参数可以进行伸缩变换,且问题的解\((w,b,\gamma)\)在目标函数和约束条件上均是齐次的,这就使得任意一组解\((w,b,\gamma)\)都可以等效为\((\frac{w}{\gamma},\frac{b}{\gamma},1)\),即设定\(\gamma\equiv1\)不会影响解的存在,因此可以在问题的形式中隐去参数\(\gamma\),最后将目标函数等效变换,就得到SVM原始问题:
现在求其对偶问题. 此问题的拉格朗日函数是 。
对偶问题即\(\max_{\alpha\ge 0}\min_{w,b} L(w,b,\alpha)\),要计算\(\min_{w,b}L(w,b,\alpha)\)需对\(w,b\)求偏导,并令偏导数等于\(0\),即 。
将\(w=\sum_{i=1}^{n}\alpha_iy_ix_i\)代回\(L(w,b,\alpha)\),再结合\(\sum_{i=1}^{n}\alpha_iy_i=0\)以及\(\alpha_i\ge 0\)的条件,就得到对偶问题为 。
线性不可分情形下,原始问题不可解,即不可能满足对所有样本都有\(y_i(wx_i+b)\ge 1\),因此软间隔SVM对每个样本考虑一个容错\(\xi_i\ge 0\),允许样本在一定程度上违背分类原则,但相应地在目标函数中施加惩罚,优化问题就产生如下变化:
这里引入了超参数\(C\)表示对分类错误的容忍程度,\(C\)代表惩罚力度,\(C=+\infty\)时软间隔SVM就退化为硬间隔SVM. 同样求其对偶问题,拉格朗日函数是 。
对偶问题是\(\max_{\alpha\ge 0,r\ge 0}\min_{w,b,\xi}L(w,b,\xi,\alpha,r)\)要求\(\min_{w,b,\xi}(\alpha,r)\),就对\(w,b,\xi\)求偏导并令之等于\(0\),得到 。
将\(w=\sum_{i=1}^{n}\alpha_iy_ix_i\)代入到\(L(w,b,\xi,\alpha,r)\)中,并结合\(\sum_{i=1}^{n}\alpha_iy_i=0\)和\(\alpha_i+r_i=C\)的约束条件,就得到对偶问题 。
可以看到,软间隔SVM相比硬间隔SVM,它们的对偶问题优化目标一致,唯一区别在于为每一个\(\alpha_i\)添加了上界\(C\),因此仅在求解时有些许区别. 。
现在根据原始问题推导得到对偶问题,并且假定已经了解对偶问题的解法. 然而最终回到问题本身,还是要找到对应的分组超平面\((w,b):w'x+b=0\),因此需要了解原始问题与对偶问题的关联. 。
首先,讨论的前提是原始问题与对偶问题同解,对支持向量机而言,已有证明表明这一条件是成立的,即原始问题与对偶问题共享拉格朗日函数的一组解,记作\((w^*,b^*,\alpha^*[,\xi^*,r^*])\)(中括号内是软间隔SVM独有的变量),且KKT条件也成立,这意味着互补松弛性\(\alpha_i^*g_i(w^*)=0\)对任何样本\(i\)都成立. 。
在上述前提下,考虑下面的几个问题:
首先,第一个问题中,互补松弛性成立表明对每个样本\(i\),都有\(\alpha_i^*g_i(w^*)=0\),回到问题定义上,\(\alpha_i\ge 0\)是对偶问题中约束条件\(g_i(w^*)\le 0\)即\(y_i(w_ix+b)\ge 1-\xi_i\)的对应系数,既然\(\alpha_i\ge 0\)且\(g_i(w^*)\le 0\),那么要使\(\alpha_i^*g_i(w^*)=0\),就必须满足\(\alpha_i^*=0\)或\(g_i(w^*)=0\). 而\(\alpha\)是通过对偶问题求解直接获得的,并且与每个样本对应,因此对每个样本,必定满足下面两个条件中的至少一个(硬间隔SVM中不含\(\xi_i\)):
实际数据集中,非支持向量的数量总是远多于支持向量,即大多数样本总是落在分隔超平面以外,支持向量的数量相对较少,但只有它们对分类器产生实质影响,因此分类器才被称为支持向量机. 为什么说只有支持向量会实质上地影响分类器,要看第二个问题与第三个问题,下面用\(SV\)表示支持向量(support vector)所构成的集合. 。
第二个问题,即如何根据\(\alpha^*\)反推\((w^*,b^*)\),这由优化过程中的偏导条件可得. 注意到令\(\frac{\partial L}{\partial w}=0\)时得到了\(w=\sum_{i=1}^{n}\alpha_iy_ix_i\),这正是最优解所满足的条件,即 。
进一步地,因为当且仅当样本为支持向量时\(\alpha_i^*>0\),即对大多数样本有\(\alpha_i^*=0\),这部分样本对\(w^*\)没有贡献,也就是 。
接下来考虑\(b^*\),同样根据互补松弛性,当且仅当样本为支持向量时成立\(y_i(w'x_i+b^*)=1-\xi_i\),因此对每个支持向量,如果能求得\(\xi_i\)的值就能得到\(b^*\)的值. 注意到当\(\alpha_i<C\)时\(r_i>0\),从而\(\xi_i=0\),因此只要能够找到一个\(\alpha_i\in (0,C)\),就能通过计算得到\(b^*=y_i-(w^*)'x_i\)(注意到\(\frac{1}{y_i}=y_i\)). 往往可以对所有这样的样本做一个平均以平滑,即 。
特别对硬间隔支持向量机,此时在正负样本中都必定存在一个支持向量,落在超平面间隔上,从而 。
最后一个问题即如何判别样本,这个问题相对简单,因为训练集中正样本总满足\((w^*)'x_i+b^*\ge 1\),负样本总满足\((w^*)'x_i+b^*\le -1\),\(\xi_i\)是针对特殊情况的补偿,因此在模型使用时不需考虑,未知样本\(x_0\)的分类就是 。
可以看到,求解完毕的支持向量机中,无论是参数表示还是模型使用,均只与支持向量有关. 。
线性不可分时,除了能使用软间隔SVM以外,还可以用特征映射\(\varphi(\cdot)\)将样本\((x_i,y_i)\)映射到高维\((\varphi(x_i),y_i)\),因为高维空间中的数据更系数,线性可分的可能性也更大. 然而,\(\varphi(\cdot)\)往往是形式未知、维度极高甚至是无限维的,在这种情形下,核技巧(kernel trick)提供了一种绕开\(\varphi(\cdot)\)的计算,不显式地计算转化后的数据集\(\varphi(x_i)\),也能在转化后的高维空间中使用支持向量机的方法. 。
先回顾支持向量机应用于非特征映射数据集时的步骤:
注意到上面的过程中,有意地隐去了\(w\)的计算,因为不论在模型表示还是样本归类中,都不需要显式地得到\(w\)的具体值;并且,任何出现了样本特征\(x\)的地方,总是以内积\(x_i'x_j\)的形式出现. 这说明,即使使用了特征映射\(\varphi(\cdot)\),也不必显式地得到每个样本\(x\)对应的高维特征\(\varphi(x)\),但是对任意样本对\((x_i,x_j)\),它们的内积\(\varphi(x_i)'\varphi(x_j)\)却是必要的. 。
因此,核技巧不显式地求解\(\varphi(\cdot)\),而是用一个对称二元函数\(\kappa:(\mathbb{R}^{d},\mathbb{R}^{d})\mapsto \mathbb{R}\)定义了内积:\(\kappa(x_i,x_j)=\varphi(x_i)'\varphi(x_j):=\langle x_i,x_j\rangle\),这样,将核技巧运用于支持向量机就可以将上面的步骤直接改写为:
综上所述,核技巧就是在不使用特征映射\(\varphi(\cdot)\)的显式表达的同时,利用内积完成了特征映射所需要达到的目标,使得用户不需要考虑如何变换样本的特征,只需尝试不同的核函数即可. 常用的核函数有:
甚至核函数的形式也不是必要的,只要有办法得到每一个样本对的核函数值即可,因此在训练过程中,传入一个核矩阵\(K\in\mathbb{R}^{n\times n}\)代表样本对的核函数值,并在使用过程中传入样本\(x_0\)的同时,传入一个向量\(k_0\in\mathbb{R}^{n}\)代表\(x_0\)与所有训练样本的核函数值,就可以等效地作为核函数使用. 。
不过,由于核函数本身是特征映射内积的替代,所以核函数本身需要满足一定的条件. Mercer表明任何半正定函数都可以作为核函数使用,半正定函数指的是对任意数据集\((x_1,\cdots,x_n)\),核函数\(\kappa\)诱导的矩阵\(K\in\mathbb{R}^{n\times n}:K_{ij}=\kappa(x_i,x_j)\)都是对称半正定的. 即使传入核矩阵\(K\)代替核函数,那么\(K\)本身也要是对称半正定矩阵,并且加入训练样本后,它与其他样本构成的核向量也要在增广意义下是对称半正定的. 。
最后进入到求解对偶问题的算法,常使用SMO(序列最小优化)算法对SVM的对偶问题进行求解,其思想是在对偶问题的\(n\)个变量中每次只选择两个进行优化,通过约束\(\sum_{i=1}^{n}\alpha_iy_i=0\),固定\(n-2\)个变量使得每次优化只有一个\(\alpha_i\)可以自由变化,因此可以通过求梯度的方式直接优化. 。
对软间隔SVM,令\(K_{ij}=\langle x_i,x_j\rangle\)即\(x_i,x_j\)的核函数值,目标是最大化 。
现选择变量对\((\alpha_1,\alpha_2)\)优化并将其他变量用无关值\(C\)代替,那么约束变为\(\alpha_1y_1+\alpha_2y_2=\zeta\),目标就变成 。
再将约束条件:\(\alpha_2=\zeta y_2-\alpha_1y_1y_2\)代入,并令\(\sum_{j=3}^{n}\alpha_jy_jK_{ij}=v_i(i=1,2)\),就得到关于\(\alpha_1\)的一元二次优化问题 。
令\(\frac{\partial W(\alpha_1)}{\partial \alpha_1}=0\)就得到\(\alpha_1\)应满足的条件为 。
在求得\(\zeta\)、\(v_1\)和\(v_2\)的同时,已经可以计算得到\(\alpha_1\)、\(\alpha_2\)的值. 注意,在软间隔SVM中还需要满足\(\alpha_1\in[0,C]\)与\(\alpha_2\in[0,C]\),并结合约束\(\alpha_1y_1+\alpha_2y_2=\zeta\). 这里分两种情况:
上述形式还可以继续化简,注意对\(\alpha^\text{new}\)和\(\alpha^\text{old}\)作区分. SVM对样本\(x\)的预测为\(f(x)=\sum_{i=1}^{n}\alpha_i^\text{old}y_i\langle x_i,x\rangle +b\),因此 。
再将\(\alpha_2=\zeta y_2-\alpha_1y_1y_2\)代入(此式子对\(\alpha^\text{new}\)和\(\alpha^\text{old}\)均成立),就得到 。
将其带回\(\frac{\partial W(\alpha_1)}{\partial \alpha_1}\)得到 。
令\(E_i=f(x_i)-y_i\)为旧模型在第\(i\)个样本上的预测误差,就有 。
上式略过了一些繁琐参数(如\(C\)、\(\zeta\))的计算,形式美观,但应用上依赖于旧模型\(f(\cdot)\),这意味着每次更新参数后需要得到新的模型,即需要对\(b\)进行更新. 注意到,至少有一个\(\alpha_i\)不在边界\([0,C]\)上时\(x_i\)是支持向量,此时有 。
若两个\(\alpha_i\)经更新后均不在边界上,则通过两个\(x_i\)计算得到的\(b^\text{new}\)相等;若两个\(\alpha_i\)经更新后均在边界上,则取用这两个样本计算得到的\(b\)的中点作为\(b^\text{new}\). 。
综上,给出SMO算法更新软间隔SVM的含代数步骤:
下面给出了使用SMO算法训练SVM分类器的具体实现,这里使用了随机抽选的方式选择每次更新的变量对\((\alpha_i,\alpha_j)\),并且使用内积核函数,指定\(C=+\infty\)代表一个硬间隔分类器. 模型对一个人造数据集合真实数据集breast_cancer都有较为不错的分辨能力,需注意要对模型标签进行\(\{-1,1\}\)化,同时这里还对特征进行归一化以防止数值溢出. 。
import numpy as np
from sklearn.datasets import load_breast_cancer
class SVM:
def __init__(self, X, y, kernel=None):
self.X = np.array(X)
self.y = np.array(y) # {-1, 1}
if not kernel:
kernel = np.dot
self.kernel = kernel
self.n_samples, self.dim = self.X.shape
self.alpha = np.zeros(self.n_samples)
self.b = 0
def fit(self, max_iter=10000, C=float('inf')):
for k in range(max_iter):
i, j = np.random.choice(self.n_samples, 2, replace=False)
Ei = self.predict(self.X[i]) - self.y[i]
Ej = self.predict(self.X[j]) - self.y[j]
eta = self.kernel(self.X[i], self.X[i]) + self.kernel(self.X[j], self.X[j]) - 2 * self.kernel(self.X[i], self.X[j])
alpha_i_unclipped = self.alpha[i] - self.y[i] * (Ei-Ej) / eta
alpha_i_clipped, alpha_j_clipped = 0, 0
if self.y[i] == self.y[j]:
K_constant = self.alpha[i] + self.alpha[j]
lower_bound = max(0, K_constant - C)
upper_bound = min(C, K_constant)
alpha_i_clipped = self.__clip(alpha_i_unclipped, lower_bound, upper_bound)
alpha_j_clipped = K_constant - alpha_i_clipped
else:
K_constant = self.alpha[i] - self.alpha[j]
lower_bound = max(0, K_constant)
upper_bound = min(C, C + K_constant)
alpha_i_clipped = self.__clip(alpha_i_unclipped, lower_bound, upper_bound)
alpha_j_clipped = alpha_i_clipped - K_constant
self.alpha[i], self.alpha[j] = alpha_i_clipped, alpha_j_clipped
if self.alpha[i] > 0 and self.alpha[i] < C:
self.b = self.__calculate_b(i)
elif self.alpha[j] > 0 and self.alpha[j] < C:
self.b = self.__calculate_b(j)
else:
self.b = (self.__calculate_b(i) + self.__calculate_b(j)) / 2.0
def __clip(self, alpha, L, H):
if alpha < L:
return L
elif alpha > H:
return H
else:
return alpha
def __calculate_b(self, ind):
return 1 - self.y[ind] * np.dot(self.y * self.alpha, self.kernel(self.X, self.X[ind]))
def predict(self, x):
x = np.array(x)
if len(x.shape) == 1:
return self.b + np.sum(self.alpha * self.y * self.kernel(self.X, x))
elif len(x.shape) == 2:
return self.b + np.dot(self.alpha * self.y, self.kernel(self.X, x.T))
def predict_label(self, x):
y_pred = self.predict(x)
return np.sign(y_pred)
def acc(pred, label):
return (pred == label).mean()
np.random.seed(0)
d = 5; n = 200
X_syn = [np.random.multivariate_normal(mean=np.random.normal(size=d), cov=np.identity(d) / 5, size=(100,)) for i in range(2)]
X_syn = np.vstack(X_syn)
y_syn = np.repeat([-1, 1], 100)
clf = SVM(X_syn, y_syn)
clf.fit()
print(f'acc = {acc(clf.predict_label(X_syn), y_syn)}')
df = load_breast_cancer()
X_real, y_real = df['data'], df['target']
X_real = (X_real - X_real.mean(0)) / X_real.std(0)
y_real = y_real * 2 - 1
clf_real = SVM(X_real, y_real, kernel=np.dot)
clf_real.fit()
print(f'acc of breast cancer = {acc(clf_real.predict_label(X_real), y_real)}')
最后此篇关于【机器学习】2.支持向量机的文章就讲到这里了,如果你想了解更多关于【机器学习】2.支持向量机的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
我的 processmaker 安装遇到了一些问题。我正在尝试使用本指南 [url]http://wiki.processmaker.com/index.php/ProcessMaker_Ubuntu
我正在使用 ShareKit。发送 SMS 消息使用 MFMessageComposeViewController,用户看到标题“文本”。我想将该标题更改为更能反射(reflect)实际可用内容的内容
我需要在我的一个针对 Gingerbread 的 Android 应用程序中使用操作栏和 fragment 的组合。所以我使用了 v7 支持库中的操作栏和 v4 支持库中的 fragment ,并使用
我明白为什么浏览器 vendor 不想帮助我阻止他们的 UI 线程。但是,我不明白为什么会有: Web Workers 中没有 sleep (2) 没有同步 WebSockets API 有一个syn
最近我的组织正在考虑使用 Docker。我们组使用的是cloudera CDH 5.1.2。 1) cloudera 是否与 Docker 容器兼容?2) docker 和cloudera 组合是否存
我正在尝试通过编译在 Mac 上安装 rsync 3.2.3。但是,我想安装所有功能。为此,它需要一些库,此处 ( https://download.samba.org/pub/rsync/INSTA
我一直在使用 PyDev 成功运行 nose 测试,并想试试 nose2。 所以我安装了它 pip install nose2 复制/粘贴来自 http://nose2.info/ 的示例代码进入名为
我想知道 LLVM 中是否有任何函数/方法可以在 LLVM IR 中添加 Open-MP 构造。 llvm-3.0 是否仍然支持 OpenMP 指令? 最佳答案 OpenMP 是一种高级语言扩展。因此
我对 CUDA 编程非常陌生。我正在浏览 SDK 附带的示例。我能够编译代码,但是当我运行它时,出现以下错误: "clock.cu(177) : CUDA Runtime API error 38:
RStudio 是用于 R 开发的出色 IDE。我想知道是否有任何方法可以很好地支持 HiDPI 分辨率? 我目前有 13 英寸显示器和 3200x1800 分辨率,甚至很难阅读 RStudio 选项
我正在寻找一种有助于为 Django 项目提供 RDF 支持的工具。 到目前为止,我发现了两个: django-rdf - 最后一次修改是在 4 年前,所以它看起来像是一个死项目。 djubby -
我刚刚尝试了一些 JS 核心原则,发现引擎评估链接的关系运算符而不会引发错误。相反,他们以我自己无法理解的方式进行评估。 console.log(1 4 > 3 > 2 > 1); //false,
我知道 etexteditor 和 vim/emacs。 是否有任何其他 Windows 编辑器支持类似 textmate 的片段(例如,您编写触发词,按 Tab,它更改为某些内容,再次按 Tab,它
我正在尝试找出验证给定集群的网络策略配置的最佳方法。 According to the documentation Network policies are implemented by the ne
很难说出这里问的是什么。这个问题是含糊的、模糊的、不完整的、过于宽泛的或修辞性的,无法以目前的形式得到合理的回答。如需帮助澄清此问题以便重新打开它,visit the help center 。 已关
Z3 会支持 AUFBV 吗? 对于以下脚本: (set-logic AUFBV) (declare-fun x () (_ BitVec 16)) (declare-const t (Array (
使用分部类编写 NUnit 测试的优缺点是什么? 我要开始了: 亲:可以测试私有(private)方法 缺点:TDD 不再可能了 还有什么? 最佳答案 缺点:要么您必须测试与您发布的版本不同的构建,要
它很容易(对于 90% 的 aop 特性)在没有任何语言本身支持的情况下做到这一点,就像大多数动态语言如 python 和 ruby 一样。然而,Dojo在 1.3.2 上直接支持它.最新版本发生
我在我的 android 应用程序中使用亚洲字符,我已经了解到某些字符无法显示,因为系统字体不支持它们。我查询了一个包含亚洲字符的数据库,并且经常检索到无法显示的标志。这些情况对我的应用程序来说通常不
你好,我想实现一个控件,我想在用户键入@字符时启用该控件,直到未填充运行文本中的空格为止,它应该显示用户列表,@符号后键入的文本应该显示基于键盘字符的建议,就像我们在上面看到的那样Twitter 或
我是一名优秀的程序员,十分优秀!