Probabilistic Block Term Decomposition for the Modelling of Higher-Order Arrays

arXiv:2310.02694 · stat.ML, cs.LG, stat.AP · Submitted 2023-10-04 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Probabilistic Block Term Decomposition for the Modeling of Higher-Order Arrays".

Jane: The paper was written by Jesper Løve Hinrich and Morten Mørup from University of Copenhagen and Technical University of Denmark.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Title: Tom: Welcome back to the show, everyone. Today we’re looking at a paper that’s got a mouthful of a title: “Probabilistic Block Term Decomposition for the Modeling of Higher-Order Arrays.” Jane, I’m going to need you to unpack that for me, because that is a dense string of words.

Jane: Happy to, Tom. So “higher-order arrays” just means data that lives in more than two dimensions. Think of a spreadsheet as a two-dimensional array, rows and columns. Now imagine stacking a bunch of spreadsheets on top of each other, and you’ve got a three-dimensional array, or a tensor. That’s what they’re talking about.

Tom: And “block term decomposition” is the way they break that data apart?

Jane: Exactly. It’s a way of finding structure inside that big block of numbers. There are two classic ways to do this. One is the CP decomposition, which breaks the data into simple rank-one pieces, like individual building blocks. The other is the Tucker model, which is more flexible and lets all the pieces interact. The block term decomposition is the middle ground, a mix of both.

Tom: So it’s like the Goldilocks option for tensor math. And the “probabilistic” part, that’s the twist here, right?

Jane: That’s the big one. Instead of just giving you a single answer, a single decomposition, probabilistic methods give you a distribution of possible answers. So you get the most likely answer, but you also get a sense of how uncertain you should be about it. That’s huge for real-world data, because data is always noisy.

Tom: And the authors, Jesper Løve Hinrich and Morten Mørup, they’re from Denmark, right? Technical University of Denmark and University of Copenhagen. They’ve been working in this space for a while.

Jane: They have. And what they’ve done here is take this block term decomposition and give it the full Bayesian treatment. They’re not just finding the best fit, they’re quantifying the uncertainty in every single component. That’s a big step forward for anyone who uses tensor methods on messy, real-world data.

Tom: I love it when math gets practical. So who should care about this? Who’s going to feel this?

Jane: Anyone working with multi-way data, which is everywhere. Chemists measuring samples across wavelengths and time, neuroscientists looking at brain signals across channels and time and frequency, even social scientists with survey data. If your data has more than two dimensions, this paper is relevant to you.

Tom: And the promise is you get better answers, with a built-in error bar. That’s a good deal.

Jane: It is. And the paper goes on to show exactly how they do it and how well it works. We’ll get into the details next.

Tom: Great, so stick around, because we’re about to dig into the actual method and the results.

Summary: Tom: So we’re back, still talking about “Probabilistic Block Term Decomposition for the Modeling of Higher-Order Arrays.” Jane, we’ve set the stage. Now what did these authors actually do?

Jane: They built a fully Bayesian version of the block term decomposition. That means they set up a generative model, they put priors on all the parameters, and then they use variational inference to approximate the posterior distribution. It’s a complete probabilistic treatment, not just a point estimate with some error bars slapped on.

Tom: And they made a specific choice about the factors, right? They used something called the von Mises-Fisher distribution.

Jane: Right. That’s a way of enforcing orthogonality on the factor matrices. In the classic block term decomposition, the factors are orthogonal, meaning they’re independent and don’t overlap. The authors wanted to keep that property in the probabilistic version, because it’s important for the interpretability and the uniqueness of the decomposition. So they used this distribution that lives on the Stiefel manifold, which is the set of all orthogonal matrices.

Tom: So they’re keeping the structure that makes the classic method work, but adding the uncertainty quantification on top.

Jane: Precisely. And they also use automatic relevance determination, which is a fancy way of saying the model can prune away parts of the core that aren’t needed. It learns which components are important and shrinks the others down to zero. That’s their built-in model selection mechanism.

