Learning from Binary Multiway Data: Probabilistic Tensor Decomposition and its Statistical Optimality

Miaoyan Wang, Lexin Li

TL;DR

This paper introduces a multilinear Bernoulli model and a rank-constrained maximum likelihood estimation (MLE) framework for decomposing binary (0/1) tensors. The authors establish minimax-optimal statistical error bounds, uncover a counterintuitive phase transition where stochastic noise actually aids recovery, and provide an alternating optimization algorithm with convergence guarantees.

What Problem Does This Paper Address?

Binary multiway data (e.g., user click/no-click actions, multi-relational social connections, or binary brain structural connectomes) are ubiquitous across modern data science. Classical tensor methods—such as CANDECOMP/PARAFAC (CP) or Tucker decompositions—assume continuous-valued entries and rely on least-squares criteria. Applying continuous methods directly to 0/1 data can lead to predictions outside $[0, 1]$ and sensitivity to entry flipping ($0 \leftrightarrow 1$).

Furthermore, while prior work explored binary matrix factorization or heuristic/Bayesian binary tensor decompositions, the statistical optimality and theoretical recovery limits for binary higher-order tensors in diverging dimensions had remained largely uncharacterized.

Methods

  • Multilinear Bernoulli Model: The observed binary tensor $\mathcal{Y} \in \{0, 1\}^{d_1 \times \cdots \times d_K}$ has independent Bernoulli entries conditioned on a continuous latent parameter tensor $\Theta$: $\mathbb{P}(y_{i_1, \dots, i_K} = 1) = f(\theta_{i_1, \dots, i_K})$, where $f$ is an inverse link function (e.g., logistic, probit, or Laplace) and $\Theta$ has a low-rank CP structure $\Theta = \sum_{r=1}^R \lambda_r a_r^{(1)} \otimes \cdots \otimes a_r^{(K)}$.
  • 1-Bit Quantization Connection: The model is shown to be equivalent to thresholding a noisy continuous latent tensor: $\mathcal{Y} = \text{sign}(\Theta + \mathcal{E})$.
  • Constrained MLE: Estimates $\Theta$ by maximizing the Bernoulli log-likelihood subject to a rank constraint $\text{rank}(\Theta) \le R$ and an entrywise boundedness constraint $\|\Theta\|_{\max} \le \alpha$.
  • Alternating Optimization (Algorithm 1): Updates one mode factor matrix at a time while fixing all others. Crucially, updating mode $k$ decomposes row-by-row into $d_k$ independent Generalized Linear Models (GLMs), enabling easy parallelization and utilization of existing GLM solvers. Each iteration is followed by a line search to enforce constraints.
  • Rank Selection: Employs the Bayesian Information Criterion (BIC) balancing data fit against effective parameter counts.

Datasets

The authors evaluated their framework on synthetic data (CP models and multi-way stochastic block models) and four real-world benchmarks:

  1. Kinship: A $104 \times 104 \times 26$ tensor of 26 kinship relations across 104 individuals of the Australian Alyawarra tribe.
  2. Nations: A $14 \times 14 \times 56$ tensor of 56 political actions/relationships among 14 nations (1950–1965).
  3. Enron: A sparse $581 \times 124 \times 48$ tensor tracking (sender, receiver, time) email communications.
  4. HCP (Human Connectome Project): A $68 \times 68 \times 212$ tensor encoding the presence/absence of white-matter fiber connections among 68 brain regions across 212 subjects.

