1
$\begingroup$

I have researched this topic in the last time, but no usefull results for me. So I'm here and I please you to help me with the following problem:

What is $VCdim$($\mathcal{H}$), where $\mathcal{H}$ is the class of concentric circles centred in origin in the 2D plane?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Can you please define formally this class $\mathcal{H}$? Or at least explain what "concentric circles" means, for us who aren't familiar with this concept? $\endgroup$
    – nir shahar
    Sep 10, 2021 at 11:56
  • 3
    $\begingroup$ I don't even see how concentric circles can shatter any two distinct points at the same distance from the origin, e.g., $(0,1)$ and $(1,0)$. Then the VC dimension is either $0$ or $1$ depending on the details of the model (does the circle include the boundary, and can I place a point on $(0,0)$?) $\endgroup$
    – Steven
    Sep 10, 2021 at 12:22
  • $\begingroup$ @Steven Well, since the circles are pairwise disjoint, they cannot shatter any set of two distinct points. So that should be the answer. $\endgroup$
    – Emil Jeřábek
    Sep 10, 2021 at 12:30
  • 1
    $\begingroup$ @nirshahar en.wikipedia.org/wiki/Concentric_objects $\endgroup$
    – Emil Jeřábek
    Sep 10, 2021 at 12:30

1 Answer 1

Reset to default
1
$\begingroup$

You haven't explained what you mean by circle. Let me consider three possible interpretations:

  1. The set of points at distance exactly $r$ from the origin, for some $r$.
  2. The set of points at distance at most $r$ from the origin, for some $r$.
  3. The set of points at distance less than $r$ from the origin, for some $r$.

In all cases, it is easy to see that the concept class shatters any single point except, possibly, the origin. In contrast, we can show that no set of two points is shattered, and so the VC dimension is 1. Indeed, if $x,y$ are at the same distance from the origin and $C$ is an origin-centered circle, then $x \in C$ iff $y \in C$, and so $\{x,y\}$ is not shattered. If $x$ is closer to the origin from $y$, then in case 1, no origin-centered circle contains both, and in the other two cases, no origin-centered circle contains $y$ but not $x$; in all cases, $\{x,y\}$ is not shattered.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Only 1. is a circle; 2. and 3. are disks. $\endgroup$
    – Emil Jeřábek
    Sep 11, 2021 at 11:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.