Efficient and Accurate Top-$K$ Recovery from Choice Data
The intersection of learning to rank and choice modeling is an active area of
research with applications in e-commerce, information retrieval and the social
sciences. In some applications such as recommendation systems, the statistician
is primarily interested in recovering the set of the top ranked items from a
large pool of items as efficiently as possible using passively collected
discrete choice data, i.e., the user picks one item from a set of multiple
items. Motivated by this practical consideration, we propose the choice-based
Borda count algorithm as a fast and accurate ranking algorithm for top
$K$-recovery i.e., correctly identifying all of the top $K$ items. We show that
the choice-based Borda count algorithm has optimal sample complexity for
top-$K$ recovery under a broad class of random utility models. We prove that in
the limit, the choice-based Borda count algorithm produces the same top-$K$
estimate as the commonly used Maximum Likelihood Estimate method but the
former's speed and simplicity brings considerable advantages in practice.
Experiments on both synthetic and real datasets show that the counting
algorithm is competitive with commonly used ranking algorithms in terms of
accuracy while being several orders of magnitude faster.