统计学习方法笔记09

李航. 统计学习方法[M]. 清华大学出版社, 2012.

7.3 非线性支持向量机与核函数

7.3.1 核技巧

用线性分类方法求解非线性分类问题分为两步：①使用一个变换将原空间的数据映射到新空间；②在新空间里用线性分类学习方法从训练数据中学习分类模型。核技巧就属于这样的方法。

核技巧应用到支持向量机，其基本思想就是通过一个非线性变换将输入空间（欧式空间或离散空间）对应于一个特征空间，使得在输入空间中的超曲面模型对应于特征空间中的超平面模型（支持向量机）。

核函数

设 $\mathcal{X}$ 是输入空间，又设 $\mathcal{H}$ 为特征空间，如果存在一个从 $\mathcal{X}$ 到

的映射 $\phi(x):\mathcal{X} \rightarrow \mathcal{H}$ 使得对所有 $x,y\in\mathcal{X}$ ，函数 $K(x,z)$ 满足条件 $K(x,z)=\phi(x)\cdot\phi(z)$ ，则称 $K(x,z)$ 为核函数， $\phi(x)$ 为映射函数，式中 $\phi(x)\cdot\phi(z)$ 为内积。

核技巧的想法是，在学习与预测过程中只定义核函数 $K(x,z)$ ，而不显式地定义映射函数 $\phi$ 。对于给定的核 $K(x,z)$ ，特征空间 $\mathcal{H}$ 和映射函数 $\phi$ 的取法并不唯一。

在对偶问题的目标函数中的内积可以用核函数来代替，于是对偶问题的目标函数成为

$W(\alpha) = \dfrac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j K(x_i,x_j) - \sum_{i=1}^N \alpha_i$

同样，分类决策函数中的内积也可以用核函数代替，分类决策函数式成为

$f(x) = sign\left( \sum_{i=1}^{N_s} \alpha_i^* y_i K(x_i,x) + b^* \right)$

7.3.2 正定核

正定核的充要条件

设 $K:\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}$ 是对称函数，则 $K(x,z)$ 为正定核函数的充要条件是对任意的 $x_i\in\mathcal{X}, i=1,2,\dots,m$ ， $K(x,z)$ 对应的Gram矩阵 $K=[K(x_i,x_j)]_{m\times m}$ 是半正定矩阵。

正定核的等价定义

设 $\mathcal{X}\subset\mathbb{R}^n$ ， $K(x,z)$ 是定义在 $\mathcal{X}\times\mathcal{X}$ 上的对称函数，如果对任意的 $x_i\in\mathcal{X}$ ， $i=1,2,\dots,m$ ， $K(x,z)$ 对应的Gram矩阵 $K=[K(x_i,x_j)]_{m\times m}$ 是半正定矩阵，则称 $K(x,z)$ 是正定核(positive definite kernel function)。

7.3.3 常用核函数

多项式核函数(polynomial kernel function)

$K(x,z)=(x\cdot z+1)^p$

高斯核函数(Gaussian kernel function)

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

字符串核函数(string kernel function)

$[\phi_n(s)]_u = \sum_{i:s(i)=u} \lambda^{l(i)}$

$\begin{aligned}k_n(s,t) &= \sum_{u\in \Sigma^n} [\phi_n(s)]_u [\phi_n(t)]_u \\&= \sum_{u\in \Sigma^n} \sum_{(i,j):s(i)=t(j)=u} \lambda^{l(i)} \lambda^{l(j)}\end{aligned}$

7.3.4 非线性支持向量分类机

非线性支持向量机

从非线性分类训练集，通过核函数与软间隔最大化，或下面算法中的凸二次规划，学习到的分类决策函数

$f(x) = sign\left( \sum_{i=1}^N \alpha_i^* y_i K(x,x_i) + b^* \right)$

称为非线性支持向量机， $K(x,z)$ 是正定核函数。

非线性支持向量机学习算法

输入：训练数据集 $T=\{(x_i,y_i)\}$ ，其中 $x_i\in\mathcal{X}=\mathbb{R}^n$ ， $y_i\in\{-1,+1\}$ ， $i=1,\dots,N$

