支持向量机与核函数

Share

支持向量机，support vector machines，简称SVM。一下全文基本都是用SVM一词。

先将这个复杂的概念化小，个人理解，SVM就是很好的现成的分类器，这里的“现成”指的是分类器不加修改即可直接使用。同时，这就意味着数据上应用基本形式的SVM分类器就可以得到低错误率的结果。SVM能够对训练集之外的数据点做出很好的分类决策。

本文主要介绍当前比较流行的SMO算法与核函数。

关于具体的SVM算法可以参考我的这篇笔记
SVM and Kernels

原理–基于最大间隔分隔数据

支持向量机
优点：泛华错误率低，计算开销不大，结果易解释
缺点：对参数调节和核函数的选择敏感，原始分类器不加修改仅适用于处理二类问题
使用数据类型：数值型和标称型数据

在介绍SVM这个主题之前，先解释几个概念。

假设现在有一组二维数据，它的数据点之间已经分隔的足够开，因此很容易就可以画出一条直线将其分为两组数据。在这种情况下，这组数据被称为线性可分(linearly separable)。大家先不用担心上诉假设过于完美，稍后当直线不能将数据点分开时，我们会对上诉假设做出一些调整。

上诉将数据集分开的直线称为分隔超平面(separating hyperplane)。在上面给出的例子中，由于给的是二维的数据集，因此此时的超平面就只是一条直线。如果所给的数据集是三维的，那么他就是一个平面。显而易见，更高维的以此类推。但是超过四维的就已经超出可描绘的范围了，此时我们称该可以区分边界的对象为超平面(hyperplane)，也就是分类的决策边界。分布在超平面一侧的所有数据都属于某个类别，而分布在另一侧的所有数据则属于另一个类别。

我们希望采用这种方式来构建分类器，即如果数据点离决策边界越远，那么其最后预测的结果就越可信。

但是有时能区分数据的直线或者平面不止一个，此时我们首先可能想到的就是做类似于直线拟合的操作，但是这并非最佳方案。我们希望能找到离分隔超平面最近的点，确保他们离分隔面尽可能远。这里点到分隔面的距离称为“间隔”(margin)。我们希望间隔尽可能的大，这是因为如果我们犯错或者在有限数据集上训练分类器的话，我们希望分类器尽可能功能完善并健壮。

支持向量(support vector)就是离分隔超平面最近的那些点。接下来我们要试着最大化支持向量到分隔面的距离，需要寻求此问题的优化求解方法。

寻找最大间隔

关于这个问题的理论求解在本文开头时的那篇链接的文章中已经介绍的很全面了，这里就不多费口舌讲解集体的数学过程。

所以我们直接跳到SVM的一般流程，若你对数学推导很有兴趣那么就强烈建议你先去看那篇文章。

SVM的一般流程

1
2
3
4
5
6
1）收集数据
2）准备数据：需要数值型数据
3）分析数据：有助于可视化分隔超平面
4）训练算法：SVM的大部分时间都源自训练，该过程主要实现两个参数的调优
5）测试算法：十分简单的计算过程
6）使用算法：几乎所有分类问题都可以使用SVM，值得一提的是，SVM本身是一个二类分类器，对多类问题应用SVM需要对代码进行一些修改

SMO–高效优化算法

1996年，John Platt发布了一个称谓SMO的强大算法，用于训练SVM。SMO表示序列最小优化(sequential minimal optimization)。Platt的SMO算法是将大优化问题分解为多个小优化问题来求解的。这些小优化问题往往很容易求解，并且对他们进行顺序求解的结果与将他们作为整体来求解的结果完全一致。与此同时，SMO算法的求解时间短很多。

SMO算法的目标是求出一系列 alpha 和 b ， 一旦求出了这些 alpha，就很容易计算出权重向量 w 并得到分隔超平面。

