机器学习2_支持向量机_线性可分——MOOC

🕗 发布于 2024-11-06 07:40 机器学习 支持向量机 python 算法

定义

线性可分（Linear Separable）

线性不可分（Nonlinear Separable）

定义

线性可分（Linear Separable）

二维

三维

特征空间维度 $\geqslant$ 四维时，二维的情况下分割圆圈和叉的直线。

线性不可分（Nonlinear Separable）

不存在一条直线

二维

三维

特征空间维度 $\geqslant$ 四维时，三维的情况下，分割圆圈和叉的平面将会变成超平面（Hyperplane）。由于人眼对空间的感知仅仅局限于三维，所以说我们无法直观的画出一个图。

数学化定义

在四维以及四维以上的情况说明线性和线性不可分的情况，必须借助数学对线性可分和线性不可分给出一个精确的定义。

假设： $\omega _1'=-\omega _1,\omega _2'=-\omega _2,b'=b$ ，则

用数学严格定义训练样本以及他们的标签

假设：我们有N个训练样本和他们的标签

$\left \{ \left ( X_1,y_1 \right ),\left ( X_2,y_2 \right ),\dots,\left ( X_n,y_n \right ) \right \}$

其中 $X_i=\left [ x_{i1},x_{i2} \right ]^T$ ， $y_i=\left \{ +1,-1 \right \}$

$X_i$ 是向量， $y_i$ 是 $X_i$ 的标签。

我们规定 $X_i$ 属于 $C_1$ ，则 $y_i= +1$ ； $X_i$ 属于 $C_2$ ，则 $y_i= -1$ 。

线性可分的严格定义：一个训练样本集 $\left \{ \left ( X_1,y_1 \right ),\left ( X_2,y_2 \right ),\dots,\left ( X_n,y_n \right ) \right \}$ ，在 $i=1\sim N$ 线性可分，是指存在 $\left ( \omega _1,\omega _2,b \right )$ ，使得对 $i=1\sim N$ ，有：

（1）若 $y_i= +1$ ，则 $\omega _1X_{i1}+\omega _2X_{i2}+b > 0$

（2）若 $y_i= -1$ ，则 $\omega _1X_{i1}+\omega _2X_{i2}+b < 0$

假设：

$X_i=\begin{bmatrix} x_{i1}\\ x_{i2} \end{bmatrix}^T$ $\omega =\begin{bmatrix} \omega _{1}\\ \omega _{2} \end{bmatrix}^T$

（1）若 $y_i= +1$ ，则 $\omega ^TX_{i}+b > 0$

（2）若 $y_i= -1$ ，则 $\omega ^TX_{i}+b < 0$

线性可分定义的最简化形式

如果 $y_i= +1$ 或 $-1$ ，则上面两个公式可以合为一个。

一个训练样本集 $\left \{ \left ( X_i,y_i \right ) \right \}$ ，在 $i=1\sim N$ 线性可分，是指存在 $\left ( \omega ,b \right )$ ，似的对 $i=1\sim N$ ，有：

$y_i\left ( \omega ^TX_i+b \right )> 0$

问题描述

支持向量机算法

1、解决线性可分问题

2、再将线性可分问题中获得的结论推广到线性不可分情况

如何解决线性可分问题？

二维特征空间中的二分类问题

如图，哪条线更好？

2号线更能抵御训练样本位置的误差。

基于最优化的理论，将寻找2号线的过程变成了一个最优化的问题。

Veapick给出的回答：

假设对于任意一条分开圆圈和叉这两类的直线，把这条直线朝一侧平行的移动，直到它插到或几个训练样本位置。同时，也把这条直线朝另外一侧平行的移动，直到它插到或几个训练样本位置。

我们定义这两条虚线，它也都是平行的。

我们定义这两条平行线插到的训练样本叫做这个数据集的支持向量（Support Vectors），把这两条平行线之间的距离叫做间隔（Margin Vipic）。

断言我们想要求的2号线是使间隔margin最大的一条线。需要比较1、2、3号3条件的间隔margin。

显然2号线的margin间隔比1号线、3号线都要大。支持向量机要找的是使间隔margin最大的那一条直线。

为了让找到的直线唯一，还需要定义这条线应该再多上下两条平行线，就是图中的两条虚线所示，这条线在上下两个平行线的正中间，也就是这条线到左右两边所有的支持向量距离应该相等。

总结

在线性可分的条件下，支持向量机寻找的最优的分类直线应该满足下面三个条件：

该直线分开了两类；
该直线最大化间隔（margin）；
该直线处于间隔的中间，到所有支持向量距离相等。

上述的结果，都是基于二维特征空间的结果。在高维的特征空间中，直线将变成超平面。但以上的结论却是一致的。

优化问题

线性可分定义

