Using Side Information to Reliably Learn Low-Rank Matrices from Missing and Corrupted Observations

Kai-Yang Chiang, Inderjit S. Dhillon, Cho-Jui HsiehJMLR 2018 · OpenReview

TL;DR

This paper introduces a general framework for learning low-rank matrices from incomplete and noisy data by effectively leveraging "side information" (auxiliary features). Their novel model balances information from these features and the observed data, leading to more robust and efficient learning, particularly when features are imperfect.

What Problem Does This Paper Address?

Many real-world datasets exhibit an underlying low-rank structure, meaning they can be represented by a smaller set of latent factors. Learning this structure is crucial for tasks like recommender systems, image analysis, and social network analysis. However, real-world data is often messy: observations can be missing (e.g., a user hasn't rated a movie) or corrupted (e.g., noisy sensor readings). Traditional methods struggle with this combined challenge. While "side information" (like user profiles or image metadata) can be helpful, existing approaches either don't use it, use it in ad-hoc ways, or only work under strict assumptions (e.g., perfect side information). This paper aims to bridge this gap by developing a unified model that can reliably learn low-rank matrices from missing and corrupted data, even when the side information is imperfect.

Methods

The authors propose a general model that decomposes the target low-rank matrix $L_0$ into two parts: one that captures information from the side features ($XMY^T$) and another that captures information from the observations alone ($N$). This allows the model to leverage informative features while still being robust to noisy or incomplete features by relying on the observed data.

  • Perfect Side Information: For the idealized case where side information perfectly describes the latent space, they show it can be used to embed the low-rank matrix into a bilinear form ($L_0 = XMY^T$), significantly reducing the learning problem's complexity. This is related to existing "Inductive Matrix Completion" (IMC) models.
  • Noisy Side Information: For more realistic scenarios, their proposed model ($L_0 \approx XMY^T + N$) explicitly models both feature-based and observation-based components. They use nuclear norm regularization on both $M$ and $N$ to enforce low-rank structures.
  • Optimization: They employ an alternative minimization scheme (block coordinate descent) to efficiently solve the optimization problem.

The paper also shows how their general model encompasses and extends existing methods like standard matrix completion and robust PCA by adjusting regularization parameters.

Datasets

The paper uses several real-world datasets for evaluation:

  • Epinions: A social network dataset for relationship prediction.
  • Mushrooms, Segment, Covtype: Datasets for semi-supervised clustering.
  • MNIST: A dataset of handwritten digits for noisy image classification.

They also conduct experiments on synthetic data to systematically evaluate their model's performance under various conditions of data sparsity, corruption, and feature quality.

Key Insights and Ideas

  • Side information is powerful, even when noisy: The core insight is that auxiliary features can significantly improve low-rank matrix learning, even if they aren't perfect. The proposed model is designed to exploit this noisy but informative side information.
  • Balancing feature and observation information is key: The model's strength lies in its ability to balance learning from side information and learning from the observed data. This makes it robust to both noisy features and missing/corrupted observations.
  • Unified framework: The proposed model acts as a unifying framework for several existing low-rank matrix learning problems (matrix completion, robust PCA) and extends them by incorporating side information.
  • Theoretical guarantees for noisy features: The paper provides theoretical analysis showing that informative side information can lead to improved sample complexity (requiring fewer observations) for learning, even in the presence of noise.

Key Results

  • Synthetic Experiments:
    • In matrix completion, their proposed IMCNF model (using noisy features) consistently outperformed standard matrix completion (MC) and IMC (which is sensitive to feature noise).
  • In robust PCA, their PCPNF model (using noisy features) showed significantly better recovery than PCP (no features) and PCPF (perfect features) when features were noisy.
  • For combined missing and corrupted data, their model (PCPF-part) could recover matrices that PCP-part (without features) could not.
  • Real-world Applications:
    • Relationship Prediction: IMCNF achieved the best accuracy and AUC on the Epinions dataset, outperforming methods that either ignored features or were misled by noisy ones.
  • Semi-supervised Clustering: IMCNF combined the benefits of feature-based and constraint-based methods, achieving state-of-the-art performance.
  • Noisy Image Classification: Their PCPNF model, when incorporating both "Eigendigit" and "label-relevant" features, significantly improved classification accuracy by effectively denoising images, outperforming methods that used fewer features or were sensitive to feature noise.

Limitations and Future Work

  • Parameter tuning: The paper acknowledges that in practical applications, feature quality and noise levels might not be known a priori, requiring parameter tuning (e.g., via validation).
  • Approximate recovery: The theoretical analysis primarily focuses on approximate recovery guarantees, rather than exact recovery, which is a common trade-off for robustness.
  • Future Work: The authors suggest exploring stronger theoretical guarantees for exact recovery in general low-rank matrix learning, particularly in the context of robust PCA with side information. They also mention that their analysis is relatively loose compared to some existing guarantees that rely on stronger assumptions.

Summary updated

Abstract

Learning a low-rank matrix from missing and corrupted observations is a fundamental problem in many machine learning applications. However, the role of side information in low-rank matrix learning has received little attention, and most current approaches are either ad-hoc or only applicable in certain restrictive cases. In this paper, we propose a general model that exploits side information to better learn low-rank matrices from missing and corrupted observations, and show that the proposed model can be further applied to several popular scenarios such as matrix completion and robust PCA. Furthermore, we study the effect of side information on sample complexity and show that by using our model, the efficiency for learning can be improved given sufficiently informative side information. This result thus provides theoretical insight into the usefulness of side information in our model. Finally, we conduct comprehensive experiments in three real-world applications---relationship prediction, semi-supervised clustering and noisy image classification, showing that our proposed model is able to properly exploit side information for more effective learning both in theory and practice.
BibTeX
@article{chiang2018using,
  author = {Kai-Yang Chiang and Inderjit S. Dhillon and Cho-Jui Hsieh},
  title = {{Using Side Information to Reliably Learn Low-Rank Matrices from Missing and Corrupted Observations}},
  journal = {J. Mach. Learn. Res.},
  year = {2018},
  url = {https://openreview.net/forum?id=yipXv1vWhKW},
}
Figure