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.
Code (0)
등록된 구현이 없습니다.
Tasks
Collaborative FilteringMatrix CompletionSimilar Papers 제목 키워드 기반
Matrix completion based on Gaussian parameterized belief propagation
We develop a message-passing algorithm for noisy matrix completion problems based on matrix factorization. The algorithm is derived by approximating message distributions of belief propagation with Gaussian distributions…
Matrix CompletionNoisy and Incomplete Boolean Matrix Factorizationvia Expectation Maximization
Probabilistic approach to Boolean matrix factorization can provide solutions robustagainst noise and missing values with linear computational complexity. However,the assumption about latent factors can be problematic in …
Missing ValuesBoolean Matrix Factorization with SAT and MaxSAT
The Boolean matrix factorization problem consists in approximating a matrix by the Boolean product of two smaller Boolean matrices. To obtain optimal solutions when the matrices to be factorized are small, we propose SAT…
Algorithms for Boolean Matrix Factorization using Integer Programming
Boolean matrix factorization (BMF) approximates a given binary input matrix as the product of two smaller binary factors. As opposed to binary matrix factorization which uses standard arithmetic, BMF uses the Boolean OR …
Generalized Low Rank Models
Principal components analysis (PCA) is a well-known technique for approximating a tabular data set by a low rank matrix. Here, we extend the idea of PCA to handle arbitrary data sets consisting of numerical, Boolean, cat…
ClusteringDenoisingMatrix Completion