机器学习之算法SVM笔记

AI 2周前 admin
99 0 0

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

在这篇文章的接下来的内容里,我们只会使用PythonNumpy,不使用其他第三方库,以避免框架影响我们的理解 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=[-10101],
            y_range=[-551],
            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(-1010)
            y = randint(-55)
            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=[-55], color=RED)
        self.add(grid, graph)

机器学习之算法SVM笔记如果从学术一点的角度说,一个N维的超平面就是这个N维平面中一个平坦的N-1维的投影,用公式表达如下下(AX为N维的向量)

机器学习之算法SVM笔记

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

机器学习之算法SVM笔记

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

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

    def construct(self):
        axes = ThreeDAxes(
            x_range=[-10101],
            y_range=[-551],
            z_range=[-551],
            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(-1010)
            y = randint(-55)
            z = randint(-55)
            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(000))
        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=[-11], v_range=[-11],
            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)

机器学习之算法SVM笔记

ok,现在我们已经可以分割数据了,通过这个超平面,但是,什么样的超平面才是最好的呢?比如说对于上面那个例子来说,有多种可能的分割线 机器学习之算法SVM笔记

Implementation

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

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

机器学习之算法SVM笔记

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

机器学习之算法SVM笔记

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

机器学习之算法SVM笔记

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

vec{k} = m vec{u}

机器学习之算法SVM笔记

其中m为距离

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

机器学习之算法SVM笔记

发现华点没,对的,β是平面内一个任意向量,A向量与β向量垂直,同时α与β垂直,这在暗示我们α很有可能与A同向,但是我们还不能肯定,但是注意,β是任意方向的,它可以在一个平面内转来转去,而不论怎么样,A都与β平行,那么有

机器学习之算法SVM笔记

在二维平面内有上述关系,很明显了A就是垂直于超平面的一个向量,而在更高维也有同样的推理,所以在下面的讨论中,我们将A用w表示(因为在上面的讨论里,我们就是用w来表示垂直于超平面的向量的,现在A和w的意义是相同的)

然后,我们尝试尝试求解之前的A了,因为z0 x0都与A相关,他们只是b不同

机器学习之算法SVM笔记

注意x0位于H2上,因此有

机器学习之算法SVM笔记

我们要使得m最大,也就是要使得后面那个表达式最大,现在思考一下,是不是其实b和w是两个不相关变量,我们可以任意取,所以实际上就是求w最小值和b2-b1最大值,先求w的最小值,它等价于求

机器学习之算法SVM笔记

接下来,我们变化一下之前的公式

y_i=left{begin{matrix} +1 红色\ -1 蓝色 end{matrix}right. \ A^Tx_i+ gamma > 0, y_i = 1 \ A^Tx_i+gamma < 0, y_i=-1


机器学习之算法SVM笔记

而样本点到超平面的距离表示为d,d满足下面这个关系,推导过程高中学过

机器学习之算法SVM笔记

要使得红蓝两方到超平面的距离都相对相等,我们可以得到如下方程组

机器学习之算法SVM笔记

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

机器学习之算法SVM笔记

对公式两边除以d,得到

机器学习之算法SVM笔记

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

机器学习之算法SVM笔记

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

机器学习之算法SVM笔记

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

机器学习之算法SVM笔记

Review of mathematics

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

来自团队学习笔记

机器学习之算法SVM笔记

机器学习之算法SVM笔记

原文始发于微信公众号(衡阳信安):机器学习之算法SVM笔记

版权声明:admin 发表于 2023年1月24日 上午12:26。
转载请注明:机器学习之算法SVM笔记 | CTF导航

相关文章

暂无评论

暂无评论...