文章目录
-06学习报告线性回归LASSO 回归Ridge 岭回归感知机算法PLApocket算法线性判别分析逻辑回归高斯判别分析PCAhard-margin SVMsoft-margin SVM-06学习报告
本月学习机器学习常见算法,并做相应的数学推导。
具体的数学推导见文件夹中的pdf文件。本word是对上面的算法进行简单的总结。
机器学习模型 主要包括以下流程:
首先根据实际问题(比如 一些 先验信息的假设),思考自己的解决方案 (算法思路)将这个解决方案 用 数学的公式 表达出来,这个数学模型其实是一个最优化问题(建模)这个最优化问题 一般为 极大似然估计拉格朗日法获得误差损失函数loss 求解上面的最优化问题,一般方法: 如果好解,可以直接求偏导即可。如果样本很大,可以 使用 梯度下降法,每次用小样本集迭代更新参数如果不好解,可以假定其有隐藏变量,从而使用EM算法求解参数
下面,通过上面的流程理清各个算法:
线性回归
模型思路:我们可以用一条线y = wx+b尽可能逼进原样本点,但是
原本我们的样本x都是由模型f(w)生成的,但是在外界干扰的条件下,模型f(w)对x的输出(即y)会有所改变。我们 假设这个干扰 服从高斯分布 均值为0,方差为 σ
建成数学模型
误差干扰ε∼N(0,σ2)干扰下样本标签y=f(w)+ε=wTx+ε则y也服从正态分布y∣x:w∼N(wTx,σ2)即p(y∣x;w=12∗π∗σ∗exp−(y−wTx)22σ2)误差干扰 \ \ \varepsilon \sim N(0, \sigma^{2}) \\ 干扰下样本标签 \ \ \ y =f(w)+\varepsilon = w^Tx+\varepsilon \\ 则y也服从正态分布 \ \ \ y|x:w \sim N(w^Tx, \sigma^2) \\ 即\ \ \ p(y|x;w = \frac{1}{\sqrt{2*\pi}*\sigma}*exp{-\frac{(y-w^Tx)^2}{2\sigma^2}}) 误差干扰ε∼N(0,σ2)干扰下样本标签y=f(w)+ε=wTx+ε则y也服从正态分布y∣x:w∼N(wTx,σ2)即p(y∣x;w=2∗π∗σ1∗exp−2σ2(y−wTx)2)
转为优化问题(这里通过极大似然估计MLE)(如果是用损失函数的方法那就是最小二乘估计)
希望找到一组w,使得模型的似然P(Y∣X;w)=∏i=1Np(yi∣xi:w)最大化这里p(yi∣xi:w)上面已经给出,所以我们已经可以完全表示出模型的似然P(Y∣X;w)即w~=argmax(logP(Y∣X;w))希望找到一组w, 使得模型的似然\ \ P(Y|X;w) = \prod_{i=1}^{N}p(y_i|x_i:w) 最大化 \\ 这里p(y_i|x_i:w) 上面已经给出,所以我们已经可以完全表示出模型的似然 P(Y|X;w) \\ 即\ \ \widetilde{w}=argmax(log \ P(Y|X;w)) 希望找到一组w,使得模型的似然P(Y∣X;w)=i=1∏Np(yi∣xi:w)最大化这里p(yi∣xi:w)上面已经给出,所以我们已经可以完全表示出模型的似然P(Y∣X;w)即w=argmax(logP(Y∣X;w))
求解上面的最优化问题
使用梯度下降发,求偏导即可。(具体数学看文件夹里面的pdf)
求解出最终模型w=(xTx)−1xTY模型y=wTx求解出最终模型 \ \ w = (x^Tx)^{-1}x^TY \\ 模型 \ \ y = w^Tx 求解出最终模型w=(xTx)−1xTY模型y=wTx
模型其他重要知识点
线性回归也可使用最小二乘的思想建立模型,与上面不同的是,上面是最大化似然,而这里是最小化样本误差。二者最终还是通过梯度下降法求解参数
事实上,最小二乘估计 就是 干扰服从高斯分布(均值为0)的极大似然法则
即最小二乘的argmin(loss) 就相对于 MLE的argmax(P(Y|X:w))
正则化的频率派 == 贝叶斯派
LASSO 回归
与上面线性回归类似,只是在上面的模型上加了一个L1正则化
w~=argmin(loss+λ∣∣w∣∣)\widetilde{w}=argmin(loss + \lambda ||w||) w=argmin(loss+λ∣∣w∣∣)
Ridge 岭回归
与上面线性回归类似,只是在上面的模型上加了一个L2正则化
w~=argmin(loss+λwTw)\widetilde{w}=argmin(loss + \lambda w^Tw) w=argmin(loss+λwTw)
感知机算法PLA
模型思想:
首先前提要求样本数据是线性可分的。现在就找一条线y=wTx将样本分开,且错误的情况尽可能的小首先前提要求样本数据是线性可分的。 \\ 现在就找一条线y=w^Tx 将样本分开,且错误的情况尽可能的小 首先前提要求样本数据是线性可分的。现在就找一条线y=wTx将样本分开,且错误的情况尽可能的小
建成数学模型
f(x)=sign(wTx)sign(a)={+1a>=0−1a<0f(x) = sign(w^Tx) \\ sign(a) = \left\{\begin{matrix} +1& a>=0 \\ -1& a<0 \end{matrix}\right. f(x)=sign(wTx)sign(a)={+1−1a>=0a<0
转为优化问题(这里通过构建损失函数loss)
想要分错的个数尽可能的少,即Loss(w)=∑i=1N−yiwTxi注意:wTxi>0yi=+1wTxi<0yi=−1}==>yiwTxi>0表示样本(xi,yi)被正确分类,yiwTxi<0表示样本(xi,yi)被错误分类想要分错的个数尽可能的少 ,即\\ Loss(w) = \sum_{i=1}^{N}-y_iw^Tx_i \\ 注意:\left.\begin{matrix} w^Tx_i>0&y_i=+1 \\ w^Tx_i<0&y_i=-1 \end{matrix}\right\}==>y_iw^Tx_i>0表示样本(x_i,y_i)被正确分类,y_iw^Tx_i<0表示样本(x_i,y_i)被错误分类 想要分错的个数尽可能的少,即Loss(w)=i=1∑N−yiwTxi注意:wTxi>0wTxi<0yi=+1yi=−1}==>yiwTxi>0表示样本(xi,yi)被正确分类,yiwTxi<0表示样本(xi,yi)被错误分类
注意不要使用Loss(w)=∑i=1NI(yiwTxi<0),因为这个函数不好求导注意不要使用Loss(w) = \sum_{i=1}^{N}I(y_iw^Tx_i<0),因为这个函数不好求导 注意不要使用Loss(w)=i=1∑NI(yiwTxi<0),因为这个函数不好求导
求解上面的最优化问题
使用梯度下降法,求偏导即可
求解出最终模型w=w+λyixi模型y=sign(wTx)求解出最终模型 \ \ w = w+\lambda y_ix_i \\ 模型 \ \ y = sign(w^Tx) 求解出最终模型w=w+λyixi模型y=sign(wTx)
模型其他重要知识点
知道发展趋势: 感知机 ----> 多层感知机(神经网络)----->深度学习
PLA算法可以理解为 错误驱动算法。
上面结论中,w的迭代方式为
w=w+λyixiw = w+\lambda y_ix_i w=w+λyixi
这个来一个错误样本,就对w进行一次更新,其实就是来一个样本就微调一次分割线。具体可见林轩田的/MosBest/article/details/52029217
PLA算法具有局限性
当遇到一个错误样本(x_i, y_i),微调一次w后,改正后的w可以使得(x_i, y_i)分类正确。但是前面的0~i-1个样本,可能分类结果发生改变。
即PLA只有运行到最后,最终的模型才有效。中间的w不能用。
PLA前提必须要求样本集线性可分。不然w迭代不会收敛。
pocket算法
pocket算法是PLA的一种改进。
pocket算法是一种贪心算法的思想。即w在迭代的过程中
w=w+λyixiw = w+\lambda y_ix_i w=w+λyixi
如果迭代后w可以使得前面i个样本都分类正确,那么修改w, 否则跳过本次修改,直接进行下一步迭代。
所以,pocket算法手里拿着的参数w永远是当前最优的解。
线性判别分析
模型思路
线性判别分析是一种降维的思想。它将样本从高维重新投射到低维,认为样本在重新构建的低维特征中是可以线性可分的。
( 这个和SVM的核方法正好相反。SVM核方法是将样本从低维投射到高维,认为样本在高维是可以线性可分 )
建模思想: **类内小,类间大 **
可以理解为 高类聚,低耦合。即将样本集投射到低维后,相同类别的样本的方差小(高类聚),不同类别的样本的均值离得很远(低耦合)
建成数学模型
假设是二分类问题,则样本集N可分为类别1的样本N1,类别1的样本N2.其中N=N1+N2新的低维特征为w则样本xi在向量w上的投影值为zi=wTxi(如果不理解,看文件夹中的pdf有详细证明)则类别1的均值为z1‾=1N1∑i=1N1wTxi则类别1的方差为S1‾=1N1∑i=1N1(wTxi−z1‾)(wTxi−z1‾)T假设是二分类问题,则样本集N可分为类别1的样本N1, 类别1的样本N2. \ \ 其中N = N1+N2 \\ 新的低维特征为 w \\ 则样本x_i在向量w上的投影值为z_i = w^Tx_i \ \ (如果不理解,看文件夹中的pdf有详细证明)\\ 则类别1的均值为\overline{z_1} =\frac{1}{N_1} \sum_{i=1}^{N_1}w^Tx_i \\ 则类别1的方差为\overline{S_1} =\frac{1}{N_1} \sum_{i=1}^{N_1}(w^Tx_i-\overline{z_1})(w^Tx_i-\overline{z_1})^T \\ 假设是二分类问题,则样本集N可分为类别1的样本N1,类别1的样本N2.其中N=N1+N2新的低维特征为w则样本xi在向量w上的投影值为zi=wTxi(如果不理解,看文件夹中的pdf有详细证明)则类别1的均值为z1=N11i=1∑N1wTxi则类别1的方差为S1=N11i=1∑N1(wTxi−z1)(wTxi−z1)T
则类别2的均值为z2‾=1N2∑i=2N1wTxi则类别2的方差为S2‾=1N2∑i=1N2(wTxi−z2‾)(wTxi−z2‾)T则类间:(z1‾−z2‾)2类内:S1+S2则类别2的均值为\overline{z_2} =\frac{1}{N_2} \sum_{i=2}^{N_1}w^Tx_i \\ 则类别2的方差为\overline{S_2} =\frac{1}{N_2} \sum_{i=1}^{N_2}(w^Tx_i-\overline{z_2})(w^Tx_i-\overline{z_2})^T \\ 则 类间:(\overline{z_1} - \overline{z_2})^2 \\ 类内:S_1+S_2 则类别2的均值为z2=N21i=2∑N1wTxi则类别2的方差为S2=N21i=1∑N2(wTxi−z2)(wTxi−z2)T则类间:(z1−z2)2类内:S1+S2
则类间:(z1‾−z2‾)2类内:S1+S2则类内小,类间大可表示为J(w)=(z1‾−z2‾)2S1+S2则 类间:(\overline{z_1} - \overline{z_2})^2 \\ 类内:S_1+S_2 \\ 则类内小,类间大可表示为J(w) = \frac{(\overline{z_1} - \overline{z_2})^2}{S_1+S_2} 则类间:(z1−z2)2类内:S1+S2则类内小,类间大可表示为J(w)=S1+S2(z1−z2)2
转为优化问题
这里是自定义的一个优化函数:最大化 类内小,类间大J(w)
argmaxJ(w)=(z1‾−z2‾)2S1+S2argmax \ \ J(w) = \frac{(\overline{z_1} - \overline{z_2})^2}{S_1+S_2} argmaxJ(w)=S1+S2(z1−z2)2
求解上面的最优化问题
涉及到矩阵运算,求偏导。(不是用梯度下降法)
w=λ∗(xc1‾−xc2‾)即,最终的w就是两个类别样本均值点连起来的方向。w = \lambda *( \overline{x_{c1}} - \overline{x_{c2}})\\ 即,最终的w就是两个类别样本均值点连起来的方向。 w=λ∗(xc1−xc2)即,最终的w就是两个类别样本均值点连起来的方向。
逻辑回归
模型思路
逻辑回归是一个概率判别模型。是要对P(y|x)进行建模,即给定样本x时,计算它的标签y=k的概率值,然后选择概率最大的类别作为它的标签。
建成数学模型
逻辑回归已给定:对p(y∣x)建模时,使用sigmoid函数p1=p(y=1∣x)=11+exp{−wTx}p0=p(y=0∣x)=1−p1=exp{−wTx}1+exp{−wTx}p(y∣x)=p1y∗p01−y逻辑回归已给定:对p(y|x)建模时,使用sigmoid 函数 \\ p1 = p(y=1|x) = \frac{1}{1+exp\{-w^Tx\}} \\ p0 = p(y=0|x) = 1 - p1 = \frac{exp\{-w^Tx\}}{1+exp\{-w^Tx\}} \\ p(y|x) = p_1^y*p_0^{1-y} 逻辑回归已给定:对p(y∣x)建模时,使用sigmoid函数p1=p(y=1∣x)=1+exp{−wTx}1p0=p(y=0∣x)=1−p1=1+exp{−wTx}exp{−wTx}p(y∣x)=p1y∗p01−y
转为优化问题
使用极大似然估计MLE
MLEw‾=argmax(log(P(Y∣X)))=argmax(log∏i=1Np(y+i∣xi))MLE \ \ \ \overline{w} = argmax(log(P(Y|X))) = argmax(log \prod_{i=1}^{N}p(y+i|x_i)) MLEw=argmax(log(P(Y∣X)))=argmax(logi=1∏Np(y+i∣xi))
求解上面的最优化问题
求偏导,梯度下降法
模型其他重要知识点
事实上,你咋计算时,你会发现
极大似然 argmax P(Y|X) 相对于 最小化loss argmin loss . (在逻辑回归中你会发现loss function就是交叉熵)
即在逻辑回归中 极大似然法则 == 最小化交叉熵
高斯判别分析
模型思路
先假设
标签y服从伯努利分布(假设2分类)每一个类别的样本集都服从高斯分布。且不同类别的样本集之间均值不同,但是方差相同。
模型和逻辑回归类型,也是对p(y|x)进行建模。不同的是,逻辑回归使用sigmoid函数,而高斯判别分析使用的是贝叶斯定理。
p(yi∣xi)∝p(xi∣yi)∗p(yi)因为我们这里最后只需比较样本xi取各个标签的概率大小,没必要把概率值求出来。所以分母不用求,因为大家的分母都是一样的大小。p(y_i|x_i) \propto p(x_i|y_i)*p(y_i) \\ 因为我们这里最后只需比较样本x_i取各个标签的概率大小,没必要把概率值求出来。所以分母不用求,因为大家的分母都是一样的大小。 p(yi∣xi)∝p(xi∣yi)∗p(yi)因为我们这里最后只需比较样本xi取各个标签的概率大小,没必要把概率值求出来。所以分母不用求,因为大家的分母都是一样的大小。
建成数学模型
其中y服从伯努利分布(公式就不写了)p(xi∣yi)服从高斯分布p(yi∣xi)∝p(xi∣yi)∗p(yi)则只要求出上面分布的参数,就可求出p(yi∣xi)y‾=argmax(p(y∣x))=argmax(p(y)p(x∣y))其中 y服从伯努利分布(公式就不写了)\\ p(x_i|y_i)服从高斯分布 \\ p(y_i|x_i) \propto p(x_i|y_i)*p(y_i) \\ 则只要求出上面分布的参数,就可求出p(y_i|x_i) \\ \overline y = argmax(p(y|x))=argmax(p(y)p(x|y)) 其中y服从伯努利分布(公式就不写了)p(xi∣yi)服从高斯分布p(yi∣xi)∝p(xi∣yi)∗p(yi)则只要求出上面分布的参数,就可求出p(yi∣xi)y=argmax(p(y∣x))=argmax(p(y)p(x∣y))
转为优化问题
极大似然估计
L(θ)=log∏i=1NP(yi∣xi)=log∏i=1NP(xi∣yi)∗P(yi)=log∏i=1NP(xi,yi)θ=argmaxL(θ)L(\theta)=log \prod_{i=1}^{N}P(y_i|x_i)=log \prod_{i=1}^{N}P(x_i|y_i)*P(y_i)=log \prod_{i=1}^{N}P(x_i,y_i)\\ \theta = argmax \ \ L(\theta) L(θ)=logi=1∏NP(yi∣xi)=logi=1∏NP(xi∣yi)∗P(yi)=logi=1∏NP(xi,yi)θ=argmaxL(θ)
求解上面的最优化问题
求偏导
伯努利分布的参数:ϕ1=N1/Nϕ2=N2/N则我们就可以表示出p(y1)和p(y2)了高斯分布的参数:u1=∑i=1NyixiN1u2=∑i=1NyixiN2方差S=没算则我们就可以表示出p(xi∣yi)最终我们就可以通过p(yi∣xi)∝p(xi∣yi)∗p(yi)比较概率,得出样本标签伯努利分布的参数:\phi_1 = N_1/N \ \ \ \ \ \ \phi_2 = N_2/N \\ 则我们就可以表示出p(y_1)和p(y_2)了 \\ 高斯分布的参数:u_1 = \frac{\sum_{i=1}^{N}y_ix_i}{N_1} \ \ \ \ \ \ u_2 = \frac{\sum_{i=1}^{N}y_ix_i}{N_2} \ \ \ \ \ 方差S = 没算 \\ 则我们就可以表示出p(x_i|y_i)\\ 最终我们就可以通过p(y_i|x_i) \propto p(x_i|y_i)*p(y_i) \ \ 比较概率,得出样本标签 伯努利分布的参数:ϕ1=N1/Nϕ2=N2/N则我们就可以表示出p(y1)和p(y2)了高斯分布的参数:u1=N1∑i=1Nyixiu2=N2∑i=1Nyixi方差S=没算则我们就可以表示出p(xi∣yi)最终我们就可以通过p(yi∣xi)∝p(xi∣yi)∗p(yi)比较概率,得出样本标签
PCA
模型思路
PCA是用于降维的,希望将 高维的具有相关性的特征 降成 低维的无关的特征
思想:
有两个,这两个本质上相同。
最大投影方差最小重构距离
下面仅仅讲最大投影方差的原理,而最小重构距离看pdf即可。
建成数学模型
首先要将样本中心化xi−x‾令新的特征为u,其模值为1,即uTu=1。则点xi−x‾在向量u上的投影值为(xi−x‾)Tu则样本xi−x‾的投影方差为((xi−x‾)Tu−0)2则N个样本的总方差为J=1N∑i=1N((xi−x‾)Tu−0)2=...=uTSu我们的目标就是找到合适的u,使得总投影方差J最大。而这个u就是我们的新特征首先要将样本 中心化x_i-\overline x \\ 令新的特征为u,其模值为1,即u^Tu = 1。则点x_i-\overline x在向量u上的投影值为(x_i-\overline x)^Tu\\ 则样本x_i-\overline x的投影方差为((x_i-\overline x)^Tu - 0)^2\\ 则N个样本的总方差为J = \frac{1}{N}\sum_{i=1}^{N}((x_i-\overline x)^Tu - 0)^2=...=u^TSu\\ 我们的目标就是找到合适的u,使得总投影方差J最大。\\ 而这个u就是我们的新特征 首先要将样本中心化xi−x令新的特征为u,其模值为1,即uTu=1。则点xi−x在向量u上的投影值为(xi−x)Tu则样本xi−x的投影方差为((xi−x)Tu−0)2则N个样本的总方差为J=N1i=1∑N((xi−x)Tu−0)2=...=uTSu我们的目标就是找到合适的u,使得总投影方差J最大。而这个u就是我们的新特征
转为优化问题
拉格朗日定理
J=1N∑i=1N((xi−x‾)Tu−0)2=...=uTSuu‾=argmaxJ=argmaxuTSu且要求uTu=1则可供偶见拉格朗日定理,L(u,λ)=uTSu+λ(1−uTu)J = \frac{1}{N}\sum_{i=1}^{N}((x_i-\overline x)^Tu - 0)^2=... = u^TSu\\ \overline u = argmax\ \ J= argmax\ \ u^TSu \ \ \ \ \ 且要求u^Tu = 1 \\ 则可供偶见拉格朗日定理,L(u,\lambda) = u^TSu+\lambda(1-u^Tu) J=N1i=1∑N((xi−x)Tu−0)2=...=uTSuu=argmaxJ=argmaxuTSu且要求uTu=1则可供偶见拉格朗日定理,L(u,λ)=uTSu+λ(1−uTu)
求解上面的最优化问题
求偏导, 得
Su=λu其中S是样本集的协方差矩阵,则,根据线性代数,要求解的特征u就是要求样本集的协方差矩阵的特征向量。即新特征u是样本的协方差矩阵的特征向量Su = \lambda u \\ 其中S是样本集的协方差矩阵, 则,根据线性代数,要求解的特征u就是要求样本集的协方差矩阵的特征向量。\\ 即新特征u是样本的协方差矩阵的特征向量 Su=λu其中S是样本集的协方差矩阵,则,根据线性代数,要求解的特征u就是要求样本集的协方差矩阵的特征向量。即新特征u是样本的协方差矩阵的特征向量
hard-margin SVM
模型思路
这里假设样本数据本就线性可分。
在感知机算法中,我们是只要找一条分割线将样本集分开即可。但是,一般满足这样的分割线(能够全部正确分类样本)其实有很多条,那么如何从这些分割线选出最优的一条,使得这条分割线的健壮性,容错性更强。
SVM就是用来干这个的。
思想:SVM是最大间隔分类器,在数据本就可分的前提下,我们希望我们的分割线离它最近的样本点尽可能的远。
建成数学模型
最开始为:
maxmargin(w,b)s.t.wTxi+b>0,yi=+1;wTxi+b<0,yi=−1max \ \ \ margin(w,b) \\ s.t. w^Tx_i+b > 0, y_i = +1;\\ w^Tx_i+b < 0, y_i = -1\\ maxmargin(w,b)s.t.wTxi+b>0,yi=+1;wTxi+b<0,yi=−1
其中
maxmargin(w,b)化简为min12wTw具体看pdf,主要用到w,b可以等比缩放所以,就变为min12wTws.t.wTxi+b>0,yi=+1;wTxi+b<0,yi=−1max margin(w,b) \ \ 化简为\ \ min \frac{1}{2}w^Tw \\ 具体看pdf, 主要用到w,b可以等比缩放\\ 所以,就变为\\ min \frac{1}{2}w^Tw \\ s.t. w^Tx_i+b > 0, y_i = +1;\\ w^Tx_i+b < 0, y_i = -1\\ maxmargin(w,b)化简为min21wTw具体看pdf,主要用到w,b可以等比缩放所以,就变为min21wTws.t.wTxi+b>0,yi=+1;wTxi+b<0,yi=−1
转为优化问题
将上面的优化问题,
先利用拉格朗日定理把带约束的优化问题转为无约束的优化问题
L(w,b,λ)=12wTw+∑i=1Nλi(1−yi(wTxi+b))minw,bmaxλL(w,b,λ)s.t.λi>=0L(w,b,\lambda) = \frac{1}{2}w^Tw+\sum_{i=1}^{N}\lambda_i(1-y_i(w^Tx_i+b))\\ min_{w,b} \ \ max_{\lambda} \ \ L(w,b,\lambda) \\ s.t. \ \ \lambda_i>=0 L(w,b,λ)=21wTw+i=1∑Nλi(1−yi(wTxi+b))minw,bmaxλL(w,b,λ)s.t.λi>=0
然后利用强对偶关系
L(w,b,λ)=12wTw+∑i=1Nλi(1−yi(wTxi+b))maxw,bminλL(w,b,λ)s.t.λi>=0L(w,b,\lambda) = \frac{1}{2}w^Tw+\sum_{i=1}^{N}\lambda_i(1-y_i(w^Tx_i+b))\\ max_{w,b} \ \ min_{\lambda} \ \ L(w,b,\lambda) \\ s.t. \ \ \lambda_i>=0 L(w,b,λ)=21wTw+i=1∑Nλi(1−yi(wTxi+b))maxw,bminλL(w,b,λ)s.t.λi>=0
对 min的一次偏导计算,得到
minλ12∑i=1N∑j=1NλiλjyiyjxiTxj−∑i=1Nλis.t.λi>=0∑i=1Nλiyj=0min_{\lambda} \frac{1}{2} \sum_{i=1}{N} \sum_{j=1}^{N} \lambda_i\lambda_jy_iy_jx_i^Tx_j-\sum_{i=1}^{N}\lambda_i \\ s.t. \lambda_i >=0 \\ \sum_{i=1}{N} \lambda_iy_j=0 minλ21i=1∑Nj=1∑NλiλjyiyjxiTxj−i=1∑Nλis.t.λi>=0i=1∑Nλiyj=0
求解上面的最优化问题
先求偏导,然后利用KKT条件(特别是其中中松弛互补条件),可得
w∗=∑i=0Nλiyixib∗=yk−∑i=0NλiyixiTxkw^*=\sum_{i=0}^{N}\lambda_iy_ix_i\\ b^*=y_k-\sum_{i=0}^{N}\lambda_iy_ix_i^Tx_k w∗=i=0∑Nλiyixib∗=yk−i=0∑NλiyixiTxk
最终的模型为
f(x)=sign(w∗x+b∗)f(x) = sign(w^*x+b^*) f(x)=sign(w∗x+b∗)
soft-margin SVM
模型思路
上面讲解hard-margin SVM时,我们假设了样本时线性可分的。
但是实际情况下,因为外界干扰等因素,样本(x,y)实际上是有波动的。
为了能够让我们的模型可以适应这种情况(即模型允许有少量的误差),我们就引入soft-margin SVM.
建成数学模型
我们的分割面方程为wx+b = 0, 则wx+b = 1 和 wx+b = -1 正好经过 模型的两个支持向量。
为了能让SVM允许有少量误差,我就假定支持向量可以适当的向wx+b=0移动一些,则经过该支持向量的超平面将会变成 wx+b=+1- \xi 或者 wx+b=-1 + \xi
即
yi(wTxi+b)=1−ξi这个ξi就相对于是样本xi的误差,则总loss=C∑i=1Nξi则最终的模型是在hard−marginSVM的基础上再加上loss=C∑i=1Nξiy_i(w^Tx_i+b)=1-\xi_i \\ 这个\xi_i就相对于是样本x_i的误差,则总loss = C\sum_{i=1}^{N}\xi_i \\ 则最终的模型是在hard-margin SVM的基础上再加上loss = C\sum_{i=1}^{N}\xi_i\\ yi(wTxi+b)=1−ξi这个ξi就相对于是样本xi的误差,则总loss=Ci=1∑Nξi则最终的模型是在hard−marginSVM的基础上再加上loss=Ci=1∑Nξi
所以,最终模型为
ξi=1−yi(wTxi+b)minw,b12wTw+C∑i=1Nξis.t.yi(wTxi+b)>=1−ξiξi>=0\xi_i=1-y_i(w^Tx_i+b)\\ min_{w,b} \frac{1}{2}w^Tw+C\sum_{i=1}^{N}\xi_i \\ s.t. y_i(w^Tx_i+b)>=1-\xi_i\\ \xi_i>=0 ξi=1−yi(wTxi+b)minw,b21wTw+Ci=1∑Nξis.t.yi(wTxi+b)>=1−ξiξi>=0
转为优化问题
同hard-margin SVM
求解上面的最优化问题
同hard-margin SVM
如果觉得《机器学习---背后数学原理--总结》对你有帮助,请点赞、收藏,并留下你的观点哦!