<!-- preamble --> $$ \newcommand{\argmin}{\mathop{\rm arg~min}\limits} $$ <!-- end preamble --> <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> </div> <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> <!----------------------------------------------------------------------------------------- --> #### Understanding Machine Learning: from Theory to Algorithms # Chap.4 Learning via Uniform Convergence <br> <br> #### 2020-MM-DD ### @ningensei848 --- ## はじめに 最初に議論した形式的な学習モデルは==PACモデル==（++確率的におおよそ正しい++モデル）であった ２章においては、実現可能性の仮定のもとではいかなる有限仮説クラスであってもPACモデルを用いて学習できることを見てきた ４章では、損失関数の取りうる範囲が抑えられている限り、＜汎用的な損失関数を持つ ++*Agnostic*++ なPACモデルにおいてはいかなる有限仮説クラスにおいてもそれが学習可能であること＞を見せるために、==「$uniform \; convergence$」== という道具を開発し、それを学習に適用する --- ## Uniform Convergence is Sufficient for Learnability 復習： ERM(経験損失最小化)学習のパラダイムについて 学習器は… - 与えられたサンプルにおいて仮説クラス $\cal{H}$ に含まれるそれぞれの予測 $h$ におけるリスク（エラー）を評価する - その経験的なリスクを最小化するような仮説クラス $\cal{H}$ の要素を出力する --- ## Uniform Convergence is Sufficient for Learnability ここで望まれるのは、$S$ に関して経験損失を最小化するような予測 $h$ が、==同様に真のデータ生成確率分布に関する ++*Minimizer*++ であること== →　仮説クラス $\cal{H}$ の ++すべての要素の経験損失が真のリスクに対して十分に近似されているということ++ を保証すれば良い --- ## Definition 4.1 別の言い方をすれば、++仮説クラスにおける仮説(予測)のすべてを一律に、その経験リスクを真のリスクへ近づけていけばよい++ <br> <br> #### $\epsilon - \rm{representative}$ sample 以下の条件を満たす時、訓練データセット $S$ は、 ==$\epsilon - \rm{representative} \; sample$== と呼ばれる $$ \forall h \in {\cal{H}}, \; \left| L_{S}(h) - L_{\cal{D}}(h) \right| \leq \epsilon $$ --- ## Lemma 4.2 以下の補題では、「ERMルールは $(\epsilon / 2) - \rm{representative}$ なサンプルであれば、いつでも良い仮説が返ることを保証する」と述べている > 訓練データセット $S$ が $(\epsilon / 2) - \rm{representative}$ であるとき、その $ERM_{\cal{H}}(S)$ すなわち $h_S \in \underset{h \in \cal{H}}{argmin} L_S(s)$ のいかなる出力も次の関係を満たす > $$ > L_{\cal{D}} (h_S) \leq \min_{h \in \cal{H}} L_{\cal{D}} (h) + \epsilon > $$ ※証明は次のスライドに示す --- ## Proof for Lemma 4.2 $$ \forall h \in {\cal{H}} \; ,\\ \begin{eqnarray} L_{\cal{D}} (h_S) &\leq& L_S (h_S) &+& \frac{\epsilon}{2} & \left( \because \; \left| L_{S}(h) - L_{\cal{D}}(h) \right| \leq \epsilon \right) \\ &\leq& L_S (h) &+& \frac{\epsilon}{2} \\ &\leq& L_{\cal{D}} (h) &+& \frac{\epsilon}{2} + \frac{\epsilon}{2} & \left( \because \; \left| L_{S}(h) - L_{\cal{D}}(h) \right| \leq \epsilon \right) \\ &=& L_{\cal{D}} (h) &+& \epsilon \end{eqnarray} $$ ２つ目の不等号について、$h_S$ はERMの予測器だから、単なる予測 $h$ よりは損失関数の値が小さくなる　→　$L_S(h_S) \leq L_S(h)$ --- ## ここまでの解釈 この補題(Lemma)は、訓練データセットをランダムに選択した上で少なくとも $1 - \delta$ の確率をもって、それが $\epsilon - \rm{representative}$ な訓練データセットであるということを示した これだけで==ERMルールが++Agnostic++なPAC学習器であること==を保証できたこと意味している <br> `Uniform Convergence Condition` がこの要件を形式化してくれる --- ## Definition 4.3 ### Uniform Convergence ==$m_{\cal{H}}^{UC} \colon (0, 1)^2 \rightarrow \mathbb{N}$ という関数が存在しているとき==、仮説クラス $\cal{H}$ は、ある性質 $uniform \; convergence$ を持つ つまり - すべての $\epsilon, \delta \in (0, 1)$ - すべての確率分布 ${\cal{D}} \sim Z$ について、==もし $S$ が $m \geq m_{\cal{H}}^{UC} (\epsilon, \delta)$ で同一の確率分布 ${\cal{D}}$ から独立 ($i.i.d$) にサンプルされていれば==、$S$ は少なくとも確信度 $1 - \delta$ の確率で $\epsilon - \rm{representative}$ である --- ## Uniform Convergence PACモデルの標本複雑性（ $sample \; complexity$ ）の定義のときと同様に、関数 $m_{\cal{H}}^{UC}$ は （学習モデルが）$Uniform \; Convergence$ という性質をもつ場合の標本複雑性を測定する →　++どのくらいサンプリングすれば++、 少なくとも確信度 $1 - \delta$ の確率で $\epsilon - \rm{representative}$ であると保証できるか　について測定している <br> ここで $uniform$ という語は、 - 仮説クラス $\cal{H}$ のすべての要素 - あるドメイン集合をもとにしてそこから取りうるすべての確率分布 に対して機能するような固定の標本サイズを持つことを意味する --- ## Corollary 4.4 > もし仮説クラス $\cal{H}$ が（標本複雑性 $m_{\cal{H}}^{UC}$ で） $Uniform \; Convergence$ という性質を持てば、そのクラスは $m_{\cal{H}}(\epsilon , \delta) \leq m_{\cal{H}}^{UC} (\epsilon / 2 , \delta)$ を満たすように、 ++*Agnostic*++ に “確率的におおよそ正しく（++*PAC*++）” 学習可能である <br> <br> 「すべての有限仮説クラスは *$Agnostic$* にPAC学習可能である 」という主張は、 $uniform \; convergence$ が有限仮説クラスを保持しているということに従う --- ## $uniform \; convergence$ の導出 $uniform \; convergence$ の導出には、次の２ステップが必要 - $union \;bound$ を適用する - 集中不等式による測定 --- ## $uniform \; convergence$ の導出 まず、精度 $\epsilon$ , 確信度 $\delta$ を固定して、その時のサンプルサイズ $m$ を探す必要がある この $m$ は、 - いかなる確率分布 $\cal{D}$ についても - 同一の $\cal{D}$ から独立（ $i.i.d$ ）に生成された $S$ を選ぶときに、少なくとも確信度 $1 - \delta$ の確率で - $\forall h \in {\cal{H}} , \; \left| L_S(h) - L_{\cal{D}}(h) \right| \leq \epsilon$ であることを保証する --- ## $uniform \; convergence$ の導出 つまり、 $$ {\cal{D}}^m \left( \{ S \; \colon \; \forall h \in {\cal{H}} , \; \left| L_S(h) - L_{\cal{D}}(h) \right| \leq \epsilon \} \right) \geq 1 - \delta $$ これは、次の関係式を示すことと同等である $$ {\cal{D}}^m \left( \{ S \; \colon \; \exists h \in {\cal{H}} , \; \left| L_S(h) - L_{\cal{D}}(h) \right| > \epsilon \} \right) < \delta $$ --- ## $uniform \; convergence$ の導出 > *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*++ を適用して、次の関係式を得る $$ \begin{eqnarray} {\cal{D}}^m \left( \{ S \; \colon \; \exists h \in {\cal{H}} , \; \left| L_S(h) - L_{\cal{D}}(h) \right| > \epsilon \} \right) &=& \bigcup_{h \in {\cal{H}}} \{ S \; \colon \left| L_S(h) - L_{\cal{D}}(h) \right| > \epsilon \} \\ &\leq& \sum_{h \in {\cal{H}}} {\cal{D}}^m \left( \{ S \; \colon \left| L_S(h) - L_{\cal{D}}(h) \right| > \epsilon \} \right) \end{eqnarray} $$ --- ## 真のエラーと経験損失の隔たり 次に、不等式の右辺の中身 ${\cal{D}}^m \left( \{ S \; \colon \left| L_S(h) - L_{\cal{D}}(h) \right| > \epsilon \} \right)$ が十分に小さいということ議論する（ただし、$m$ が十分に大きいとする） つまり、どんな仮説 $\cal{H}$ であっても、「++真のエラーならびに経験損失との間にある隔たり ( $\left| L_S(h) - L_{\cal{D}}(h) \right|$ ) が小さそうである++」ということを示していく --- ## 真のエラーと経験損失の隔たり $L_{\cal{D}}(h) \; = \; \mathbb{E}_{Z \sim {\cal{D}}} \left[ \ell (h, z) \right]$ と $L_S(h) \; = \; \frac{1}{m} \sum_{i = 1}^{m} \ell (h, z_i)$ を思い出そう ドメイン集合 $Z$ のインスタンス $z_i$ は、同一の $\cal{D}$ から独立( $i.i.d.$ )に抽出されていることから、ランダム変数 $\ell (h, z_i)$ の期待値は $L_{\cal{D}}(h)$ である 期待値の線形性によれば、$l_{\cal{D}}(h)$ もまた $L_S(h)$ の期待値に従う そうなれば、$\left| L_{\cal{D}}(h) - L_S(h) \right|$ はランダム変数 $L_S(h)$ の偏差であり、自身の期待値から得られる つまり、「 $L_S(h)$ を測定することは、その期待値の周辺(を測ること)に集中する」と示したい --- ## $Hoeffding$ の集中不等式 基礎的な統計学における事実として、大数の法則がある > サンプル数が大きいほど、その平均は秦の期待値に収束する これは $L_S(h)$ にとっては真であるが、実際にはその法則は我々に漸近的な結果をもたらすだけで、二つのエラーの間に（経験的に推定されたエラーと限られたサンプルが与えられた中での真のエラーの間に）ギャップがあるのかについて何かわかるわけではない 代わりに、$Hoeffding$ による「==**集中不等式**==」を用いる これにより、経験的な平均値とそれらの期待値の間にある隔たりを定量化できる --- ## Lemma 4.5 #### $Hoeffding$ の集中不等式 - $\theta_{1} , \; \ldots , \; \theta_{m}$ は同一分布から独立 ( $i.i.d.$ ) に抽出された点の列 - すべての $i$ について、 $\mathbb{E} [\theta_{i}] = \mu$ - すべての $i$ について、 $\mathbb{P} [a \leq \theta_{i} \leq b] = 1$ とする このとき、いかなる $\epsilon > 0$ についても、以下の関係が成り立つ ※ この証明は付録Bを参照 $$ \mathbb{P} \left[ \left| \frac{1}{m} \sum_{i = 1}^{m} \theta_{i} - \mu \right| > \epsilon \right] \leq 2 \exp \{ -2 m \epsilon ^2 / (b - a)^2 \} $$ --- ## $uniform \; convergence$ の導出 これまで見てきた問題に戻ろう $\theta_{i}$ をランダム変数 $\ell ( h, z_i )$ とする 予測 $h$ が固定され、$z_1, \; \ldots , \; z_m$ が同一の分布から独立に抽出されていることから、$\theta_{1} , \; \ldots , \; \theta_{m}$ もまたランダム変数である もっといえば、$L_S(h) = \frac{1}{m} \sum_{i = 1}^{m} \theta_{i}$ と $L_{\cal{D}} (h) = \mu$ となる --- ## $uniform \; convergence$ の導出 より深く、$\ell$ は閉区間 $[0, 1]$ であり、そこから $\theta_{i} \in [0, 1]$ であると仮定してみよう このとき、以下の関係式を得る $$ \begin{eqnarray} {\cal{D}}^m \left( \{ S \; \colon \left| L_S(h) - L_{\cal{D}}(h) \right| > \epsilon \} \right) &=& \mathbb{P} \left[ \left| \frac{1}{m} \sum_{i = 1}^{m} \theta_{i} - \mu \right| > \epsilon \right] \\ &\leq& 2 exp (-2 m \epsilon^2) \end{eqnarray} $$ --- ## $uniform \; convergence$ の導出 これを、$\mathbb{P} \left[ \left| \frac{1}{m} \sum_{i = 1}^{m} \theta_{i} - \mu \right| > \epsilon \right] \leq 2 \exp \{ -2 m \epsilon ^2 / (b - a)^2 \}$ と組み合わせると $$\begin{eqnarray} {\cal{D}}^m \left( \{ S \; \colon \exists h \in {\cal{H}}, \; \left| L_S(h) - L_{\cal{D}}(h) \right| > \epsilon \} \right) &\leq& \sum 2 exp (-2 m \epsilon^2) \\ &=& 2 \left| {\cal{H}} \right| exp (-2 m \epsilon^2) \end{eqnarray} $$ --- ## $uniform \; convergence$ の導出 最終的に、$m \geq \frac{\log \left( 2 |{\cal{H}}| / \delta \right)}{2 \epsilon ^2}$ となる $m$ を選べば、以下の関係を得る $$ {\cal{D}}^m \left( \{ S \; \colon \exists h \in {\cal{H}}, \; \left| L_S(h) - L_{\cal{D}}(h) \right| > \epsilon \} \right) \leq \delta $$ --- ## Corollary 4.6 - $\cal{H}$ : 有限仮説クラス - $Z$ : ドメイン集合 - $\ell \colon \; {\cal{H}} \times Z$ を閉区間 $[0, 1]$ の損失関数 とするとき、有限仮説クラス $\cal{H}$ は、標本複雑性 $m_{\cal{H}}^{UC} \left( \epsilon, \delta \right) \leq \lceil \frac{\log \left( 2 |{\cal{H}}| / \delta \right)}{2 \epsilon ^2} \rceil$ を満たすように $uniform \; convergence$ という性質を持つ <br> もっといえば、この有限仮説クラス $\cal{H}$ は、次の関係式を満たす標本複雑性をもったERMのアルゴリズムをつかって ++*Agnositically*++ にPAC学習しうる $$ $m_{\cal{H}} \left( \epsilon, \delta \right) \leq $m_{\cal{H}}^{UC} \left( \epsilon / 2, \delta \right) \leq \lceil \frac{2 \log \left( 2 |{\cal{H}}| / \delta \right)}{\epsilon ^2} \rceil$ $$ --- ## Remark 4.1 #### the "Discretization" Trick ここまで論じてきた $corollary$ は有限仮説クラスにのみ適用できるが、一方で無限の仮説がある状況においても、標本複雑性を実践的によりうまく推定させてくれる単純な手法が存在している まず、パラメタ *d* によって「媒介変数化(パラメタ化)」された仮説クラスを考えてみよう --- ## the "Discretization" Trick すべての例について、${\cal{X}} = \mathbb{R} , {\cal{Y}} = \{ \pm 1 \}$ とし、仮説クラス $\cal{H}$ をすべて $h_{\theta}(x) = sign (x - \theta)$ という形の関数であるとする ※ それぞれの仮説がひとつのパラメタ $\theta \in \mathbb{R}$ によってパラメタ化される ※ インスタンス（ここでは符号関数 $sign$ の引数 $x$）が $\theta$ よりも大きければ 1, 小さければ -1 が出力される --- ## 現実世界で起こる問題: 表現の限界 しかし実際に学習する際には計算機をしようするため、実数を 64*bit* の範囲で扱わねばならない →　実践においては、仮説クラス $\cal{H}$ も　64*bit* であらわせるスカラの集合としてパラメタ化すべき このような数は多くとも $2^64$ 個しかない（ので、実際のクラスの数も高々 $2^64$ 個しかない） もっと一般化して言えば、仮説クラスが *d* でパラメタ化されるとき、（その個数分だけクラスが存在するから）多くとも $\left( 2^64 \right)^\it{d}$ のクラスが必要となる --- ## 現実世界で起こる問題: 表現の限界 このように、実践的な制約も踏まえて考えると、標本複雑性は $m \leq \frac{128 {\it{d}} + 2 \log (2 / \delta)}{\epsilon ^2}$ と抑えられる 標本複雑性におけるこのような上界は、計算機を活用した特定の実数表現依存するという欠点があるといえよう 6章では、無限の大きさを持つ仮説クラスにおける標本複雑性を厳格に解析する方法を紹介する → この場合でも、パラメタ化の手法（離散化する手法）は、多くの実践的な場面で標本複雑性をラフに推定してくれるのである --- ## 4章のまとめ - ++*uniform convergence*++ という性質が仮説クラス $\cal{H}$ に当てはまる場合、多くは仮説クラス $\cal{H}$ における経験損失が忠実に真のリスクを表現しうる - uniform convergenceは、ERMルールに従う ++*Agnostic*++ なPAC学習可能性を担保する ==有限仮説クラスは ++*uniform convergence*++ という性質をもち、それ故に ++*Agnostic*++ なPAC学習可能である　ということを示した==