Questions tagged [vc-dimension]

Question 1

I have this hypothesis class: H = {ha : R → {0, 1} | a > 0, a ∈ R, where ha(x) = 1−a,a = { 1, x ∈ [−a, a] 0, x ̸ ∈ [−a, a] } I need to compute the growth function for m>= 0. So I think that this ...

Question 2

This is usually shown by an application of the Statistical No Free Lunch Theorem. But is this possible to show this by working simply with the definition of PAC learnability and the sample complexity ...

Question 3

Statement : A half space is set of all points on one side of a linear separator, i.e., a set of the form $\{x \mid w^{T}x \ge t\}$. The VC-dimension of half spaces in $d$-dimensions is at least $d+1$. ...

Question 4

VC dimension covers the binary classification case, i.e. when we want to get a predictor $X \to \{0, 1\}$. Using VC dimension, we can get the upper bound on the sample complexity for PAC-learning. In ...

Question 5

Suppose a real-valued function class $\mathcal{F}$ with pseudo dimension less than $d$, I am wondering what is the pseudo dimension of the following function class \begin{equation} \mathcal{F}_2 = \{\...

Question 6

I am trying to determine some bounds for sample complexity. Suppose we have a bounded loss function $\ell$ and target function $f:\mathcal{X}\to\mathcal{Y}$. Hypothesis $h$ is learned, then the ...

Question 7

Let $H_{1}$ and $H_{2}$ are two hypothesis classes over some domain $X$1. If both $H_{1}$ and $H_{2}$ have the uniform convergence property, then do $H_{1}$ U $H_{2}$ have uniform convergence?

Question 8

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

Question 9

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

Question 10

I still have some doubts for finding the VC-dimension. Suppose $\mathcal{H}$ has VC-dimension $n$. This is the process of how I think about it: (1) Show that there is a set of $n$ points that can be ...

Question 11

I have researched this topic in the last time, but no usefull results for me. So I'm here and I please you to help me with the following problem: What is $VCdim$($\mathcal{H}$), where $\mathcal{H}$ is ...

Question 12

What is the VC Dimension of the class of $k$-dimensional cross-polytope (1-norm ($l_1$) balls)? A $k$-dimensional $l_1$ ball with radius $r\in \mathcal R$ and center $\mathbb v\in \mathcal R^k$ is $\{\...

Question 13

Let's say there are two sets of affine functions. $\mathcal{A} = \{ax +b \mid a,b \in \mathbb{R}\}$ $\mathcal{H} = \{2x + 1, x, 3x + 4, 4x\}$ I know that the $\mathrm{Pdim}(\mathcal{A}) = 2$. From ...

Question 14

I have found this exercise and I cannot solve it: In $X=\mathbb R^2$, let's observe two models $H_1$ (rectangle with sides parallel to the coordinate axes) and $H_2$ (lines). We define a model $H_3$ ...

Question 15

This is a problem of VC that I've been trying to solve. Any help is appreciated. Let's assume hypothesis classes $H_{\mathit{init}}$ of initial segments over domain $X = \mathbb R$ and $H_{\mathit{...

Stack Exchange Network

Questions tagged [vc-dimension]

How to calculate the growth function of a hypothesis class?

Infinite VC Dim not PAC learnable

How can I understand the proof of the VC dimension of half-spaces in d-dimensions?

Multi-class sample complexity for PAC learning using "VC dimension"

pseudo dimension of the minimum of functions

Hoeffding's inequality applicability for sample complexity

Uniform convergence of union of hypothesis

Question about machine learning

prove that 2 collection have the same VC-dimensions

Proof of Calculating VC-Dimensions

VCdim of concentric circles

VC Dimension of the class of $k$-dimensional cross-polytope (1-norm ($l_1$) ball)

Pseudo-dimension of a subset of affine functions

VC dimension of a combination of two hypothesis classes

VC dimension of axis-aligned hyperplanes and their complements

Hot Network Questions