DISCO Verification: Division of Input Space into COnvex polytopes for neural network verification

• URL: http://arxiv.org/abs/2105.07776v1
• Date: Mon, 17 May 2021 12:40:51 GMT
• Title: DISCO Verification: Division of Input Space into COnvex polytopes for neural network verification
• Authors: Julien Girard-Satabin (LIST, TAU), Aymeric Varasse (LIST), Marc Schoenauer (TAU), Guillaume Charpiat (TAU), Zakaria Chihani (LIST)
• Abstract summary: The impressive results of modern neural networks partly come from their non linear behaviour. We propose a method to simplify the verification problem by operating a partitionning into multiple linear subproblems. We also present the impact of a technique aiming at reducing the number of linear regions during training.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The impressive results of modern neural networks partly come from their non linear behaviour. Unfortunately, this property makes it very difficult to apply formal verification tools, even if we restrict ourselves to networks with a piecewise linear structure. However, such networks yields subregions that are linear and thus simpler to analyse independently. In this paper, we propose a method to simplify the verification problem by operating a partitionning into multiple linear subproblems. To evaluate the feasibility of such an approach, we perform an empirical analysis of neural networks to estimate the number of linear regions, and compare them to the bounds currently known. We also present the impact of a technique aiming at reducing the number of linear regions during training.

Related papers

• Recurrent Neural Networks Learn to Store and Generate Sequences using Non-Linear Representations [54.17275171325324]
  We present a counterexample to the Linear Representation Hypothesis (LRH) When trained to repeat an input token sequence, neural networks learn to represent the token at each position with a particular order of magnitude, rather than a direction. These findings strongly indicate that interpretability research should not be confined to the LRH.
  arXiv  Detail & Related papers  (2024-08-20T15:04:37Z)
• The Evolution of the Interplay Between Input Distributions and Linear Regions in Networks [20.97553518108504]
  We count the number of linear convex regions in deep neural networks based on ReLU. In particular, we prove that for any one-dimensional input, there exists a minimum threshold for the number of neurons required to express it. We also unveil the iterative refinement process of decision boundaries in ReLU networks during training.
  arXiv  Detail & Related papers  (2023-10-28T15:04:53Z)
• Exploring Linear Feature Disentanglement For Neural Networks [63.20827189693117]
  Non-linear activation functions, e.g., Sigmoid, ReLU, and Tanh, have achieved great success in neural networks (NNs) Due to the complex non-linear characteristic of samples, the objective of those activation functions is to project samples from their original feature space to a linear separable feature space. This phenomenon ignites our interest in exploring whether all features need to be transformed by all non-linear functions in current typical NNs.
  arXiv  Detail & Related papers  (2022-03-22T13:09:17Z)
• Mean-field Analysis of Piecewise Linear Solutions for Wide ReLU Networks [83.58049517083138]
  We consider a two-layer ReLU network trained via gradient descent. We show that SGD is biased towards a simple solution. We also provide empirical evidence that knots at locations distinct from the data points might occur.
  arXiv  Detail & Related papers  (2021-11-03T15:14:20Z)
• DL-Reg: A Deep Learning Regularization Technique using Linear Regression [4.1359299555083595]
  This paper proposes a novel deep learning regularization method named as DL-Reg. It carefully reduces the nonlinearity of deep networks to a certain extent by explicitly enforcing the network to behave as much linear as possible. The performance of DL-Reg is evaluated by training state-of-the-art deep network models on several benchmark datasets.
  arXiv  Detail & Related papers  (2020-10-31T21:53:24Z)
• Bounding The Number of Linear Regions in Local Area for Neural Networks with ReLU Activations [6.4817648240626005]
  We present the first method to estimate the upper bound of the number of linear regions in any sphere in the input space of a given ReLU neural network. Our experiments showed that, while training a neural network, the boundaries of the linear regions tend to move away from the training data points.
  arXiv  Detail & Related papers  (2020-07-14T04:06:00Z)
• Provably Efficient Neural Estimation of Structural Equation Model: An Adversarial Approach [144.21892195917758]
  We study estimation in a class of generalized Structural equation models (SEMs) We formulate the linear operator equation as a min-max game, where both players are parameterized by neural networks (NNs), and learn the parameters of these neural networks using a gradient descent. For the first time we provide a tractable estimation procedure for SEMs based on NNs with provable convergence and without the need for sample splitting.
  arXiv  Detail & Related papers  (2020-07-02T17:55:47Z)
• An analytic theory of shallow networks dynamics for hinge loss classification [14.323962459195771]
  We study the training dynamics of a simple type of neural network: a single hidden layer trained to perform a classification task. We specialize our theory to the prototypical case of a linearly separable dataset and a linear hinge loss. This allow us to address in a simple setting several phenomena appearing in modern networks such as slowing down of training dynamics, crossover between rich and lazy learning, and overfitting.
  arXiv  Detail & Related papers  (2020-06-19T16:25:29Z)
• Measuring Model Complexity of Neural Networks with Curve Activation Functions [100.98319505253797]
  We propose the linear approximation neural network (LANN) to approximate a given deep model with curve activation function. We experimentally explore the training process of neural networks and detect overfitting. We find that the $L1$ and $L2$ regularizations suppress the increase of model complexity.
  arXiv  Detail & Related papers  (2020-06-16T07:38:06Z)
• Eigendecomposition-Free Training of Deep Networks for Linear Least-Square Problems [107.3868459697569]
  We introduce an eigendecomposition-free approach to training a deep network. We show that our approach is much more robust than explicit differentiation of the eigendecomposition. Our method has better convergence properties and yields state-of-the-art results.
  arXiv  Detail & Related papers  (2020-04-15T04:29:34Z)
• Empirical Studies on the Properties of Linear Regions in Deep Neural Networks [34.08593191989188]
  A deep neural network (DNN) with piecewise linear activations can partition the input space into numerous small linear regions. It is believed that the number of these regions represents the expressivity of the DNN. We study their local properties, such as the inspheres, the directions of the corresponding hyperplanes, the decision boundaries, and the relevance of the surrounding regions.
  arXiv  Detail & Related papers  (2020-01-04T12:47:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.