SMO算法的工作原理：每次循环中选择两个 alpha 进行优化处理。一旦找到一对合适的 alpha，那么久增大其中一个同时减小另一个。这里所谓的“合适”是指两个 alpha 必须要符合一定的条件，条件之一就是这两个 alpha 必须要在间隔边界之外，而其中第二个条件是这两个 alpha 还没有进行过区间化处理或者不在边界上。

Platt的SMO算法的完整实现需要实现大量的代码。所以我们由浅入深，先将其进行简化处理，以便了解算法的基本工作思路，之后再基于简化版给出完整版。简化版的代码虽然量少，但是执行速度慢。Platt SMO算法中的外循环确定要优化的最佳 alpha 对。而简化版却会跳过这一部分，首先在数据集上做一次遍历，遍历每一个 alpha，然后在剩余的 alpha 集合中随机选择另一个 alpha，从而构成 alpha 对。这里有一点相当重要，就是我们要同时改变两个 alpha。之所以这样做是因为我们有个约束条件：

∑αi*label(i) = 0

由于单独改变一个 alpha 可能会导致该约束条件失效，因此我们总是同时调整两个 alpha。

此外，我们构建一个辅助函数，用于在某个区间范围内随机选择一个整数。同时，我们也需要了另一个辅助函数，用于在数值太大时对其进行调整。下面的代码实现了这两个函数。首先新建一个叫 svmMLiA.py 的文件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def loadDataSet(fileName):
    dataMat = []; labelMat = []
    fr = open(fileName)
    for line in fr.readlines():
        lineArr = line.strip().split('\t')
        dataMat.append([float(lineArr[0]), float(lineArr[1])])
        labelMat.append(float(lineArr[2]))
    return dataMat,labelMat

def selectJrand(i,m):
    j=i #we want to select any J not equal to i
    while (j==i):
        j = int(random.uniform(0,m))
    return j

def clipAlpha(aj,H,L):
    if aj > H: 
        aj = H
    if L > aj:
        aj = L
    return aj

上诉代码中，第一个函数就是常见的 loadDatSet() 函数，该函数的功能显而易见。

第二个函数 selectJrand() 有两个参数值，其中 i 是第一个 alpha 的下标，m 是所有 alpha 的数目。只要函数值不等于输入值 i，函数就会进行随机选择。

最后一个辅助函数是 clipAlpha()，它是用于调整大于H 或小于 L 的 alpha 值。

尽管上诉三个辅助函数本身做的事情不是很多，但在分类器中却很有用。

然后我们进入到python环境中，输入如下语句，看看预期效果。

1
2
3
import svmPLiA
dataArr, labelArr = avmPLiA.loadDataSet('testSet.txt')
labelArr

从输出结果中我们可以看出，这里采用的类别标签是-1和1，而不是0和1。

上诉工作完成后就可以实现SMO的第一个版本了，伪代码如下：

1
2
3
4
5
6
7
8
创建一个 alpha 向量并将其初始化为零向量
当迭代次数小于最大迭代次数时（外循环）
	对数据集中的每个数据向量（内循环）：
		如果该数据可以被优化：
			随机选择另外一个数据向量
			同时优化这两个向量
			如果两个向量都不能被优化，退出内循环
		如果所有向量都没有被优化，增加迭代数目，进行下一次循环