Tom: That sounds like it solves a big problem. Usually you have to guess how many components to use, right?

Jane: You do, and it’s a pain. You fit the model with different numbers of components and compare them, which is computationally expensive. With this approach, you can start with a bigger model and let the algorithm figure out which parts to keep. That’s a huge practical advantage.

Tom: And they tested it. What did they find?

Jane: They ran synthetic experiments where they knew the true structure. They found that the probabilistic version was much more robust to noise than the standard maximum likelihood methods. When they gave it the wrong model order, it still performed well because it could prune away the extra components. The standard methods, on the other hand, would overfit the noise and give worse results.

Tom: So the probabilistic version is more forgiving when you don’t know the exact structure ahead of time.

Jane: Exactly. And they also showed it could identify the correct structure using the evidence lower bound, which is the model evidence approximation. It’s a principled way to compare different model orders.

Tom: So it’s not just a theoretical exercise, they actually demonstrated it works.

Jane: They did, on synthetic data and on two real datasets. We’ll talk about those real-world results in a bit, but the short version is that the method works and it’s computationally competitive with the standard approaches.

Tom: Sounds like a win. Let’s dig into the details of how they set up the model.

Jane: Good, because that’s where the cleverness really is.

Improvements: Tom: We’re back with “Probabilistic Block Term Decomposition for the Modeling of Higher-Order Arrays.” Jane, we’ve covered the basics. What’s the actual improvement here over what came before?

Jane: The key improvement is that they’re the first to do a general Bayesian block term decomposition with orthogonal factors. There was a previous attempt by another group, but they only handled a special case, the so-called (Lr, Lr, one) blocks, and they used normal distributions for the factors, which doesn’t enforce orthogonality. That’s a big difference.

Tom: So the previous work was limited and didn’t match the classic method’s structure. This paper fixes both issues.

Jane: Exactly. By using the von Mises-Fisher distribution, they get orthogonality baked into the prior. That means the probabilistic model respects the same geometry as the classic block term decomposition. It’s not just a probabilistic version in name; it’s a proper probabilistic version of the actual method.

Tom: And they also handle the full range of models, from CP to Tucker and everything in between, all in one framework.

Jane: That’s the elegant part. The block term decomposition is a generalization that includes both. If you set the number of blocks to one, you get Tucker. If you set each block to be rank-one, you get CP. So their framework is a unified treatment of all three models. You can fit one model and compare all the intermediate structures.

Tom: That’s a nice way to think about it. Instead of having separate tools for each model, you have one tool that can explore the whole space.

Jane: Right. And they also improved the computational efficiency. Because of the orthogonality, the updates for the core elements become independent, which means you can compute them in parallel and it’s much faster. They mention it’s about one and a half to two times slower than the fastest maximum likelihood method, but ten to fifteen times faster than the other standard method. That’s a very reasonable trade-off for getting uncertainty quantification.

Tom: So you get more information, and it’s still fast enough to be practical.

Jane: Exactly. And they also showed that the automatic relevance determination, the pruning mechanism, helps with model misspecification. If you don’t know the right number of blocks or the right size, the model can adapt and still give you a good answer.

Tom: So it’s more forgiving for people who don’t have perfect knowledge of their data.

Jane: That’s the whole point. Real data is messy, and you rarely know the exact structure ahead of time. This method gives you a principled way to handle that uncertainty.

Tom: I’m curious about the real-world applications. What did they test it on?

Jane: They used a flow injection dataset from chemistry and an EEG dataset from neuroscience. We’ll get into those next, but the short version is that the method worked well on both, and it highlighted some interesting trade-offs between interpretability and model fit.

Tom: Let’s hear about those results then.

Jane: Good, because that’s where the rubber meets the road.

First Page: Tom: We’re still on “Probabilistic Block Term Decomposition for the Modeling of Higher-Order Arrays.” Jane, we’ve talked about the method. Let’s look at the first page and what they set out to do.

