PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient and Generalizable Archetypal Analysis for Discrete Data

A. Emilie J. Wedenborg, Jesper Løve Hinrich, Morten Mørup

arXiv:2610.12035v1stat.MLcs.LG

TL;DR

Classical least-squares archetypal analysis is poorly suited to discrete observations, motivating likelihood-based methods. This paper introduces DAAA and predictive-likelihood model selection; synthetic experiments recover true model complexity, while real-data archetypes represent meaningful domain-specific profiles.

  • Problem

    Classical least-squares AA is suboptimal for binary, count, and categorical observations, motivating likelihood-based analysis for discrete data.

    Source: B. Archetypal Analysis for Discrete Data · p. 1, A. Optimization Challenges in… · p. 1

  • Method

    DAAA combines likelihood-based AA with local quadratic approximations, SMO and constrained active-set updates, and a predictive-likelihood criterion for selecting archetype count.

    Source: D. C-update by constrained active-set… · p. 4, §V · p. 10

  • Results

    The predictive-likelihood criterion recovered true model complexity in synthetic experiments, and real-data archetypes represented meaningful cancer-mutation, PBMC gene-expression, and microbiome body-site profiles.

    Source: §V · pp. 10–11

  • Takeaways & Limitations

    The framework provides an efficient likelihood-based alternative for discrete-data AA and assesses archetype models by their generalization to new data.

    Source: §V · p. 11

    AA remains non-convex and initialization-sensitive, and the framework assumes a specific likelihood formulation with separable likelihoods.

    Source: A. Limitations · p. 10

Abstract

from arXiv · show

Archetypal Analysis (AA) represents observations as convex combinations of extremal data-driven profiles, yielding interpretable low-dimensional descriptions of complex datasets. Classical AA relies on a least-squares objective, which is poorly suited to discrete observations such as binary, count, and categorical data. We introduce an efficient likelihood-based framework for AA supporting Bernoulli, Poisson, and multinomial observation models. Our optimization scheme employs local quadratic approximations of the negative log-likelihood, enabling constrained updates through sequential minimal optimization (SMO) and an active-set method. Scalability is improved by bounding the active set while preserving simplex feasibility. We further introduce a cross-validated predictive likelihood criterion for selecting the number of archetypes, providing a principled alternative to reconstruction-error heuristics and stability-based diagnostics. Synthetic experiments demonstrate computational efficiency and accurate recovery of model complexity. Applications to single-cell RNA sequencing, microbiome composition, and somatic mutation data show that the learned archetypes capture interpretable domain-specific structures while achieving competitive likelihood fits and stable solutions. Overall, the proposed framework enables efficient likelihood-based archetypal analysis of discrete data, complemented by predictive likelihood-based model selection.

I. INTRODUCTION

Archetypal analysis describes observations through convex combinations of extreme, data-driven profiles, but its conventional least-squares optimization is poorly suited to discrete data. DAAA combines likelihood-based quadratic approximations with constrained SMO and active-set updates to address this gap.

I. INTRODUCTION

  • AA represents observations as convex combinations of extreme profiles, distinguishing it from clustering and factorization that do not enforce archetype extremality.Its archetypes lie within the data convex hull, yielding interpretable profiles of extreme yet realizable configurations.Source: §I · p. 1

A. Optimization Challenges in Archetypal Analysis

  • AA estimation is jointly non-convex, so standard alternating optimization solves two convex subproblems and converges to a local optimum.Both the archetype mixtures and the reconstruction weights must be learned.Source: A. Optimization Challenges in… · p. 1

B. Archetypal Analysis for Discrete Data

  • Binary, categorical, and count observations make classical least-squares AA suboptimal, motivating a computationally efficient, principled likelihood-based framework for discrete data.Prior approaches include multiplicative updates, data transformations, and archetypoids, with stated convergence, initialization, distortion, or flexibility drawbacks.Source: B. Archetypal Analysis for Discrete Data · pp. 1–2

C. Proposed Framework

  • DAAA uses local quadratic approximations of the negative log-likelihood, SMO updates for reconstruction weights, and bounded active-set updates for archetype construction weights.The quadratic strategy is stated to extend to twice-differentiable separable losses.Source: C. Proposed Framework · p. 2

D. Model Selection via Predictive Likelihood

