Efficiently Factorizing Boolean Matrices using Proximal Gradient Descent

• URL: http://arxiv.org/abs/2307.07615v1
• Date: Fri, 14 Jul 2023 20:22:21 GMT
• Title: Efficiently Factorizing Boolean Matrices using Proximal Gradient Descent
• Authors: Sebastian Dalleiger, Jilles Vreeken
• Abstract summary: We introduce a novel elastic-binary regularizer to relax BMF continuously. We show that our method works well in practice on synthetic and real-world data.
• Score: 31.00422943397691
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Addressing the interpretability problem of NMF on Boolean data, Boolean Matrix Factorization (BMF) uses Boolean algebra to decompose the input into low-rank Boolean factor matrices. These matrices are highly interpretable and very useful in practice, but they come at the high computational cost of solving an NP-hard combinatorial optimization problem. To reduce the computational burden, we propose to relax BMF continuously using a novel elastic-binary regularizer, from which we derive a proximal gradient algorithm. Through an extensive set of experiments, we demonstrate that our method works well in practice: On synthetic data, we show that it converges quickly, recovers the ground truth precisely, and estimates the simulated rank exactly. On real-world data, we improve upon the state of the art in recall, loss, and runtime, and a case study from the medical domain confirms that our results are easily interpretable and semantically meaningful.

Related papers

• BOLD: Boolean Logic Deep Learning [1.4272256806865107]
  We introduce the notion of Boolean variation such that neurons made of Boolean weights and inputs can be trained efficiently in Boolean domain using Boolean logic instead of descent gradient and real arithmetic. Our approach achieves baseline full-precision accuracy in ImageNet classification and surpasses state-of-the-art results in semantic segmentation. It significantly reduces energy consumption during both training and inference.
  arXiv  Detail & Related papers  (2024-05-25T19:50:23Z)
• AnyLoss: Transforming Classification Metrics into Loss Functions [21.34290540936501]
  evaluation metrics can be used to assess the performance of models in binary classification tasks. Most metrics are derived from a confusion matrix in a non-differentiable form, making it difficult to generate a differentiable loss function that could directly optimize them. We propose a general-purpose approach that transforms any confusion matrix-based metric into a loss function, textitAnyLoss, that is available in optimization processes.
  arXiv  Detail & Related papers  (2024-05-23T16:14:16Z)
• Large-Scale OD Matrix Estimation with A Deep Learning Method [70.78575952309023]
  The proposed method integrates deep learning and numerical optimization algorithms to infer matrix structure and guide numerical optimization. We conducted tests to demonstrate the good generalization performance of our method on a large-scale synthetic dataset.
  arXiv  Detail & Related papers  (2023-10-09T14:30:06Z)
• Neural incomplete factorization: learning preconditioners for the conjugate gradient method [2.899792823251184]
  We develop a data-driven approach to accelerate the generation of effective preconditioners. We replace the typically hand-engineered preconditioners by the output of graph neural networks. Our method generates an incomplete factorization of the matrix and is, therefore, referred to as neural incomplete factorization (NeuralIF)
  arXiv  Detail & Related papers  (2023-05-25T11:45:46Z)
• Unitary Approximate Message Passing for Matrix Factorization [90.84906091118084]
  We consider matrix factorization (MF) with certain constraints, which finds wide applications in various areas. We develop a Bayesian approach to MF with an efficient message passing implementation, called UAMPMF. We show that UAMPMF significantly outperforms state-of-the-art algorithms in terms of recovery accuracy, robustness and computational complexity.
  arXiv  Detail & Related papers  (2022-07-31T12:09:32Z)
• Efficient Multidimensional Functional Data Analysis Using Marginal Product Basis Systems [2.4554686192257424]
  We propose a framework for learning continuous representations from a sample of multidimensional functional data. We show that the resulting estimation problem can be solved efficiently by the tensor decomposition. We conclude with a real data application in neuroimaging.
  arXiv  Detail & Related papers  (2021-07-30T16:02:15Z)
• Solving weakly supervised regression problem using low-rank manifold regularization [77.34726150561087]
  We solve a weakly supervised regression problem. Under "weakly" we understand that for some training points the labels are known, for some unknown, and for others uncertain due to the presence of random noise or other reasons such as lack of resources. In the numerical section, we applied the suggested method to artificial and real datasets using Monte-Carlo modeling.
  arXiv  Detail & Related papers  (2021-04-13T23:21:01Z)
• Entropy Minimizing Matrix Factorization [102.26446204624885]
  Nonnegative Matrix Factorization (NMF) is a widely-used data analysis technique, and has yielded impressive results in many real-world tasks. In this study, an Entropy Minimizing Matrix Factorization framework (EMMF) is developed to tackle the above problem. Considering that the outliers are usually much less than the normal samples, a new entropy loss function is established for matrix factorization.
  arXiv  Detail & Related papers  (2021-03-24T21:08:43Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  We propose a simple and efficient unsupervised feature selection method, by combining reconstruction error with $l_2,p$-norm regularization. We present an efficient optimization algorithm to solve the proposed unsupervised model, and analyse the convergence and computational complexity of the algorithm theoretically.
  arXiv  Detail & Related papers  (2020-12-29T04:08:38Z)
• Binary Matrix Factorisation via Column Generation [6.445605125467574]
  We consider the problem of low-rank binary matrix factorisation (BMF) under arithmetic. We formulate the problem as a mixed integer linear program and use a large scale optimisation technique of column generation to solve it. Experimental results on real world datasets demonstrate that our proposed method is effective at producing highly accurate factorisations.
  arXiv  Detail & Related papers  (2020-11-09T14:27:36Z)
• A Scalable, Adaptive and Sound Nonconvex Regularizer for Low-rank Matrix Completion [60.52730146391456]
  We propose a new non scalable low-rank regularizer called "nuclear Frobenius norm" regularizer, which is adaptive and sound. It bypasses the computation of singular values and allows fast optimization by algorithms. It obtains state-of-the-art recovery performance while being the fastest in existing matrix learning methods.
  arXiv  Detail & Related papers  (2020-08-14T18: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.