Linear Regression with Shuffled Labels

Abubakar Abid, Ada S. Y. Poon, James ZouarXiv 2017 · DOI · arXiv

Abstract

Is it possible to perform linear regression on datasets whose labels are shuffled with respect to the inputs? We explore this question by proposing several estimators that recover the weights of a noisy linear model from labels that are shuffled by an unknown permutation. We show that the analog of the classical least-squares estimator produces inconsistent estimates in this setting, and introduce an estimator based on the self-moments of the input features and labels. We study the regimes in which each estimator excels, and generalize the estimators to the setting where partial ordering information is available in the form of experiments replicated independently. The result is a framework that enables robust inference, as we demonstrate by experiments on both synthetic and standard datasets, where we are able to recover approximate weights using only shuffled labels. Our work demonstrates that linear regression in the absence of complete ordering information is possible and can be of practical interest, particularly in experiments that characterize populations of particles, such as flow cytometry.

Introduction: The "Who Goes with Whom?" Problem

In standard linear regression, we assume we have pairs of data: for every input $x$, we have a corresponding label $y$. However, in many real-world "population-level" experiments, this link is lost. For example, in flow cytometry, different properties of cells are measured in separate batches, resulting in two sets of measurements where the individual pairing is unknown. This "shuffled regression" problem also appears in data de-anonymization and archaeological dating.

The fundamental challenge is that the most intuitive approach—finding a permutation that minimizes the least-squares error—is statistically inconsistent. Even with minimal noise, this method produces a systematic "amplification bias," where the estimated weights are much larger than the true weights.

The Shuffled Regression Model

The authors formalize the problem using a model where input features $x$ undergo an unknown permutation $\pi_0$ before being processed by linear weights $w_0$ and corrupted by Gaussian noise $e$.

The shuffled regression model: input features $x$ are permuted by $\pi_0$, multiplied by weights $w_0$, and corrupted by Gaussian noise $e$ to produce labels $y$.

Proposed Estimators

To address the loss of ordering, several estimators are proposed:

  1. The LS (Least-Squares) Estimator: This method searches for weights that minimize the distance between sorted inputs and sorted labels. While computationally efficient, it is biased in the presence of noise because sorting forces the noise to align with the signal.
  2. The SM (Self-Moments) Estimator: This approach matches the statistical moments (e.g., mean, variance) of the predicted values to those of the observed labels. Since moments are order-invariant, this method ignores the unknown permutation.
  3. Hybrid Projection Estimators (P1, P2): For high-dimensional data, features are projected to a lower dimension before applying the SM estimator, followed by gradient-descent optimization.
  4. Replications: If "partial ordering" is available (knowing groups of labels belong to groups of inputs), accuracy improves significantly by reducing the search space.

Experimental Results and Consistency

The authors evaluated these estimators on synthetic data, standard benchmarks (e.g., UCI repository), and a biological case study on Aptamer evolution.

A key finding is the consistency of the SM estimator. As shown in the figure below, while the LS estimator ($w_{LS}$) remains stuck with a high relative error due to sorting bias, the SM estimator ($w_{SM}$) converges toward the performance of the Ordinary Least Squares ($w_{OLS}$) baseline as the number of data points $n$ increases.

Relative error of estimators as a function of the number of data points $n$. The SM estimator ($w_{SM}$) converges toward the OLS baseline, while the LS estimator ($w_{LS}$) remains biased.

In the Aptamer case study, the shuffled regression framework successfully identified the same DNA motifs as standard regression, recovering 3 of the top 5 motifs. This demonstrates that qualitative scientific inference is possible even without explicit pairing.

Conclusion and Future Directions

This work establishes that linear regression is feasible without complete ordering information. While the current framework assumes a linear model and faces challenges with non-convex loss functions, it provides a robust foundation for population-level data analysis. Future work may extend these techniques to non-linear settings or focus on recovering the original permutation itself.

Summary updated

Abstract

Is it possible to perform linear regression on datasets whose labels are shuffled with respect to the inputs? We explore this question by proposing several estimators that recover the weights of a noisy linear model from labels that are shuffled by an unknown permutation. We show that the analog of the classical least-squares estimator produces inconsistent estimates in this setting, and introduce an estimator based on the self-moments of the input features and labels. We study the regimes in which each estimator excels, and generalize the estimators to the setting where partial ordering information is available in the form of experiments replicated independently. The result is a framework that enables robust inference, as we demonstrate by experiments on both synthetic and standard datasets, where we are able to recover approximate weights using only shuffled labels. Our work demonstrates that linear regression in the absence of complete ordering information is possible and can be of practical interest, particularly in experiments that characterize populations of particles, such as flow cytometry.
BibTeX
@misc{abid2017linear,
  author = {Abubakar Abid and Ada S. Y. Poon and James Zou},
  title = {{Linear Regression with Shuffled Labels}},
  year = {2017},
  eprint = {1705.01342},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1705.01342},
}

Loading related content...

Figure