Jane: The first page sets up the problem nicely. They talk about how tensors show up everywhere, from psychology to chemometrics to biology. And they point out that the two dominant models, CP and Tucker, have different strengths. CP is unique and easy to interpret, but it’s rigid. Tucker is flexible, but it has rotational ambiguity, meaning you can get different answers that fit equally well.

Tom: So you have to choose between interpretability and flexibility.

Jane: Right, and the block term decomposition is the middle ground. It’s a sum of smaller Tucker models, so you get some flexibility but also some structure that helps with uniqueness. The paper argues that this is a natural framework that interpolates between the two extremes.

Tom: And the Bayesian approach is the solution to the limitations of maximum likelihood, right?

Jane: Exactly. The first page lays out that maximum likelihood gives you a point estimate, but it doesn’t tell you about uncertainty. Bayesian inference gives you a distribution over the parameters, which lets you quantify uncertainty and regularize the solution. The paper argues that this adds robustness to noise and helps with model selection.

Tom: And they also mention that previous Bayesian work focused on binary or count data, but this paper is applying it more broadly.

Jane: Right. There’s been a rise in Bayesian tensor methods, but they often focus on specific data types. This paper is part of a broader trend of applying Bayesian inference to continuous data with Gaussian noise, which is the most common setting in practice.

Tom: So the first page is really setting the stage for why this is needed.

Jane: It is. It’s a well-structured introduction that motivates the problem and positions the contribution. They’re not just saying “here’s a new method,” they’re saying “here’s a gap in the literature and here’s how we fill it.”

Tom: And the gap is that no one had done a fully Bayesian block term decomposition with orthogonal factors.

Jane: Precisely. That’s the novel contribution. And the rest of the paper is about showing that it works and that it’s useful.

Tom: I remember they also mentioned the ELBO, the evidence lower bound, as a way to compare models. That’s a key tool for model selection.

Jane: Yes, that’s their principled way of choosing between different structures. It’s not perfect, but it’s a lot better than just eyeballing the reconstruction error.

Tom: So the first page really sets up the whole story. What did they find when they applied it to real data?

Jane: We’re about to get there, but let me just say the results were interesting, especially the tension between model fit and interpretability. The full Tucker model fit best according to the ELBO, but the CP model was easier to interpret. That’s a classic trade-off.

Tom: That’s a great segue into the real data results. Let’s hear about those.

Jane: Good, because that’s where the method really gets tested.

Conclusion: Tom: We’ve reached the end of our discussion on “Probabilistic Block Term Decomposition for the Modeling of Higher-Order Arrays.” Jane, let’s wrap this up. What’s the big takeaway for our listeners?

Jane: The big takeaway is that this paper gives us a unified, fully Bayesian framework for tensor decomposition. It covers CP, Tucker, and everything in between through the block term decomposition. And it does it with orthogonal factors, which is the right structure for interpretability, and with automatic relevance determination for pruning.

Tom: And it’s computationally practical, right? Not just a theoretical exercise.

Jane: Exactly. It’s about one and a half to two times slower than the fastest maximum likelihood method, but it gives you uncertainty quantification and robustness to noise. That’s a great trade-off. And it’s much faster than the other standard method.

Tom: And they showed it works on real data, both chemistry and neuroscience.

Jane: They did. On the flow injection data and the EEG data, the method found good solutions. Interestingly, the full Tucker model had the highest evidence lower bound, meaning it fit best, but the CP model was easier to interpret. That’s a classic tension in tensor modeling, and this paper gives you the tools to explore it.

Tom: So for someone working with multi-way data, this is a valuable addition to their toolbox.

Jane: Absolutely. It gives you a principled way to handle uncertainty, to select model order, and to avoid overfitting. And it’s all in one framework, so you can compare different structures fairly.

Tom: Lu, Meng, Lalam, any final thoughts before we move on?

Lu: I think the most exciting part is the potential for this to be extended to other types of data, like count data or binary data. The framework is general enough that it could be adapted.

