本文共 1024 字,大约阅读时间需要 3 分钟。
(Machine Learning Foundations)—Mathematical Foundations
,副教授 (Associate Professor),资讯工程学系 (Computer Science and Information Engineering)
Theory of Generalization
Restriction of Break Points
- growth function mH(N) m H ( N ) : max number of dichotomies
- 漏出一线曙光的点 break point
- break point k k restricts maximum possible mH(N) a lot for N>k N > k
Bounding Function: Basic Cases
- B(N,k) B ( N , k ) : maximum possible mH(N) m H ( N ) when break point = k
- 表格
Bounding Function: Inductive Cases
- B(4,3) B ( 4 , 3 ) 的估计
- Putting It All Together
- B(N,k)≤∑k−1i=0(Ni) B ( N , k ) ≤ ∑ i = 0 k − 1 ( N i )
- 数学归纳法
- C iN−1+C i+1N−1=C i+1N C N − 1 i + C N − 1 i + 1 = C N i + 1
- actually ≤ ≤ can be = =
- B(N,k)≥2B(N−1,k−1)+(B(N−1,k)−B(N−1,k−1))
- can bound mH(N) m H ( N ) by only one break point
A Pictorial Proof
- Step 1: Replace Eout E o u t by E ′in E i n ′
- Step 2: Decompose H H by Kind
- Step 3: Use Hoeffding without Replacement
- Vapnik-Chervonenkis (VC) bound