# Questions tagged [vc-theory]

The tag has no usage guidance.

11 questions
Filter by
Sorted by
Tagged with
19 views

### Growth function of a 6-dimensional linear classifier

In our course, we are dealing with a d-dimensional classification problem ($\chi = \mathbb{R}^{d}$ as our input space, and $y = \{-1,+1\}$). Our hypothesis class $H$ consists of all hypotheses of the ...
63 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 ...
64 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, ...
285 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?
50 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. ...
822 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. ...
106 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$, ...
4k 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 ...
245 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 ...
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 ...