机器学习 (8)——支持向量机 (SVM)

本贴最后更新于 2455 天前,其中的信息可能已经时过境迁

0x00 支持向量机

在机器学习中,支持向量机(support vector machine,常简称为 SVM,又名支持向量网络)是在分类与回归分析中分析数据的监督式学习模型与相关的学习算法。给定一组训练实例,每个训练实例被标记为属于两个类别中的一个或另一个,SVM 训练算法建立一个将新的实例分配给两个类别之一的模型,使其成为非概率二元(binary classifier)线性分类器。SVM 模型是将实例表示为空间中的点,这样映射就使得单独类别的实例被尽可能宽的明显的间隔分开。然后,将新的实例映射到同一空间,并基于它们落在间隔的哪一侧来预测所属类别。

0x01 间隔与支持向量
首先看一张图:

如果要用一条直线将两种类型的图形分开,那这样的直线我们可以找到很多条。那么哪条才是最好的分割线?

我们可以设想一下,目前的样本并不代表所有可能发生的情况,如果进入新样本,很有可能会存在向直线贴近的样本,那么如果选择的直线到两边最近的点间隔越长,输入新样本时越过这条线的机会就越小,泛化能力就越强。

图中距离这条分割线最近的这几个点,就被称为支持向量。

两个异类支持向量到这条直线的距离之和,就被称为间隔。

假设我们分割线的方程如下:

其中 w 是法向量。

我们的可以通过它将训练样本正确分类,即

留出间隔,令:

则间隔的数学表示为:

我们为了找到最大间隔,也就是使 γ 最大,也就是使 ||w||² 最小,就可以转换成找

的最小值。这被称为支持向量机的基本型。
0x02 对偶问题

上面的问题最终转换成求支持向量机基本型的最小值问题,这是一个凸二次规划问题,可以直接求解,但是我们有更优的计算方法。那就是通过拉格朗日乘子法得到其”对偶问题“。

具体做法是对每条约束都增加拉格朗日乘子 αi,则该问题可以写成:

这个时候要求其最小值,从之前转换成最小值的模型前加了 1/2 这点就可以想到,我们接下来肯定要通过求导,求导数零点,找极值点来完成。

所以分别对 w 和 b 求导可以得出:

将其结论代回 L 中可得对偶问题:

这个结果,我们就可以直接交给机器去处理数据求这个式子的最大值了。

0x03 核函数

线性可分的训练样本我们可以通过直线将其正确分类,但是如果遇到线性不可分的训练样本,或许就不能通过一条直线来进行分割。

这种情况下,我们可以将样本从原本的空间映射到一个更高维度的空间,使样本在这个空间内线性可分。

比如二维平面中的样本投影到三维空间中,就可以通过一个超平面线性分割两类样本了:

具体做法是用 Φ(x)代表 x 映射之后的特征向量,对偶问题就变为:

在计算 Φ(xi)的转置与 Φ(xj)的矩阵乘积时,在高维会变的十分困难,所以就引入了:

Φ(xi)与 Φ(xj)内积等于它们在原始样本空间通过 k 函数计算的结果,这样就不用去高维计算内积。这个 k 函数就被称为核函数。

常用的核函数如下:

并不是所有的情况通过核函数映射之后都是线性可分的,我们会根据实际的情况去选取合适的核函数,使其映射到高维之后可以分割,然后高维分割的超平面在原始平面上的投影就是在原始平面上的分割曲线。

0x04 硬间隔和软间隔

即使使用了核函数,实际中,我们仍然存在一种不可分的情况,即两类样本互相有一部分出现在对方的区域,如图:

那么这种情况,我们的处理方式就是允许支持向量机在一些样本上出错,也就是“软间隔”。

对应的所有样本都被正确分类就被称为“硬间隔”。

在之前机器学习的经验中我们都明白,出错就会有损失,那么我们需要一个损失函数来计算惩罚,最终的优化目标是在最大化间隔的同时使不满足约束的样本尽可能少,可写为:

这里面使用的损失函数是 0/1 损失函数:

我们也有其他几种替代损失函数可供选择:

在软间隔情况中,只使满足最终优化目标的值优化到最小即可。

0x05 支持向量机的优缺点

支持向量机的优势在于:

  • 在高维空间中非常高效
  • 即使在数据维度比样本数量大的情况下仍然有效
  • 在决策函数(称为支持向量)中使用训练集的子集,因此它也是高效利用内存的
  • 通用性: 不同的核函数 核函数与特定的决策函数一一对应,常见的 kernel 已

经提供,也可以指定定制的内核

支持向量机的缺点包括:

  • 如果特征数量比样本数量大得多,在选择核函数 核函数 时要避免过拟合,

而且正则化项是非常重要的

  • 支持向量机不直接提供概率估计
  • 机器学习

    机器学习(Machine Learning)是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。专门研究计算机怎样模拟或实现人类的学习行为,以获取新的知识或技能,重新组织已有的知识结构使之不断改善自身的性能。

    77 引用 • 37 回帖

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...

