<div>
<style>
/* basic design */
.reveal h1, .reveal h2, .reveal h3, .reveal h4, .reveal h5, .reveal h6,
.reveal section, .reveal table, .reveal li, .reveal blockquote, .reveal th, .reveal td, .reveal p {
font-family: 'Meiryo UI', 'Source Sans Pro', Helvetica, sans-serif, 'Helvetica Neue', 'Helvetica', 'Arial', 'Hiragino Sans', 'ヒラギノ角ゴシック', YuGothic, 'Yu Gothic';
text-align: left;
line-height: 1.6;
letter-spacing: normal;
text-shadow: none;
word-wrap: break-word;
color: #444;
}
.reveal h1, .reveal h2, .reveal h3, .reveal h4, .reveal h5, .reveal h6 {font-weight: bold;}
.reveal h1, .reveal h2, .reveal h3 {color: #2980b9;}
.reveal th {background: #DDD;}
.reveal section img {background:none; border:none; box-shadow:none; max-width: 95%; max-height: 95%;}
.reveal blockquote {width: 90%; padding: 0.5vw 3.0vw;}
.reveal table {margin: 1.0vw auto;}
.reveal code {line-height: 1.2;}
.reveal p, .reveal li {padding: 0vw; margin: 0vw;}
.reveal .box {margin: -0.5vw 1.5vw 2.0vw -1.5vw; padding: 0.5vw 1.5vw 0.5vw 1.5vw; background: #EEE; border-radius: 1.5vw;}
/* table design */
.reveal table {background: #f5f5f5;}
.reveal th {background: #444; color: #fff;}
.reveal td {position: relative; transition: all 300ms;}
.reveal tbody:hover td { color: transparent; text-shadow: 0 0 3px #aaa;}
.reveal tbody:hover tr:hover td {color: #444; text-shadow: 0 1px 0 #fff;}
/* blockquote design */
.reveal blockquote {
width: 90%;
padding: 0.5vw 0 0.5vw 6.0vw;
font-style: italic;
background: #f5f5f5;
}
.reveal blockquote:before{
position: absolute;
top: 0.1vw;
left: 1vw;
content: "\f10d";
font-family: FontAwesome;
color: #2980b9;
font-size: 3.0vw;
}
/* font size */
.reveal h1 {font-size: 5.0vw;}
.reveal h2 {font-size: 4.0vw;}
.reveal h3 {font-size: 2.8vw;}
.reveal h4 {font-size: 2.6vw;}
.reveal h5 {font-size: 2.4vw;}
.reveal h6 {font-size: 2.2vw;}
.reveal section, .reveal table, .reveal li, .reveal blockquote, .reveal th, .reveal td, .reveal p {font-size: 2.2vw;}
.reveal code {font-size: 1.6vw;}
/* new color */
.red {color: #EE6557;}
.blue {color: #16A6B6;}
/* split slide */
#right {left: -18.33%; text-align: left; float: left; width: 50%; z-index: -10;}
#left {left: 31.25%; text-align: left; float: left; width: 50%; z-index: -10;}
</style>
<style>
/* specific design */
.reveal h2 {
padding: 0 1.5vw;
margin: 0.0vw 0 2.0vw -2.0vw;
border-left: solid 1.2vw #2980b9;
border-bottom: solid 0.8vw #d7d7d7;
}
</style>
</div>
<!-- --------------------------------------------------------------------------------------- -->
# chapter 02: A Gentle Start
<br>
<br>
#### 2020-MM-DD
### @ningensei848
<!-- preamble -->
$$
\newcommand{\argmin}{\mathop{\rm arg~min}\limits}
$$
---
## 紳士的に始める
比較的単純な設定をもとに，学習がどのように成功するか見ていく．
これと並行して，数学的な解析を行なう．
---
## 単純な設定: パパイヤの美味しさ推定
ある無人島に漂着してしまい、何かを食べて生きていかねばならない状況を考える
> この島にはパパイヤが実っていることが分かったが、いったいこの中からどのようなパパイヤを食べればいいのだろうか？
「色」と「硬さ」に注目すればよさそうだと仮定しよう．つまり，
- パパイヤの色
- パパイヤの硬さ
という入力情報だけをもとに，「パパイヤの美味しさ」を推測するタスクを設計する．
---
## 2.1 Formal Model
#### the Statistical Learning Framework
学習を達成しうる形式的なモデルを記述するために，以下の五つに分けて考える．
1. 学習器への入力
- ドメイン集合
- ラベル集合
- 訓練データ集合
2. 学習器の出力
3. （単純な）データ生成モデル
4. 学習の成否を測る指標
5. 学習器が利用可能な情報に関する注意
---
## 1. 学習器への入力
本書で記述する統計学的な学習モデルの基礎的な設定においては，学習器は以下の三つの情報が利用可能である．
1. ドメイン集合
2. ラベル集合
3. 訓練データ集合
---
## 1. 学習器への入力: ドメイン集合
任意の集合 $\cal{X}$ で表され，これは「ラベリングされてほしい」オブジェクトが集まって構成される．
- パパイヤの例でいえば，「島の至る所にあるパパイヤすべて（ただしそれが美味しいかどうかは不明）」の集合．
- たいていは，ドメイン（ここではパパイヤ）の特徴量のベクトルとしてあらわされる．
ドメイン集合から抜き出してきた点を「インスタンス（実現値？）」と呼び，それが集まってできる “実測値の集合” を $\cal{X}$ と呼ぶ
---
## 1. 学習器への入力: ラベル集合
$\cal{Y}$ はドメイン集合が取りうるすべてのラベルの集合
（ $\{ 0, 1 \}$ や $\{ -1, 1 \}$ などがよく使われるが，いまの議論においては二つに制限しておく）
- パパイヤの場合、0: 不味い, 1: 美味しい として表現するのが妥当といえる
---
## 1. 学習器への入力: 訓練データ集合
$S \colon \; \cal{X} \times \cal{Y}$ は， *instance space* $\cal{X}$ と ラベル集合 $\cal{Y}$ との直積であらわされる列である．
→ ラベリングされたドメイン点の集合のこと
$$
S = \left( \left( x_1, y_1 \right) \; \ldots \; \left( x_m, y_m \right) \right)
$$
これらをラベル付き訓練サンプルデータと呼び，その集合である $S$ を訓練データセットと呼ぶ．
---
## 2. 学習器の出力
学習器には，予測の法則 $h \; \colon \; \cal{X} \rightarrow \cal{Y}$ を出力してほしい．
→ この関数は「予測器」「仮説」「分類器」とも呼ばれ，ドメイン集合からの観測点への新たなラベル付けに使われる．
<br>
※ $A(S)$ という記法で仮説を表すとき，訓練データ $S$ を引数として受け取るアルゴリズム $A$ が返す値が仮説である．
---
## 3. （単純な）データ生成モデル
インスタンス点群 $\cal{X}$ がいくつかの確率分布 $\cal{D}$ に沿って生成されたものと仮定する．
ただし，学習器はこの分布について何も知らないものとする．
==$\cal{X}$ の各点に "正しく" ラベリングする関数を $f$ とすると，$f \; \colon \; \cal{X} \rightarrow \cal{Y}$ であり，すべての $i$ について $y_i = f(x_i)$ となる．==
### まとめ
訓練データセット $S$ に含まれるそれぞれのペアは
- 任意の確率分布 $\cal{D}$ でドメイン集合からサンプリングされる $x_i$
- それをラベリング関数 $f$ でラベル付けしたもの ( $y_i$ )
の二つから構成される．
---
## 4. 学習の成否を測る指標 (1/4)
「分類のエラー」 $error \; of \; a \; classifier$ を確率として定義する．
これは，前述の確率分布をもとにして生成されたランダムなデータ点群に対して，正しく予測ラベルを付けられなかった場合の確率である．
つまり，仮説 $h$ がエラーとなる確率は $h(x)$ で表され，$h(x) \neq f(x)$ である．
真の写像 $f \colon \cal{X} \rightarrow \cal{Y}$ と比較して，ある確率分布 $\cal{D}$ をもとにして抽出されたインスタンス $x$ については，すべて "ただしく" ラベリングはできない．
---
## 4. 学習の成否を測る指標 (2/4)
形式的に言えば，ドメイン集合の部分集合として $A$ が与えられたとき，そこから実現値を確率分布 $\cal{D}$ で抽出する関数を ${\cal{D}}(A)$ とする．
これは，$x \in A$ がどれくらい観測されそうであるか，を決めることになる．
多くの場合，$A$ を何らかの事象とし，関数 $\pi \colon \cal{X} \rightarrow \{ 0, 1 \}$ として表現する．
すなわち，
$$
A = \{ x \in {\cal{X}} \colon \pi (x) = 1 \}
$$
※ $\pi (x) = 1$ となるような $x \in \cal{X}$ の集合が $A$ である（集合の内包的表記）
---
## 4. 学習の成否を測る指標 (3/4)
このとき， $\mathbb{P}_{x \sim {\cal{D}}} \left[ \pi (x) \right]$ のように関数 ${\cal{D}}(A)$ を表す．
<br>
これにより，予測ルール $h \colon \cal{X} \rightarrow \cal{Y}$ を以下のように定義する．
$$
\begin{eqnarray}
L_{{\cal{D}}, f}(h)
&\stackrel{\mathrm{def}}{=}&
\underset{x \sim {\cal{D}}}{\mathbb{P}} \left[ h(x) \neq f(x) \right] \\
&\stackrel{\mathrm{def}}{=}&
{\cal{D}} \left( \{ x \colon h(x) \neq f(x) \} \right)
\end{eqnarray}
$$
---
## 4. 学習の成否を測る指標 (4/4)
仮説 $h$ のエラーは，$h(x) \neq f(x)$ となるよな実現値 $x$ を無作為に抽出される確率であらわされる．
$L_{{\cal{D}}, f}(h)$ の ${\cal{D}}, f$ はそれぞれ確率分布 $\cal{D}$，真のラベリング関数 $f$ に関してエラーが測定されることを示している．
- このような関数を，*Generalization Error* とか *risk* と呼ぶ．
- 文脈から明らかな場合は，この表記を省略する．
- $L$ を使うのは，これをのちに学習器の ++損失（*loss*）++ として用いるからである．
---
## 5. 学習器が利用可能な情報に関する注意
- 学習器は確率分布 $\cal{D}$ ，およびラベリング関数 $f$ について関知しない．
- パパイヤの例でいえば，見たこともない島にあるパパイヤの発生分布やら，どうやってその美味しさを予測するのかなどについて全くわからないことと同じである．
- 学習器がデータの分布を知るためにできる唯一のことは，訓練データセットを観察することだけである．
---
## 経験的リスク最小化法
#### *Empirical Risk Minimization*
これまで見てきたように，学習アルゴリズムは ++*訓練データセット $S$ を受け取って，それに依存して*++ 予測器 $h_S \colon \cal{X} \rightarrow \cal{Y}$ を出力すべきだ．
> 訓練データセットは未知の確率分布 $\cal{D}$ によってサンプリングされ，いくつかの未知のラベリング関数 $f$ によってラベル付けされる
この学習アルゴリズムの目標は，未知の ${\cal{D}} , f$ に関してエラーが最小化される仮説 $h_S$ を見つけ出すことである．
しかし， ++${\cal{D}} , f$ が未知であるため++ に，学習器は ==真のエラーを**直接**求めることはできない．==
---
## *training error*
==${\cal{D}} , f$ が未知であっても，代わりに $training \; error$ を計算すればよい．==
$$
L_S(h) \stackrel{\mathrm{def}}{=} \frac{\left| \{ i \in [m] \colon h(x_i) \neq y_i \} \right|}{m}, \; \; ({\rm{where}} \; [m] = \{ 1, \ldots , m\})
$$
これは，「経験的エラー」とか「経験リスク」と呼ばれる．
---
## *ERM* : 経験リスク最小化法
訓練データとは学習器が観測可能な世界の写しであることから，そのようなデータにおいてもよく機能する解決手法を探すことには意義がある．
<br>
このような "あるエラー $L_S(h)$ を最小化するような予測器 $h$ を追い求めていくやり方" を「経験リスク最小化法」，或いは単に ++*ERM*++ と呼ぶ．
---
## 2.2.1 なにかうまくいかないことも
#### 過学習: *overfitting*
*ERM* ルールはとても自然なように思えるけれども，注意せずにいるとみじめに失敗してしまうかもしれない．
パパイヤの色と硬さをもとにその味を予測する学習タスクに戻って考えてみる．
---
## 過学習: 例から考える (1/3)
- 確率分布 $\cal{D}$ で生成されたインスタンス点群は灰色のBOX内部に一様に分布
- ラベリング関数 $f$ は破線であらわされたBOXの内外で各インスタンス点群を 1 か 0 かに分類する
<div align="center">
<img src="https://i.imgur.com/ojxq5ws.png" title="predictionBox" width="300">
</div>
---
## 過学習: 例から考える (2/3)
次の予測器を考えてみる．
$$
L_S(x) =
\begin{cases}
y_i & {\rm{if}} \; \exists i \in [m] \; {\rm{s.t.}} \; x_i = x \\ \\
0 & \rm{otherwise}
\end{cases}
$$
すべての $i \in [m]$ について $x_i = x$，これはつまり，訓練データのどのサンプルをとっても $L_S(h_S) = 0$ （エラーがゼロになる） ということ．
→ この予測器が（優先的に） *ERM* ルール によって選ばれる．
<!-- 0よりも小さなエラーを出せる予測器はほかに存在しないため，必然的にこの予測器が採用される -->
---
## 過学習: 例から考える (3/3)
一方で，現実の世界に実際に存在する真のエラーの割合は $1/2$ を占めている．
よって，実測したエラーは $L_{\cal{D}} (h_S) = 1/2$ で表される．
<br>
つまり，訓練データセットにおいてはエラーを0にする性能を発揮する一方で，実世界データにおいては半分以上間違える「貧弱な」学習器になってしまう．
→ 過学習: $Overfitting$ と呼ぶ．
---
## 「誘導的バイアスを伴う」ような経験的リスク最小化法
どうにかして *ERM* が過学習しない状況を探す．つまり，
- 訓練データ
- 実世界におけるデータ
++どちらにも良い性能を発揮する予測器++ があるような状況を探す．
---
## 仮説クラス $\cal{H}$
ありふれた解決方法は、限られた空間にのみ *ERM* ルールを適用すること．
形式的に言えば、「訓練データを見る前に」 ++予測 $h$ の集合 $\cal{H}$ を選んでしまうこと++ である．
<br>
これを仮説クラス $\cal{H}$ と呼ぶ．
---
## 小さなエラーをもつように
仮説クラス $\cal{H}$ に含まれるそれぞれの予測 $h$ は，$\cal{X}$ から $\cal{Y}$ への写像となっている．
<br>
仮説クラス $\cal{H}$ と訓練データセット $S$ が与えられると，${\rm{ERM}}_{\cal{H}}$ に基づく学習器は $h \in \cal{H}$ を選ぶために，$S$ に依存してもっとも小さなエラーをもつように *ERM* ルールを適用する．
$$
{\rm{ERM}}_{\cal{H}}(S) = \underset{h \in \cal{H}}{\rm{argmin}} \; L_S(h)
$$
ただし $\underset{h \in \cal{H}}{\rm{argmin}}$ とは，$\cal{H}$ に依存する $L_S(h)$ の値を最小にしうる仮説 $h$ の集合である．
---
## 予測器を選択に制限をかける
学習器が仮説クラス $\cal{H}$ から予測器を選ぶ際に制限をかけることで，特定の予測器の集合に対してバイアスをかけられる（ $Inductive \; bias$ と呼ぶ）．
> 訓練データを見る前に予測器の選択に制限をかければ，学習器をそれまで学習してきた問題に関する知識に準拠させられる．
<br>
では，どのような仮説 $h$ を選べるようにすればいいのか？
---
## 有限仮説クラス: サイズの上限を定める
もっとも単純にクラスに対して制限をかける方法は，そのサイズについて上限を定めることだ．
> つまり、予測器 $h$ の最大存在個数は，ある仮説クラス $\cal{H}$ のサイズより大きくならない
<br>
このセクションにおいては， ++もし $\cal{H}$ が有限クラスであれば，十分に大きな訓練データが与えられたときの $ERM_{\cal{H}}$ は過学習しないという性質++ を示す．
（「十分に大きな」とは、$\cal{H}$ のサイズに依存した数値）
---
## 有限クラス $\cal{H}$ を想定した ${\rm{ERM}}_{\cal{H}}$ の振る舞い
$\cal{H}$ が有限クラスであると仮定して ${\rm{ERM}}_{\cal{H}}$ を分析しよう．
<br>
関数 $f: \cal{X} \rightarrow \cal{Y}$ でラベリングされた訓練データ $S$ について，$h_S$ (訓練データ $S$ から得られた仮説) は ${\rm{ERM}}_{\cal{H}}$ を $S$ に適用した結果として定義する．すなわち，
$$
h_S \in \underset{h \in \cal{H}}{\rm{argmin}} \: L_S(h).
$$
---
## 定義：実現可能性の仮定
#### DEFINITION 2.1 (The realizability Assumption)
$$
h^* \in {\cal{H}} \; \; s.t. \; \; L_{({\cal{D, f}})} (h^*) \: = \: 0
$$
上記のような $h^*$ が存在すると仮定する．すなわち，
- 確率１のランダムサンプリングで訓練データセット $S$ が抽出され，
- 確率分布 $\cal{D}$ で訓練データセット $S$ のインスタンス点群が抽出され，
- ラベリング関数 $f$ でそのインスタンス点群がラベル付けされる．
<br>
<br>
このとき，「$L_S(h^*) = 0$ （エラーがゼロ）となる $h^*$ が存在する」 ことを意味している．
---
## 実現可能性の仮定についての依存関係
実現可能性の仮定は，すべての ${\rm{ERM}}_{\cal{H}}$ の仮説について，$L_S(h^*) = 0$ であることを意味する．
- つまり，すべての仮説 $h \in \cal{H}$ について，エラーがゼロ
- しかし，我々が知りたいのはその経験リスクではない
- むしろ， $h_S, \; L_{({\cal{D}}, f)}(h_S)$ に対する真のリスクである．
<br>
<br>
$S$ のサンプルにだけアクセスできるアルゴリズムの基礎となる確率分布 $\cal{D}$ に関するエラーのいかなる保証も， ++確率分布 $\cal{D}$ と訓練データセット $S$ の関係だけに依存しているべき++ だ．
---
## 統計学的機械学習に共通の仮定
統計学的な機械学習に共通する仮定として，
- 訓練サンプルデータセット $S$ はある点群によって構成される
- 確率分布 $\cal{D}$ は，$S$ とはお互いに独立に点群を生成する
が挙げられる．
<br>
<br>
これは，$i.i.d.$ *assumption* と呼ばれ，次のように形式的に定義される．
---
## 独立同一分布: the $i.i.d.$ Assumption
#### **The i.i.d. assumption:**
- 訓練データは確率分布 $\cal{D}$ によって①同一の分布から ②独立に 生成される．
- すべての $x_i \in S$ は $\cal{D}$ によって常に新しく抽出され、$\cal{f}$ によってラベリングされる．
- これを $S \sim \cal{D}^m$ と定義する
- 本来「～」は *Similar* の意味だが，ここでは $are \; sampling \; from$ の意味．
- $m$ は $S$ の要素数 (*size*)
- $\cal{D}^m$ は、 $\cal{D}$ で抽出され $\cal{f}$ でラベリングされた $m$ 個のタプルとして定義
> 訓練データ $S$ は、ある世界の断片的な情報を探すような "覗き窓" である．
> → サンプルが大きくなるほど，分布とラベル付けをより正確に反映できる．
---
## エラー $L_{(\cal{D, f})} (h_S)$ のランダム性
$L_{(\cal{D, f})} (h_S)$ について，
- 訓練データセット $S$ に依存
- ランダムな手続きによって選び出されている
<br>
<br>
ゆえに，予測器 $h_S$ の選択と その結果として起こるリスク $L_{(\cal{D, f})} (h_S)$ には無作為性がある．
<br>
<br>
形式的に言えば，$L_{({\cal{D}}, f)} (h_S)$ は ++ランダム変数である++ といえる ．
---
## サンプリングそのものが偏っていることも
$\cal{D}$ の視点からみて，「訓練データセット $S$ が ++完全に確実に++ 学習器をよい分類器へと導いてくれる」と期待するのは現実的ではない．
→ 訓練データセットが実際のデータの分布を *全くよく表していない* という可能性もある．
<br>
**例：**
- 「島にあるパパイヤのうち７割が美味しい」という真の事実がある．
- 「観測範囲にあったパパイヤが，たまたま全く美味しくない」という（小さな）可能性が常にいくらか存在する．
このとき $ERM_{\cal{H}}(S)$ は， ==すべてのパパイヤが「美味しくない（$-1$）」とラベリングされる== （ような定数関数になる）．
---
## 確信度 $1 - \delta$ : サンプリングの偏りを減らすために
ゆえに， "確率" を割り当てて考える．
- リスク $L_{(\cal{D, f})} (h_S)$ が大きくならないような訓練データセットをサンプリングしたい．
たいていは， $\delta$ によって ++非代表的なデータセットを獲得してしまう確率++ を定義する．
- この「よくないデータセットを選ばない確率」＝ $(1-\delta)$ のことを "確信度パラメータ" と呼ぶ．
---
## 精度 $\epsilon$ : 予測器の質を知るために
さらに，予測の質を示すための "精度パラメータ" も導入する．
- ラベル付け予測を完璧にすることを保証できない
- $\epsilon$ を用いて，「どのくらい予測が信じられるか」を定量化する
<br>
<br>
$L_{(\cal{D, f})} (h_S) > \epsilon$ : :-1:
- 学習が失敗している
- エラーの値が精度パラメータより大きいため
$L_{(\cal{D, f})} (h_S) \leq \epsilon$ : :+1:
- 学習が成功している
- アルゴリズムの出力がおおよそ正しいであろうと解釈できる
---
## 失敗しているインスタンスはどのくらい？
ラベリング関数を $f \colon \cal{X} \rightarrow \cal{Y}$ に固定したとき，
どのくらいのサンプル（インスタンスとラベルのペア，あるいはタプル）が学習に失敗しているのか？
<br>
→ 学習がうまくいっていない $m$ 個のタプルがどのような確率で生成されるのか？
（を知るために，まずは ++その上限に関心が向く++ ）
---
## 「わるい」仮説クラスの個数を抑える (1/2)
形式的に言えば，訓練データセットのインスタンスを ==$S \vert _x = \left( x_1, \ldots , x_m \right)$== とする．
また，上界(Upper bound)（ここでは，学習が失敗しているところ）を以下のように表記する．
$$
{\cal{D}}^m \left( \{ S \vert _x \colon L_{(\cal{D, f})} (h_S) > \epsilon \} \right)
$$
<br>
「わるい」仮説の集合を ${\cal{H}}_B$ とし，以下のように表記する．
$$
{\cal{H}}_B = \{ h \in {\cal{H}} \colon L_{(\cal{D, f})}(h) > \epsilon \}
$$
---
## 「わるい」仮説クラスの個数を抑える (2/2)
加えて，誤ってサンプリングしてしまったものの集合 $M$ を以下のように表記する．
$$
M = \{ S \vert _x \colon \exists h \in {\cal{H}}_B , L_S(h) = 0 \}
$$
すなわち，すべての $S \vert _x \in M$ について，
- 訓練データセット $S \vert _x$ においてはわるくない
- 実際には「わるい」仮説 $h \in {\cal{H}}_B$ が ++少なくとも１つはある++
ということになる．
---
## 失敗とみなされる確率を抑える (1/3)
ここで，$L_{(\cal{D, f})} (h_S) > \epsilon$ となる確率（エラーが精度の値を超えてしまい，学習が失敗したとみなされる確率）を抑えたかったことを思い出そう．
> 実現性の仮定は $L_S(h_S) = 0$ を伴うがために， $L_{(\cal{D, f})} (h_S) > \epsilon$ という事象は「いくつかの予測 $h \in {\cal{H}}_B$ について， $L_S(h) = 0$ となる」という場合にしか，この事象は起こりえない．
> 言い換えれば，この不等式は私達のサンプル点群が「誤っているサンプルの集合」である $M$ に含まれている場合にしか起こりえない．
---
## 失敗とみなされる確率を抑える (2/3)
形式的に言えば，以下のようになる．
$$
\{ S \vert _x \colon L_{(\cal{D, f})}(h_S) > \epsilon \} \subseteq M
$$
<br>
<br>
$M$ は次のように書き換えられる．
$$
M = \bigcup_{h \in \cal{H}_B} \{ S \vert _x \colon L_S(h) = 0 \}
$$
---
## 失敗とみなされる確率を抑える (3/3)
したがって，以下のようになる．
$$
\begin{eqnarray}
{\cal{D}}^m \left( \{ S \vert _x \colon L_{(\cal{D, f})} (h_S) > \epsilon \} \right)
&\leq&
{\cal{D}}^m (\rm{M}) \\
&=&
{\cal{D}}^m (\cup_{h \in {\cal{H}}_B} \{ S \vert _x \colon L_S(h) = 0 \}) \\
\end{eqnarray}
$$
---
## *Union Bound* とは
次に，（確率の基本的な性質である）「Union bound」を使用して，前述の方程式の右辺の上限を設定する（上から抑える？）．
<br>
<br>
**LEMMA 2.2 (Union Bound)**
いかなる2つの集合 $A, B$ についても，ある分布 $\cal{D}$ は，以下を満たす
$$
\begin{eqnarray}
{\cal{D}} \left( \rm{A} \cup \rm{B} \right)
&=&
{\cal{D}} \left( \rm{A} \right)
+ {\cal{D}} \left( \rm{B} \right)
- {\cal{D}} \left( \rm{A} \cap \rm{B} \right) \\
&\leq&
{\cal{D}} \left( \rm{A} \right)
+ {\cal{D}} \left( \rm{B} \right) \\
\end{eqnarray}
$$
---
## *Union Bound* を適用して……
これを前述の関係式の右辺に適用すると，以下のようになる．
$$
{\cal{D}}^m \left( \{ S \vert _x \colon L_{(\cal{D, f})} (h_S) > \epsilon \} \right)
\leq
\sum_{h \in {\cal{H}}_B} {\cal{D}}^m \left( \{ S \vert _x \colon L_S(h) = 0 \} \right)
$$
---
## 「わるい」仮説 $h \in {\cal{H}}_B$ を修正
次に，この不等式の右辺にあるそれぞれの被加数を抑えよう．
- いくつかの「わるい」仮説 $h \in {\cal{H}}_B$ を修正していく．
- $L_S(h) = 0$ という事象は $\forall i, h(x_{i}) = f(x_{i})$ という事象と同等である．
<!-- すべての仮説の関数 $h(x)$ が理想的なラベリング関数fと一致している、つまり誤差/エラーがない -->
<br>
<br>
訓練データの各サンプルが独立同一分布（$\cal{i.i.d}$）から抽出されているから，次の等式を得る．
$$
\begin{eqnarray}
{\cal{D}}^m \left( \{ S \vert _x \colon L_S(h) = 0 \} \right)
&=&
{\cal{D}}^m \left( \{ S \vert _x \colon \forall i, h(x_{i}) = f(x_{i}) \} \right) \\
&=&
\prod_{i=1}^{m} {\cal{D}} \left( \{ x_i \colon h(x_{i}) = f(x_{i}) \} \right)
\end{eqnarray}
$$
---
## 少しづつ式変形を施すと……
訓練データセットの各要素に関しての個々のサンプリングについて，次の $1 - \epsilon$ が仮説 $h \in \cal{H}_B$ という事実から続く時，以下の関係式を得たことになる．
$$
\begin{eqnarray}
{\cal{D}} \left( \{ x_{i} \colon h(x_{i}) = y_{i} \} \right)
&=&
1 - L_{(\cal{D, f})}(h) \\
&\leq&
1 - \epsilon
\end{eqnarray}
$$
それぞれの $h \in \cal{H}_B$ について得られる $1 - \epsilon \leq e^{- \epsilon}$ という不等式も組み合わせると，次のような関係が得られて……，
$$
\begin{eqnarray}
{\cal{D}}^m \left( S \vert _x \colon L_S(h) = 0 \} \right)
&\leq&
\left( 1 - \epsilon \right) ^ m \\
&\leq&
e^{- \epsilon m}
\end{eqnarray}
$$
---
## 結論: 有限仮説クラス $\cal{H}$ と訓練サンプル数 $m$
もともと考えていた
$$
{\cal{D}}^m \left( \{ S \vert _x \colon L_{(\cal{D, f})} (h_S) > \epsilon \} \right) \leq \sum_{h \in {\cal{H}}_B} {\cal{D}}^m \left( \{ S \vert _x \colon L_S(h) = 0 \} \right)
$$
の関係式に代入して考えると，以下のように結論付けられる．
<br>
<br>
$$
\begin{eqnarray}
{\cal{D}}^m \left( \{ S \vert _x \colon L_{(\cal{D, f})} (h_S) > \epsilon \} \right)
&\leq&
\left| \cal{H}_B \right| e^{- \epsilon m} \\
&\leq&
\left| \cal{H} \right| e^{- \epsilon m}
\end{eqnarray}
$$
---
## Corollary 2.3
- $\cal{H}$ : 有限仮説クラス
- $\delta \in (0, 1)$
- $\epsilon > 0$
- $m \geq \frac{\log \left( \left| \cal{H} \right| / \delta \right)}{\epsilon}$
であるする．このとき，
いかなるラベリング関数 $f$ ，確率分布 $\cal{D}$ であっても，それが「実現可能性の仮定」に基づいていて，大きさ $m$ の訓練データセット $S$ が確信度 $1 - \delta$ の確率で $i.i.d.$ に抽出されるのならば，
$$
\forall h_S, \; \; \; L_{({\cal{D}}, f)} (h_S) \leq \epsilon
$$
---
## 2章のまとめ
訓練データセットの大きさ $m$ が十分に大きければ，有限仮説クラスに基づくリスク最小化法 ${\rm{ERM}}_{\cal{H}}$ は， ++確率的におおよそ++ 正しい．
- 確率的: 確信度（学習が間違っていない確率）が $1 - \delta$
- おおよそ: エラーの値は精度 $\epsilon$ の値よりも小さい
{"metaMigratedAt":"2023-06-15T04:58:40.946Z","metaMigratedFrom":"YAML","title":"UML chapter 02","breaks":true,"lang":"ja-jp","GA":"UA-110561341-4","slideOptions":"{\"theme\":\"white\",\"slideNumber\":\"c/t\",\"center\":false,\"transition\":\"none\",\"keyboard\":true,\"width\":\"93%\",\"height\":\"100%\"}","contributors":"[{\"id\":\"b4f3bbe0-936a-4516-a9bf-652fb6d3ed0a\",\"add\":22373,\"del\":8059}]"}