XOR-based Boolean Matrix Decomposition

Jörg Wicker, Yan Cathy Hua, Rayner Rebello, Bernhard Pfahringer: XOR-based Boolean Matrix Decomposition. In: International Conference on Data Mining, IEEE, Forthcoming.

Abstract

Boolean matrix factorization (BMF) is a data summarizing and dimension-reduction technique. Existing BMF methods build on matrix properties defined by Boolean algebra, where the addition operator is the logical inclusive OR and the multiplication operator the logical AND. As a consequence, this leads to the lack of an additive inverse in all Boolean matrix operations, which produces
an indelible type of approximation error. Previous research adopted various methods to address such an issue and produced reasonably accurate approximation. However, an exact factorization is rarely found in the literature. In this paper, we introduce a new algorithm named XBMaD (Xor-based Boolean Matrix Decomposition) where the addition operator is defined as the exclusive OR (Xor). This change completely removes the error-mitigation issue of OR-based BMF methods, and allows for an exact error-free factorization. An evaluation comparing XBMaD and classic OR-based methods suggested that XBMAD performed equal or in most cases more accurately and faster.

    BibTeX (Download)

    @inproceedings{Wicker2019,
    title = {XOR-based Boolean Matrix Decomposition},
    author = {Jörg Wicker and Yan Cathy Hua and Rayner Rebello and Bernhard Pfahringer},
    year  = {2019},
    date = {2019-11-08},
    booktitle = {International Conference on Data Mining},
    publisher = {IEEE},
    abstract = {Boolean matrix factorization (BMF) is a data summarizing and dimension-reduction technique. Existing BMF methods build on matrix  properties defined by Boolean algebra, where the addition operator is the logical inclusive OR and the multiplication operator the logical AND. As a consequence, this leads to the lack of an additive inverse in all Boolean matrix operations, which produces 
    an indelible type of approximation error. Previous research adopted various methods to address such an issue and produced reasonably accurate approximation. However, an exact factorization is rarely found in the literature. In this paper, we introduce a new algorithm named XBMaD (Xor-based Boolean Matrix Decomposition) where the addition operator is defined as the exclusive OR (Xor). This change completely removes the error-mitigation issue of OR-based BMF methods, and allows for an exact error-free factorization. An evaluation comparing XBMaD and classic OR-based methods suggested that XBMAD performed equal or in most cases more accurately and faster. 
    },
    keywords = {Boolean matrix decomposition, data mining},
    pubstate = {forthcoming},
    tppubtype = {inproceedings}
    }