Meng: And from a practical standpoint, the fact that it’s computationally feasible is huge. That means it can be used on real problems, not just toy examples.

Lalam: The cultural impact here is that it democratizes advanced tensor analysis. Researchers in fields like psychology or biology, who might not be experts in Bayesian methods, can now use these tools to get better answers from their data.

Tom: Well said, everyone. That’s a wrap on “Probabilistic Block Term Decomposition for the Modeling of Higher-Order Arrays.” Thanks for listening, and we’ll see you on the next one.

Jane: Bye, everyone.

Jesper Løve Hinrich, Morten Mørup

University of Copenhagen · Technical University of Denmark

stat.ML, cs.LG, stat.AP

Submitted: 2023-10-04

Updated: 2026-08-10

Comments: 11 pages, preprint of submitted article

Journal ref: Computing in Science & Engineering ( Volume: 26, Issue: 4, Oct.-Dec. 2024)

DOI: 10.1109/MCSE.2024.3398054

License: http://creativecommons.org/publicdomain/zero/1.0/

Importance score: 37/100

The gist: The paper proposes a probabilistic Block-Term Decomposition (pBTD) framework for tensor factorization, unifying the Canonical Polyadic Decomposition (CPD) and Tucker models as special cases.

Key concepts

Higher-Order Arrays (Tensors): These are datasets that live in more than two dimensions. While a spreadsheet is a two-dimensional array, a three-dimensional array is like stacking multiple spreadsheets on top of each other. This structure allows researchers to model complex data across multiple variables.
Block Term Decomposition: This method of finding structure within large blocks of numbers is the middle ground between simple rank-one pieces (CP decomposition) and highly flexible models (Tucker model). It provides a unified framework that interpolates between these two extremes.
Bayesian Inference: Instead of providing a single best answer, probabilistic methods provide a distribution of possible answers. This allows researchers to quantify how uncertain they are about the results, which is crucial when dealing with noisy real-world data.
Orthogonal Factors: This refers to keeping the factors in a specific mathematical structure that ensures they are independent and do not overlap. By using the von Mises-Fisher distribution, this property is enforced within the probabilistic model, maintaining interpretability.

Terminology

Core — 72× in this paper · explained in 2 episodes
Bayesian Inference — 26× in this paper · explained in 5 episodes
Pruning — 11× in this paper · explained in 4 episodes
Sparsity — 10× in this paper · explained in 4 episodes
Robustness — 8× in this paper · explained in 5 episodes
Block-Term Decomposition — 7× in this paper
Reconstruction Error — 7× in this paper · explained in 2 episodes
Interpretability — 6× in this paper · explained in 15 episodes
Canonical Polyadic Decomposition — 5× in this paper
Bayesian Framework — 3× in this paper · explained in 3 episodes
Generative Model — 3× in this paper · explained in 2 episodes
Stiefel manifold — 3× in this paper · explained in 2 episodes
Uncertainty Quantification — 3× in this paper · explained in 8 episodes
Regularization — 2× in this paper · explained in 3 episodes
Signal-to-Noise Ratios — 2× in this paper
Tucker Decomposition — 2× in this paper · explained in 2 episodes
Decoupling — 1× in this paper · explained in 2 episodes
Degeneracy — 1× in this paper · explained in 3 episodes
Generalization — 1× in this paper · explained in 13 episodes
Markov Chain Monte Carlo — 1× in this paper
Trace — 1× in this paper · explained in 2 episodes
Wavelet Transform — 1× in this paper · explained in 2 episodes

Summary

The paper proposes a probabilistic Block-Term Decomposition (pBTD) framework for tensor factorization, unifying the Canonical Polyadic Decomposition (CPD) and Tucker models as special cases. The authors state: We propose, an efficient variational Bayesian probabilistic BTD, which uses the von-Mises Fisher matrix distribution to impose orthogonality in the multi-linear Tucker parts forming the BTD.