Key Insights and Ideas

  • Optimal Tensor Rate: For an equal-dimension tensor ($d_1 = \dots = d_K = d$), the estimation error in Frobenius loss scales as $O(d^{-(K-1)/2})$. This matches the information-theoretic minimax lower bound and is strictly faster than matricization/flattening strategies ($O(d^{-\lfloor K/2 \rfloor / 2})$) or nuclear-norm-relaxed 1-bit tensor completion ($O(d^{-(K-1)/4})$).
  • The "Noise Helps" Phenomenon (Dithering): In continuous tensor estimation, higher noise always degrades performance. In binary tensor estimation, there is a distinct three-phase transition governed by the latent Signal-to-Noise Ratio ($\text{SNR} = \|\Theta\|_{\max}/\sigma$):
  • High SNR ($\text{SNR} \gg O(1)$): Near-zero noise causes identical sign patterns for vastly different signals (a deterministic quantization ceiling/perfect separation). Adding stochastic noise provides "dithering" that smooths probabilities, making estimation possible; thus, noise helps.
  • Moderate SNR: Error scales linearly with $\sigma$, matching continuous tensor rates (minimal information is lost due to 1-bit quantization).
  • Low SNR: The signal is buried; consistent estimation is impossible.

Key Results

  • Binary Tensor Completion: Across 5-fold cross-validation (80% train / 20% test), the proposed method consistently surpassed continuous-valued decomposition in AUC and Root Mean Squared Error (RMSE):
  • Kinship: AUC 0.9708 vs. 0.9436; RMSE $1.2 \times 10^{-4}$ vs. $1.4 \times 10^{-3}$.
  • Nations: AUC 0.9169 vs. 0.8619; RMSE $1.1 \times 10^{-2}$ vs. $2.2 \times 10^{-2}$.
  • Enron (only 0.01% non-zeros): AUC 0.9432 vs. 0.7956; classical least-squares fails in extreme sparsity by predicting all zeros.
  • HCP: AUC 0.9860 vs. 0.9314.
  • Clustering & Interpretability:
  • Nations: Recovered 5 interpretable political blocs (communist, Western, neutral, etc.) and identified key relational drivers (e.g., common bloc membership, NGO alliances).
  • HCP: Extracted distinct intra-hemispheric association fibers and inter-hemispheric commissural tracts (identifying the corpus callosum).
  • Computational Efficiency: The per-iteration cost scales as $O(R^3 \sum_k d_k + R^2 K \prod_k d_k)$. For $d=60$ and $R=10$, each iteration took under 3 seconds, typically converging in under 8 iterations.

Limitations and Future Work

  • Non-Convex Landscape & Global Optima: Although any estimator in the level set $\{ \mathcal{L}(\hat{\Theta}) \ge \mathcal{L}(\Theta_{\text{true}}) \}$ is statistically optimal, the alternating algorithm only guarantees convergence to a stationary point. Formal global convergence guarantees remain open.
  • Rank Selection Theory: The authors use BIC empirically to pick rank $R$, but formal consistency proofs for rank estimation in this model remain to be investigated.
  • Beyond Bernoulli: Extending this theoretical framework and GLM-based alternating algorithm to other non-Gaussian distributions (e.g., Poisson/count tensors, multinomial/categorical tensors) is suggested for future research.

Summary updated

Abstract

We consider the problem of decomposing a higher-order tensor with binary entries. Such data problems arise frequently in applications such as neuroimaging, recommendation system, topic modeling, and sensor network localization. We propose a multilinear Bernoulli model, develop a rank-constrained likelihood-based estimation method, and obtain the theoretical accuracy guarantees. In contrast to continuous-valued problems, the binary tensor problem exhibits an interesting phase transition phenomenon according to the signal-to-noise ratio. The error bound for the parameter tensor estimation is established, and we show that the obtained rate is minimax optimal under the considered model. Furthermore, we develop an alternating optimization algorithm with convergence guarantees. The efficacy of our approach is demonstrated through both simulations and analyses of multiple data sets on the tasks of tensor completion and clustering.
BibTeX
@article{wang2020learning,
  author = {Miaoyan Wang and Lexin Li},
  title = {{Learning from Binary Multiway Data: Probabilistic Tensor Decomposition and its Statistical Optimality}},
  journal = {J. Mach. Learn. Res.},
  year = {2020},
  url = {https://openreview.net/forum?id=VCVh46CdD7},
}

Loading related content...

Figure