Active Seriation: Efficient Ordering Recovery with Statistical Guarantees

Abstract

We consider the problem of active seriation, where the goal is to recover an unknown ordering of $n$ items based on noisy observations of pairwise similarities. The similarities are assumed to correlate with the underlying ordering: pairs of items that are close in the ordering tend to have higher similarity scores, and vice versa. In the active setting, the learner sequentially selects which item pairs to query and receives noisy similarity measurements. We propose a novel active seriation algorithm that provably recovers the correct ordering with high probability. Furthermore, we provide optimal performance guarantees in terms of both the probability of error and the number of observations required for successful recovery.