Search papers, labs, and topics across Lattice.
This paper introduces an active learning algorithm for recovering a latent ordering of items from noisy pairwise similarity measurements, modeled as a permuted Robinson matrix. The algorithm adaptively queries pairwise similarities based on partial information about the ordering. The authors provide theoretical guarantees, demonstrating that the algorithm recovers the latent ordering with high probability and near-optimal sample complexity under a uniform separation condition.
Provable guarantees for active seriation offer a sample-efficient route to ordering recovery from noisy pairwise comparisons.
Active seriation aims at recovering an unknown ordering of $n$ items by adaptively querying pairwise similarities. The observations are noisy measurements of entries of an underlying $n$ x $n$ permuted Robinson matrix, whose permutation encodes the latent ordering. The framework allows the algorithm to start with partial information on the latent ordering, including seriation from scratch as a special case. We propose an active seriation algorithm that provably recovers the latent ordering with high probability. Under a uniform separation condition on the similarity matrix, optimal performance guarantees are established, both in terms of the probability of error and the number of observations required for successful recovery.
