Define $$l_i(x) := \text{sgn} \left( w_i^\top x - b_i \right)$$

for $i=1,...,n$, where $x \in \mathbb{R}^d$.

Then define the classifier

$$ g(x) := \max \{ l_1(x),..., l_n(x) \}$$

which represents the intersection of $n$ linear functions and hence a convex polytope in $\mathbb{R}^d$ with $n$ facets.

What is the VC dimension of the family of all $g$ of this form?

I found that an upper bound is $2 (d+1) n \text{log}_2( (d+1)n ).$

  • 1
    $\begingroup$ VC dimension is normally defined for range spaces — pairs $(X, R)$ where $X$ is a set of points and $R\subseteq 2^X$ is a set of subsets of $X$ called ranges. (Range spaces are also called set systems.) I assume you want $X$ to be a convex polyhedron, but what are your ranges? Or is $X=\mathbb{R}^n$ and $R$ the set of convex polyhedra? $\endgroup$ – Jeffε May 2 '13 at 14:13
  • $\begingroup$ I mean that $X$ is a convex polyhedron in dimension $n$ formed by the intersection of $n$ half-spaces. $\endgroup$ – user693 May 2 '13 at 15:05
  • 1
    $\begingroup$ And what is $R$? $\endgroup$ – Jeffε May 2 '13 at 16:00
  • 3
    $\begingroup$ on the off chance that you got confused and meant to say that $X$ is $\mathbb{R}^n$ and $R$ is all translates of a convex polytope, does this answer your question: arxiv.org/pdf/0907.5223v2.pdf (the VC-dimension is infinite in $n=3$ and at most $3$ in $n=2$) $\endgroup$ – Sasho Nikolov May 2 '13 at 18:55
  • 2
    $\begingroup$ so you actually mean the range space of all convex polytopes, taken as subsets of $\mathbb{R}^n$. you should understand that the VC dimension of "a polytope" is 0, because it's a single set! you need some family of sets here. $\endgroup$ – Sasho Nikolov May 2 '13 at 20:48

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.