Active Learning for Nonparametric Choice Models

• 成果类型: Article; Early Access
• 署名作者: Susan, Fransisca; Golrezaei, Negin; Emamjomeh-Zadeh, Ehsan; Kempe, David
• 署名单位: Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); University of Southern California
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.0397
• 发表日期: 2025-11-07
• 关键词: Active learning; nonparametric choice models; preference learning; directed acyclic graphs (DAGs); Identifiability; polynomial-time algorithms; consumer response; ASSORTMENT

摘要

We study the problem of actively learning a nonparametric choice model based on consumers' decisions. We present a negative result showing that such choice models may not be identifiable. To overcome the identifiability problem, we introduce a directed acyclic graph (DAG) representation of the choice model. This representation provably encodes all the information about the choice model that can be inferred from the available data, in the sense that it permits computing all choice probabilities. We establish that, given exact choice probabilities for a collection of item sets, one can reconstruct the DAG. However, attempting to extend this methodology to estimate the DAG from noisy choice frequency data obtained during an active learning process leads to inaccuracies. To address this challenge, we present an inclusion-exclusion approach that effectively manages error propagation across DAG levels, leading to a more accurate estimate of the DAG. Utilizing this technique, our algorithm estimates the DAG representation of an underlying nonparametric choice model. The algorithm operates efficiently (in polynomial time) when the set of frequent rankings is drawn uniformly at random. It learns the distribution over the most popular items among frequent preference types by actively and repeatedly offering assortments of items and observing the chosen item. We demonstrate that our algorithm more effectively recovers a set of frequent preferences on both synthetic and publicly available data sets on consumers' preferences compared with corresponding nonactive learning estimation algorithms. These findings underscore the value of our algorithm and the broader applicability of active-learning approaches in modeling consumer behavior.