MDL4BMF: Minimum Description Length for Boolean Matrix Factorization. Matrix factorizations—where a given data matrix is approximated by a product of two or more factor matrices—are powerful data mining tools. Among other tasks, matrix factorizations are often used to separate global structure from noise. This, however, requires solving the “model order selection problem” of determining the proper rank of the factorization, that is, to answer where fine-grained structure stops, and where noise starts. Boolean Matrix Factorization (BMF)—where data, factors, and matrix product are Boolean—has in recent years received increased attention from the data mining community. The technique has desirable properties, such as high interpretability and natural sparsity. Yet, so far no method for selecting the correct model order for BMF has been available. In this article, we propose the use of the Minimum Description Length (MDL) principle for this task. Besides solving the problem, this well-founded approach has numerous benefits; for example, it is automatic, does not require a likelihood function, is fast, and, as experiments show, is highly accurate. We formulate the description length function for BMF in general—making it applicable for any BMF algorithm. We discuss how to construct an appropriate encoding: starting from a simple and intuitive approach, we arrive at a highly efficient data-to-model--based encoding for BMF. We extend an existing algorithm for BMF to use MDL to identify the best Boolean matrix factorization, analyze the complexity of the problem, and perform an extensive experimental evaluation to study its behavior.
Keywords for this software
References in zbMATH (referenced in 7 articles )
Showing results 1 to 7 of 7.
- Makhalova, Tatiana; Trnecka, Martin: From-below Boolean matrix factorization algorithm based on MDL (2021)
- Mattenet, Alex; Davidson, Ian; Nijssen, Siegfried; Schaus, Pierre: Generic constraint-based block modeling using constraint programming (2021)
- Yamanishi, Kenji; Wu, Tianyi; Sugawara, Shinya; Okada, Makoto: The decomposed normalized maximum likelihood code-length criterion for selecting hierarchical latent variable models (2019)
- Belohlavek, Radim; Trnecka, Martin: Handling noise in Boolean matrix factorization (2018)
- Hess, Sibylle; Morik, Katharina; Piatkowski, Nico: The PRIMPING routine -- tiling through proximal alternating linearized minimization (2017)
- Koutra, Danai; Kang, U.; Vreeken, Jilles; Faloutsos, Christos: Summarizing and understanding large graphs (2015)
- Metzler, Saskia; Miettinen, Pauli: Clustering Boolean tensors (2015)