Non-negative Tensor Mixture Learning for Discrete Density Estimation

Authors: Kazu Ghalamkari, Jesper Løve Hinrich, Morten Mørup
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords: Tensor factorization, EM algorithm, Low-rank approximation

Abstract:
We present an expectation-maximization (EM) based unified framework for non-negative tensor decomposition that optimizes the Kullback-Leibler divergence. To avoid iterations in each M-step and learning rate tuning, we establish a general relationship between low-rank decomposition and many-body approximation. Using this connection, we exploit that the closed-form solution of the many-body approximation can be used to update all parameters simultaneously in the M-step. Our framework offers not only a unified methodology for a variety of low-rank structures, including CP, Tucker, and Train decompositions but also their combinations forming mixtures of tensors. The weights of each low-rank tensor in the mixture can be learned from the data, which eliminates the need to carefully choose a single low-rank structure in advance. We empirically demonstrate that our framework provides superior generalization for discrete density estimation compared to conventional tensor-based approaches.

Decision: reject
Reviewer scores: 3, 6, 3, 5

Reviews and discussion:
<thread>
creation date:
1730608668882

thread_type:
official_review

<thread_object>
creator: reviewer_edxn

<content>
summary:
The work deals with a nonnegative tensor decomposition algorithm for discrete density estimation. The framework is based on expectation maximization algorithm from KL divergence minimization perspective. Unlike the existing KL divergence-based nonnegative tensor decomposition algorithms for this problem that used gradient-based iterative steps for parameter updates, the proposed approach leverages the insights from the many-body approximation problem. Consequently, the updates of the parameters in the M-step boils down to closed form expressions, reminiscent of the updates derived in (Huang & Sidiropoulos,2017; Yeredor & Haardt, 2019) .

strengths:
Strengths:

1.	The proposed tensor decomposition method is a general framework that can handle different types of tensor decomposition models like CP, Tucker and tensor train, innovatively utilizing the many body approximation technique from the (Ghalamkari et al.,2023). The closed-form updates of the parameters in the M-step of the EM algorithm is also attractive as it avoid tuning of any hyperparameters, which is often practically inconvenient

weaknesses:
Weakness:

1.	The paper organization has lot of room for improvement. From the start of the paper, a clear description of problem is missing. Section 4 introduces the problem statement, while section 3 starts describing the approach (many-body approximation). Then, it is confusing to connect and understand that some of the terms have been obtained from the previous step of the algorithm.

2.	The problem formulation and the application of the solution itself is debatable. The tensor ${\cal T}$ is an empirical distribution tensor which is of the dimension of the categorical features. The entire solution of discrete density learning depends on the accuracy of the empirical tensor, which is hard to make sure due to curse of dimensionality. 

3.	The problem is hardly scalable as it deals with the many-body approximation tensor ${\cal M}$ whose dimension is much larger than that of even the empirical tensor ${\cal T}$.

4.	The experiments and major baselines are lacking. In discrete density estimation, there are works using second and third order marginals, that can mitigate the curse of dimensionality problem to an extent.

a.	Kargas, Nikos & Sidiropoulos, N.D. & Fu, Xiao. (2017). Tensors, Learning, and “Kolmogorov Extension” for Finite-Alphabet Random Vectors. IEEE Transactions on Signal Processing. 66. 10.1109/TSP.2018.2862383.

b.	S. Ibrahim and X. Fu, "Recovering Joint Probability of Discrete Random Variables From Pairwise Marginals," in IEEE Transactions on Signal Processing, vol. 69, pp. 4116-4131, 2021, doi: 10.1109/TSP.2021.3090960

Discussions and comparisons with these baselines would help readers understand the strength of the approach (if any).

questions:
Questions/Comments:

1.	Writing and Organization: It is important to introduce the low-rank tensor structures when discussing it in the introduction. 

2.	It is commented that “it always converges regardless of the choice of the low-rank structure assumed in the model.” EM convergence is hard to establish unless it is well initialized. Hence, it is not easy to claim convergence for the proposed method

