Ε-net

From Freepedia

The title of this article is incorrect due to technical limitations. The correct title is {{{title|{{{1}}}}}}.

Let <math>P</math> be a probability distribution over some set <math>X</math>. An <math>\epsilon</math>-net for a class <math>H \subseteq 2^X</math> of subsets of <math>X</math> is any subset <math>S \subseteq X</math> such that for any <math>h \in H</math>

<math> P(h) \ge \epsilon \quad \Longrightarrow \quad S\cap h \neq \emptyset </math>

Intuitively <math>S</math> approximates the probability distribution.

Stronger notion is <math>\epsilon</math>-approximation. An <math>\epsilon</math>-approximation for class <math>H</math> is subset <math>S \subseteq X</math> such that for any <math>h \in H</math> it holds

<math> \left| P(h) - \frac{|S \cap h|}{|S|} \right| < \epsilon </math>