SVM(Support Vector Machines)
SVM(Support Vector Machines)
0. Introduction
- Is capable of performing both linear and nonlinear classifications, regression analyses, as well as detecting outliers.
- It is well-suited for the classification of complex datasets that are relatively small or medium in size.
1. Linear SVM Classifcation
introduction
- 寻找一个离实例最宽的街道平面。这个概念被称为大间隔分类。
- 这条街道完全是被边缘上的实例所影响的，这些实例就是支持向量。
- SVM模型对于特征尺度敏感。
Hinge-free-margin classification, also known as Hinge-loss-based classification, is a machine learning method designed to achieve maximum margin separation between different classes. A rigorous requirement for data separation is imposed to ensure clear boundaries between classes. The two critical challenges in this approach are
1. the data is linearly separable
2. it is quite sensitive to outliersSoft Margin Classification
允许一些异常值保留在street中，并寻求在尽可能扩大street的同时限制margin违反
通过C超参数调节street的宽度范围
1. C越大，宽度越小，对模型要求越严格
2. C越小，宽度越大，对模型要求越不严格三种实现API ——
该模型采用Hinge损失函数，并设置C参数为1。
该分类器配置使用Hinge损失函数和Alpha参数值为1/(m*C)，特别适用于内存中无法容纳的大规模数据集（外存训练）以及在线分类任务。
A Support Vector Classifier configured with a linear kernel and C parameter set to 1 is relevant for optimization purposes.
2. Nonlinear SVM Classifcation
degree，多项式的阶； coef0 controls how much the model is influenced by highdegree polynomials versus low-degree polynomials，C controls the width of street，C越大对street要求越严格
degree...
Gaussian RBF Kernel
通过引入相似度特征来处理非线性数据的一种方法是基于坐标系转换的技术——选择landmark点，并将每个点的坐标映射到与该landmark的相似关系中去。高斯径向基函数（RBF）就是一个典型的应用案例；它通过计算点X与landmark l之间的距离平方并取指数负值来实现这一转换过程：
Gaussian \; RBF \; \phi\gamma(X, l) = e^{-\gamma||X-l||^2}
此外，在这一过程中可以通过引入新的坐标系来巧妙地将复杂非线性的数据转化为简单的线性可分形式：
The simplest approach is to create a landmark at the location of each and every instance，并将原始数据从非线性的X(m, n) 转换为线性的X(m, m) 表示形式
SVC(kernel=“rbf”, gamma=5, C=0.001)
第一个超参数γ（gamma）是一个重要的调节因子，在指数项中起到关键作用：它控制着决策边界（street）的平滑程度——当γ越大时，在指数运算中数值的变化速度加快，在钟型曲线上表现为更加陡峭，在分类模型中表现为更高的拟合能力以及更低的偏差水平；相反地，在γ较小时则会表现出较低的拟合能力以及较高的偏差水平
第二个超参数C则直接决定了决策边界（street）宽度的影响范围——当C增大时决策边界会变得更加狭窄；这意味着模型在训练阶段能够更好地避免过拟合现象的发生；然而与此同时模型可能会因为过度拟合而表现出较低的一般化性能；相反地当C减小时决策边界会变得更加宽泛从而允许模型在一定程度上牺牲拟合能力以换取更好的泛化性能
Computational Complexity
| Class | 时间复杂度 | 超大数据量 | 特征压缩处理 | 核函数 |
|---|---|---|---|---|
| LinearSVC | O(m*n) | No | Yes | No |
| SGDClassifier | O(m*n) | Yes | Yes | No |
| SVC | O(mmn) to O(mmm*n) | No | Yes | Yes |
3. SVM Regression
-
线性支持向量回归模型
使用epsilon值为1.5的LinearSVR模型
为了获得更好的模型性能，请确保训练数据已标准化和去均值化
其中超参数ϵ（即epsilon）越小，则方差会越大 -
非线性回归问题
支持向量回归（SVR）参数设置为：核函数为多项式型（poly），其次数设定为2次方（degree），惩罚系数（C）设为100值域内的标准值（default value），容错率（epsilon）设定为0.1范围内的默认值（default value）。
其中参数C越小，则表示施加于模型的正则化强度越大。
4. Under the Hood
Decision Function and Predictions
1）新约定，the bias term will be called b，the feature weights vector will be called w，No bias feature x_0
2）几个超平面
Decision function —— 决策函数是一个n+1维的超平面
Decision boundary —— 决策边界是当决策函数值为0时的一个n维的超平面，the set of points where the decision function is equal to 0
Margin boundary —— street的边界是 the decision function is equal to 1 or –1的超平面，永远和决策边界平行
3）Linear SVM classifer
||w||决定了street的宽度，当||w||越大的时候，street的宽度越小
\hat{y} = \begin{cases} 0 \quad if \; w^Tx+b
Training Objective
1）Hard margin
目标是在最大化street宽度的同时最小化权重向量的模长||w||。
定义t(i)=-1表示负实例（当y(i)=0时），而t(i)=1表示正实例（当y(i)=1时）。
2）Soft margin
在保证最大化边界的同时允许一定程度的误分类情况发生。
其中ζ度量第i个实例能违反边界的程度——定义ζ(i)用来衡量第i个实例违反边界的程度有多大。
超参数C即上文所述的参数——当C增大时会使ζ减小，这意味着模型的方差会增大且street宽度会减小；相反地，减小C会导致ζ增大，在这种情况下模型的偏差会增大且street宽度会变宽。
不等式右边的项1- ζ(i)，表示的是margin到决策边界的距离——随着 ζ(i)值增大，在street中被允许出现并违反margin的最大数量也会随之增加，并且这会使得模型的偏差变大、对应的 C值也会变小、margin整体宽度也会变宽。
如何从物理上解释ζ越大，1-ζ越小，模型反而越宽敞？
\begin{aligned} Rigidity \; margin \; &linear \; SVM \; classification \; objective \\ \underset{w, b}{\text{minimize}} &\quad \frac{1}{2}w^Tw \\ subject \; to &\quad t^{(i)}(w^T x^{(i)} + b) \geq 1 \; for \; i=1,2,\dots,m \\ \\ Flexibility \; margin \; &linear \; SVM \; classification \\&\text{objective such that} \\&\quad t^{(i)}(w^T x^{(i)} + b) + C\zeta^{(i)} - 1 = 0\\&\quad with\;\zeta^{(i)}\geq0,\;\text{for}\;\ i=1,2,\dots,m\\&\quad and\\&\quad C>0\\end{aligned}
Quadratic Programming
Both the hard-margin and soft-margin problems represent convex quadratic optimization challenges constrained by linear limitations. Such optimization problems are commonly referred to as Quadratic Programming (QP) problems.
双重优化问题是研究领域中的核心议题之一。在优化理论中，在给定一个带约束的优化问题（即原问题）的基础上，我们可以相应地定义并求解其对偶（dual）优化模型。这种原-对偶模型之间的关系具有重要的理论价值和实际应用意义。在机器学习领域中尤其是支持向量机(SVM)的学习过程中，在解决分类任务时会自然地对应到这一理论框架下的一种特定实现方式。
Kernelized SVM
常用的核函数
\begin{aligned} Linear \; Kernel \; &: \quad K(\mathbf{a}, \mathbf{b}) = \mathbf{a}^\top \cdot \mathbf{b} \\ Polynomial \; Kernel \; &: \quad K(\mathbf{a}, \mathbf{b}) = (\gamma \cdot (\mathbf{a}^\top \cdot \mathbf{b}) + r)^d \\ Gaussian\ RBF\ Kernel\; &: \quad K(\mathbf{a}, \mathbf{b}) = e^{-\gamma\|\mathbf{a}-\mathbf{b}\|^2} \\ Sigmoid\ Kernel\; &: \quad K(\mathbf{a}, \mathbf{b}) = tanh(\gamma\cdot (\mathbf{a}^\top \cdot \mathbf{b}) + r) \end{aligned}
- Online SVMs
线性支持向量机分类器的成本函数
J(w, b) = \frac{1}{2}w^T \cdot w + C\sum_{i=1}^{m}\max(0,\; t^{(i)}(w^T \cdot x^{(i)} + b))
前半部分代表截距项的斜率——导致更大的间隔；
后半部分则代表位于街道中间的所有点的误差——尽可能小且数量最少；
Hinge损失函数——\max(0,\; 1 - t)被称为Hinge损失函数，在t>1时该函数值恒为零；对应街道边缘以外的数据点集合
@ 学必求其心得，业必贵其专精