1
$\begingroup$

Let $\mathcal{C}$ be a pointed, salient cone in $\mathbb{R}^d$. We may also assume that $\mathcal{C}$ is full-dimensional. Consider the set of binary classifiers $$\mathcal{H} = \{\boldsymbol{x}\mapsto\boldsymbol{1}\hspace{-0.9ex}\mathrm{1}(\boldsymbol{h}^\mathsf{T}\boldsymbol{x}\ge 0)\mid \boldsymbol{h} \in \mathcal{C} \}.$$ Is there any bound known for the VC-dimension of $\mathcal{H}$ that depends on $\mathcal{C}$ and can be significantly better than the VC-dimension of the set of all (linear) classifiers in $\mathbb{R}^d$ (i.e., $d$)?

Edit: Above, $\boldsymbol{1}\hspace{-0.9ex}\mathrm{1}(\cdot)$ denotes the binary indicator function. So a more explicit definition of $\mathcal{H}$ is the set of functions $$f_\boldsymbol{h}(\boldsymbol{x})=\begin{cases} 0 & \text{if }\boldsymbol{h}^\mathsf{T}\boldsymbol{x}<0 \\ 1 & \text{if }\boldsymbol{h}^\mathsf{T}\boldsymbol{x}\ge0\end{cases},$$ parametrized by $\boldsymbol{h}\in \mathcal{C}$.

Improve this question
$\endgroup$
9
  • $\begingroup$ I'm sorry but I don't understand your notation. What is $\mathcal H$? $\endgroup$
    – domotorp
    Commented Aug 30, 2016 at 20:35
  • $\begingroup$ @domotorp I have explained the notation in added edit line. I hope the definition of $\mathcal{H}$ is clear now. $\endgroup$
    – S.B.
    Commented Aug 30, 2016 at 21:09
  • $\begingroup$ Thx, now it's clear. I just wonder why you use functions instead of sets, so I would define $S_h=\{x \mid h^Tx\ge 0\}$. $\endgroup$
    – domotorp
    Commented Aug 31, 2016 at 4:04
  • $\begingroup$ Also, being pointed or salient doesn't change much, at most a factor of two. $\endgroup$
    – domotorp
    Commented Aug 31, 2016 at 4:07
  • $\begingroup$ And there's one more thing missing - what are (linear) classifiers? $\endgroup$
    – domotorp
    Commented Aug 31, 2016 at 4:09

1 Answer 1

Reset to default
2
$\begingroup$

No, I claim that the set of $d$ unit vectors, $e_1=(1,0,\ldots,0)$, $e_2=(0,1,0,\ldots,0)$, $\ldots,$ $e_d=(0,\ldots,0,1)$, along the axes can be shattered, except that for every $\mathcal H$ either the empty set, or all $d$ of the won't be in any $h\in \mathcal H$, so the VC-dimension is $d-1$. (For similar reasons, it cannot be $d$ for any point set.)

Indeed, if $\mathcal H$ is the opposite of the cone spanned by the above $d$ vectors, i.e., the all-negative hyperoctant, and $h_I=-\sum_{i\in I} e_i$, then $f_h(e_i)=0$ if and only if $i\in I$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Is this independent of the cone $\mathcal{C}$ (i.e., the domain where $\boldsymbol{h}$ lives in)? $\endgroup$
    – S.B.
    Commented Aug 31, 2016 at 22:33
  • $\begingroup$ If I understood your answer correctly, you are taking the cone to be the positive (or the negative) orthant. Does it generalize to arbitrary cones? $\endgroup$
    – S.B.
    Commented Aug 31, 2016 at 22:47
  • $\begingroup$ Yes, it works the same for any full-dimensional cone, you just have to replace the $e_i$ with other vectors whose negation is in the cone. $\endgroup$
    – domotorp
    Commented Sep 1, 2016 at 5:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .