# Pseudo-dimension of a subset of affine functions

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?

• Can you please also define what $Pdim(\mathcal{A})$ means? It might be a common term for you. But I am not aware of it. Any weblink would also work. :) May 8 '21 at 14:42
• @InuyashaYagami I found a definition of page 10 of this pdf May 8 '21 at 15:10
• It would be nice if the definition was self contained in the question.
– Jake
May 8 '21 at 18:27

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$$.