PaperlayerView exact revision on arXiv

Source-linked AI summary

PU Learning for Matrix Completion

Cho-Jui Hsieh, Nagarajan Natarajan, Inderjit S. Dhillon

arXiv:1411.6081v1cs.LGmath.NAstat.ML

TL;DR

The paper asks how to complete a matrix when observations are one-bit and only positive entries are revealed. It proposes shifted and biased matrix completion under probabilistic and thresholded models, obtaining O(1/((1−ρ)n)) error for n × n matrices and demonstrating effectiveness on large link-prediction data.

  • Problem

    PU matrix completion seeks recovery when one-bit observations reveal only a subset of positive entries, a setting motivated by recommender systems and social networks.

  • Method

    The paper uses shifted matrix completion for probabilistic binary generation and biased matrix completion for thresholded binary observations, under a bounded nuclear-norm assumption.

  • Results

    The methods achieve O(1/((1−ρ)n)) error for n × n matrices and demonstrate effectiveness for link prediction on networks with over 2 million users and 90 million links.

  • Takeaways & Limitations

    The results provide theoretical support for recovering matrices from one-sided positive observations and for the biased matrix-completion approach used heuristically in practice.

  • Takeaways & Limitations

    In the deterministic setting, the real-valued matrix M is impossible to recover from its thresholded matrix Y, even when all entries of Y are observed.

Abstract

from arXiv · show

