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 realworld applications, such collaborative filtering with large-scale Boolean data. A body of problems in machine learning, communication theory and combinatorial optimization involve the product form Z = X Y where operation corresponds to a type of matrix multiplication and Here, often one or two components out of three are (partially) known and the task is to recover the unknown component(s). A subset of these problems, which are most closely related to Boolean matrix factorization and matrix completion, can be expressed over the Boolean domaini.e., Z m,n , X m,k , Y k,n ∈ {false, true} ∼ = {0, 1}. The two most common Boolean matrix products used in such applications are where we refer to Equation (1a) simply as Boolean product and we distinguish Equation (1b) as exclusive-OR (XOR) Boolean product. One may think of Boolean product as ordinary matrix product where the values that are larger than zero in the product matrix are set to one. Alternatively, in XOR product, the odd (even) numbers are identically set to one (zero) in the product matrix. This model can represent Low Density Parity Check (LDPC) coding using the XOR product, with N = 1. In LDPC, the objective is to transmit the data vector Y ∈ {0, 1} K though a noisy channel. For this, it is encoded by Equation (1b), where X ∈ {0, 1} m×k is the parity check matrix and vector Z{0, 1} M is then sent though the channel with a noise model p O (O | Z), producing observation O. Message passing decoding has been able to transmit Z and recover Y from O at rates close to the theoretical capacity of the communication channel (Gallager, 1962) . LDPC codes are in turn closely related to the compressed sensing (Donoho, 2006) -so much so that successful binary LDPC codes (i.e., matrix X) have been reused for compressed sensing (Dimakis et al., 2012) . In this setting, the column-vector Y is known to be -sparse (i.e., non-zero values) which makes it possible to use approximate message passing (Donoho et al., 2009 ) to recover Y using few noisy measurements O -that is M K and similar to LDPC codes, the measurement matrix X is known. When the underlying domain and algebra is Boolean (i.e., Equation (1a)), the compressed sensing problem reduces to the problem of (noisy) group testing (Du and Hwang, 1993) 1 where message passing has been successfully applied in this setting as well (Atia and Saligrama, 2012; Sejdinovic and Johnson, 2010) . These problems over Boolean domain are special instances of the problem of Boolean factor analysis in which Z is given, but not X nor Y . Here, inspired by the success of message passing techniques in closely related problems over "real" domain, we derive message passing solutions to a novel graphical model for "Boolean" factorization and matrix completion, and show that simple application of Belief Propagation (BP; Pearl, 1982) to this graphical model favorably compares with the state-of-the-art in both Boolean factorization and completion. In the following, we briefly introduce the Boolean factorization and completion problems in Section -A and Section I reviews the related work. Section II formulates both of these problems in a Bayesian framework using a graphical model. The ensuing message passing solution is introduced in Section III. Experimental study of Section IV demonstrates that message passing is an efficient and effective method for performing Boolean matrix factorization and noisy completion. The umbrella term "factor analysis" refers to the unsupervised methodology of expressing a set of observations in 1 The intuition is that the non-zero elements of the vector Y identify the presence or absence of a rare property (e.g., a rare disease or manufacturing defect), therefore Y is sparse. The objective is to find these non-zero elements (i.e., recover Y ) by screening a few (M K) "subsets" of elements of Y . Each of these Y -bundles corresponds to a row of X (in Equation (1a)).
By modeling the problem as Markov network, REF has achieved the best performance in noisy matrix factorization and noisy matrix completion respectively.
Boolean Matrix Factorization and Noisy Completion via Message Passing
ICML 2016
arXiv: Statistics Theory
Computer Science Mathematics