DL generalises as the parameter-function map is biased towards simple functions


  • A very interesting paper showing that random initialization of NN parameters (under various initialization distributions) leads to a distribution over the functional space, such that the simpler functions have a higher probability. 
  • One of the main tools of the paper is the notion of the ‘parameter-function map’ which maps parameters to the functions realized by these parameters. For example, if there are n boolean variables, the size of the space of functions is 2^(2^n). The parameters-function map then assigns each parameter in R^d (if ‘d’ is the size of the parameters) to one of these functions (note that the space of parameters is continuous and infinite and the space of functions is discrete and finite, in this example).
    • This is a critical notion as it says we should not be deceived by the number of parameters as the measure of complexity, instead, need to look into the descriptive complexity (using compression based scheme such as KC) of the functions being realised by the networks.
  • They measure the complexity (simplicity) of a function by using Lempel-Ziv (LZ), related to Kolmogorov complexity (KC). The KC of an object is the length of the smallest program that can generate it, eg for a piece of text, we can consider the length of its compressed version plus the decompression algorithm. The smallest such scheme is the KC of that text. 
  • They show that random setting of the parameters gives rise to assigning a higher probability of simpler functions (in the LZ sense), which in turn have higher generalization. The following figure sums it up:


  • They show that if the target function is structured and simple (which is the case in many real-life settings, as they claim), then the SGD and variants tend to select a closely approximate simple function (among the ones with zero error) to this simple target function with high probability as many parameter initializations are in the basis of attraction of simple functions of the network’s space of functions.
  • They provide a formal PAC-Bayes bound using the ‘prior’ imposed by the network on the space of functions and the posterior resulting from the (close to) zero-error functions picked after training on data. The main result of the paper is:


  • Now, assuming that the subspace of zero-error functions U (note that U is characterized by the data, as its functions need to have zero error) has high marginal probability P(U), then the posterior Q has low error upper-bound (the right-hand-side is reduced). P(U) will be high assuming the target function is a simple function, and noting that simple functions have a high prior probability.

  • An interesting side note is that whether SGD achieves zero error and samples hypothesis under the posterior Q, i.e. whether it leads to the function 'f' from all initialization of parameters that map to this function without leaving this basis of attraction.

  • In a follow up paper they address the sampling power of SGD, where the title speaks for itself: Is SGD a Bayesian sampler? Well, almost

Comments

Post a Comment

Popular posts from this blog

Humans Learn From Task Descriptions and So Should Our Models

Image
An excellent talk on PE T: https://www.youtube.com/watch?v=_YOaRLQnBjc&t=246s TDLR; They provide a task description (patterns + class label verbalizer; abbreviated by PET) plus a few examples of the target task of interest to a pre-trained LLM, and train the LLM based on the few examples. Their main difference to GPT3 prompting is that they allow the model to be trained based on the few examples in the prompt. They show that it leads to big improvements compared to GPT3, even if the size of their LLM is much smaller compared to GPT3. The intuition is that, as humans, we update our brains and 'learn' after receiving examples. Can ‘one’ model be trained for a large number of patterns? Yes, maybe in a sequential manner. That is, the problem is now reduced to ‘continual learning', or even multitask learning? Maybe subnetwork pruning can help here, to identify the relevant subnetwork and only update those parameters.   Can the unlabeled data be used to filter our good patte...
Read more

Divergence Frontiers for Evaluating Deep Generative Models

I was reading a collection of interesting papers on the evaluation of deep generative models, which I have summarised in the following slides .  The papers include:  Assessing Generative Models via Precision and Recall " (NeurIPS 2018) Precision-Recall Curves Using Information Divergence Frontiers  (AISTATS 2020) Divergence Frontiers for Generative Models:Sample Complexity, Quantization Effects,and Frontier Integrals  (NuerIPS 2021) MAUVE: Measuring the GapBetween Neural Text and Human Textusing Divergence Frontiers  (NuerIPS 2021)
Read more