View Single Post
Old 04-30-2013, 04:13 AM
Elroch Elroch is offline
Invited Guest
Join Date: Mar 2013
Posts: 143
Default Re: Q10 higher bound

A useful little construction is this.

If you have two underlying disjoint sets of points A and B, and hypothesis sets \mathcal H_A \subset 2^A and \mathcal H_B \subset 2^B (where 2^S is the set of subsets of S), then you can can form a new hypothesis set \mathcal H_{ A X B} \subset 2^{A \cup B} with one hypothesis for each pair of hypotheses in \mathcal H_A and \mathcal H_B (in the obvious way). There is a simple relationship between the VC-dimensions of these three hypothesis sets, which can be used in examples.
Reply With Quote