RUMBoost: 梯度提升的随机效用模型
内容提要
本文综述随机效用模型（RUMs）的多项研究：提出基于贝叶斯实验设计的GRUMs偏好引导方案与MAP推断算法，并证明一类GRUMs似然函数的单峰性；构建带特征的广义RUM以生成不完整偏好；提出RBCML框架学习RUMs并刻画其严格对数凹性与一致性条件；给出拟合RUMs的多项式时间算法；并将RUMs应用于非合作博弈建模、uplift建模的GBDT改进、基于PAC学习的新学习算法、决策桩集成及结合领域知识的可解释离散选择框架。
延伸解读
从理论保证到实用算法
文章梳理的多个工作不仅提出模型，还关注可计算性与统计性质。例如，有研究证明一类GRUMs似然函数的单峰性，为MAP推断提供优化基础；另有工作刻画RBCML目标函数严格对数凹性的条件，并给出一致性与渐近正态的充要条件。这些理论结果降低了实际拟合RUMs时对算法收敛性和估计可靠性的担忧，也解释了为何部分方法能在合成数据上取得更好的统计与计算效率。
偏好数据不完整时的建模思路
针对带特征的RUMs，文章提到一种广义模型用于生成不完整的偏好，并证明在带特征的Plackett-Luce模型可识别时最大似然估计一致。这提示读者：当选择数据存在缺失或仅观察到部分排序时，不应简单丢弃，而可借助带特征的RUM框架进行建模。不过，该结论依赖可识别性条件，实际应用前需确认数据是否满足相应假设，否则一致性保证可能不成立。
RUMs跨场景应用的共同线索
文章列举的应用覆盖非合作博弈建模、uplift建模的GBDT改进、基于PAC学习的新学习算法、决策桩集成以及结合领域知识的可解释离散选择框架。这些场景的共同点是将用户选择或交互视为由效用驱动的结果，并借助RUMs的结构提升预测或解释能力。读者可据此判断：若任务涉及个体在备选项间的偏好或激励响应，RUMs可能提供比通用黑箱模型更贴合问题机制的建模范式。
Q&A
GRUMs的偏好引导方案有哪些？分别适用于什么场景？
基于贝叶斯实验设计提出了两种GRUMs的偏好引导方案：一种适用于社会选择，另一种适用于个性化选择。
RBCML框架是用来做什么的？它有什么理论保证？
RBCML是一个基于排名打破的复合边际似然框架，用于学习随机效用模型（包括Plackett-Luce模型）。它表征了目标函数为严格对数凹性的条件，并给出了满足一致性和渐近正态的必要充分条件。
拟合随机效用模型到用户选择问题有什么高效算法？
提出了一种基于线性规划和椭球法的多项式时间算法，可以得到可行的近似分离规则解决方案，该问题可视为超图的加权反馈弧集问题的一般化。
如何将随机效用模型应用于非合作博弈建模？
使用鲁棒的参数效用学习框架，将用户交互建模为非合作博弈，并通过集成方法扩展来提高预测性能。在鼓励用户节能行为的社交游戏实验中表现出良好性能。
UTBoost是什么？它解决了 uplift modeling 中的什么问题？
UTBoost是一个针对 uplift modeling 具体设计的树提升系统。它通过创新GBDT算法的两种方法（序贯学习和克服反事实性）来优化资源分配、最大化整体回报，并在大规模数据集上验证了有效性。
基于PAC学习的RUM新学习算法有什么特点？
该算法使用分层消除和基于两两相对比较的临界统计值进行训练，可以在O(n/(c^2ε^2) log(k/δ))轮内识别出一个具有ε优异度的项，其中c是RUM对项参数差距的敏感度。
