Support vector machine, SVM

• central point is: 找一个决策边界使得两类之间的间隔最大(也就是下图那个红线），间隔最大使它有别于感知机。间隔最大也就一位置以充分大的确信度对它进行分类

source: https://medium.com/@chih.sheng.huang821/機器學習-支撐向量機-support-vector-machine-svm-詳細推導-c320098a3d2e

• SVM則是去假設有一個hyperplane(wTx+b=0)可以完美分割兩組資料，所以SVM就是在找參數(w和b) 讓兩組之間的距離最大化。

• svm学习方法包含 线性可分 linearly separable case, 线性支持 以及 非线性支持向量机。

• 当数据线性可分，通过硬间隔最大化 （hard magin maximization) ； 当训练数据近似线性可分，通过 soft margin maximization; 当线性不可分时，用核技巧 kernal trick 及软间隔最大化 学习。

1. 线性可分支持向量机与硬间隔最大化

Form of equation defining the decision surface separating the classes is a hyperplane of the form:
wTx + b = 0
– w is a weight vector
– x is input vector
– b is bias

Functional margin 函数间隔

既然是间隔最大 那首先得了解什么是函数间隔 一般来说 一个点距离分类超平面的远近可以表示分类预测的确信程度

为了约束w，引入了几何间隔 geometric margin， 而根据下面这个图：

我们可以导出几何间隔的概念：

所以现在基本想法就是能正确划分训练数据集并且集合间隔最大的分离超平面。 而对于这个条件的分离超平面是唯一的。这里的最大化 也是hard margin

这里插一下目标函数 损失函数之类的概念 因为我又搞混了

损失函数(loss function)，或者叫代价函数(cost function)。损失函数越小，就代表模型拟合的越好。

这个时候还有一个概念叫风险函数(risk function)。风险函数是损失函数的期望，这是由于我们输入输出的 遵循一个联合分布，但是这个联合分布是未知的，所以无法计算。但是我们是有历史数据的，就是我们的训练集， 关于训练集的平均损失称作经验风险(empirical risk)，即 ，所以我们的目标就是最小化 ，称为经验风险最小化。

到这里完了吗？还没有。我们不仅要让经验风险最小化，还要让结构风险最小化。这个时候就定义了一个函数，这个函数专门用来度量模型的复杂度，在机器学习中也叫正则化(regularization)。

到这一步我们就可以说我们最终的优化函数是：即最优化经验风险和结构风险，而这个函数就被称为目标函数。

收

现在得到线性可分支持向量机学习的最优化问题：

而根据之前得到的几何间隔的概念，又转换成 max λ/||w||的问题。 又函数间隔λ并不影响它的解，故可以去λ = 1， 代入发现最小化 1/||w|| 等价于 最小化的 1/2||w||^2 （想想导数），于是就可以转化为

求解这个约束最优化问题得到最优解 w，b，由此得到分离超平面：

以及分类决策函数：

支持向量与间隔边界

训练集的样本点中与分离超平面距离最近的样本点的实例成为 支持向量 support vector，中间有个长带。Example：

source: http://web.mit.edu/6.034/wwwbob/svm-notes-long-08.pdf

分离超平面时只有支持向量起作用，其他实例点不起作用:

间隔依赖于分离超平面的法向量w， 等于2/||w||

拉格朗日来了

为了求解这个最优化问题，用拉格朗日对偶性，又是上一章的那个dual解决primal的问题。

关于拉格朗日乘子法问题可以参照 https://www.matongxue.com/madocs/939.html 非常清晰 关于 梯度 法向量 约束条件等等

个人理解就是，作为一种约束条件下的最优化求解，也就是求一种最小化距离问题，比如取最小值时两个函数可能相切 （图自Wiki）

收

整体的学习算法就是：

线性支持向量机和软间隔最大化

• 当线性不可分时... 对每个样本点引入松弛变量，于是有：

(明天继续, im really sleepy now... need to refresh my head with other theories)