# Copyright Contributors to the Cellarium project.
# SPDX-License-Identifier: BSD-3-Clause
import math
import warnings
from abc import ABC, abstractmethod
from collections.abc import Callable, Sequence
from typing import Any, Literal
import lightning.pytorch as pl
import numpy as np
import torch
import torch.nn.functional as F
from lightning.pytorch.strategies import DDPStrategy
from cellarium.ml.models.model import CellariumModel
from cellarium.ml.utilities.testing import (
assert_arrays_equal,
assert_columns_and_array_lengths_equal,
)
warnings.filterwarnings("ignore")
@torch.compile()
@torch.no_grad()
def solve_nnls_fista_precomputed(
AtA: torch.Tensor,
AtB: torch.Tensor,
initial_x: torch.Tensor,
max_iter: int = 100,
return_history: bool = False,
) -> tuple[torch.Tensor, torch.Tensor | None]:
"""
Highly optimized FISTA core for torch.compile.
Assumes AtA and AtB are already precomputed.
"""
# Compute the Lipschitz constant L (largest eigenvalue of AtA).
# eigvalsh is faster and exact, but not implemented on MPS; power iteration
# uses only matmul and works on all devices.
if AtA.device.type == "mps":
v = torch.ones(*AtA.shape[:-1], 1, device=AtA.device, dtype=AtA.dtype)
for _ in range(10):
v = AtA @ v
v = v / v.norm(dim=-2, keepdim=True).clamp(min=1e-8)
L = (v.transpose(-2, -1) @ AtA @ v).clamp(min=1e-12) # [r, 1, 1]
else:
eigenvals = torch.linalg.eigvalsh(AtA)
L = torch.clamp(eigenvals[..., -1:], min=1e-12).unsqueeze(-1) # [r, 1, 1]
x = initial_x.clone()
y = initial_x.clone()
# Initialize momentum scalar
t = 1.0
# torch.compile specializes on Python booleans, so the False branch generates
# a much smaller kernel (no per-iteration tensors kept alive), which is required
# to stay within Metal's 31 constant-buffer limit on MPS.
history: torch.Tensor | None = torch.zeros(max_iter, device=AtA.device, dtype=AtA.dtype) if return_history else None
# Fixed iteration loop for compilation compatibility
for i in range(max_iter):
# Gradient step
grad = AtA @ y - AtB
x_new = torch.clamp(y - grad / L, min=0.0)
if return_history:
assert history is not None
history[i] = (x_new - x).abs().max()
# Beck & Teboulle Momentum update
t_new = (1.0 + math.sqrt(1.0 + 4.0 * t**2)) / 2.0
momentum = (t - 1.0) / t_new
y = x_new + momentum * (x_new - x)
x = x_new
t = t_new
return x, history
@torch.compile()
@torch.no_grad()
def nmf_compute_factors_fista(
w_rkg: torch.Tensor,
A_rkk: torch.Tensor, # This is H^T H
B_rkg: torch.Tensor, # This is H^T X
max_iter: int = 100,
return_history: bool = False,
) -> tuple[torch.Tensor, torch.Tensor | None]:
"""
Wrapper to update Factors using FISTA.
"""
# w_rkg has shape [r, k, g].
# A_rkk @ w_rkg works directly natively via batched matrix multiplication.
w_rkg_new, history = solve_nnls_fista_precomputed(
AtA=A_rkk, AtB=B_rkg, initial_x=w_rkg, max_iter=max_iter, return_history=return_history
)
return w_rkg_new, history
@torch.compile()
@torch.no_grad()
def nmf_compute_loadings_fista(
x_ng: torch.Tensor,
w_rkg: torch.Tensor,
h_rnk: torch.Tensor,
max_iter: int = 100,
return_history: bool = False,
) -> tuple[torch.Tensor, torch.Tensor | None]:
"""
Wrapper to update Loadings using FISTA.
"""
# Precompute the transposed equivalents: W W^T and W X^T
# W W^T shape: [r, k, k]
wwT_rkk = torch.einsum("rkg,rhg->rkh", w_rkg, w_rkg)
# W X^T shape: [r, k, n]
wxT_rkn = torch.einsum("rkg,ng->rkn", w_rkg, x_ng)
# h_rnk is [r, n, k]. We transpose to [r, k, n] to match FISTA's Ax=B expectation
h_transposed_rkn = h_rnk.transpose(-2, -1)
# Solve for transposed H
h_new_transposed, history = solve_nnls_fista_precomputed(
AtA=wwT_rkk, AtB=wxT_rkn, initial_x=h_transposed_rkn, max_iter=max_iter, return_history=return_history
)
return h_new_transposed.transpose(-2, -1), history
def nmf_frobenius_loss(x_ng: torch.Tensor, loadings_nk: torch.Tensor, factors_kg: torch.Tensor):
# compute prediction error as the frobenius norm
return F.mse_loss(torch.matmul(loadings_nk, factors_kg), x_ng, reduction="sum")
def _reduction_dtype(device: torch.device) -> torch.dtype:
"""Widest float the device supports, for the scalar reductions in the Frobenius loss.
MPS has no float64 at all, so there the reductions stay in float32. That is accurate to
roughly 1e-6 relative to the loss unless the fit is nearly exact.
"""
return torch.float32 if device.type == "mps" else torch.float64
def compute_x_squared_sum(x_ng: torch.Tensor) -> torch.Tensor:
"""
``||X||_F^2`` as a scalar, for sharing across calls to :func:`frobenius_loss_trace_compiled`
(e.g. when looping over ``k``) rather than recomputing it each time.
"""
return x_ng.pow(2).sum(dtype=_reduction_dtype(x_ng.device))
@torch.compile()
@torch.no_grad()
def frobenius_loss_trace_compiled(
x_ng: torch.Tensor,
h_rnk: torch.Tensor,
w_rkg: torch.Tensor,
x_squared_sum: torch.Tensor | None = None,
) -> torch.Tensor:
"""
Per-replicate ``||X - H W||_F^2`` computed *without* materializing the reconstruction.
Uses :math:`\\|X - HW\\|_F^2 = \\|X\\|^2 - 2\\langle HX, W\\rangle + \\langle H^\\top H,
WW^\\top\\rangle`, so the intermediates are ``(r, k, g)`` and ``(r, k, k)`` rather than
``(r, n, g)``. At ``r=100, n=2048, g=2000`` that is 80 MB instead of 1.6 GB.
The three scalar terms are reduced in float64 where the device supports it (float32 on MPS),
which removes cancellation in the final combination. The ``(r, k, g)`` and ``(r, k, k)``
contractions themselves run in the input dtype.
Args:
x_ng: Data, shape ``(n, g)``.
h_rnk: Loadings, shape ``(r, n, k)``.
w_rkg: Factors, shape ``(r, k, g)``.
x_squared_sum: Optional precomputed :func:`compute_x_squared_sum` of ``x_ng``, shared across
calls that use the same ``x_ng``. Computed here if not given.
Returns:
Sum of squared errors per replicate, shape ``(r,)``.
"""
reduction_dtype = _reduction_dtype(x_ng.device)
if x_squared_sum is None:
x_squared_sum = compute_x_squared_sum(x_ng)
hx_rkg = torch.einsum("rnk,ng->rkg", h_rnk, x_ng)
hth_rkk = torch.einsum("rnk,rnj->rkj", h_rnk, h_rnk)
wwt_rkk = torch.einsum("rkg,rjg->rkj", w_rkg, w_rkg)
cross_r = (hx_rkg * w_rkg).sum(dim=(-2, -1), dtype=reduction_dtype)
quad_r = (hth_rkk * wwt_rkk).sum(dim=(-2, -1), dtype=reduction_dtype)
sse_r = x_squared_sum.to(reduction_dtype) - 2.0 * cross_r + quad_r
return sse_r.clamp(min=0.0).to(w_rkg.dtype)
def solve_nnls_fista(A, B, max_iter=1000, tol=1e-6):
"""
FISTA algorithm for NNLS solving Ax = B for x >= 0
Args:
A: Coefficient matrix of shape (..., m, n)
B: Right-hand side of shape (..., m, k)
max_iter: Maximum number of iterations
tol: Convergence tolerance
Returns:
x: Solution of shape (..., n, k) with x >= 0
"""
# Handle batch dimensions
*batch_dims, m, n = A.shape
*batch_dims_B, m_B, k = B.shape
assert m == m_B, f"Incompatible dimensions: A has {m} rows, B has {m_B} rows"
# Precompute AtA and AtB for efficiency
AtA = A.transpose(-2, -1) @ A # (..., n, n)
AtB = A.transpose(-2, -1) @ B # (..., n, k)
# Compute Lipschitz constant (largest eigenvalue of AtA).
# eigvals is not implemented on MPS; power iteration uses only matmul.
if AtA.device.type == "mps":
v = torch.ones(*AtA.shape[:-1], 1, device=AtA.device, dtype=AtA.dtype)
for _ in range(20):
v = AtA @ v
v = v / v.norm(dim=-2, keepdim=True).clamp(min=1e-8)
L = (v.transpose(-2, -1) @ AtA @ v).clamp(min=1e-12) # (..., 1, 1)
else:
eigenvals = torch.linalg.eigvals(AtA).real # (..., n)
L = eigenvals.max(dim=-1, keepdim=True)[0].unsqueeze(-1) # (..., 1, 1)
# Initialize variables
x = torch.zeros(*batch_dims, n, k, device=A.device, dtype=A.dtype)
y = x.clone()
t = torch.ones(*batch_dims, 1, 1, device=A.device, dtype=A.dtype)
for i in range(max_iter):
x_old = x.clone()
# Gradient step: grad = AtA @ y - AtB
grad = AtA @ y - AtB
x_new = torch.clamp(y - grad / L, min=0)
# Momentum update
t_new = (1 + torch.sqrt(1 + 4 * t**2)) / 2
y = x_new + ((t - 1) / t_new) * (x_new - x)
x = x_new
t = t_new
# Check convergence
if torch.norm(x - x_old) < tol:
break
return x
@torch.compile()
@torch.no_grad()
def nmf_torch_update_loadings_hals_compiled(
x_ng: torch.Tensor,
w_rkg: torch.Tensor,
h_rnk: torch.Tensor,
max_iter: int = 200,
) -> None:
"""
Compiled version of the HALS loadings update, run for exactly ``max_iter`` iterations.
Updates ``h_rnk`` in place; convergence is checked by the caller between calls.
"""
assert x_ng.shape[0] == h_rnk.shape[-2]
assert x_ng.shape[1] == w_rkg.shape[-1]
assert w_rkg.shape[-2] == h_rnk.shape[-1]
wwT_rkk = torch.einsum("rkg,rhg->rkh", w_rkg, w_rkg)
xwT_rnk = torch.einsum("ng,rkg->rnk", x_ng, w_rkg)
# Use a fixed number of iterations instead of dynamic convergence
# This makes the function more amenable to compilation
for i in range(max_iter):
for k in range(h_rnk.shape[-1]):
numer_rn = xwT_rnk[..., k] - torch.einsum("rnk,rk->rn", h_rnk, wwT_rkk[..., k])
h_rn = h_rnk[..., k]
# Avoid division by zero using torch.where instead of manual checks
denom = wwT_rkk[:, k, k].unsqueeze(-1)
hvec_rn = torch.where(denom > 1e-12, torch.clamp(h_rn + numer_rn / denom, min=0.0), torch.zeros_like(h_rn))
h_rnk[..., k] = hvec_rn
@torch.no_grad()
def nmf_torch_update_loadings_hals_with_compile(
x_ng: torch.Tensor,
w_rkg: torch.Tensor,
h_rnk: torch.Tensor,
max_iter: int = 200,
h_tol: float = 0.05,
) -> None:
"""
Wrapper that uses compiled function with convergence checking.
"""
# Use smaller chunks of iterations with convergence checks
chunk_size = 10
total_iterations = 0
while total_iterations < max_iter:
h_old = h_rnk.clone()
current_chunk = min(chunk_size, max_iter - total_iterations)
# Run compiled function for a chunk of iterations
nmf_torch_update_loadings_hals_compiled(x_ng, w_rkg, h_rnk, current_chunk)
total_iterations += current_chunk
# Check convergence
max_change = (h_rnk - h_old).abs().max()
mean_h = h_rnk.mean(dim=(-2, -1))
relative_change = max_change / torch.clamp(mean_h.max(), min=1e-12)
if relative_change < h_tol:
# print(f"NMF HALS loadings update converged in {total_iterations} iterations.")
break
# else:
# print("NMF HALS loadings update reached max iterations without convergence.")
@torch.compile()
@torch.no_grad()
def nmf_torch_update_factors_hals_compiled(
w_rkg: torch.Tensor,
A_rkk: torch.Tensor,
B_rkg: torch.Tensor,
max_iter: int = 200,
) -> None:
"""
Compiled version of the HALS factors update, run for exactly ``max_iter`` iterations.
Updates ``w_rkg`` in place; convergence is checked by the caller between calls.
"""
# Use a fixed number of iterations instead of dynamic convergence
# This makes the function more amenable to compilation
for j in range(max_iter):
for k in range(A_rkk.shape[-1]):
numer_rg = B_rkg[:, k, :] - torch.einsum("rk,rkg->rg", A_rkk[:, k, :], w_rkg)
w_new_rg = w_rkg[:, k, :] + numer_rg / A_rkk[:, k, k].unsqueeze(-1)
# Avoid division by zero using torch.where instead of manual checks
w_new_rg = torch.where(torch.isnan(w_new_rg), torch.zeros_like(w_new_rg), torch.clamp(w_new_rg, min=0.0))
w_rkg[:, k, :] = w_new_rg
@torch.no_grad()
def nmf_torch_update_factors_hals_with_compile(
w_rkg: torch.Tensor,
A_rkk: torch.Tensor,
B_rkg: torch.Tensor,
max_iter: int = 200,
w_tol: float = 0.05,
) -> None:
"""
Wrapper that uses compiled function with convergence checking.
"""
# Use smaller chunks of iterations with convergence checks
chunk_size = 10
total_iterations = 0
while total_iterations < max_iter:
w_old = w_rkg.clone()
current_chunk = min(chunk_size, max_iter - total_iterations)
# Run compiled function for a chunk of iterations
nmf_torch_update_factors_hals_compiled(w_rkg, A_rkk, B_rkg, current_chunk)
total_iterations += current_chunk
# Check convergence
max_change = (w_rkg - w_old).abs().max()
mean_w = w_rkg.mean(dim=(-2, -1))
relative_change = max_change / torch.clamp(mean_w.max(), min=1e-12)
if relative_change < w_tol:
break
def find_local_minima(mean_neighbor_distance_m: torch.Tensor, n_bins: int = 100) -> list[float]:
"""
Helper function to find local minima in a histogram of distance values.
Args:
mean_neighbor_distance_m: 1D tensor of distance values
n_bins: Number of bins for the histogram (default: 100)
Returns:
List of distance values corresponding to local minima (bin centers)
"""
# Convert to numpy for histogram computation
distances = mean_neighbor_distance_m.cpu().numpy()
# Create histogram
counts, bin_edges = np.histogram(distances, bins=n_bins, range=(0, 1))
# Calculate bin centers
bin_centers = (bin_edges[:-1] + bin_edges[1:]) / 2
# Smooth the histogram slightly to reduce noise
if len(counts) >= 3:
# Simple smoothing: each bin becomes average of itself and neighbors
smoothed_counts = counts.copy()
for i in range(1, len(counts) - 1):
smoothed_counts[i] = (counts[i - 1] + counts[i] + counts[i + 1]) / 3
counts = smoothed_counts
# Find local minima in the histogram counts
# A local minimum is a point that is smaller than or equal to both neighbors
# but at least one neighbor must be strictly larger
local_minima_indices = []
for i in range(1, len(counts) - 1):
left_count = counts[i - 1]
center_count = counts[i]
right_count = counts[i + 1]
# Check if this is a local minimum
if (
center_count <= left_count
and center_count <= right_count
and (center_count < left_count or center_count < right_count)
):
local_minima_indices.append(i)
# Convert indices to actual distance values (bin centers)
candidate_values = [bin_centers[i] for i in local_minima_indices]
# Also consider the first and last bins as potential candidates
# if they are at the boundaries and could be minima
if len(counts) > 1:
# Add first bin if it's a potential minimum
if counts[0] <= counts[1]:
candidate_values.insert(0, bin_centers[0])
# Add last bin if it's a potential minimum
if counts[-1] <= counts[-2]:
candidate_values.append(bin_centers[-1])
# Remove duplicates and sort
candidate_values = sorted(list(set(candidate_values)))
# Filter out values that are too close to each other (within 5% of range)
min_distance = 0.05
filtered_candidates: list[float] = []
for val in candidate_values:
if not any(abs(val - existing) < min_distance for existing in filtered_candidates):
filtered_candidates.append(val)
candidate_values = filtered_candidates
return candidate_values
def online_dictionary_update_nmf_torch_hals(
x_ng: torch.Tensor,
factors_rkg: torch.Tensor,
loadings_rnk: torch.Tensor,
A_rkk: torch.Tensor,
B_rkg: torch.Tensor,
n_iterations: int = 200,
alpha_tol: float = 0.05,
D_tol: float = 0.05,
exponential_decay_rho: float = 1.0,
) -> dict[str, torch.Tensor]:
"""
Algorithm adapted from the nmf-torch github library.
Args:
x_ng: The data.
factors_rkg: The matrix of gene expression programs (Mairal's dictionary D).
loadings_rnk: The matrix of cell loadings (Mairal's coefficients alpha).
A_rkk: Mairal's matrix A.
B_rkg: Mairal's matrix B.
n_iterations: The number of iterations to perform.
alpha_tol: The tolerance for the change in alpha for stopping.
D_tol: The tolerance for the change in D for stopping.
exponential_decay_rho: The exponential decay factor for A and B updates (default: 1, no decay).
Returns:
dict with keys:
"factors_rkg": The updated dictionary factors_rkg.
"A_rkk": The updated matrix A.
"B_rkg": The updated matrix B.
"""
# inplace update loadings_rnk
nmf_torch_update_loadings_hals_with_compile(
x_ng=x_ng,
w_rkg=factors_rkg,
h_rnk=loadings_rnk,
max_iter=n_iterations,
h_tol=alpha_tol,
)
with torch.no_grad():
# update A and B, Mairal Algorithm 1 step 5 and 6 (sums are taken over the cells of all ranks if distributed)
AtA_rkk, AtX_rkg, n_global = all_reduce_mairal_sufficient_statistics(
*mairal_sufficient_statistics(loadings_rnk, x_ng)
)
A_rkk = exponential_decay_rho * A_rkk + AtA_rkk / n_global
B_rkg = exponential_decay_rho * B_rkg + AtX_rkg / n_global
# inplace update factors_rkg
nmf_torch_update_factors_hals_with_compile(
w_rkg=factors_rkg,
A_rkk=A_rkk,
B_rkg=B_rkg,
max_iter=n_iterations,
w_tol=D_tol,
)
return {"factors_rkg": factors_rkg, "A_rkk": A_rkk, "B_rkg": B_rkg}
def online_dictionary_update_fista(
x_ng: torch.Tensor,
factors_rkg: torch.Tensor,
loadings_rnk: torch.Tensor,
A_rkk: torch.Tensor,
B_rkg: torch.Tensor,
n_iterations: int = 100,
exponential_decay_rho: float = 1.0,
return_history: bool = False,
) -> dict[str, torch.Tensor]:
"""
Algorithm adapted from the nmf-torch github library.
Args:
x_ng: The data.
factors_rkg: The matrix of gene expression programs (Mairal's dictionary D).
loadings_rnk: The matrix of cell loadings (Mairal's coefficients alpha).
A_rkk: Mairal's matrix A.
B_rkg: Mairal's matrix B.
n_iterations: The number of iterations to perform.
exponential_decay_rho: The exponential decay factor for A and B updates (default: 1, no decay).
Returns:
dict with keys:
"factors_rkg": The updated dictionary factors_rkg.
"A_rkk": The updated matrix A.
"B_rkg": The updated matrix B.
"""
# update loadings_rnk
loadings_rnk, loadings_history = nmf_compute_loadings_fista(
x_ng=x_ng,
w_rkg=factors_rkg,
h_rnk=loadings_rnk,
max_iter=n_iterations,
return_history=return_history,
)
with torch.no_grad():
# update A and B, Mairal Algorithm 1 step 5 and 6 (sums are taken over the cells of all ranks if distributed)
AtA_rkk, AtX_rkg, n_global = all_reduce_mairal_sufficient_statistics(
*mairal_sufficient_statistics(loadings_rnk, x_ng)
)
A_rkk = exponential_decay_rho * A_rkk + AtA_rkk / n_global
B_rkg = exponential_decay_rho * B_rkg + AtX_rkg / n_global
# update factors_rkg
factors_rkg, factors_history = nmf_compute_factors_fista(
w_rkg=factors_rkg,
A_rkk=A_rkk,
B_rkg=B_rkg,
max_iter=n_iterations,
return_history=return_history,
)
result = {
"factors_rkg": factors_rkg,
"A_rkk": A_rkk,
"B_rkg": B_rkg,
"loadings_rnk": loadings_rnk,
}
if loadings_history is not None:
result["loadings_history"] = loadings_history
if factors_history is not None:
result["factors_history"] = factors_history
return result
def l1_normalize_factors(factors_rkg: torch.Tensor) -> torch.Tensor:
"""
L1-normalize each gene expression program (each row of ``factors_rkg``).
The unconstrained NNLS dictionary update of :func:`online_dictionary_update_fista` leaves the scale of
``factors_rkg`` free (the loadings absorb it), so the caller normalizes after each update to keep it fixed.
"""
return F.normalize(factors_rkg, p=1, dim=-1, eps=1e-8)
def _distributed_world_size() -> int:
"""Number of processes in the default process group, or 1 if not running distributed."""
if torch.distributed.is_available() and torch.distributed.is_initialized():
return torch.distributed.get_world_size()
return 1
def mairal_sufficient_statistics(
loadings_rnk: torch.Tensor,
x_ng: torch.Tensor,
) -> tuple[torch.Tensor, torch.Tensor, int]:
"""
Per-minibatch sums that Mairal's matrices A and B accumulate. These are linear in the cells, so sums computed
on disjoint sets of cells can simply be added together.
Args:
loadings_rnk: The loadings (Mairal's alpha) of the cells in the minibatch.
x_ng: The data for the cells in the minibatch.
Returns:
Tuple of the sum over cells of alpha alpha^T (shape r, k, k), the sum over cells of alpha x^T
(shape r, k, g), and the number of cells.
"""
r, n, _ = loadings_rnk.shape
g = x_ng.shape[1]
alpha_t_rkn = loadings_rnk.transpose(1, 2)
return torch.bmm(alpha_t_rkn, loadings_rnk), torch.bmm(alpha_t_rkn, x_ng.expand(r, n, g)), n
def all_reduce_mairal_sufficient_statistics(
AtA_rkk: torch.Tensor,
AtX_rkg: torch.Tensor,
n: int,
) -> tuple[torch.Tensor, torch.Tensor, int]:
"""
Sum the output of :func:`mairal_sufficient_statistics` across all processes, if running distributed.
This makes the result equivalent to a single minibatch made of the union of every rank's cells.
"""
if _distributed_world_size() == 1:
return AtA_rkk, AtX_rkg, n
n_t = torch.tensor([n], dtype=AtA_rkk.dtype, device=AtA_rkk.device)
packed = torch.cat([AtA_rkk.flatten(), AtX_rkg.flatten(), n_t])
torch.distributed.all_reduce(packed, op=torch.distributed.ReduceOp.SUM)
AtA_size = AtA_rkk.numel()
AtA_rkk = packed[:AtA_size].view_as(AtA_rkk)
AtX_rkg = packed[AtA_size : AtA_size + AtX_rkg.numel()].view_as(AtX_rkg)
return AtA_rkk, AtX_rkg, int(round(packed[-1].item()))
class NMFInit:
@staticmethod
def __call__(x: torch.Tensor, k: int, transformed_data_mean: float | None = None) -> None:
"""Modify the values of x in place as a way to initialize a dictionary factor matrix for NMF."""
pass
class NMFInitSklearnRandom(NMFInit):
@staticmethod
def __call__(x: torch.Tensor, k: int, transformed_data_mean: float | None = None) -> None:
"""Modify the values of x in place according to the sklearn NMF init random recipe."""
# https://github.com/scikit-learn/scikit-learn/blob/
# 99bf3d8e4eed5ba5db19a1869482a238b6223ffd/sklearn/decomposition/_nmf.py#L304-L315
assert transformed_data_mean is not None
factor = np.sqrt(transformed_data_mean / k)
x.normal_(0.0, factor).abs_()
class NMFInitUniformRandom(NMFInit):
@staticmethod
def __call__(x: torch.Tensor, k: int, transformed_data_mean: float | None = None) -> None:
"""Modify the values of x in place according to a Joshua Welch NMF init random recipe."""
# https://www.nature.com/articles/s41587-021-00867-x#Sec10
# algorithm 1 step 2
x.uniform_(0.0, 2.0)
class NonNegativeMatrixFactorization(ABC, CellariumModel):
"""
Abstract base class for non-negative matrix factorization implementations.
An implementation only has to provide the learned factors of each replicate (:attr:`factors_dict`). Given
consensus factors computed from them (see :class:`~cellarium.ml.api.NMFOutput`), the loadings of new cells and the
reconstruction error are the same for every implementation, so they are implemented here.
"""
_alpha_tol = 1e-5
def __init__(self, var_names_g: Sequence[str], k_values: list[int], **kwargs):
super().__init__()
self.var_names_g = np.array(var_names_g)
self.k_values = k_values
@property
@abstractmethod
def factors_dict(self) -> dict[int, torch.Tensor]:
"""
Return the learned factors for each k value.
Returns:
Dictionary mapping k -> factor tensor of shape (r, k, g) where:
- r is number of replicates (could be 1 for some implementations)
- k is number of factors
- g is number of genes
"""
pass
def _training_buffer_names(self) -> list[str]:
"""
The names of the buffers that only training uses (the sufficient statistics of the online algorithm, say), as
opposed to the factors. By default there are none; an implementation that has some returns them, for
:meth:`free_training_state`.
"""
return []
def free_training_state(self) -> None:
"""
Release the buffers that only training uses (see :meth:`_training_buffer_names`), keeping the factors, which
are all that :meth:`infer_loadings` and :meth:`reconstruction_error` and the consensus need. For the online
algorithms this about halves what the model holds in memory and writes to a checkpoint. The model cannot be
trained further afterwards: it raises when training starts. Does nothing for an implementation with no such
buffers.
"""
for name in self._training_buffer_names():
setattr(self, name, None) # None keeps the name of a buffer but leaves it out of the state dict
def _check_training_state_present(self) -> None:
"""For ``on_train_start`` of an implementation: refuse to train a model whose training state was freed."""
if any(getattr(self, name) is None for name in self._training_buffer_names()):
raise RuntimeError(
"The training state of this model was released by free_training_state(): train a new model."
)
def on_load_checkpoint(self, checkpoint: dict[str, Any]) -> None:
# the checkpoint of a model whose training state was freed has no such buffers, so those of the model that was
# just built are dropped as well, for the state dicts to match
state_dict = checkpoint["state_dict"]
for name in self._training_buffer_names():
if not any(key == name or key.endswith(f".{name}") for key in state_dict):
setattr(self, name, None)
@torch.no_grad()
def infer_loadings(
self,
x_ng: torch.Tensor,
var_names_g: np.ndarray,
consensus_factors: dict[int, dict[str, torch.Tensor | float]],
k: int,
normalize: bool = False,
obs_names_n: np.ndarray | None = None,
) -> torch.Tensor:
"""
Infer the loadings of each program for the input count matrix, by non-negative least squares against the
consensus factors. To be run after the model has been trained and consensus factors have been computed.
Args:
x_ng: Gene counts matrix.
var_names_g: The list of the variable names in the input data.
consensus_factors: The consensus factors for each k value are in ``consensus_factors[k]["consensus_D_kg"]``.
k: Number of factors.
normalize: Whether to normalize the loadings of each cell to sum to 1.
obs_names_n: Cell names (not used).
Returns:
Loadings tensor of shape (n, k).
"""
assert_arrays_equal("var_names_g", var_names_g, "self.var_names_g", self.var_names_g)
D_kg = consensus_factors[k]["consensus_D_kg"]
assert isinstance(D_kg, torch.Tensor), "consensus_D_kg must be a tensor"
alpha_nk = (
solve_nnls_fista(
D_kg.to(x_ng.device).unsqueeze(0).transpose(1, 2),
x_ng.t(),
tol=self._alpha_tol * 0.1,
max_iter=1000,
)
.transpose(1, 2)
.squeeze(0)
)
if normalize:
alpha_nk = F.normalize(alpha_nk, p=1, dim=-1)
return alpha_nk
@torch.no_grad()
def reconstruction_error(
self,
x_ng: torch.Tensor,
var_names_g: np.ndarray,
consensus_factors: dict[int, dict[str, torch.Tensor | float]],
) -> dict[int, float]:
"""
Compute the reconstruction error for each k value in ``consensus_factors``, using the consensus factors
``consensus_factors[k]["consensus_D_kg"]``.
Args:
x_ng: Gene counts matrix.
var_names_g: The list of the variable names in the input data.
consensus_factors: The consensus factors for each k value.
Returns:
A dictionary mapping each k value to its reconstruction error.
"""
assert_arrays_equal("var_names_g", var_names_g, "self.var_names_g", self.var_names_g)
rec_error = {}
for k in consensus_factors.keys():
D_kg = consensus_factors[k]["consensus_D_kg"]
assert isinstance(D_kg, torch.Tensor), "consensus_D_kg must be a tensor"
if (D_kg == 0).all():
raise ValueError("D_kg is all zeros, please train the model and compute consensus factors first")
alpha_nk = self.infer_loadings(
x_ng=x_ng,
var_names_g=var_names_g,
consensus_factors=consensus_factors,
k=k,
normalize=False,
).squeeze(0)
rec_error[k] = (
nmf_frobenius_loss(
x_ng=x_ng,
loadings_nk=alpha_nk.to(x_ng.device),
factors_kg=D_kg.to(x_ng.device),
)
.sum()
.item()
)
return rec_error
[docs]
class OnlineNonNegativeMatrixFactorization(NonNegativeMatrixFactorization):
"""
Use the online NMF algorithm of Mairal et al. [1] to factorize the count matrix
into a dictionary of gene expression programs and a matrix of cell program loadings.
**References:**
1. `Online learning for matrix factorization and sparse coding. Mairal, Bach, Ponce, Sapiro. JMLR 2009.`
Args:
var_names_g: The variable names schema for the input data: should be highly variable genes.
k_values: A list of the number of gene expression programs to infer.
r: Number of NMF replicates (for consensus).
solver: The solver for the loadings and dictionary updates, in ["fista", "hals"].
``"fista"`` (FISTA for non-negative least squares) recomputes each minibatch's loadings from scratch, so
memory does not grow with the number of cells, and it supports multi-process training.
``"hals"`` (hierarchical alternating least squares, following nmf-torch) stores the loadings of every
cell (see :attr:`stores_loadings`), requires ``n_cells_total`` and ``obs_names_n``, and does not
support multi-process training.
init: The initialization method to use for the NMF factors, in ["sklearn_random", "uniform_random"].
transformed_data_mean: The mean of the transformed data, used for initialization if an only if
`init` is "sklearn_random".
n_cells_total: The total number of cells in the dataset, used if and only if `solver` is "hals".
"""
def __init__(
self,
var_names_g: Sequence[str],
k_values: list[int],
r: int,
solver: Literal["fista", "hals"] = "fista",
init: Literal["sklearn_random", "uniform_random"] = "uniform_random",
transformed_data_mean: None | float = None,
n_cells_total: int | None = None,
) -> None:
super().__init__(var_names_g=var_names_g, k_values=k_values)
g = len(self.var_names_g)
if solver not in ("fista", "hals"):
raise ValueError(f"Unknown solver: {solver}")
self.solver = solver
self.obs_names_to_index_map: dict[str, int] = {} # used for local latents
if self.stores_loadings and n_cells_total is None:
raise ValueError("n_cells_total must be provided when solver='hals'")
self.r = r
self.transformed_data_mean = transformed_data_mean
self.init = init
if init == "sklearn_random":
if transformed_data_mean is None:
raise ValueError("transformed_data_mean must be provided when using the sklearn_random initialization")
for i in self.k_values:
self.register_buffer(f"A_{i}_rkk", torch.empty(r, i, i))
self.register_buffer(f"B_{i}_rkg", torch.empty(r, i, g))
self.register_buffer(f"D_{i}_rkg", torch.empty(r, i, g))
if self.stores_loadings:
assert isinstance(n_cells_total, int)
self.register_buffer(f"loadings_{i}_rnk", torch.empty(r, n_cells_total, i)) # initialized later
self._dummy_param = torch.nn.Parameter(torch.empty(()))
self._hals_tol = 1e-4
self.reset_parameters()
def reset_parameters(self) -> None:
match self.init:
case "sklearn_random":
init_fn: NMFInit = NMFInitSklearnRandom()
case "uniform_random":
init_fn = NMFInitUniformRandom()
case _:
raise ValueError(f"Unknown initialization method: {self.init}")
for i in self.k_values:
getattr(self, f"A_{i}_rkk").zero_()
getattr(self, f"B_{i}_rkg").zero_()
init_fn(getattr(self, f"D_{i}_rkg"), k=i, transformed_data_mean=self.transformed_data_mean)
if self.stores_loadings:
init_fn(getattr(self, f"loadings_{i}_rnk"), k=i, transformed_data_mean=self.transformed_data_mean)
if self.stores_loadings:
self._prev_err_rk: torch.Tensor | None = None
self._init_err_rk: torch.Tensor | None = None
self._err_running_sum_rk = torch.zeros((self.r, len(self.k_values)), device=self._dummy_param.device)
self._cells_seen_in_epoch = 0 # Track cells seen in current epoch
def _apply(self, fn: Callable[[torch.Tensor], torch.Tensor], recurse: bool = True):
# the running errors of the HALS solver are plain tensors, not buffers: they follow the module when it is moved
module = super()._apply(fn, recurse)
for name in ("_prev_err_rk", "_init_err_rk", "_err_running_sum_rk"):
tensor = getattr(self, name, None)
if tensor is not None:
setattr(self, name, fn(tensor))
return module
@property
def stores_loadings(self) -> bool:
"""
Whether the loadings of every cell are stored across minibatches, as buffers of shape
``(r, n_cells_total, k)``. True for the ``"hals"`` solver, which warm-starts from them; False for ``"fista"``,
which recomputes each minibatch's loadings from scratch.
"""
return self.solver == "hals"
@property
def factors_dict(self) -> dict[int, torch.Tensor]:
"""Return the learned factors for each k value."""
return {k: getattr(self, f"D_{k}_rkg") for k in self.k_values}
def _training_buffer_names(self) -> list[str]:
# the stored loadings of the "hals" solver are left out: they are a result of the run, not scratch
return [name for k in self.k_values for name in (f"A_{k}_rkk", f"B_{k}_rkg")]
[docs]
def online_dictionary_update(self, x_ng: torch.Tensor, k: int, minibatch_indices_n: torch.Tensor | None) -> None:
"""
Algorithm 1 from Mairal et al. [1] for online dictionary learning.
Args:
x_ng: The data.
k: The value of k to run.
minibatch_indices_n: The indices of the cells in the current minibatch.
"""
# get running values
A_rkk = getattr(self, f"A_{k}_rkk")
B_rkg = getattr(self, f"B_{k}_rkg")
factors_rkg = getattr(self, f"D_{k}_rkg")
if self.solver == "fista":
# the loadings of the minibatch are solved from scratch, so nothing per-cell is stored
updated_values = online_dictionary_update_fista(
x_ng=x_ng,
factors_rkg=factors_rkg,
loadings_rnk=torch.zeros(self.r, x_ng.shape[0], k, dtype=factors_rkg.dtype, device=factors_rkg.device),
A_rkk=A_rkk,
B_rkg=B_rkg,
)
updated_factors_rkg = l1_normalize_factors(updated_values["factors_rkg"])
else:
assert isinstance(minibatch_indices_n, torch.Tensor), (
"minibatch_indices_n must be provided for solver='hals'"
)
stored_loadings_rnk = getattr(self, f"loadings_{k}_rnk")
loadings_rnk = stored_loadings_rnk[:, minibatch_indices_n, :] # a copy, which hals updates in place
# run nmf-torch hals online update
updated_values = online_dictionary_update_nmf_torch_hals(
x_ng=x_ng,
factors_rkg=factors_rkg,
loadings_rnk=loadings_rnk,
A_rkk=A_rkk,
B_rkg=B_rkg,
)
updated_factors_rkg = updated_values["factors_rkg"]
# store the updated loadings of the minibatch cells, to warm-start the next time these cells are seen
stored_loadings_rnk[:, minibatch_indices_n, :] = loadings_rnk
# update running values
setattr(self, f"A_{k}_rkk", updated_values["A_rkk"])
setattr(self, f"B_{k}_rkg", updated_values["B_rkg"])
setattr(self, f"D_{k}_rkg", updated_factors_rkg)
[docs]
def forward(
self,
x_ng: torch.Tensor,
var_names_g: np.ndarray,
obs_names_n: np.ndarray | None = None,
) -> dict[str, torch.Tensor | None]:
"""
Args:
x_ng: Gene counts matrix.
var_names_g: The list of the variable names in the input data.
obs_names_n: The names of the cells in the current minibatch (used when there are local latents).
Returns:
An empty dictionary.
"""
assert_columns_and_array_lengths_equal("x_ng", x_ng, "var_names_g", var_names_g)
assert_arrays_equal("var_names_g", var_names_g, "self.var_names_g", self.var_names_g)
if self.stores_loadings and _distributed_world_size() > 1:
# the per-cell loadings are rank-local buffers, which DDP would overwrite with rank 0's values
raise NotImplementedError("solver='hals' does not support multi-process training.")
# handle the mapping of obs_names to indices for local latents
minibatch_indices_n: torch.Tensor | None = None
if self.stores_loadings:
assert obs_names_n is not None, "obs_names_n must be provided for solver='hals'"
new_obs_names = set(obs_names_n.tolist()) - set(self.obs_names_to_index_map.keys())
if len(new_obs_names) > 0:
self.obs_names_to_index_map |= {
name: i for i, name in enumerate(new_obs_names, start=len(self.obs_names_to_index_map))
}
vectorized_lookup = np.vectorize(lambda x: self.obs_names_to_index_map[x])
minibatch_indices_n = torch.from_numpy(vectorized_lookup(obs_names_n)).to(x_ng.device)
if self.stores_loadings:
# for error computation to assess convergence
if self._init_err_rk is None:
assert isinstance(minibatch_indices_n, torch.Tensor)
self._loss(x_ng=x_ng, minibatch_indices_n=minibatch_indices_n)
# Take sqrt and normalize by number of cells in this batch
self._init_err_rk = self._err_running_sum_rk.clone() / x_ng.shape[0]
assert isinstance(self._init_err_rk, torch.Tensor)
self._prev_err_rk = self._init_err_rk.clone()
self._err_running_sum_rk.zero_() # Reset after initialization
self._cells_seen_in_epoch = 0 # Reset counter
for k in self.k_values:
self.online_dictionary_update(x_ng=x_ng, k=k, minibatch_indices_n=minibatch_indices_n)
if self.stores_loadings:
# for error computation to assess convergence
assert isinstance(minibatch_indices_n, torch.Tensor)
self._loss(x_ng=x_ng, minibatch_indices_n=minibatch_indices_n)
return {}
# @torch.compile()
@torch.no_grad()
def _loss(self, x_ng: torch.Tensor, minibatch_indices_n: torch.Tensor) -> None:
"""
Simple and efficient NMF reconstruction loss computation.
Computes ||X - WH||_F^2 for the current batch.
"""
x_squared_sum = compute_x_squared_sum(x_ng)
for i, k in enumerate(self.k_values):
factors_rkg = getattr(self, f"D_{k}_rkg") # (r, k, g)
loadings_rnk = getattr(self, f"loadings_{k}_rnk")[:, minibatch_indices_n, :] # (r, batch_size, k)
squared_error_r = frobenius_loss_trace_compiled(
x_ng=x_ng,
h_rnk=loadings_rnk,
w_rkg=factors_rkg,
x_squared_sum=x_squared_sum,
) # (r,)
# Accumulate the squared error
self._err_running_sum_rk[:, i] += squared_error_r
# Track cells seen in this epoch
self._cells_seen_in_epoch += x_ng.shape[0]
def on_train_start(self, trainer: pl.Trainer) -> None:
self._check_training_state_present()
if trainer.world_size > 1:
assert isinstance(trainer.strategy, DDPStrategy), (
"OnlineNonNegativeMatrixFactorization requires that the trainer uses the DDP strategy."
)
assert trainer.strategy._ddp_kwargs["broadcast_buffers"] is True, (
"OnlineNonNegativeMatrixFactorization requires that the `broadcast_buffers` parameter of "
"lightning.pytorch.strategies.DDPStrategy is set to True"
)
def on_train_epoch_end(self, trainer: pl.Trainer) -> None:
# convergence criterion check
if self.stores_loadings:
cur_err_rk = self._err_running_sum_rk / self._cells_seen_in_epoch
assert isinstance(self._prev_err_rk, torch.Tensor)
assert isinstance(self._init_err_rk, torch.Tensor)
current_overall_err_rk = torch.abs((self._prev_err_rk - cur_err_rk) / self._init_err_rk)
if current_overall_err_rk.max() < self._hals_tol:
trainer.should_stop = True
print(f"Stopping early: converged, loss={cur_err_rk}")
self._prev_err_rk = cur_err_rk.clone()
self._err_running_sum_rk.zero_()
self._cells_seen_in_epoch = 0 # Reset for next epoch
# this hard reset to zero is equivalent to forgetting momentum each epoch
for i in self.k_values:
getattr(self, f"A_{i}_rkk").zero_()
getattr(self, f"B_{i}_rkg").zero_()
def on_end(self, trainer: pl.Trainer) -> None:
trainer.save_checkpoint(trainer.default_root_dir + "/NMF.ckpt")