IML Lab2 report
作者: Ruixuan Huang 学号: PB20111686
目标
- 使用两种方法构建解决 SVM 问题的算法类
- 测试构建好的算法类的泛化性能
- 比较两种方法
方法
方法1：SMO 算法
SMO 算法处理的是原优化问题的对偶问题，根据教材，对偶问题为 $$ \underset{\boldsymbol\alpha}{\arg \max } \sum_{i=1}^m \alpha_i-\frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m \alpha_i \alpha_j y_i y_j \boldsymbol{x}i^T \boldsymbol{x}_j $$ 约束条件为 KKT 条件： $$ \sum{i=1}^m\alpha_iy_i=0\quad\textbf{and}\quad0\le\alpha_i\le C\quad (1\le i\le m) $$ SMO 算法每次更新一对变量。在给定 \boldsymbol\alpha 的初值后，每次选择第一个不满足 KKT 约束的变量，也就是满足下面条件的变量 \alpha_t： $$ \left(\alpha_i<C \text { and } y_i E_i<-\varepsilon\right) \text { or }\left(\alpha_i>0 \text { and } y_i E_i>\varepsilon\right) $$ 记误差 $$ \newcommand{\w}{\boldsymbol w} \newcommand{\t}{\top} \newcommand{\x}{\boldsymbol x} E_t=\w^\t \x_i+b-y_i $$ 在剩余的变量列表中，选择 \alpha_l，其中 l 满足 $$ l=\underset i{\arg\max}|E_t-E_i| $$
上面选择的两个变量外，其余的都看成常量，则有 $$ \left{\begin{array}{l} \alpha_l y_l+\alpha_t y_t=k \ \alpha_{l, u} y_l+\alpha_{t, u} y_t=k \ \sum_{i \neq l, t}^m \alpha_i y_i=-k \end{array}\right. $$ 其中 \left(\alpha_l, \alpha_t\right) 是上一轮迭代的参数值，是常量； \left(\alpha_{l, u}, \alpha_{t, u}\right) 是本轮优化变量，其不一定满足 KKT 条件，需要根据可行域进一步修剪为符合约束的 \left(\alpha_{l, *}, \alpha_{t, *}\right)。
记优化目标函数为 \Gamma(·)，记 v_l=\boldsymbol{x}_l^\t \sum_{i \neq l, t}^m \alpha_i y_i \boldsymbol{x}_i, v_t=\boldsymbol{x}_t^\t \sum_{i \neq l, t}^m \alpha_i y_i \boldsymbol{x}_i，则 $$ \begin{aligned} &\Gamma\left(\alpha_{l, u}, \alpha_{t, u}\right)=\sum_{i=1}^m \alpha_i-\frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m \alpha_i \alpha_j y_i y_j \boldsymbol{x}i^\t\boldsymbol{x}_j\newline &\Rightarrow \begin{aligned} \Gamma\left(\alpha{t, u}\right) =&\left(k-\alpha_{t, u} y_t\right) y_l+\alpha_{t, u}-\frac{1}{2}\left(k-\alpha_{t, u} y_t\right)^2 \boldsymbol{x}l^\t \boldsymbol{x}_l-\frac{1}{2} \alpha{t, u}^2 \boldsymbol{x}t^\t \boldsymbol{x}_t \ &-\left(k-\alpha{t, u} y_t\right) \alpha_{t, u} y_t \boldsymbol{x}l^\t \boldsymbol{x}_t-\left(k-\alpha{t, u} y_t\right) v_l-\alpha_{t, u} y_t v_t \end{aligned} \end{aligned} $$ 这是单变量二次规划问题，直接求导即可获得极值点： $$ \frac{\partial \Gamma\left(\alpha_{t, u}\right)}{\partial \alpha_{t, u}}=-y_t y_l+1+y_t\left(k-\alpha_{t, u} y_t\right) \boldsymbol{x}l^\t \boldsymbol{x}_l-\alpha{t, u} \boldsymbol{x}t^\t \boldsymbol{x}_t-k y_t \boldsymbol{x}_l^\t \boldsymbol{x}_t+2 \alpha{t, u} \boldsymbol{x}_l^\t \boldsymbol{x}_t+y_t v_l-y_t v_t=0 $$
随后，需要根据可行域修剪参数： $$ \alpha_{t, *}=\left{\begin{array}{l} H, \alpha_{t, u}>H \ \alpha_{t, u}, L \leqslant \alpha_{t, u} \leqslant H \ L, \alpha_{t, u}<L \end{array}\right. $$
\w 的更新： $$ \boldsymbol{w}=\sum_{i=1}^m \alpha_i y_i \boldsymbol{x}_i^\t $$ 因为 \w 的计算不涉及 b，所以每次迭代不更新 b，最后用梯度下降法确定 b。
方法2：GD 算法
原问题为（使用 Hinge loss）
$$
\min_{\w,b}\frac12||\w||^2+\frac Cm\sum_{i=1}^m\max(0,1-y_i(\w^\t\x_i+b)):=\min_{\w,b}J(\w,b)
$$
约束条件为
$$
y_i(\w^\t\x_i+b)\ge1\quad(1\le i\le m)
$$
当分类正确时，\w,b 不改变；当分类不正确也就是 y_i(\w^\t\x+b)<1 时，梯度
$$
\nabla J(\w)=\w-\frac Cm\sum_{i\in {i|y_i(·)<1}}y_i\x_i\quad \nabla J(b)=-\frac Cm\sum_{i\in {i|y_i(·)<1}}y_i
$$
参数更新公式为
$$
\begin{aligned}
&\w\leftarrow \w+lr\nabla J(\w)\newline
&b\leftarrow b+lr\nabla J(b)\newline
\end{aligned}
$$
直到两次更新参数后 J(\w,b) 之差小于 self.tol，退出，宣告训练完毕。
结果
SMO 算法
使用随机生成数据，维度为 20，长度为 10000。使用留出法进行训练和测试，训练集占数据集的 70%，测试集占余下的 30%。系数 C=0.5，选择 \varepsilon=10^{-5}，\eta_b=1。\boldsymbol\alpha 的初值设为 np.ones(self.m)/20 （即全部为 0.05）。
多次重复测试（不同随机数据）表明，测试集上的精度 \left(\text{accuracy}=\frac{TP+FN}{TP+TN+FP+FN}\right) 为 95% 左右，训练所需时间为 70 秒左右。
GD 算法
使用随机生成数据，维度为 20，长度为 10000。使用留出法进行训练和测试，训练集占数据集的 70%，测试集占余下的 30%。系数 C=0.01，选择 lr=0.1,tol=10^{-3}。
多次重复测试（不同随机数据）表明，测试集上的精度 \left(\text{accuracy}=\frac{TP+FN}{TP+TN+FP+FN}\right) 为 95% 左右，训练所需时间为 120 秒左右。
比较
可以看出，方法 1（SMO）的训练时间比方法 2（GD）要好，但是二者的泛化能力在本数据上相差并不大。
本文阅读量