第7章 支持向量机

习题7.1

  比较感知机的对偶形式与线性可分支持向量机的对偶形式。

解答：

解答思路：

1. 列出感知机的原始形式；
2. 写出感知机的对偶形式；
3. 列出线性可分支持向量机的原始形式；
4. 写出线性可分支持向量机的对偶形式；
5. 比较感知机和线性可分支持向量机的对偶形式。

解答步骤：

第1步：感知机的原始形式

  根据书中第2.3.1节的感知机学习算法的原始形式：

给定一个训练数据集

T={(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)}

\min \limits_{w,b} L(w,b)=-\sum_{x_i \in M} y_i(w \cdot x_i + b)

w \leftarrow w + \eta y_i x_i \
b \leftarrow b + \eta y_i

\alpha_i \leftarrow \alpha_i + \eta \
b \leftarrow b + \eta y_i

w=\sum_{i=1}^N \alpha_i y_i x_i\
b=\sum_{i=1}^N \alpha_i y_i

\min_{w,b} L(w,b)=-\sum_{x_i \in M} y_i(w \cdot x_i + b)

\min_{w,b} L(w,b) = \min_{\alpha} L(\alpha) = - \sum \limits_{x_i \in M} ( y_i ( \sum_{j=1}^N \alpha_j y_j x_j \cdot x_i + \sum_{j=1}^N \alpha_j y_j ) )

\begin{align}
\displaystyle \min_{w,b} \quad & \displaystyle \frac{1}{2} |w|^2 \tag{7.13} \
\text{s.t.} \quad & y_i(w \cdot x_i + b) -1 \geqslant 0, \quad i=1, 2,\cdots, N \tag{7.14} \
\end{align}

\begin{array}{cl}
\displaystyle \min_{\alpha} & \displaystyle \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) - \sum_{i=1}^N
\alpha_i \
\text{s.t.} & \displaystyle \sum_{i=1}^N \alpha_i y_i = 0 \
& \alpha_i \geqslant 0, \quad i=1,2,\cdots,N
\end{array}

w^* = \sum_{i=1}^N \alpha_i^* y_j x_i

b^*=y_i-\sum_{i=1}^N \alpha_i^* y_i (x_i \cdot x_j)

w^* \cdot x + b^* = 0

f(x) = \text{sign}(w^* \cdot x + b^*)

\min_{w,b} L(w,b) = \frac{1}{2} |w|^2

\min_{w,b} L(w,b) = \min_{\alpha} L(\alpha) = \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) - \sum_{i=1}^N
\alpha_i

\begin{array}{cl}
\displaystyle \min \limits_{w,b,\xi} & \displaystyle \frac{1}{2} |w|^2 + C \sum_{i=1}^N \xi_i^2 \
\text{s.t.} & y_i(w \cdot x_i + b) \geqslant 1 - \xi_i, \quad i=1,2,\cdots, N \
& \xi_i \geqslant 0, \quad i=1,2,\cdots, N
\end{array}

\begin{align}
\displaystyle \min \limits_{x \in R^n} \quad & f(x) \tag{C.1} \
\text{s.t.} \quad & c_i(x) \leqslant 0, \quad i=1,2,\cdots, k \tag{C.2} \
\quad & h_j(x) = 0, \quad j=1,2,\cdots, l \tag{C.3}
\end{align}

L(x,\alpha, \beta) = f(x) + \sum_{i=1}^k \alpha_i c_i(x) + \sum_{j=1}^l \beta_j h_j(x) \tag{C.4}

\theta_P(x) = \max \limits_{\alpha,\beta:\alpha_i \geqslant 0} L(x, \alpha, \beta) \tag{C.5}

\min \limits_{x} \theta_P(x) = \min \limits_{x} \max \limits_{\alpha,\beta:\alpha_i \geqslant 0} L(x, \alpha, \beta)

