Generalisation and expressiveness for over-parameterised neural networks

自从学习过程的数学分析真正开始以来，半个多世纪过去了，F. Rosenblatt提出了第一个学习机器模型——感知器。从那时起，学习理论在理论和实践方面都取得了巨大的进步。然而，深度神经网络的发展，能够表现得比任何理论预期都要好，强调了缺乏一个完整的数学理论，能够对学习过程背后的机制提供启发性的见解。学习理论背后的基本思想是找到一种量化算法泛化能力的方法，这意味着从有限且相对较小的训练数据集中推断出一些未知规则的能力，这些规则允许对不属于原始训练集的数据进行连贯分类。学习算法通常通过引入损失函数来评估，测量正确答案与学习机器给出的答案之间的差异。这个函数对整个现有数据集的期望称为风险函数。然而，在实践中，没有办法直接评估它，人们必须处理它在训练集上的近似值，经验风险。一个有效的学习理论应该能够对经验风险和风险函数之间的差异（泛化误差）给出严格的概率界限。Vapnik-Chervonenkis理论是理论界30年来（从60年代到90年代）的主要研究方向，但它无法解释现代深度神经网络的高泛化能力，即机器能够推断出比现有训练数据更多的参数。在过去20年发展起来的理论中，相关的兴趣是PAC- bayes方法，PAC代表可能几乎正确。PAC-Bayes的主要思想是考虑独立于训练集数据的假设空间（即编码算法可能选择的所有可能的“分类规则”的空间）上的概率分布（先验）。之后必须选择另一个分布（后验），并且由于McAllester的一个众所周知的结果，然后可以根据先验和后验之间的KL散度来量化经验风险和风险函数之间的距离。在最近的一项工作中，Dziugaite和Roy表明，通过优化PAC-Bayes边界，可以计算泛化误差的非真空数值边界。本博士项目的主要目标是尝试使用PAC-Bayes框架来获得新的理论见解，从而更好地理解深度神经网络中的潜在学习机制。

More than half a century has passed since the mathematical analysis of learning processes truly began, that is when F. Rosenblatt proposed the first model of learning machine, the Perceptron. Since then, huge progresses have been achieved in learning theory, both from theoretical and practical perspectives.However the development of deep neural networks, able to perform better than any theoretical expectation, has underlined the lack of a complete mathematical theory, capable of giving an enlightening insight on the mechanisms underlying the learning process.The basic idea behind learning theory is to find a way to quantify the generalisation capacity of an algorithm, meaning the ability to extrapolate, from a finite and relatively small training dataset, some unknown rule allowing to coherently classify data which are not part of the original training set.A learning algorithm is usually evaluated via the introduction of a loss function, measuring the discrepancy between the correct answer and the answer given by the learning machine. The expectation of this function on the whole set of existing data is called the risk functional. However, in practice there's no way to evaluate it directly, and one has to deal with its approximation evaluated on the training set only, the empirical risk.An efficient learning theory should be able to give tight probability bounds on the difference (generalisation error) between the empirical risk and the risk functional.The Vapnik-Chervonenkis theory, which has been the main direction of theorists' work for about three decades (from the 60's to the 90's), cannot explain the high generalisation capacity of modern deep neural networks, where the machine is able to infer many more parameters than the available training data.Among the theory developed in the last 20 years, of relevant interest is the PAC-Bayes approach, PAC standing for Probably Almost Correct. The main idea in PAC-Bayes is to consider a probability distribution (prior) on the hypothesis space (meaning the space encoding all the possible "classification rules" that the algorithm might choose) which is independent of the training set data. Another distribution (posterior) has to be chosen afterwards and, thanks to a well known result by McAllester, it is then possible to quantify the distance between empirical risk and risk functional in terms of the KL divergence between prior and posterior.In a recent work, Dziugaite and Roy have shown that by optimising a PAC-Bayes bound it is possible to compute nonvacuous numerical bounds for generalisation error.The main goal of this doctoral project is to try to use the PAC-Bayes framework in order to get new theoretical insights allowing for a better understanding of the underlying learning mechanisms in deep neural networks.