Как посчитать VC-размерность для сверточной сети?

[BeS 53]

Всем привет,

В теории, если мы знаем размерность Вапника-Червоненкиса для нейронной сети, то мы можем примерно оценить минимальное число сэемплов, необходимое для сходимости нейронной сети. Но на практике я нигде не встречал методов, позволяющих посчитать VC-размерность для сети произвольной топологии. Может кто-то встречал подобные работы? Заранее спасибо.

[mrgloom 242]

Хмм, не знал что этот термин вообще применим к нейросетям, думал используется только для SVM.

Хотя гугл говорит

What is your opinion on a well-performing convnet without any theoretical justifications for why it should work so well? Do you generally favor performance over theory? Where do you place the balance?

I don’t think their is a choice to make between performance and theory. If there is performance, there will be theory to explain it.

Also, what kind of theory are we talking about? Is it a generalization bound? Convnets have a finite VC dimension, hence they are consistent and admit the classical VC bounds. What more do you want? Do you want a tighter bound, like what you get for SVMs? No theoretical bound that I know of is tight enough to be useful in practice. So I really don’t understand the point. Sure, generic VC bounds are atrociously non tight, but non-generic bounds (like for SVMs) are only slightly less atrociously non tight.

If what you desire are convergence proofs (or guarantees), that’s a little more complicated. The loss function of multi-layer nets is non convex, so the easy proofs that assume convexity are out the window. But we all know that in practice, a convnet will almost always converge to the same level of performance, regardless of the starting point (if the initialization is done properly). There is theoretical evidence that there are lots and lots of equivalent local minima and a very small number of “bad” local minima. Hence convergence is rarely a problem.

http://blog.kaggle.com/2014/12/22/convolutional-nets-and-cifar-10-an-interview-with-yan-lecun/

 

p.s. тоже интересная область

https://en.wikipedia.org/wiki/Stability_%28learning_theory%29#History

 

[BeS 53]

VC-размерность применима к любому семейству функций, задающих классификаторы.

Для многослойного персептрона вроде как даже существует оценка этой размерности, а вот для конволюшенов что-то не видать.

А нужно оно для того, чтобы оценить качество обучаюжщей выборки, т.к. без этого мы возвращаемся к пресловутому вопросу "а давайте возьмем еще пару миллионов сэмплов и посмотрим на сходимость". Такой подход к формированию баз попахивает каким-то шаманством

[mrgloom 242]

Еще немного на эту тему от Lecun'a

https://www.cs.nyu.edu/~yann/talks/lecun-20071207-nonconvex.pdf

http://videolectures.net/eml07_lecun_wia/