View Single Post
Old 04-18-2013, 06:25 AM
Elroch Elroch is offline
Invited Guest
Join Date: Mar 2013
Posts: 143
Default VC dimension puzzle

Pondering the loose relationship between parametrisation of a hypothesis set and VC dimension d_{VC} (or the minimum break point, d_{VC} + 1) led me to the following example and puzzle.

Let the set of points be the natural numbers \{1, 2, 3, ...\}

Let elements of the hypothesis set be made up of alternating intervals of the same size, like a 1-dimensional checkerboard with varying scale

H_n = \{1, 2, ... n\} \cup \{2n+1, 2n+2, ..., 3n\} \cup \{4n+1, 4n+2, ... 5n\} \cup ...

What is the VC dimension of this hypothesis set?

[there is also a continuous version on the real line, but all the structure is in this simplified version]
Reply With Quote