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}$.

$\endgroup$
9
  • $\begingroup$ I'm sorry but I don't understand your notation. What is $\mathcal H$? $\endgroup$
    – domotorp
    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.
    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
    Aug 31, 2016 at 4:04
  • $\begingroup$ Also, being pointed or salient doesn't change much, at most a factor of two. $\endgroup$
    – domotorp
    Aug 31, 2016 at 4:07
  • $\begingroup$ And there's one more thing missing - what are (linear) classifiers? $\endgroup$
    – domotorp
    Aug 31, 2016 at 4:09

1 Answer 1

1
$\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$.

$\endgroup$
3
  • $\begingroup$ Is this independent of the cone $\mathcal{C}$ (i.e., the domain where $\boldsymbol{h}$ lives in)? $\endgroup$
    – S.B.
    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.
    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
    Sep 1, 2016 at 5:27

Your Answer

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

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