Learning Nonlinearity of Boolean Functions: An Experimentation with Neural Networks

• URL: http://arxiv.org/abs/2502.01060v1
• Date: Mon, 03 Feb 2025 05:10:25 GMT
• Title: Learning Nonlinearity of Boolean Functions: An Experimentation with Neural Networks
• Authors: Sriram Ranga, Nandish Chattopadhyay, Anupam Chattopadhyay,
• Abstract summary: We train encoder style deep neural networks to learn to predict the nonlinearity of Boolean functions. We show that deep neural networks are able to learn to predict the property for functions in 4 and 5 variables with an accuracy above 95%.
• Score: 3.4179091429029382
• License:
• Abstract: This paper investigates the learnability of the nonlinearity property of Boolean functions using neural networks. We train encoder style deep neural networks to learn to predict the nonlinearity of Boolean functions from examples of functions in the form of a truth table and their corresponding nonlinearity values. We report empirical results to show that deep neural networks are able to learn to predict the property for functions in 4 and 5 variables with an accuracy above 95%. While these results are positive and a disciplined analysis is being presented for the first time in this regard, we should also underline the statutory warning that it seems quite challenging to extend the idea to higher number of variables, and it is also not clear whether one can get advantage in terms of time and space complexity over the existing combinatorial algorithms.

Related papers

• Explainable Neural Networks with Guarantees: A Sparse Estimation Approach [11.142723510517778]
  This paper introduces a novel approach to constructing an explainable neural network that harmonizes predictiveness and explainability. Our model, termed SparXnet, is designed as a linear combination of a sparse set of jointly learned features. Our research paves the way for further research on sparse and explainable neural networks with guarantee.
  arXiv  Detail & Related papers  (2025-01-02T12:10:17Z)
• Coding schemes in neural networks learning classification tasks [52.22978725954347]
  We investigate fully-connected, wide neural networks learning classification tasks. We show that the networks acquire strong, data-dependent features. Surprisingly, the nature of the internal representations depends crucially on the neuronal nonlinearity.
  arXiv  Detail & Related papers  (2024-06-24T14:50:05Z)
• Instance-wise Linearization of Neural Network for Model Interpretation [13.583425552511704]
  The challenge can dive into the non-linear behavior of the neural network. For a neural network model, the non-linear behavior is often caused by non-linear activation units of a model. We propose an instance-wise linearization approach to reformulates the forward computation process of a neural network prediction.
  arXiv  Detail & Related papers  (2023-10-25T02:07:39Z)
• Utility-Probability Duality of Neural Networks [4.871730595406078]
  We propose an alternative utility-based explanation to the standard supervised learning procedure in deep learning. The basic idea is to interpret the learned neural network not as a probability model but as an ordinal utility function. We show that for all neural networks with softmax outputs, the SGD learning dynamic of maximum likelihood estimation can be seen as an iteration process.
  arXiv  Detail & Related papers  (2023-05-24T08:09:07Z)
• Points of non-linearity of functions generated by random neural networks [0.0]
  We consider functions from the real numbers to the real numbers, output by a neural network with 1 hidden activation layer, arbitrary width, and ReLU activation function. We compute the expected distribution of the points of non-linearity.
  arXiv  Detail & Related papers  (2023-04-19T17:40:19Z)
• Neural networks trained with SGD learn distributions of increasing complexity [78.30235086565388]
  We show that neural networks trained using gradient descent initially classify their inputs using lower-order input statistics. We then exploit higher-order statistics only later during training. We discuss the relation of DSB to other simplicity biases and consider its implications for the principle of universality in learning.
  arXiv  Detail & Related papers  (2022-11-21T15:27:22Z)
• A Theoretical Analysis on Feature Learning in Neural Networks: Emergence from Inputs and Advantage over Fixed Features [18.321479102352875]
  An important characteristic of neural networks is their ability to learn representations of the input data with effective features for prediction. We consider learning problems motivated by practical data, where the labels are determined by a set of class relevant patterns and the inputs are generated from these. We prove that neural networks trained by gradient descent can succeed on these problems.
  arXiv  Detail & Related papers  (2022-06-03T17:49:38Z)
• 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)
• Data-driven emergence of convolutional structure in neural networks [83.4920717252233]
  We show how fully-connected neural networks solving a discrimination task can learn a convolutional structure directly from their inputs. By carefully designing data models, we show that the emergence of this pattern is triggered by the non-Gaussian, higher-order local structure of the inputs.
  arXiv  Detail & Related papers  (2022-02-01T17:11:13Z)
• Going Beyond Linear RL: Sample Efficient Neural Function Approximation [76.57464214864756]
  We study function approximation with two-layer neural networks. Our results significantly improve upon what can be attained with linear (or eluder dimension) methods.
  arXiv  Detail & Related papers  (2021-07-14T03:03:56Z)
• How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks [80.55378250013496]
  We study how neural networks trained by gradient descent extrapolate what they learn outside the support of the training distribution. Graph Neural Networks (GNNs) have shown some success in more complex tasks.
  arXiv  Detail & Related papers  (2020-09-24T17:48:59Z)

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.