91

"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 dimensions appear not to be very helpful. The matter is hotly debated, see e.g.: H. W. Lin, M. Tegmark, D. Rolnick, Why does deep and cheap learning work so well?...


69

"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 conditions under which generalization is guaranteed. But the converse ain't necessarily so. Even if you fail to meet those conditions, the ML method still might ...


26

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 to give rise to interesting concepts and questions (such as VC dimension and its connection to sample complexity), it has very little to do with real life ...


15

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 used is simple: CNNs work much better than anything else. See ImageNet 2012 for example: CNNs: 15.315% (that was an early example. CNNs are much better now. At ...


12

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?) proportion of weight combinations have acceptable loss after regularization. The true dimension is many orders of magnitude less as a result, so generalization can ...


6

If, as you've stated, you're interested in coming up with a PAC learning algorithm then finite VC-dimension is a prerequisite. This follows from what is sometimes referred to as the Fundamental Theorem of Statistical Learning Theory. In brief this results says that if a concept class $C$ has finite VC-dimension $d$ then a learning algorithm that produces a ...


6

A distinction should be made between constructing practical machine learning algorithms and theoretical algorithms, such as PAC learning algorithms. A machine learning practitioner doesn't usually invoke the concept of VC dimension — indeed, many of them probably have never heard of it, especially if they're applying machine learning in some other ...


5

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 and experience, when its predictions disagree with our experience, then there is obviously something lacking in the theory. In this case, VC theory just isn't ...


5

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 link) makes it clear that you can choose whether it is the inside or the outside of the circle which gets the value +1, and this shows that any two points whose ...


4

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 \in H$ such that $h(s) = 1_{s \in T}$ for all $s \in S$, that is, $h(s) = 1$ if $s \in T$ and $h(s) = 0$ if $s \in S \setminus T$. A singleton family $H$ cannot ...


3

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 $d$ there exists a function $f\colon C \to \{0,1\}$ which is not compatible with any function computed by an $n$-state Turing machine. You are attempting to ...


3

We address the paper: Understanding Deep Learning Requires Rethinking Generalization. in Rethinking generalization requires revisiting old ideas: statistical mechanics approaches and complex learning behavior Charles H. Martin and Michael W. Mahoney See: https://arxiv.org/pdf/1710.09553.pdf Basically, we argue that the VC bounds are too loose because the ...


3

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 applications. If $\mathcal{C}\subseteq 2^\mathcal{X}$ is a concept class with high VC dimension, there might still be an algorithm that achieves small generalization ...


3

So this result pertains to the online mistake bound framework. I found a proof here in Shai Shalev-Shwartz's lecture notes. I'll give a rough sketch of it here for the sake of keeping things self contained. One way to think of online learning is a game between the learner and an adversarial environment. The environment produces an example $x_t$ at time $t$....


2

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 required to obtain an error of at most $\epsilon$ with probability at least $1-\delta$. Since the bound you mentioned on $M(\epsilon, \delta)$ holds for any ...


2

Suppose you're aiming for a specific error rate. Suppose for the moment that there is no training error. You have an inequality involving all your known parameters and the unknown $m$, and you can solve it to obtain a value of $m$ that guarantees the specific true error rate, assuming that there is no training error. If you then run classification, you can ...


2

Yes, an open interval in $\mathbb{R}$ is defined as $(a,b) = ]a,b[ = \left \{ x \in \mathbb{R}|\,a<x<b\right \} $. It has two parameters $a$ and $b$. The sets of all open intervals, i.e. $\left \{ \left \{ x \in \mathbb{R}|\,a<x<b\right \} | a,b \in \mathbb{R}\right\}$ has a VC dimension of 2 for the reason you mention. Keep in mind that the VC ...


2

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$ iff $\{nx\} \in (1/2,1)$. Suppose first that the set of points is independent over the rationals. Weyl's equidistribution theorem shows that $\{nx_1\},\ldots,...


2

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 arbitrary, there isn't a general geometric interpretation. However, if you think of $\mathcal{X}$ as $\mathbb{R}^d$, then you can think of binary functions as ...


2

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 -+-+... of length $n+2$. This shows that the VC dimension is at most $n+1$. On the other hand, for any set of $n+1$ pairs $(x_1,y_1),\ldots,(x_{n+1},y_{n+1})$, there is ...


2

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 answer is yes -- Aaron Roth gives the example of width-$k$ conjunctions for $k \gg \log n$. And in the comments, Avrim Blum is quoted as giving the answer of $2$-...


2

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 components of the pairs are positive: $\emptyset$ is accounted for by $f_{c, c + \varepsilon}$ for any real $c$ such that $ca_1 \neq a_a$ and $cb_1 \neq b_2$ and some ...


1

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 $\mathcal F$ has VC dimension $d$ then $\mathcal F$ shatters some set $S \subseteq \mathcal X$ of size $d$. This means that for any function $\phi\colon S \to \{0,...


1

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.


1

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 inequality implies that $$ \Pr\left[X \geq \frac{M}{\delta}\right] \leq \delta. $$ This implies that $$ \Pr\left[X \leq \frac{M}{\delta}\right] \geq \Pr\left[X < \...


1

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 can shatter only 2 points.


1

Assume that the points on the circle are considered inside. With that if you have 2 points at an equal distance from the origin, you cannot label one + and the other -. Either both are in or both are out. On the contrary for 3 points with varying distance from the origin, you can label them +, -, +. This arrangement cannot be shattered. Hence the VC ...


1

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 number of layers L increases. My reasoning is based on considering deep neural networks where the activation function is replaced by polynomial ones. Then ...


1

I assume a half interval $I_a$ is always of the form $$ \{(-\infty \leq x \leq a) \mid a \in \mathbb{R}\} $$ This means that all points equal or smaller than $a$ belong to the interval. Now, choose any set $S = \{y,z\} \subset \mathbb{R}$ such that $y < z$. $S$ is not shattered, since it is impossible to find a half interval $I_a$ such that $S \cap I_a =...


1

First, observe that it is enough to prove that $d\le d'$. Then, the converse inequality follows from the fact that $\overline{\overline{C}}=C$, and by applying the initial argument to $\overline{C}$. To prove the claim, we actually prove something stronger: we prove that if $C$ shatters $S$, then $\overline{C}$ also shatters $S$. Let $S$ be a set that is ...


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