Linearly constrained Bayesian matrix factorization for blind source separation

Mikkel N. SchmidtNeurIPS 2009 · OpenReview

Introduction

Matrix factorization is a workhorse of data science, used to break down complex signals into simpler "sources" and "mixing coefficients" ($X \approx AB$). However, standard methods often struggle with interpretability. Independent Component Analysis (ICA), for instance, often produces abstract, noisy patterns, while Non-negative Matrix Factorization (NMF) is famous for finding "parts-based" representations (like individual brushstrokes of a digit).

While NMF is highly useful, it is limited to a single type of constraint: non-negativity. In many real-world scenarios, we have more specific domain knowledge about the data—perhaps we know the sources must exist within a specific range, or that the mixing coefficients must represent proportions that sum to 100%.

To address this, this paper introduces a flexible Bayesian framework for matrix factorization that can handle any combination of linear equality and inequality constraints. By using an efficient Gibbs sampling inference procedure, the method allows researchers to bake domain-specific geometric knowledge directly into the model, resulting in much more interpretable feature extraction than standard techniques.

Methods: Linearly Constrained Bayesian Matrix Factorization

The author proposes a general probabilistic framework whose key technical contributions include:

  1. The Model: A Gaussian observation model with Gaussian priors on the factorizing matrices $A$ and $B$. The true power of the model lies in these priors, which are truncated by any number of linear equality ($R(a,b) = 0$) or inequality ($Q(a,b) \leq 0$) constraints.
  2. Biaffine Constraints: The framework allows for constraints that involve both $A$ and $B$ jointly (biaffine), though the primary experiments focus on constraining them separately.
  3. The Inference Engine: Because the constraints make the posterior distribution complex, the author develops a specialized Gibbs sampler.
  4. To handle equality constraints, the algorithm uses Singular Value Decomposition (SVD) to map the problem onto a lower-dimensional subspace where the constraints are automatically satisfied.
  5. To handle inequality constraints, it samples from truncated multivariate Gaussians using a coordinate-descent style approach. This ensures every sample remains within the "feasible region" (the valid model space).
Illustration of the Gibbs sampling procedure for inequality constraints, showing coordinate-wise sampling within a bounded polytope.

Key Insights and Ideas

  • Geometry is Destiny: The paper beautifully illustrates how different constraints fundamentally change the "model space." Applying no constraints creates a linear subspace; enforcing non-negativity creates a simplicial cone; adding a "sum-to-one" constraint creates a convex polytope.
Various geometric spaces formed by applying different linear equality and inequality constraints to the model parameters.
  • Competition vs. Collaboration: This is a core "aha moment" of the paper. In standard NMF, sources "collaborate" to build an image from parts. By adding a constraint that mixing coefficients must sum to unity, the author forces the sources to compete. To explain a mixture of a '3' and a '5', the model is incentivized to find a distinct '3' source and a '5' source rather than a collection of random curves and lines.
  • Interpretability by Design: Unlike ICA, which is purely statistical, this method is geometric. By constraining the pixel intensities of the sources to the 0–1 range, the resulting factors are guaranteed to look like actual, physically plausible images.

Experimental Results

The method was evaluated using a synthetic "blind source separation" task based on the MNIST dataset of handwritten digits. The author took 8,000 MNIST images and mixed them in pairs (adding their intensities 50/50). The goal was to see if the algorithm could recover the original, clean digits given only these blurry mixtures.

The paper compares the proposed method against ICA and NMF on this task:

  • ICA: Produced complex, high-contrast patterns that were difficult for a human to recognize as digits.
  • NMF: Successfully decomposed the images, but into "parts" (dots and line segments) rather than whole digits.
  • Proposed Method: Successfully recovered "whole" digits. The 40 hidden sources extracted by the model clearly resembled handwritten numbers, effectively "unmixing" the data into its original constituent parts. Furthermore, the model identified "utility" sources, such as a solid black blob and an all-white feature, which it used to adjust the overall brightness of the reconstructed images.

Limitations and Future Work

  • Computational Complexity: As an MCMC-based method (Gibbs sampling), this approach is likely significantly slower than optimization-based NMF or FastICA, especially as the number of constraints or the size of the data grows.
  • Constraint Selection: Currently, the user must specify the constraints manually based on domain knowledge. The author notes that a major future challenge is developing methods to learn the relevant constraints directly from the data.
  • Scalability: While Bayesian matrix factorization can theoretically scale to large datasets, the specific overhead of sampling from highly-constrained multivariate Gaussians in high dimensions remains a potential bottleneck for massive applications.

Summary updated

Abstract

We present a general Bayesian approach to probabilistic matrix factorization subject to linear constraints. The approach is based on a Gaussian observation model and Gaussian priors with bilinear equality and inequality constraints. We present an efficient Markov chain Monte Carlo inference procedure based on Gibbs sampling. Special cases of the proposed model are Bayesian formulations of non-negative matrix factorization and factor analysis. The method is evaluated on a blind source separation problem. We demonstrate that our algorithm can be used to extract meaningful and interpretable features that are remarkably different from features extracted using existing related matrix factorization techniques.
BibTeX
@inproceedings{schmidt2009linearly,
  author = {Mikkel N. Schmidt},
  title = {{Linearly constrained Bayesian matrix factorization for blind source separation}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2009},
  url = {https://openreview.net/forum?id=ryVOztZObH},
}

Loading related content...

Figure