\begin{array}{cl}
\displaystyle \min \limits_{w,b,\xi} & \displaystyle \frac{1}{2} |w|^2 + C \sum_{i=1}^N \xi_i^2 \
\text{s.t.} & y_i(w \cdot x_i + b) \geqslant 1 - \xi_i, \quad i=1,2,\cdots, N \
& \xi_i \geqslant 0, \quad i=1,2,\cdots, N
\end{array}

\left { \begin{array}{ll}
\displaystyle f(x) = \frac{1}{2} |w|^2 + C \sum_{i=1}^N \xi_i^2 \
c_i^{(1)}(x) = 1 - \xi_i - y_i(w \cdot x_i + b), \quad i = 1,2,\cdots, N \
c_i^{(2)}(x) = - \xi_i, \quad i = 1,2,\cdots, N
\end{array} \right.

L(w,b,\xi, \alpha, \mu) = \frac{1}{2} |w|^2 + C \sum_{i=1}^N \xi_i^2 - \sum_{i=1}^N \alpha_i(y_i (w \cdot x_i + b)-1 + \xi_i) - \sum_{i=1}^N \mu_i \xi_i

\begin{array}{l}
\displaystyle \nabla_w L(w,b,\xi,\alpha,\mu) = w - \sum_{i=1}^N \alpha_i y_i x_i = 0 \
\displaystyle \nabla_b L(w,b,\xi,\alpha,\mu) = -\sum_{i=1}^N \alpha_i y_i = 0 \
\displaystyle \nabla_{\xi_i} L(w,b,\xi,\alpha,\mu) = 2C \xi_i - \alpha_i - \mu_i = 0
\end{array}

\begin{array}{l}
\displaystyle w = \sum_{i=1}^N \alpha_i y_i x_i \
\displaystyle \sum_{i=1}^N \alpha_i y_i = 0 \
\displaystyle 2C \xi_i - \alpha_i - \mu_i = 0
\end{array}

\begin{aligned}
L(w, b, \xi, \alpha, \mu)
&= \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) + C \sum_{i=1}^N \xi_i^2 - \sum_{i=1}^N \alpha_i y_i \left( \left( \sum_{j=1}^N \alpha_j y_j x_j \right) \cdot x_i + b \right) \
& + \sum_{i=1}^N \alpha_i - \sum_{i=1}^N \alpha_i \xi_i - \sum_{i=1}^N \mu_i \xi_i \
&= -\frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) + \sum_{i=1}^N \alpha_i + C \sum_{i=1}^N \xi_i^2 - \sum_{i=1}^N \alpha_i \xi_i - \sum_{i=1}^N \mu_i \xi_i \
&= -\frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) + \sum_{i=1}^N \alpha_i + C \sum_{i=1}^N \xi_i^2 - \sum_{i=1}^N (\alpha_i + \mu_i) \xi_i \
&= -\frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) + \sum_{i=1}^N \alpha_i + C \sum_{i=1}^N \xi_i^2 - \sum_{i=1}^N \left( 2C \xi_i \right) \xi_i \
&= -\frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) + \sum_{i=1}^N \alpha_i + C \sum_{i=1}^N \xi_i^2 - 2C \sum_{i=1}^N \xi_i^2 \
&= -\frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) + \sum_{i=1}^N \alpha_i - C \sum_{i=1}^N \xi_i^2 \
&= -\frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) + \sum_{i=1}^N \alpha_i - C \sum_{i=1}^N \left(\frac{1}{4 C^2}(\alpha_i + \mu_i)^2 \right) \
&= -\frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) + \sum_{i=1}^N \alpha_i - \frac{1}{4 C}\sum_{i=1}^N (\alpha_i + \mu_i)^2
\end{aligned}

\begin{array}{cl}
\displaystyle \max \limits_{\alpha} & \displaystyle -\frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) + \sum_{i=1}^N \alpha_i - \frac{1}{4 C}\sum_{i=1}^N (\alpha_i + \mu_i)^2 \
\text{s.t.} & \displaystyle \sum_{i=1}^N \alpha_i y_i = 0 \
& \displaystyle 2C \xi_i - \alpha_i - \mu_i = 0 \
& \alpha_i \geqslant 0 ,\mu_i \geqslant 0, \xi_i \geqslant 0, \quad i=1,2,\cdots, N
\end{array}

