5,337
edits
Machine Learning: Difference between revisions
→VC dimension
| Line 33: | Line 33: | ||
The VC dimension of a model <math>f</math> is the maximum number of points that can be arranged so that <math>f</math> shatters them. | The VC dimension of a model <math>f</math> is the maximum number of points that can be arranged so that <math>f</math> shatters them. | ||
More formally, it is the maximum cardinal <math>D</math> such that some data point set of cardinality <math>D</math> can be shattered by <math>f</math>. | More formally, it is the maximum cardinal <math>D</math> such that some data point set of cardinality <math>D</math> can be shattered by <math>f</math>. | ||
;Notes | |||
* To show VCdim is at least n, find a training set of size n that can be shattered by our hypothesis class. | |||
* To show VCdim is leq n, prove no training set of size n+1 can be shattered by our hypothesis class. | |||