支持向量机(SVM)
前言
SVM（Support Vector Machine）是一种寻求最大分类间隔的机器学习方法，广泛应用于各个领域，许多人把SVM当做首选方法，它也被称之为最优分类器。
原理
图中有三个分类实例，都将数据正确分类，我们直观上看，会觉得图中第三个效果会比较好，而SVM是为了求间隔margin最大的那个平面即(效果比较好的那个平面）
$$w^Tx+b=0$$
对于这个平面，通过最开始的判断，它有这样几个条件
1.
$$\begin{matrix}
w^Tx+b>0 \quad y_n=1\\ w^Tx+b<0 \quad y_n=-1
\end{matrix}$$
$$y_n(w^Tx+b)>0$$
2.
$$margin(w,b)=\underset{n=1,\cdots,N}{min}distance(x_n,w,b)$$
通过此我们可以建立我们的目标问题
$$\underset{w,b}{max} \space\space\space margin(w,b) \\ subject\ to\space\space\space every\space\space\ y_n(w^Tx+b)>0 \\ \space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space margin(w,b)=\underset{n=1,\cdots,N}{min}distance(x_n,w,b)$$
对于distance我们可以利用线性代数中的知识化简
$$distance(x_n,w,b)= \left|\frac{w^T(x_n-x')}{\left ||w\right||} \right|=\left | \frac{w^Tx_n+b}{\left ||w\right||} \right |= \frac { y_n(w^Tx_n+b)}{\left ||w\right||}$$
我们作出假设,令
$$\underset{n=1,\cdots,N}{min}\space\space\space y_n(w^Tx_n+b) = 1$$
则求解答式子变为
$$\underset{b,w}{max} \space\space\space \frac {1}{\left ||w\right||} \\ subject\ to\space\space\space every\space\space\ y_n(w^Tx_n+b)\geq1$$
等价于
$$\underset{b,w}{min}\space \frac{1}{2}w^Tw \\ subject\ to\space\space\space \space\ y_n(w^Tx_n+b)\geq1\space for\space all \space n$$
一般我们考虑的都是非线性SVM，即将数据映射到高维
$$x_n\rightarrow z_n$$
此时这个式子不能仅通过枚举条件，要使用拉格朗日方法
首先，使用拉格朗日乘子法,原式化为
$$L(w,b,\alpha)= {\frac{1}{2}w^Tw}+\sum_{n=0}^N \alpha_n\underbrace{(1-y_n(w^Tz_n+b))}_{constraint}$$
同时通过证明，将弱对偶转为强对偶
$${\underset{b,w}{min}(\underset{all\space\alpha_n\geq0}{max}L(w,b,\alpha))}={\underset{all\space\alpha_n\geq0}{max}(\underset{b,w}{min}L(w,b,\alpha))}$$
接下来用对偶SVM来求解原问题，对偶SVM如下
$$\underset{all\space\alpha_n\geq0}{max}(\underset{b,w}{min}{\frac{1}{2}w^Tw+\sum_{n=1}^N \alpha_n(1-y_n(w^Tz_n+b))})$$
里面的最小化是没有约束条件的，约束条件在最大化上，于是我们可以取梯度为0来求极值
由$\frac{\partial L(w,b,\alpha)}{\partial b}=0$，得$\sum_{n=1}^N\alpha_ny_n=0$，代入对偶SVM，化简得
$$\underset{all\space\alpha_n\geq0,\sum_{n=1}^N\alpha_ny_n=0}{max}(\underset{b,w}{min}\frac{1}{2}w^Tw+\sum_{n=1}^N \alpha_n(1-y_n(w^Tz_n)))$$
由$\frac{\partial L(w,b,\alpha)}{\partial w}=0$，得$w=\sum_{n=1}^N\alpha_ny_nz_n$
原式化为
$$\underset{\alpha}{min}\space\space \frac{1}{2}\sum_{n=1}^N\sum_{m=1}^N\alpha_n\alpha_my_ny_mz_n^Tz_m-\sum_{n=1}^N\alpha_n\\subject\space to \space\space \sum_{n=1}^Ny_n\alpha_n=0;\alpha_n\geq0(for\space n=1,2,\cdots,N)$$
同时有一些约束条件(KTT条件)
(1) 原问题需满足$y_n(w^Tx_n+b)≥1$
(2) 对偶问题$αn≥0$
(3) 对偶问题最优解$\sum_{n=1}^N\alpha_ny_n=0,w=\sum_{n=0}^N\alpha_ny_nz_n$
(4) $α_n(1−y_n(w^Tx_n+b))=0$
SMO算法
序列最小最优化(sequential minimal optimization)算法，简称为SMO算法。
SMO算法的特点：不断地将原二次规划问题分解为只有两个变量的二次规划子问题，并对子问题进行解析求解，直到所有变量满足KKT条件为止。
SMO算法采用了一种启发式的方法。它每次只优化两个变量，将其他的变量都视为常数。
1.第一个变量的选择
SMO算法称选择第一个变量为外层循环，这个变量需要选择在训练集中违反KKT条件最严重的样本点。一般来说，我们首先选择$0<a_1<C$的点
2.第二个变量的选择
SMO算法称选择第二个变量为内层循环，假设我们在外层循环已经找到了$a_1$，第二个变量$a_2$的选择标准是让$|E_{1}−E_{2}|$有足够大的变化。由于$a_1$定了的时候，$E_{1}$也确定了，所以要想$|E_{1}−E_{2}|$最大，只需要在$E_{1}$为正时，选择最小的$E_{1}$作为$E_{2}$， 在$E_{1}$为负时，选择最大的$E_{1}$作为$E_{2}$，可以将所有的$E_{1}$保存下来加快迭代。
如果内存循环找到的点不能让目标函数有足够的下降,可以采用遍历支持向量点来做$a_2$，直到目标函数有足够的下降， 如果所有的支持向量做$a_2$都不能让目标函数有足够的下降，可以跳出循环，重新选择$a_1$。
3.阈值限制
当$y_{1} \ne y_{2}$时
1. $L = \max(0, \alpha_{2}^{old} - \alpha_{1}^{old})$
2. $H = \min(C, C + \alpha_{2}^{old} - \alpha_{1}^{old})$
当$y_{1} = y_{2}$时
1. $L = \max(0, \alpha_{1}^{old} + \alpha_{2}^{old} - C)$
2. $H = \min(C, \alpha_{2}^{old} + \alpha_{1}^{old})$
4.更换新值
令$\eta = K_{1, 1} + K_{2, 2} - 2K_{1, 2}$
$$\alpha_{2}^{new} = \alpha_{2}^{old} + \frac{y_{2}(E_{1} - E_{2})}{\eta}$$
$$\alpha_{1}^{new} = \alpha_{1}^{old} + y_{1}y_{2}(\alpha_{2}^{old} - \alpha_{2}^{new})$$
$$b^{new} = \frac{b_{1}^{new} + b_{2}^{new}}{2}$$
部分代码
def selectj(i, os, Ei):
maxK = 0
maxdeltaE = 0
Ej = 0
os.ecache[i] = [1, Ei]
validEcacheList = np.nonzero(os.ecache[:, 0].A)[0]
if (len(validEcacheList)) > 1:
for k in validEcacheList:
if k == i: continue
Ek = calcEi(os, k)
deltaE = abs(Ei - Ek)
if (deltaE > maxdeltaE):
maxK = k
maxdeltaE = deltaE
Ej = Ek
return maxK, Ej
else:
j = simple.otherselect(i, os.m)
Ej = calcEi(os, j)
return j, Ej
def innerL(i, oS):
Ei = calcEi(oS, i)
if ((oS.labelmat[i] * Ei < -oS.tol) and (oS.alphas[i] < oS.C)) or (
(oS.labelmat[i] * Ei > oS.tol) and (oS.alphas[i] > 0)):
j, Ej = selectj(i, oS, Ei)
alphaIold = oS.alphas[i].copy()
alphaJold = oS.alphas[j].copy()
if (oS.labelmat[i] != oS.labelmat[j]):
L = max(0, oS.alphas[j] - oS.alphas[i])
H = min(oS.C, oS.C + oS.alphas[j] - oS.alphas[i])
else:
L = max(0, oS.alphas[j] + oS.alphas[i] - oS.C)
H = min(oS.C, oS.alphas[j] + oS.alphas[i])
if L == H:
print("L==H")
return 0
eta = 2.0 * oS.X[i, :] * oS.X[j, :].T - oS.X[i, :] * oS.X[i, :].T - oS.X[j, :] * oS.X[j, :].T
if eta >= 0:
print("eta>=0")
return 0
oS.alphas[j] -= oS.labelmat[j] * (Ei - Ej) / eta
oS.alphas[j] = simple.clipalpha(oS.alphas[j], H, L)
updateEk(oS, j)
if (abs(oS.alphas[j] - alphaJold) < 0.00001):
print("alpha_j变化太小")
return 0
oS.alphas[i] += oS.labelmat[j] * oS.labelmat[i] * (alphaJold - oS.alphas[j])
updateEk(oS, i)
b1 = oS.b - Ei - oS.labelmat[i] * (oS.alphas[i] - alphaIold) * oS.X[i, :] * oS.X[i, :].T - oS.labelmat[j] * (
oS.alphas[j] - alphaJold) * oS.X[i, :] * oS.X[j, :].T
b2 = oS.b - Ej - oS.labelmat[i] * (oS.alphas[i] - alphaIold) * oS.X[i, :] * oS.X[j, :].T - oS.labelmat[j] * (
oS.alphas[j] - alphaJold) * oS.X[j, :] * oS.X[j, :].T
if (0 < oS.alphas[i]) and (oS.C > oS.alphas[i]):
oS.b = b1
elif (0 < oS.alphas[j]) and (oS.C > oS.alphas[j]):
oS.b = b2
else:
oS.b = (b1 + b2) / 2.0
return 1
else:
return 0
def smoP(dataMatIn, classLabels, C, toler, maxIter):
oS = optstruct(dataMatIn, classLabels, C, toler)
iter = 0
entireSet = True
alphaPairsChanged = 0
while (iter < maxIter) and ((alphaPairsChanged > 0) or (entireSet)):
alphaPairsChanged = 0
if entireSet:
for i in range(oS.m):
alphaPairsChanged += innerL(i, oS)
print("全样本遍历:第%d次迭代 样本:%d, alpha优化次数:%d" % (iter, i, alphaPairsChanged))
iter += 1
else: # 遍历非边界值
nonBoundIs = np.nonzero((oS.alphas.A > 0) * (oS.alphas.A < C))[0] # 遍历不在边界0和C的alpha
for i in nonBoundIs:
alphaPairsChanged += innerL(i, oS)
print("非边界遍历:第%d次迭代 样本:%d, alpha优化次数:%d" % (iter, i, alphaPairsChanged))
iter += 1
if entireSet: # 遍历一次后改为非边界遍历
entireSet = False
elif (alphaPairsChanged == 0): # 如果alpha没有更新,计算全样本遍历
entireSet = True
print("迭代次数: %d" % iter)
return oS.b, oS.alphas
结语
其实还有一个核KVM，就是对于映射到高维，我们希望找到一个对内积的函数使我们直接使用内积就可以表示高维数，没啥好写的，就是定义了新的处理函数，对数据处理，所以没写，SMO算法的数学推导也没写，太多了，下一篇应该是adaboost算法了
Comments | NOTHING