3.	While there is a technique introduced to reduce the computational complexity of tensor train decomposition as presented in Section 4.2, computational complexity of Tucker remains the same which becomes dominant especially the case of K>1 mixture cases. The convergence speed curves should be presented with time in x axis to understand where it stands with respect to the baselines. Due to the computational complexity, it is also challenging to utilize the mixture model in practice. Once may need to choose the component of the mixtures (the type of tensor decomposition) , rather than allowing the model to learn by itself. A detailed discussion on the limitation of the approach (in the main section) would help here. 

4.	It is unclear how does the adaptive noise term guarantees the ``convexity” and convergence as claimed in Section 4.4. What do you mean by convexity here? How do you learn the noise parameter here? Do you learn different noise parameter for different low-rank tensor models?

5.	Experiments are limited to showing negative log likelihood. While it shows the dynamics of the algorithm, it does not show how does the approach learn the ground-truth. Simulation studies would help understand how well the method learns the true discrete density. In real data experiments, missing value prediction should be a better approach to understand the applicability of the approach.

6.	Minor typos: “distribution underlying the data” in Page 5, notation $\eta^k$ is confusing with $\eta$ raised to kth power.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730652225521

thread_type:
official_review

<thread_object>
creator: reviewer_kjtx

<content>
summary:
This paper aims to parsimoniously unify a variety of low-rank tensor decomposition structures and address discrete density estimation using a novel mixture of decompositions method. The method permits mixtures of CP, Tucker, and tensor-train decompositions to model non-negative data. The authors derive a computationally efficient expectation-maximization (EM) algorithm for performing inference in their model. The inference algorithm allows for learning of the mixture weights of the components, which are tensor decompositions. In addition to establishing a unifying framework for low-rank tensor decompositions, the authors demonstrate their method’s effectiveness in estimating discrete mass functions by comparing a specific instance of their method, EMCPTrain, to a large body of existing ones. Their method achieves marginally better negative-log-likelihood per sample than existing methods.

strengths:
The contribution of closed-form maximization updates for the specific EM algorithm is a strength. The computational efficiency, in some instances of the method (such as EMCPTrain), are useful. The unifying framework across low-rank tensor decompositions is parsimonious, and leveraging the parsimony of mixture models is a neat idea. I particularly like how the authors show that one may learn the weights of their mixture model, removing the need to choose between low-rank structures in advance of training.

weaknesses:
The approach, while unifying in theory and a neat idea, yields very incremental empirical results at best. The empirical gains are modest. When more baselines are taken into account, as in Table 6, the gains are further reduced. The comparisons and evaluations are not well-organized, making the aggregate contribution difficult to evaluate across the many tables in Section 5 and Appendix C. There are some section of the paper that came across as unclear that first time I read it. In particular, the paper refers to “many-body approximation” many times in the first two sections of the paper without a clear definition. A formal definition in Section 1 would help clarify how the paper aims to leverage the many-body approximation representation.

questions:
In my experience, adding a noise (or constant tensor) term to a non-negative tensor decomposition can significantly improve model fit, and the empirical results shown in Table 2 mostly demonstrate this phenomena. How much of the empirical improvements in negative log-likelihood are from the adaptive noise term? I view the ability to seamlessly learn the noise term from the data as an advantage of this method, although I am concerned it is the only substantial advantage of this method in practice. 
When would it be useful to include a Tucker component in practice? EMTucker is computationally expensive, scaling as R^D. While EMTuckerN beats existing methods in Table 5, it generally performs worse than EMCPTrainN.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730941949108

thread_type:
official_review

<thread_object>
creator: reviewer_jcin

<content>
summary:
This work presents an expectation-maximization (EM) based unified framework for nonnegative tensor decomposition that optimizes the Kullback-Leibler divergence, and further establishes a general relationship between low-rank decomposition and many-body approximation. The proposed framework offers a unified methodology for a variety of low-rank structures, including CP,
Tucker, and Train decompositions, and their combinations. A series of experiments are carried out to illustrate the merits of the developed methodology.