接下来就是代码部分了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
def smoSimple(dataMatIn, classLabels, C, toler, maxIter):
    dataMatrix = mat(dataMatIn); labelMat = mat(classLabels).transpose()
    b = 0; m,n = shape(dataMatrix)
    alphas = mat(zeros((m,1)))
    iter = 0
    while (iter < maxIter):
        alphaPairsChanged = 0
        for i in range(m):
            fXi = float(multiply(alphas,labelMat).T*(dataMatrix*dataMatrix[i,:].T)) + b
            Ei = fXi - float(labelMat[i])#if checks if an example violates KKT conditions
            # 如果 alpha 可以更改进入优化过程
            if ((labelMat[i]*Ei < -toler) and (alphas[i] < C)) or ((labelMat[i]*Ei > toler) and (alphas[i] > 0)):
            	# 随机选择第二个 alpha
                j = selectJrand(i,m)
                fXj = float(multiply(alphas,labelMat).T*(dataMatrix*dataMatrix[j,:].T)) + b
                Ej = fXj - float(labelMat[j])
                alphaIold = alphas[i].copy(); alphaJold = alphas[j].copy();
                # 保证 alpha 在 0 与 C 之间
                if (labelMat[i] != labelMat[j]):
                    L = max(0, alphas[j] - alphas[i])
                    H = min(C, C + alphas[j] - alphas[i])
                else:
                    L = max(0, alphas[j] + alphas[i] - C)
                    H = min(C, alphas[j] + alphas[i])
                if L==H: print "L==H"; continue
                eta = 2.0 * dataMatrix[i,:]*dataMatrix[j,:].T - dataMatrix[i,:]*dataMatrix[i,:].T - dataMatrix[j,:]*dataMatrix[j,:].T
                if eta >= 0: print "eta>=0"; continue
                alphas[j] -= labelMat[j]*(Ei - Ej)/eta
                alphas[j] = clipAlpha(alphas[j],H,L)
                if (abs(alphas[j] - alphaJold) < 0.00001): print "j not moving enough"; continue
                # 对 i 进行修改，修改量与 j 相同，但方向相反
                alphas[i] += labelMat[j]*labelMat[i]*(alphaJold - alphas[j])
                # 设置常数项
                b1 = b - Ei- labelMat[i]*(alphas[i]-alphaIold)*dataMatrix[i,:]*dataMatrix[i,:].T - labelMat[j]*(alphas[j]-alphaJold)*dataMatrix[i,:]*dataMatrix[j,:].T
                b2 = b - Ej- labelMat[i]*(alphas[i]-alphaIold)*dataMatrix[i,:]*dataMatrix[j,:].T - labelMat[j]*(alphas[j]-alphaJold)*dataMatrix[j,:]*dataMatrix[j,:].T
                if (0 < alphas[i]) and (C > alphas[i]): b = b1
                elif (0 < alphas[j]) and (C > alphas[j]): b = b2
                else: b = (b1 + b2)/2.0
                alphaPairsChanged += 1
                print "iter: %d i:%d, pairs changed %d" % (iter,i,alphaPairsChanged)
        if (alphaPairsChanged == 0): iter += 1
        else: iter = 0
        print "iteration number: %d" % iter
    return b,alphas

这个函数可能比较大，咱们慢慢来看。

上诉函数首先先将多个列表和输入参数转换成 NumPy 矩阵，这样就可以简化很多数学操作。由于转置了类别标签，因此我们得到的是一个列向量而不是列表。于是类别标签向量的每行元素都与数据矩阵中的行一一对应。我们也可以通过矩阵 dataMatIn 的 shape 属性得到常数 m 和 n。最后我们可以构建一个 alpha 列矩阵，矩阵元素都初始化为0，并建立一个 iter 变量。该变量存储的则是在没有任何 alpha 改变的情况下的遍历数据集的次数。当该变量达到输入值 maxIter 时函数结束运行并退出。

最后，在优化过程结束的同时，必须确保在合适的时机结束循环。如果程序执行到 for 循环的最后一行都不执行 continue 语句，那么就已经成功的改变了一对 alpha，同时可以增加 alphaPairsChanged 的值。在 for 循环之外，需要检查 alpha 值是否做了更新，如果有更新则将 iter 设为0后继续运行程序。只有在所有数据集上遍历 maxIter 次，且不再发生任何 alpha 修改之后，程序才会停止并退出 while 循环。

由于SMO算法的随机性，大家在多运行几次后所得到的结果可能会不一样。

利用完整的 Platt SMO算法加速优化

