PaperlayerView exact revision on arXiv

Source-linked AI summary

Automatic Relevance Determination in Nonnegative Matrix Factorization with the β-Divergence

Vincent Y. F. Tan, Cédric Févotte

arXiv:1111.6085v3stat.MLstat.ME

TL;DR

The paper addresses selecting NMF latent dimensionality under β-divergence without sacrificing data fidelity or encouraging overfitting. It introduces a Bayesian ARD model tying dictionary columns to activation rows through shared scales and develops MM-based MAP algorithms. Experiments across synthetic and real data report effective model-order selection and competitive performance, while initialization and hyperparameter estimation remain practical boundaries.

  • Problem

    Selecting NMF model order is difficult because too few components underfit, too many overfit, and BIC is unsuitable when the parameter count grows with the data size.

  • Method

    A Bayesian β-NMF model ties each dictionary column and activation row through a shared relevance scale, with MM algorithms for MAP estimation and group-sparse pruning.

  • Results

    The proposed algorithms recover correct model orders and produce competitive or improved decompositions across synthetic, swimmer, music, and stock-price tasks.

  • Takeaways & Limitations

    The framework unifies β-dependent observation models and prior structures while automatically removing irrelevant component pairs.

  • Takeaways & Limitations

    Music decomposition remained initialization-sensitive, while method-of-moments estimates of hyperparameter a were not consistently satisfactory when FN was not sufficiently large.

Abstract

from arXiv · show

This paper addresses the estimation of the latent dimensionality in nonnegative matrix factorization (NMF) with the β-divergence. The β-divergence is a family of cost functions that includes the squared Euclidean distance, Kullback-Leibler and Itakura-Saito divergences as special cases. Learning the model order is important as it is necessary to strike the right balance between data fidelity and overfitting. We propose a Bayesian model based on automatic relevance determination in which the columns of the dictionary matrix and the rows of the activation matrix are tied together through a common scale parameter in their prior. A family of majorization-minimization algorithms is proposed for maximum a posteriori (MAP) estimation. A subset of scale parameters is driven to a small lower bound in the course of inference, with the effect of pruning the corresponding spurious components. We demonstrate the efficacy and robustness of our algorithms by performing extensive experiments on synthetic data, the swimmer dataset, a music decomposition example and a stock price prediction task.

1 INTRODUCTION

The paper targets NMF model-order selection under the β-divergence, where choosing too few or too many components harms the balance between data fidelity and overfitting. It introduces Bayesian ARD and MM algorithms that estimate model order while supporting a continuum of β-based costs.

  • 1 INTRODUCTION: NMF represents nonnegative data as WH using nonnegative basis and activation matrices with shared latent dimension K.The factorization reduces parameters when FK + KN ≪ FN.
  • 1 INTRODUCTION: The β-divergence includes squared Euclidean, generalized Kullback-Leibler, and Itakura-Saito divergences as special cases.Thus β-NMF covers multiple cost functions within one parameterized family.
  • 1.1 Main Contributions: Model-order selection is difficult because small K causes poor fit, whereas large K causes overfitting, and standard BIC is unsuitable when parameter count grows with N.The NMF parameter count is FK + KN, which scales with the number of data points.
  • 1.1 Main Contributions: The proposed Bayesian β-NMF model uses automatic relevance determination to estimate K and jointly estimate W and H.The approach is inspired by Bayesian PCA but accommodates nonnegative factorization and β-divergence costs.
  • 1.1 Main Contributions: Auxiliary-function optimization yields computationally efficient MM algorithms with monotonicity guarantees and multiplicative updates.Experiments report recovery of the correct model order and better decompositions on synthetic and real datasets.
  • 1.2 Prior Work: The paper extends earlier KL-only work to a continuum of β costs and replaces heuristic optimization with MM-based convergence to a local minimum.The authors report improved factorization and model-selection quality across real-world signal classes.

2 PRELIMINARIES