输出：分类决策函数

(1) 选取适当的核函数 $K(x,z)$ 和适当的参数 $C$ ，构造并求解最优化问题

$\begin{equation}\begin{aligned}\min_{\alpha} \quad & \dfrac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j K(x_i,x_j) - \sum_{i=1}^N \alpha_i \\\text{s.t.} \quad & \sum_{i=1}^N \alpha_i y_i = 0 \\& 0 \leq \alpha_i \leq C, i=1,2,\dots,N\end{aligned}\end{equation}$

(2) 选择 $\alpha^*$ 的一个正分量 $0<\alpha_j^*<C$ ，计算

$b^* = y_j - \sum_{i=1}^N \alpha_i^* y_i K(x_i,x_j)$

(3) 构造决策函数 $f(x) = sign\left( \sum_{i=1}^N \alpha_i^* y_i K(x,x_i) + b^* \right)$

7.4 序列最小最优化算法

序列最小最优化算法(sequential minimal optimization, SMO)算法旨在高效实现支持向量机学习，是一种启发式算法，其基本思路是：如果所有变量的解都满足此最优化问题的KKT条件(Karush-Kuhn-Tucker conditions)，那么这个最优化问题的解就得到了。因为KKT条件是该最优化问题的充分必要条件。

SMO算法

输入：训练数据集 $T=\{(x_i,y_i)\}$ ，其中 $x_i\in\mathcal{X}=\mathbb{R}^n$ ， $y_i\in\{-1,+1\}$ ，精度 $\varepsilon$

输出：近似解 $\hat{\alpha}$

(1) 取初值 $\alpha^{(0)}=0$ ，令 $k=0$ ；

(2) 选取优化变量 $\alpha_1^{(k)},\alpha_2^{(k)}$ ，解析求解两个变量的最优化问题

$\begin{aligned}\min_{\alpha_1,\alpha_2} \quad & W(\alpha_1,\alpha_2) = \dfrac{1}{2} K_{11}\alpha_1^2 + \dfrac{1}{2} K_{22}\alpha_2^2 + y_1 y_2 K_{12} \alpha_1 \alpha_2 - (\alpha_1+\alpha_2) + \\& \qquad\qquad\qquad y_1 \alpha_1 \sum_{i=3}^N y_i\alpha_i K_{i1} + y_2 \alpha_2 \sum_{i=3}^N y_i \alpha_i K_{i2}\\\text{s.t.} \quad & \alpha_1 y_1 + \alpha_2 y_2 = -\sum_{i=3}^N y_i \alpha_i = \varsigma \\& 0 \leq \alpha_i \leq C, i=1,2\end{aligned}$

求得最优解 $\alpha_1^{(k+1)},\alpha_2^{(k+1)}$ ，更新 $\alpha$ 为 $\alpha^{(k+1)}$ ；

(3) 若在精度 $\varepsilon$ 范围内满足停机条件

$\sum_{i=1}^N \alpha_i y_i = 0,\quad 0\leq\alpha_i\leq C, \quad i=1,2,\dots,N$

$y_i \cdot g(x_i) \begin{cases}\geq 1, \quad \{x_i|\alpha_i=0\} \\=1, \quad \{x_i|0<\alpha_i<C\} \\\leq 1, \quad \{x_i|\alpha_i=C\}\end{cases}$

其中 $g(x_i)=\sum_{j=1}^N \alpha_j y_j K(x_j,x_i)+b$ ，则转(4)；否则令 $k=k+1$ ，转(2)；

(4) 取 $\hat{\alpha}=\alpha^{(k+1)}$ 。

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 216,470评论 6赞 501
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 92,393评论 3赞 392
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 162,577评论 0赞 353
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,176评论 1赞 292
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,189评论 6赞 388
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,155评论 1赞 299
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,041评论 3赞 418
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,903评论 0赞 274
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,319评论 1赞 310
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,539评论 2赞 332
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,703评论 1赞 348
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,417评论 5赞 343
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,013评论 3赞 325
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,664评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,818评论 1赞 269
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,711评论 2赞 368
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,601评论 2赞 353