References:

• 对核函数(kernel)最通俗易懂的理解
• 机器学习笔记029 | 核函数
• 核方法、核技巧和核函数
• 【ML系列】“非线性”二元分类

【Cover 定理】

在实际应用中，分类问题有许多是线性不可分的

References：

• 【机器学习】支持向量机 SVM（非常详细）
• 机器学习笔记（五）：支持向量机（SVM）
• 支持向量机（SVM）——原理篇

【引入】

硬间隔支持向量机是用来解决训练集完全线性可分情况的二分类模型，但在实际应用中，由于实际获取的真实样本往往会存在噪声，使得训练数据不是清晰线性可分的，又或者即使找到了一个可以使不同类样本完全分开的超平面，也很难确定这个线性可分的结果是不是由于过拟合导致的

【概述】

序列最小最优化（Sequential Minimal Optimization，SMO）算法，是用于快速求解凸二次规划问题的算法，其主要针对于支持向量机的对偶问题

对于凸优化问题：

References：

• 【机器学习】支持向量机 SVM（非常详细）
• 机器学习笔记（五）：支持向量机（SVM）
• 支持向量机（SVM）——原理篇

【假设形式】

对于给定容量为 $n$ 的线性可分训练集 $D=\{(\mathbf{x}_1,y_1),(\mathbf{x}_2,y_2),…,(\mathbf{x}_n,y_n)\}$，第 $i$ 组样本中的输入 $\mathbf{x}_i$ 具有 $m$ 个特征值，即：$\mathbf{x}_i=(x_i^{(1)},x_i^{(2)},…,x_i^{(n)})\in \mathbb{R}^m$，输出 $y_i\in\mathcal{Y}=\{+1,-1\}$

【引入】

在 单层感知机 中介绍了单层感知机，其能够处理线性可分问题，同时，根据 Novikoff 定理可知，感知机学习算法的原始形式是迭代收敛的

但单层感知机的学习算法是以误分类样本点到超平面 $S$ 的总几何间隔作为损失函数，其存在诸多解，这些解既依赖于参数 $\boldsymbol{\omega}$ 和阈值 $\theta$ 初值的选择，也依赖于迭代过程中误分类点的选择顺序

【引入】

在 单层感知机 中，介绍了单层感知机模型：

其可以处理线性可分的二分类问题

【Novikoff 定理】

设训练集 $D=\{(\mathbf{x}_1,y_1),(\mathbf{x}_2,y_2),…,(\mathbf{x}_N,y_N)\}$ 是是线性可分的，第 $i$ 组样本中的输入 $\mathbf{x}_i$ 具有 $n$ 个特征值，即：$\mathbf{x}_i=(x_i^{(1)},x_i^{(2)},…,x_i^{(n)})\in \mathbb{R}^n$，输出 $y_i\in\mathcal{Y}=\{+1,-1\}$，则：

1. 存在满足条件 $||W_{opt}||_2=1$ 的超平面 $S:W_{opt}X=\boldsymbol{\omega}_{opt}\cdot\mathbf{x}+\theta_{opt}=0$ 将训练集完全正确分开，且存在 $\gamma>0$，对所有的 $i=1,2,…,N$，有：

【原始形式与对偶形式】

对于感知机模型 $f(\mathbf{x})=\text{sign}(\boldsymbol{\omega}\cdot \mathbf{x}+\theta)$，其损失函数为：

这时感知机学习问题就转换为求解损失函数的最优化问题，即：

【概述】

感知机（Perceptron）是神经网络和支持向量机的起源算法，从结构上来讲，其分为单层感知机（Single Layer Perceptron）和多层感知机（Multi-Layer Perceptron）

单层感知机就是 MP 神经元，其一般用于处理线性可分问题，多层感知机是多个 MP 神经元的累叠，通过增加层数来处理线性不可分问题

【线性可分与分离超平面】

在二维空间上，两类点被一条直线完全分开称为线性可分