# 附 第七章作业

## 作业1

### 题目

给定如下训练数据集

$$
x\_1 = \[3\ 3]\ y^1 = 1\ x\_2 = \[4\ 3]\ y^2 = 1\ x\_3 = \[1\ 1]\ y^3 = -1
$$

通过求解SVM的对偶问题来求解最大间隔的分类超平面

### 解

首先，对偶问题为：

$$
\begin{align} \max\limits\_{\alpha} &\sum\_{i=1}^N \alpha\_i - \frac{1}{2}\sum\_{i,j=1}^N y^i y^j\alpha\_i\alpha\_j (\mathbf{x}^i)^T\mathbf{x}^j\nonumber \ \operatorname{s.t.}&\ \alpha\_i\geq0,i=1,\dots,N \ &\sum\_{i=1}^N \alpha\_i y^i = 0 \end{align}
$$

并求的其最优解$$\boldsymbol{\alpha}^*=(\alpha\_1^*,\dots,\alpha\_l^\*)$$

则得到原问题的最优解：

$$
\begin{align} &\mathbf{w}^\*=\sum\_{i=1}^N\alpha\_i^*y^i\mathbf{x}^i \nonumber \ \&b^* = y^j-\sum\_{i=1}^N\alpha\_i^*y^i(\mathbf{x}^i)^T\mathbf{x}^j \ & \alpha\_j^* > 0 \end{align}
$$

进而可以得到分离超平面：

$$
(\mathbf{w}^*)^T\mathbf{x} + b^* = 0
$$

对于给定的训练数据集，有：

$$
\begin{align} \mathbf{x}^1 &= \[3\ 3] \ \nonumber \mathbf{x}^2 &= \[4\ 3] \ \mathbf{x}^3 &= \[1\ 1] \ y^1 &= 1 \ y^2 &= 1 \ y^3 &= -1 \end{align}
$$

则有：

$$
k = \mathbf x^T \cdot \mathbf x = \begin{pmatrix} 18&21&6\ 21&25&7\ 6&7&2 \end{pmatrix}
$$

目标函数为：

$$
\max\limits\_{\alpha} \quad\sum\_{i=1}^N \alpha\_i - \frac{1}{2}\sum\_{i,j=1}^N y^i y^j\alpha\_i\alpha\_j k\_{ij}
$$

约束条件为：

$$
\begin{align} &\alpha\_i \geq 0, i=1,\dots,N \ \nonumber &\sum\_{i=1}^N \alpha\_i y^i = 0 \end{align}
$$

### 代码实现

#### 使用scipy求解最优化

```python
import numpy as np
from scipy.optimize import minimize

X = np.array([[3, 3], [4, 3], [1, 1]])
y = np.array([1, 1, -1])
k = np.dot(X, X.T)


def objective(alpha):
    return -np.sum(alpha) + 0.5 * np.sum(np.outer(y, y) * np.outer(alpha, alpha) * k)


def constraint1(alpha):
    return alpha


def constraint2(alpha):
    return np.dot(alpha, y)


N = X.shape[0]
bounds = [(0, None)] * N
constraints = [{'type': 'ineq', 'fun': constraint1}, {'type': 'eq', 'fun': constraint2}]

alpha_initial = np.zeros(N)
result = minimize(objective, alpha_initial, bounds=bounds, constraints=constraints)

alphas = result.x
print(f'Optimal alphas:[{alphas[0]},{alphas[1]},{alphas[2]}]')

w = np.dot(alphas * y, X)
print(w)

b_index = np.argmax(alphas)
b = y[b_index] - np.sum(alphas * y * np.dot(X, X[b_index]))
print(b)
```

输出结果为：

w=\[0.49999996 0.49999996] b=-1.999999927629584

#### 使用sklearn中的SVM模块求解

```python
import numpy as np
from sklearn.svm import SVC

X = np.array([[3, 3], [4, 3], [1, 1]])
y = np.array([1, 1, -1])

svm = SVC(kernel='linear')
svm.fit(X, y)

w = svm.coef_[0]
b = svm.intercept_[0]

print(w)
print(b)
```

输出结果为：

w = \[0.5 0.5] b = -2.0

