Pseudo-dimension of a subset of affine functions

Question

Let's say there are two sets of affine functions.

1. $\mathcal{A} = \{ax +b \mid a,b \in \mathbb{R}\}$
2. $\mathcal{H} = \{2x + 1, x, 3x + 4, 4x\}$

I know that the $\mathrm{Pdim}(\mathcal{A}) = 2$. From my understanding the $\mathrm{Pdim}(\mathcal{H})$ is also equal to 2 as I can find $\{x_1, x_2\}$ and $z_1, z_2$ such that for all subsets $T \subseteq \{x_1, x_2\}$, there is a function $f \in \mathcal{H}$ such that $\forall x \in T, f(x) \geq z_1$ and $\forall x \notin T f(x) < z_1$.

Is my intuition correct?

Answer 1

I am using the definition of pseudo-dimension found here, page 10 of the pdf.

Denote $h_1(x) = 2x+1$, $h_2(x) = 4x$, $h_3(x) = x$ and $h_4(x) =3x+4$.

Let's consider $C = (-2, 2)$ a vector. Then $r = (-2.5, 6)$ is a witness that proves that $C$ is pseudo-shattered by $\mathcal{H}$:

• $h_1(-2) = -3 <-2.5$, $h_1(2) = 5 <6$;
• $h_2(-2) = -8 <-2.5$, $h_2(2) = 8 >6$;
• $h_3(-2) = -2>-2.5$, $h_3(2) = 2<6$;
• $h_4(-2) = -2 >-2.5$, $h_4(2) = 10 >6$.

Clearly $\text{Pdim}(\mathcal{H})< 3$ since the pseudo-dimension cannot be greater than $\log_2 |\mathcal{H}|$.

That proves that $\text{Pdim}(\mathcal{H}) = 2$.