-
Notifications
You must be signed in to change notification settings - Fork 5
/
23.html
759 lines (671 loc) · 34.8 KB
/
23.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
754
755
756
757
758
759
<!doctype html>
<html lang="ja">
<head>
<meta charset="utf-8">
<title>パターン認識・機械学習勉強会 第23回 @ ナビプラス </title>
<meta name="description" content="Seminar of category theory">
<meta name="author" content="Koichi Nakamura">
<meta name="apple-mobile-web-app-capable" content="yes" />
<meta name="apple-mobile-web-app-status-bar-style" content="black-translucent" />
<meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no">
<link rel="stylesheet" href="css/reveal.css">
<link rel="stylesheet" href="css/theme/beige.css" id="theme">
<meta http-equiv="X-UA-Compatible" CONTENT="IE=EmulateIE7" />
<!-- For syntax highlighting -->
<link rel="stylesheet" href="plugin/highlight/styles/github.css">
<!-- If the query includes 'print-pdf', use the PDF print sheet -->
<script>
document.write( '<link rel="stylesheet" href="css/print/' + ( window.location.search.match( /print-pdf/gi ) ? 'pdf' : 'paper' ) + '.css" type="text/css" media="print">' );
</script>
<script type="text/javascript"
src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS_HTML">
</script>
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
tex2jax: {
inlineMath: [ ['$','$'], ["\\(","\\)"] ],
displayMath: [ ['$$','$$'], ["\\[","\\]"] ]
}
});
</script>
<style type="text/css">
<!--
div.definition {
padding-left: 10px;
padding-right: 10px;
border: 4px solid #333333;
box-shadow: 0 0 10px rgba(0, 0, 0, 0.15);
}
.reveal .chapter-title {
margin-top: 3em;
}
.reveal {
font-size: 36px;
line-height: 1.4em;
}
.reveal .slides {
text-align: left;
}
.reveal section img {
border: none;
background: 0;
margin-left: 1em;
margin-right: 1em;
box-shadow: none;
}
.reveal strong {
color: #ff6666;
}
.reveal sup {
font-size: 40%;
}
.reveal .note {
font-size: 40%;
}
.reveal .controls div.navigate-up,
.reveal .controls div.navigate-down {
display: none;
}
.reveal .block {
border: solid 2px;
position: relative;
border-radius: 8px;
margin: 0.5em;
padding: 1em 0.8em 0.5em 0.8em;
}
.reveal .block:after {
content: "";
display: block;
clear: both;
height: 1px;
overflow: hidden;
}
-->
</style>
<!--[if lt IE 9]>
<script src="lib/js/html5shiv.js"></script>
<![endif]-->
</head>
<body>
<div class="reveal">
<!-- Any section element inside of this container is displayed as a slide -->
<div class="slides">
<section>
<h2>パターン認識・<br> 機械学習勉強会 <br> 第23回</h2>
<h3>@ナビプラス</h3>
<small> 中村晃一 <br> 2014年10月9日 </small>
</section>
<section>
<h3>謝辞</h3>
<p>
会場・設備の提供をしていただきました<br>
㈱ ナビプラス様<br>
にこの場をお借りして御礼申し上げます.
</p>
</section>
<section>
<p>
本日がこの勉強会シリーズの最終回となります.
</p>
<p>
本日はテキストの最後の章「モデルの結合」をやります. これまでに紹介しました学習器を複数組み合わせる事によってより複雑なデータに対する識別や回帰を行う方法を紹介します.
</p>
</section>
<section>
<h2 class="chapter-title"> 集団学習 </h2>
</section>
<section>
<p>
学習データ $\mathbf{X}$ を元に複数のモデル $f_1(\mathbf{x}),\ldots,f_M(\mathbf{x})$ を学習させ，それらの合議(多数決や平均)によって最終的な結果を求めるというアプローチを <strong> 集団学習(ensemble learning) </strong> と呼びます. 各 $f_1,\ldots,f_M$ の事を <strong> 弱学習器(weak learner)</strong> と呼びます.
</p>
<p>
用いる弱学習器の種類，弱学習器の学習方法，合議の方法などによって幾つかの手法が存在します．
</p>
<div align="center"> <img width="500px" src="fig/ensemble-learning.png"> </div>
</section>
<section>
<h3> バギング </h3>
<p>
<strong> バギング(bagging) </strong> は非常に単純な集団学習アルゴリズムです.
</p>
<p class="fragment">
バギングでは，学習データセット $\mathbf{X}$ から $M$ 個のデータセット $\mathbf{X}_1,\ldots,\mathbf{X}_M$ を <strong> ブートストラップ (bootstrap) </strong> という方法で作ります.
</p>
<p class="fragment">
そしてそれぞれ適当なモデルで学習させて $M$ 個の弱学習器 $f_1(\mathbf{x}),\ldots,f_M(\mathbf{x})$ を作り識別の場合には多数決，回帰の場合にはそれらの平均を最終的な結果とします.
</p>
</section>
<section>
<p>
同じデータセット $\mathbf{X}$ を学習させてしまったら、全ての弱学習器が全く同じものになってしまいます．ブートストラップとは元の学習データ $\mathbf{X}$ から異なる $M$ 個のデータセット $\mathbf{X}_1,\ldots,\mathbf{X}_M$ を作る方法の１つです.
</p>
<p class="fragment" data-fragment-index="1">
方法は簡単で，$m = 1,2,\ldots,M$ について $\mathbf{X}$ から重複を許して何個か($|\mathbf{X}|$個など)サンプリングしたものを $X_m$ とします.
</p>
<div align="center" class="fragment" data-fragment-index="1"> <img width="800px" src="fig/bootstrap.png"> </div>
</section>
<section style="font-size:90%">
<p>
以下のようなデータセットに対する回帰問題を用いてバギングの効果を見てみます. 青い点が訓練用，赤い点が検証用です.
</p>
<p> 弱学習器には単純な線形モデル $y=ax+b+\varepsilon$ を用いました. </p>
<div align="center"> <img width="600px" src="prog/prog23-2-1.png"> <a href="prog/prog23-2.py" style="font-size:60%">prog23-2.py</a> </div>
</section>
<section style="font-size:90%">
<p>
弱学習器の数 $M$ を変えながら，検証用セットに対する二乗誤差平均の期待値の推定値をプロットすると以下のようになります. 学習器の数を増やすと(平均的に)性能が向上していく事が分かります.
</p>
<div align="center"> <img width="600px" src="prog/prog23-2-2.png"> <a href="prog/prog23-2.py" style="font-size:60%">prog23-2.py</a> </div>
</section>
<section style="font-size:90%">
<p>
単純に平均を取っただけで何故精度が上がるのかを考えます．
</p>
<p class="fragment">
真の回帰方程式を $y=f(\mathbf{x})$ とします. $m$ 番目に学習されたモデルを
\[ f_m(\mathbf{x}) = f(\mathbf{x}) + \varepsilon_m(\mathbf{x}) \]
と表すと二乗誤差の期待値は
\[ \mathbb{E}[\{f_m(\mathbf{x}) - f(\mathbf{x})\}^2] = \mathbb{E}[\varepsilon_m(\mathbf{x})^2] \]
となります.
</p>
<p class="fragment">
すると，$M$ 個の弱学習器全体での二乗誤差の期待値の平均は
\[ E_{\mathrm{AV}} = \frac{1}{M}\sum_{m=1}^M\mathbb{E}[\varepsilon_m(\mathbf{x})^2] \]
です.
</p>
</section>
<section style="font-size:80%">
<p>
バギングによるモデルは
\[ \hat{f}(\mathbf{x}) = \frac{1}{M}\sum_{m=1}^M f_m(\mathbf{x}) \]
なので，これと真のモデルの二乗誤差の期待値は以下のようになります.
\[\begin{aligned}
E_{\mathrm{COM}} &= \mathbb{E}\left[\left\{\hat{f}(\mathbf{x})-f(\mathbf{x})\right\}^2\right] \\
&=\mathbb{E}\left[\left\{\frac{1}{M}\sum_{m=1}^M\{f(\mathbf{x})+\varepsilon_m(\mathbf{x})\}-f(\mathbf{x})\right\}^2\right] \\
&= \mathbb{E}\left[\left\{\frac{1}{M}\sum_{m=1}^M\varepsilon_m(\mathbf{x})\right\}^2\right] \\
&= \frac{1}{M^2}\mathbb{E}\left[\left\{\sum_{m=1}^M\varepsilon_m(\mathbf{x})\right\}^2\right] \\
\end{aligned} \]
</p>
</section>
<section style="font-size:80%">
<p>
ここで<a href="http://ja.wikipedia.org/wiki/%E3%82%B3%E3%83%BC%E3%82%B7%E3%83%BC%EF%BC%9D%E3%82%B7%E3%83%A5%E3%83%AF%E3%83%AB%E3%83%84%E3%81%AE%E4%B8%8D%E7%AD%89%E5%BC%8F">コーシー・シュワルツの不等式</a>から
\[ \left\{\sum_{m=1}^M\varepsilon_m(\mathbf{x})\right\}^2 \leq M\sum_{m=1}^M\varepsilon_m(\mathbf{x})^2 \]
が成り立つ事を使えば
\[ \color{red}{ E_{\mathrm{COM}} \leq E_{\mathrm{AV}} } \]
となります. つまり，平均を取って出来るモデルは個々の弱学習器の平均的な性能よりも優れているという事が分かります.
</p>
</section>
<section style="font-size:80%">
<p>
性能向上の目安ですが
\[ \mathbb{E}[\varepsilon_m(\mathbf{x})] = 0,\quad \mathrm{Cov}[\varepsilon_i(\mathbf{x}),\varepsilon_j(\mathbf{x})] = 0 \quad (i\neq j) \]
ならば
\[ E_{\mathrm{COM}} = \frac{1}{M^2}\mathbb{E}\left[\left\{\sum_{m=1}^M\varepsilon_m(\mathbf{x})\right\}^2\right] = \frac{1}{M^2}\sum_{m=1}^M\mathbb{E}\left[\varepsilon_m(\mathbf{x})^2\right] \]
が成り立つので，
\[ E_{\mathrm{COM}} = \frac{1}{M}E_{\mathrm{AV}} \]
となります. 実際には $\mathrm{Cov}[\varepsilon_i(\mathbf{x}),\varepsilon_j(\mathbf{x})] = 0$ という事はまずないので，ここまで良い精度にはなりません.
</p>
</section>
<section style="font-size:80%">
<h3> ブースティング </h3>
<p>
<strong> ブースティング (boosting) </strong> と呼ばれる手法は，$M$ 個の弱学習器を順番に学習し，前の弱学習器の学習結果を次の弱学習器の学習で利用する事で積極的に性能をあげようとするものです. <strong> AdaBoost (Adaptive Boosting) </strong> というアルゴリズムが有名です.
</p>
<p>
バギングと異なり個々の学習器は対等ではないので，重み付きでの多数決・平均値を取ります.
</p>
<div align="center"> <img width="400px" src="fig/boosting.png"> </div>
</section>
<section style="font-size:90%">
<p>
AdaBoostでは，<strong> 重み付き誤差関数(weighted error function)</strong> を用いて学習セットに色を付けます.
</p>
<p>
つまり, モデル $\hat{f}$ の誤差を各データ $(\mathbf{x}_n,t_n)$ 毎に重み $w_n$ を付与した
\[ \sum_{n=1}^N w_n E(\hat{f}(\mathbf{x}_n), t_n) \]
で計算します.
</p>
<p class="fragment">
識別の場合は単純損失関数などを用います. この場合 $E(y,t) = (\text{正解なら $0$, そうでなければ $1$})$ とします.
</p>
</section>
<section style="font-size:90%">
<p>
$f_m$ が識別に失敗したデータには大きな重みを付与して次の $f_{m+1}$ ではそれらをより良く識別しようというのがAdaBoostの考え方です.
</p>
<div align="center"> <img width="500px" src="fig/adaboost.png"> </div>
</section>
<section style="font-size:60%">
<div class="block" style="border-color:blue">
<h4 style="color:blue"> AdaBoost(単純損失を用いた識別問題の場合) </h4>
<ol>
<li> 重みを $w_n = 1/N$ で初期化. </li>
<li> $m=1,\ldots,M$ について以下を繰り返す.
<ol>
<li> 以下を最小化する事により弱学習器 $f_m$ を構築
\[ \sum_{n=1}^N w_n E(f_m(\mathbf{x}_n), t_n) \] </li>
<li>
重み付きの誤差平均
\[ \varepsilon_m = \frac{\sum_{n=1}^Nw_n E(f_m(\mathbf{x}_n), t_n)}{\sum_{n=1}^N w_n} \]
を元に，合議の際の重みを
\[ \alpha_m = \log\left(\frac{1-\varepsilon_m}{\varepsilon_m}\right) \]
とする.
</li>
<li>
重みを更新
\[ w_n \leftarrow w_n \exp\left\{\alpha_m E(f_m(\mathbf{x}_n),t_n)\right\} \]
</li>
</ol>
</li>
<li>
重み付きで多数決を取る.
\[ \hat{f}(\mathbf{x}) = \mathrm{sign}\left(\sum_{m=1}^M\alpha_m f_m(\mathbf{x})\right) \]
</li>
</ol>
</div>
</section>
<section style="font-size:90%">
<p>
AdaBoostは <strong> 指数損失関数 (exponential error function) </strong>
\[ E(y,t) = \exp(-ty) \]
を用いた経験損失
\[ J = \sum_{n=1}^N\exp\left\{-t_nf_m(\mathbf{x}_n)\right\} \]
を反復法を用いて最小化するアルゴリズムであると解釈する事が出来ます。
</p>
<div align="center"> <img width="400px" src="fig/exponential-error-function.png"> </div>
</section>
<section style="font-size:90%">
<p>
ここで $f_m(\mathbf{x})$ のモデルとして弱学習器 $g_\ell(\mathbf{x})$ の線形結合
\[ f_m(\mathbf{x}) = \frac{1}{2}\sum_{\ell=1}^m \alpha_\ell g_\ell(\mathbf{x}) \]
で表される物を考えます. $1/2$ は計算を簡単にする為のものです.
</p>
<p>
弱学習器 $g_\ell(\mathbf{x})$ は $\{-1, 1\}$ のいずれかを返す二値の識別器とします.
従って $\mathrm{sign}(f_m(\mathbf{x}))$ は $g_\ell$ の結果の重み付きの多数決を表します.
</p>
</section>
<section style="font-size:80%">
<p>
すると
\[ f_m(\mathbf{x}) = f_{m-1}(\mathbf{x}) + \frac{1}{2}\alpha_m g_m(\mathbf{x}) \]
より
\[ \begin{aligned}
J &= \sum_{n=1}^N\exp\left\{-t_nf_{m-1}(\mathbf{x}_n)-\frac{1}{2}t_n\alpha_m g_m(\mathbf{x}_n)\right\}\\
&= \sum_{n=1}^N w_n\exp\left\{-\frac{1}{2}t_n\alpha_m g_m(\mathbf{x}_n)\right\}
\end{aligned} \]
となります. 但し
\[ w^{(m)}_n \stackrel{\mathrm{def}}{=} \exp\left\{-t_nf_{m-1}(\mathbf{x}_n)\right\} \]
であり，$g_1,\ldots,g_{m-1},\alpha_1,\ldots,\alpha_{m-1}$ を固定して $g_m,\alpha_m$ だけを動かす場合にはこれは定数となります.
</p>
</section>
<section style="font-size:80%">
<p>
ここで $g_m(\mathbf{x})$ が $\mathbf{x}_n$ を正しく識別したときは $t_ng_m(\mathbf{x}_n)=1$，そうでない時は $t_ng_m(\mathbf{x}_n)=-1$ となるので
\[ J= \left(e^{\alpha_m/2}-e^{-\alpha_m/2}\right)\sum_{n=1}^Nw_n^{(m)}E(g_m(\mathbf{x}_n), t_n) + e^{-\alpha_m/2}\sum_{n=1}^Nw_n^{(m)} \]
と書くことが出来ます。よってこれを最小化する $g_m$ は経験的単純損失
\[ \sum_{n=1}^Nw_n^{(m)}E(g_m(\mathbf{x}_n), t_n) \]
を最小化するものであり，
</p>
</section>
<section style="font-size:80%">
<p>
ここで
\[ \varepsilon_m = \frac{\sum_{n=1}^Nw^{(m)}_n E(g_m(\mathbf{x}_n), t_n)}{\sum_{n=1}^N w^{(m)}_n} \]
と置くと
\[ J = \left(e^{\alpha_m/2}-e^{-\alpha_m/2}\right)\varepsilon_m\sum_{n=1}^N w_n + e^{-\alpha_m/2}\sum_{n=1}^Nw_n^{(m)} \]
となるので，$J$ を最小化する $\alpha_m$ は
\[ (e^{\alpha_m/2}-e^{-\alpha_m/2})\varepsilon_m + e^{-\alpha_m/2} \]
を最小化する
\[ \alpha_m = \log\frac{1-\varepsilon_m}{\varepsilon_m} \]
となります.
</p>
</section>
<section style="font-size:80%">
<p>
最後に重み $w_n$ の更新規則は
\[ \begin{aligned}
w_n^{(m+1)} &= \exp\{-t_nf_m(\mathbf{x}_n)\}\\
&= \exp\{-t_n\left(f_{m-1}(\mathbf{x}_n)+\alpha_mg_m(\mathbf{x}_n)/2\right)\}\\
&= w_n^{(m)}\exp\{-t_n\alpha_mg_m(\mathbf{x}_n)/2\}
\end{aligned} \]
と
\[ t_ng_m(\mathbf{x}_n)= 1 - 2E(g_m(\mathbf{x}_n),t_n) \]
より
\[ \begin{aligned}
w_n^{(m+1)} &= w_n^{(m)}\exp\{\alpha_mE(g_m(\mathbf{x}_n),t_n)\}\exp(-\alpha_m/2)
\end{aligned} \]
となります. $\exp(-\alpha_m/2)$ の部分はデータ $(\mathbf{x}_n,t_n)$ によらない定数で，$f_m$ の符号には影響しないため除去しても良いです.
</p>
</section>
<section>
<p>
以上の「弱学習器の線形和モデルで指数損失を反復的に最小化する」というアイデアに基づけば、様々なブースティングアルゴリズムの拡張を導出する事が出来ます.
</p>
<p>
例えばAdaBoostを回帰に用いる例は以下の論文などで紹介されています.
</p>
<ul style="font-size:80%">
<li>
Freund, Yoav, and Robert E. Schapire. "A desicion-theoretic generalization of on-line learning and an application to boosting." Computational learning theory. Springer Berlin Heidelberg, 1995.
</li>
</ul>
</section>
<section style="font-size:70%">
<p>
そもそも「指数損失の最小化」とは一体どういう事なのか補足します.
</p>
<p>
経験損失ではなく期待損失は
\[ \mathbb{E}[\exp(-tf(\mathbf{x}))] = \sum_{t=1,-1}\int \exp(-tf(\mathbf{x}))p(t|\mathbf{x})p(\mathbf{x})\mathrm{d}\mathbf{x} \]
となりますが，これを最小とする $f$ を変分法で求めると(次頁)
\[ f(\mathbf{x}) = \frac{1}{2}\log \frac{p(t=1|\mathbf{x})}{p(t=-1|\mathbf{x})} \]
となります. これは <strong> 対数オッズ(log odds) </strong> や <strong> ロジット (logit) </strong> と呼ばれる量(割る2)になっています.
</p>
</section>
<section style="font-size:60%">
<p>
【前頁の導出】<br>
$f$ に微小変化 $\varepsilon \eta(\mathbf{x})$ を加えると
\[\sum_{t=1,-1}\int \exp\{-t(f+\varepsilon \eta)\}p(t|\mathbf{x})p(\mathbf{x})\mathrm{d}\mathbf{x} \]
これを $\varepsilon$ で微分すると
\[\sum_{t=1,-1}\int \exp(-t\eta)\exp\{-t(f+\varepsilon \eta)\}p(t|\mathbf{x})p(\mathbf{x})\mathrm{d}\mathbf{x} \]
となりこれが $\varepsilon=0$ で $0$ となる条件を求めれば良い.
\[-\sum_{t=1,-1}\int t\eta\exp(-tf)p(t|\mathbf{x})p(\mathbf{x})\mathrm{d}\mathbf{x} = 0 \]
$\eta(\mathbf{x})$ は任意に取れるのでこれが $0$ になるためには
\[\sum_{t=1,-1}t \exp(-tf)p(t|\mathbf{x})p(\mathbf{x}) = 0 \]
が必要. これを解いて
\[ f(\mathbf{x}) = \frac{1}{2}\log \frac{p(t=1|\mathbf{x})}{p(t=-1|\mathbf{x})} \]
</p>
</section>
<section>
<h2 class="chapter-title"> 決定木 </h2>
</section>
<section style="font-size:90%">
<h3> 決定木 </h3>
<p>
集団学習とは異なる学習器の組み合わせ方として <strong> 決定木 (decision tree) </strong> というものも使われます.
</p>
<p>
決定木とは2つの識別器 $f_1(\mathbf{x})$ と $f_2(\mathbf{x})$ のどちらを使うのかを他の識別器 $g(\mathbf{x})$ で選び，選ばれたもので識別を行うというものです.
</p>
<div align="center"> <img width="300px" src="fig/decision-tree1.png"> </div>
</section>
<section style="font-size:90%">
<p>
$f_1,f_2$ に再び決定木を用いれば下図のような木構造の識別器となります.
</p>
<div align="center"> <img width="50%" src="fig/decision-tree.png"> </div>
</section>
<section>
<p>
決定木は特徴空間を再帰的に幾つかの領域に分割し，各領域毎に別々の学習で回帰や識別を行うというものです.
</p>
<p>
下図のようにある軸，もしくは数本の軸に平行な面で分割していく方法が一般的です.
</p>
<div align="center"> <img width="800px" src="fig/decision-tree2.png"> </div>
</section>
<section>
<p>
例えば下図の様に途中で不連続的にパターンが変化するようなデータに対しても
</p>
<div align="center"> <img width="600px" src="prog/prog23-3-1.png"> <a href="prog/prog23-3.py" style="font-size:60%">prog23-3.py</a> </div>
</section>
<section>
<p>
以下のように領域を分割して個別に回帰を行うという事が出来ます.
</p>
<div align="center"> <img width="600px" src="prog/prog23-3-2.png"> <a href="prog/prog23-3.py" style="font-size:60%">prog23-3.py</a> </div>
</section>
<section>
<p>
分割された個々の領域毎の学習はこれまでに紹介しましたいろいろな方法をそのまま使えば良いので，決定木の学習は木構造の学習が中心になります.
</p>
<p>
決定木を構築する場合には領域を再帰的に分割する事を繰り返していきますので，
</p>
<ol>
<li> 領域を分割する基準 </li>
<li> 分割を停止する基準 </li>
</ol>
<p>
が必要です. これらの選択によって様々なアルゴリズムを考える事が出来ます.
</p>
</section>
<section>
<p>
決定木の構造は離散的なものなので解析的にその構造を学習する事は難しいです. 従いまして <strong> 貪欲法(greedy algorithm)</strong> などが用いられます.
</p>
<div align="center"> <img width="500px" src="fig/decision-tree3.png"> </div>
</section>
<section style="font-size:90%">
<h3> 分割基準 </h3>
<p>
「最も良く分割する」という基準も幾つか考え方がありますが，<strong> 相互情報量 (mutual information) </strong> などが使われます.
</p>
<p class="fragment">
二つの確率変数 $\mathbf{X}_1,\mathbf{X}_2$ に対する相互情報量は
\[ I(\mathbf{X}_1,\mathbf{X}_2) = \sum_{\mathbf{x}_1\in\mathbf{X}_1,\mathbf{x}_2\in\mathbf{X}_2}p(\mathbf{x}_1,\mathbf{x}_2)\log \frac{p(\mathbf{x}_1,\mathbf{x}_2)}{p(\mathbf{x}_1)p(\mathbf{x}_2)} \]
で定義され，これは $\mathbf{X}_2$ を知ることで $\mathbf{X}_1$ に関して得る情報量と解釈する事が出来ます.
</p>
<p class="fragment">
これを用いて，分割を行う事によってクラスの割り当てに関して得る情報量を測る事が出来ます. (授業当日ではこの点について誤った説明をしてしまいました.)
</p>
</section>
<section>
<h3> 停止基準 </h3>
<p>
分割を停止する際に考慮すべき事は
</p>
<ol>
<li> 十分な識別精度を達成出来るほど細かいか？ </li>
<li> サンプル数が少なくなりすぎていないか？ </li>
</ol>
<p>
という２点です. これらはトレードオフの関係にあります.
</p>
</section>
<section>
<p>
そこで，もともとの空間が $T$ 個の領域に分割されたとし， $Q_t(T)\quad (t=1,\ldots,T)$ を $t$ 番目の領域 $t$ における誤差の和とした際に
\[ C(T) = \sum_{t=1}^TQ_t(T) + \lambda T \quad (\lambda > 0)\]
という量を停止基準のしきい値として用いる事が出来ます.
</p>
<p>
$\lambda T$ は分割が細かくなりすぎることに対するペナルティ項です.
</p>
</section>
<section style="font-size:80%">
<p>
回帰の場合には $Q_t(T)$ として残差平方和などを用いれば良いです.
</p>
<p>
一方，識別の場合にはノード $t$ がクラス $k$ に所属する確率を $p(k|t)$ とした場合に交差エントロピー
\[ Q_t(T) = \sum_{k=1}^Kp(k|t)\log p(k|t) \]
や <strong> Giniインデックス (Gini index) </strong>
\[ Q_t(T) = \sum_{k=1}^K p(k|t)(1-p(k|t)) \]
を用います. これらは $p(k|t)=0$ は $p(k|t)=1$ となる $k$ が存在した場合に $0$ になります. ノード $t$ のデータが1つのクラスに対応する場合にはそれ以上分割する必要がないというわけです.
</p>
</section>
<section>
<h3> ランダムフォレスト </h3>
<p>
<strong> ランダムフォレスト (random forest) </strong> という手法は新しいのでPRML本では説明がないですが非常に精度が高く有名です.
</p>
<p>
これは弱学習器として決定木を用いて集団学習を行うアルゴリズムです. 弱学習器の学習にはブートストラップで生成したサンプルを利用する為，並列に学習を行わせる事が可能です.
</p>
</section>
<section>
<h3> まとめ </h3>
<p>
では最後にPRML本の各章で学んだ事を振り返りたいと思います.
</p>
</section>
<section>
<h3> 第3・4章 </h3>
<p>
線形回帰モデル・線形識別モデルという話題を扱いました.
</p>
<p>
学習データを $\mathbf{x}$，それの基底変換関数を $\Psi$ として
\[ y = f(\mathbf{w}^T\Psi(\mathbf{x})) \]
の形で表されるものを扱いました.
</p>
</section>
<section>
<p>
線形モデルは解析的に取り扱える物が多く，他の全ての手法の基礎となるモデルです.
</p>
<p>
識別問題については特にロジスティックモデルが重要です.
\[ y = \frac{1}{1 + \exp(\mathbf{w}^T\Psi(\mathbf{x})}) \]
</p>
</section>
<section>
<h3> 第5章 </h3>
<p>
ニューラルネットワークの紹介をしました.
</p>
<div align="center"> <img width="500px" src="fig/neural-network.png"> </div>
</section>
<section>
<p>
ニューラルネットワークは隠れ層が十分にある場合，任意の連続な非線形関数を表現出来るという極めて重要な特徴がありました.
</p>
<p>
その学習には誤差逆伝播法という手法を用います.
</p>
</section>
<section>
<h3> 第6,7章 </h3>
<p>
カーネル法という手法の紹介を行いました.
</p>
<p>
カーネル法は特徴ベクトル $\Psi(\mathbf{x})$ を明示的に扱う代わりに，その内積 $\Psi(\mathbf{x}_i)^T\Psi(\mathbf{x}_j)$ やそれを一般化したカーネル関数
\[ k(\mathbf{x}_i,\mathbf{x}_j) \]
をプリミティブとして用いる手法です. カーネル法では複雑な特徴ベクトルを用いても計算量がデータ数 $N$ のみに依存するようにする事が出来ます. 特に無限次元の特徴ベクトルを用いる事が出来ます.
</p>
<p>
一方で識別関数を構築する為には基本的に学習データを全て保持しておく必要があります。
</p>
</section>
<section>
<p>
カーネル法を用いる最も重要な識別器はサポートベクターマシンです。
</p>
<p>
これはマージン最大化という考え方によって，汎化性能を高める仕組みがあらかじめ内包されたモデルで非常に使い勝手が良いです。
</p>
<p>
また，識別器の構築にサポートベクターしか必要ないという大きな特徴があり，保持すべき学習データ数を減らす事が可能になります.
</p>
</section>
<section>
<h3> 第8章 </h3>
<p>
グラフィカルモデルという確率モデルの表現方法を紹介しました.確率変数間の因果関係をグラフ構造を用いて表現する事により，他のモデルも含む非常に広範なモデルを表現する事が出来ます.
</p>
<p>
有向グラフを用いるベイジアンネットワークや無向グラフを用いるマルコフ確率場などを紹介しました.
</p>
<div align="center"> <img width="300px" src="fig/bayesian-network1.png"> </div>
</section>
<section>
<p>
グラフィカルモデルの学習には変数消去法やメッセージパッシングなどの方法を用います. これは根と葉の間でメッセージを一回伝播させるだけで，全てのクラスタに対する同時確率を求める事が出来てしまうというものです.
</p>
<div align="center"> <img width="800px" src="fig/message-passing2.png"> </div>
</section>
<section>
<h3> 第9, 10章 </h3>
<p>
教師なし学習のタスクの１つであるクラスタリングやディリクレ配分問題のアルゴリズムを紹介しました.
</p>
<p>
これらの問題は隠れ変数を持つモデルを用いて解く事が出来，厳密な反復解法であるEM法や近似解法である変分ベイズ法，ギブスサンプリングなどの紹介をしました.
</p>
</section>
<section>
<h3> 第11章 </h3>
<p>
ランダムサンプリング，特にマルコフ連鎖モンテカルロ法の一種であるメトロポリスヘイスティングス法を紹介しました.
</p>
<p>
非常に高次元の変数に対する期待値の計算，積分の計算などを効率的に解く為にはサンプリングベースの方法が必要になります.
</p>
<div align="center"> <img width="500px" src="prog/fig3-9-1.png"> </div>
</section>
<section>
<h3> 第12章 </h3>
<p>
高次元の空間内でのデータが比較的低次元の多様体上にしか分布していないというケースは非常に良く有ります.
</p>
<p>
そういったデータに対しては次元削減や多様体学習などの手法を用いた変換が有効です. 具体的なアルゴリズムとしては主成分分析のみを紹介しました.
</p>
</section>
<section style="font-size:90%">
<h3> 第13章 </h3>
<p>
系列データの確率モデルの１つである隠れマルコフモデルを紹介しました. 観測データの系列の裏に隠れ変数の一次の系列を考える事によって，モデルの複雑さの増加を抑えつ，任意の離れた観測データ間の相関を表現出来るように工夫したものです.
</p>
<p>
パラメータの学習には前向き後ろ向きアルゴリズム，パラメータを既知とした隠れ変数の推定にはビタビアルゴリズムを用います.
</p>
<div align="center"> <img width="500px" src="fig/hmm.png"> </div>
</section>
<section>
<h3> 第14章 </h3>
<p>
弱学習器を組み合わせて１つでは達成出来ない性能を持つ学習器を作り上げる集団学習・決定木という手法を紹介しました.
</p>
<p>
１つの非常に複雑な学習器を用いると過学習や計算コストの増加の問題が生じます. 集団学習には多数の弱い学習器の結果を平均化する事によって過学習を抑制する効果があり，またバギングなどは並列化を容易に行う事が出来ます.
</p>
</section>
<section>
<h3> 以上でこの勉強会を終了します. </h3>
<p>
全23回お疲れ様でした. 数学的な部分の説明が殆どでしたが，実際のデータの分析では理論通りには上手くはいかない事が多数ありますので，まずは実際にやってみるという事が大事だと思います. 何か困難な問題にぶつかった時には，数学的な理解がその解決に役に立つと思います.
</p>
<p>
資料の不足や不備が多数あり大変申し訳ありませんでした. 資料は今後も随時更新していきます.
</p>
</section>
</div>
</div>
<script src="lib/js/head.min.js"></script>
<script src="js/reveal.min.js"></script>
<script>
// Full list of configuration options available here:
// https://github.com/hakimel/reveal.js#configuration
Reveal.initialize({
controls: false,
progress: true,
history: true,
center: true,
rollingLinks: false,
theme: Reveal.getQueryHash().theme, // available themes are in /css/theme
transition: Reveal.getQueryHash().transition || 'none', // default/cube/page/concave/zoom/linear/fade/none
// Optional libraries used to extend on reveal.js
dependencies: [
{ src: 'lib/js/classList.js', condition: function() { return !document.body.classList; } },
{ src: 'plugin/markdown/showdown.js', condition: function() { return !!document.querySelector( '[data-markdown]' ); } },
{ src: 'plugin/markdown/markdown.js', condition: function() { return !!document.querySelector( '[data-markdown]' ); } },
{ src: 'plugin/highlight/highlight.js', async: true, callback: function() { hljs.initHighlightingOnLoad(); } },
{ src: 'plugin/zoom-js/zoom.js', async: true, condition: function() { return !!document.body.classList; } },
{ src: 'plugin/notes/notes.js', async: true, condition: function() { return !!document.body.classList; } }
// { src: 'plugin/search/search.js', async: true, condition: function() { return !!document.body.classList; } }
// { src: 'plugin/remotes/remotes.js', async: true, condition: function() { return !!document.body.classList; } }
]
});
Reveal.addEventListener( 'slidechanged', function( event ) {
MathJax.Hub.Rerender(event.currentSlide);
});
</script>
</body>
</html>