\begin{array}{cl}
\displaystyle \min \limits_{\alpha} & \displaystyle \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) - \sum_{i=1}^N \alpha_i + \frac{1}{4 C}\sum_{i=1}^N (\alpha_i + \mu_i)^2 \
\text{s.t.} & \displaystyle \sum_{i=1}^N \alpha_i y_i = 0 \
& \displaystyle 2C \xi_i - \alpha_i - \mu_i = 0 \
& \alpha_i \geqslant 0 ,\mu_i \geqslant 0, \xi_i \geqslant 0, \quad i=1,2,\cdots, N
\end{array}

K = [K(x_i, x_j)]_{m \times m}

\begin{aligned}
\sum_{i,j=1}^n c_i c_j K(x_i,x_j)
&= \sum_{i,j=1}^n c_i c_j (x_i \bullet x_j) \
&= \left(\sum_{i=1}^m c_i x_i \right) \bullet \left(\sum_{j=1}^m c_j x_j \right) \
&= \Bigg|\left( \sum_{i=1}^m c_i x_i \right)\Bigg|^2 \geqslant 0
\end{aligned}

\phi(x):\mathcal{X} \rightarrow \mathcal{H}

K(x,z) = \phi(x) \bullet \phi(z)

\phi(x):R^n \rightarrow \mathcal{H}

K(x,z) = \phi(x) \bullet \phi(z)

\begin{aligned}
K(x,z)
&= (x \bullet z)^{k+1} \
&= (x \bullet z)^k (x \bullet z) \
&= (\phi(x) \bullet \phi(z))(x \bullet z) \
&= (f_1(x)f_1(z) + f_2(x)f_2(z) + \cdots + f_m(x)f_m(z))(x^{(1)}z^{(1)} + x^{(2)}z^{(2)} + \cdots + x^{(n)}z^{(n)}) \
&= f_1(x)f_1(z)(x^{(1)}z^{(1)} + x^{(2)}z^{(2)} + \cdots + x^{(n)}z^{(n)}) \
& \quad + f_2(x)f_2(z)(x^{(1)}z^{(1)} + x^{(2)}z^{(2)} + \cdots + x^{(n)}z^{(n)}) + \cdots \
& \quad + f_m(x)f_m(z)(x^{(1)}z^{(1)} + x^{(2)}z^{(2)} + \cdots + x^{(n)}z^{(n)}) \
&= (f_1(x)x^{(1)})(f_1(z)z^{(1)}) + (f_1(x)x^{(2)})(f_1(z)z^{(2)}) + \cdots \
& \quad + (f_1(x)x^{(n)})(f_1(z)z^{(n)}) \
& \quad + (f_2(x)x^{(1)})(f_2(z)z^{(1)}) + (f_2(x)x^{(2)})(f_2(z)z^{(2)}) + \cdots \
& \quad + (f_2(x)x^{(n)})(f_2(z)z^{(n)}) + \cdots \
& \quad + (f_m(x)x^{(1)})(f_m(z)z^{(1)}) + (f_m(x)x^{(2)})(f_m(z)z^{(2)}) + \cdots \
& \quad + (f_m(x)x^{(n)})(f_m(z)z^{(n)})
\end{aligned}

\begin{aligned}
\phi'(x) &= (f_1(x)x^{(1)}, f_1(x)x^{(2)}, \cdots, f_1(x)x^{(n)}, \
& \quad f_2(x)x^{(1)}, f_2(x)x^{(2)}, \cdots, f_2(x)x^{(n)}, \
& \quad f_m(x)x^{(1)}, \cdots, f_m(x)x^{(n)})^T
\end{aligned}

K(x,z) = (x \bullet z)^{k+1} = \phi'(x) \bullet \phi'(z)