Selecting the number of archetypes remains an open problem, often approached through heuristic reconstruction-error curves or stability measures. The paper proposes likelihood-based AA and held-out predictive likelihood to assess model generalization and select archetype count.

D. Model Selection via Predictive Likelihood

  • Held-out predictive log-likelihood selects K by model generalization, offering an alternative to reconstruction-error heuristics and stability measures.The criterion evaluates the predictive likelihood of a trained archetypal model.Source: D. Model Selection via Predictive… · p. 2

E. Contributions

  • The paper contributes likelihood-based AA with local quadratic approximations, extending the optimization strategy to general twice-differentiable separable losses.Its stated contributions also include constrained active-set and SMO procedures for the two convex subproblems.Source: E. Contributions · p. 2

A. Likelihood-Optimized Archetypal Analysis

  • AA represents observations as convex combinations of archetypes, with each archetype constrained to the convex hull of observed data.The formulation estimates C and S under simplex constraints by minimizing negative log-likelihood.Source: A. Likelihood-Optimized Archetypal… · p. 2
  • The loss function determines the likelihood used to model the data, while alternating optimization updates C and S because each subproblem is convex when the other matrix is fixed.The joint problem is non-convex.Source: A. Likelihood-Optimized Archetypal… · p. 3

B. Quadratic Approximation of the Likelihood

The likelihood is locally approximated by a second-order expansion, turning alternating updates into simplex-constrained quadratic subproblems. SMO reduces reconstruction-weight updates to analytically solvable pairwise problems.

B. Quadratic Approximation of the Likelihood

  • A second-order Taylor approximation of the negative log-likelihood converts each alternating subproblem into a convex quadratic program under simplex constraints.The resulting form is optimized with SMO for S and a constrained active-set procedure for C.Source: B. Quadratic Approximation of the… · p. 3

C. Updating S through sequential minimal optimization

  • SMO decomposes the large quadratic program for S into the smallest possible subproblems, fitting its low-dimensional dense reconstruction-weight matrix.The framework optimizes archetypes in pairs iteratively.Source: C. Updating S through sequential… · p. 3
  • SMO updates paired archetypes by reparameterizing their weights with a shared total t_j and a single α_j in [0, 1].This reduces the pairwise subproblem to a quadratic optimization in α_j with a closed-form update, clipped to [0, 1].Source: C. Updating S through sequential… · p. 3

D. C-update by constrained active-set optimization

The C update uses local quadratic likelihood approximations and a simplex-constrained active set to exploit sparse archetype construction. When the active set grows beyond its bound, a simplex-preserving proxy replaces the current active combination.

D. C-update by constrained active-set optimization

  • A constrained active-set strategy exploits the expected sparsity of archetype construction, updating C while the reconstruction weights S are fixed.A second-order likelihood expansion supplies first- and second-order terms for each column update.Source: D. C-update by constrained active-set… · p. 3
  • The active update enforces the simplex equality directly in the KKT system, with inactive coefficients set to zero and non-negativity conditions governing active-set changes.A small ridge term supports numerical stability.Source: D. C-update by constrained active-set… · p. 4
  • The active set is capped at Nmax to control computational cost, and an oversized set is reset using a proxy equal to the current active convex combination.The proxy is a simplex-preserving surrogate observation whose contribution to the quadratic subproblem is computed from the original likelihood expansion.Source: D. C-update by constrained active-set… · p. 4

E. Likelihood specific derivatives

The likelihood-specific updates use chain-rule derivatives for both model parameter matrices. Their Jacobian, gradient, and curvature terms are tailored to the S- and C-updates and the observation model.

E. Likelihood specific derivatives

  • Both S- and C-updates use partial derivatives of the loss with respect to model parameters via the chain rule.The generic update structure is summarized in Tables I and II.Source: E. Likelihood specific derivatives · p. 4, Table I · p. 4
  • For fixed C, the S-update defines a Jacobian term and combines the loss derivative with an adjustment term in its update direction.The second-order terms are specified for the Gaussian, Bernoulli, Poisson, and multinomial likelihoods.Source: E. Likelihood specific derivatives · p. 4
  • For fixed S, the C-update defines a Jacobian and uses likelihood-specific partial derivatives and Hessian approximations.For the multinomial likelihood, the feature index is replaced by a feature-category pair.Source: E. Likelihood specific derivatives · p. 4

