7
$\begingroup$

Define a binary classifier for points in the complex plane, whose parameter $\theta$ is an isometry of $\mathbb{C}$, and which classifies $z \in \mathbb{C}$ based on whether or not $\theta(z)$ is in the Mandelbrot set.

Two questions:

  1. What is the VC dimension of this classifier? My intuition strongly says that it should be infinite.

  2. Even more strongly, does this classifier shatter all finite sets of points if we also allow scaling in $\theta$ (that is, $\theta$ is a similarity)?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Here's a rephrasing of your question 2 (essentially unpacking the definition). Let $A$ and $B$ be two disjoint finite subsets of $\mathbb C$. Does there exist a similarity $\theta:\mathbb C\to\mathbb C$ of the complex plane such that $\theta(A)$ is contained in the Mandelbrot set, and $\theta(B)$ is contained in the complement of the Mandelbrot set? $\endgroup$
    – André Henriques
    Commented Dec 18, 2015 at 9:39
  • $\begingroup$ I made a little numerical progress on this. By writing a program that does blind brute-force search I found a set of 12 points that I could shatter, showing numerically that the VC dimension is at least 12. To get much beyond this I'll clearly need a less brute-force approach, though. $\endgroup$
    – Peter Schmidt-Nielsen
    Commented Dec 21, 2015 at 7:02
  • $\begingroup$ Good question. Since even a sinusoid, appropriately scaled and shifted, has infinite VC-dim, I would wager that so does the Mandelbrot set. I remain agnostic regarding the stronger claim. $\endgroup$
    – Aryeh Kontorovich
    Commented Jul 18, 2016 at 20:28

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .