Handling Noise in Boolean Matrix Factorization

Radim Belohlávek, Martin TrneckaIJCAI 2017 · DOI

TL;DR

This paper critiques existing methods for Boolean Matrix Factorization (BMF) when dealing with noisy data, arguing they fail to properly assess an algorithm's robustness. The authors introduce a novel, quantitative method to evaluate how well BMF algorithms maintain their factorizations under varying noise levels, revealing a clear distinction between robust and sensitive algorithms.

What Problem Does This Paper Address?

Boolean Matrix Factorization (BMF) is a technique used to decompose a binary matrix $M$ (representing, for example, objects and their attributes) into two smaller matrices $A$ and $B$ such that $M \approx A \circ B$. This decomposition is useful for uncovering underlying structures or patterns in data. However, real-world data is often noisy, meaning some entries in the matrix might be incorrect. Existing BMF research has begun to address this "noise" by developing algorithms that can handle it. The problem this paper tackles is that the current methods for evaluating how well these algorithms handle noise are insufficient. They often focus on metrics like coverage quality, which can decrease even if the algorithm is fundamentally robust, because the underlying factors themselves might change significantly. The authors argue that a more nuanced approach is needed to distinguish between algorithms that truly adapt to noise and those that simply produce fragmented or incorrect results.

Methods

The core contribution of this paper is a new methodology for assessing the robustness of BMF algorithms to noise. Instead of solely relying on metrics like coverage quality (which measures how well the reconstructed matrix matches the observed data), the authors propose:

  • A New Robustness Metric: They define a similarity measure, $Sim(F, F')$, between two sets of factors, $F$ and $F'$. $F$ represents the factors computed from the original, noise-free data, while $F'$ represents the factors computed from the noisy version of the data. This similarity is based on the Jaccard index of the rectangular regions corresponding to each factor. A high $Sim(F, F')$ indicates that the algorithm produces similar factors regardless of noise.
  • Assessing Ground Truth Recovery: The same $Sim(F, F')$ metric is used to evaluate an algorithm's ability to recover the original, "true" factors when noise is present. Here, $F$ is the set of known ground-truth factors used to generate the synthetic data, and $F'$ is the set of factors found by the algorithm on the noisy data.

This approach allows for a more direct assessment of whether an algorithm's discovered factors remain stable (robustness) and whether they accurately reflect the original underlying structure (ground truth recovery).

Datasets

The paper uses both synthetic and real-world datasets for evaluation:

  • Synthetic Datasets: Matrices of size $500 \times 250$ were generated as Boolean products $A \circ B$, where $A$ and $B$ were randomly generated matrices with varying dimensions ($k$) and a density of approximately 15% ones. Noise was added to these datasets at various levels.
  • Real-World Dataset: The "Domino dataset" (size $231 \times 79$, density 10%) was used for robustness experiments.
  • Datasets from Gupta et al. (2008): Data 4, 6, and 7 from this previous work were revisited to compare results with prior claims.

Key Insights and Ideas

  • Existing robustness assessments are flawed: The common practice of evaluating robustness by observing a gradual decrease in coverage quality with increasing noise is misleading. This metric doesn't account for the possibility that the underlying factors themselves might change drastically, indicating a lack of true robustness.
  • Robustness and Ground Truth Recovery are distinct: An algorithm can be robust (its factors don't change much with noise) but still fail to recover the original ground truth factors. Conversely, an algorithm might be less robust in terms of factor stability but still manage to recover the original factors.
  • A clear separation of algorithms emerges: The proposed similarity measure clearly distinguishes between BMF algorithms that are robust to noise and those that are not. Algorithms that do not commit "overcovering" (a specific type of error in BMF) tend to fragment their factors when noise is introduced, leading to low similarity scores.
  • Overcovering algorithms show better robustness: Algorithms that allow for "overcovering" (another type of error) generally exhibit better robustness to noise, as they are less susceptible to factor fragmentation.

Key Results

  • Robustness to Noise: Tables 1 and 2 present quantitative results. Algorithms like TILING, GRECOND, HYPER, and GREESS (which do not commit overcovering) consistently show very low similarity scores ($Sim(F, F')$) when noise is added, indicating they are not robust. In contrast, algorithms like 8M, ASSO, PANDA, NASSAU, and GRECOND+ generally achieve higher similarity scores, demonstrating better robustness.
  • Recovery of Ground Truth: Table 2 shows that even algorithms designed for robustness don't always perfectly recover ground truth, especially at higher noise levels. ASSO and GRECOND+ are noted as performing best in this regard.
  • Algorithm Behavior: The paper highlights that NASSAU tends to output larger, merged factors, and GRECOND+ is a simple but effective extension of GRECOND.

Limitations and Future Work

  • Limitations: The authors acknowledge that their experimental evaluation is restricted in scope, focusing on selected results. They also note that the HYPER+ algorithm was not directly included because its behavior is similar to HYPER, and its postprocessing could be applied to other algorithms.
  • Future Work: The authors suggest several avenues for future research:
  • Developing further methods to assess BMF algorithm robustness.
  • Conducting thorough analyses of robustness on both real and synthetic data, including newer algorithms.
  • Performing real-case studies on noise in BMF.
  • Developing a comprehensive, purpose-driven methodology for assessing the overall quality of BMF algorithms.

Summary updated

BibTeX
@inproceedings{belohlavek2017handling,
  author = {Radim Belohlávek and Martin Trnecka},
  title = {{Handling Noise in Boolean Matrix Factorization}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/198},
}

Loading related content...

Figure