<commit_before>---
layout: post
title: 支持向量机SMO序列最小最优化算法实现
category: blog
description: 《统计学习方法》书中SMO算法的实现
---

最近在看李航教授的《统计学习方法》的过程中，发现支持向量机部分的SMO算法的数理部分第一次看的时候有点吃力，反复看了两三遍才算勉强弄明白了证明和推导过程。作为一个所谓的工程师，遇到比较晦涩的理论脑袋里面浮现的第一个念头当然就是去实践它。上网查了一下，果然有[JustForCS](http://www.cnblogs.com/JustForCS/p/5283489.html)和[刘洪江](http://liuhongjiang.github.io/tech/blog/2012/12/28/svm-smo/)两位同道已经完成了SMO算法实现的代码。

但是仔细研究了一下代码，发现他们的代码中都对违反KKT原则条件做了更近一步的推导和对SMO选择变量部分做了一些简化。原书中对于选择变量的算法是以最违反KKT原则的alpha_i作为锚定的第一变量，下降最大的alpha_j作为选定的第二变量继而更新alpha值。而在这两位的代码中，他们都选择了随机选择变量然后计算优化步长来决定是否使用变量。

所以在这里也打算以《统计学习方法》一书中的算法作为标准，手动实现SMO算法。当然这样并不意味着就一定比上面两位的实现方式要好，只不过是更贴近书中算法的说明从而更容易理解。

对于支持向量机比较全面的描述可以参考[文章](http://blog.csdn.net/crazy_programmer_p/article/details/38512945)。

这里直接给出《统计学习方法》一书中关于SMO的算法说明。

## SMO算法

<p style="text-indent:0"><em style="color:blue"> 输入：</em>训练数据集 $ T={ \\({x\_1},{y\_1}),({x\_2},{y\_2}), \cdot \cdot \cdot ,({x\_N},{y\_N})\\ }$ </p> 

其中$ {x\_i} \in \chi  \in {\mathbb{R}^n}$，${y\_i} \in \\{-1,+1\\}$，$i=1,2,\cdot\cdot\cdot,N$，精度$\varepsilon$。

<p style="text-indent:0"><em style="color:blue">输出：</em>近似解$\hat a$</p>

<p style="text-indent:0"><em style="color:blue">算法描述：</em></p>

(1) 取初始值${a^{(0)}}=0$，令$K=0$

(2) 选取优化变量 ${a\_1^{(k)}}$ , ${a\_2^{(k)}}$ , 针对优化问题，求得最优解 ${a\_1^{(k+1)}}$ , ${a\_2^{(k+1)}}$ 并且更新 ${a^{(k)}}$ 为 ${a^{(k+1)}}$ 。

(3) 在精度条件范围内是否满足停机条件，即**是否有变量违反KKT条件**，如果违反了，则令$k=k+1$，跳转(2)，否则(4)。

(4) 求得近似解$\hat a = a^{(k+1)}$

下面就对(2)，(3)步分别解释。<commit_msg>Test for MathFormula in blog<commit_after>---
layout: post
title: 支持向量机SMO序列最小最优化算法实现
category: blog
description: 《统计学习方法》书中SMO算法的实现
---

最近在看李航教授的《统计学习方法》的过程中，发现支持向量机部分的SMO算法的数理部分第一次看的时候有点吃力，反复看了两三遍才算勉强弄明白了证明和推导过程。作为一个所谓的工程师，遇到比较晦涩的理论脑袋里面浮现的第一个念头当然就是去实践它。上网查了一下，果然有[JustForCS](http://www.cnblogs.com/JustForCS/p/5283489.html)和[刘洪江](http://liuhongjiang.github.io/tech/blog/2012/12/28/svm-smo/)两位同道已经完成了SMO算法实现的代码。

但是仔细研究了一下代码，发现他们的代码中都对违反KKT原则条件做了更近一步的推导和对SMO选择变量部分做了一些简化。原书中对于选择变量的算法是以最违反KKT原则的alpha_i作为锚定的第一变量，下降最大的alpha_j作为选定的第二变量继而更新alpha值。而在这两位的代码中，他们都选择了随机选择变量然后计算优化步长来决定是否使用变量。

所以在这里也打算以《统计学习方法》一书中的算法作为标准，手动实现SMO算法。当然这样并不意味着就一定比上面两位的实现方式要好，只不过是更贴近书中算法的说明从而更容易理解。

对于支持向量机比较全面的描述可以参考[文章](http://blog.csdn.net/crazy_programmer_p/article/details/38512945)。

这里直接给出《统计学习方法》一书中关于SMO的算法说明。

## SMO算法

<p style="text-indent:0"><em style="color:blue"> 输入：</em>训练数据集 $ T=\{ \\({x\_1},{y\_1}),({x\_2},{y\_2}), \cdot \cdot \cdot ,({x\_N},{y\_N})\\ \}$ </p> 

其中$ {x\_i} \in \chi  \in {\mathbb{R}^n}$，${y\_i} \in \\{-1,+1\\}$，$i=1,2,\cdot\cdot\cdot,N$，精度$\varepsilon$。

<p style="text-indent:0"><em style="color:blue">输出：</em>近似解$\hat a$</p>

<p style="text-indent:0"><em style="color:blue">算法描述：</em></p>

(1) 取初始值${a^{(0)}}=0$，令$K=0$

(2) 选取优化变量 ${a\_1^{(k)}}$ , ${a\_2^{(k)}}$ , 针对优化问题，求得最优解 ${a\_1^{(k+1)}}$ , ${a\_2^{(k+1)}}$ 并且更新 ${a^{(k)}}$ 为 ${a^{(k+1)}}$ 。

(3) 在精度条件范围内是否满足停机条件，即**是否有变量违反KKT条件**，如果违反了，则令$k=k+1$，跳转(2)，否则(4)。

(4) 求得近似解$\hat a = a^{(k+1)}$

下面就对(2)，(3)步分别解释。
{'fraction_non_alphanumeric': 0.24295894129623347, 'fraction_numerical': 0.03664743807261622, 'mean_word_length': 7.8, 'pattern_counts': {'":': 0, '<': 27, '<?xml version=': 0, '>': 27, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3724782', 'n_tokens_mistral': 2128, 'n_tokens_neox': 2328, 'n_words': 127}