在几百个点组成的小规模数据集中，简化版SMO算法运行的时间是没有什么问题的，但是在更大的数据集上的运行速度就会变慢。刚才已经讨论了SMO的简化版算法，现在来谈谈完整版的SMO算法。在这两个版本中，实现 alpha 的更改和代数运算的优化环节一模一样。在优化过程中唯一的不同就是选择 alpha 的方式。完整版的 Platt SMO 算法应用了一些能够提速的启发方法。或许有些技术厉害的读者已经意识到上诉代码还可以优化运行时间。

Platt SMO 算法是通过一个外循环来选择第一个 alpha 值的，并且其选择过程会在两种方式之间进行交替：一种方式是在所有数据集上进行单遍扫描，另一种方式则是在非边界 alpha 中实现单遍扫描。而所谓的非边界 alpha 值的就是那些不等与边界0或C的 alpha 值。对整个数据集的扫描相当容易，而实现非边界 alpha 值的扫描时，首先需要建立这些 alpha 的值的列表，然后对这个表进行遍历。同时，该步骤会跳过那些已知的不会改变的 alpha 的值。

在选择第一个 alpha 值后，算法会通过一个内循环来选择第二个 alpha 值。在优化过程中，会通过最大化步长的方式来获得第二个 alpha 值。在简化版SMO算法中，我们会在选择 j 之后计算错误率 Ej。但在这里，我们会建立一个全局的缓存用于保存误差值，并从中选择步长或者说 Ei-Ej 最大的 alpha 值。

完整版 SMO 的辅助函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class optStruct:
    def __init__(self,dataMatIn, classLabels, C, toler, kTup):  
        self.X = dataMatIn
        self.labelMat = classLabels
        self.C = C
        self.tol = toler
        self.m = shape(dataMatIn)[0]
        self.alphas = mat(zeros((self.m,1)))
        self.b = 0
        self.eCache = mat(zeros((self.m,2))) #first column is valid flag
        self.K = mat(zeros((self.m,self.m)))
        for i in range(self.m):
        # 缓存误差
            self.K[:,i] = kernelTrans(self.X, self.X[i,:], kTup)
        
def calcEk(oS, k):
    fXk = float(multiply(oS.alphas,oS.labelMat).T*oS.K[:,k] + oS.b)
    Ek = fXk - float(oS.labelMat[k])
    return Ek
        
def selectJ(i, oS, Ei):        
	# 内循环的启发式方法
    maxK = -1; maxDeltaE = 0; Ej = 0
    oS.eCache[i] = [1,Ei]  
    validEcacheList = nonzero(oS.eCache[:,0].A)[0]
    if (len(validEcacheList)) > 1:
        for k in validEcacheList:   
            if k == i: continue 
            Ek = calcEk(oS, k)
            deltaE = abs(Ei - Ek)
            # 选择具有最长步长的 j
            if (deltaE > maxDeltaE):
                maxK = k; maxDeltaE = deltaE; Ej = Ek
        return maxK, Ej
    else:  
        j = selectJrand(i, oS.m)
        Ej = calcEk(oS, j)
    return j, Ej

def updateEk(oS, k):
    Ek = calcEk(oS, k)
    oS.eCache[k] = [1,Ek]

首要的事情就就是建立一个数据结构来保存所有的重要值，而这个过程可以通过一个对象来完成。这里使用对象的目的并不是为了面向对象编程，而只是作为一个数据结构来使用对象。在将值传给函数时，我们可以通过将所有数据移到另一个结构中来实现，这样就可以省掉手工输入的麻烦了。而此时，数据就可以通过一个对象来进行传递。

对于给定的 alpha 值，第一个辅助函数 caleEk() 能够计算 E 值并返回。以前，该过程是采用内嵌的方式来完成的，但是由于该过程在这个版本的SMO算法中出现频繁，这里必须要将其单独实现。

下一个函数 selectJ() 用于选择第二个 alpha 值。

