高效学习多项式逻辑模型权重，10秒理解推荐系统背后的概率选择机制。
Learning Multinomial Logits in $O(n \log n)$ time
- 通过大小为2的查询子集，用自适应/非自适应方法快速估计物品权重
- 自适应算法仅需 $O(n/ε^3 \log n)$ 次查询即可达到误差 $\varepsilon$
- 算法在推荐系统中可实现高精度概率建模，适合大规模排序场景
多项式逻辑（MNL）模型将一组物品 $[n]$ 与正权重关联，每次查询指定一个合法子集（称为展示位），模型按权重比例随机选择一个物品。该模型也被称为Plackett-Luce模型或条件采样预言机。尽管研究广泛，但核心问题仍未解决：给定对展示位的查询访问，如何以多高效的方式学习权重，使得每个展示位上的选择分布与真实分布的总变差距离不超过 $\varepsilon$？本文提出两种算法：一种使用自适应查询，另一种使用非自适应查询。两者均输出一个新模型 $M'$，使得对任意展示位 $S$，其诱导分布 $M'_S$ 与真实分布的总变差距离小于 $\varepsilon$。自适应算法仅需 $O(n/\varepsilon^3 \log n)$ 次查询，非自适应算法需 $O(n^2/\varepsilon^3 \log n \log(n/\varepsilon))$ 次查询。两算法均只使用大小为2的展示位，运行时间与查询复杂度成正比。我们进一步证明，自适应查询下下界为 $\Omega(n/\varepsilon^2 \log n)$，非自适应为 $\Omega(n^2/\varepsilon^2 \log n)$，表明自适应算法在 $n$ 上最优，非自适应算法仅差一个 $\log n$ 因子。
原文摘要 · Abstract (English)
A Multinomial Logit (MNL) model is composed of a finite universe of items $[n]=\{1,..., n\}$, each assigned a positive weight. A query specifies an admissible subset -- called a slate -- and the model chooses one item from that slate with probability proportional to its weight. This query model is also known as the Plackett-Luce model or conditional sampling oracle in the literature. Although MNLs have been studied extensively, a basic computational question remains open: given query access to slates, how efficiently can we learn weights so that, for every slate, the induced choice distribution is within total variation distance $\varepsilon$ of the ground truth? This question is central to MNL learning and has direct implications for modern recommender system interfaces. We provide two algorithms for this task, one with adaptive queries and one with non-adaptive queries. Each algorithm outputs an MNL $M'$ that induces, for each slate $S$, a distribution $M'_S$ on $S$ that is within $\varepsilon$ total variation distance of the true distribution. Our adaptive algorithm makes $O\left(\frac{n}{\varepsilon^{3}}\log n\right)$ queries, while our non-adaptive algorithm makes $O\left(\frac{n^{2}}{\varepsilon^{3}}\log n \log\frac{n}{\varepsilon}\right)$ queries. Both algorithms query only slates of size two and run in time proportional to their query complexity. We complement these upper bounds with lower bounds of $Ω\left(\frac{n}{\varepsilon^{2}}\log n\right)$ for adaptive queries and $Ω\left(\frac{n^{2}}{\varepsilon^{2}}\log n\right)$ for non-adaptive queries, thus proving that our adaptive algorithm is optimal in its dependence on the support size $n$, while the non-adaptive one is tight within a $\log n$ factor.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。