python為什么叫爬蟲，SVR模型python應用

2023-10-09 阅读 62 评论 0

摘要：1. SVR模型 SVR應用鏈接,處理波士頓房價預測問題在SVM分類模型中，我們的目標函數是讓12∣∣w∣∣2\cfrac{1}{2}||w||^221?∣∣w∣∣2最小，同時讓各個訓練集中的點盡量遠離自己類別一邊的的支持向量，即yi(w??(xi)+b)≥1y_i(w \cdot \phi(x_i )+

1. SVR模型

SVR應用鏈接,處理波士頓房價預測問題
在SVM分類模型中，我們的目標函數是讓 $12∣∣w∣∣2\cfrac{1}{2}||w||^2$ 最小，同時讓各個訓練集中的點盡量遠離自己類別一邊的的支持向量，即 $yi(w??(xi)+b)≥1y_i(w \cdot \phi(x_i )+ b) \geq 1$ 。若加入一個松弛變量 $ξi≥0\xi_i \geq 0$ ,則目標函數為：
$12∣∣w∣∣22+C∑i=1mξi(式1)\frac{1}{2}||w||_2^2 +C\sum\limits_{i=1}^{m}\xi_i\tag{式1}$
約束條件為：
$yi(w??(xi)+b)≥1?ξi(式2)y_i(w \cdot \phi(x_i ) + b ) \geq 1 - \xi_i\tag{式2}$
現在用于回歸模型，優化目標函數可以繼續和SVM分類模型保持一致為 $12∣∣w∣∣22\frac{1}{2}||w||_2^2$ ，但是約束條件不可能是讓各個訓練集中的點盡量遠離自己類別一邊的的支持向量，因為我們是回歸模型，沒有類別。對于回歸模型，我們的目標是讓訓練集中的每個點 $x_i,y_i)$ ,盡量擬合到一個線性模型 $yi≈w??(xi)+by_i \approx{ w \cdot \phi(x_i ) +b }$ 。一般的回歸模型，使用均方差作為損失函數,但是SVR不是這樣定義損失函數的。

