论文标题
学习两个多项式逻辑的任意混合物
Learning an arbitrary mixture of two multinomial logits
论文作者
论文摘要
在本文中，我们考虑了多项式逻辑模型（MNL）的混合物，这些混合物已知$ε$ - 对任何随机效用模型的敏感性。尽管历史悠久和广泛使用，但严格的结果仅用于学习两个MNL的均匀混合物。继续进行这一研究，我们研究了学习两个MNL的任意混合物的问题。我们表明，混合模型的可识别性可能只能在多种措施的代数种类上失败。这是通过减少学习两个MNL的混合物到解决单变四分之一方程系统的问题的问题来完成的。我们还设计了一种算法，以使用多项式数量的样品和线性数量的查询来学习两个MNL的混合物，前提是在某些有限的宇宙上有两个MNL的混合物是可识别的。还提出了一些数值实验和猜想。
In this paper, we consider mixtures of multinomial logistic models (MNL), which are known to $ε$-approximate any random utility model. Despite its long history and broad use, rigorous results are only available for learning a uniform mixture of two MNLs. Continuing this line of research, we study the problem of learning an arbitrary mixture of two MNLs. We show that the identifiability of the mixture models may only fail on an algebraic variety of a negligible measure. This is done by reducing the problem of learning a mixture of two MNLs to the problem of solving a system of univariate quartic equations. We also devise an algorithm to learn any mixture of two MNLs using a polynomial number of samples and a linear number of queries, provided that a mixture of two MNLs over some finite universe is identifiable. Several numerical experiments and conjectures are also presented.
