清华大学-数据挖掘-5.1 最大间隔 清华大学-数据挖掘-5.2 SVM 清华大学-数据挖掘-5.3 核技巧 清华大学-数据挖掘-5.4 VC维度
SVM 和 核方法 在很多领域得到广泛应用 主要思想就是制作一个从 输入空间 到 高维空间 的映射，再去分类 通常认为，新空间中问题会被简化，线性可分
线形SVM
线性分类器 （Linear Classifier） 法线w方向垂直于分界面(w・x + b = 0) 两类：g(x)>0，g(x)<0 两类：f(x)=1，f(x)=-1 
点到超平面的距离 （Distance to Hyperplane） 1 点到超平面的距离, x = (x1,x2,x3,... ,xd) 2 原点到超平面的距离, 0 = (0, 0, 0, ... ,0) 和高中学过的点到线的距离公式一样 \[
直线一般式： g(x)=b+w_1x_1+w_2x_2=0\\
点\vec x到直线的距离：d=\frac{|g(\vec x)|}{\sqrt{w_1^2+w_2^2}}
\] 
间隔 （Margin width） 可以由SV决定，M越大容错率越强 \[
d_{\pm1}==\frac{g(x)}{||w||}=\frac {\pm1}{||w||}\\
M = \frac {2}{||w||}
\] 支持向量 （Suport Vectors） 是数据中的一小部分（拉格朗日乘数alpha!=0）， 决定了分界面能移动的范围=margin的宽度， 托着边界，对Margin有贡献 
linear SVM的 目标函数 （Objective Function） SVM预测+1/-1，点在上界的上侧(式1)预测1 ，点在下界的下侧(式2)预测-1 . 两种情况综合起来就是(式3) 分界面取等号 \[
\begin{align}
if\ y_i=+1,\ \ \ \ \vec w \cdot\vec x_i +b&\geq+1\Leftrightarrow x_i\in\{上边界的上侧\} \tag{1} \\
if\ y_i=-1,\ \ \ \ \vec w \cdot\vec x_i +b&\leq-1\Leftrightarrow x_i\in\{下边界的下侧\} \tag{2} \\
根据(1)(2)..y_i (\vec w\cdot \vec x_i + b) &\geq 1 \tag{3}\\
\end{align}
\] 
间隔最大化 Maximize the margin 
二次优化问题（a） （Quadratic Optimization problem） 正确的分类器，要在保证预测正确（式3）的前提下 最大化Margin 
拉格朗日乘数法 （Lagrange Multipliers） 间隔M最大化问题続き１ 把限制条件(3)加到w^2/2里以后可以把二次问题转化为 通过最大化Lp（求极值问题）来间隔最大化 
对偶问题 （Dual Problem） 间隔M最大化问题続き２ 把这两个公式带入Lp消掉w和b，再次将（求极值）问题转化为 （只求alpha的）二次优化问题。 
二次优化问题的解：决策边界的参数 （Solutions of w & b） 根据拉格朗日法中的式子，前k个参数w \[
\vec w = \sum_{m \in\{\alpha_m ≠ 0\}=S}\alpha_m y_m \vec x_m
\] 然后随便找个支持向量xs和ys带入, (两)边界表达式（ ys(xs・w+b)=1）求b 
SVM的实例 训练集：{ {(1,1),1}, {(0, 0),-1}, .... , {(xi1, xi2),yi}} 解：w=[1,1], b=-1 分界面：g(x) = x1 + x2 -1 = 0 间隔：2/|w|=sqrt(2) 例子中，式子很简单，直接用拉格朗日法求最值了。 
软边缘-线性SVM
软边缘线性SVM （Soft-Margin linear SVM） 因为有些错误的点不在边界外或者正确的一方，所以理论上没法找到这种目标函数。 所以加入容错，往回缩距离2ξi/｜w｜ \[
\begin{align}
if\ y_i=+1,\ \ \ \ \vec w \cdot\vec x_i +b&\geq+1-ξ_i\Leftrightarrow x_i\in\{上边界的上侧\} \tag{1} \\
if\ y_i=-1,\ \ \ \ \vec w \cdot\vec x_i +b&\leq-1+ξ_i\Leftrightarrow x_i\in\{下边界的下侧\} \tag{2} \\
根据(1)(2)..y_i (\vec w\cdot \vec x_i + b) &\geq 1 -ξ_i\tag{3}\\
\end{align}
\] （上下）决策界面的方程 \[
\vec w \cdot\vec x_i +b+ξ_i=+1\\
w \cdot\vec x_i +b-ξ_i=-1
\] 
间隔最大化 因为soft margin里加了容错ξ，所以加入惩罚项和参数C来缓和。 通过最小化w^2来最大化间隔 
（同样转换）拉格朗日求极值。 
（同样再转换）二次优化问题 
和原来比多了一个C。
非线形SVM
特征空间 （Feature Space） 特征空间往往是高纬的。 转化为特征空间中的线形分类问题。
二次基函数 （Quadratic Basis Functions） 
线性核函数 （Polynomial Kernel function） 基于这个核函数，可以降低内积运算的计算计算量 
线性核函数成立的证明 
高斯核函数 (Gaussian Kernel function) \[ K(x_i,x_j)=exp(-\frac{||x_i-x_j||^2}{2\sigma^2}) \]
字符串核函数 (String Kernel) 如果包含，则指数是两个字母间字符串的长度 
Hyperbolic Tangent核函数 (Hyperbolic Tangent Kernel) \[ K(x_i,x_j)=tanh(kx_i・x_j+C) \]
核技巧 （Kernel Trick） 像线性核函数一样。用核函数来代替内积运算可以大幅减小运算量 
运用核技巧求参数表达式 （Solutions of w & b） 
和原来相比 
模型误差
shatter ：无论点怎么分布，用模型（1条直线）就能分成两类，
模型能力 （Model Capacity） 模型-一条直线最大可以 shatter 3个点 模型-矩形窗口最大可以shatter4个点
VC维 （VC dimension） 模型m的VC dimension = h 意思是：存在h个点，不管怎么打标签，模型m都能把它分开。The VC dimension of a model M is h if there exists a set of （up to）hpoints that can be shattered by M.
决策树的VC维 树越长，节点越多 VCdimension越高
SVM的VC维 根据核函数的不同而不同
VC维的重要性 实际问题中不是很重要，因为实际问题中样本是有规律可循的，而不是随机打乱的
测试误差 的 bound ：训练误差和测试误差的距离：根号下的式子 
确信率：η 训练误差：Etrain 测试误差：Etest VC纬度：h 训练集内样本数：N 当VC-dimension变大的时候测试误差也有可能增加。 所以当两个树训练效果相同的时候，结构简单的树误差可能小（因为VC-d低）。
转载请注明来源 https://tianweiye.github.io