# Questions tagged [vc-theory]

The tag has no usage guidance.

30 questions
Filter by
Sorted by
Tagged with
37k views

### What is the exact definition of VC dimension?

I'm studying machine learning from Andrew Ng Stanford lectures and just came across the theory of VC dimensions. According to the lectures and what I understood, the definition of VC dimension can be ...
• 383
37k views

### How to calculate VC-dimension?

Im studying machine learning, and I would like to know how to calculate VC-dimension. For example: $h(x)=\begin{cases} 1 &\mbox{if } a\leq x \leq b \\ 0 & \mbox{else } \end{cases}$, with ...
• 173
11k views

### With regards to VC-dimension, why can you shatter 3 points with circles but not 4 points?

When using VC-dimensions to estimate the capability of a binary classifier, you can find 3 points in R2 that can be shattered, e.g.: But you can not shatter any 4 points with a circle. This is ...
• 22.1k
3k views

### VC dimension of hypothesis space of finite union of intervals

I have the following concept: $$C = \left\{\bigcup_{i=1}^{k}(a_i, b_i): a_i, b_i \in {\Bbb R}, a_i < b_i, i=1,2,..,k\right\}$$ and was wondering how to determine the VC dimension of C?
870 views

### Why is a lower bound necessary in proofs of VC-dimensions for various examples of hypotheses?

In the book "Foundations of Machine Learning" there are examples of proving the VC dimensions for various hypotheses, e.g., for axis-aligned rectangles, convex polygons, sine functions, hyperplanes, ...
5k views

### Why the VC dimension to this linear hypothesis equal to 3?

I am trying hard to understand this. Here is the scenario: X = R^2 H = { h(x) = x + 10 } I need to calculate the VC dimension for the above linear separator. ...
• 611
88 views

### A question on realizable sample complexity

I came across the following exercise, and I just can't seem to crack it: Let $l$ be some loss function such that $l \leq 1$. Let $H$ be some hypothesis class, and let $A$ be a learning algorithm. ...
180 views

### calculate the VC-dimension [closed]

I have a question about VC-dimension. I have this claim and I need to find out what its VC-dimension is $H\subseteq\{0,1\}^n$ collection of Boolean functions over n In my opinion the answer should ...
• 121
124 views

### VC Dimensions in Machine Learning

Hello I'm learning about VC dimensions in machine learning. The class of classifiers $H$ where $h \in H$ if $h \in \mathbb{R} \rightarrow \{0,1\}$ is what I believe is simply binary classifiers (with ...
• 21
237 views

### Find VC dimension

I'm studying theoretical machine learning at university, and I have this problem in textbook, that I have no Idea how to start. In space $X=R^2$ are given two models $H_1$ (rectangle with sides ...
157 views

### Intuition behind Occam's Learner Algorithm using VC-Dimension

So I'm learning about Occam's Learning algorithm and PAC-Learning where for a given hypothesis space $H$, if we want to have a model/hypothesis $h$ that has an True error of $error_D \leq \epsilon$, ...
• 101
594 views

### How to determine the VC Dimension of axis-aligned, origin-centered ellipses?

I've been trying to determine the VC dimension of ellipses which are origin centered and axis aligned. My first approach was to find some equivalence to a threshold classifier function family of the ...
• 21
1 vote
258 views

### VC-dimension of the infinite set of convex bodies?

I try to find and prove the VC-dimension of the infinite set of (uni-directional) convex bodies. From intuition, it's clear to me that it goes to infinity, but I don't know the correct way to prove it ...
• 113
1 vote
37 views

### Disproving or proving claim that if VCdim is "n" then it is possible that a set of smaller size is not shattered

Today in the lecture the lecturer said something I found peculiar, and I felt very inconvenient when I heard it: He claimed, that if the maximal VCdim of some hypothesis class is $n\in\mathbb N$, then ...
• 11
1 vote
511 views

### VC dimension of half spaces over the real line

I'm studying VC dimension and I'm having a little difficulty understanding it. I read lots of explanations, but when I come across this simple exercise I did not get a good intuition. The problem is ...
1 vote
47 views

### Occam's factor and the VC dimension

I was watching this lecture by Prof. Dr. Philipp Hennig (Probabilistic ML) and when he reached this formula which is the type two maximum log likelihood I had the following question: The Occam's ...
1 vote