Boolean Matrix Factorization and Noisy Completion via Message Passing
Abstract
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.
Cite
Text
Ravanbakhsh et al. "Boolean Matrix Factorization and Noisy Completion via Message Passing." International Conference on Machine Learning, 2016.Markdown
[Ravanbakhsh et al. "Boolean Matrix Factorization and Noisy Completion via Message Passing." International Conference on Machine Learning, 2016.](https://mlanthology.org/icml/2016/ravanbakhsh2016icml-boolean/)BibTeX
@inproceedings{ravanbakhsh2016icml-boolean,
title = {{Boolean Matrix Factorization and Noisy Completion via Message Passing}},
author = {Ravanbakhsh, Siamak and Poczos, Barnabas and Greiner, Russell},
booktitle = {International Conference on Machine Learning},
year = {2016},
pages = {945-954},
volume = {48},
url = {https://mlanthology.org/icml/2016/ravanbakhsh2016icml-boolean/}
}