strengths:
1. A unified methodology has been developed to deal with a variety of low-rank structures, including CP, Tucker, Train decompositions, and  their combinations, forming mixtures of low-rank tensors. 
2. A mixture of low-rank tensor modeling procedure is developed  to empirically demonstrates inferential robustness and improved generalization.
3. Both theoretical analysis and numerical comparisons are provided to show the merits of the proposed methodology.

weaknesses:
1. The convergence analysis seems overly coarse and somewhat redundant, as it only demonstrates that negative cross-entropy increases with iterations—an expected result given the maximization objective. More importantly, the analysis should address how negative cross-entropy could converge to the true value.
2. Please note that the computational cost of the proposed algorithm increases significantly with the size of the tensor. Kindly provide the specific order of computational complexity and compare it with the complexity orders of related algorithms.
3. The compared baselines are not SOTA. Please consider some recent methods for numerical comparisons. 
4. Please provide a detailed description of the convergence conditions in Algorithm 1.

questions:
Is there a specific general mathematical expression for the many-body approximation?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732281134018

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response by Authors

comment:
We appreciate all reviewers for their efforts. We summarize our rebuttal here. The major comments can be divided into the following five categories: convergence of the algorithm, scalability, readability, convergence to the true distribution, and comparison with SOTA.


**1. Convergence of the algorithm** (JciN, edxN)

*The proposed algorithm always converges*, which is proved by Theorem 4 regardless of initial value and low-rank structures. 


**2. Scalability** (JciN, edxN)

*Our framework is scalable* except for EMTucker since the tensor M is sparse, and the closed-form update requires summation on only observed indices. In practice, our mixture model successfully works on large tensors, such as the 35th-dimensional Chess dataset. 

**3. Readability** (Kjtx, edxN)

We inserted the definition of many-body approximation and problem setup in Section 1 (Lines 111-120). 

**4. Convergence to the true distribution** (JciN)

We conducted additional experiments with synthetic data, demonstrating that the proposed method can estimate the true distribution as the sample size increases. (Please refer to Figure 7.)

**5. The empirical gain is limited, and there is no comparison with SOTA** (JciN, edxN)

We added the pairwise marginalized-based CNMFOPT as a baseline (Table 1). We agree that the empirical gains are modest in terms of generalization error. However, we emphasize our motivation is not SOTA and our gains are
- a unified optimization framework that is flexible enough to be applied freely to a variety of non-negative low-rank structures (CP, Tucker, Train, and Tree), mixtures, and adaptive noise-term,
- convergence guarantee monotonically decreasing the KL divergence,
- closed update rules for all parameters simultaneously,
- eliminating the need to tune the learning rate, which is often required in modern methods.


If you have any additional questions, concerns, or discussions, please feel free to respond.

Best,

Authors of the submission #6148
</content>
</thread_object>

</thread>
<thread>
creation date:
1732550601354

thread_type:
official_review

<thread_object>
creator: reviewer_yenj

<content>
summary:
This paper studies negative tensor decomposition that optimizes the Kullback-Leibler divergence. To avoid iterations in each M-step and learning rate tuning, they establish a general relationship between low-rank decomposition and many-body approximation. The framework offers not only a unified methodology for a variety of low-rank structures, including CP, Tucker, and Train decompositions, but also their combinations, forming mixtures of low-rank tensors. The weights of each low-rank tensor in the mixture can be learned from the data, which eliminates the need to carefully choose a single low- rank structure in advance

strengths:
The logic of the paper is reasonable to me that they want to optimize each block in an alternating minimization/maximization way, the experiments look good and rich, demonstrating the benefit of the proposed algorithm.

weaknesses:
I don't see novel contribution in this paper, to me, the nonnegative tensor factorization is well studied in both distance and divergence. The author find the optimal solutions by making use of EM or alternating method including weights $\eta$'s, which is well known.

