Study on functions computed by deep-layered machines finds same distribution in neural networks and Boolean circuits.
problem Understanding the space of functions computed by deep-layered machines.
method Investigation of Boolean functions on random-layered machines, including neural networks and Boolean circuits.
result The space of functions computed at large depth limit is characterized and the macroscopic entropy of Boolean functions is either monotonically increasing or decreasing with depth.
Probabilistic learning for binary classification with categorical variables.
problem Binary classification with categorical covariates.
method Probabilistic analysis and two algorithms for learning boolean functions.
result Effective learning of boolean functions from binary data.
New Fourier analysis method for non-uniform Boolean hypercube.
problem Non-uniform probability measures on the Boolean hypercube.
method ANOVA-based decomposition, explicit basis, least squares problem.
result Generalization of Fourier analysis for arbitrary probability measures.
Survey on learning Boolean functions in computational theory.
problem Learning Boolean function classes in computational theory.
method Overview of known results in PAC and related models.
result Discussion of various learning results for Boolean functions.
Minimalist softmax attention learns constrained Boolean functions with supervision.
problem Learning k-bit Boolean functions, especially AND and OR. method Minimalist single-head softmax-attention mechanism with teacher forcing.
result Minimalist attention can solve Boolean tasks with supervision, but not without.
Transformers learn sparse Boolean functions through RL and SFT, revealing distinct learning behaviors.
problem Learning sparse Boolean functions with Transformers.
method Reinforcement Learning (RL) with process rewards and Supervised Fine-Tuning (SFT).
result RL learns the whole CoT chain simultaneously, while SFT learns step by step.
We explain why numbers occurring in the classification of polygon spaces coincide with numbers of self-dual equivalence classes of threshold functions, or of regular Boolean functions, or of decisive weighted majority games.
Study examines noise sensitivity of DNNs for binary classification.
problem Understanding non-robustness of DNN classifiers under noise.
method Defined and extended noise sensitivity and stability concepts for Boolean functions, applied to DNN models.
result Sorted out the relation between definitions and properties of DNN architectures under noise.
The study explores how Matrix Product States can represent boolean and continuous functions.
problem Representing arbitrary boolean and continuous functions using Matrix Product States.
method Developed a construction method for MPS to represent boolean gates and proved density in continuous function space.
result MPS can accurately represent arbitrary boolean functions and continuous functions densely.
Study links neural network inductive bias, feature learning, and generalization on Boolean functions.
problem Understanding how neural networks learn and generalize on Boolean data.
method End-to-end analysis of depth-2 discrete fully connected networks and DNF formulas, using Monte Carlo learning.
result Predictable training dynamics and interpretable features emerge, linking inductive bias and generalization.
This paper explores how boolean formulas can be learned by deep neural networks.
problem Understanding the learnability of boolean formulas by deep neural networks.
method Analysis of boolean formulas associated with model-sampling benchmarks, combinatorial optimization problems, and random 3-CNFs.
result Neural networks outperform rule-based systems and pure symbolic approaches in learning boolean formulas.
Cube category simplifies set modeling.
problem Modeling set operations efficiently.
method Introducing interval-preserving monotone functions between finite Boolean lattices.
result Cube category facilitates model structures equivalent to simplicial sets.
Efficiently optimizes boolean functions using multilinear polynomials and exponential weight updates.
problem Optimizing boolean functions over the boolean hypercube with high computational cost.
method Proposes a computationally efficient algorithm using multilinear polynomials and exponential weight updates.
result Improves computational time up to several orders of magnitude compared to state-of-the-art algorithms.
Paper improves variational inference on Boolean hypercube using quantum methods.
problem Improving variational inference for pairwise Markov random fields on the Boolean hypercube.
method Quantum relaxations of the Kullback-Leibler divergence for upper-bounds, primal-dual optimization, and greedy selection of hierarchies.
result Efficient algorithm and improved bounds for variational inference.
Boolean logic used for neural network training and inference, with convergence analysis.
problem Discrete optimization in neural networks with Boolean logic.
method Boolean logic backpropagation with convergence analysis.
result First convergence analysis for Boolean logic in neural networks.
Extends quantum learning theory to multiclass and online settings.
problem Quantum learning theory for batch and online learning.
method Adapts classical models to quantum settings, introduces new online learning model.
result Quantum and classical sample complexities have the same form for various learning scenarios.
The paper explores how neural networks learn logical functions and their generalization error.
problem Learning logical functions with neural networks and understanding generalization error.
method Gradient descent on neural networks, analyzing noise-stability and Boolean influence.
result Gradient descent on certain neural architectures tends to favor low-degree representations, impacting generalization error.
New approach to certifiably robust neural networks using Boolean function perspective.
problem Lack of principled understanding and certified robustness for ℓ∞ perturbations. method New perspective on Boolean functions, deriving impossibility results, and developing a unified Lipschitz network.
result Unified Lipschitz network that bypasses expressive power limitations and achieves better certified robustness.
New findings show that common optimization algorithms struggle with random problems.
problem Finding near-optimal solutions to random optimization problems.
method Low-degree polynomials, Boolean circuits, and Langevin dynamics.
result These algorithms fail to produce nearly optimal solutions with high probability.
The degree-d Chow parameters of a Boolean function f:{−1,1}n→R are its degree at most d Fourier coefficients. It is well-known that degree-d Chow parameters uniquely characterize degree-d polynomial threshold functions (PTFs) within the space of all bounded functions. In this paper, we prove …
The ability to compose learned skills to solve new tasks is an important property of lifelong-learning agents. In this work, we formalise the logical composition of tasks as a Boolean algebra. This allows us to formulate new tasks in terms of the negation, disjunction and conjunction of a set of base tasks. We then sho…
Paper computes link determinants using Fourier-Hadamard transforms.
problem Computing determinants of complex link structures.
method Fourier-Hadamard transforms of Boolean functions.
result Determinant of centrally symmetric links with even components equals zero.
We show a connection between the Fourier spectrum of Boolean functions and the REINFORCE gradient estimator for binary latent variable models. We show that REINFORCE estimates (up to a factor) the degree-1 Fourier coefficients of a Boolean function. Using this connection we offer a new perspective on variance reduction…
Understanding the inductive bias of neural networks is critical to explaining their ability to generalise. Here, for one of the simplest neural networks -- a single-layer perceptron with n input neurons, one output neuron, and no threshold bias term -- we prove that upon random initialisation of weights, the a priori p…
A new deep learning method using Boolean logic reduces training and inference energy.
problem High computational and energy costs in deep learning training and inference.
method Introduces Boolean weights and inputs for efficient training using Boolean logic.
result Achieves full-precision accuracy in ImageNet classification and surpasses state-of-the-art results in semantic segmentation.
Boolean matrix factorization and Boolean matrix completion from noisy observations are desirable unsupervised data-analysis methods due to their interpretability, but hard to perform due to their NP-hardness. We treat these problems as maximum a posteriori inference problems in a graphical model and present a message p…
New Boolean algebra method shows knot unknotting number is (c+1)/2.
problem Finding the minimum number of region crossing changes to unknot a knot.
method Boolean algebra applied to region crossing changes.
result Region unknotting number is (c+1)/2 for any knot with crossing number c.
A new method relaxes Boolean Matrix Factorization to make it more efficient.
problem High computational cost of solving NP-hard combinatorial optimization problems in Boolean Matrix Factorization.
method Proposes a proximal gradient algorithm using an elastic-binary regularizer to relax BMF.
result Demonstrates improved runtime and better recall, loss, and interpretability on real-world data.
Boolean matrix factorisation aims to decompose a binary data matrix into an approximate Boolean product of two low rank, binary matrices: one containing meaningful patterns, the other quantifying how the observations can be expressed as a combination of these patterns. We introduce the OrMachine, a probabilistic genera…
We consider efficiency in the implementation of deep neural networks. Hardware accelerators are gaining interest as machine learning becomes one of the drivers of high-performance computing. In these accelerators, the directed graph describing a neural network can be implemented as a directed graph describing a Boolean…
A Bayesian Boolean Matrix Factorization for cancer genomics
problem Identifying coordinated feature changes in cancer
method Bayesian Boolean Matrix Factorization
result Captures widespread, near-simultaneous chromosome-number changes
New framework reduces LLM complexity by directly finetuning in Boolean domain.
problem Reducing the complexity of large language models (LLMs) while maintaining performance.
method Proposes a novel framework using multi-kernel Boolean parameters for direct finetuning in the Boolean domain.
result Significantly reduces complexity during both finetuning and inference, outperforming recent techniques.
GETF efficiently decomposes large-scale Boolean tensors.
problem Efficiently factorizing large-scale Boolean tensors.
method Geometric Expansion for all-order Tensor Factorization (GETF).
result GETF significantly improves reconstruction accuracy and efficiency.
This paper provides lower bounds on the convergence rate of Derivative Free Optimization (DFO) with noisy function evaluations, exposing a fundamental and unavoidable gap between the performance of algorithms with access to gradients and those with access to only function evaluations. However, there are situations in w…
This study shows neural nets can approximate Turing machines with meaningful statistical properties.
problem Theoretical limitations in approximating Turing machines with neural networks.
method Formal definition of statistically meaningful approximation, analysis of boolean circuits and Turing machines using neural nets.
result Transformers can statistically meaningfully approximate Turing machines with polynomial sample complexity.
There is a growing body of literature showing that deep neural networks are vulnerable to adversarial input modification. Recently this work has been extended from image classification to malware classification over boolean features. In this paper we present several new methods for training restricted networks in this …
As a contribution to interpretable machine learning research, we develop a novel optimization framework for learning accurate and sparse two-level Boolean rules. We consider rules in both conjunctive normal form (AND-of-ORs) and disjunctive normal form (OR-of-ANDs). A principled objective function is proposed to trade …
Paper proposes algorithms for BMF using integer programming.
problem Approximating binary input matrix as product of two smaller binary factors.
method Alternating optimization strategy using integer programming to solve subproblems and combine solutions.
result Proposed algorithms outperform state of the art on medium-scale problems.
The paper develops algorithms for Boolean matrix factorization using IP and heuristics.
problem Approximating binary input matrices as products of smaller binary factors.
method Alternating optimization with integer programming and greedy/local-search heuristics.
result Proposed methods improve scalability and performance compared to existing techniques.
Boolean matrix factorization (BMF) is a popular and powerful technique for inferring knowledge from data. The mining result is the Boolean product of two matrices, approximating the input dataset. The Boolean product is a disjunction of rank-1 binary matrices, each describing a feature-relation, called pattern, for a g…
This paper introduces the combinatorial Boolean model (CBM), which is defined as the class of linear combinations of conjunctions of Boolean attributes. This paper addresses the issue of learning CBM from labeled data. CBM is of high knowledge interpretability but naïve learning of it requires exponentially large compu…
Theory of ends of spaces using linear algebra.
problem Understanding ends of spaces at infinity.
method Developing a theory using scale, sub-Boolean algebras, and linear algebra.
result All known types of ends are special cases of a linear algebraic process.
Boolean matrix has been used to represent digital information in many fields, including bank transaction, crime records, natural language processing, protein-protein interaction, etc. Boolean matrix factorization (BMF) aims to find an approximation of a binary matrix as the Boolean product of two low rank Boolean matri…
It is feasible and practically-valuable to bridge the characteristics between graph neural networks (GNNs) and logical reasoning. Despite considerable efforts and successes witnessed to solve Boolean satisfiability (SAT), it remains a mystery of GNN-based solvers for more complex predicate logic formulae. In this work,…
The study optimizes polynomial regression for learning under Gaussian distributions.
problem Agnostic learning of Boolean and real-valued functions under Gaussian distributions.
method LP duality and polynomial degree analysis for L1-regression. result Optimal SQ lower bounds for various function classes.
Predictive models are finding an increasing number of applications in many industries. As a result, a practical means for trading-off the cost of deploying a model versus its effectiveness is needed. Our work is motivated by risk prediction problems in healthcare. Cost-structures in domains such as healthcare are quite…
During the past few years Boolean matrix factorization (BMF) has become an important direction in data analysis. The minimum description length principle (MDL) was successfully adapted in BMF for the model order selection. Nevertheless, a BMF algorithm performing good results from the standpoint of standard measures in…
This work extends score-based methods to binary data on the Boolean hypercube.
problem Learning and sampling binary data on the Boolean hypercube.
method Adopting Bernoulli noise as a smoothing device, deriving a TMF-like expression for the optimal denoiser, and using a Langevin-like sampler.
result The method successfully samples noisy binary data and reduces effective noise through multiple measurements.