机器学习day6-svm中训练误差为0存在问题

2020-06-02 本文已影响0人 rivrui

支持向量机

支持向量机（Support Vector Machine，SVM）是众多监督学习方法中十分出色的一种。svm中广为流传的魔鬼与天使的故事。

分球问题

分球问题的解

复杂的分球问题

高维空间中的解

我们所看到的解

在空间中线性可分的两类点，分别向SVM分类的超平面上做投影，这些点在

是否存在一组参数使得SVM训练误差为0

一个使用高斯核 $(K(x,z)=e-||x-z||^{2/r^{2}})$ 训练的SVM为例。
SVM的预测公式
$f(x)=\sum_{i=1}^{m}a_{i} y^{(i)}K(x^{(i)},x)+b$
其中 $((x^{(1)},y^{(1)}),...,(x^{(m)},y^{(m)})$ 是训练样本，而 $\left\{ a_1,...,a_m,b\right\}$ 以及高斯核参数 $\gamma$ 为训练样的参数。有用不存在两个点在同一位置，因此对于任意的 $i\not ={j}$ ，有 $|x^{(i)}-x^{(j)}|\geq\epsilon$ 。
对于任意的i，固定 $a_{i}$ =1和b=0，只保留参数 $\gamma$ 。
$f(x)=\sum_{i=1}^{m}a_iy^{(i)}K(x^{(i)},x)+b$
$=\sum_{i=1}^my^{(i)}K(x^{(i)},x)$
$=\sum_{i=1}^my^{(i)}e^{-||x-x^{(i)}||^2/\gamma^2}$
将 $x^{(j)}$ 带入，则有
$f(x^{(j)})=\sum_{i=1}^my^{(i)}e^{-||x^{(j)}-x^{(i)}||^2/\gamma^2}$
$f(x^{(j)})-y^{(j)}=\sum_{i=1,i\not ={j}}^my^{(i)}e^{-||x^{(j)}-x^{(i)}||^2/\gamma^2}$
$||f(x^{(j)})-y^{(j)}||\le \sum_{i=1,i\not ={j}}^my^{(i)}e^{-||x^{(j)}-x^{(i)}||^2/\gamma^2}$
而 $||x(j)-x(i)||\ge\epsilon$ ，取 $\gamma=\epsilon/\sqrt{logm}$ ，
$||f(x^{(j)})-y^{(j)}||\le||\sum_{i=1,i\ne j}^{m}e^{-||x^{(j)}-x^{(i)}||^2/\gamma^2}||$
$\le ||\sum_{i=1,i\ne j}^{m}e^{-logm}||=\frac{m-1}{m}\le 1$
因此真实值与预测结果的距离小于1，当真实值为1，预测结果必定属于（0，1）,此时预测结果为正，当真实值为-1，预测结果属于(-1,0)，一寸结果为负，因此。所有样本的类别全部被预测正确，则训练误差为0。