0
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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. :) $\endgroup$ Commented May 8, 2021 at 14:42
  • 1
    $\begingroup$ @InuyashaYagami I found a definition of page 10 of this pdf $\endgroup$ Commented May 8, 2021 at 15:10
  • $\begingroup$ It would be nice if the definition was self contained in the question. $\endgroup$ Commented May 8, 2021 at 18:27

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.