Boolean Matrix Factorization and Noisy Completion via Message Passing
This addresses interpretable unsupervised data analysis for large-scale Boolean data, such as in collaborative filtering, but is incremental as it builds on existing graphical model and message passing techniques.
The authors tackled the NP-hard problems of Boolean matrix factorization and noisy completion by treating them as maximum a posteriori inference in a graphical model, using a message passing approach that scales linearly with observations and factors, and demonstrated recovery at theoretical boundaries with favorable comparisons to state-of-the-art in applications like collaborative filtering.
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 passing approach that scales linearly with the number of observations and factors. Our empirical study demonstrates that message passing is able to recover low-rank Boolean matrices, in the boundaries of theoretically possible recovery and compares favorably with state-of-the-art in real-world applications, such collaborative filtering with large-scale Boolean data.