I've been trying to determine the VC dimension of ellipses which are origin centered and axis aligned. My first approach was to find some equivalence to a threshold classifier function family of the form

$$ H=\big\{\text{ sign}\big(\sum_{x}(Wx)+b\big)\ |\ w \in \mathbb{R}^d, b \in \mathbb{R}\ \big\}$$

For these functions I know the VC dimension is $d+1$, so for axis-aligned origin-centered ellipses I tried

$$ H=\big\{\text{ sign}\big(\sum_{x}(W^2x^2)-R^2\big)\ |\ w \in \mathbb{R}^d, R \in \mathbb{R}\ \big\} $$

I thought from here it would be straightforward but I couldn't figure it out. The limitations on the values that $w,x$ and $b$ (which equals $-R^2$) can get now can affect the dimension, but I'm not sure how.

  • $\begingroup$ do you only want to know the dimension or also a proof? $\endgroup$
    – oW_
    Feb 8, 2018 at 0:23
  • $\begingroup$ The focus is on the proof $\endgroup$
    – AlexFink
    Feb 8, 2018 at 7:48


Your Answer

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

Browse other questions tagged or ask your own question.