As of May 31, 2023, we have updated our Code of Conduct.

Questions tagged [vc-dimension]

The VC dimension (for Vapnik–Chervonenkis dimension) is a measure of the capacity (complexity, expressive power, richness, or flexibility) of a statistical classification algorithm, defined as the cardinality of the largest set of points that the algorithm can shatter.

Filter by
Sorted by
Tagged with
103 votes
7 answers
22k views

Why is deep learning hyped despite bad VC dimension?

The Vapnik–Chervonenkis (VC)-dimension formula for neural networks ranges from $O(E)$ to $O(E^2)$, with $O(E^2V^2)$ in the worst case, where $E$ is the number of edges and $V$ is the number of nodes. ...
yters's user avatar
  • 1,399
6 votes
2 answers
465 views

What is usually the next step after showing the VC dimension?

I am new to statistical learning. I have a structure $X$ where I showed its hypothesis class $H$ has VC dimension $d$. All I know now is that I can bound the number of examples by $m\geq \frac{1}{\...
seteropere's user avatar
4 votes
2 answers
1k views

Is it a problem that "successful" machine learning algorithms have large VC dimension?

In my limited exposure, it appears that "successful" machine learning algorithms tend to have very large VC dimension. For example, XGBoost is famous for being used to win the Higgs Boson Kaggle ...
yters's user avatar
  • 1,399
2 votes
1 answer
78 views

prove that 2 collection have the same VC-dimensions

I'm new here on the site, I'm a final year student in computer science. In a machine learning course, there was a question on a test that I could not understand. The question goes like this: Suppose ...
hah's user avatar
  • 29
0 votes
0 answers
38 views

Question about machine learning

Hello everyone I am new to the site, I have a question that was in the test and did not understand the parts that are in the question. This question from a test I failed to pass, in a machine learning ...
hah's user avatar
  • 29
0 votes
1 answer
616 views

VC dimension of monotone disjunctions of length k over n variables?

There are of course $n \choose k$ monotone disjunctions which bounds the VC dimension at $\log_2 {n \choose k}$. I'm wondering if this is bound at $k \log_2 n$? (Possibly follows from combinatorial ...
djechlin's user avatar
  • 487
0 votes
1 answer
151 views

Classes of circle rims

The input space is a unit circle, $\mathcal{X} = \mathbb{S}^1 \subset \mathbb{R}^2$. There is class $\mathcal{F}$ of arcs on $\mathbb{S}^1$, where a point is labeled 1 if it is on the arc, and 0 ...
user avatar