Lower Bounds on the VC Dimension of Unions of Concept Classes
Lev Reyzin · 2006
In this paper we consider bounds on the VC dimension of a class, Tk(C), that consists of unions of k concepts from class C of VC dimension d. Blumer et al. [1] show that the VC dimension of Tk(C) cannot exceed 2dk log2 3k. By considering grids of points and the class of line segments, we show that it is possible for Tk(C) to have VC dimension 8 5 kd. We also demonstrate that our method cannot produce classes that asymptotically match Blumer et al. upper bound, leaving the gap open for future research. 1