魔王编译

透过现象看实质,图解支撑向量机

作家说:我以前不停没有真正了解支撑向量机,直到我画了一张图。

1. 题目

支撑向量机(SVM)旨办理「分类」题目。数据一般包罗必定命量的条目/行/点。现,我们念对每个数据点举行分类。为简单起睹,我们假设两个种别:「正类」和「负类」。这大约可以帮帮解答以下题目:

  • 基于图像的像素数据,判别这张图像中是否有猫(有猫则标签为正类);

  • 基于邮件的中心、发送者、文本等,判别该邮件是否为垃圾邮件;

  • 判别某个病人是否患有某种疾病。

其精髓于,当我们晓得准确谜底时,我们会念到少许将数据分为两类的规矩(关于支撑向量机而言,「规矩」是画一个平面,一侧的所有点均为「正」,另一侧的所有点均为「负」)。当我们碰到不晓得种另外新数据点时,我们运用规矩对其举行分类。分类题目告急依赖束缚优化,同时也是束缚优化的一个直观示例。大师可以参考以下博客或吴恩达的作品。

  • 博客地址:https://towardsdatascience.com/lagrange-multipliers-with-pictures-and-code-ace8018dac5e

  • 吴恩达作品地址:http://cs229.stanford.edu/notes/cs229-notes3.pdf

1.1 图解

我以前不停没有真正了解支撑向量机,直到我画了一张图。

我们可以看到特征空间中有少许点。为便当可视化,我们运用一个可屏幕上观看的 2D 特征空间。该空间中散落着少许数据点,每个点具备二元标签((1/-1)。如下图所示,我们将绿色点看作正类,血色点看作负类,黄色点种别未知。假如让你猜念黄色点的标签,你会怎样选?你可以会发明此中少许点并不是那么容易确认种别。

图 1:2-D 分类题目绿色点是正类,血色点是负类。你可以猜出黄色点的标签吗?(绘图东西:https://github.com/ryu577/pyray)

现,假如我画一条紫色线将两个种别支解开,那么黄色点属于哪个种别就分明众了(紫色线上方是绿色点,系澜是血色点)。

图 2:画一条线,举措将正类标签和负类标签支解开来的「规矩」。现,我们可以运用该规矩标注每个黄色点的种别。

然而,这条线并非独一。有许众条紫色线可以将绿色点和血色点完美支解(睹下图)。跟着下图中紫色线的挪动,某些黄色点就显得很微妙了(它们处于紫色线的差别侧,于是它们的种别取决于你挑选运用哪条紫色线)。

图 3:将血色点和绿色点完美支解的线有许众条。那么我们该中挑选哪一条呢?

题目于,所有候选线中,哪一条是「最优」的?有一点很分明:当上图中的紫色线接近右下角的血色点(critical point)时,其泛化效果欠好,而当它远离谁人点时,其支解效果要好得众。于是,这个血色点可以阐明紫色线的分类效果,于是它是「要害点」。我们可以说,远离该血色点的线同样远离所有教练样本,而接近该血色点的线最终的分类效果并欠好。于是,离近来的教练样本较远的线才是精良的分类器。

接下来,我们来看怎样应用数学常识绘制支解线。

2. 绘制支解线

现我们要( 2D 空间中)画一条支解线(更高维度的空间中,则为支解面)。那么这条线是什么呢?它是具备某种共性的点的无量汇合。这些点满意一个特定公式。为了找到这个公式,我们先葱☆简单的线 x 轴开端。x 轴上所有点的位置向量保管什么共性?v_x = [x,0],即它们对应的 y 坐标均为 0。

也便是说,x 轴上每个点的位置向量与指向 y 轴偏向的向量是正交(笔直)的。

这个说法可以看起来比较艰涩难懂,可是我们必需这么说,因为这种现象实对所有线都修立,而并非只适用于 x 轴。我们期望将此说法泛化至恣意线。现每次挪动一小步,我们来看看透过原点的线(如 x 轴)。如下图所示,只需将 x 轴改变必定角度,就可以取得这些线。

图 4:改变 x 轴可以取得穿过原点的恣意线。这些线上的每个点都与橙色向量相笔直。

跟着线的改造,与线相笔直的向量也改造,可是所有线上每个点的位置向量都与某个向量笔直。我们把这个与线笔直的向量叫做 w。当我们改动 w 时,就可以捕捉到所有此类线。

当心,关于恣意给定线而言,保管众个 w 值。假如我们将向量 w 扩展或缩小必定命值,该线上每个点的位置向量仍与向量 w 笔直。

图 5:扩展或缩小正交 w 向量。

为什么不把 w 向量限制大小为 1 呢?下文中,我们将 w 向量的大小设为 1。

现我们曾经将穿过原点的所有线都参数化了。那么那些没有穿过原点的线呢?我们将穿过原点的线挪动必定量,即该线法向量 w 的偏向上挪动 b。现,w 与该线上每个点的位置向量的点积不为零,而是常量 b(参睹下图)。w 向量是从原点指向紫色线的单位向量,且与紫色线笔直。A 即紫色线上与原点最接近的点。假设 OA 的间隔是 -b。现,思索两个随机点 B 和 C(区分是图中绿色点和橙色点)。将 OB 或 OC 与单位向量 w 相乘,区分取得三角形 OAB 和 OAC 的底。

这两种状况中,OA 为 -b。因为这两个点只是紫色线上的恣意点,我们可以推测出,紫色线上的所有点均满意 w^T x+b=0(此中 x 外示紫色线上点的位置向量)。

图 6:未穿过原点的线。

假如我们将不该线上的点运用于上述公式呢?取得的结果不是零,而是从该点到紫色线的笔直间隔(关于紫色线上的点而言也是云云,以是它们所对应的公式结果为零)。我们需求当心:这个结论仅适用于 |w|=1 的状况。下图分明阐清楚这一结果。B 为不属于紫色线的恣意点,B』』 为从 B 到紫色线的垂点,B』 为从 B 到 w 向量的垂点。从 B 到紫色线的笔直间隔为 BB』』。可是因为 A-B』-B-B』』 是一个矩形,于是该笔直间隔等于 AB』=OB』-OA。现,OB』 是 B 的位置向量与 w 的点积。于是,假如 x 是 B 的位置向量,则 |OB』| = w^T x。这意味着 |AB』|=w^T x-(-b)(OA=-b)。于是从点 B 到紫色线的间隔是:|AB』|=w^T x+b(该公式恰恰是紫色线的公式)。

图 7:将不紫色线上的点运用于紫色线公式会爆发什么?我们取得该点与紫色线之间的笔直间隔。

当心, w 指向偏向一侧的所有点(如图 7 中的点 B)到紫色线的笔直间隔为正值,而另一侧点的笔直间隔为负值。

w 指向偏向一侧的所有点均取得正类标签 (t_i=1),而另一侧的所有点均取得负类标签 (t_i=-1)。于是,假如我们将这些标签与笔直间隔相乘,则所有点调解后的笔直间隔均为正,条件是这些点均被紫色线准确分类(即具备正类标签的点线一侧,具备负类标签的点另一侧)。

3. 最佳支解线

现到了 SVM 的要点了。我们将恣意点到支解线的调解后笔直间隔叫做「间距」(margin)。那么,关于恣意给定支解线,所有点均具备间距(假如点被支解线准确分类,则间距为正,反之则间距为负)。我们念获取将正类和负类完美支解的线。也便是说,间距越大越好,即使是关于临近界线(支解平面)的点。

那么,最大化所有间距(以致是最接近支解线的点的间距)的支解平面应当可以很好地支解这些点。现,给出 (w,b),第 i 个点的间距为:

间距公式。

此中 x_i 外示特征空间中的位置向量,t_i 外示标签:1 为正类,-1 为负类。

所有点中的最小间距为:

公式 1:所有点中的最小间距。

我们念让 (w,b) 最大化上述最小间距。也便是:

即我们念让 (w,b) 满意 |w|=1,且最大化间距:

公式 2:SVM 目标函数

当心:假如这条线没有分别数据,那么关于 (w,b),某些点的间距

间距公式。

为负。且这些点中的此中一个会第一次最小化中「脱颖而出」,这意味着 (w,b) 无法第二次 arg max 时胜出。于是,该公式包管了胜出的 (w,b) 可以支解数据。

公式 2 是一个优化题目,涉及最小化和最大化(mini-max)。办理一级优化总比二级优化要简单。于是,我们实验将公式 2 转化为束缚优化题目。

我们用 γ 外示所有点的最小间距。

公式 3:束缚。

最终取得的优化题目为:

公式 4:SVM 优化题目。

上述优化题目具备二次/线性束缚和线性目标函数。我们可以运用二次计划求解器(quadratic programming solver)和最优支解线/平面 (w,b) 办理该题目。

现,我们来试着进一步简化该题目。我们发明可以去除 γ。其价钱是,我们必需放弃 w^T w = 1 这一请求。但这是值得的。我们运用 γ 将束缚支解为两部分,取得:

公式 5:运用 γ 支解支解平面公式。

现,使

引入新的 w 变量。

为两侧取绝对值:

取绝对值。

我们之前请求 |w|=1。这意味着:

于是,公式 3 变成了:

公式 5 和公式 6 使公式 4 中的优化题目变成了:

现,优化题目有了一个寝陋的目标函数。可是最大化 1/|w| 等同于最小化 |w|,等同于最小化 |w|²。添加 1/2 使得盘算更加简单。

于是,上述优化题目变为:

公式 7

现,该优化题目具备二次目标函数和线性束缚(线性束缚二次计划,LCQP)。运用二次计划求解器即可办理该题目。

现,我们晓得怎样通过办理优化题目寻得最优支解线了。透过外面查看办理这类优化题目的真正机制,会帮帮我们对该题目了解更众,具备更强大的洞察和睹地。

初学SVM支撑向量机
61
相关数据
吴恩达人物

斯坦福大学传授,人工智能出名学者,板滞进修蕉蔟者。2011年,吴恩达谷歌创立了谷歌大脑项目,以通过分布式集群盘算机开辟超大范围的人工神经收集。2014年5月16日,吴恩达到场百度,认真“百度大脑”方案,并承当百度公司首席科学家。2017年3月20日,吴恩达发布从百度告退。2017年12月,吴恩达发布修立人工智能公司Landing.ai,并承当公司的首席施行官。2018年1月,吴恩达修立了投资机构AI Fund。

参数技能

数学和统计学裡,参数(英语:parameter)是运用通用变量来修立函数和变量之间联系(岛镶种联系很难用方程来阐述时)的一个数目。

二次计划技能

二次计划(Quadratic programming),运筹学当中,是一种特别类型的最佳化题目。

支撑向量机技能

板滞进修中,支撑向量机是分类与回归剖析平剖析数据的监视式进修模子与相关的进修算法。给定一组教练实例,每个教练实例被标记为属于两个种别中的一个或另一个,SVM斗嗽翥法创立一个将新的实例分派给两个种别之一的模子,使其成为非概率二元线性分类器。SVM模子是将实破例示为空间中的点,如许映照就使得独自种另外实例被尽可以宽的分明的间隔分开。然后,将新的实例映照到同一空间,并基于它们落间隔的哪一侧来预测所属种别。

目标函数技能

目标函数f(x)便是用计划变量来外示的所寻求的目标方式,以是目标函数便是计划变量的函数,是一个标量。从工程原理讲,目标函数是系统的功用标准,比如,一个构造的最轻重量、最低制价、最合理方式;一件产物的最短生产时间、最小能量消耗;一个实行的最佳配方等等,修立目标函数的进程便是寻找计划变量与目标的联系的进程,目标函数和计划变量的联系可用弧线、曲面或超曲面外示。

分类题目技能

分类题目是数据开掘处理的一个主要构成部分,板滞进修范畴,分类题目一般被认为属于监视式进修(supervised learning),也便是说,分类题目的目标是依据已知样本的某些特征,判别一个新的样本属于哪种已知的样本类。依据种另外数目还可以进一步将分类题目划分为二元分类(binary classification)和众元分类(multiclass classification)。

引荐作品
作家您好,我是数智泉大众号的编辑,请问可以转发这篇作品到我们大众号吗?