SVR需要定義一個常量 $?>0\epsilon>0$ ,對于某一個點 $x_i,y_i)$ ，如果 $∣yi?w??(xi)?b∣≤?|y_i - w \cdot\phi(x_i ) -b| \leq \epsilon$ ，則沒有損失，如果 $∣yi?w??(xi)?b∣>?|y_i - w \cdot \phi(x_i ) -b| >\epsilon$ ,則對應的損失為 $∣yi?w??(xi)?b∣??|y_i - w \cdot \phi(x_i ) -b| - \epsilon$ ，這和均方差損失函數不同，如果是均方差，那么只要 $yi?w??(xi)?b≠0y_i - w \cdot\phi(x_i ) -b \neq{0}$ ，那么就會有損失。
如圖所示，在條帶里面的點都是沒有損失的，但是外面的點的是有損失的:
在這里插入圖片描述
這樣一來我們的SVR模型的損失函數度量為：
$err(xi,yi)={0∣yi?w??(xi)?b∣≤?∣yi?w??(xi)?b∣??∣yi?w??(xi)?b∣>?(式3)err(x_i,y_i) = \begin{cases}{ 0\qquad\qquad\qquad\qquad\qquad\quad|y_i - w \cdot \phi(x_i ) -b| \leq\epsilon}\\ |y_i - w \cdot \phi(x_i ) -b| - \epsilon\qquad {|y_i - w \cdot \phi(x_i ) -b|>\epsilon} \tag{式3} \end{cases}$

2. SVR模型目標函數的原始形式

定義目標函數如下：
$min12∣∣w∣∣22s.t∣yi?w??(xi)?b∣≤?(i=1,2,...m)(式4)\begin{aligned} &min\quad \cfrac{1}{2}||w||_2^2\\ &s.t \qquad |y_i - w \cdot \phi(x_i ) -b| \leq \epsilon(i =1,2,...m) \end{aligned}\tag{式4}$
和SVM模型相似，SVR模型也可以對每個樣本 $x_i,y_i)$ 加入松弛變量 $ξi≥0\xi_i \geq 0$ , 但是由于我們這里用的是絕對值，實際上是兩個不等式，也就是說兩邊都需要松弛變量，定義為 $ξi∨,ξi∧\xi_i^{\lor}, \xi_i^{\land}$ , 則SVR模型的損失函數度量在加入松弛變量之后變為：
$min12∣∣w∣∣22+C∑i=1m(ξi∨+ξi∧)s.t.???ξi∨≤yi?w??(xi)?b≤?+ξi∧ξi∨≥0,ξi∧≥0(i=1,2,...,m)(式5)\begin{aligned} min\quad &\cfrac{1}{2}||w||_2^2 + C\sum_{i=1}^{m}(\xi_i^{\lor}+ \xi_i^{\land}) \\ &s.t. \quad -\epsilon - \xi_i^{\lor} \leq {y_i - w \cdot \phi(x_i ) -b }\leq\epsilon +\xi_i^{\land}\\ &\xi_i^{\lor} \geq 0, \quad\xi_i^{\land} \geq 0 (i = 1,2,..., m) \end{aligned}\tag{式5}$
依然和SVM分類模型相似，用拉格朗日函數將目標優化函數變成無約束的形式，如下：
$L(w,b,α∨,α∧,ξi∨,ξi∧,μ∨,μ∧)=12∣∣w∣∣22+C∑i=1m(ξi∨+ξi∧)+∑i=1mα∨(???ξi∨?yi+w??(xi)+b)+∑i=1mα∧(yi?w??(xi)?b???ξi∧)?∑i=1mμ∨ξi∨?∑i=1mμ∧ξi∧(式6)\begin{aligned} L(w,b,\alpha^{\lor}, \alpha^{\land},\xi_i^{\lor}, \xi_i^{\land}, \mu^{\lor},\mu^{\land}) &= \frac{1}{2}||w||_2^2 + C\sum_{i=1}^{m}(\xi_i^{\lor}+ \xi_i^{\land}) + \sum_{i=1}^{m}\alpha^{\lor}(-\epsilon - \xi_i^{\lor} -y_i +w \cdot\phi(x_i) + b) +\\ &\sum_{i=1}^{m} \alpha^{\land}(y_i -w \cdot \phi(x_i ) - b -\epsilon -\xi_i^{\land}) -\sum_{i=1}^{m}\mu^{\lor}\xi_i^{\lor} -\sum_{i=1}^{m}\mu^{\land}\xi_i^{\land} \end{aligned}\tag{式6}$
其中 $μ∨≥0,μ∧≥0,αi∨≥0,αi∧≥0\mu^{\lor} \geq 0, \mu^{\land}\geq 0, \alpha_i^{\lor} \geq 0, \alpha_i^{\land}\geq 0$ ,均為拉格朗日乘子。

3. SVR模型的目標函數的對偶形式