This section defines β-NMF notation and explains how MM replaces direct optimization with simpler auxiliary-function minimization. The resulting updates reduce the objective monotonically while accommodating β-dependent auxiliary functions.

  • 2 PRELIMINARIES: V, W, and H denote the data, dictionary, and activation matrices with dimensions F × N, F × K, and K × N.Their entries are vfn, wfk, and hkn, respectively.
  • 2 PRELIMINARIES: The β-divergence generalizes several NMF costs: β = 0 gives Itakura-Saito, β = 1 gives Kullback-Leibler, and β = 2 gives squared Euclidean distance.β controls the assumed observation-noise statistics and can be fixed or learned by cross-validation.
  • 2 PRELIMINARIES: Standard β-NMF alternately updates H given W and W given H using the symmetry of the factorization.The two optimization steps are equivalent under transposition.
  • 2 PRELIMINARIES: MM constructs a nonnegative auxiliary function G(H|H̃) that upper-bounds the objective and matches it at the current iterate.Minimizing this surrogate is simpler than directly minimizing the original cost.
  • 2 PRELIMINARIES: Each MM update cannot increase the objective because C(H^(i+1)) ≤ G(H^(i+1)|H^(i)) ≤ G(H^(i)|H^(i)) = C(H^(i)).A fixed point of the update attains a local minimum under the stated equality conditions.
  • 2 PRELIMINARIES: The auxiliary function is built by separately majorizing convex and concave parts, producing simple β-dependent multiplicative updates.The form of the update changes across β < 1, 1 ≤ β ≤ 2, and β > 2.

3 THE MODEL FOR AUTOMATIC RELEVANCE DETERMINATION IN β-NMF

The model ties each dictionary column and activation row through a shared relevance scale, using nonnegative priors so irrelevant component pairs can be suppressed. Bayesian MAP estimation then yields group-sparse regularization and pruning within β-NMF.

  • 3 THE MODEL FOR AUTOMATIC RELEVANCE DETERMINATION IN β-NMF: Each column of W and corresponding row of H share a common scale parameter λk, whose reduction drives both component parts toward zero.This construction exploits the scale ambiguity between W and H.
  • 3 THE MODEL FOR AUTOMATIC RELEVANCE DETERMINATION IN β-NMF: Bayesian PCA motivates relevance weights, but this model retains nonnegativity and cannot analytically integrate out H.These differences require a formulation tailored to nonnegative factorization.
  • 3 THE MODEL FOR AUTOMATIC RELEVANCE DETERMINATION IN β-NMF: The model uses nonnegative Half-Normal or Exponential priors for W and H to preserve nonnegative basis and activation matrices.The two prior choices lead to different norm-based regularization forms.
  • 3 THE MODEL FOR AUTOMATIC RELEVANCE DETERMINATION IN β-NMF: When λk is small, the corresponding W column and H row have norms near zero and can be removed, making the factorization more parsimonious.The relevance weight therefore identifies components that are not relevant to the representation.
  • 3 THE MODEL FOR AUTOMATIC RELEVANCE DETERMINATION IN β-NMF: The β-divergence can act as a negative log-likelihood for Tweedie observations, linking the data-fit term to a statistical noise model.The connection applies when the Tweedie distribution is defined, with β-dependent support and special cases.
  • 3 THE MODEL FOR AUTOMATIC RELEVANCE DETERMINATION IN β-NMF: MAP estimation produces a penalized NMF objective whose relevance-weight terms trade off component norms and scale parameters.The objective combines the β-NMF fit with prior-induced regularization.
  • 3 THE MODEL FOR AUTOMATIC RELEVANCE DETERMINATION IN β-NMF: Optimizing λk drives some relevance parameters to a lower bound, pruning irrelevant component pairs through group-sparsity regularization.The grouped units are pairs consisting of a column of W and a row of H.

4 INFERENCE ALGORITHMS

The inference procedures combine automatic relevance determination with majorization-minimization to obtain tractable updates for β-NMF and jointly infer relevance weights and effective model order.

  • Majorization-minimization: The algorithms construct an upper-bounding auxiliary function so the regularized β-NMF updates can be solved in closed form.They separately handle β≥2 and β<2 by majorizing either the regularizer or the auxiliary function.
  • ℓ2-ARD β-NMF: For β>2, the method upper-bounds the ℓ2 regularizer elementwise using a moving-term inequality.The resulting modified auxiliary function yields multiplicative updates.
  • ℓ2-ARD β-NMF: For β≤2, the method majorizes the auxiliary function itself before differentiating it to obtain a simple update.The exponent used in the updates is summarized separately across β regimes.
  • Special cases: At β=0, 1, and 2, direct polynomial updates are possible, requiring cubic, quadratic, and linear equations respectively.For general rational β, the polynomial order depends on β.
  • Relevance-weight updates: The relevance update is obtained by setting the partial derivative of the objective with respect to λk to zero, and it is shared by ℓ1-ARD and ℓ2-ARD.The update uses the functions f(·) and c defined in the objective.
  • Stopping and model order: The algorithm stops when relative relevance-weight changes fall below τ and counts components whose weights exceed the lower bound B=b/c.When λk reaches B, the corresponding dictionary column and activation row are zero and pruned.
  • Hyperparameters: The dispersion parameter φ controls the tradeoff between data fidelity and regularization and is fixed in this work rather than estimated.Its interpretation depends on the assumed noise model, including Gaussian, Poisson, and multiplicative Gamma noise.
  • Hyperparameters: Method-of-moments estimates for a were not consistently satisfactory, especially when FN was insufficient, motivating small a values or future fully Bayesian estimation.The paper reports that smaller a relative to F+N typically produced better results.

