机器学习基石 - Theory of Generalization
机器学习基石上 (Machine Learning Foundations)—Mathematical Foundations
Hsuan-Tien Lin, 林轩田,副教授 (Associate Professor),资讯工程学系 (Computer Science and Information Engineering)
Theory of Generalization
Restriction of Break Points
- growth function : max number of dichotomies
- 漏出一线曙光的点 break point
- break point restricts maximum possible a lot for
Bounding Function: Basic Cases
-
: maximum possible when break point = k
- 表格
Bounding Function: Inductive Cases
-
的估计
- Putting It All Together
-
- 数学归纳法
- actually can be
- can bound by only one break point
A Pictorial Proof
- Step 1: Replace by
- Step 2: Decompose by Kind
- Step 3: Use Hoeffding without Replacement
- Vapnik-Chervonenkis (VC) bound