根據SVR模型的目標函數的原始形式,我們的目標是:
$min?(w,b,ξi∨,ξi∧)max?(μ∨≥0,μ∧≥0,αi∨≥0,αi∧≥0)L(w,b,α∨,α∧,ξi∨,ξi∧,μ∨,μ∧)(式7)\min({w,b,\xi_i^{\lor}, \xi_i^{\land}})\qquad \max({\mu^{\lor}\geq 0, \mu^{\land}\geq 0,\alpha_i^{\lor}\geq 0,\alpha_i^{\land}\geq 0})\quad L(w,b,\alpha^{\lor}, \alpha^{\land},\xi_i^{\lor}, \xi_i^{\land}, \mu^{\lor},\mu^{\land})\tag{式7}$
和SVM分類模型一樣，這個優化目標也滿足KKT條件，也就是說，我們可以通過拉格朗日將優化問題轉化為等價的對偶問題來求解如下：
$max?(μ∨≥0,μ∧≥0,αi∨≥0,αi∧≥0)min?(w,b,ξi∨,ξi∧)L(w,b,α∨,α∧,ξi∨,ξi∧,μ∨,μ∧)(式8)\max({\mu^{\lor}\geq 0, \mu^{\land}\geq 0,\alpha_i^{\lor}\geq 0,\alpha_i^{\land}\geq 0})\qquad\min({w,b,\xi_i^{\lor}, \xi_i^{\land}})\qquad \quad L(w,b,\alpha^{\lor}, \alpha^{\land},\xi_i^{\lor}, \xi_i^{\land}, \mu^{\lor},\mu^{\land})\tag{式8}$ 　　　　
可以先求優化函數對于 $w,b,ξi∨,ξi∧w,b,\xi_i^{\lor}, \xi_i^{\land}$ 的極小值, 接著再求拉格朗日乘子 $α∨,α∧,μ∨μ∧\alpha^{\lor}, \alpha^{\land}, \mu^{\lor}\mu^{\land}$ 的極大值。
首先我們來求優化函數對于 $w,b,ξi∨,ξi∧w,b,\xi_i^{\lor}, \xi_i^{\land}$ 的極小值。
這個可以通過求偏導數求得：
$?L?w=0?w=∑i=1m(αi∧?αi∨)?(xi)(式9)\frac{\partial L}{\partial w} = 0 \Rightarrow w = \sum\limits_{i=1}^{m}(\alpha_i^{\land} - \alpha_i^{\lor})\phi(x_i)\tag{式9}$
$?L?b=0?∑i=1m(αi∧?αi∨)=0(式10)\frac{\partial L}{\partial b} = 0 \Rightarrow \sum\limits_{i=1}^{m}(\alpha_i^{\land} - \alpha_i^{\lor}) = 0\tag{式10}$
$?L?ξi∨=0?C?α∨?μ∨=0(式11)\frac{\partial L}{\partial \xi_i^{\lor}} = 0 \Rightarrow C-\alpha^{\lor}-\mu^{\lor} = 0 \tag{式11}$
$?L?ξi∧=0?C?α∧μ∧=0(式12)\frac{\partial L}{\partial \xi_i^{\land}} = 0 \Rightarrow C-\alpha^{\land}\mu^{\land} = 0\tag{式12}$ 　　　
好了，把上面4個式子帶入 $L(w,b,α∨,α∧,ξi∨,ξi∧,μ∨,μ∧)L(w,b,\alpha^{\lor},\alpha^{\land},\xi_i^{\lor}, \xi_i^{\land}, \mu^{\lor},\mu^{\land})$ 消去 $w,b,ξi∨,ξi∧w,b,\xi_i^{\lor}, \xi_i^{\land}$ 了。
最終得到的對偶形式為：
$max?α∨,α∧?∑i=1m(??yi)αi∧+(?+yi)αi∨)?12∑i=1,j=1m(αi∧?αi∨)(αj∧?αj∨)Kijs.t.∑i=1m(αi∧?αi∨)=00<αi∨<C(i=1,2,...m)0<αi∧<C(i=1,2,...m(式13)\begin{aligned} \underbrace{ max }_{\alpha^{\lor}, \alpha^{\land}} -\sum\limits_{i=1}^{m}(\epsilon-y_i)\alpha_i^{\land}&+ (\epsilon+y_i)\alpha_i^{\lor}) - \frac{1}{2}\sum\limits_{i=1,j=1}^{m}(\alpha_i^{\land} - \alpha_i^{\lor})(\alpha_j^{\land} -\alpha_j^{\lor})K_{ij} \\ &s.t. \sum\limits_{i=1}^{m}(\alpha_i^{\land} - \alpha_i^{\lor}) = 0\\ &0<\alpha_i^{\lor} <C \; (i =1,2,...m)\\ &0<\alpha_i^{\land} <C (i =1,2,...m\tag{式13} \end{aligned}$

取負號求最小值可以得到和SVM分類模型類似的求極小值的目標函數如下：
$min?α∨,α∧12∑i=1,j=1m(αi∧?αi∨)(αj∧?αj∨)Kij+∑i=1m(??yi)αi∧+(?+yi)αi∨s.t.∑i=1m(αi∧?αi∨)=00<αi∨<C(i=1,2,...m)0<αi∧<C(i=1,2,...m)(式14)\underbrace{ min}_{\alpha^{\lor}, \alpha^{\land}}\frac{1}{2}\sum\limits_{i=1,j=1}^{m}(\alpha_i^{\land} - \alpha_i^{\lor})(\alpha_j^{\land} -\alpha_j^{\lor})K_{ij} + \sum\limits_{i=1}^{m}(\epsilon-y_i)\alpha_i^{\land}+ (\epsilon+y_i)\alpha_i^{\lor} \\ s.t. \sum\limits_{i=1}^{m}(\alpha_i^{\land} - \alpha_i^{\lor}) = 0\\ 0 < \alpha_i^{\lor} <C (i =1,2,...m)\\ 0<\alpha_i^{\land} <C (i =1,2,...m)\tag{式14}$
對于此目標函數，可以用SMO算法來求出對應的 $α∨,α∧\alpha^{\lor}, \alpha^{\land}$ ，進而求出我們的回歸模型系數 $w, b$ 。

4.SVR模型系數的稀疏性

python為什么叫爬蟲？在SVM分類模型中，我們的KKT條件的對偶互補條件為: $αi?(yi(w??(xi)+b)?1+ξi?)=0\alpha_{i}^{*}(y_i(w \cdot \phi(x_i) + b) - 1+\xi_i^{*}) = 0$ ，而在回歸模型中，我們的對偶互補條件類似如下：
$αi∨(?+ξi∨+yi?w??(xi)?b)=0(式15)\alpha_i^{\lor}(\epsilon + \xi_i^{\lor} + y_i - w \cdot \phi(x_i ) - b) = 0 \tag{式15}$
$αi∧(?+ξi∧?yi+w??(xi)+b)=0(式16)\alpha_i^{\land}(\epsilon + \xi_i^{\land} -y_i + w \cdot \phi(x_i ) + b) = 0\tag{式16}$
根據松弛變量定義條件，如果 $∣yi?w??(xi)?b∣<?|y_i - w \cdot \phi(x_i ) -b| <\epsilon$ ，我們有 $ξi∨=0,ξi∧=0\xi_i^{\lor} = 0, \xi_i^{\land}= 0$ ，此時 $?+ξi∨+yi?w??(xi)?b≠0,?+ξi∧?yi+w??(xi)+b≠0\epsilon + \xi_i^{\lor} + y_i - w \cdot \phi(x_i ) - b \neq 0, \epsilon + \xi_i^{\land} -y_i + w \cdot \phi(x_i ) + b \neq 0$ 這樣要滿足對偶互補條件，只有 $αi∨=0,αi∧=0\alpha_i^{\lor} = 0, \alpha_i^{\land} = 0$ 。定義樣本系數系數
$βi=αi∧?αi∨(式17)\beta_i =\alpha_i^{\land}-\alpha_i^{\lor} \tag{式17}$
根據上面 $w$ 的計算式 $\sum_{i=1}^{m}(\alpha_i^{\land} - \alpha_i^{\lor})\phi(x_i)$ ，發現此時 $βi=0\beta_i = 0$ ,也就是說 $w$ 不受這些在誤差范圍內的點的影響。對于在邊界上或者在邊界外的點， $αi∨≠0,αi∧≠0\alpha_i^{\lor} \neq 0, \alpha_i^{\land} \neq 0$ ，此時 $βi≠0\beta_i \neq 0$ 。
推導參考鏈接