A problem related to shattering coefficients

Question

I have been working on some problems in my introductory machine learning course, and I have been having some difficulty on problems related to shattering coefficients. To initialize, I'll give some background as to shattering coefficients in general. Take $F$ to be a set and $\mathcal{A}$ to be a set of sets. We say that $\mathcal{A}$ picks out $G \subseteq F$ is there exists an $A \in \mathcal{A}$ such that $F \cap A = G.$ Take $s(\mathcal{A},F)$ to be the number of subsets in $F$ that $\mathcal{A}$ picks out. Take $\mathcal{F}_n = \{F| |F| = n\}.$ The shattering coefficient of $\mathcal{A}$ is defined as $$s_n(\mathcal{A}) = \sup_{F \in \mathcal{F}_n} s(\mathcal{A},F).$$ Take $\mathcal{C} = \mathcal{A} \cup \mathcal{B}.$ I want to show that $$s_n(\mathcal{C}) \leq s_n(\mathcal{A}) + s_n(\mathcal{B}).$$ I had imagined that the first step is to consider $q = s_n(\mathcal{C})$ for some $q \in \mathbb{N}.$ This means that there is some $G \in \mathcal{F}_n$ such that $\mathcal{C}$ picks out $q$ subsets from $G$. I had imagined that given $\mathcal{C} = \mathcal{A} \cup \mathcal{B}$ that in those $q$ subsets, $a$ of them come from $\mathcal{A} \setminus \mathcal{B},$ $b$ of them come from $\mathcal{B} \setminus \mathcal{A}$, and $c$ of them come from $\mathcal{A} \cap \mathcal{B}.$ Thus, $$s_n(\mathcal{C}) = q = a + b + c.$$ However, I am having some difficulty figuring out where to move forward with this, and how $a,b,$ and $c$ might relate to $s_n(\mathcal{A})$ and $s_n(\mathcal{B}).$ Any recommendations?

Answer 1

For any set $F$ and any collection $\cal A$, define $p({\cal A}, F)$ to be the collection of subsets $G\subset F$ that $\cal A$ picks out. Then $s({\cal A}, F)$ is simply the number of elements in $p({\cal A},F)$. Prove the assertion in the following steps:

a. Use the definition of "picks out" to argue that for any set $F$, $$ p({\cal A\cup B},F)\subset p({\cal A},F)\cup p({\cal B}, F).\tag1 $$

b. Since the size of the union of two sets is at most the sum of the individual sizes, we deduce from (1) for any $F$: $$ s({\cal A\cup B},F)\le s({\cal A},F)+ s({\cal B}, F).\tag2 $$

c. Take sups over $F\in{\cal F}_n$ in (2) to deduce $$ s_n({\cal A\cup B})\le s_n({\cal A})+ s_n({\cal B}).\tag3 $$ Intuitively, (3) follows quickly if we view $s({\cal A}, F)$ and $s({\cal B}, F)$ and $s({\cal A\cup B},F)$ as functions of $F$; then (2) is an assertion about pointwise behavior of functions.