Optimal Strategies for Matching and Retrieval Problems by Comparing Covariates
This work addresses retrieval problems in scenarios with noisy covariate recognition, but it appears incremental as it focuses on optimizing existing covariate-based methods rather than introducing a new paradigm.
The paper tackles the problem of retrieval based on matching covariates when covariate recognition is inaccurate, analyzing optimal strategies for various retrieval tasks and verifying the analytical results through experiments.
In many retrieval problems, where we must retrieve one or more entries from a gallery in response to a probe, it is common practice to learn to do by directly comparing the probe and gallery entries to one another. In many situations the gallery and probe have common covariates -- external variables that are common to both. In principle it is possible to perform the retrieval based merely on these covariates. The process, however, becomes gated by our ability to recognize the covariates for the probe and gallery entries correctly. In this paper we analyze optimal strategies for retrieval based only on matching covariates, when the recognition of the covariates is itself inaccurate. We investigate multiple problems: recovering one item from a gallery of $N$ entries, matching pairs of instances, and retrieval from large collections. We verify our analytical formulae through experiments to verify their correctness in practical settings.