一个训练样本集 $\left \{ \left ( X_i,y_i \right ) \right \}$ ，在 $i=1\sim N$ 线性可分，是指存在 $\left ( \omega ,b \right )$ 使：

（1）若 $y_i= +1$ ，则 $\omega ^TX_{i}+b > 0$

（2）若 $y_i= -1$ ，则 $\omega ^TX_{i}+b < 0$

假定训练样本集是线性可分的

支持向量机需要寻找的是最大化 间隔（Margin）的超平面。

可以写出如下形式：

1、最小化（Minimize）： $\frac{1}{2}\left \| \omega \right \|^2$

$\left \| \omega \right \|^2$

$\omega =\begin{bmatrix} \omega_1\\ \omega_2\\ ...\\ \omega_m\\ \end{bmatrix}$

$\left \| \omega \right \|^2=\omega_1^2+\omega_2^2+...+\omega_m^2=\displaystyle\sum_{i=1}^{m}\omega_i^2$

2、限制条件： $y_i\left ( \omega ^Tx_i+b \right )\geq 1,(i=1\sim N)$

已知：训练样本集 $\left \{ \left ( X_i,y_i \right ) \right \}$ ， $i=1\sim N$ ；

待求： $\left ( \omega ,b \right )$

回顾【问题描述】

支持向量机需要找一个超平面，使它的间隔最大；

离两边所有支持向量的距离相等。

事实1：

$\omega ^TX_{i}+b = 0$

$\left (\alpha \omega ^T\right ) x+\left (ab \right ) = 0$ 是同一个超平面。 $\left (a\neq 0 \right )$

事实2：

一个点 $X_0$ 到超平面 $\omega ^TX_{i}+b = 0$ 的距离 $d=\frac{\left | \omega ^Tx_0+b \right |}{\left \| \omega \right \|}$

点到超平面的距离公式

一个点 $\left ( x_0,y_0 \right )$ 到超平面 $\omega _1x_0+\omega_2y_0+b=0$ 的距离 $d=\frac{\left | \omega _1x_0+\omega _2y_0+b \right |}{\sqrt{\omega _1^2+\omega _2^2}}$

支持向量机优化问题推导中最难理解的部分

用 $a$ 去缩放 $\omega b$

$\left ( \omega,b \right )\rightarrow \left ( a \omega,a b \right )$

最终使在支持向量 $x_0$ 上有 $\left | \omega ^Tx_0+b \right |= 1$ ，而在非支持向量上 $\left | \omega ^Tx_0+b \right |> 1$

$\because$ 根据【事实1】 $\left ( \omega,b \right )$ 表示的超平面和 $\left ( a \omega,a b \right )$ 表示的超平面是同一个平面。

$\therefore$ 参数 $a$ 去缩放 $\left ( \omega,b \right )$

$\because$ 根据【事实2】，支持向量 $X_0$ 到超平面的距离将会变为： $d=\frac{\left | \omega ^Tx_0+b \right |}{\left \| \omega \right \|}=\frac{1}{\left \| \omega \right \|}$

$\therefore$ 最大化支持向量机到超平面的距离 等价于最小化 $\left \| \omega \right \|$

优化问题定为：

最小化： $\frac{1}{2}\left \| \omega \right \|^2$

最小化： $\left \| \omega \right \|$

限制条件：

支持向量到超平面的距离为： $\frac{1}{2}\left \| \varepsilon \right \|$

在非支持向量上 $\left | \omega ^Tx_0+b \right |> 1$

$\therefore$ $y_i\left ( \omega ^Tx_i+b \right )\geq 1,(i=1\sim N)$

其中 $y_i \Rightarrow$ 协调超平面的左右

$\Rightarrow \left ( \omega ^Tx_0+b \right )> 1$

$\Rightarrow \left ( \omega ^Tx_0+b \right )< 1$

如果把限制条件改成： $y_i\left ( \omega ^Tx_i+b \right )\geq 2$ ，那么会跟原来的相差一个 $a$ ，根据【事实1】，他们代表的是用一个平面。

总结

线性可分的情况下，支持向量机寻找最佳超平面的优化问题可以表示为：

凸优化（Convex Optimization） $\Rightarrow$ 只有唯一一个全局极值

最小化（Minimize）： $\frac{1}{2}\left \| \omega \right \|^2$

限制条件： $y_i=\left ( \omega ^Tx_i+b \right )\geq 1,(i=1\sim N)$

在这个训练数据以及 $\left ( X_i,y_i \right ),i=1\sim N$ 是已知的，而 $\left ( \omega,b \right )$ 是待求的。

二次规划的定义：

（1）目标函数（Objective Function）是二次项。

目标函数： $\frac{1}{2}\left \| \omega \right \|^2 \Rightarrow \frac{1}{2}\left \| \omega \right \|^2= \frac{1}{2} \omega_1 ^2+\frac{1}{2} \omega_2 ^2+...+\frac{1}{2} \omega_M ^2$