questions:
Is there any theoretical guarantee that your updating algorithm can converge to local minimal or global minimal. Though the objective is nonconvex, but there exists a wide class of factorization problem that local minimal is also global.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733226858490

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response by Authors, Part II

comment:
Given comments from Reviewers edxN and Kjtx, we provide the experiment for the classification based on the estimated density with additional five datasets. 


Following the description in Section D.1, we estimate the density $p$. The final feature $x_D$ in the density $p(x_1,\dots,x_D)$ corresponds to the class label of the discrete item $(x_1,\dots,x_{D-1})$. Thus, for a given test sample ${\bf y} = (y_1,\dots,y_{D-1})$, we see the estimated density $p(x_1=y_1, \dots, x_{D-1}=y_{D-1}, c)$ for each class label $c$. The sample ${\bf y}$ is then classified into the class $c$ that maximizes $p(y_1,…,y_{D-1},c)$. We repeated the calculations five times with random initialization to evaluate the mean and standard error of accuracy.



|               | CNMFOPT    | MPS        | BM         | LPS        | EMCPTrainN | 
| :--- | :---: |  :---: |  :---: |  :---: |  :---: | 
| CarEvaluation | 0.71(0.00) | 0.92(0.03) | 0.79(0.12) | 0.97(0.00) | 0.91(0.02) | 
| Mofn          | 0.77(0.04) | 0.97(0.02) | 0.99(0.00) | 1.00(0.00) | 0.98(0.01) | 
| XD6           | 0.74(0.02) | 1.00(0.00) | 0.99(0.00) | 1.00(0.00) | 1.00(0.00) | 
| Parity5p5     | 0.42(0.00) | 0.99(0.00) | 0.41(0.02) | 0.88(0.27) | 1.00(0.00) | 
| GermanGSS     | 0.83(0.00) | 0.83(0.00) | 0.83(0.06) | 0.89(0.01) | 0.90(0.03) | 

We emphasize that our method does not require hyperparameter for optimization, while other baselines, CNMFOPT, BM, MPS, and LPS, require learning rate and/or batch size tuning. Please refer to Section D.2.2 for the hyperparameter selection. 

The experimental result demonstrates that the proposed method achieves competitive classification performance compared to existing methods.

Again, our motivation is not to achieve SOTA but to develop a generic, flexible, and unified framework for tensor factorization that optimizes the KL divergence with guaranteed convergence. Please also refer to our answer [**5**. in General Response Part I](https://openreview.net/forum?id=mbo4YnWCHd&noteId=uKnAvn0Co9).


---


### Dataset detail:

We used relatively large datasets in the main text to verify the scalability of our methods. However, these datasets have a small number of samples relative to the vast size of the sample space, making them unsuitable for evaluation in classification tasks (Table 7). Therefore, we used the following dataset for this experiment.

|               | D (dimension of tensor) | # Classes | # Samples | | 
| :--- | :---: |  :---: |  :---: |  :---: | 
| CarEvaluation | 7                       | 5       | 1728      | UCI Datasets               | 
| Mofn          | 11                      | 2       | 1342      | PMLB Datasets               | 
| XD6           | 10                      | 10      | 973       | PMLB Datasets               | 
| Parity5p5     | 6                       | 4       | 400       | PMLB Datasets               | 
| GermanGSS     | 6                       | 2       | 400       | PMLB Datasets               |
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper introduces an EM-based unified framework for tensor decomposition founded on KL-divergence minimization. The authors use low-rank decomposition and many-body approximations to derive closed-form updates during the M-step. The reviewers found the overall idea interesting and appreciated both the framework's applicability to various tensor decomposition scenarios and the absence of required hyperparameter tuning. However, they expressed concerns regarding the experimental validation of the proposed approach. Although the authors attempted to address these concerns during the rebuttal phase, they did not provide sufficiently convincing arguments or demonstrate clear practical benefits. I believe the current version of the paper requires significant revision, particularly in terms of experimental validation. Therefore, I recommend rejecting the paper in its current form.