F. Predictive Likelihood

The section selects the number of archetypes by evaluating held-out predictive likelihood. It approximates predictive integration using reconstructed training parameters and aggregates held-out scores across cross-validation folds.

F. Predictive Likelihood

  • Held-out observations are scored under an empirical mixture over reconstructed training parameters to compare candidate numbers of archetypes.The fitted archetypal representation is based on the training data, and the likelihood contribution depends on the observation model.Source: F. Predictive Likelihood · pp. 4–5
  • With a uniform prior over the simplex, the posterior over sample weights is proportional to the training likelihood, allowing training samples to approximate the predictive integral.The uniform prior is specified as Dirichlet(s|1).Source: F. Predictive Likelihood · p. 5
  • For Poisson and multinomial models, terms independent of the reconstructed parameter are omitted because they do not affect comparisons across K.The likelihood contribution is observation-model specific.Source: F. Predictive Likelihood · p. 5
  • F-fold cross-validation scores each candidate K by summing held-out predictive log-likelihoods across folds.The likelihood contributions used by the criterion are summarized in Table III.Source: F. Predictive Likelihood · p. 5, Table III · p. 5

G. Normalized Mutual Information

Normalized Mutual Information (NMI) evaluates the consistency of solutions across different initializations. It treats columns of S as probability distributions and uses mutual information and entropy to compare two solutions.

G. Normalized Mutual Information

  • NMI evaluates solution consistency across different initializations of S, with high values indicating stability and low values indicating instability.The columns of S are treated as probability distributions.Source: G. Normalized Mutual Information · p. 5
  • The NMI comparison is between two solutions, Sr and Sr′.The section defines mutual information and entropy for the measure.Source: G. Normalized Mutual Information · p. 5
  • The displayed NMI expression combines mutual information between solutions with their entropies.The equation is provided as the measure for comparing Sr and Sr′.Source: G. Normalized Mutual Information · p. 5

H. Computational complexity and memory usage.

The S-update has costs tied to the number of samples and archetypes, while the C-update presents the main scalability challenge. Bounding its active set makes its practical memory use depend primarily on the bound rather than the full sample count.

H. Computational complexity and memory usage

  • A full S-update sweep costs O(NK^2) after likelihood-specific derivatives are formed, whose construction typically costs O(MNK).Each sweep updates all archetype pairs.Source: H. Computational complexity and memory… · p. 6
  • Bounding the C-update active set at Nmax limits each reduced solve to at most Nmax explicit variables and reduces Hessian storage to O(Nmax^2).Without the bound, materializing the full Hessian can require O(N^2) memory.Source: H. Computational complexity and memory… · p. 6
  • When the active set reaches its bound, a proxy vector preserves its accumulated convex combination while explicit active entries reset.The full coefficient vector remains represented by the proxy and explicit entries, so optimization can continue exploring observations.Source: H. Computational complexity and memory… · p. 6

I. Extension of PCHA to discrete data

The PCHA architecture was extended to discrete observations with likelihood-consistent gradients for Bernoulli, Poisson, and multinomial models. Experiments compare methods on synthetic and real data using controlled seeds and predictive cross-validation.

I. Extension of PCHA to discrete data

  • Likelihood-consistent gradients extend PCHA to Bernoulli, Poisson, and multinomial observations, enabling probabilistic modeling within its established architecture.The extension also enables direct empirical comparison with PCHA.Source: §I · p. 6

III. RESULTS

  • Experiments first assess optimization on synthetic data with known archetype counts, then evaluate the framework on three real datasets.Source: §III · p. 6

A. Reproducibility

  • Models were evaluated over five random seeds and five-fold predictive cross-validation, with shared fold splits and initial values for direct method comparisons.The synthetic settings used K⋆ = 5 and candidate K values from 2 to 15; DAAA used a 25% active-set cap unless stated otherwise.Source: A. Reproducibility · p. 6

B. Synthetic Data Experiments

