支持向量机系列（一）——线性可分情形下的SVM

Linear Support Vector Machines in the Linearly Separable Case

Problem Description

Assume we have a learning set of data, $\mathscr{L}= \{(\mathbf{x}_i,y_i):i=1,2,\cdots,n\}$ where $\mathbf{x}_i\in \mathbb{R}^r$ and $y_i\in\{1,-1\}$ . The binary classification problem is to use $\mathscr{L}$ to construct a function $f: \mathbb{R}^r \rightarrow \mathbf{R}$ so that
$\begin{align*} C(\mathbf{x})&= sign(f(\mathbf{x}))\\ &=sign (\beta_0 + \mathbf{x}^{\top}{\boldsymbol\beta}) \end{align*}$ is a classifier.

If $\mathscr{L}$ is linearly separable, then the optimization problem is given by
$\begin{align*} \min\limits_{\beta_0,{\boldsymbol\beta}} \ &\dfrac{1}{2}\|{\boldsymbol\beta}\|^2\\ \qquad \qquad s.t. \quad& y_i (\beta_0 + \mathbf{x}_i^{\top} {\boldsymbol\beta})\geq 1 ,\qquad i=1,2,\cdots,n \end{align*}$

Primal Problem Given by Lagrangian Multipliers

By using Lagrangian multipliers, the primal function is given by
$\begin{align*} F_P(\beta_0,{\boldsymbol\beta},{\boldsymbol\alpha})&= \frac{1}{2}\|{\boldsymbol\beta}\|^2 + \sum_{i=1}^{n}\alpha_i [1-y_i(\beta_0 + \mathbf{x}_i^{\top} {\boldsymbol\beta})] \end{align*}$
where ${\boldsymbol\alpha}= \begin{pmatrix} \alpha_1&\cdots&\alpha_n \end{pmatrix}^{\top}\succeq \mathbf{0}$ is the Lagrangian coefficients. So the primal problem is equivalent to
$\begin{align*} \min\limits_{\beta_0,{\boldsymbol\beta}}\max\limits_{{\boldsymbol \alpha}}\ & F_P(\beta_0,{\boldsymbol\beta},{\boldsymbol\alpha}) \\ s.t. \quad& {\boldsymbol\alpha} \succeq \mathbf{0} \end{align*}$

The Karush–Kuhn–Tucker conditions give necessary and suﬃcient conditions for a solution to a constrained optimization problem:
$\begin{align*} \dfrac{\partial F_P(\beta_0, {\boldsymbol\beta},{\boldsymbol\alpha})}{\partial\beta_0} & =- \sum_{i=1}^{n}\alpha_i y_i=0\\ \dfrac{\partial F_P(\beta_0, {\boldsymbol\beta},{\boldsymbol\alpha})}{\partial{\boldsymbol\beta}} & ={\boldsymbol\beta}- \sum_{i=1}^{n}\alpha_i \mathbf{x}_i =0\\ 1-y_i(\beta_0 + \mathbf{x}_i^{\top} {\boldsymbol\beta})&\leq 0\\ \alpha_i&\geq 0\\ \alpha_i [1-y_i(\beta_0 + \mathbf{x}_i^{\top} {\boldsymbol\beta})]&=0 \end{align*}$
KKT conditions yields
$\begin{align*} \sum_{i=1}^{n}\alpha_iy_i&=0\\ {\boldsymbol\beta} &= \sum_{i=1}^{n}\alpha_iy_i \mathbf{x}_i \end{align*}$
and $\beta_0$ is implicitly determined by the KKT complementarity condition, by choosing any $i$ for which $\alpha_i \neq 0$ and computing $\beta_0$ (note that it is numerically safer to take the mean value of $\beta_0$ resulting from all such equations).

Applying KKT conditions to the primal function simplifies the dual function
$\begin{align*} F_D({\boldsymbol\alpha})&= \min\limits_{\beta_0,{\boldsymbol\beta}}F_P(\beta_0,{\boldsymbol\beta},{\boldsymbol\alpha}) \\ &= \frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}\alpha_i\alpha_jy_iy_j \mathbf{x}_i^{\top}\mathbf{x}_j - \sum_{i=1}^{n} \sum_{j=1}^{n}\alpha_i\alpha_jy_iy_j \mathbf{x}_i^{\top}\mathbf{x}_j+ \sum_{i=1}^{n}\alpha_i\\ &= -\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}\alpha_i\alpha_jy_iy_j \mathbf{x}_i^{\top}\mathbf{x}_j + \sum_{i=1}^{n}\alpha_i\\ &= -\frac{1}{2}{\boldsymbol\alpha}^{\top}\mathbf{H}{\boldsymbol\alpha}+ \mathbf{1}^{\top}_n {\boldsymbol\alpha} \end{align*}$
where $\mathbf{H}= \begin{pmatrix} \langle y_i \mathbf{x}_i, y_j \mathbf{x}_j\rangle \end{pmatrix}$ .

Dual Problem

When KKT conditions are satisfied, the primal problem is equivalent to the dual problem
$\begin{align*} \max\limits_{{\boldsymbol \alpha}}\min\limits_{\beta_0,{\boldsymbol\beta}}\ &F_P(\beta_0,{\boldsymbol\beta},{\boldsymbol\alpha}) \\ s.t. \quad& {\boldsymbol\alpha} \succeq \mathbf{0} \end{align*}$
i.e.
$\begin{align*} \max\limits_{{\boldsymbol \alpha}}\ &F_D({\boldsymbol\alpha}) \\ s.t. \quad& {\boldsymbol\alpha} \succeq \mathbf{0}\\ &{\boldsymbol\alpha}^{\top}\mathbf{y}=0 \\ \end{align*}$

If ${\boldsymbol\alpha}^*$ solves this optimization problem, then
${\boldsymbol\beta}^*= \sum_{i=1}^{n} \alpha_i^* y_i \mathbf{x}_i$
By using KKT complementarity condition,
${\boldsymbol\beta}^*= \sum_{i\in SV} \alpha_i^* y_i \mathbf{x}_i$
where $SV\subset\{1,2,\cdots,n\}$ is the set of supporting vectors.

Then $\beta_0^*= \dfrac{1}{|SV|} \sum_{i\in SV} \dfrac{1-y_i \mathbf{x}_i^{\top}{\boldsymbol\beta}^*}{y_i}$

Since
$\begin{align*} \|{\boldsymbol\beta}\|^2&= \sum_{i=1}^{n}\alpha_i^*y_i \mathbf{x}_i^{\top} {\boldsymbol\beta} \\ &=\sum_{i=1}^{n}\alpha_i^*[1-y_i\beta_0]\\ &=\sum_{i=1}^{n}\alpha_i^* \end{align*}$
the maximum margin is given by $\dfrac{2}{\|{\boldsymbol\beta}\|}=\dfrac{2}{\sqrt{\sum_{i=1}^{n}\alpha_i^*}}$ .

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

支持向量机系列（一）——线性可分情形下的SVM

Linear Support Vector Machines in the Linearly Separable Case

Problem Description

Primal Problem Given by Lagrangian Multipliers

Dual Problem

推荐阅读更多精彩内容