統計的学習理論の基礎 II

Transcript

1. CompML ౷ܭతֶशཧ࿦ͷجૅ II Masanari Kimura (@machinery81)
2. CompML TL;DR • ౷ܭతֶशཧ࿦ͷجૅతͳࣄ߲ͷ·ͱΊ • ୈೋճ͸ҎԼͷτϐοΫʹ͍ͭͯ • ू߹ͷ෼཭֓೦ • VC-Dimension • Pseudo-Dimension • Fat-Shattering Dimension • VCό΢ϯυ 2
3. CompML VC-Dimension
4. CompML VC-Dimension ఆٛ 1.ʢVC-࣍ݩʣՄଌۭؒ ͷ͋Δू߹Λ ͱ͢Δɽશͯͷ෦෼ू߹ ʹ͍ͭͯɼ ͱͳΔΑ͏ͳ ͕ଘࡏ͢Δͱ͖ɼू߹ ͸ Ͱ෼཭͞ ΕΔͱ͍͏ɽ ͷVapnik-Chervonenkis࣍ݩ ͸ɼ ʹΑͬͯ෼཭͞ΕΔू ߹ͷج਺ͷ࠷େ஋ʹ౳͍͠ɽ (𝑋, 𝑆) 𝒜 ⊂ 𝑆 𝐵 ⊂ 𝑆 𝑆 ∩ 𝐴 = 𝐵 𝐴 ∈ 𝒜 𝑆 𝒜 𝒜 𝑉𝐶𝑑𝑖𝑚(𝒜) 𝒜 Photo by Wikipedia.
5. CompML The Pseudo-Dimension ఆٛ2.ʢ -࣍ݩʣՄଌۭؒ ͷ্ͷՄଌؔ਺ͷू߹Λ ͱ͢Δɽ ू߹ ͸ҎԼ͕੒Γཱͭͱ͖ -shatteredͰ͋Δͱ͍͏ɿ ೚ҙͷ2஋ϕΫτϧ ͱͦΕʹରԠ͢Δؔ਺ ʹ͍ͭͯɼ ্هͷ৚݅ΛHeavisideؔ਺ Ͱॻ͖׵͑Δͱ ؔ਺Ϋϥε ͷ -࣍ݩ͸ ʹΑͬͯ -shatteredͱͳΔΑ͏ͳू߹ͷج਺ͷ࠷େ஋Ͱఆٛ͞Εɼ ͱॻ͔ΕΔɽ 𝑃 (𝑋, 𝑆 ) ℱ ⊂ [0,𝑅] 𝑋 𝑆 = {𝑥1 , …, 𝑥𝑛} ⊂ 𝑋 𝑃 𝑒 ∈ {0,1}𝑛 𝑓𝑒 ∈ ℱ { 𝑓𝑒(𝑥𝑖) ≥ 𝑐𝑖 𝑖𝑓 𝑒𝑖 = 1, 𝑓𝑒(𝑥𝑖) < 𝑐𝑖 𝑖𝑓 𝑒𝑖 = 0. 𝜂(𝑧) 𝜂[𝑓𝑒(𝑥𝑖) − 𝑐𝑖] = 𝑒𝑖 , ∀𝑖, ∀𝑒 . ℱ 𝑃 ℱ 𝑃 𝑃𝑑𝑖𝑚(ℱ)
6. CompML Illustration of P-Shattering 𝑥1 𝑥2 𝑥3 𝑓 [01…1] 𝑓 [00…1] 𝑓 [11…0] 𝑐1 𝑐2 𝑐3 { 𝑓𝑒(𝑥𝑖) ≥ 𝑐𝑖 𝑖𝑓 𝑒𝑖 = 1, 𝑓𝑒(𝑥𝑖) < 𝑐𝑖 𝑖𝑓 𝑒𝑖 = 0.
7. CompML VC࣍ݩͱ -࣍ݩͷಉ஋৚݅ 𝑃 ิ୊1ɽ ʹ͍ͭͯɼҎԼͷΑ͏ʹ Λఆٛ͢Δɿ ͜ͷͱ͖ɼ ℱ = {𝑓:𝑋 → [0,𝑅]} ¯ ℱ ¯ ℱ = { ¯ 𝑓(𝑥, 𝑐) = 𝜂[𝑓(𝑥) − 𝑐] :𝑓 ∈ ℱ} . 𝑃𝑑𝑖𝑚( ¯ ℱ) = 𝑉𝐶𝑑𝑖𝑚( ¯ ℱ) .
8. CompML The Fat-Shattering Dimension ఆٛɽʢFat-Shattering࣍ݩʣ Մଌۭؒ ͷ্ͷՄଌؔ਺ͷू߹Λ ͱ͢Δɽू߹ ͸Ҏ Լ͕੒Γཱͭͱ͖෯ ͓Αͼਫ਼౓ Ͱfat-shatteredͰ͋Δͱ͍͏ɿ ೚ҙͷ2஋ϕΫτϧ ͱͦΕʹରԠ͢Δؔ਺ ʹ͍ͭͯɼ ؔ਺Ϋϥε ͷFat-Shattering࣍ݩ͸ ʹΑͬͯfat-shatteredͱͳΔΑ͏ͳू߹ͷج ਺ͷ࠷େ஋Ͱఆٛ͞Εɼ ͱॻ͔ΕΔɽ (𝑋, 𝑆) ℱ ⊂ [0,𝑅] 𝑋 S = {x1 , …, xn } γ c 𝑒 ∈ {0,1}𝑛 𝑓𝑒 ∈ ℱ { fe (xi ) ≥ ci + γ if ei = 1, fe (xi ) < ci − γ if ei = 0. ℱ ℱ Fdim(ℱ, γ)
9. CompML VC Generalization Bound ఆཧɽظ଴ޡࠩ ͓Αͼܦݧޡࠩ ʹ͍ͭͯɼVC࣍ݩΛ ͱॻ͘ͱɼ ͕ຬ଍͞ΕΔɽ ൚Խޡ͕ࠩVC࣍ݩΛ༻͍ͯ཈͑ΒΕΔɽ R(h) ̂ R(h) dVC R(h) − ̂ R(h) ≤ 8dVC(ln 2m dVC + 1) + 8 ln 4 δ m
10. CompML LemmaʢSymmetrizationʣ ิ୊ɽ ͱͳΔΑ͏ͳ ʹ͍ͭͯɼ ͕੒Γཱͭɽ͜͜Ͱ ؔ਺ͷظ଴஋ͱܦݧ஋ͷࠩ͸ɼಠཱʹಘΒΕͨೋछྨͷܦݧ஋ͷࠩͰ཈͑ΒΕΔɽ t ≥ 2/m t > 0 P( sup f∈ℱ | f − ̂ f | ) ≤ 2P( sup f∈ℱ | ̂ f′ − ̂ f | ≥ t/2) f = 𝔼[ f ] ̂ f = 1 m m ∑ i=1 f(xi , yi ) ̂ f′ = 1 m m ∑ i=1 f(x′ i , y′ i )
11. CompML ࢀߟจݙ • Shalev-Shwartz, S., Ben-David, S. (2014). Understanding Machine Learning - From Theory to Algorithms.. Cambridge University Press. ISBN: 978-1-10-705713-5 • Mohri, Mehryar, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.