计算题: a)已知一个如下图所示的训练数据集，其正类样本为x1= (3,3)T,x2=(4,3)T，负类样本是x3=(1,1)”。 训练样本分布 6 3 2 1 2 3 4 5 6 试写出上述问题的线性 SVM 原始优化问题的数学形式， ii. 包含目标函数与约束条件; 试写出经过拉格朗日对偶处理后的优化问题的数学形式， ii. 包含目标函数与约束条件; iv. 试写出SVM对应的 KKT条件。 对照图中的决策面和间隔区域，试推算样本xi,i=1,2,3对 应的系数αi,i = 1,2,3. b)对于 1 个标准的 XOR 问题，x1 =[1,0], x2 = [0,1],x3 = [0,0],x4 = [1,1]。其中x1,x^2 EW1类，x3,x4 EW2类。请设计一 个非线性矢量映射函数Φ:R2→R3，将样本从2维空间映射到 3 位空间，使得数据在 3 维空间中可分，并给出对应的核函数 K。

a) 线性 SVM 原始优化问题的数学形式为

$$
\begin{aligned}
\min_{w,b}\frac{1}{2}\|w\|^2 \\
s.t. \quad y_i(w^Tx_i+b) \geq 1, \quad &\forall i=1,\dots,m
\end{aligned}
$$

其中，$w$ 和 $b$ 是线性 SVM 的参数，$m$ 是样本数量，$x_i$ 和 $y_i$ 分别是第 $i$ 个样本的特征向量和标签。对于本问题，$m=3$，$x_1$ 和 $x_2$ 是正类样本，标签 $y_i=1$，$x_3$ 是负类样本，标签 $y_3=-1$。因此，上述优化问题的具体形式为：

$$
\begin{aligned}
\min_{w,b}\frac{1}{2}\|w\|^2 \\
s.t. \quad w^Tx_1+b \geq 1, \\
w^Tx_2+b \geq 1, \\
w^Tx_3+b \leq -1
\end{aligned}
$$

经过拉格朗日对偶处理后的优化问题的数学形式为

$$
\begin{aligned}
\max_{\alpha}\sum_{i=1}^{m}\alpha_i-\frac{1}{2}\sum_{i,j=1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_j \\
s.t. \quad \sum_{i=1}^{m}\alpha_iy_i=0, \\
0 \leq \alpha_i \leq C, \quad &\forall i=1,\dots,m
\end{aligned}
$$

其中，$\alpha$ 是拉格朗日乘子，$C$ 是正则化参数。对于本问题，$m=3$，$x_1$ 和 $x_2$ 是正类样本，标签 $y_i=1$，$x_3$ 是负类样本，标签 $y_3=-1$。因此，上述优化问题的具体形式为：

$$
\begin{aligned}
\max_{\alpha}\alpha_1+\alpha_2-\frac{1}{2}(\alpha_1^2+\alpha_2^2+\alpha_3^2-4\alpha_1\alpha_2-6\alpha_3) \\
s.t. \quad \alpha_1+\alpha_2-\alpha_3=0, \\
0 \leq \alpha_i \leq C, \quad &\forall i=1,2,3
\end{aligned}
$$

SVM 对应的 KKT 条件为：

$$
\begin{aligned}
\alpha_i \geq 0, \quad &\forall i=1,\dots,m \\
y_i(w^Tx_i+b)-1+\xi_i \geq 0, \quad &\forall i=1,\dots,m \\
\alpha_i(y_i(w^Tx_i+b)-1+\xi_i) = 0, \quad &\forall i=1,\dots,m \\
\xi_i \geq 0, \quad &\forall i=1,\dots,m \\
\sum_{i=1}^{m}\alpha_iy_i = 0 \\
w = \sum_{i=1}^{m}\alpha_iy_ix_i
\end{aligned}
$$

对于本问题，由于决策面 $w^Tx+b=0$ 经过点 $(3,3)$ 和 $(4,3)$，因此有

$$
\begin{aligned}
w_1\times 3 + w_2\times 3 + b &= 0 \\
w_1\times 4 + w_2\times 3 + b &= 0
\end{aligned}
$$

解以上方程组可得

$$
\begin{aligned}
w &= (-1, 2) \\
b &= -1
\end{aligned}
$$

由此可知，决策面的方程为 $-x_1 + 2x_2 - 1 = 0$，对应的间隔界为 $x_2 - x_1 - 1 = 0$。因此，在间隔界上的支持向量为 $(3,3)$ 和 $(4,3)$，对应的系数分别为 $\alpha_1 = \frac{1}{2}$ 和 $\alpha_2 = \frac{1}{2}$。在决策面上的支持向量为 $(1,1)$，对应的系数为 $\alpha_3 = \frac{1}{2C}$，由于该点的标签为 $-1$，因此 $\alpha_3$ 取正值。

b) 对于标准的 XOR 问题，数据点 $(1,0)$ 和 $(0,1)$ 属于第一类，标签为 $y_1=1$，数据点 $(0,0)$ 和 $(1,1)$ 属于第二类，标签为 $y_2=-1$。由于这是一个非线性可分问题，需要使用非线性 SVM。

一种解决方法是通过非线性映射将数据从 2 维空间映射到 3 维空间，使得数据在 3 维空间中可分。常用的非线性映射有多项式映射和径向基函数（Radial Basis Function, RBF）映射。对于本问题，一种可能的非线性映射是：

$$
\begin{aligned}
\Phi(x) &= (x_1^2, x_2^2, \sqrt{2}x_1x_2) \\
&= (1, 0, 0) + (0, 1, 0) + (0, 0, \sqrt{2})x_1x_2 + (1, -1, 0)x_1^2 + (1, 1, 0)x_2^2
\end{aligned}
$$

其中，$(x_1,x_2)$ 是原始数据点，$\Phi(x)$ 是映射后的数据点。可以发现，通过这种映射，原始数据点被映射到了 3 维空间，且在该空间中可以被一个平面完全分割。对应的核函数为：

$$
K(x,z) = \Phi(x)^T\Phi(z) = (1+x_1z_1+x_2z_2)^2
$$

其中，$x$ 和 $z$ 分别是两个原始数据点的特征向量。可以验证，该核函数是 Mercer 核函数，因此