-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathall_2.html
405 lines (256 loc) · 15.1 KB
/
all_2.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
<!doctype html>
<html class="no-js" lang="en">
<head>
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>
Helei's Tech Notes
</title>
<meta name="description" content="(map learn unkown-stream)">
<link href="atom.xml" rel="alternate" title="Helei's Tech Notes" type="application/atom+xml">
<link rel="stylesheet" href="asset/css/foundation.min.css" />
<link rel="stylesheet" href="asset/css/docs.css" />
<script src="asset/js/vendor/modernizr.js"></script>
<script src="asset/js/vendor/jquery.js"></script>
<script src="asset/highlightjs/highlight.pack.js"></script>
<link href="asset/highlightjs/styles/github.css" media="screen, projection" rel="stylesheet" type="text/css">
<script>hljs.initHighlightingOnLoad();</script>
</head>
<body class="antialiased hide-extras">
<div class="marketing off-canvas-wrap" data-offcanvas>
<div class="inner-wrap">
<nav class="top-bar docs-bar hide-for-small" data-topbar>
<div id="header">
<h1><a href="index.html">Helei's Tech Notes</a></h1>
</div>
</nav>
<nav class="tab-bar show-for-small">
<a href="javascript:void(0)" class="left-off-canvas-toggle menu-icon">
<span> Helei's Tech Notes</span>
</a>
</nav>
<aside class="left-off-canvas-menu">
<ul class="off-canvas-list">
<li><a href="index.html">Home</a></li>
<li class="divider"></li>
<li><label>技术</label></li>
<li><a title="Nand2tetris - CPU 是机器语言的解释器" href="15511071282967.html">Nand2tetris - CPU 是机器语言的解释器</a></li>
<li><a title="Nand2tetris - 触发器，寄存器，RAM" href="15471318129470.html">Nand2tetris - 触发器，寄存器，RAM</a></li>
<li><a title="Nand2tetris - 从布尔逻辑到算数运算" href="15468825413653.html">Nand2tetris - 从布尔逻辑到算数运算</a></li>
<li><a title="Nand2tetris - 布尔逻辑" href="15467841044137.html">Nand2tetris - 布尔逻辑</a></li>
<li><a title="Flask，从简单开始" href="15013781349463.html">Flask，从简单开始</a></li>
<li><a title="Apache 配置文件解释" href="14698086378177.html">Apache 配置文件解释</a></li>
<li><a title="Git" href="14696393471602.html">Git</a></li>
<li><a title="shared_ptr 原理及事故" href="14696398760857.html">shared_ptr 原理及事故</a></li>
<li class="divider"></li>
<li><label>算法</label></li>
<li><a title="SVD在图像处理中的基本应用" href="15084626290253.html">SVD在图像处理中的基本应用</a></li>
<li><a title="神经网络计算模型 - 理论解释" href="14696391071598.html">神经网络计算模型 - 理论解释</a></li>
<li><a title="fastText 源码分析" href="14732610572844.html">fastText 源码分析</a></li>
<li><a title="SVM 推导" href="14698080869715.html">SVM 推导</a></li>
<li><a title="WSABIE 算法解释" href="14696374110477.html">WSABIE 算法解释</a></li>
<li class="divider"></li>
<li><label>想法</label></li>
<li><a title="2019 新年快乐" href="15467823342030.html">2019 新年快乐</a></li>
<li><a title="如何学习新技术" href="14953815607558.html">如何学习新技术</a></li>
</ul>
</aside>
<a class="exit-off-canvas" href="#"></a>
<section id="main-content" role="main" class="scroll-container">
<div class="row">
<div class="large-3 medium-3 columns">
<div class="hide-for-small">
<div class="sidebar">
<nav>
<ul id="side-nav" class="side-nav">
<li class="side-title"><span>技术</span></li>
<li><a title="Nand2tetris - CPU 是机器语言的解释器" href="15511071282967.html">Nand2tetris - CPU 是机器语言的解释器</a></li>
<li><a title="Nand2tetris - 触发器，寄存器，RAM" href="15471318129470.html">Nand2tetris - 触发器，寄存器，RAM</a></li>
<li><a title="Nand2tetris - 从布尔逻辑到算数运算" href="15468825413653.html">Nand2tetris - 从布尔逻辑到算数运算</a></li>
<li><a title="Nand2tetris - 布尔逻辑" href="15467841044137.html">Nand2tetris - 布尔逻辑</a></li>
<li><a title="Flask，从简单开始" href="15013781349463.html">Flask，从简单开始</a></li>
<li><a title="Apache 配置文件解释" href="14698086378177.html">Apache 配置文件解释</a></li>
<li><a title="Git" href="14696393471602.html">Git</a></li>
<li><a title="shared_ptr 原理及事故" href="14696398760857.html">shared_ptr 原理及事故</a></li>
<li class="side-title"><span>算法</span></li>
<li><a title="SVD在图像处理中的基本应用" href="15084626290253.html">SVD在图像处理中的基本应用</a></li>
<li><a title="神经网络计算模型 - 理论解释" href="14696391071598.html">神经网络计算模型 - 理论解释</a></li>
<li><a title="fastText 源码分析" href="14732610572844.html">fastText 源码分析</a></li>
<li><a title="SVM 推导" href="14698080869715.html">SVM 推导</a></li>
<li><a title="WSABIE 算法解释" href="14696374110477.html">WSABIE 算法解释</a></li>
<li class="side-title"><span>想法</span></li>
<li><a title="2019 新年快乐" href="15467823342030.html">2019 新年快乐</a></li>
<li><a title="如何学习新技术" href="14953815607558.html">如何学习新技术</a></li>
</ul>
</nav>
</div>
</div>
</div>
<div class="large-9 medium-9 columns">
<div class="markdown-body">
<h1>SVM 推导</h1>
<h2 id="toc_0">1. Intuition</h2>
<p>（每个）样本点距离分类面越远，说明分类面选得越好。为了度量这一点，我们引入<strong>函数间隔</strong>和<strong>几何间隔</strong>。这里的间隔（margin）指的是点与分类面的间隔。</p>
<h3 id="toc_1">函数间隔</h3>
<ul>
<li><p>单个样本<br/>
\[ \hat{\gamma}_i=y_i(\omega^Tx+b) \]</p></li>
<li><p>样本集<br/>
\[ \hat{\gamma}=\min_{1..m}\hat{\gamma}_i \]</p></li>
<li><p>性质<br/>
由于没有对 w 和 b 进行归一化，函数间隔在两者 scale 时候，将会成倍变化。</p></li>
</ul>
<h3 id="toc_2">几何间隔</h3>
<ul>
<li><p>单个样本<br/>
\[ \gamma_i = \hat{\gamma}_i / ||\omega||\]</p></li>
<li><p>样本集<br/>
\[ \gamma=\min_{1..m}\gamma_i \]</p></li>
<li><p>性质<br/>
对 w 进行了归一化，这样，在最优化的时候，我们可以针对 w 的长度施加各种限制，但不影响最终结果。</p></li>
</ul>
<h2 id="toc_3">2. 最优化问题</h2>
<h3 id="toc_4">问题化简</h3>
<ol>
<li><p>基础形态<br/>
\[ \max_{\gamma,\omega,b}\gamma \\ y_i(\omega^tx+b)\ge\gamma \\ ||w||=1\]<br/>
<em>最优化条件非凸</em></p></li>
<li><p>基础形态2<br/>
\[ \max_{\hat{\gamma},\omega,b}\hat{\gamma}/||w|| \\ y_i(\omega^tx+b)\ge\hat{\gamma} \]<br/>
<em>最优化目标非凸</em></p></li>
<li><p>QP形态（施加限制，函数间隔为1，且最大变最小）<br/>
\[ \min_{\omega,b}1/2||w||^2 \\ y_i(\omega^tx+b)\ge1 \]<br/>
<em>二次规划（凸）</em></p></li>
</ol>
<h3 id="toc_5">对偶问题</h3>
<p>对于最优化问题：</p>
<p>\[ \min_\omega f(\omega) \\ g_i(\omega)\le0\ (i=1...k) \\ h_i(\omega)=0\ (i=1..l)\]</p>
<p>有<strong>广义拉格朗日函数</strong>:</p>
<p>\[ L(\omega,\alpha,\beta) = f(\omega)+\Sigma\alpha_ig_i(\omega) + \Sigma\beta_ih_i(\omega) \]</p>
<p>其中要求 alpha 大等于0（显然，否则 Primal 问题不成立）</p>
<ul>
<li><p>Primal 问题 (p*)<br/>
\[ \min_\omega\max_{\alpha,\beta}L(\omega,\alpha,\beta) \]<br/>
一旦 w 超出限定范围，内层的 max 立马飙到正无穷</p></li>
<li><p>Dual 问题 (d*)<br/>
\[ \max_{\alpha,\beta}\min_\omega L(\omega,\alpha,\beta) \]</p></li>
<li><p>两者关系<br/>
\[ d^*\le p^*\]<br/>
根据alpha,beta,g,h的取值范围，在可行域内，拉格朗日函数必须小等于f(w)，自然也小等于p*，无论它怎么min，max，依然小等于。</p></li>
</ul>
<p><strong>在f,g是凸函数，h是仿射函数（wx+b)，且g包围的区域不为空的时候</strong></p>
<p>w*是原问题的解，alpha*，beta*是对偶问题的解，且<br/>
\[ d^*=p^*=L(\omega^*,\alpha^*,\beta^*)\]</p>
<p>此时，有KKT条件成立（充要？）</p>
<p>\[ \frac{\partial}{\partial \omega_i}L(\omega^*,\alpha^*,\beta^*)=0 \\<br/>
\frac{\partial}{\partial \beta_i}L(\omega^*,\alpha^*,\beta^*)=0 \\<br/>
\alpha^*_ig_i(\omega^*)=0 \\<br/>
g_i(\omega^*)\le0 \\<br/>
\alpha^*\ge0<br/>
\]</p>
<h2 id="toc_6">3. 将QP转换为Dual形式</h2>
<h3 id="toc_7">重写限制条件</h3>
<p>\[ g_i(\omega)=1-y_i(\omega^Tx_i+b)\le0\]<br/>
性质：根据KKT条件，<strong>当alpha_i大于0时，g_i(w)=0</strong>，此时xi是支撑矢量。</p>
<h3 id="toc_8">构造广义拉格朗日函数</h3>
<p>\[ L(\omega,b,\alpha)=1/2||w||^2+\Sigma\alpha_ig_i(\omega)\\<br/>
= 1/2||w||^2+\Sigma_{i=1..m}\alpha_i[1-y_i(\omega^Tx_i+b)]\\<br/>
= 1/2||w||^2+\Sigma\alpha_i-\Sigma\alpha_iy_i\omega^Tx_i-\Sigma\alpha_i y_i b<br/>
\]</p>
<h3 id="toc_9">对于 w 求最小值</h3>
<p>令<br/>
\[<br/>
\frac{\partial}{\partial\omega}L(\omega,b,\alpha)\\<br/>
=\omega-\Sigma\alpha_iy_ix_i=0<br/>
\]<br/>
所以有：<br/>
\[<br/>
\omega^*=\Sigma\alpha_iy_ix_i<br/>
\]<br/>
将其代入到拉格朗日函数中：<br/>
\[<br/>
L(\omega^*,b,\alpha)=1/2(\Sigma\alpha_iy_ix_i^T)(\Sigma\alpha_iy_ix_i)+\Sigma\alpha_i-\Sigma\alpha_iy_i(\Sigma\alpha_iy_ix_i^T)x_i-\Sigma\alpha_iy_ib\\<br/>
=1/2\Sigma_{i,j}\alpha_i\alpha_jy_iy_jx_i^Tx_j+\Sigma\alpha_i-\Sigma_{i,j}\alpha_i\alpha_jy_iy_jx_i^Tx_j-\Sigma\alpha_iy_ib<br/>
\\<br/>
=-1/2\Sigma_{i,j}\alpha_i\alpha_jy_iy_jx_i^Tx_j+\Sigma\alpha_i-\Sigma\alpha_iy_ib<br/>
\]</p>
<h3 id="toc_10">对于 b 求最小值</h3>
<p>令<br/>
\[<br/>
\frac{\partial}{\partial b}L(\omega,b,\alpha)\\<br/>
=-\Sigma a_iy_i=0<br/>
\]<br/>
带入到上一步中，消掉最后一项，得到：<br/>
\[<br/>
L(\omega^*,b,\alpha)=-1/2\Sigma_{i,j}\alpha_i\alpha_jy_iy_jx_i^Tx_j+\Sigma\alpha_i<br/>
\]</p>
<h3 id="toc_11">得到对偶问题</h3>
<p>整理得到以下最终的最优化问题：</p>
<p>\[<br/>
\max_\alpha-1/2\Sigma_{i,j}\alpha_i\alpha_jy_iy_jx_i^Tx_j+\Sigma\alpha_i\\<br/>
\alpha_i\ge0\ (i=1..m)\\<br/>
\Sigma a_iy_i=0\ (i=1..m)<br/>
\]</p>
<p>在得到alpha后，w可以根据上面的推导得到，对于b，在w得到后，将正负样本中最接近超平面的两个加起来取平均（根据图示可以很容易看出来）</p>
<p>\[<br/>
b^*=-\frac{\min{\omega^*}^Tx_++\max{\omega^*}^Tx_-}{2}<br/>
\]</p>
<p>在预测时，我们可以不用 w，而是采用如下的公式（kernel trick的基础）</p>
<p>\[<br/>
\omega^Tx+b=\Sigma\alpha_iy_i(x_i^Tx)+b<br/>
\]</p>
<p>因为只有支撑矢量的alpha才非零，所以，我们只需要保存支撑矢量（和b），就能进行分类。</p>
<h2 id="toc_12">4. 核函数</h2>
<p>给定一个feature mapping（x->phi(x)），核函数K定义为：</p>
<p>\[<br/>
K(x,z)=\phi(x)^T\phi(z)<br/>
\]</p>
<p>可以看出，当x和z相近时，核函数取值越大，x和z越相似。我们可以直接找核函数，而不用找到显式的 feature mapping，为了做到这一点，必须规定核函数所需要满足的条件。</p>
<h3 id="toc_13">Mercer定理</h3>
<p>给定函数K，对于任意m个向量，它们构成的核矩阵对称半正定 <=> K是一个核函数</p>
<h2 id="toc_14">5. 软间隔策略</h2>
<p>为了处理线性不可分情况，SVM可以改写为：</p>
<p>\[<br/>
\min_{\omega,b}1/2||w||^2 + C\Sigma\xi_i\\<br/>
y_i(\omega^tx+b)\ge1-\xi_i\ (i=1..m)\\<br/>
\xi_i\ge0 (i=1..m)<br/>
\]</p>
<p>化简成对偶问题后，和之前的形式惊人相近，除了alpha的范围</p>
<p>\[<br/>
\max_\alpha-1/2\Sigma_{i,j}\alpha_i\alpha_jy_iy_jx_i^Tx_j+\Sigma\alpha_i\\<br/>
C\ge\alpha_i\ge0\ (i=1..m)\\<br/>
\Sigma a_iy_i=0\ (i=1..m)<br/>
\]</p>
<p>此时，b的计算也变了（略），且KKT条件有如下推论：</p>
<p>\[<br/>
\alpha_i=0 ⇒ y_i(\omega^Tx+b)\ge1\\<br/>
\alpha_i=C ⇒ y_i(\omega^Tx+b)\le1\\<br/>
0\le\alpha_i\le C ⇒ y_i(\omega^Tx+b)=1<br/>
\]</p>
</div>
</div></div>
<div class="page-bottom">
<div class="row">
<hr />
<div class="small-9 columns">
<p class="copyright">Copyright © 2015
Powered by <a target="_blank" href="http://www.mweb.im">MWeb</a>,
Theme used <a target="_blank" href="http://github.com">GitHub CSS</a>.</p>
</div>
<div class="small-3 columns">
<p class="copyright text-right"><a href="#header">TOP</a></p>
</div>
</div>
</div>
</section>
</div>
</div>
<script src="asset/js/foundation.min.js"></script>
<script src="asset/js/foundation/foundation.offcanvas.js"></script>
<script>
$(document).foundation();
</script>
<script src="asset/chart/all-min.js"></script><script type="text/javascript">$(function(){ var mwebii=0; var mwebChartEleId = 'mweb-chart-ele-'; $('pre>code').each(function(){ mwebii++; var eleiid = mwebChartEleId+mwebii; if($(this).hasClass('language-sequence')){ var ele = $(this).addClass('nohighlight').parent(); $('<div id="'+eleiid+'"></div>').insertAfter(ele); ele.hide(); var diagram = Diagram.parse($(this).text()); diagram.drawSVG(eleiid,{theme: 'simple'}); }else if($(this).hasClass('language-flow')){ var ele = $(this).addClass('nohighlight').parent(); $('<div id="'+eleiid+'"></div>').insertAfter(ele); ele.hide(); var diagram = flowchart.parse($(this).text()); diagram.drawSVG(eleiid); } });});</script>
<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script><script type="text/x-mathjax-config">MathJax.Hub.Config({TeX: { equationNumbers: { autoNumber: "AMS" } }});</script>
</body>
</html>