最后一个辅助函数 updateEk()，它会计算误差值并存入缓存中。在对 alpha 进行优化之后就会用到这个值。

完整 Platt SMO 算法中的优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def innerL(i, oS):
    Ei = calcEk(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.K[i,j] - oS.K[i,i] - oS.K[j,j] 
        if eta >= 0: print "eta>=0"; return 0
        oS.alphas[j] -= oS.labelMat[j]*(Ei - Ej)/eta
        oS.alphas[j] = clipAlpha(oS.alphas[j],H,L)
        updateEk(oS, j) 
        if (abs(oS.alphas[j] - alphaJold) < 0.00001): print "j not moving enough"; 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.K[i,i] - oS.labelMat[j]*(oS.alphas[j]-alphaJold)*oS.K[i,j]
        b2 = oS.b - Ej- oS.labelMat[i]*(oS.alphas[i]-alphaIold)*oS.K[i,j]- oS.labelMat[j]*(oS.alphas[j]-alphaJold)*oS.K[j,j]
        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

上面这段代码几乎与简化版中的 smoSimple() 函数一模一样，但是这里的代码已经使用了自己的数据结构。该结构在参数 oS 中传递。第二个重要的修改就是使用了辅助函数 selectJ() 来改变第二个 alpha 的值。最后在 alpha 值改变时更新 Ecache。

完整版 SMO 的外循环代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def smoP(dataMatIn, classLabels, C, toler, maxIter,kTup=('lin', 0)):    
    oS = optStruct(mat(dataMatIn),mat(classLabels).transpose(),C,toler, kTup)
    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 "fullSet, iter: %d i:%d, pairs changed %d" % (iter,i,alphaPairsChanged)
            iter += 1
        else:
            nonBoundIs = nonzero((oS.alphas.A > 0) * (oS.alphas.A < C))[0]
            for i in nonBoundIs:
                alphaPairsChanged += innerL(i,oS)
                print "non-bound, iter: %d i:%d, pairs changed %d" % (iter,i,alphaPairsChanged)
            iter += 1
        if entireSet: entireSet = False #toggle entire set loop
        elif (alphaPairsChanged == 0): entireSet = True  
        print "iteration number: %d" % iter
    return oS.b,oS.alphas

其输入函数与 smoSimple() 完全一样。函数一开始构建一个数据结构来容纳所有的数据，然后需要对控制函数的退出的一些变量进行初始化。整个代码的主题也是 while 循环，但是退出条件更多一些。当迭代次数超过指定最大值，或者遍历整个集合都未对 alpha 对进行修改时，就退出循环。

接下来，我们对 for 循环在非边界循环和完整遍历之间进行切换，并打印出迭代次数。最后程序会返回边界0或C上的值。

大家可能会想，刚才我们花了大量时间来计算 alpha 值，但是如何利用他们进行分类呢？这不成问题，首先必须基于 alpha 值得到超平面，这也包括了 w 的计算。下面的一个小函数可以实现上诉任务。

1
2
3
4
5
6
7
def calcWs(alphas,dataArr,classLabels):
    X = mat(dataArr); labelMat = mat(classLabels).transpose()
    m,n = shape(X)
    w = zeros((n,1))
    for i in range(m):
        w += multiply(alphas[i]*labelMat[i],X[i,:].T)
    return w

我们现在成功训练出分类器了，我想指出的就是，这里的两个类中的数据点分布在一条直线的两边。但是倘若两类数据点分别分布在一个圆的内部与外部，那么会得到什么样子的分类面呢？下面我会介绍一种方法对分类器进行修改，以说明类别区域形状不同情况下的数据集分隔问题。

在复杂数据上使用核函数

这里我主要介绍的是径向基核函数，关于核函数的详细介绍还是参见本文开头的那个连接的文章。

核函数的原理–将数据映射到高维空间

从某个特征空间到另一个特征空间的映射是通过核函数来实现的。大家可以把核函数想象为一个包装器(wrapper)或者是接口(interface)，它能把数据从某个难处理的形式转换为另一个较容易处理的形式。如果上诉特征空间听起来很模糊的话，那么可以将它想象成一种计算距离的方法。前面我们提到过距离计算的方法。距离计算的方法有很多种，核函数也有很多种。经过空间转换后，我们可以在高维空间中解决线性问题，这也就等价于在低维空间中解决非线性问题。

SVM 优化中一个特别好的地方就是，所有的运算都可以写成内积(inner product 或者点积)的形式。向量的内积值的是两个向量相乘，之后得到单个标量或者数值。我们可以把内积运算替换成核函数，而不做简化处理。将内积替换为核函数的方式称为核技巧(kernal trick)。

核函数并不仅仅支持 SVM，很多其他的机器学习算法都用到核函数。

径向基核函数

径向基核函数是 SVM 中常用的一个核函数。径向基函数是一个采用向量作为自变量的函数，能够基于向量距离运算输出一个标量。这个距离可以是从 <0,0> 向量或者其他向量开始计算的距离。

我们想要使用径向基核函数，就要在原代码中进行适当的修改。

核转换函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def kernalTrains(X, A, kTup):
    m, n = shape(X)
    K = mat(zeros((m,1)))
    if kTup[0] == 'lin': 
        K = X * A.T
    elif kTup[0] == 'rbf':
        for j in range(m):
            deltaRow = X[j,:] - A
            K[j] = deltaRow * deltaRow.T
        K = exp(K / (-1*kTup[1]**2))
    else:
        raise NameError('Wrong')
    return K

class optStructK:
    def __init__(self,dataMatIn, classLabels, C, toler):  # Initialize the structure with the parameters 
        self.X = dataMatIn
        self.labelMat = classLabels
        self.C = C
        self.tol = toler
        self.m = shape(dataMatIn)[0]
        self.alphas = mat(zeros((self.m,1)))
        self.b = 0
        self.eCache = mat(zeros((self.m,2)))

在初始化方法结束后，矩阵K先被建立，然后再通过调用函数 kernalTrains() 进行填充。全局的K只需要计算一次。然后当想使用核函数时，就可以对它进行调用。

最后如果遇到一个无法识别的元组，程序会抛出一个异常。

同时，为了使用核函数，先前的 innerL() 与 calcEk() 函数需要进行修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def innerLK(i, oS):
    Ei = calcEk(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) #this has been changed from selectJrand
        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] = clipAlpha(oS.alphas[j],H,L)
        updateEk(oS, j) #added this for the Ecache
        if (abs(oS.alphas[j] - alphaJold) < 0.00001): print "j not moving enough"; return 0
        oS.alphas[i] += oS.labelMat[j]*oS.labelMat[i]*(alphaJold - oS.alphas[j])#update i by the same amount as j
        updateEk(oS, i) #added this for the Ecache                    #the update is in the oppostie direction
        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 calcEkK(oS, k):
    fXk = float(multiply(oS.alphas,oS.labelMat).T*(oS.X*oS.X[k,:].T)) + oS.b
    Ek = fXk - float(oS.labelMat[k])
    return Ek

小结

SVM 是一个分类器。之所以成为“machine”是因为它会产生一个二值决策效果，即是一种决策“机”。SVM的泛化错误率低，这就意味着它有着良好的学习能力，且得到的结果具有很好的推广性。这些优点使得SVM十分流行。

SVM 的主要求解方式就是试图通过求解一个二次优化问题来最大化分类间隔。

核方法会将数据从一个低维空间映射到一个高维空间，可以将一个在低维空间中的非线性问题转换为高维空间下的线性问题求解。

SVM 是一个二类分类器。当用其解决多类问题时，则需要额外的方法对其进行扩展。这点我在本篇文章开头时的那个连接文章中的最后详细介绍了。

看，其实支持向量机与核函数主要就这些。