Skip to main content
96 votes
Accepted

Why is deep learning hyped despite bad VC dimension?

"If the map and the terrain disagree, trust the terrain." It's not really understood why deep learning works as well as it does, but certainly old concepts from learning theory such as VC ...
Martin Berger's user avatar
71 votes

Why is deep learning hyped despite bad VC dimension?

"Given the inability of Deep Learning to generalize, according to VC dimensional analysis [...]" No, that's not what VC dimensional analysis says. VC dimensional analysis gives some sufficient ...
D.W.'s user avatar
  • 162k
26 votes

Why is deep learning hyped despite bad VC dimension?

Industry people have no regard for VC dimension, hooligans... On a more serious note, although the PAC model is an elegant way to think about learning (in my opinion at least), and is complex enough ...
Ariel's user avatar
  • 13.4k
15 votes

Why is deep learning hyped despite bad VC dimension?

Given the inability of Deep Learning to generalize, I don't know where you take that from. Empirically, generalization is seen as the score (e.g. accuracy) on unseen data. The answer why CNNs are ...
Martin Thoma's user avatar
  • 2,360
12 votes

Why is deep learning hyped despite bad VC dimension?

The one word answer is "regularization". The naive VC dimension formula does not really apply here because regularization requires that the weights not be general. Only a tiny (infinitesimal?) ...
David Khoo's user avatar
5 votes

Is it a problem that "successful" machine learning algorithms have large VC dimension?

When left with a discrepancy between theory and data, data is king. Theory is intended to be predictive -- to make predictions about the world -- but when it fails to predict what we actually observe ...
D.W.'s user avatar
  • 162k
5 votes
Accepted

VC Dimension of Origin-Centered Circle