推荐标签 标签

  • 分享

    有什么新发现就分享给大家吧!

    248 引用 • 1794 回帖
  • B3log

    B3log 是一个开源组织,名字来源于“Bulletin Board Blog”缩写,目标是将独立博客与论坛结合,形成一种新的网络社区体验,详细请看 B3log 构思。目前 B3log 已经开源了多款产品:SymSoloVditor思源笔记

    1062 引用 • 3455 回帖 • 151 关注
  • 酷鸟浏览器

    安全 · 稳定 · 快速
    为跨境从业人员提供专业的跨境浏览器

    3 引用 • 59 回帖 • 54 关注
  • PWA

    PWA(Progressive Web App)是 Google 在 2015 年提出、2016 年 6 月开始推广的项目。它结合了一系列现代 Web 技术,在网页应用中实现和原生应用相近的用户体验。

    14 引用 • 69 回帖 • 184 关注
  • jQuery

    jQuery 是一套跨浏览器的 JavaScript 库,强化 HTML 与 JavaScript 之间的操作。由 John Resig 在 2006 年 1 月的 BarCamp NYC 上释出第一个版本。全球约有 28% 的网站使用 jQuery,是非常受欢迎的 JavaScript 库。

    63 引用 • 134 回帖 • 733 关注
  • CodeMirror
    2 引用 • 17 回帖 • 174 关注
  • JetBrains

    JetBrains 是一家捷克的软件开发公司,该公司位于捷克的布拉格,并在俄国的圣彼得堡及美国麻州波士顿都设有办公室,该公司最为人所熟知的产品是 Java 编程语言开发撰写时所用的集成开发环境:IntelliJ IDEA

    18 引用 • 54 回帖
  • Thymeleaf

    Thymeleaf 是一款用于渲染 XML/XHTML/HTML5 内容的模板引擎。类似 Velocity、 FreeMarker 等,它也可以轻易的与 Spring 等 Web 框架进行集成作为 Web 应用的模板引擎。与其它模板引擎相比,Thymeleaf 最大的特点是能够直接在浏览器中打开并正确显示模板页面,而不需要启动整个 Web 应用。

    11 引用 • 19 回帖 • 395 关注
  • 链滴

    链滴是一个记录生活的地方。

    记录生活,连接点滴

    183 引用 • 3885 回帖
  • danl
    179 关注
  • FFmpeg

    FFmpeg 是一套可以用来记录、转换数字音频、视频,并能将其转化为流的开源计算机程序。

    23 引用 • 32 回帖 • 8 关注
  • V2Ray
    1 引用 • 15 回帖 • 2 关注
  • Solidity

    Solidity 是一种智能合约高级语言,运行在 [以太坊] 虚拟机(EVM)之上。它的语法接近于 JavaScript,是一种面向对象的语言。

    3 引用 • 18 回帖 • 445 关注
  • PHP

    PHP(Hypertext Preprocessor)是一种开源脚本语言。语法吸收了 C 语言、 Java 和 Perl 的特点,主要适用于 Web 开发领域,据说是世界上最好的编程语言。

    167 引用 • 408 回帖 • 482 关注
  • WebComponents

    Web Components 是 W3C 定义的标准,它给了前端开发者扩展浏览器标签的能力,可以方便地定制可复用组件,更好的进行模块化开发,解放了前端开发者的生产力。

    1 引用 • 14 关注
  • 星云链

    星云链是一个开源公链,业内简单的将其称为区块链上的谷歌。其实它不仅仅是区块链搜索引擎,一个公链的所有功能,它基本都有,比如你可以用它来开发部署你的去中心化的 APP,你可以在上面编写智能合约,发送交易等等。3 分钟快速接入星云链 (NAS) 测试网

    3 引用 • 16 回帖 • 1 关注
  • 人工智能

    人工智能(Artificial Intelligence)是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门技术科学。

    115 引用 • 319 回帖
  • Node.js

    Node.js 是一个基于 Chrome JavaScript 运行时建立的平台, 用于方便地搭建响应速度快、易于扩展的网络应用。Node.js 使用事件驱动, 非阻塞 I/O 模型而得以轻量和高效。

    139 引用 • 269 回帖 • 2 关注
  • Firefox

    Mozilla Firefox 中文俗称“火狐”(正式缩写为 Fx 或 fx,非正式缩写为 FF),是一个开源的网页浏览器,使用 Gecko 排版引擎,支持多种操作系统,如 Windows、OSX 及 Linux 等。

    7 引用 • 30 回帖 • 372 关注
  • Anytype
    3 引用 • 31 回帖 • 28 关注
  • 创业

    你比 99% 的人都优秀么?

    81 引用 • 1395 回帖
  • BookxNote

    BookxNote 是一款全新的电子书学习工具,助力您的学习与思考,让您的大脑更高效的记忆。

    笔记整理交给我,一心只读圣贤书。

    1 引用 • 1 回帖 • 3 关注
  • V2EX

    V2EX 是创意工作者们的社区。这里目前汇聚了超过 400,000 名主要来自互联网行业、游戏行业和媒体行业的创意工作者。V2EX 希望能够成为创意工作者们的生活和事业的一部分。

    16 引用 • 236 回帖 • 240 关注
  • 反馈

    Communication channel for makers and users.

    120 引用 • 906 回帖 • 281 关注
  • CAP

    CAP 指的是在一个分布式系统中, Consistency(一致性)、 Availability(可用性)、Partition tolerance(分区容错性),三者不可兼得。

    12 引用 • 5 回帖 • 633 关注
  • Tomcat

    Tomcat 最早是由 Sun Microsystems 开发的一个 Servlet 容器,在 1999 年被捐献给 ASF(Apache Software Foundation),隶属于 Jakarta 项目,现在已经独立为一个顶级项目。Tomcat 主要实现了 JavaEE 中的 Servlet、JSP 规范,同时也提供 HTTP 服务,是市场上非常流行的 Java Web 容器。

    162 引用 • 529 回帖 • 9 关注
  • Ubuntu

    Ubuntu(友帮拓、优般图、乌班图)是一个以桌面应用为主的 Linux 操作系统,其名称来自非洲南部祖鲁语或豪萨语的“ubuntu”一词,意思是“人性”、“我的存在是因为大家的存在”,是非洲传统的一种价值观,类似华人社会的“仁爱”思想。Ubuntu 的目标在于为一般用户提供一个最新的、同时又相当稳定的主要由自由软件构建而成的操作系统。

    127 引用 • 169 回帖