Efficiently estimate Boolean product distribution parameters from truncated samples.
problem Estimating parameters of Boolean product distributions from truncated samples.
method Introducing fatness of truncation set, using membership queries, and adapting Stochastic Gradient Descent.
result Efficiently learn Boolean product distributions from truncated samples with small sample complexity.
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…
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 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.
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.
Product diversity of large US firms has declined steadily since 1997.
problem Lack of data on global product diversity makes investigation difficult.
method Text mining of US firms' product descriptions from 1997-2017.
result Product diversity of large US firms has been declining since 1997.
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…
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.
While on some natural distributions, neural-networks are trained efficiently using gradient-based algorithms, it is known that learning them is computationally hard in the worst-case. To separate hard from easy to learn distributions, we observe the property of local correlation: correlation between local patterns of t…
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…
We present novel, computationally efficient, and differentially private algorithms for two fundamental high-dimensional learning problems: learning a multivariate Gaussian and learning a product distribution over the Boolean hypercube in total variation distance. The sample complexity of our algorithms nearly matches t…
We introduce economic models based on Boolean Delay Equations: this formalism makes easier to take into account the complexity of the interactions between firms and is particularly appropriate for studying the propagation of an initial damage due to a catastrophe. Here we concentrate on simple cases, which allow to und…
The study shows that the visible range from a point on harmonic manifolds follows an exponential distribution.
problem Understanding the visible range from a point on harmonic manifolds.
method Analyzing Poisson Boolean models on harmonic manifolds, focusing on the geometric mechanism of tube volumes around geodesic segments.
result The visible range from a point on harmonic manifolds follows an exponential distribution.
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.
Boolean tensor decomposition approximates data of multi-way binary relationships as product of interpretable low-rank binary factors, following the rules of Boolean algebra. Here, we present its first probabilistic treatment. We facilitate scalable sampling-based posterior inference by exploitation of the combinatorial…
New algorithm learns halfspaces over hypercube with random bit flips.
problem Agnostic learning of Boolean halfspaces over discrete domains is computationally hard.
method Smoothed analysis with random bit flips for discrete inputs.
result First efficient algorithm for smoothed agnostic learning of halfspaces over Boolean hypercube.
We study the problem of learning a distribution from samples, when the underlying distribution is a mixture of product distributions over discrete domains. This problem is motivated by several practical applications such as crowd-sourcing, recommendation systems, and learning Boolean functions. The existing solutions e…
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 …
Restricted Boltzmann Machines are described by the Gibbs measure of a bipartite spin glass, which in turn corresponds to the one of a generalised Hopfield network. This equivalence allows us to characterise the state of these systems in terms of retrieval capabilities, both at low and high load. We study the paramagnet…
The theory of learning under the uniform distribution is rich and deep, with connections to cryptography, computational complexity, and the analysis of boolean functions to name a few areas. This theory however is very limited due to the fact that the uniform distribution and the corresponding Fourier basis are rarely …
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.
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.
New algorithm learns disjunctions faster than previous methods.
problem Learning Boolean disjunctions in the agnostic PAC model.
method Developed an agnostic learner with complexity 2ildeO(n1/3). result First separation between SQ and CSQ models in distribution-free agnostic learning.
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.
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.
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.
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
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.
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.
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.
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.
Paper proves L2 regression can learn k-juntas without distributional assumptions.
problem Learning k-juntas using L2 regression without distributional restrictions.
method L2 polynomial regression and minimum mean square estimation (MMSE).
result Agnostic PAC learning of k-juntas using L2 polynomial regression.
Efficiently learns complex Boolean functions under Gaussian distributions.
problem Learning complex Boolean functions of halfspaces under Gaussian marginals.
method First efficient proper agnostic learning algorithm for arbitrary Boolean functions of K halfspaces.
result Matches the best known improper learning algorithm's run-time dependence on dimension.
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.
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.
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.
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.
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…
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.
Unified tractability conditions for various compositional inference queries.
problem Analyzing tractability of probabilistic and causal inference queries.
method Algebraic perspective on circuits, focusing on semiring operators.
result Unified sufficient conditions for tractable composition of operators.
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…
We study the problem of partitioning a small sample of n individuals from a mixture of k product distributions over a Boolean cube {0,1}K according to their distributions. Each distribution is described by a vector of allele frequencies in RK. Given two distributions, we use γ to denote the average $\el…
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.
We study the statistical behavior of reasoning probes in a stylized model of iterative computation inspired by neural algorithmic reasoning. The underlying computation is given by a looped Boolean circuit whose graph is a perfect ν-ary tree (ν≥2), with outputs recursively fed back as inputs across computation ro…
Randomly biased data makes complex models as easy to learn as simple ones.
problem Learning complex models like multi-index and sparse Boolean functions.
method Introducing a small random shift in the first moment of the data distribution.
result Randomly biased data makes Gaussian single index models and sparse Boolean functions as easy to learn as linear functions.