Boolean Matrix Factorization and Noisy Completion via Message Passing


Siamak Ravanbakhsh, Barnabas Poczos, Russell Greiner ;
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:945-954, 2016.


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.

Related Material