The paper begins by noting that Tensors are ubiquitous in science and engineering and tensor factorization approaches have become important tools for the characterization of higher order structure. It explains that "Factorizations includes the outer-product rank Canonical Polyadic Decomposition (CPD) as well as the multi-linear rank Tucker decomposition in which the Block-Term Decomposition (BTD) is a structured intermediate interpolating between these two representations. The authors highlight that Whereas CPD, Tucker, and BTD have traditionally relied on maximum-likelihood estimation, Bayesian inference has been use to form probabilistic CPD and Tucker."

The generative model for the pBTD is specified as follows: the noise precision follows a Gamma distribution, the factor matrices follow a von Mises-Fisher matrix distribution (with a uniform prior on the Stiefel manifold, i.e., F0 = 0), the core arrays follow normal distributions with zero mean and precision matrices, and the data likelihood is normal. The parameters include the noise precision, the factor matrices, the core arrays, and the penalization prior on the cores.

For variational inference, the authors impose a mean-field approximation with factorized Q-distributions. The update rules are derived for each parameter: the factor matrices follow a von Mises-Fisher distribution with concentration matrix given by equation (17), the core arrays follow normal distributions with mean and covariance given by equations (19)-(20), the precision parameters follow Gamma distributions with shape and rate parameters given by equations (21)-(26), and the noise precision follows a Gamma distribution with parameters given by equations (27)-(28).

The paper considers three types of core priors: scale, sparsity, and automatic relevance determination (ARD), noting The sparsity prior has a precision on each element of the BTD cores and the ARD prior has precision ψt = [ψt,1, ψt,2,..., ψt,Dt(n)] thus Dt(n) elements for each core t. The implementation supports the scale and sparsity prior, but the paper presently only consider the sparsity prior.

In the synthetic studies, the authors generated data according to a BTD(4,3) model with varying signal-to-noise ratios from-20dB to 30dB. They compared the proposed pBTD against two maximum likelihood estimation methods from the Tensorlab Toolbox (BTD-NLS and BTD-minf). The results show that for the correct model order all methods have similar performance but for high noise levels, pBTD learns to turn off the modelling - whereas the MLE approaches overfit noise in the data and has high loss on the noiseless data. For the incorrect model order, the pBTD model is preferred as it achieves a lower error. The authors note that BTD-minf model is the fastest model with pBTD being 1.5x to 2x times slower and BTD-NLS is by far the slowest being 20-30x slower than BTD-minf and The proposed pBTD method achieves better results than both MLE methods and is 10-15x times faster than BTD-NLS.

The paper also assesses whether the pBTD can determine the correct BTD structure of a dataset. The authors simulated ground truth models for each of six BTD configurations and fit all six models to each. They found that the pBTD model is able to identify the correct BTD structure via ELBO and this structure also achieves the best reconstruction error in most cases, with the exception of BTD-(4,3) where the models with fewer but larger cores obtain higher ELBO and lower error. They note that the pruning ability based on the sparse core prior is able to get a good performance out of an over-specified model.

For the real data experiments, the authors applied the pBTD to two datasets. The Flow Injection dataset (X ∈ R12×100×89) from industrial injection molding showed support for the Tucker model but also observe that the inferred Tucker core has many elements close to zero which we attribute to the pruning of the automatic relevance determination imposed on each core element. The EEG dataset of inter-trial phase coherence (X ∈ R28×64×4392) also showed highest support for the full Tucker model indicating a preference for a full multilinear representation of the data. However, the authors note that the CPD provides more easily interpretable representations with notably the first and eleventh component well discriminating between left and right hand stimulation.

In the conclusion, the authors state: "We presented the probabilistic Block Term Decomposition (pBTD) and highlighted how variational Bayesian inference can be used in the context of tensor factorization using the BTD also naturally encompassing the two perhaps most prominent tensor factorization models CPD and Tucker as special cases. They emphasize that the Bayesian inference further admits automatic relevance determination enabling the pruning of core elements by learning their length scales as well as model assessment through the associated evidence lower bound (ELBO) and we found that this enabled successful identification of model structures imposed in the synthetically generated data."

