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.

7 questions
Filter by
Sorted by
Tagged with
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. ...
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}{\... 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 ... 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 ... 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 ... 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 ... 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 ... 