Synthetic experiments compare recovery, runtime, stability, and active-set convergence across data distributions. Predictive likelihood also identifies model complexity where training-fit measures continue to improve with larger K.

  • Across four data-generating distributions and k = 5, 10, 15, PAA, PCHA, and DAAA reach essentially the same final loss in every setting; loss ratios remain within ±2% relative to DAAA.Source: B. Synthetic Data Experiments · p. 6
  • DAAA is competitive across distributions, but runtime varies: PCHA is much faster on Gaussian data, while at K = 10 and 15 it is up to 4× slower on multinomial data.PAA becomes comparable to or faster than DAAA on Poisson and multinomial data at K = 15, but remains slower on Gaussian and Bernoulli data.Source: B. Synthetic Data Experiments · pp. 6–7
  • Stability declines with K for all methods, from near-perfect NMI at K = 5 to approximately 0.85–0.90 on Gaussian and 0.60–0.65 on multinomial data at K = 15.The methods have comparable NMI at each setting.Source: B. Synthetic Data Experiments · p. 7
  • Active sets below the full sample achieve faster early descent; fractions of at least 5% match full-set final loss for Gaussian, binary, and count data, while multinomial requires at least 25%.Multinomial active sets of 1% and 5% leave a persistent loss gap.Source: B. Synthetic Data Experiments · p. 7, Figure 2 · p. 7
  • After the optimal K, predictive log-likelihood declines while variance explained and NMI increase, making predictive likelihood a quantitative signal for model order.The signal becomes clearer as noise increases.Source: B. Synthetic Data Experiments · p. 7

C. Real Data experiments

Real-data experiments assess likelihood fit, stability, runtime, and archetype interpretability across mutation, single-cell RNA-sequencing, and microbiome datasets. The selected model orders yield domain-specific structures, while the discussion notes both optimization and scope considerations.

C. Real Data experiments

  • Across three datasets, DAAA generally produces more stable solutions and better likelihood fits than PAA, while fitting faster than PCHA despite similar solution quality.The benchmarks cover MSK Heme Bernoulli, PBMC3k Poisson, and HMP microbiome multinomial data; DAAA uses a 25% active set.Source: C. Real Data experiments · p. 8, Figure 4 · p. 8
  • Predictive likelihood selects K = 10 for MSK Heme, K = 40 for PBMC3k, and K = 2 for HMP microbiome, with interpretable structures reported across the domains.MSK Heme archetypes include AML, MDS, and distinct B-NHL profiles.Source: C. Real Data experiments · p. 8, Figure 5 · p. 9
  • The selected real-data models show distinct variation patterns: cancer-type-specific mutation profiles, PBMC cell-type expression patterns, and microbiome composition associated with body site and sex.Source: C. Real Data experiments · p. 8, §IV · p. 10

IV. DISCUSSION

  • The constrained active-set procedure improves convergence with minimal compromise in solution quality, supporting its use to scale the method.Source: §IV · p. 9
  • The authors interpret PAA’s poorer likelihoods as an optimization issue rather than evidence against archetypal representations; multiplicative updates can converge slowly and calibrate probabilities or intensities poorly.The discussion links this concern to rare events, zero counts, and low-probability categories in discrete likelihoods.Source: §IV · p. 9
  • The optimization and model-order frameworks may extend beyond the discrete likelihoods considered, although the present study focuses on those likelihoods.Source: §IV · p. 10

A. Limitations

The conclusion reports recovery of model complexity in synthetic experiments and interpretable domain-specific archetypes in real-data examples. It also notes limits involving active-set precision, qualitative validation, and predictive scoring with limited training data.

A. Limitations

  • A constrained active set can trade exactness for scalability and fit time, but reduces numeric precision when that precision is critical.Source: A. Limitations · p. 10
  • Predictive log-likelihood indicated optimal K, but model selection and archetype validation were assessed only qualitatively.Source: A. Limitations · p. 10
  • With few training samples, the empirical training S-matrix can be sparse and unstable, making predictive likelihood sensitive to train-test splits and potentially penalizing reasonable archetypes.Source: A. Limitations · p. 10

V. CONCLUSION

  • For Bernoulli, Poisson, and multinomial data, DAAA combines local quadratic likelihood approximations, SMO mixture-weight updates, and constrained active-set archetype-weight updates.Source: §V · p. 10
  • Synthetic experiments recovered true model complexity, while real-data archetype counts yielded interpretable profiles for cancer mutations, PBMC gene expression, and microbiome variation.Source: §V · pp. 10–11
  • Predictive likelihood provides model-order assessment based on how well the extracted archetypal polytope generalizes to new data.Source: §V · p. 11
Loading 2610.12035v1…