The authors note that from an interpretation point of view the full Tucker model representation as well as the intermediate BTD representation are harder to interpret when compared to the CPD due to component interactions within blocks. They conclude that "the presented pBTD exemplifies the utility of Bayesian inference in the context of tensor decomposition highlighting how conventional tensor decomposition approaches, i.e., the BTD as presently considered, can be expanded to probabilistic modeling explicitly accounting for orthogonality with computational complexity similar to conventional BTD estimation."

Improvements for AI systems

Based on the paper, I can improve AI systems in the following specific ways:

Improvement: Implement a variational Bayesian inference system that generalizes across CPD, Tucker, and BTD models within a single framework, using von Mises-Fisher matrix distributions for orthogonal factor constraints.
Capability: The system can automatically select between CPD, Tucker, or intermediate BTD structures based on the evidence lower bound (ELBO), eliminating the need for manual model selection.
Improvement: Integrate sparsity-inducing priors on core array elements with Gamma-distributed precision parameters, enabling automatic pruning of irrelevant components during inference.
Capability: The system can determine the optimal number of cores and their dimensions from data alone, reducing overfitting and improving generalization on noisy datasets (demonstrated robust performance from-20dB to 30dB SNR).
Improvement: Replace point-estimate maximum likelihood approaches with full posterior distributions over all parameters (factor matrices, cores, noise precision), using mean-field variational inference.
Capability: The system provides confidence intervals for all extracted patterns and can distinguish between genuine structure and noise-induced artifacts, particularly valuable in low-SNR regimes where MLE methods overfit.
Improvement: Leverage the orthogonality property of factor matrices to derive closed-form updates for core covariance matrices, reducing computational complexity from O(K3) to O(K) per core element.
Capability: The system achieves inference speeds 10-15x faster than the best-performing MLE baseline (BTD-NLS) while maintaining superior reconstruction accuracy, making it practical for large-scale tensor data.
Improvement: Implement the sparse core prior that automatically shrinks unnecessary core elements toward zero, allowing the system to gracefully handle incorrect model order specifications.
Capability: When given an over-specified model (e.g., BTD(4,6) when truth is BTD(4,3)), the system prunes redundant components and achieves lower reconstruction error than MLE methods that cannot perform such regularization.
Improvement: Apply the probabilistic BTD framework to EEG inter-trial phase coherence data with automatic component ranking and uncertainty-aware factor loading estimation.
Capability: The system can identify discriminative neural components (e.g., distinguishing left vs. right hand stimulation) with quantified reliability, while simultaneously providing model evidence for choosing between interpretable CPD representations and more expressive Tucker representations.
Improvement: Use the factorized Q-distribution approximation with closed-form update equations for all parameters, avoiding expensive MCMC sampling while maintaining Bayesian benefits.
Capability: The system scales to tensors with millions of elements (e.g., 28×64×4392 EEG data) with computational complexity comparable to conventional maximum likelihood estimation, making Bayesian tensor analysis feasible for real-world applications.

Abstract

Tensors are ubiquitous in science and engineering and tensor factorization approaches have become important tools for the characterization of higher order structure. Factorizations includes the outer-product rank Canonical Polyadic Decomposition (CPD) as well as the multi-linear rank Tucker decomposition in which the Block-Term Decomposition (BTD) is a structured intermediate interpolating between these two representations. Whereas CPD, Tucker, and BTD have traditionally relied on maximum-likelihood estimation, Bayesian inference has been use to form probabilistic CPD and Tucker. We propose, an efficient variational Bayesian probabilistic BTD, which uses the von-Mises Fisher matrix distribution to impose orthogonality in the multi-linear Tucker parts forming the BTD. On synthetic and two real datasets, we highlight the Bayesian inference procedure and demonstrate using the proposed pBTD on noisy data and for model order quantification. We find that the probabilistic BTD can quantify suitable multi-linear structures providing a means for robust inference of patterns in multi-linear data.