Boolean matrix factorization and noisy completion via message passing
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.
Citation
S. Ravanbakhsh,
B. Poczos,
R. Greiner.
"Boolean matrix factorization and noisy completion via message passing".
International Conference on Machine Learning (ICML), (ed: Maria Florina Balcan, Kilian Q. Weinberger), pp 945-954, June 2016.
Keywords: |
message passing, Probabilistic Graphical Models, matrix factorization |
Category: |
In Conference |
Web Links: |
ICML Link |
BibTeX
@incollection{Ravanbakhsh+al:ICML16,
author = {Siamak Ravanbakhsh and Barnabas Poczos and Russ Greiner},
title = {Boolean matrix factorization and noisy completion via message
passing},
Editor = {Maria Florina Balcan, Kilian Q. Weinberger},
Pages = {945-954},
booktitle = {International Conference on Machine Learning (ICML)},
year = 2016,
}
Last Updated: February 11, 2020
Submitted by Sabina P