Questions tagged [vc-theory]

For questions related to the Vapnik–Chervonenkis theory (also known as VC theory), which a form of computational learning theory, so it attempts to explain the learning process from a statistical point of view, developed during 1960–1990 by Vladimir Vapnik and Alexey Chervonenkis.

Filter by
Sorted by
Tagged with
1
vote
1answer
52 views

VC Dimension of Reinforcement Learning (RL)

Is the VC dimension meaningful for the reinforcement learning (RL) as a machine learning (ML) method? How?
1
vote
1answer
49 views

What do we mean by saying “VC dimension gives a LOOSE, not TIGHT bound”?

From what I understand VC dimension is what establishes the feasibility of learning for infinite hypothesis sets, the only kind we would use in practice. But, the literature (i.e. Learning from Data)...
5
votes
4answers
394 views

How does size of the dataset depend on VC dimension?

This might be a little broad question, but I have been watching Caltech youtube videos on Machine Learning, and in this video prof. is trying to explain how we should interpret VC dimension in terms ...
1
vote
1answer
50 views

Understanding relation between VC Symmetrization Lemma and Generalization Bounds

I am new in the field of Machine Learning so I wanted to start of by reading more about mathematics and history behind it. I am currently reading, in my opinion, a very good and descriptive paper on ...
1
vote
0answers
43 views

Why does the growth function need to be polynomial in order for the learning algorithm to be consistent?

Could someone please explain to me why in VC theory, specifically, when calculating the VC dimension, the growth function needs to be polynomial in order for the learning algorithm to be consistent? ...
0
votes
1answer
50 views

What are the prior beliefs in a neural network? (if any)

Let us confine ourselves to the case where we have a $n$ dimensional input and a $+1$ or $-1$ output. It can be shown that: For every $n$, there exists a dense NN of depth 2, such that it ...
1
vote
1answer
39 views

Can feature engineering change the selection of the model according to the minimum description length?

The definition of MDL according to these slides is: The minimum description length (MDL) criteria in machine learning says that the best description of the data is given by the model which ...
2
votes
1answer
80 views

How to prove $\mathcal H$ with VC dimension $d$ shatter all subsets with size less than $d-1$?

I was wondering that if a certain hypothesis class $H$ has a VC dimension $d$ over domain $X$ how to prove that $H$ will shatter all subsets of $X$ with size less than $d$ i.e $H$ will shatter $A \...
5
votes
1answer
118 views

Are PAC learning and VC dimension relevant to machine learning in practice?

Are PAC learning and VC dimension relevant to machine learning in practice? If yes, what is their practical value? To my understanding, there are two hits against these theories. The first is that ...