对于某些数据集, 并不能找到一个超平面把它们分开, 也就是说不能找到一组 w⃗ , b , 满足 yi(w⃗ ⋅x⃗ i+b)≥1 , 解决办法就是引入一个松弛变量 ξi , 让所有样本点都满足 yi(w⃗ ⋅x⃗ i+b)≥1−ξi , 这样得到一个新的约束条件, 可以注意到 ξi 与1的关系,等于1的时候样本刚好落在分隔超平面上,大于1的时候符号反转, 说明被分错.形象的解释就是把某些样本点挪一下, 挪成线性可分的, 并且要使得挪的距离尽量小(挪太远就误分了), 同时间隔尽量大, 这样支持向量机的学习问题就变成了
minw⃗ ,b,ξ⃗ 12||w⃗ ||2+C∑iξi s.t. yi(w⃗ ⋅x⃗ i+b)≥1−ξi ξi≥0 C是一个关联系数, 若C为无穷大, 优化问题则要求 ξi=0 , 迫使样本均满足约束条件. 还有另外一种解释, ξi 是损失函数(比如合页损失函数), 若样本没有落在间隔带正确的那一边, 则 ξi 大于0, 学习问题是让总损失尽可能小, 并且加了L2正则项 (||w⃗ ||2)和硬间隔类似, 利用拉格朗日乘子法可以得到对偶问题, 拉格朗日函数为
L(w⃗ ,b,ξ⃗ ,α⃗ ,μ⃗ )=12||w⃗ +C∑iξi+∑iαi(yi(w⃗ ⋅x⃗ i+b)−1+ξi)−∑iμiξi 进行求导, 代入等操作以后可得对偶问题 minα⃗ 12∑i∑jαiαjyiyj(x⃗ i⋅x⃗ j)−∑iαi s.t.∑iαiyi=0, C≥αi≥0 求得最优解 α∗→ 之后 w∗=∑iα∗iyixi, 选择合适的 α∗j b∗=yj−∑iα∗iyi(x⃗ i⋅x⃗ j)支持向量机的对偶问题为
minα⃗ 12∑i∑jαiαjyiyj(x⃗ i⋅x⃗ j)−∑iαis.t.∑iαiyi=0, C≥αi≥0
有时候遇到非线性划分的时候, 需要将样本映射到高维空间, 在高维空间中是线性可分的, 假设有一个从 χ 到 H 的映射ψ(x⃗ ), 使得
K(x⃗ ,z⃗ )=ψ(x⃗ )⋅ψ(z⃗ )为了避免直接计算高维空间的 ψ(x⃗ )⋅ψ(z⃗ ) , 选取的 K(x⃗ ,z⃗ ) 具有内积性质就可以了,这种方法被称为核诡计(kennel trick). 通常所说的和函数是正定核, 具有内积的性质.
李航的书上定义的再生核希尔伯特空间 H 是一个函数空间, 里面定义了函数的内积和范数
正定核: 对于任意个样本x⃗ i∈χ, i=1,2,...,m , Gram矩阵: [K(x⃗ i,x⃗ j)]m×m 是半正定的, 则称 K(x⃗ ,z⃗ ) 为正定核函数.
常用的有多项式核
K(x⃗ ,z⃗ )=(x⃗ ⋅z⃗ +1)p 高斯核 K(x⃗ ,z⃗ )=exp(−||x⃗ −z⃗ ||p2σ2) 等等.这样, 目标函数变成
W(α⃗ )=12∑i∑jαiαjyiyjK(x⃗ i⋅x⃗ j)−∑iαi决策函数变为
f(x⃗ )=sign∑iα∗iyiK(x⃗ i,x⃗ )+b∗