オッカムの剃刀と汎化誤差解析

Transcript

1. Intro Occan Bound Additional Discussions References オッカムの剃刀と汎化誤差解析 Masanari Kimura mkimura@ridge-i.com August 31, 2021
2. Intro Occan Bound Additional Discussions References Intro 2/11
3. Intro Occan Bound Additional Discussions References TL;DR ▶ オッカムの剃刀の概念について説明； ▶ オッカムの剃刀の形式化と汎化誤差解析への応用について説明． 3/11
4. Intro Occan Bound Additional Discussions References オッカムの剃刀（Occam’s Razor） オッカム [Drouhin, 2006] 必要が無いなら多くのものを定立してはならない．少数の論理でよい場合は多数の論理を 定立してはならない． ▶ ある二つの理論が同程度にデータを説明できているとき，より単純な方が好まれる； ▶ 統計的機械学習において単純さは直感的にだけでなく定量的に測れる； ▶ 以下ではオッカムの剃刀を形式的に記述していく． 4/11
5. Intro Occan Bound Additional Discussions References Occan Bound 5/11
6. Intro Occan Bound Additional Discussions References Occam Bound Theorem 独立かつ同一なサンプルサイズ m のデータセット S = {x, y} とある仮説 h ∈ H について 少なくとも 1 − δ の確率で以下が成り立つ： L(h) ≤ ˆ L(h) + √ (ln 2)|h| + ln 1 δ 2m . (1) ただし，|h| は仮説 h を記述するのに必要な bit 数であり， L(h) := E [ 1[h(x) ̸= y] ] , (2) ˆ L(h) := 1 m m ∑ i=1 1[h(xi) ̸= yi]. (3) 6/11
7. Intro Occan Bound Additional Discussions References Proof of the Occam Bound Proof. 定理に矛盾する仮説集合を B とする： B := { L(h) ≥ ˆ L(h) + √ (ln 2)|h| + ln 1 δ 2m ; h ∈ H } (4) このとき， P [ h ∈ B ] ≤ ∑ h∈H exp { −2m (√ (ln 2)|h| + ln 1 δ 2m )2 } (∵ Chernoff bound) (5) = ∑ h∈H δ2−|h| = δ ∑ h∈H 2−|h| ≤ δ (∵ Kraft inequality) (6) 7/11
8. Intro Occan Bound Additional Discussions References Occam Bound と仮説選択 Occam bound は期待誤差の上界を与えるので，これを最小化するように仮説選択をする ことが考えられる： ˆ h = arg min h∈H ˆ L(h) + √ (ln 2)|h| + ln 1 δ 2m . (7) ▶ この最適化は，手元へのデータの説明能力（第一項）とモデルのシンプルさ（第二 項）の最小化のトレードオフになっている； ▶ これは，ある h1 , h2 ∈ H がもし同じだけデータを説明できるとき，よりシンプルな方 が未知のデータへの誤差を小さくできる可能性が高いことを意味している； ▶ これはまさしくオッカムの剃刀の形式的な記述になっている． 8/11
9. Intro Occan Bound Additional Discussions References Additional Discussions 9/11
10. Intro Occan Bound Additional Discussions References Occam Bound のベイズ的解釈 P を h に関する確率分布とし，|h|P を以下のように定義する： |h|P := log 2 1 P(h) . (8) このとき，Occam bound は次のように書き換えることができる： L(h) ≤ ˆ L(h) + √ (ln 2)|h|P + ln 1 δ 2m . (9) これはまさしく仮説集合に関する任意の事前分布を考えた場合の Occam bound に相当 する． 10/11
11. Intro Occan Bound Additional Discussions References References I Nicolas Drouhin. Pluralitas non est ponenda sine neccesitate. Technical report, GRID Working paper, 2006. 11/11