Detecting Memorization in ReLU Networks

Edo Collins, Siavash Arjomand Bigdeli, Sabine SüsstrunkarXiv 2018 · OpenReview

TL;DR

This paper introduces a novel way to detect memorization in ReLU networks by analyzing the "non-linearity" of layer activations using Non-negative Matrix Factorization (NMF). They found that high non-linearity in deep layers, particularly when processing batches of similar samples, is a strong indicator of memorization, and this metric can be used for effective early stopping during training.

What Problem Does This Paper Address?

The paper tackles the intriguing phenomenon of deep neural networks not exhibiting the expected overfitting or memorization behavior, even when they possess immense capacity. While traditional machine learning theory suggests that models with high capacity should easily memorize training data, empirical observations have shown that deep networks often generalize surprisingly well. Understanding why and how networks learn to generalize, and conversely, identifying when they do memorize, is crucial for building more robust and reliable AI systems. This paper aims to provide a new tool to detect this memorization behavior, particularly in ReLU networks, which are ubiquitous in modern deep learning.

Methods

The core of the paper's contribution lies in a new metric for "non-linearity" of a ReLU layer with respect to an input batch. This non-linearity is linked to the non-negative rank of the activation matrix. The authors propose to estimate this non-negative rank by applying Non-negative Matrix Factorization (NMF) to the activation matrix.

Here's a breakdown of their approach:

  • ReLU-Induced Support: ReLU activation functions introduce non-linearity by thresholding at zero. This creates a "support" matrix (where activations are positive) that is crucial for analyzing the layer's behavior.
  • Non-Negative Rank as a Linearity Measure: The paper posits that for a batch of similar inputs, a linear layer will have a simple support structure, leading to a low non-negative rank. Conversely, high non-linearity (and thus memorization) will manifest as a complex support structure and a higher non-negative rank.
  • NMF for Approximation: Directly computing the non-negative rank is computationally expensive (NP-hard). The authors use NMF to approximate the activation matrix with a lower rank, allowing them to estimate the non-negative rank and thus the layer's non-linearity. By varying the rank k in NMF and observing the impact on classification accuracy, they can infer the layer's robustness to compression.
  • Single-Class Batches: To isolate the effect of memorization from the network's ability to distinguish between different classes, they analyze batches containing samples from only a single class. They hypothesize that deep layers should be approximately linear with respect to single-class batches if the network is generalizing well. Memorization is indicated when these layers remain highly non-linear even for single-class batches.

Datasets

The paper uses a variety of standard datasets for training and evaluation:

  • Image Datasets:
    • CIFAR-10
    • Fashion-MNIST
    • SVHN (Street View House Numbers)
    • ImageNet (for pre-trained VGG-19 analysis)
  • Audio Dataset:
    • Urban Sounds

No new benchmarks were introduced; the focus was on applying their method to existing, well-established datasets.

Key Insights and Ideas

  • Non-linearity as a Memorization Indicator: The central idea is that high non-linearity in deep layers, especially when processing similar inputs (single-class batches), is a strong signal of memorization. This is a departure from some prior work that focused on other metrics like "flatness" of minima.
  • NMF as a Diagnostic Tool: NMF, by its nature of enforcing non-negativity and seeking low-rank approximations, proves to be a sensitive tool for uncovering the non-linear structure induced by ReLUs and detecting memorization.
  • Layer-by-Layer Memorization Phases: The analysis reveals that memorization isn't a monolithic process but can occur in distinct phases across different layers of a network. This suggests a structured way in which networks might learn to "memorize" data.
  • Single-Class Batches are Key: Analyzing single-class batches is crucial because it isolates the network's behavior on data that should be linearly separable in deeper layers if generalizing well. When this linearity breaks down, it points to memorization.
  • Early Stopping Potential: The proposed metric is not just diagnostic but also practical, showing promise for implementing early stopping to prevent overfitting and improve generalization.

Key Results

  • NMF Sensitivity: NMF-based compression was found to be significantly more sensitive to detecting memorization compared to Principal Component Analysis (PCA) and random ablations. This is attributed to NMF's ability to capture the non-linear structure of ReLU activations.
  • Correlation with Generalization Error: The Area Under the Curve (AuC) of the NMF compression accuracy plots showed a strong negative correlation (-0.82) with generalization error on CIFAR-10, outperforming PCA (-0.64) and random ablations (-0.61).
  • Layer-wise Memorization Patterns: Experiments on CIFAR-10 showed distinct phases in CNNs: a feature extraction phase, followed by a memorization phase in deeper layers, and finally a clustering phase before the output layer. This pattern shifted to earlier layers with increased label randomization.
  • Early Stopping Efficacy: Figure 6 demonstrates that the NMF AuC curve's turning point aligns closely with the test error's turning point, indicating that the method can effectively signal the onset of overfitting and enable early stopping.
  • Cross-Dataset Validation: The findings were consistent across various image and audio datasets and different network architectures (CNNs and fully-connected networks).

Limitations and Future Work

  • Computational Cost: While NMF is used as an approximation, computing it across multiple layers and ranks can still be computationally intensive.
  • Theoretical Guarantees: The authors acknowledge that while their approach is successful empirically, "more analysis is required before definite guarantees could be given" regarding its theoretical underpinnings for all scenarios.
  • Generalization to Other Activation Functions: The current method is specifically tailored for ReLU networks. Extending it to other activation functions (e.g., sigmoid, tanh) might require modifications.
  • Understanding Memorization Mechanism: While the paper identifies when memorization occurs and its layer-wise progression, further research could delve deeper into the precise mechanisms by which ReLUs contribute to this phenomenon.

Summary updated

Abstract

We propose a new notion of `non-linearity' of a network layer with respect to an input batch that is based on its proximity to a linear system, which is reflected in the non-negative rank of the activation matrix. We measure this non-linearity by applying non-negative factorization to the activation matrix. Considering batches of similar samples, we find that high non-linearity in deep layers is indicative of memorization. Furthermore, by applying our approach layer-by-layer, we find that the mechanism for memorization consists of distinct phases. We perform experiments on fully-connected and convolutional neural networks trained on several image and audio datasets. Our results demonstrate that as an indicator for memorization, our technique can be used to perform early stopping.
BibTeX
@misc{collins2018detecting,
  author = {Edo Collins and Siavash Arjomand Bigdeli and Sabine Süsstrunk},
  title = {{Detecting Memorization in ReLU Networks}},
  year = {2018},
  eprint = {1810.03372},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1810.03372},
}
Figure