5 CONNECTIONS WITH OTHER WORKS

The paper situates its unified β-NMF model-order framework among pruning, variational, projective, and sampling-based alternatives, emphasizing symmetric tied-factor pruning and monotonic optimization.

  • Existing approaches: Prior NMF model-order methods include computationally intensive MCMC and reversible-jump MCMC approaches, alongside automatic-pruning and variational methods.The paper presents its approach as part of a relatively limited literature on NMF model-order selection.
  • Comparison with pruning methods: Compared with the closest pruning method, this approach treats each dictionary column and corresponding activation row symmetrically.The competing method constrains W columns to unit norm and prunes only H rows.
  • Comparison with pruning methods: When λk reaches its lower bound, the corresponding wk and hk are driven to zero jointly, avoiding the competing method’s ill-posed unobservable W columns.The comparison concerns how pruning affects the parameterization of the factor model.
  • Projective NMF: Projective NMF uses H=W^T V with half-normal priors on W columns under an additive Gaussian noise model, whereas this paper addresses general β-NMF.The projective approach adapts EM for MAP estimation of W and its relevance parameters.
  • Position of the proposed framework: The proposed algorithms have low per-iteration complexity, are simple to implement, and decrease the objective at every iteration.The paper compares them with earlier methods on music decomposition and stock price prediction.

6 EXPERIMENTS

Experiments on synthetic, image, music, and stock-price data evaluate whether ℓ1- and ℓ2-ARD recover useful model orders and decompositions across β-divergences. ℓ1-ARD is generally more consistent at pruning, while ℓ2-ARD can model data well despite retaining extra components.

  • 6.1 Simulations with synthetic data: ℓ1-ARD correctly recovered Ktrue = 5 for a ≤100 across β ∈{0, 1, 2}, whereas ℓ2-ARD was less robust at recovering latent dimensionality.This held at approximately 10 dB SNR and included the generating value atrue = 50.
  • 6.1 Simulations with synthetic data: Across β values, estimation quality was relatively consistent, while performance depended more on noise level and β should reflect the assumed noise statistics.With F = 500, even ℓ2-ARD selected the correct order for a ≤25 and β ∈{1, 2}, with little initialization variability.
  • 6.2 Simulations with the swimmer dataset: On the swimmer dataset, ℓ1-ARD consistently estimated Ktrue = 16 up to a = 500, while ℓ2-ARD varied more across runs and hyperparameter values.The ℓ2-ARD dictionaries remained interpretable at a = 1000, although the additional components captured residual noise rather than being fully pruned.
  • 6.3 Music decomposition: ARD IS-NMF retained 6 components matching the expected piano decomposition, whereas IS-NMF split the second note and competing methods produced less accurate or overfit decompositions.The retained components represented four notes, hammer-string sound, and sustain-pedal sound; the relevance dropped by about 2000× from component 6 to 7.
  • 6.3 Music decomposition: The retrieved music decompositions were robust to a, but initialization remained an issue because only the best of 10 runs consistently produced the desired decomposition.This limits the interpretation of robustness for the music experiment.
  • 6.4 Prediction of stock prices: For stock-price prediction, ℓ2-ARD performed uniformly better than standard KL-NMF across a range of a, with missing-price NKLD around 0.2 versus above 0.23 for KL-NMF.The comparison used NKLD and NEUC, with similar results across the reported metrics; a separate method had mean NKLD 0.37 ± 0.03.

7 CONCLUSION

The paper develops a Bayesian β-NMF model with ARD-based group sparsity and efficient MM algorithms for selecting model order and learning nonnegative factors. Experiments show competitive performance and flexibility across data types, while fully Bayesian inference remains a future direction.

  • The Bayesian model ties columns of W and rows of H through a common prior scale parameter, addressing their scale ambiguity.
  • MAP estimation becomes a penalized NMF problem with a group-sparsity-inducing regularizer.
  • MM algorithms support all β values and both ℓ1- and ℓ2-norm group regularization while ensuring monotonic objective decrease.
  • The updates have linear complexity in F, K, and N, preserve nonnegativity under positive initialization, and are easily implemented.
  • The approach achieved competitive performance on synthetic and real-world datasets and accommodates varied observation noise and prior structures in one framework.
  • More sophisticated fully Bayesian inference could improve inference and enable more principled hyperparameter estimation beyond the presented MAP approach.
Loading 1111.6085v3…