-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path14968173531750.html
executable file
·753 lines (496 loc) · 30.1 KB
/
14968173531750.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
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
<!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>
CS229 学习笔记 Part3 - 雪地
</title>
<link href="atom.xml" rel="alternate" title="雪地" type="application/atom+xml">
<link rel="stylesheet" href="asset/css/foundation.min.css" />
<link rel="stylesheet" href="asset/css/docs.css" />
<link rel="icon" href="asset/img/favicon.ico" />
<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>
<script type="text/javascript">
function before_search(){
var searchVal = 'site:yinzo.github.io ' + document.getElementById('search_input').value;
document.getElementById('search_q').value = searchVal;
return true;
}
</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>
<section class="top-bar-section">
<div class="row">
<div style="position: relative;width:100%;"><div style="position: absolute; width:100%;">
<ul id="main-menu" class="left">
<li id="menu_item_index"><a href="index.html">Blog</a></li>
<li id="menu_item_archives"><a href="archives.html">Archives</a></li>
<li id="menu_item_about"><a href="http://yinz.xyz/">Home</a></li>
</ul>
<ul class="right" id="search-wrap">
<li>
<form target="_blank" onsubmit="return before_search();" action="http://google.com/search" method="get">
<input type="hidden" id="search_q" name="q" value="" />
<input tabindex="1" type="search" id="search_input" placeholder="Search"/>
</form>
</li>
</ul>
</div></div>
</div>
</section>
</nav>
<nav class="tab-bar show-for-small">
<a href="javascript:void(0)" class="left-off-canvas-toggle menu-icon">
<span> 雪地</span>
</a>
</nav>
<aside class="left-off-canvas-menu">
<ul class="off-canvas-list">
<li><a href="index.html">Blog</a></li>
<li><a href="archives.html">Archives</a></li>
<li><a href="http://yinz.xyz/">Home</a></li>
<li><label>Categories</label></li>
<li><a href="Security%20Info.html">Security Info</a></li>
<li><a href="Adversary%20Learning.html">Adversary Learning</a></li>
<li><a href="TCPIP.html">TCP/IP</a></li>
<li><a href="Pattern%20Recognition.html">Pattern Recognition</a></li>
<li><a href="Python.html">Python</a></li>
<li><a href="OS.html">OS</a></li>
<li><a href="Deep%20Learning.html">Deep Learning</a></li>
<li><a href="Machine%20Learning.html">Machine Learning</a></li>
</ul>
</aside>
<a class="exit-off-canvas" href="#"></a>
<section id="main-content" role="main" class="scroll-container">
<script type="text/javascript">
$(function(){
$('#menu_item_index').addClass('is_active');
});
</script>
<div class="row">
<div class="large-8 medium-8 columns">
<div class="markdown-body article-wrap">
<div class="article">
<h1>CS229 学习笔记 Part3</h1>
<div class="read-more clearfix">
<span class="date">2017/6/7 14:35 下午</span>
<span>posted in </span>
<span class="posted-in"><a href='Machine%20Learning.html'>Machine Learning</a></span>
<span class="comments">
</span>
</div>
</div><!-- article -->
<div class="article-content">
<ul>
<li>
<a href="#toc_0">SVM</a>
<ul>
<li>
<a href="#toc_1">函数间隔和几何间隔 (Functional and geometric margin)</a>
</li>
<li>
<a href="#toc_2">最优间隔分类器 (Optimal margin classifier)</a>
</li>
<li>
<a href="#toc_3">拉格朗日对偶问题</a>
<ul>
<li>
<a href="#toc_4">原始问题</a>
</li>
<li>
<a href="#toc_5">对偶问题</a>
</li>
<li>
<a href="#toc_6">KKT 条件</a>
</li>
</ul>
</li>
<li>
<a href="#toc_7">回到最优间隔分类器问题</a>
</li>
<li>
<a href="#toc_8">核 (Kernels)</a>
</li>
<li>
<a href="#toc_9">正则化</a>
</li>
<li>
<a href="#toc_10">SMO 算法</a>
<ul>
<li>
<a href="#toc_11">坐标上升算法 (Coordinate ascent)</a>
</li>
<li>
<a href="#toc_12">SMO</a>
</li>
</ul>
</li>
</ul>
</li>
</ul>
<h2 id="toc_0">SVM</h2>
<p>CS229 对于 SVM 的理论解释是我学习到的最详细也是最好的一份资料了，对比对象有周志华《机器学习》、《机器学习实战》、Coursera 上的 Machine Learning 等。相当推荐学习 CS229。</p>
<p>分类间隔 (Margin) 和 SVM 的优化目标『最大化分类间隔』这里就不多说了，很好理解，主要还是记录 CS229 中学到的新内容。一个数据点离分类边界 (decision boundary) 越远，则确信度越高。我们的优化目标也相当于寻找一个远离所有数据点的分类边界，当然，前提是这个分类边界得到的分类都正确。</p>
<p>SVM 的一些特殊定义也提及一下，</p>
<ul>
<li>\(y\) 的取值不是 \(\{0,1\}\) 而是 \(\{-1,1\}\)。</li>
<li>假设函数 \(h_{w,b}(x) = g(w^Tx+b)\) 中，我们把截距项单独写出来，便与后续的计算。</li>
<li>我们的分类器输出结果会直接是 1 或 -1，不像 Logistic 回归那样先输出 \(y\) 是某一类的概率。</li>
</ul>
<span id="more"></span><!-- more -->
<h3 id="toc_1">函数间隔和几何间隔 (Functional and geometric margin)</h3>
<p>函数间隔 \(\hat{\gamma}\) 的定义如下<br/>
\[\hat{\gamma}^{(i)} = y^{(i)}(w^Tx+b)\]</p>
<p>\[\hat{\gamma} = \min_{i=1,\cdots,m} \hat{\gamma}^{(i)}\]</p>
<p>函数间隔，是所有数据点的函数输出中的最小值，函数间隔越大，说明这个点分类的自信越高。但是可以发现，我们等比例放大参数 \(w\) 和 \(b\) 的数值大小，可以使得函数间隔变大，并且分类间隔直线的位置并不会移动。于是我们又定义了几何间隔</p>
<p><img src="media/14968173531750/14968200759292.jpg" alt=""/></p>
<p>注意图中的点 A，我们需要求 A 到分类边界的距离 \(\gamma^{(i)}\)，就是我们现在需要求的值。</p>
<p>因为 A 代表着 \(x^{(i)}\)， 所以我们可以得到点 B 的公式为 \(x^{(i)} - \gamma^{(i)} \cdot w/\|w\|\)，并且点 B 在分类边界上，我们有 \(w^Tx+b=0\)，因此</p>
<p>\[w^T\left(x^{(i)}-\gamma^{(i)}\frac{w}{\|w\|}\right)+b=0\]</p>
<p>\[\gamma^{(i)} = \frac{w^Tx^{(i)}+b}{\|w\|} = \left(\frac{w}{\|w\|}\right)^Tx^{(i)}+\frac{b}{\|w\|}\]</p>
<p>再把函数的正负性考虑进去，最终我们得到</p>
<p>\[\gamma^{(i)} = y^{(i)}\left(\left(\frac{w}{\|w\|}\right)^Tx^{(i)}+\frac{b}{\|w\|}\right)\]</p>
<p>注意如果 \(\|w\| = 1\)，则函数间隔等于几何间隔——这给了我们一个联系起这两种间隔的思路。并且，几何间隔并不受参数的等比缩放影响，这个特性在后面的推导中很有用。比如说我们在拟合 w 和 b 的时候，我们需要对他进行一个缩放以满足 \(\|w\| = 1\) 这个约束，那么我们并不需要担心几何间隔会因此改变。</p>
<p>最后，对于一组大小为 m 的训练集，我们同样定义</p>
<p>\[\gamma = \min_{i=1,\cdots,m}\gamma^{(i)}\]</p>
<h3 id="toc_2">最优间隔分类器 (Optimal margin classifier)</h3>
<p>当我们假设数据是线性可分的时候，也就是存在一个超平面能够将正类和负类分隔开，这时我们如何找到这个最大化集合间隔的分类器呢，有以下优化问题</p>
<p>\[\begin{eqnarray}<br/>
\max_{\gamma,w,b}&&\gamma \nonumber \\<br/>
s.t. & &y^{(i)}(w^Tx^{(i)}+b)\geq \gamma,i=1,\cdots,m \nonumber \\<br/>
&&\|w\|=1 \nonumber \\<br/>
\end{eqnarray}\]</p>
<p>我们限制了 \(\|w\|=1\)，所以几何间隔和函数间隔此时是相等的。因此，解决这个优化问题，我们能够求出对于这个训练集最大的几何间隔。但是，"\(\|w\|=1\)“ 这个限制不怎么友好（non-convex），我们无法套用现成的优化求解算法来解决它，所以我们尝试把它变形一下</p>
<p>\[\begin{eqnarray}\max_{\hat{\gamma},w,b} &&\frac{\hat{\gamma}}{\|w\|} \nonumber \\<br/>
s.t. && y^{(i)}(w^Tx^{(i)}+b)\geq \hat{\gamma},\ \ i=1,\cdots,m \nonumber \\<br/>
\end{eqnarray}\]</p>
<p>现在我们尝试最大化 \(\hat{\gamma}/\|w\|\)，这个优化问题和上面的那个是等价的，并且我们成功抛弃掉了那个不友好的限制条件。但是，现在变成我们的目标函数不怎么友好了 (non-convex)。</p>
<p>让我们继续尝试变形。回想起我们能够随意等比例缩放 \(w,b\)，这非常关键。我们限制\(\hat{\gamma}=1\)，则我们的优化目标可以变为最大化 \(\hat{\gamma}/\|w\| = 1/\|w\|\)，也就相当于最小化 \(\|w\|^2\)</p>
<p>\[\begin{eqnarray}<br/>
\min_{\gamma,w,b} &&\frac{1}{2}\|w\|^2 \nonumber \\<br/>
s.t. && y^{(i)}(w^Tx^{(i)}+b)\geq 1,\ \ i=1,\cdots,m \nonumber \\<br/>
\end{eqnarray}\]</p>
<p>现在我们终于将问题转化为一个能够使用现成计算包解决的优化问题了。上面的优化问题是一个凸二次优化问题，并且只有一个线性约束。但是相比使用现成计算包直接解决这个优化问题，我们还有一个解决办法，并且解决过程中还引出了更加重要的 kernel 概念。</p>
<h3 id="toc_3">拉格朗日对偶问题</h3>
<h4 id="toc_4">原始问题</h4>
<p>有『等式约束条件』和『不等式约束条件』下的优化问题，能够通过拉格朗日方法，转换为无约束的拉格朗日函数优化问题。<br/>
比如说<br/>
\[\begin{eqnarray}<br/>
\min_w && f(w)\nonumber \\<br/>
s.t. &&g_i(w) \leq 0, \ \ i=1,\cdots,k\nonumber \\<br/>
&&h_i(w)=0, \ \ i=1,\cdots,l \nonumber \\<br/>
\end{eqnarray}\]<br/>
通过引入拉格朗日乘数 \(\alpha_i, \beta_i\) ，我们能够得到拉格朗日函数</p>
<p>\[\mathcal{L}(w,\alpha,\beta) = f(w) + \sum^k_{i=1}\alpha_ig_i(w)+\sum^l_{i=1}\beta_i h_i(w)\]</p>
<p>此时，若我们对拉格朗日函数求最大值的优化问题</p>
<p>\[\theta_{\mathcal{P}}(w) = \max_{\alpha,\beta:\alpha_i \geq 0} \mathcal{L}(w,\alpha,\beta)\]</p>
<p>我们发现，当 \(h_i(w)\) 等于零的时候，即 \(w\) 的取值符合原函数约束时，拉格朗日函数等于原函数；当\(w\) 的取值不符合原函数约束时，即 \(h_i(w)\) 不等于零的时候，总能通过使 \(\beta_i\) 等于正无穷或负无穷，使得 \(\theta_{\mathcal{P}}(w)\) 等于正无穷。</p>
<p>\[\theta_{\mathcal{P}}(w) = \left\{ <br/>
\begin{array}{ll}<br/>
f(w) &若 w 满足原问题约束 \\<br/>
\infty &其他 \\<br/>
\end{array}<br/>
\right.\]</p>
<p>利用这个性质，我们再对 \(\theta_{\mathcal{P}}(w)\) 函数化为最小值的优化问题，则得到</p>
<p>\[\min_w \theta_{\mathcal{P}}(w) = \min_w \max_{\alpha,\beta:\alpha_i \geq0} \mathcal{L}(w,\alpha,\beta)\]</p>
<p>求解这一个优化问题，我们就将得到在满足原问题约束条件下，对于原目标函数 \(f(w)\) 的最小值优化问题的解，因为不符合约束条件的参数会使得函数变为正无穷，从而被符合约束条件的参数筛选掉。</p>
<p>\[\min_w \max_{\alpha,\beta:\alpha_i \geq0} \mathcal{L}(w,\alpha,\beta)\]</p>
<p>这个优化问题，就称为拉格朗日函数的原始问题 (primal problem)。</p>
<h4 id="toc_5">对偶问题</h4>
<p>那么，对偶问题是什么呢。可以看到，原始问题中有两个最值优化步骤。将这两个最值优化步骤对调一下顺序，就成为了拉格朗日函数的对偶问题 (dual problem)</p>
<p>我们称，原始问题最终求得的最优解为 \(p^*\)，对偶问题的最优解为 \(d^*\)。我们很容易想到</p>
<p>\[d^* = \max_{\alpha,\beta:\alpha_i \geq0} \min_w \mathcal{L}(w,\alpha,\beta) \leq \min_w \max_{\alpha,\beta:\alpha_i \geq0} \mathcal{L}(w,\alpha,\beta) = p^*\]</p>
<p>并且，在一定条件下，我们有</p>
<p>\[d^* = p^*\]</p>
<h4 id="toc_6">KKT 条件</h4>
<p>若满足以下假设，必定存在 \(w^*, \alpha^*, \beta^*\) 是原始问题的解。<br/>
1. 函数 \(f\) 和 \(g_i\) 都是凸函数<br/>
2. \(h_i\) 函数是仿射函数（\(h_i\) 满足 \(h_i(w) = a_i^Tw+b_i\) 形式，称 \(h_i\) 为仿射函数 (Affine)）</p>
<p>并且，若 \(w^*, \alpha^*, \beta^*\) 同时满足 <strong>KKT 条件</strong>，则此解同时是对偶问题和原始问题的解。<br/>
\[\begin{eqnarray}<br/>
\frac{\partial}{\partial w_i}\mathcal{L}(w^*,\alpha^*,\beta^*) &=& 0,i=1,\cdots,n \\<br/>
\frac{\partial}{\partial \beta_i}\mathcal{L}(w^*,\alpha^*,\beta^*) &=& 0,i=1,\cdots,l \\<br/>
\alpha_i^*g_i(w^*) &=& 0, i=1,\cdots,k \\<br/>
g_i(w^*) &\leq& 0, i=1,\cdots,k \\<br/>
\alpha^* &\geq& 0, i=1,\cdots,k \\<br/>
\end{eqnarray}\]</p>
<h3 id="toc_7">回到最优间隔分类器问题</h3>
<p>现在，我们尝试使用拉格朗日方法来解决我们的最优间隔分类器优化问题</p>
<p>\[\min_{\gamma,w,b} \frac{1}{2} \|w\|^2\]<br/>
\[s.t.\ \ y^{(i)}（w^Tx^{(i)} +b)\geq 1,\ i=1,\cdots,m\]</p>
<p>我们将约束条件化为以下形式</p>
<p>\[g_i(w) = -y^{(i)}(w^Tx^{(i)}+b) + 1 \leq 0\]</p>
<p>则我们根据 KKT 条件中的公式(3)得知，只有当函数间隔恰好等于 1 时，\(g_i(w) = 0\)，\(\alpha_i\) 才有可能大于0. 我们称 \(\alpha_i > 0\) 的数据点为支持向量 (support vectors)，也就是支持向量机的名称由来。并且支持向量的数量一般远少于训练集样本数量，这是后续算法优化的一个很重要的特性。</p>
<p>我们求出原优化问题的拉格朗日函数</p>
<p>\[ \begin{equation} \mathcal{L}(w,b,\alpha) = \frac{1}{2}\|w\|^2-\sum^m_{i=1}\alpha_i[y^{(i)}(w^Tx^{(i)}+b)-1] \end{equation} \]</p>
<p>我们求解对偶问题，首先使用 \(w,b\) 为参数，求解拉格朗日函数的最小值。则我们求函数分别对于 \(w,b\) 的偏导数并使其等于零</p>
<p>\[\nabla_w\mathcal{L}(w,b,\alpha) = w-\sum^m_{i=1}\alpha_iy^{(i)}x^{(i)}= 0\]</p>
<p>\[ \begin{equation} w=\sum^m_{i=1}\alpha_iy^{(i)}x^{(i)} \end{equation} \]</p>
<p>\[ \begin{equation} \frac{\partial}{\partial b}\mathcal{L}(w,b,\alpha) = \sum^m_{i=1} \alpha_iy^{(i)}=0\end{equation} \]</p>
<p>然后我们将他们代入原拉格朗日函数中，进行下一步最值求解</p>
<p>\[\mathcal{L}(w,b,\alpha) = \sum^m_{i=1}\alpha_i - \frac{1}{2}\sum^m_{i,j=1}y^{(i)}y^{(j)}\alpha_i\alpha_j(x^{(i)})^Tx^{(j)}\]</p>
<p>需要注意的是，此时 KKT 条件中的公式(5)，以及刚刚求出的公式(8) 成为了现在的最值优化问题的新约束。则我们得到<br/>
\[\begin{eqnarray}<br/>
\max_a &&W(\alpha) = \sum^m_{i=1}\alpha_i-\frac{1}{2}\sum^m_{i,j=1}y^{(i)}y^{(j)}\alpha_i\alpha_j\langle x^{(i)},x^{(j)}\rangle \nonumber \\ <br/>
s.t. && \alpha_i \geq 0,\ \ i=1,\cdots,m \nonumber \\<br/>
&&\sum^m_{i=1}\alpha_iy^{(i)} = 0 \nonumber \\<br/>
\end{eqnarray}\]<br/>
最终我们求出 \(\alpha_i\) 的最优值，代入到公式(7) 求得 \(w\) 的最优值，再将 \(w, \alpha_i\) 代入原拉格朗日函数公式(6) 中，求得</p>
<p>\[ \begin{equation} b^* = -\frac{\max_{i:y^{(i)}=-1}w^*Tx^{(i)} + \min_{i:y^{(i)}=1} w^{*T}x^{(i)}}{2} \end{equation} \]</p>
<p>则此时我们已经求得了我们原优化问题的最优解，可喜可贺。</p>
<h3 id="toc_8">核 (Kernels)</h3>
<p>还能有什么优化的地方？我们的分类器的可用性还存在一个前提，数据必须线性可分。如果线性不可分呢？我们引入了『核』的概念，用来对输入数据进行一个特征转换。我们定义特征函数</p>
<p>\[\phi(x) = \begin{bmatrix}<br/>
x\\<br/>
x^2\\<br/>
x^3<br/>
\end{bmatrix}\]</p>
<p>回头看我们的公式(7)，如果将它代入到我们的假设函数 \(w^Tx+b\) 中，我们得到</p>
<p>\[\begin{eqnarray}<br/>
w^Tx+b &=& \left( \sum^m_{i=1}\alpha_iy^{(i)}x^{(i)} \right)^Tx+b \\<br/>
&=& \sum^m_{i=1}\alpha_iy^{(i)}\langle x^{(i)}, x\rangle +b \\<br/>
\end{eqnarray}\]<br/>
将假设函数转化成了输入数据和所有支持向量的点积的形式（\(\langle x^{(i)},x\rangle\) 指 \(x^{(i)}\) 和 \(x\) 的点积），于是我们就可以将这个点积替换成一个特征向量的点积了。<br/>
我们再定义一个关于 \(x^{(i)}\) 和 \(x\) 的函数 \(K(x,z)\)</p>
<p>\[K(x,z) = \phi(x)^T\phi(z)\]</p>
<p>这个函数，我们就称为<strong>核函数</strong>。我们现在只需要将公式(11)中的点积替换成核函数，我们的 SVM 就可以处理非线性可分的数据集了。<br/>
为什么我们使用核函数，而不是直接套用特征向量的点积呢？让我们看下面一个例子</p>
<p>\[K(x,z) = (x^Tz)^2\]</p>
<p>也可以写成下面这个形式<br/>
\[\begin{eqnarray}<br/>
K(x,z) &=& \left(\sum^n_{i=1}x_iz_i \right) \left(\sum^n_{j=1}x_jz_j \right) \nonumber \\<br/>
&=&\sum^n_{i=1} \sum^n_{j=1}x_ix_jz_iz_j \nonumber \\<br/>
&=&\sum^n_{i,j=1}(x_ix_j)(z_iz_j)\nonumber \\<br/>
\end{eqnarray}\]<br/>
化为特征向量点积的形式，我们可以得到这个核函数对应的特征向量是这个形式的</p>
<p>\[\phi(x) = \begin{bmatrix}<br/>
x_1x_1\\<br/>
x_1x_2\\<br/>
x_1x_3\\<br/>
x_2x_1\\<br/>
x_2x_2\\<br/>
x_2x_3\\<br/>
x_3x_1\\<br/>
x_3x_2\\<br/>
x_3 x_3<br/>
\end{bmatrix}\]</p>
<p>我们可以发现，直接使用特征向量点积，计算复杂度为 \(O(n^2)\)，而核函数形式的计算复杂度仅为 \(O(n)\)。所以使用核函数，能够大幅优化计算复杂度。</p>
<p>那么，是否所有的函数都能作为核函数呢？当然不是。</p>
<p>假设 \(K\) 是一个合法核函数，并定义核函数矩阵 \(K_{ij} = K(x^{(i)},x^{(j)})\)。</p>
<p>则有 \(K_{ij} = K(x^{(i)},x^{(j)}) = \phi(x^{(i)})^T\phi(x^{(j)}) = \phi(x^{(j)})^T\phi(x^{(i)}) = K(x^{(j)},x^{(i)}) = K_{ji}\)</p>
<p>所以，<strong>核函数矩阵必须是对称的</strong></p>
<p>然后，我们使用一个任意向量 \(z\)，有</p>
<p>\[\begin{eqnarray} z^TKz &=& \sum_i\sum_jz_iK_{ij}z_j \nonumber \\<br/>
&=&\sum_i\sum_jz_i \phi(x^{(i)})^T \phi(x^{(j)}) z_j \nonumber \\<br/>
&=&\sum_i\sum_jz_i \sum_k \phi_k(x^{(i)}) \phi_k(x^{(j)}) z_j \nonumber \\<br/>
&=&\sum_k\sum_i\sum_j z_i \phi_k(x^{(i)}) \phi_k(x^{(j)}) z_j \nonumber \\<br/>
&=&\sum_k\left(\sum_i z_i\phi_k(x^{(i)})\right)^2 \nonumber \\<br/>
&\geq& 0 \nonumber <br/>
\end{eqnarray}\]</p>
<p>所以，<strong>核函数矩阵</strong>是半正定的。</p>
<p>需要注意的是，核函数的概念并不是专门为 SVM 提出的，它的概念比 SVM 要广得多。实际上你可以将任何学习算法中的点积替换成核函数，就能使得这个学习算法支持高维度特征学习。</p>
<h3 id="toc_9">正则化</h3>
<p>我们的分类器一直以来都有一个限制条件，那就是分类边界必须能够正确的分类所有的样本。我们知道现实中的样本，绝大部分都存在着噪音数据。如果出现了噪音数据，就会导致 SVM 的分类边界很不合理，如下图所示<br/>
<img src="media/14968173531750/14969181791214.jpg" alt=""/></p>
<p>为了解决这个问题，我们加入了一个 \(l1\) 正则项：</p>
<p>\[\begin{eqnarray}<br/>
\min_{\gamma,w,b} &&\frac{1}{2}\|w\| ^2+C\sum^m_{i=1}\xi_i \nonumber \\<br/>
s.t. && y^{(i)}(w^Tx^{(i)}+b)\geq1-\xi_i,i=1,\cdots,m \nonumber \\<br/>
&& \xi_i\geq0,\ i=1,\cdots,m \nonumber \\<br/>
\end{eqnarray}\]</p>
<p>这使得样本的函数间隔能够小于1 （甚至为负数）。其中的参数 \(C\) 代表了两个目标权重的权衡：</p>
<ol>
<li>使所有样本的函数间隔大于1</li>
<li>最小化 \(\|w\|^2\)</li>
</ol>
<p>\(C\) 越大，则优化目标越偏向目标1，即最原始的，强迫所有样本必须分类正确的模型。</p>
<p>在新的优化目标下，我们的 KKT 条件有一点改变：</p>
<p>\[\begin{eqnarray}<br/>
\alpha_i = 0 &\Rightarrow& y^{(i)}(w^Tx^{(i)}+b)\geq1 \\<br/>
\alpha_i = C &\Rightarrow& y^{(i)}(w^Tx^{(i)}+b)\leq 1 \\<br/>
0<\alpha_i <C &\Rightarrow& y^{(i)}(w^Tx^{(i)}+b) = 1 \\<br/>
\end{eqnarray}\]</p>
<h3 id="toc_10">SMO 算法</h3>
<p>SMO 算法全称 Sequential minimal optimization，提供了一种有效的方法来解决 SVM 的对偶问题。在介绍 SMO 算法之前，我们先了解另一个算法。</p>
<h4 id="toc_11">坐标上升算法 (Coordinate ascent)</h4>
<p>假设你正在尝试解决一个无约束优化问题</p>
<p>\[\max_aW(\alpha_1,\alpha_2,\cdots,\alpha_m)\]</p>
<p>新算法逻辑如下：</p>
<p><img src="media/14968173531750/14970255117856.jpg" alt=""/><br/>
可以看到在循环的最里层，我们固定了除了 \(\alpha_i\) 以外的所有参数，然后仅通过 \(\alpha_i\) 来优化函数 \(W\)。以下是一个坐标上升算法实战中的情形<br/>
<img src="media/14968173531750/14970260504690.jpg" alt=""/></p>
<h4 id="toc_12">SMO</h4>
<p>这是我们准备解决的对偶优化问题：</p>
<p>\[\begin{eqnarray}<br/>
\max_\alpha &&W(\alpha) = \sum^m_{i=1}\alpha_i -\frac{1}{2}\sum^m_{i,j=1}y^{(i)}y^{(j)}\alpha_i\alpha_j\langle x^{(i)},x^{(j)}\rangle \\<br/>
s.t. &&0\leq \alpha_i \leq C,\ \ i=1,\cdots,m \\ <br/>
&&\sum^m_{i=1}\alpha_iy^{(i)}=0 \\<br/>
\end{eqnarray}\]<br/>
假设我们使 \(\alpha_i\) 都符合公式(16)、(17)的约束。现在，如果我们将 \(\alpha_2,\cdots,\alpha_m\) 都固定，并使用坐标上升算法来尝试优化目标函数，你觉得这能产生效果吗？并不能。因为我们有一个约束是这样的</p>
<p>\[ \alpha_1y^{(1)} = -\sum^m_{i=2}\alpha_iy^{(i)}\]</p>
<p>两边同乘以 \(y^{(1)}\)</p>
<p>\[\alpha_1 = -y^{(1)}\sum^m_{i=2}\alpha_iy^{(i)}\]<br/>
因此，如果你固定了 \(\alpha_2,\cdots,\alpha_m\)，实际上你也固定了 \(\alpha_1\)。所以如果我们需要通过 \(\alpha_i\) 来优化目标函数，我们需要同时使用其中的两项来进行优化，也就是我们 SMO 算法的主要思想<br/>
<img src="media/14968173531750/14970275107451.jpg" alt=""/></p>
<p>我们使用 SMO 算法有一个重要的原因，那就是 \(\alpha_i, \alpha_j\) 的计算非常简单。</p>
<p>首先，我们通过计算剩余项的和，可以写出以下约束</p>
<p>\[\alpha_1y^{(1)}+\alpha_2y^{(2)}=-\sum^m_{i=3}\alpha_iy^{(i)}\]<br/>
使等号右边等于一个常数 \(\zeta\)，则我们有</p>
<p>\[ \begin{equation}\alpha_1y^{(1)}+\alpha_2y^{(2)} = \zeta \end{equation} \]<br/>
并且，根据新的 KKT 条件公式(12-14) \(\alpha_i\) 的取值范围被固定在了 \([0,C]\)，则我们可以画出以下图像<br/>
<img src="media/14968173531750/14970286141343.jpg" alt=""/></p>
<p>并且根据公式(18) ，我们发现能够将原优化目标写成以下形式的二次函数<br/>
\[a\alpha_2^2 + b\alpha_2+c\]</p>
<p>则我们先计算得出 \(\alpha_2\) 的最优值，再根据上图的值域限制进行一个修剪 (clip)<br/>
<img src="media/14968173531750/14970845058858.jpg" alt=""/><br/>
以此得到符合限制条件的新 \(\alpha_2\) 值。</p>
</div>
<div class="row">
<div class="large-6 columns">
<p class="text-left" style="padding:15px 0px;">
</p>
</div>
<div class="large-6 columns">
<p class="text-right" style="padding:15px 0px;">
<a href="14965964854250.html"
title="Next Post: CS229 学习笔记 Part2">CS229 学习笔记 Part2 »</a>
</p>
</div>
</div>
<div class="comments-wrap">
<div class="share-comments">
<div id="disqus_thread"></div>
<script>
/**
* RECOMMENDED CONFIGURATION VARIABLES: EDIT AND UNCOMMENT THE SECTION BELOW TO INSERT DYNAMIC VALUES FROM YOUR PLATFORM OR CMS.
* LEARN WHY DEFINING THESE VARIABLES IS IMPORTANT: https://disqus.com/admin/universalcode/#configuration-variables
*/
/*
var disqus_config = function () {
this.page.url = PAGE_URL; // Replace PAGE_URL with your page's canonical URL variable
this.page.identifier = PAGE_IDENTIFIER; // Replace PAGE_IDENTIFIER with your page's unique identifier variable
};
*/
(function() { // DON'T EDIT BELOW THIS LINE
var d = document, s = d.createElement('script');
s.src = '//yinzo.disqus.com/embed.js';
s.setAttribute('data-timestamp', +new Date());
(d.head || d.body).appendChild(s);
})();
</script>
<noscript>Please enable JavaScript to view the <a href="https://disqus.com/?ref_noscript" rel="nofollow">comments powered by Disqus.</a></noscript>
</div>
</div>
</div><!-- article-wrap -->
</div><!-- large 8 -->
<div class="large-4 medium-4 columns">
<div class="hide-for-small">
<div id="sidebar" class="sidebar">
<div id="site-info" class="site-info">
<div class="site-a-logo"><img src="asset/img/3.png" /></div>
<h1>雪地</h1>
<div class="site-des"></div>
<div class="social">
<a class="github" target="_blank" href="https://github.com/Yinzo" title="GitHub">GitHub</a>
<a class="email" href="mailto:[email protected]" title="Email">Email</a>
<a class="rss" href="atom.xml" title="RSS">RSS</a>
</div>
</div>
<div id="site-categories" class="side-item ">
<div class="side-header">
<h2>Categories</h2>
</div>
<div class="side-content">
<p class="cat-list">
<a href="Security%20Info.html"><strong>Security Info</strong></a>
<a href="Adversary%20Learning.html"><strong>Adversary Learning</strong></a>
<a href="TCPIP.html"><strong>TCP/IP</strong></a>
<a href="Pattern%20Recognition.html"><strong>Pattern Recognition</strong></a>
<a href="Python.html"><strong>Python</strong></a>
<a href="OS.html"><strong>OS</strong></a>
<a href="Deep%20Learning.html"><strong>Deep Learning</strong></a>
<a href="Machine%20Learning.html"><strong>Machine Learning</strong></a>
</p>
</div>
</div>
<div id="site-categories" class="side-item">
<div class="side-header">
<h2>Recent Posts</h2>
</div>
<div class="side-content">
<ul class="posts-list">
<li class="post">
<a href="14968173531750.html">CS229 学习笔记 Part3</a>
</li>
<li class="post">
<a href="14965964854250.html">CS229 学习笔记 Part2</a>
</li>
<li class="post">
<a href="14946020792948.html">CS229 学习笔记 Part 1</a>
</li>
<li class="post">
<a href="14883590547961.html">原始模型优化笔记</a>
</li>
<li class="post">
<a href="14863637393852.html">低素质弹幕分类器的CNN实现</a>
</li>
</ul>
</div>
</div>
<div id="site-link" class="side-item">
<div class="side-header">
<h2>Link</h2>
</div>
<div class="side-content">
<p class="link-list">
<a href="http://blog.winkidney.com/">阿毛</a>
</p>
</div>
</div>
</div><!-- sidebar -->
</div><!-- hide for small -->
</div><!-- large 4 -->
</div><!-- row -->
<div class="page-bottom clearfix">
<div class="row">
<p class="copyright">Copyright © 2016
Powered by <a target="_blank" href="http://www.mweb.im">MWeb</a>,
Theme used <a target="_blank" href="http://github.com">GitHub CSS</a>.
Modified by <a target="_blank" href="http://yinz.xyz">Yinzo</a>.</p>
</div>
</div>
</section>
</div>
</div>
<script src="asset/js/foundation.min.js"></script>
<script>
$(document).foundation();
function fixSidebarHeight(){
var w1 = $('.markdown-body').height();
var w2 = $('#sidebar').height();
if (w1 > w2) { $('#sidebar').height(w1); };
}
$(function(){
fixSidebarHeight();
})
$(window).load(function(){
fixSidebarHeight();
});
</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://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script><script type="text/x-mathjax-config">MathJax.Hub.Config({TeX: { equationNumbers: { autoNumber: "AMS" } }});</script>
<script src="asset/js/instantclick.min.js" data-no-instant></script>
<script data-no-instant>InstantClick.on('change', function() {
MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
});</script>
<script data-no-instant>InstantClick.init();</script>
</body>
</html>