SVR推导

目标函数：

$\min_{w,b}\frac12||w||^2+C\sum_{i=1}^l(\xi_i+\xi_i^*) \\ s.t. \begin{cases} y_i-<w,x_i>-b&\leq\varepsilon+\xi_i \\ <w,x_i>+b-y_i &\leq\varepsilon+\xi_i^* \\ \xi_i,\xi_i^* &\geq0 \end{cases}$w,bmin​21​∣∣w∣∣2+Ci=1∑l​(ξi​+ξi∗​)s.t.⎩⎪⎨⎪⎧​yi​−<w,xi​>−b<w,xi​>+b−yi​ξi​,ξi∗​​≤ε+ξi​≤ε+ξi∗​≥0​

拉格朗日函数

$L=\frac12||w||^2+C\sum_{i=1}^l(\xi_i+\xi_i^*)-\sum_{i=1}^l(\eta_i\xi_i+\eta_i^*\xi_i^*) \\ -\sum_{i=1}^l\alpha_i(\varepsilon+\xi_i-y_i+<w,x_i>+b)\\ -\sum_{i=1}^l\alpha_i^*(\varepsilon+\xi_i^*+y_i-<w,x_i>-b)\\ s.t.\ \ \ \alpha_i^{(*)},\eta_i^{(*)}\geq 0$L=21​∣∣w∣∣2+Ci=1∑l​(ξi​+ξi∗​)−i=1∑l​(ηi​ξi​+ηi∗​ξi∗​)−i=1∑l​αi​(ε+ξi​−yi​+<w,xi​>+b)−i=1∑l​αi∗​(ε+ξi∗​+yi​−<w,xi​>−b)s.t.   αi(∗)​,ηi(∗)​≥0

原问题化为

$\min_{w,b}\max_{\alpha_i^{(*)},\eta_i^{(*)}}L(w,b, \xi_i,\xi_i^*,\alpha_i,\alpha_i^*)$w,bmin​αi(∗)​,ηi(∗)​max​L(w,b,ξi​,ξi∗​,αi​,αi∗​)

对偶问题

$\max_{\alpha_i^{(*)},\eta_i^{(*)}}\min_{w,b}L(w,b, \xi_i,\xi_i^*,\alpha_i,\alpha_i^*)$αi(∗)​,ηi(∗)​max​w,bmin​L(w,b,ξi​,ξi∗​,αi​,αi∗​)
$KKT条件 \begin{cases} \alpha_i(\varepsilon+\xi_i-y_i+<w,x_i>+b)=0 \\ \alpha_i^*(\varepsilon+\xi_i^*+y_i-<w,x_i>-b)=0 \\ (C-\alpha_i)\xi_i=0\\ (C-\alpha_i^*)\xi_i^*=0\\ \end{cases}$KKT条件⎩⎪⎪⎪⎨⎪⎪⎪⎧​αi​(ε+ξi​−yi​+<w,xi​>+b)=0αi∗​(ε+ξi∗​+yi​−<w,xi​>−b)=0(C−αi​)ξi​=0(C−αi∗​)ξi∗​=0​

求导令其为零

$\frac{\partial L}{\partial b}=\sum_{i=1}^l(\alpha_i^*-\alpha_i)=0$∂b∂L​=i=1∑l​(αi∗​−αi​)=0
$\frac{\partial L}{\partial w}=w-\sum_{i=1}^l(\alpha_i-\alpha_i^*)x_i=0$∂w∂L​=w−i=1∑l​(αi​−αi∗​)xi​=0
$\frac{\partial L}{\partial \xi_i^{(*)}}=C-\alpha_i^{(*)}-\eta_i^{(*)}=0$∂ξi(∗)​∂L​=C−αi(∗)​−ηi(∗)​=0

回归方程

$w=\sum_{i=1}^l(\alpha_i-\alpha_i^*)x_i$w=i=1∑l​(αi​−αi∗​)xi​
$f(x)=\sum_{i=1}^l(\alpha_i-\alpha_i^*)<x_i,x>+b$f(x)=i=1∑l​(αi​−αi∗​)<xi​,x>+b

SMO完事