What you are missing is a definition of origin-centered circles. The definition of the slides (your second link) is wrong, for the reasons you mention. The definition in the lecture notes (your first ...
Yuval Filmus's user avatar
4 votes
Accepted

Do I have the right definition of VC dimension?

A family of hypothesis functions on domain $\cal X$ is a subset of $\{0,1\}^{\cal X}$. A family $H$ shatters a set $S \subseteq \cal X$ if for every subset $T \subseteq S$ there exists a function $h \...
Yuval Filmus's user avatar
3 votes
Accepted

VC dimension of the class of polynomial classifiers of degree $n$

The idea is that a polynomial of degree $n$ has at most $n$ roots, and so can change signs at most $n$ times. Therefore no polynomial of degree $n$ can form an alternating pattern +-+-... or -+-+... ...
Yuval Filmus's user avatar
3 votes
Accepted

How can the VC-dimension of Turing machine be finite?

First, let me correct your definition of VC dimension: it is the largest size of a set which can be shattered. If the VC dimension is $d$, then this means that for every set $C$ of size larger than $...
Yuval Filmus's user avatar
3 votes
Accepted

Is it a problem that "successful" machine learning algorithms have large VC dimension?

To expand my point in your previous post, VC theory (and PAC learning) is a WORST CASE theory. The requirement to handle any possible distribution on the data is too restrictive for real life ...
Ariel's user avatar
  • 13.4k
3 votes

Why is deep learning hyped despite bad VC dimension?

We address the paper: Understanding Deep Learning Requires Rethinking Generalization. in Rethinking generalization requires revisiting old ideas: statistical mechanics approaches and complex learning ...
Charles Martin's user avatar
2 votes

Why is deep learning hyped despite bad VC dimension?

No one seems to have pointed out in the above answers, that the VC dimension formula quoted is only for a 1-layer neural network. My guess is that the VC dimension actually grows exponentially as the ...
Yan King Yin's user avatar
2 votes
Accepted

The VC dimension when the samples are fixed

Suppose were in the realizable model, i.e. we want to learn some $f^*\in\mathcal{H}\subseteq 2^\mathcal{X}$ where $VCdim(\mathcal{H})=d$. Let $M(\epsilon,\delta)$ be the minimal number of samples ...
Ariel's user avatar
  • 13.4k
2 votes
Accepted

VC dimensions: Let ${x_1, \ldots, x_N}$ be $N$ labelled points on $\mathbb{R}$, then there exists a sinusoid that separates these points

Here are some ideas. Denote by $\{x\}$ the fractional value of $x$, and consider the function $f_n(x) = \operatorname{sgn} (\sin 2\pi n x)$. Then: $f_n(x) = +1$ iff $\{nx\} \in (0,1/2)$. $f_n(x) = -1$...
Yuval Filmus's user avatar
2 votes

Geometric intuition behind VC-dimension

The VC dimension is a complexity measure for a family of boolean functions over some domain $\mathcal{X}$. Families who allow "richer" behavior have a higher VC dimension. Since $\mathcal{X}$ can be ...
Ariel's user avatar
  • 13.4k
2 votes
Accepted

PAC learning vs. learning on uniform distribution

Is there a case where a class $\mathcal{F}$ is not efficiently PAC learnable, yet it is efficiently learnable on the uniform distribution? This has been asked on TCS.SE. It looks like the short ...
Caleb Stanford's user avatar
2 votes

What is the VC dimension of the hypothesis class $H=\left\{f_{\theta_{1}, \theta_{2}}: R^{2} \rightarrow\{0,1\} \mid 0<\theta_{1}<\theta_{2}\right\}$?

The VC-dimension of your hypothesis class $\mathcal H$ is 2. To see this, we begin by showing that $\mathcal H$ shatters any 2-element set $\{(a_1 a_2), (b_1, b_2)\}$ of real numbers where all ...
Watercrystal's user avatar
  • 1,526
1 vote

Uniform convergence of union of hypothesis

Let's start with the definition. A hypothesis class $\mathcal{H}$ has uniform convergence if for every $\epsilon,\delta>0$ there exists $m = m(\epsilon,\delta)$ such that the following holds for ...
Yuval Filmus's user avatar
1 vote

prove that 2 collection have the same VC-dimensions

Every $f \in F$ is mapped to $f' \in F'$ defined as follows: $f'|_{\Omega \times \{0\}} = f$ and $f'|_{\Omega \times \{1\}} = 1 - f$. Let us call a subset of $\Omega'$ mixed if it contains both $(\...
Yuval Filmus's user avatar
1 vote

Proof of Calculating VC-Dimensions

The VC-dimension of a hypothesis class $\mathcal{H}$ is the maximal size of a set shattered by $\mathcal{H}$, if such a maximal size exists, and $\infty$ otherwise. Therefore to prove that the VC-...
Yuval Filmus's user avatar
1 vote

VCdim of concentric circles

You haven't explained what you mean by circle. Let me consider three possible interpretations: The set of points at distance exactly $r$ from the origin, for some $r$. The set of points at distance ...
Yuval Filmus's user avatar
1 vote
Accepted

Pseudo-dimension of a subset of affine functions

I am using the definition of pseudo-dimension found here, page 10 of the pdf. Denote $h_1(x) = 2x+1$, $h_2(x) = 4x$, $h_3(x) = x$ and $h_4(x) =3x+4$. Let's consider $C = (-2, 2)$ a vector. Then $r = (-...
Nathaniel's user avatar
  • 15.8k
1 vote
Accepted

VC dimension of set of functions

This is a classical result of Assouad (Densité et dimension) about dual VC dimension. Let $A$ be a binary matrix. The VC dimension of $A$ is the maximal size of a set $S$ of columns which are ...
Yuval Filmus's user avatar
1 vote
Accepted

Understanding growth function of closed intervals in $\mathbb{R}$

Let the real numbers be $r_1 < \cdots < r_m$. The intersection $H \cap C$ could be of the form $\{r_i,\ldots,r_j\}$ for $1 \leq i \leq j \leq m$, or empty. There are $\binom{m+1}{2}$ of the ...
Yuval Filmus's user avatar
1 vote

VC dimension of only the rim of a unit disk

Let us prove the following general result: Let $\mathcal F$ be a class of functions from $\mathcal X$ to $\{0,1\}$. If $\mathcal F$ has VC dimension $d$ then $|\mathcal F| \geq 2^d$. Indeed, if $\...
Yuval Filmus's user avatar
1 vote

VC dimension of finite unions of one-sided intervals

Finite unions of one-sided intervals can shatter only 2 points, because as said by @YuvalFilmus in comments the union of Finite unions is a single one-sided interval, and a single one-sided interval ...
Joshna Gunturu's user avatar
1 vote
Accepted

Uniform Convergence and VC Theroy

What is considered in VC theory is about the bound of error between empirical risk and real expected risk. Hence, the worst-case function is when the difference between these two risks is maximized.
OmG's user avatar
  • 3,572
1 vote
Accepted

Proof of uniform convergence if VC dimension is finite

Let $X = |L_\mathcal{D}(h) - L_S(h)|$. The statement on the expectation of the supremum of $X$ implies, in particular, that for some $M$, $$ \mathbb{E}[X] \leq M. $$ Since $X \geq 0$, Markov's ...
Yuval Filmus's user avatar
1 vote

VC dimension of the class of polynomial classifiers of degree $n$

Here is a proof (not the only one). This proof appeals to the fact that our hypothesis class is a subset of a linear hypothesis class of degree $n+1$. Let $\cal{P}_n$ denote the set of all d-degree ...
Selina Carter's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible