文章目錄
- SVM目标函數
-
- SVM目标函數推導
-
- 函數間隔：
- 幾何間隔：
- 軟間隔、松弛
-
- HingeLoss和軟間隔
- 随機梯度下降算法
- 線性SVM的算法描述：
- 線性SVM算法實作：
SVM目标函數
SVM目标函數推導
函數間隔：
幾何間隔：
SVM 算法就可以比較自然地叙述為：最大化（幾何間隔）d、使得：
不妨假設函數間隔為1，這樣就得到最開始的優化目标方程。
限制條件中： y i ( w . x + b ) − 1 > = 0 y_i(w . x + b) -1 >=0 yi(w.x+b)−1>=0，那個“1”就是函數間隔，注意這裡的目标是關注的是間隔， y i ( w . x + b ) − 1 = 0 y_i(w . x + b) -1 =0 yi(w.x+b)−1=0就是間隔直線上的點。
軟間隔、松弛
在數學上就是做了如下操作：
ξ i \xi_i ξi就是松弛變量，可以把函數間隔變量化，但是變化可以控制，如何控制了，使用懲罰因子來控制函數間隔。
限制條件為：
從常識來看這個優化問題的解存在，w的解唯一，但是b的解不唯一，也就是解是一組平行線
HingeLoss和軟間隔
上述目标函數限制條件 ξ i \xi_i ξi>=0，也就是函數間隔為1- ξ i \xi_i ξi，當 ξ i \xi_i ξi<0時，函數間隔就為1，當 ξ i \xi_i ξi>0時，函數間隔就為1- ξ i \xi_i ξi，等價為如下函數：
對應的目标函數為：
實際上我們一般見到的hingeLoss的目标函數是：
令 λ \lambda λ = 1\2C，他們二者是等價的。
Hinge Loss就相當于松弛因子ξ
對于間距大于一定程度的點，就沒有loss，就不用松弛。
正則化的作用相當于把分類的距離拉大。
随機梯度下降算法
松弛因子ξ>=0轉化為Hinge Loss之後使用随機梯度下降就比較友善了，針對單一樣本（ x i x_i xi, y i y_i yi)對w,b求偏導：
線性SVM的算法描述：
首先該算法是基于hingeloss的随機梯度下降算法，和感覺機算法流程一緻：周遊樣本，找出誤差最大的樣本，也就是函數間隔比1小的最多的樣本，然後在誤差為正的樣本裡面，選出誤差最大的樣本，使用這個樣本更新w和b,使用新的參數周遊樣本，直到所有的樣本誤差為負，也就是所有的樣本函數間隔大于1。
線性SVM算法實作：
import numpy as np
class LinearSVM:
def __init__(self):
self._w = self._b = None
def fit(self, x, y, c=1, lr=0.01, epoch=10000):
x, y = np.asarray(x, np.float32), np.asarray(y, np.float32)
self._w = np.zeros(x.shape[1])
self._b = 0.
for _ in range(epoch):
self._w *= 1 - lr
err = 1 - y * self.predict(x, True)
idx = np.argmax(err)
# 注意即使所有 x, y 都滿足 w·x + b >= 1
# 由于損失裡面有一個 w 的模長平方
# 是以仍然不能終止訓練，隻能截斷目前的梯度下降
if err[idx] <= 0:
continue
delta = lr * c * y[idx]
self._w += delta * x[idx]
self._b += delta
def predict(self, x, raw=False):
x = np.asarray(x, np.float32)
y_pred = x.dot(self._w) + self._b
if raw:
return y_pred
return np.sign(y_pred).astype(np.float32)
這種使用最大誤差樣本更新w,b的方式，是随機梯度下降？預測一遍全部樣本找誤差最大的樣本，為什麼不使用全部樣本的來更新w,b，我覺得随機梯度就應該随便找選擇一個樣本，使用這個樣本來更新w,b,假如有誤差就按照上述更新，沒有誤差就換一個樣本。