Abstract

通过之前几天的学习，我们应该已经建立了一个对ML大概的认知，并且，通过如sklearn之类的框架，我们也可以完成一些机器学习任务了，对于常见的分类任务，我们已经可以完美完成了，但是我们对ML的底层还是一知半解，所以接下来我们的任务就是暂时先跳出微软对初学者的框架，开始研究一些算法的底层实现，这次我们选择的目标就是SVM（Support Vector Machine)

Link Reference

Implementing Support Vector Machine From Scratch | by Marvin Lanhenke | Towards Data Science

机器学习实战教程（八）：支持向量机原理篇之手撕线性SVM (cuijiahua.com)

Introduction

在这篇文章的接下来的内容里，我们只会使用Python与Numpy，不使用其他第三方库，以避免框架影响我们的理解 SVM是在上个世纪九十年代在计算机社区中被提出的，它经常被用在分类算法中，就像我们的第四天一样，第四天我们就学习了如何在有第三方库的情况下使用SVM（SVC），它还有一个名字，Maximal Margin Classifier，但是SVM并不能解决所有的问题，它更多是在数据具有离散线性关系的时候很好用，不过对于这个，SVM也有它的扩展可以解决

我们先从简单的开始，假设一个二分类问题，我们的数据集是一个具有离散线性关系的二分集合，而之所以SVM也叫MMC，是因为它寻求寻找这个集合里的两类数据间具有最大间隙的超平面（HyperPlane)，我们可以简单看一下其可视化表现，我们下面给出这个可视化的代码（还花了点时间学manim这个库）

from random import randint
from manimlib import *

class HyperPlane(Scene):
    def construct(self):
        grid = Axes(
            x_range=[-10, 10, 1],
            y_range=[-5, 5, 1],
            x_length=20,
            y_length=10,
            axis_config={
                "stroke_color": GREY,
                "stroke_width": 2,
                "include_numbers": True,
                "font_size": 13
            },
            y_axis_config={
                "include_tip": False,
            }
        )

        #points is sperated by y = 1.5x + 1
        #up red, down blue
        points = []
        for i in range(36):
            x = randint(-10, 10)
            y = randint(-5, 5)
            if y > 1.5 * x + 1:
                points.append([x, y, RED])
            else:
                points.append([x, y, BLUE])

        for i in range(len(points)):
            dot = Dot(x = 1, y = 1, color=points[i][2])
            dot.move_to(grid.c2p(points[i][0],points[i][1]))
            grid.add(dot)

        graph = grid.get_graph(lambda x: 1.5*x + 1, x_range=[-5, 5], color=RED)
        self.add(grid, graph)

如果从学术一点的角度说，一个N维的超平面就是这个N维平面中一个平坦的N-1维的投影，用公式表达如下下（A与X为N维的向量）

就像在二维空间中，一个超平面可以描述维

而如果到了三维空间，这个超平面就变成了一个二维平面，但是这画出来太抽象了。。我也不知道怎么更好可视化一些，大概就是对于点来说，越大表示距离摄像机越近，灰色平面就是那个超平面

class HyperPlane(ThreeDScene):
    CONFIG = {
        "camera_class" : ThreeDCamera
    }

    def construct(self):
        axes = ThreeDAxes(
            x_range=[-10, 10, 1],
            y_range=[-5, 5, 1],
            z_range=[-5, 5, 1],
            x_length=20,
            y_length=10,
        )
        self.add(axes)

        #points is sperated by z = 1.5x - 2y + 1
        #up red, down blue
        points = []
        for i in range(36):
            x = randint(-10, 10)
            y = randint(-5, 5)
            z = randint(-5, 5)
            if z > 1.5 * x - 2 * y + 1:
                points.append([x, y, z, RED])
            else:
                points.append([x, y, z, BLUE])


        self.camera.frame.save_state()
        self.camera.frame.move_to(axes.c2p(0, 0, 0))
        self.camera.frame.rotate(PI*2/3, axis=RIGHT)
        self.camera.frame.rotate(PI/6, axis=OUT)

        # draw a plane
        plane = ParametricSurface(
            lambda u, v: np.array([
                u,
                v,
                1.5 * u - 2 * v + 1
            ]), u_range=[-1, 1], v_range=[-1, 1],
            checkerboard_colors=[RED_D, RED_E],
        )
        self.add(plane, axes)

        for i in range(len(points)):
            dot = Dot(x = 1, y = 1, z = 1, color=points[i][3])
            dot.move_to(axes.c2p(points[i][0],points[i][1],points[i][2]))
            axes.add(dot)

ok，现在我们已经可以分割数据了，通过这个超平面，但是，什么样的超平面才是最好的呢？比如说对于上面那个例子来说，有多种可能的分割线 

Implementation

看这两条线，它都满足我们的要求，怎么选？记住我们在做什么，我们是在做ML，我们现在只是在训练模型，最终我们面对的数据是位置的，所以我们选择的这条线应该要留出足够多的容错空间，即下面这样 

H1和H2到H0的距离相等，如果超平面选H0，那么在未知数据的范围内，我们预留了一个足够大而且比较公平的容错空间，两种类型的数据预测错误的结果和预测正确的结果的概率应该是相同的，对于H1和H2，我们这么描述（因为H1H2应该是平行的，系数是一样的）

但是这个A又怎么取？？？这条线的斜率我们还没确定呢，下面这张图这样的，这么多条线，不是都可以？？

在SVM里，这条线的选取就是能让H1和H2距离最大的这条线，现在的问题就是这个距离怎么描述，用高中的知识来讲的话，可以使用垂直于这个超平面的向量来描述，设w为一个垂直于超平面H1H2的向量，且w不为0，则单位向量可以描述为

然后就可以把这个距离向量描述为

vec{k} = m vec{u}

其中m为距离

现在思考，假设z0为H1上的一点，x0为H2上的一点，且x0与z0的连线垂直，那么我们可以得到一个这样的关系

再然后，讨厌的数学家们又对公式做了简化

对公式两边除以d，得到

最后合成一个公式，这个就是我们求解SVM时要使用到的约束条件

回到之前的推导，我们求解d的最大值就等价于求解w（A）的最小值，好了， 现在我们可以把求解方程和约束条件放在一起，就有了最终需要的表达式

它是一个具有不等式约束条件的优化问题，现在我们使用拉格朗日乘数法来解决它，构造一个下面这样的函数

Review of mathematics

然后我就寄了，怎么一个SVM需要这么多的基础知识，甚至我们需要先了解感知机才能更好地学习SVM。。

来自团队学习笔记

原文始发于微信公众号（衡阳信安）：机器学习之算法SVM笔记