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…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,742 papers · 148 categories
Trend · papers per month
48 results for “Boolean Matrix”
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…
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.
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
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.
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 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…
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…
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…
We develop a method to factorize symmetric sparse Boolean matrices efficiently.
problem Finding a symmetric factorization of a given matrix into a sparse, Boolean matrix.
method Polynomial-time algorithm based on bootstrapping higher-order information and tensor decomposition.
result A matrix with full column rank can be recovered with high probability when the matrix size is sufficiently large.
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.
Probabilistic approach to Boolean matrix factorization can provide solutions robustagainst noise and missing values with linear computational complexity. However,the assumption about latent factors can be problematic in real world applications.This study proposed a new probabilistic algorithm free of assumptions of lat…
We propose a new approach for Collaborative Filtering which is based on Boolean Matrix Factorisation (BMF) and Formal Concept Analysis. In a series of experiments on real data (Movielens dataset) we compare the approach with the SVD- and NMF-based algorithms in terms of Mean Average Error (MAE). One of the experimental…
We build upon probabilistic models for Boolean Matrix and Boolean Tensor factorisation that have recently been shown to solve these problems with unprecedented accuracy and to enable posterior inference to scale to Billions of observation. Here, we lift the restriction of a pre-specified number of latent dimensions by …
Decision Machines embeds decision trees into vector spaces for improved optimization.
problem Overfitting and difficulty in finding optimal decision tree structure.
method Embedding Boolean tests into a binary vector space and representing tree structure as matrices.
result Optimized decision trees with enhanced predictive power.
Low-rank approximations of data matrices are an important dimensionality reduction tool in machine learning and regression analysis. We consider the case of categorical variables, where it can be formulated as the problem of finding low-rank approximations to Boolean matrices. In this paper we give what is to the best …
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.
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.
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.
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.
Generalized Low Rank Modelsstat.ML
Principal components analysis (PCA) is a well-known technique for approximating a tabular data set by a low rank matrix. Here, we extend the idea of PCA to handle arbitrary data sets consisting of numerical, Boolean, categorical, ordinal, and other data types. This framework encompasses many well known techniques in da…
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.
Minimalist softmax attention learns constrained Boolean functions with supervision.
problem Learning -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.
LIBRE learns interpretable Boolean rules from data.
problem Creating interpretable classifiers in imbalanced settings.
method Ensemble of weak learners on random feature subsets, combined with a simple union.
result Efficiently balances prediction accuracy and interpretability.
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.
Graph neural networks struggle with proving unsatisfiability in complex logical formulas.
problem Proving unsatisfiability in complex logical formulas.
method Investigating the limitations of graph neural networks in logical reasoning tasks.
result Graph neural networks may fail in certifying unsatisfiability in Boolean formulae.
Particles representing tokens cluster in Transformers, influenced by initial tokens and matrix spectrum.
problem Understanding the geometry of learned representations in Transformers.
method Viewing Transformers as particle systems, applying dynamical systems and partial differential equations.
result Particles cluster towards limiting objects, confirming context-awareness and the emergence of leaders.
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.
A Boolean algebra formalizes task composition for reinforcement learning.
problem Formalizing task composition for efficient learning and problem-solving.
method Formalized tasks as a Boolean algebra, learning goal-oriented value functions, and composing them to solve new tasks.
result Agents can solve new tasks without additional learning by composing value functions in specific ways.
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.
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.
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.
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.
Federated learning approach for binary matrix factorization.
problem Efficiently factorizing binary data distributed across stakeholders while maintaining privacy.
method Proximal optimization for federated learning of relaxed binary matrix factorization.
result Federated algorithm outperforms state-of-the-art methods in quality and efficacy.
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.
Neural networks favor Boolean functions with low entropy.
problem Understanding the inductive bias of neural networks.
method Analyzing a single-layer perceptron with random initial weights.
result There is a strong intrinsic bias towards low entropy Boolean functions.
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 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.
Understanding properties of deep neural networks is an important challenge in deep learning. In this paper, we take a step in this direction by proposing a rigorous way of verifying properties of a popular class of neural networks, Binarized Neural Networks, using the well-developed means of Boolean satisfiability. Our…
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.
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.
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.