Binary Matrix Factorisation via Column Generation

Réka Á. Kovács, Oktay Günlük, Raphael A. HauserAAAI 2021 · DOI

Abstract

Binary Matrix Factorisation (BMF) is a critical tool for dimensionality reduction in binary data, yet finding optimal solutions is NP-hard. This paper presents a novel optimization framework using Column Generation (CG) to solve BMF as a Mixed Integer Linear Program. By explicitly modeling Boolean logic and utilizing a pricing subproblem to identify optimal rank-1 patterns, the proposed method achieves state-of-the-art accuracy and provides the first real optimality guarantees for several benchmark datasets.

Introduction

In data science, dimensionality reduction is essential for simplifying complex datasets into interpretable core patterns. While real-valued data can be handled by Singular Value Decomposition (SVD) or Non-negative Matrix Factorisation (NMF), binary data (0s and 1s) requires specialized approaches to maintain interpretability. Standard methods often yield fractional results that lack physical meaning in binary contexts.

Binary Matrix Factorisation (BMF) addresses this by keeping factors in the binary domain. This paper specifically focuses on Boolean BMF, where addition follows Boolean logic ($1 \lor 1 = 1$). This is ideal for "on/off" scenarios, such as medical diagnoses where the presence of multiple symptoms doesn't result in a "double" symptom. However, finding the optimal BMF is NP-hard, and existing tools typically rely on greedy heuristics that offer no guarantees of optimality.

Methodology

The authors propose a shift from heuristic pattern mining to formal mathematical optimization using a Mixed Integer Program (MIP) solved via Column Generation (CG).

The Master Problem and Column Generation

The problem is formulated as selecting the best $k$ "rank-1" binary matrices from the set of all possible $2^n \times 2^m$ rank-1 matrices. Since this pool is astronomically large, the authors employ Column Generation—a "smart search" technique. The algorithm starts with a small subset of patterns and iteratively solves a Pricing Subproblem to identify the new pattern that would most improve the reconstruction error.

Boolean Logic and Symmetry Breaking

Unlike traditional BMF models that suffer from "permutation symmetry" (where swapping the order of features confuses solvers), this model uses indicator variables for rank-1 matrices directly. This eliminates symmetry and allows the model to explicitly handle Boolean algebra, ensuring the factorisation remains physically meaningful for categorical data.

Convergence of the Column Generation approach for k=5 and k=10, showing the objective value over time.

Experimental Results

The method was evaluated on eight real-world categorical datasets from the UCI Machine Learning Repository, including medical (Tumor, Hepat, Heart) and political (Votes) data.

Performance and Accuracy

The proposed CG method demonstrated superior accuracy, outperforming state-of-the-art heuristics like ASSO, ASSO++, and NMF in 15 out of 24 tested instances. For smaller datasets such as "Zoo," the method successfully proved it had found the mathematically absolute best factorisation.

Comparison of the proposed CG method against state-of-the-art heuristics across various datasets and k values.

Optimality Bounds

A key advantage of the CG approach is the provision of a "dual bound." Even when the algorithm does not reach the global optimum, it provides a lower bound on the possible error, allowing researchers to quantify the remaining room for improvement—a feature missing in previous heuristic approaches. The synergy between heuristics and exact optimization is further enhanced by using tools like ASSO++ to "warm start" the process, accelerating convergence.

Conclusion and Future Work

While the Column Generation framework brings unprecedented rigor to BMF, it is computationally more intensive than simple heuristics. The Pricing Subproblem remains a bottleneck for very large matrices. Future research directions include developing a full "Branch-and-Price" algorithm to solve pricing problems more efficiently and exploring specialized heuristics to handle massive datasets. Despite these challenges, the method provides a robust foundation for interpretable, high-accuracy binary data analysis.

Summary updated

BibTeX
@inproceedings{kovacs2021binary,
  author = {Réka Á. Kovács and Oktay Günlük and Raphael A. Hauser},
  title = {{Binary Matrix Factorisation via Column Generation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i5.16500},
}
Figure