In this paper, we consider the matrix completion problem when the observations are one-bit measurements of some underlying matrix M, and in particular the observed samples consist only of ones and no zeros. This problem is motivated by modern applications such as recommender systems and social networks where only "likes" or "friendships" are observed. The problem of learning from only positive and unlabeled examples, called PU (positive-unlabeled) learning, has been studied in the context of binary classification. We consider the PU matrix completion problem, where an underlying real-valued matrix M is first quantized to generate one-bit observations and then a subset of positive entries is revealed. Under the assumption that M has bounded nuclear norm, we provide recovery guarantees for two different observation models: 1) M parameterizes a distribution that generates a binary matrix, 2) M is thresholded to obtain a binary matrix. For the first case, we propose a "shifted matrix completion" method that recovers M using only a subset of indices corresponding to ones, while for the second case, we propose a "biased matrix completion" method that recovers the (thresholded) binary matrix. Both methods yield strong error bounds --- if M is n by n, the Frobenius error is bounded as O(1/((1-rho)n), where 1-rho denotes the fraction of ones observed. This implies a sample complexity of O(n\log n) ones to achieve a small error, when M is dense and n is large. We extend our methods and guarantees to the inductive matrix completion problem, where rows and columns of M have associated features. We provide efficient and scalable optimization procedures for both the methods and demonstrate the effectiveness of the proposed methods for link prediction (on real-world networks consisting of over 2 million nodes and 90 million links) and semi-supervised clustering tasks.

1 Introduction

The paper formulates matrix completion from one-sided positive observations as PU matrix completion and develops recovery guarantees, scalable algorithms, and empirical evaluations for this setting.

  • Problem motivation: PU matrix completion asks whether an underlying matrix can be recovered when only a subset of positive entries is observed.The setting combines one-bit quantization with one-sided sampling and is motivated by applications such as recommender systems and social networks.
  • Problem motivation: Observed positive entries alone can produce a degenerate all-ones rank-1 solution under squared-loss completion.Treating missing observations as zeros is a practical heuristic, especially when the underlying matrix has few positive entries.
  • Contributions: The paper introduces PU matrix completion, extends the analysis to inductive matrix completion, and provides recovery guarantees and scalable optimization algorithms.The contributions include theoretical insight into biased matrix completion and experiments on simulated and real-world data.
  • Contributions: O(1/((1−ρ)n)) is the reported recovery error for an n × n matrix in the non-deterministic setting, compared with O(1/((1−ρ)√n)) implied by prior work.Here, 1−ρ is the fraction of observed 1’s.
  • Empirical evaluation: Experiments on social networks with over 2 million users and 90 million links demonstrate the proposed methods’ superiority for link prediction.The paper also presents synthetic-data experiments and describes its experimental evaluation in a dedicated section.

2 Problem Settings

The paper studies PU matrix completion under probabilistic and thresholded observation models, while identifying limits of recovering the real-valued matrix and prior approaches.

  • Problem formulation: The model assumes a bounded nuclear norm, ∥M∥_*≤t, and observes only a uniformly sampled subset of positive entries.The observed subset Ω1 is drawn from indices where the binary observation matrix Y equals one.
  • Non-deterministic setting: In the non-deterministic setting, entries Mij ∈[0,1] parameterize probabilities that generate a clean binary matrix Y.The observed matrix A retains each positive entry with sampling ratio 1−ρ, so P(Aij=1)=Mij(1−ρ).
  • Non-deterministic setting: Prior one-bit completion can be adapted by treating unobserved entries as zeros, but its recovery guarantee may require more than O(n log n) observed ones for dense matrices.The cited analysis describes this sample complexity as too high for the dense case.
  • Non-deterministic setting: The shifted estimator is obtained through an optimization problem using an unbiased loss for the underlying squared error.The shifted loss is applied to observed Aij while minimizing expected loss with respect to the latent matrix.
  • Deterministic setting: In the deterministic setting, thresholding produces Yij=I(Mij>q), but only a subset of positive entries is observed.The observation matrix A marks sampled positive indices and sets all other entries to zero.
  • Deterministic setting: The real-valued matrix M cannot be recovered from Y even when every entry of Y is observed, because distinct matrices can share the same thresholded output.The recovery target is therefore the thresholded binary matrix Y rather than M.
  • Deterministic setting: Applying noisy matrix completion to the deterministic setting is not guaranteed to improve over the trivial estimator A.The stated bound is ∥Ŷ−Y∥≤∥A−Y∥.

3 Proposed Algorithms for PU Matrix Completion

The section introduces shifted matrix completion for non-deterministic PU learning and biased matrix completion for deterministic PU learning. Both methods use loss constructions suited to one-sided positive observations and provide error guarantees that scale favorably with matrix size and the observed-positive fraction.

  • Shifted Matrix Completion: Shifted matrix completion uses an unbiased loss estimator on asymmetric noisy observations, with trace-norm and boundedness constraints controlling the optimization.The observed matrix has false negatives but no false positives, and the shifted loss estimates the underlying squared loss in expectation.
  • Shifted Matrix Completion: O(1/(n(1−ρ))) average error is achieved for n × n matrices, where 1−ρ is the ratio of observed 1’s.The result states that accurate estimation remains possible even when only a small ratio of ones is observed, provided n is sufficiently large.
  • Biased Matrix Completion: Biased matrix completion minimizes a label-dependent loss and recovers the underlying binary matrix by thresholding the fitted matrix at q.The thresholding operator assigns one when the fitted value exceeds q and zero otherwise.
  • Biased Matrix Completion: O(1/(n(1−ρ))) average error is also obtained for the biased matrix completion estimator on n × n matrices.The bound has the same order as the ShiftMC estimator and includes η = max(1/q^2, 1/(1−q)^2).

4 PU Inductive Matrix Completion

The paper extends PU matrix completion to settings where rows and columns have associated features. Shifted and biased inductive methods operate in feature-induced subspaces and retain vanishing mean-square-error guarantees under bounded dimensions and appropriate subspace assumptions.

  • Problem and Setting: Inductive PU matrix completion incorporates row and column features Fu and Fv into the factorization of the target matrix.The framework covers applications including multi-label learning and semi-supervised clustering with partially observed positive relationships.
  • Feature Assumptions: The inductive estimator can recover the ground-truth matrix when its row and column spaces lie in the subspaces formed by Fu and Fv.The paper assumes the ground truth has the representation M = Fu(Fu)^T M Fv(Fv)^T.
  • Shifted Inductive Matrix Completion: O(1/n) mean squared error is obtained for inductive ShiftMC when t and d are bounded.The guarantee applies to the shifted inductive method under the stated feature-space assumptions.
  • Biased Inductive Matrix Completion: Inductive BiasMC uses a thresholded fitted factorization and relates its expected 0-1 error to a label-dependent weighted error through a linear transformation.The transformation uses α* = (1+ρ)/2 and supports the corresponding recovery theorem.
  • Biased Inductive Matrix Completion: O(1/n) mean squared error is obtained for inductive BiasMC when t and d are bounded.The result is stated for the deterministic inductive setting with the fitted matrix thresholded to produce the binary output.

5 Optimization Techniques for PU Matrix Completion

The paper develops scalable optimization procedures for BiasMC and ShiftMC, including low-rank and relaxed formulations suited to large datasets.

  • BiasMC can be solved efficiently for datasets with millions of rows and columns, while ShiftMC becomes efficient after relaxation.
  • Proximal gradient descent updates use singular-value soft thresholding, with approximate SVD computed through power or Lanczos methods.
  • Low-rank representations reduce gradient-related computation to O(mk^2 + nk^2) plus O(|Ω1|k) terms.
  • BiasMC’s non-convex form supports efficient ALS or coordinate descent, with each coordinate update requiring O(|Ωi| + k) flops.
  • ShiftMC’s bounded constraint makes direct optimization expensive, motivating a relaxed formulation for scaling to large datasets.

6 Experiments

Experiments on synthetic data, link prediction, and semi-supervised clustering support the proposed methods’ theoretical error behavior, predictive performance, and scalability.

  • 6.1 Synthetic Data: Synthetic experiments with ρ = 0.9 show that estimator error decreases with matrix size, consistent with the theoretical O(1/n) rate.
  • 6.1 Synthetic Data: The best BiasMC performance occurs at α = (1+ρ)/2, while performance remains well-behaved across a range of α values.
  • 6.2 Link Prediction: On real-world link prediction datasets, BiasMC generally performs best, ShiftMC often performs strongly early, and both methods achieve lower FPR and FNR than competitors.
  • 6.3 Inductive Matrix Completion: BiasMC-inductive outperforms MC-inductive and spectral clustering, which respectively treat unlabeled pairs as zeros or omit feature information.
  • 6.2 Link Prediction: BiasMC processes the largest MySpace dataset in 516 seconds for 10 coordinate-descent sweeps, compared with 2408 seconds for 100 Matlab eigenvectors.
  • 6.3 Inductive Matrix Completion: BiasMC-inductive is evaluated for semi-supervised clustering with positive relationships only on Mushroom and Segment datasets.

7 Conclusions

The paper concludes that its methods recover matrices accurately despite one-bit quantization and one-sided sampling, with theory supported by synthetic and real-world experiments.

  • The work studies two PU matrix completion settings and provides similar recovery guarantees for both.
  • Synthetic experiments conform to the theory, while real-world network experiments demonstrate effectiveness for link prediction.
  • Selecting or estimating the BiasMC parameter α remains an open direction for further research.

A.2 Proof of Theorem 3

The proof bounds concentration and random-matrix terms using bounded sensitivity and a theorem for independent zero-mean random matrices.

  • Changing one random observation changes the relevant loss by at most a quantity controlled by 1/(1−ρ).
  • The proof uses that Aij is deterministically zero when Mij = 0 in the analyzed setting.
  • Latala’s theorem bounds the expected spectral norm of the random matrix by C(√n + √m + 4√s).

A.3 Proof of Theorem 4

The proof establishes the required bound by analyzing the two possible values of Y_ij, controlling complexity through a trace-norm Rademacher bound, and extending the argument to inductive matrix completion.

  • Case analysis: The proof verifies the key inequality separately for Y_ij = 0 and Y_ij = 1 using η = max(1/q^2, 1/(1 − q)^2).The two cases reduce to bounds involving q and 1 − q, and the chosen η satisfies both requirements.
  • Complexity bound: The proof bounds the shifted loss using its Lipschitz property, with constant 1/(1 − ρ) when X_ij lies between 0 and 1.This bound is then combined with a Rademacher-complexity argument.
  • Complexity bound: A trace-norm Rademacher lemma is applied to the feasible matrix class, where the number of observed-one terms is p = n^2(1 − ρ).The resulting bound contains the factors t, √(log 2d), √(mn), and √(1 − ρ).
  • Inductive extension: For the inductive case, the proof preserves the key inequality despite dependent entries and the stricter representation X = F_u D F_v^T under a trace-norm constraint.Theorem 5 supplies the needed upper bound, after which the argument combines the preceding inequalities and Theorem 2.
Loading 1411.6081v1…