Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Sign up for free
Menu
Search
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Pricing
Search
Sign in
Sign up for free
統計的学習理論の基礎 I
Search
Masanari Kimura
December 11, 2020
Research
610
3
Share
Embed
Copy iframe code
Copy JS code
Copy link
Start on current slide
統計的学習理論の基礎 I
Masanari Kimura
December 11, 2020
Transcript
16 slides
CompML 統計的学習理論の基礎 I Masanari Kimura (@machinery81)
CompML TL;DR • 統計的学習理論の基礎的な事項のまとめ • 第一回は以下のトピックについて: • 種々の収束概念 • 確率収束
• 概収束 • UCEP property • ASCEP property • UCEM property • PAC Learning 2
CompML Uniform Convergence
CompML (, ):可測空間,:確率測度 からi.i.d.に生成された! , … , " から計算される ∈
の経験確率 + ; " = ## ∈ = 1 1 #$! " % # 気になるのは, • + (; " )がちゃんと()に収束するのか? • もしそうならば,どのように収束するのか? 4 経験確率(Empirical Probability)
CompML 確率収束(Converges in Probability) 定義.ある > 0について ! % ;
! − () > → 0 ( → ∞) のとき, % (; ! )は()に確率収束するという. 同値な表現として, ∀, > 0, ∃" , > 0 . . ! % ; ! − > ≤ ∀ ≥ "
CompML 概収束(Converges almost surely) 定義.経験確率について # % ; ! →
→ ∞ = 1 となるとき, % (; ! )は()に概収束するという. 概収束は確率収束より強い: % ; ! $.&. () ⟹ % (; ! ) → ' ()
CompML 経験確率は真の確率に確率収束する (証明)インジケータ関数( ()はBernoulli過程とみなせる: ( = 1 = 従って,Chernoffの不等式から !
% ; ! − () > ≤ 2 exp −2) が得られる.従って, → ∞で ! % ; ! − () > → 0であるので, % (; ! )は()に確率収束することが証明された. □ 実はもっと強く,経験確率は真の確率に概収束する.
CompML UCEP; Uniform Convergence of Empirical Probabilities 単一のではなく,その集合 ⊂ を考える.
定義.あるについて, ! sup (∈ % − () > → 0 ( → 0) が成り立つとき,はUCEP propertyを持つという.
CompML ASCEP; Almost Sure Convergence of Empirical Probabilities 定義.あるについて, #
sup (∈ % ! − () → 0 → ∞ = 1 が成り立つとき,はASCEP propertyを持つという.
CompML UCEM; Uniform Convergence of Empirical Means 確率変数についての関数の経験平均を以下のように書く: F ()
= 1 I ,-. ! , 定義.ある関数クラスℱについて, ! sup /∈ℱ F − > → 0 ( → 0) が成り立つとき,ℱはUCEM propertyを持つという.
CompML PAC Learning
CompML Learning Concepts • 未知の関数または概念を学習するとはどういうことか? • より強くいうと,汎化するとはどういうことか? • 学習理論における基本的なパーツは ◦
集合 ◦ 加法族 ◦ 可測空間(, )の確率測度のクラス ◦ conceptクラス ⊂ または関数クラスℱ
CompML Concept Learning 目的は,観測. , … , ! に基づいて未知のtarget concept
∈ を学習すること. • 各, について,それがに含まれるかどうかを1 (, )で表す(オラクル) • これらのペアから,写像の族(アルゴリズム)を考える: ! : × 0,1 ! → このアルゴリズムによって生成される仮説(hypothesis) ! = ! . , 1 . , … , ! , 1 !
CompML PAC学習可能;Probability Approximately Correct 定義.アルゴリズム! は以下を満たすとき精度でPAC学習可能であるという: sup 1∈2 ! 3
, ! > → 0 ( → 0) ここで3 は仮説とtarget conceptの間の何らかのエラーに当たる. 同値な表現:! は任意の, > 0について,ある" (, )が存在して以下を満た すときPAC学習可能: ! 3 , ! > ≤ , ∀ ≥ "
CompML まとめ • 統計的学習理論の準備として幾つかの基礎的な事項をまとめた • 確率収束,概収束 • PAC学習可能性
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.
More Decks by Masanari Kimura
See All by Masanari Kimura
Equivalence of Geodesics and Importance Weighting from the Perspective of Information Geometry
mkimura
0
410
機械学習における重要度重み付けとその応用
mkimura
3
3.8k
Paper Intro: Human Rademacher Complexity
mkimura
0
270
On the principle of Invariant Risk Minimization
mkimura
0
440
論文紹介:Clustering with Bregman Divergences: an Asymptotic Analysis
mkimura
0
680
Generalization Bounds for Set-to-Set Matching with Negative Sampling
mkimura
0
230
論文紹介:On the Importance of Gradients for Detecting Distributional Shifts in the Wild
mkimura
2
980
論文紹介:Dangers of Bayesian Model Averaging under Covariate Shift
mkimura
0
410
Information Geometry of Dropout Training
mkimura
0
390
Other Decks in Research
See All in Research
Empreinte carbone des ovins : une approche globale (technique, économique, environnementale) – 4 années de résultats avec LIFE GREEN SHEEP
institutdelelevage
PRO
0
160
Pesée et pointage par imagerie 3D : PHENO3D entre en phase de test terrains
institutdelelevage
PRO
0
120
Volatilité des marchés et sécheresse historique, l’élevage bovin viande sous contraintes en 2026
institutdelelevage
PRO
0
240
Détection des lésions podales par thermographie infrarouge chez les bovins et les ovins
institutdelelevage
PRO
0
130
Être éleveur dans un monde en transition : Comprendre les changements pour mieux les accompagner
institutdelelevage
PRO
0
160
Du suivi individuel à la sélection animale : comment Digi4Live valorise les données des technologies numériques en élevage
institutdelelevage
PRO
0
130
[最先端NLP勉強会2026] Agentic Rubrics as Contextual Verifiers for SWE Agents
rfujii
1
430
CDCL を用いた MILP の厳密解法
imai448
0
330
PHTalks Bengaluru - SSRF When All Else Fails
dk999
0
1.2k
Prithvi-EO-2.0
satai
3
120
OWASP AISVS - C7
shiell
2
870
Paris et Berlin face à un monde sans repères. Entre convergences et divergences en matière de politique étrangère
ifri
0
130
Featured
See All Featured
HU Berlin: Industrial-Strength Natural Language Processing with spaCy and Prodigy
inesmontani
PRO
0
810
Rails Girls Zürich Keynote
gr2m
96
14k
Digital Ethics as a Driver of Design Innovation
axbom
PRO
2
550
Jess Joyce - The Pitfalls of Following Frameworks
techseoconnect
PRO
1
480
Facilitating Awesome Meetings
lara
57
7.2k
Leveraging Curiosity to Care for An Aging Population
cassininazir
1
570
A Tale of Four Properties
chriscoyier
163
24k
Taking LLMs out of the black box: A practical guide to human-in-the-loop distillation
inesmontani
PRO
3
2.5k
Organizational Design Perspectives: An Ontology of Organizational Design Elements
kimpetersen
PRO
1
880
The Impact of AI in SEO - AI Overviews June 2024 Edition
aleyda
6
1.3k
What does AI have to do with Human Rights?
axbom
PRO
1
2.5k
WENDY [Excerpt]
tessaabrams
15
41k