主动排序算法高效恢复物品顺序，有理论保证。
Active Seriation: Efficient Ordering Recovery with Statistical Guarantees
- 自适应查询成对相似性，逐步逼近真实排序。
- 在相似度矩阵均匀分离条件下，错误率极低且所需观测数最优。
- 适合需要高可靠性排序的场景，如数据排序与推荐系统。
主动排序旨在通过自适应地查询成对相似性来恢复 $n$ 个物品的未知顺序。观测值是底层 $n \times n$ 置换罗宾逊矩阵中元素的噪声测量，其置换编码了潜在排序。该框架允许算法从部分潜在排序信息开始，包括从零开始排序作为特例。本文提出一种主动排序算法，可在高概率下恢复潜在排序。在相似度矩阵满足均匀分离条件时，建立了最优性能保证，涵盖错误概率和成功恢复所需的观测数量。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。