## 作业2

### 题目

高斯核有以下形式：

$$
K(x,z) = \exp \left(-\frac{\Vert x-z \Vert^2}{2\sigma^2}\right)
$$

请证明高斯核函数可以表示为一个无穷维特征向量的内积

**提示**：利用以下展开式，将中间的因子展开为幂级数

$$
K(x,z) = \exp \left(-\frac{x^Tx}{2\sigma^2}\right) \exp \left(\frac{x^Tz}{2\sigma^2}\right) \exp \left(-\frac{z^Tz}{2\sigma^2}\right)
$$

### 证明

首先，有：

$$
\begin{align} K(x,z) &= \exp \left(-\frac{\Vert x-z \Vert^2}{2\sigma^2}\right) \nonumber \ &= \exp \left(-\frac{x^2+z^2-2xz}{2\sigma^2}\right) \ &= \exp \left(-\frac{x^2+z^2}{2\sigma^2}\right) \exp \left(\frac{xz}{\sigma^2}\right) \end{align}
$$

记为式（1）

由于函数$$e^x$$的幂级数展开式为：

$$
\begin{align} e^x &= \sum\_{i=0}^\infin\frac{x^n}{n!}\ \nonumber &= 1 + x + \frac{x^2}{2!} + \dots + \frac{x^n}{n!} + R\_n \end{align}
$$

因此，可以有：

$$
\begin{align} \exp \left(\frac{xz}{\sigma^2}\right) &= 1 + \left(\frac{xz}{\sigma^2}\right) + \frac{\left(\frac{xz}{\sigma^2}\right)^2}{2!} + \dots + \frac{(\frac{xz}{\sigma^2})^n}{n!} + \dots \nonumber \ &=1 + \frac1{\sigma^2}\cdot\frac{xz}{1!} + \left(\frac1{\sigma^2}\right)^2\cdot\frac{(xz)^2}{2!} + \dots + \left(\frac1{\sigma^2}\right)^n\cdot\frac{(xz)^n}{n!} + \dots \ &= 1\cdot1 + \frac1{1!}\frac x\sigma\cdot\frac z\sigma + \frac1{2!}\frac{x^2}{\sigma^2}\cdot\frac{z^2}{\sigma^2} +\dots+\frac1{n!}\frac{x^n}{\sigma^n}\cdot\frac{z^n}{\sigma^n} + \dots \end{align}
$$

将其带回（1）式，有：

$$
\begin{align} K(x,z) &= \exp \left(-\frac{x^2+z^2}{2\sigma^2}\right)\cdot\left(1\cdot1 + \frac1{1!}\frac x\sigma\cdot\frac z\sigma + \frac1{2!}\frac{x^2}{\sigma^2}\cdot\frac{z^2}{\sigma^2} +\dots+\frac1{n!}\frac{x^n}{\sigma^n}\cdot\frac{z^n}{\sigma^n} + \dots\right) \nonumber \ &= \exp \left(-\frac{x^2}{2\sigma^2}\right)\cdot\exp \left(-\frac{z^2}{2\sigma^2}\right)\cdot\left(1\cdot1 + \frac1{1!}\frac x\sigma\cdot\frac z\sigma + \frac1{2!}\frac{x^2}{\sigma^2}\cdot\frac{z^2}{\sigma^2} +\dots+\frac1{n!}\frac{x^n}{\sigma^n}\cdot\frac{z^n}{\sigma^n} + \dots\right) \ &= \Phi(x)^T\cdot\Phi(z) \end{align}
$$

其中，

$$
\Phi(x) = \exp \left(-\frac{x^2}{2\sigma^2}\right)\cdot\left(1 , \sqrt\frac1{1!}\frac x\sigma , \sqrt\frac1{2!}\frac{x^2}{\sigma^2} , \dots , \sqrt\frac1{n!}\frac{x^n}{\sigma^n} , \dots\right)
$$

因此，高斯核函数可以表示为一个无穷维特征向量的内积


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aye10032.gitbook.io/prml-note/di-qi-zhang-zhi-chi-xiang-liang-ji/fu-di-qi-zhang-zuo-ye.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.