不可知学习)"/>
Agnostic Learning (不可知学习)
Agnostic Learning (不可知学习)
Computational Learning Theory (Cont.)
The Vapnik-Chervonenkis(VC) dimension
- Shattering a set of instances
- VC dimension- Definition and several examples
The Vapnik-Chervonenkis(VC) dimension
- An unbiased hypothesis spaceis one that shatters the instance space X.
- Sometimes X cannotbe shattered by H, but a large subset of it can.
- Definition: The Vapnik-ChervonenkisDimensionVC(H)of hypothesis space Hdefined over instance space X
- is the size of the largestfinite subset of X shattered by H.
- if arbitrarily large finite sets of X can be shattered by H, then VC(H)≡∞
- If we find ONE set of instances of size d that can be shattered, then VC(H) d.
- To show that VC(H)
VC Dim. Examples (1)
- Example 1:
- Instance space X: the set of real numbers
X = R - H is the set of intervals on the real number axis.
- Form of H is: a < x < b
- VC(H) = ?
- Instance space X: the set of real numbers
更多推荐
Agnostic Learning (不可知学习)
发布评论