（2）限制条件是一次项。

限制条件： $y_i=\left ( \omega ^Tx_i+b \right )\geq 1,(i=1\sim N)$

要么无解，要么只有唯一的最小值。

凸优化问题的例子

根据梯度不断试探。

先找到一个 $\omega _0$ 和对应的 $f\left ( \omega _0\right )$ ，然后在 $\omega _0$ 的旁边再找到一个 $\omega _1$ 和对应的 $f\left ( \omega _1\right )$

一个优化问题是凸的 $\Rightarrow$ 总能找到高效快速算法去解决它

用凸优化解出的支持向量机最佳分类超平面的例子：

用凸优化解出的支持向量机最佳分类超平面的例子

原文地址：https://blog.csdn.net/Jay_NanX/article/details/143432581

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：GaussDB高智能--库内AI引擎：模型管理&数据集管理
下一篇：Java 实现接口幂等的九种方法：确保系统稳定性与数据一致性

查看磁盘文件系统格式 linux ubuntu blkid ext4
【代码】查看磁盘文件系统格式 linux ubuntu blkid ext4。
阅读更多2024-11-07
TLS协议基本原理与Wireshark分析_wireshark分析tls协议
传输层安全协议（TLS）是一种加密通信协议，用于确保在网络上的数据传输过程中的安全性和隐私保护。TLS的前身是安全套接层协议（SSL），后来在标准化过程中发展成为TLS。TLS协议的主要目标是通过加密
阅读更多2024-11-07
[数组排序] 0215. 数组中第K个最大元素
【代码】[数组排序] 0215. 数组中第K个最大元素。
阅读更多2024-11-07
go语言中package详解
定义package是 Go 语言的模块化单位，类似于其他编程语言中的库或模块。它将相关功能的代码组织在一起，便于复用和维护。作用：主要用于代码分组和管理，将不同功能模块进行逻辑分割，使得代码更加清晰、
阅读更多2024-11-07
深度学习：Transformer 详解
对于Transformer模型的详细解释，可以更深入地探讨其各个组成部分、工作原理、以及在自然语言处理任务中的应用方法。
阅读更多2024-11-07
25源码编译安装软件
通过今天的课程，你学习了如何通过源码编译的方式安装软件。虽然相对于使用软件包管理工具来说较为复杂，但这种方法可以让你获得软件的最新版本，并根据需要进行定制化配置。掌握了这些基本技能后，你可以更加灵活地
阅读更多2024-11-07
String可以被继承吗？
由于字符串无论在任何 Java 系统中都广泛使用，会用来存储敏感信息，如账号，密码，网络路径，文件处理等场景里，保证字符串 String 类的安全性就尤为重要了，如果字符串是可变的，容易被篡改，那我们
阅读更多2024-11-07
C02S11-Linux系统的安全与控制
在Systemd中，不同类型的Systemd对象被称为单元，Systemd单元类型是用于定义系统启动和服务管理的不同种类的配置文件。每种单元类型对应不同的系统资源或服务，并定义了如何启动和管理这些资源
阅读更多2024-11-07
双路快速排序和三路排序算法
三路快速排序是双路快速排序的进一步改进版本，三路排序算法把排序的数据分为三部分，分别为小于 v，等于 v，大于 v，v 为标定值，这样三部分的数据中，等于 v 的数据在下次递归中不再需要排序，小于 v
阅读更多2024-11-07
【Axure视频教程】多选按钮控制元件显示和隐藏
今天教大家在Axure制作多选按钮控制元件显示和隐藏的原型模板，我们点击选中或取消选中多选按钮，可以将对应的元件显示或隐藏，如果右侧有其他元件，还会将他们移动到对应位置，本教程从基础原理开始讲起然后再
阅读更多2024-11-07

机器学习2_支持向量机_线性可分——MOOC

定义

线性可分（Linear Separable）

线性不可分（Nonlinear Separable）

数学化定义

问题描述

优化问题

线性可分定义

假定训练样本集是线性可分的

1、最小化（Minimize）：

2、限制条件：

已知：训练样本集 ， ；

待求：

事实1：

事实2：

支持向量机优化问题推导中最难理解的部分

优化问题定为：

限制条件：

总结

二次规划的定义：

凸优化问题的例子

相关文章

1、最小化（Minimize）： $\frac{1}{2}\left \| \omega \right \|^2$

2、限制条件： $y_i\left ( \omega ^Tx_i+b \right )\geq 1,(i=1\sim N)$

已知：训练样本集 $\left \{ \left ( X_i,y_i \right ) \right \}$ ， $i=1\sim N$ ；

待求： $\left ( \omega ,b \right )$