Shattering: Difference between revisions

Revision as of 20:01, 15 July 2019

Let $X$ be a set of objects one wants to label as 0 or 1, and let $H$ be a class of functions from $X$ to ${0, 1}$ , called a hypothesis class. Let $S = {p_{1}, \dots, p_{n}} \subseteq X$ be a set of points in $X$ . The hypothesis class $H$ shatters $S$ iff for every label assignment $f : S \to {0, 1}$ there exists some $h \in H$ such that $h (p) = f (p)$ for all $p \in S$ .

We can use the idea of function restriction to restate this idea:

The hypothesis class $H$ shatters $S$ iff for every label assignment $f : S \to {0, 1}$ there exists some $h \in H$ such that $h |_{S} = f$ .

The hypothesis class $H$ shatters $S$ iff ${h |_{S} : h \in H} = {0, 1}^{S}$ .

Since functions going into ${0, 1}$ can be seen as subsets of the domain, we can also state the definition using just sets. Let $H' = {h^{- 1} ({1}) : h \in H}$ be the set of possible regions that the hypothesis class can label as positive.

The hypothesis class $H$ shatters $S$ iff for each subset $E$ of $S$ there exists some set $H \in {H^{'}}^{'}$ such that $E = H \cap S$ .

The hypothesis class $H$ shatters $S$ iff $P (S) = {H \cap S : H \in {H^{'}}^{'}}$ .

References

https://en.wikipedia.org/wiki/Shattered_set

Understanding Machine Learning, chapter on VC dimension.

Revision as of 20:00, 15 July 2019 (view source) IssaRice (talk \| contribs) (Created page with "Let <math>\mathcal H</math> be a class of functions from <math>\mathcal X</math> to <math>\{0,1\}</math>, called a hypothesis class. Let <math>S = \{p_1, \ldots, p_n\} \subset...")		Revision as of 20:01, 15 July 2019 (view source) IssaRice (talk \| contribs) No edit summary Newer edit →
Line 1:		Line 1:
	Let <math>\mathcal H</math> be a class of functions from <math>\mathcal X</math> to <math>\{0,1\}</math>, called a hypothesis class. Let <math>S = \{p_1, \ldots, p_n\} \subseteq \mathcal X</math> be a set of points in <math>\mathcal X</math>. The hypothesis class <math>\mathcal H</math> shatters <math>S</math> iff for every label assignment <math>f : S \to \{0,1\}</math> there exists some <math>h \in \mathcal H</math> such that <math>h(p) = f(p)</math> for all <math>p \in S</math>.		Let <math>\mathcal X</math> be a set of objects one wants to label as 0 or 1, and let <math>\mathcal H</math> be a class of functions from <math>\mathcal X</math> to <math>\{0,1\}</math>, called a hypothesis class. Let <math>S = \{p_1, \ldots, p_n\} \subseteq \mathcal X</math> be a set of points in <math>\mathcal X</math>. The hypothesis class <math>\mathcal H</math> shatters <math>S</math> iff for every label assignment <math>f : S \to \{0,1\}</math> there exists some <math>h \in \mathcal H</math> such that <math>h(p) = f(p)</math> for all <math>p \in S</math>.

	We can use the idea of function restriction to restate this idea:		We can use the idea of function restriction to restate this idea: