Monday, April 30, 2018

Video, Preprint and Implementation: Measuring the Intrinsic Dimension of Objective Landscapes

While waiting for the Workshop on the Future of Random Projections this coming Wednesday (you can register here) . Here is a video that present a paper that will be featured at ICLR this week that talks about random projections !

In this video from Uber AI Labs, researchers Chunyuan Li and Jason Yosinski describe their ICLR 2018 paper "Measuring the Intrinsic Dimension of Objective Landscapes". The research, performed with co-authors Heerad Farkhoor and Rosanne Liu, develops intrinsic dimension as a fundamental property of neural networks. Intrinsic dimension quantifies the complexity of a model in a manner decoupled from its raw parameter count, and the paper provides a simple way of measuring this dimension using random projections. Many problems have smaller intrinsic dimension than one might suspect. By using intrinsic dimension to compare across problem domains, one may measure, for example, that solving the inverted pendulum problem is about 100 times easier than classifying digits from MNIST, and playing Atari Pong from pixels is about as hard as classifying CIFAR-10.

Many recently trained neural networks employ large numbers of parameters to achieve good performance. One may intuitively use the number of parameters required as a rough gauge of the difficulty of a problem. But how accurate are such notions? How many parameters are really needed? In this paper we attempt to answer this question by training networks not in their native parameter space, but instead in a smaller, randomly oriented subspace. We slowly increase the dimension of this subspace, note at which dimension solutions first appear, and define this to be the intrinsic dimension of the objective landscape. The approach is simple to implement, computationally tractable, and produces several suggestive conclusions. Many problems have smaller intrinsic dimensions than one might suspect, and the intrinsic dimension for a given dataset varies little across a family of models with vastly different sizes. This latter result has the profound implication that once a parameter space is large enough to solve a problem, extra parameters serve directly to increase the dimensionality of the solution manifold. Intrinsic dimension allows some quantitative comparison of problem difficulty across supervised, reinforcement, and other types of learning where we conclude, for example, that solving the inverted pendulum problem is 100 times easier than classifying digits from MNIST, and playing Atari Pong from pixels is about as hard as classifying CIFAR-10. In addition to providing new cartography of the objective landscapes wandered by parameterized models, the method is a simple technique for constructively obtaining an upper bound on the minimum description length of a solution. A byproduct of this construction is a simple approach for compressing networks, in some cases by more than 100 times.

implementation is here:

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.


Anonymous said...

If what they are doing is variable precision weight sharing:

Then it would be very interesting to figure out an algorithm to know which weights were being set very exactly to high precision and which ones to low precision. You can think of schemes where you alternate the backpropagation through 2 different random projections then look later where they agree to high precision on some weights and disagree on others.
I presume other people think it is a very significant paper?

Anonymous said...

Just to say where the variable precision comes from. The Walsh Hadamard transform maps points to certain patterns. And can map those certain patterns back to the original points again, since it is self inverse.
With random projections based on the WHT you get similar properties except they are not generally self inverse, you have to construct an inverse if you need it.
Anyway certain patterns can focus to a point in the output allowing to set whatever value you like there. With incomplete patterns (doing a dimension increase) you can only focus specific values in some places in the output and other places only a low precision approximation of the wanted value.
Anyway it is all just the linear algebra of under-determined systems.

You could put a non-linearity at the output of the random projection after the dimension increase. Using say a signed square function y=x*x x>0, y=-x*x x<=0 you would get somewhat sparse synthesized weights with a spiky type of distribution. Or the signed square root (similar idea) has attractor states of +1,1 if you think the synthesized weights should have a soft binary type distribution.