# Regularization for Shuffled Data Problems via Exponential Family Priors on the Permutation Group

arXiv: https://arxiv.org/abs/2111.01767 · HTML: https://mlsanity.com/paper/2111.01767/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 81 references that are in the map.
- First posted on arXiv 2 Nov 2021.

## Builds on (most cited first, 23 of 23)

- [Unsupervised Alignment of Embeddings with Wasserstein Procrustes](https://mlsanity.com/paper/1805.11222/) (2018)
- [Oops I Took A Gradient: Scalable Sampling for Discrete Distributions](https://mlsanity.com/paper/2102.04509/) (2021)
- [(Almost) All of Entity Resolution](https://mlsanity.com/paper/2008.04443/) (2020)
- [Linear Regression with Sparsely Permuted Data](https://mlsanity.com/paper/1710.06030/) (2017)
- [Linear regression without correspondence](https://mlsanity.com/paper/1705.07048/) (2017)
- [Uncoupled isotonic regression via minimum Wasserstein deconvolution](https://mlsanity.com/paper/1806.10648/) (2018)
- [A Two-Stage Approach to Multivariate Linear Regression with Sparsely Mismatched Data](https://mlsanity.com/paper/1907.07148/) (2019)
- [Denoising Linear Models with Permuted Data](https://mlsanity.com/paper/1704.07461/) (2017)
- [Linear Regression with Shuffled Labels](https://mlsanity.com/paper/1705.01342/) (2017)
- [Linear Regression without Correspondences via Concave Minimization](https://mlsanity.com/paper/2003.07706/) (2020)
- [Optimal Rates of Statistical Seriation](https://mlsanity.com/paper/1607.02435/) (2016)
- [Optimal Permutation Recovery in Permuted Monotone Matrix Model](https://mlsanity.com/paper/1911.10604/) (2019)
- [A Pseudo-Likelihood Approach to Linear Regression with Partially Shuffled Data](https://mlsanity.com/paper/1910.01623/) (2019)
- [Spherical Regression under Mismatch Corruption with Application to Automated Knowledge Translation](https://mlsanity.com/paper/1810.05679/) (2018)
- [Learning relationships between data obtained independently](https://mlsanity.com/paper/1601.00504/) (2016)
- [The Benefits of Diversity: Permutation Recovery in Unlabeled Sensing from Multiple Measurement Vectors](https://mlsanity.com/paper/1909.02496/) (2019)
- [Scaling Bayesian Probabilistic Record Linkage with Post-Hoc Blocking: An Application to the California Great Registers](https://mlsanity.com/paper/1905.05337/) (2019)
- [Stochastic EM for Shuffled Linear Regression](https://mlsanity.com/paper/1804.00681/) (2018)
- [An algebraic-geometric approach for linear regression without correspondences](https://mlsanity.com/paper/1810.05440/) (2018)
- [Unlinked monotone regression](https://mlsanity.com/paper/2007.00830/) (2020)
- [Estimation in exponential family Regression based on linked data contaminated by mismatch error](https://mlsanity.com/paper/2010.00181/) (2020)
- [New Directions in Anonymization: Permutation Paradigm, Verifiability by Subjects and Intruders, Transparency to Users](https://mlsanity.com/paper/1501.04186/) (2015)
- [Multiview Sensing With Unknown Permutations: An Optimal Transport Approach](https://mlsanity.com/paper/2103.07458/) (2021)

## Built on by (most cited first, 1 of 1)

- [Alternating minimization algorithm with initialization analysis for r-local and k-sparse unlabeled sensing](https://mlsanity.com/paper/2211.07621/) (2022)

## Abstract (arXiv)

In the analysis of data sets consisting of (X, Y)-pairs, a tacit assumption is that each pair corresponds to the same observation unit. If, however, such pairs are obtained via record linkage of two files, this assumption can be violated as a result of mismatch error rooting, for example, in the lack of reliable identifiers in the two files. Recently, there has been a surge of interest in this setting under the term "Shuffled data" in which the underlying correct pairing of (X, Y)-pairs is represented via an unknown index permutation. Explicit modeling of the permutation tends to be associated with substantial overfitting, prompting the need for suitable methods of regularization. In this paper, we propose a flexible exponential family prior on the permutation group for this purpose that can be used to integrate various structures such as sparse and locally constrained shuffling. This prior turns out to be conjugate for canonical shuffled data problems in which the likelihood conditional on a fixed permutation can be expressed as product over the corresponding (X,Y)-pairs. Inference is based on the EM algorithm in which the intractable E-step is approximated by the Fisher-Yates algorithm. The M-step is shown to admit a significant reduction from n2 to n terms if the likelihood of (X,Y)-pairs has exponential family form as in the case of generalized linear models. Comparisons on synthetic and real data show that the proposed approach compares favorably to competing methods.