Source-linked AI summary
Generalized Canonical Polyadic Tensor Decomposition
David Hong, Tamara G. Kolda, Jed A. Duersch
TL;DR
The paper addresses the limitation of squared-error CP decomposition for data that are nonnegative, discrete, or boolean. It develops GCP with generic losses, generalized gradients, and missing-data handling, then demonstrates flexible tensor factorization across real-world settings.
Problem
Squared-error CP implicitly assumes normally distributed data, although many datasets are nonnegative, discrete, or boolean.
Method
GCP fits a low-rank CP model with generic elementwise losses, direct optimization, generalized gradients, and observed-entry handling for missing data.
Results
Bernoulli-odds and Bernoulli-logit consistently outperform the Gaussian approach for predicting rare ones in the social-network experiment.
Takeaways & Limitations
GCP provides flexibility to select loss functions for different data types while efficiently managing missing data and supporting standard tensor computational kernels.
Takeaways & Limitations
Logit-link components can be difficult to interpret because signed factors may increase probability for some entries while reducing it for others.
Abstract
from arXiv · showhide
Tensor decomposition is a fundamental unsupervised machine learning method in data science, with applications including network analysis and sensor data processing. This work develops a generalized canonical polyadic (GCP) low-rank tensor decomposition that allows other loss functions besides squared error. For instance, we can use logistic loss or Kullback-Leibler divergence, enabling tensor decomposition for binary or count data. We present a variety statistically-motivated loss functions for various scenarios. We provide a generalized framework for computing gradients and handling missing data that enables the use of standard optimization methods for fitting the model. We demonstrate the flexibility of GCP on several real-world examples including interactions in a social network, neural activity in a mouse, and monthly rainfall measurements in India.
1. Introduction.
GCP generalizes CP tensor decomposition by replacing squared error with generic elementwise losses suited to different data types. The framework also provides gradients, missing-data handling, and standard optimization for practical fitting.
- Motivation and framework: GCP approximates a data tensor with a low-rank CP model while measuring fit using a generic elementwise loss function.The model tensor has CP structure, and standard CP uses squared error as its loss.
- Motivation and framework: Squared error implicitly assumes normally distributed data, whereas many datasets are nonnegative, discrete, or boolean.
- Contributions: The framework supports loss functions adapted to data nature, including a binary-tensor loss for entries in {0, 1}.It is designed to let analysts choose losses appropriate to the observed data.
- Contributions: GCP derives gradients using the same computational kernels as standard CP and handles incomplete tensors by summing over observed entries.The framework supports standard optimization methods and missing-data fitting.
- Applications: The paper demonstrates GCP across real-world examples involving different data types, including missing-entry inference and unsupervised pattern extraction.
2. Background and notation.
The paper represents tensors through modes, indices, observed-entry sets, and low-rank CP structure. A Kruskal tensor uses shared component counts across factor matrices, making the model more parsimonious than the full tensor.
- Tensor notation: A tensor is a real-valued d-way array whose modes have sizes n1 × n2 × · · · × nd.The paper distinguishes tensors, matrices, vectors, and scalars in its notation.
- Indices and missing data: Tensor entries use the multiindex i = (i1, i2, . . . , id), while I denotes the set of all possible indices.
- Indices and missing data: The observed-entry set Ω contains measured entries, while I \ Ω contains entries missing because of measurement problems.
- CP structure: A CP-structured model uses d factor matrices with r columns, where each component is the outer product of corresponding factor columns.The same component count r appears in every factor matrix.
- CP structure: When r is relatively small, the CP model is low-rank and more parsimonious than directly specifying all nd tensor entries.
- Connection to GCP: The difference between GCP and standard CP is the flexibility to choose loss functions, motivated through statistical likelihoods.
3. Choice of loss function.
GCP derives elementwise loss functions from statistical assumptions about how tensor entries are generated, while allowing alternative links and heuristic losses. These choices determine data-domain constraints and the interpretation of the resulting factors.
- Statistical loss construction: The negative log-likelihood framework converts a distribution, link function, and observed entry into an elementwise loss f(x, m).The model seeks a maximum-likelihood estimate over the low-rank tensor, then minimizes the summed negative log-likelihood.
- Choosing a loss: The framework also permits heuristic choices such as Huber and β-divergence losses, so users generally compare several losses and model ranks when the data-generating process is uncertain.The paper notes that non-statistical losses may be useful and that the listed choices are not comprehensive.
- Gaussian loss: Squared error corresponds to Gaussian data with an identity link and is appropriate for real-valued observations under that assumption.The resulting loss is f(x, m) = (x −m)^2 for x, m ∈R.
- Bernoulli losses: For binary data, Bernoulli modeling supports identity, odds, and logit links, producing different constraints and interpretations for the model tensor.The odds link requires m ≥0 and can be enforced through nonnegative factors, whereas the logit link permits unconstrained real-valued m.
- Bernoulli losses: The odds formulation makes each nonnegative component increase the probability of a 1, while the unconstrained logit formulation may yield components that counteract one another.The paper identifies interpretability as a trade-off between the two link choices.
- Nonnegative continuous data: Gamma and Rayleigh distributions provide statistically motivated losses for nonnegative continuous data, with Gamma requiring strictly positive observations in its stated formulation.The Gamma-derived loss uses positivity constraints and is numerically adjusted in practice by replacing m with m + ϵ.
4. GCP decomposition.
GCP fits a low-rank CP model by minimizing a generic elementwise loss over observed tensor entries. Its gradient reduces to standard MTTKRP computations, supporting missing data, constraints, regularization, and off-the-shelf first-order optimization.
- Objective and optimization: The GCP objective minimizes the mean elementwise loss over known indices while constraining the model tensor to have CP structure.Only entries in Ω contribute to the objective, and the factor matrices determine M.
- Objective and optimization: GCP uses direct all-at-once optimization rather than alternating least squares because its subproblems do not have closed-form solutions.The mean scaling also facilitates comparisons across tensors with different sizes or amounts of missing data.
- Extensions: GCP supports factor constraints and L2 regularization, with regularization especially useful when extensive missing data leaves some factor elements weakly constrained.Regularization parameters can be selected by cross-validation using held-out entries.
- GCP gradient: Theorem 3 expresses each factor-matrix gradient through a matricized tensor times Khatri-Rao product, allowing existing optimized tensor kernels to be reused.The result generalizes gradients for standard CP, missing-data CP, and Poisson tensor factorization.
- GCP gradient: The gradient separates model structure from data and loss through Z_k and an elementwise derivative tensor Y, which is zero at missing entries.The sparsity pattern of Y is determined by the observed-index set Ω.
- Implementation: Algorithm 1 computes observed model values, the elementwise derivative tensor, and a full sequence of MTTKRPs to return the loss and factor gradients.For sparse observations, model entries can be computed only at known locations rather than forming the full model tensor.
- Sparse or scarce tensors: Scarcity can induce sparsity in gradient calculations, motivating data subsampling or stochastic gradient descent for large-scale tensors.The paper cautions that subsampling must preserve enough nonzero entries when the tensor itself is sparse.
5. Experimental results.
Experiments show that GCP produces interpretable, loss-function-specific factors across social-network, mouse-neural-activity, and Indian-rainfall data. These examples also demonstrate applications to prediction, regression, missing data, and unsupervised pattern discovery.
- Social network: GCP factors reveal distinct social-network structure under different loss functions, including temporal locality, correlated sender–receiver groups, and activity concentrated on active days.Bernoulli-odds factors show stronger temporal locality and sender–receiver correlations, while Bernoulli-logit factors emphasize the abundance of zero interactions.
- Social network: Bernoulli-odds and Bernoulli-logit consistently outperform standard CP for held-out binary prediction, although predicting rare ones remains difficult.The experiment repeats 200 times, holding out 50 ones and 50 zeros per trial; differences are negligible for zeros but larger for ones.
- Mouse neural activity: For mouse neural activity, standard CP and β-divergence factors correlate with reward and turn conditions, while β-divergence yields nonnegative and arguably easier-to-interpret factors.β-divergence assigns clearer identities to example neurons, including neuron 176 for reward and neuron 273 for no reward, though some components remain unexplained.
- Mouse neural activity: Only the Gamma loss failed to achieve perfect turn classification in the illustrative regression comparison, while reward prediction was harder.The authors caution that changing ranks and other parameters might alter the relative performance of the methods.
- Rainfall in India: For Indian rainfall, Gaussian loss highlights July–September and a few dominant regions, whereas Gamma loss captures the monsoon mainly in its first two components without region dominance.The rainfall tensor covers 36 regions, 12 months, and 115 years, with 0.72% missing data handled explicitly.
- Cross-application findings: Across these applications, GCP demonstrates flexibility for explanatory factor visualization, prediction, regression, missing-entry inference, and unsupervised pattern discovery.The framework is implemented with L-BFGS-B and applied to social-network, neural-activity, and rainfall examples.
6. Conclusions and future work.
GCP provides flexible loss-function choices and explicitly handles missing data, while retaining efficient gradient computation through MTTKRP. The framework also identifies extensions for heterogeneous losses, scarcity, and functional tensor decomposition.
- GCP does not claim one loss function is universally better; it instead offers choices suited to an analyst’s data and goals.
- Missing data is handled explicitly, with weights that can be generalized from binary indicators to nonnegative confidence-based values.
- The gradient retains MTTKRP structure, enabling efficient implementations of a dominant tensor-computation kernel.
- The discussion assumes one loss function for every tensor entry, although entry-specific losses could support heterogeneous data types.
- Future work includes exploiting sparsity for larger tensors and extending GCP to functional tensor decomposition.
Appendix A. Kruskal tensors with explicit weights.
The appendix extends Kruskal-tensor notation and gradient results to models with explicit component weights. It gives vectorized representations and states the corresponding derivative framework.
- Explicit weights represent the model as M = Jλ; A1, A2, . . . , AdK and vectorize it as m = Zλ.
- The Khatri-Rao product Z is defined by combining the factor matrices in reverse mode order.
- Theorem 3 extends directly to explicit-weight models, yielding partial derivatives with respect to both factor matrices and λ.
- The derivative notation uses Y(k), y, Zk, and Z for tensor unfoldings, vectorization, and Khatri-Rao constructions.
Appendix B. Special structure of standard CP gradient.
For standard CP with squared-error loss, the gradient separates into terms that exploit sparse input tensors and efficiently computed factor structure. The appendix also explains conversion between tensor-factor variables and vector-valued optimization variables.
- The gradient’s first term is an MTTKRP with the original tensor, allowing sparse computation that avoids explicitly forming Zk.
- The second term also avoids explicitly forming Zk because its Gram matrix can be computed through Hadamard products.
- The kt2vec operator converts factor matrices into one vector so first-order optimization methods can operate on the model variables.
Appendix C. GCP optimization.
GCP factor matrices are rearranged into vectors so standard first-order optimization routines can evaluate the objective and gradient. The appendix supplies a wrapper implementing this conversion.
- The kt2vec representation stacks the vectorized factor matrices into one optimization vector.
- The inverse vec2kt operation reconstructs the set of factor matrices without changing the number of variables.
- Algorithm 2 wraps GCP evaluation by converting the input vector to factor matrices, computing the objective and factor gradients, then vectorizing the gradients.