基于面板数据的Markov Chain选择模型的估计、预测与分类优化

# 基于面板数据的马尔可夫链选择模型的估计、预测与品类优化  
来源：https://arxiv.org/html/2607.09817  
Yalcin Akcay, Gerardo Berbeglia¹¹footnotemark:1, Young-San Lin¹¹footnotemark:1  

###### 摘要  

我们提出了一个面向面板数据的马尔可夫链（MC）选择模型框架，包括参数估计、个性化选择预测以及个性化品类优化。与假设每笔交易独立地从随机效用模型中抽取的传统设定不同，我们的框架考虑了同一客户在历史数据中交易之间的依赖关系，并通过偏序偏好信息加以刻画。据我们所知，我们的框架首次在MC下开启了面板数据选择建模的研究。作为主要结果，我们通过引入基于偏序的客户偏好信息，提出了新颖的期望最大化（EM）算法用于MC参数估计。在合成数据集和寿司数据集上，我们的EM算法优于Şimşek和Topaloglu（Operations Research, 66, 2018）的传统EM算法以及从Jagabathula和Vulcano（Management Science, 64, 2018）改编的基于多项logit的偏序基准方法。作为次要贡献，我们给出了条件选择预测和品类优化问题的难解性与可计算性结果。这些结果补充了我们的估计框架，并阐明了条件选择和品类优化的计算前景，可能具有独立的研究价值。  

## 1 引言  

将客户选择行为纳入品类规划是收益管理中的核心问题。品类规划的标准路线包括两个关键步骤：选择模型估计和品类优化。在文献中，传统选择模型估计算法通常假设历史数据集中的交易是独立的，而品类优化问题则旨在最大化整个客户群体上的期望收益。这些传统框架的一个关键特征是其对无条件选择概率的依赖——即选择概率在所有客户之间是相同的，且独立于客户特定的交易历史。  

数据采集和电子商务技术的最新进展使得零售商能够在个体客户层面观察到详细的交易历史。这类信息通常被称为**面板数据**，它揭示了同一客户多次交易之间的相关性，从而对经典模型下的独立性假设提出了挑战。这一发展自然引出了以下问题：*能否通过将个体历史交易信息纳入选择模型来更精确地估计客户的选择概率？完成这一任务所需的计算量是多少？* 这些问题以选择模型为前提，并专注于选择概率估计层面的个性化。具体来说，我们研究如何在假设无条件选择概率由一个所有客户共有的底层选择模型控制的前提下，计算基于个体交易历史的条件客户选择概率。直观上，交易历史提供了关于个体偏好的额外信息，因为同一客户的重复选择本质上是相关的。  

从更广泛的角度看，这引出了第二个互补的问题：*能否通过利用个体历史交易信息来改善整个群体的选择模型估计？这种方法在何时更加有利？* 这里，重点从预测转向推断，探讨利用重复客户选择交互中的信息是否能更准确地估计底层选择模型。受这些问题启发，我们针对面板数据下的选择模型估计、条件选择预测和品类优化，发展了理论和实验结果。我们的分析展示了如何系统性地利用个体层面的交易数据来提升品类规划中的预测精度和决策绩效。  

### 1.1 我们的结果  

据我们所知，我们的框架首次在马尔可夫链（MC）选择模型下开启了面板数据选择建模的研究。我们的结果总结如下。  

- • 作为启发性的问题，我们研究了对于哪些选择模型，面板数据能够改善群体层面的估计。主要目标是通过选择最佳参数来最大化给定数据的**似然**。在这里，似然定义为完整观测集独立发生的概率。在传统设定中，每个观测是一笔交易。在面板数据设定中，每个观测是由客户特定历史交易描述的客户特定偏序。在多项logit（MNL）中，选择概率在群体极限下可观测，使用面板数据不会增加MNL参数的识别能力。相反，对于MC，客户层面的信息可以改善模型估计。这一结果凸显了MNL与MC在利用个体交易信息促进选择模型估计方面的差异，从而激励在估计MC时使用面板数据。  
- • 作为我们的主要结果，我们提出了结合客户层面信息来估计MC的期望最大化（EM）算法。EM算法Cus假设每个客户有一个严格潜在的偏好，并旨在最大化每个客户具有特定交易集的似然，这等价地由偏序偏好捕获（Jagabathula and Vulcano 2018 (https://arxiv.org/html/2607.09817#bib.bib25); Jagabathula et al. 2022 (https://arxiv.org/html/2607.09817#bib.bib1)）。混合算法Hyb结合了Cus和传统EM算法（Şimşek and Topaloglu 2018 (https://arxiv.org/html/2607.09817#bib.bib11)），提供了一种实用启发式方法来混合偏好一致的历史与普通的独立交易。这些算法在合成数据集和寿司数据集上（类似于Berbeglia et al. 2022 (https://arxiv.org/html/2607.09817#bib.bib3)的设定）优于用于MC估计的传统EM算法（Şimşek and Topaloglu 2018 (https://arxiv.org/html/2607.09817#bib.bib11)）以及基于偏序启发式的MNL估计基准（Jagabathula and Vulcano 2018 (https://arxiv.org/html/2607.09817#bib.bib25)）。改进不仅体现在客户特定的选择预测上，也体现在群体选择预测上。  
- • 作为次要贡献，我们给出了在MNL或MC下针对特定客户的条件选择概率计算和条件品类优化的计算难解性与可计算性结果。这些结果补充了我们的估计框架，并阐明了MNL和MC下条件选择和品类优化的计算前景。与先前工作（Jagabathula and Vulcano 2018 (https://arxiv.org/html/2607.09817#bib.bib25); Jagabathula et al. 2022 (https://arxiv.org/html/2607.09817#bib.bib1)）考虑**所有**产品上的偏序不同，我们的公式考虑**客户选择的产品**上的偏序。该公式高度依赖MNL或MC的结构，并可能减少计算负担。  

### 1.2 相关文献  

#### 1.2.1 用于选择模型估计的EM算法  

需求或选择模型估计中最常用的度量标准之一是似然度量。在某些特殊情况下，由于对数似然目标的凹性，寻找最优参数在计算上是可行的（McFadden 1974 (https://arxiv.org/html/2607.09817#bib.bib22); van Ryzin and Vulcano 2015 (https://arxiv.org/html/2607.09817#bib.bib30)）。然而，对数似然函数通常缺乏良好结构。标准优化方法可能变得计算密集。解决这种计算负担的常用方法是EM算法（Dempster et al. 1977 (https://arxiv.org/html/2607.09817#bib.bib27)），广泛用于可替代产品的需求审查或选择模型估计（Vulcano et al. 2012 (https://arxiv.org/html/2607.09817#bib.bib29); van Ryzin and Vulcano 2017 (https://arxiv.org/html/2607.09817#bib.bib31); Jagabathula and Rusmevichientong 2017 (https://arxiv.org/html/2607.09817#bib.bib32); Anupindi et al. 1998 (https://arxiv.org/html/2607.09817#bib.bib33); Talluri and van Ryzin 2004 (https://arxiv.org/html/2607.09817#bib.bib8); Kök and Fisher 2007 (https://arxiv.org/html/2607.09817#bib.bib34); Conlon and Mortimer 2013 (https://arxiv.org/html/2607.09817#bib.bib35); Stefanescu 2009 (https://arxiv.org/html/2607.09817#bib.bib36)）。在选择模型估计的范围内，Train (2008 (https://arxiv.org/html/2607.09817#bib.bib28)) 建立了潜在类别MNL和离散混合选择分布的EM算法。潜在类别MNL的EM框架后来被调整用于面板数据设定（Jagabathula and Vulcano 2018 (https://arxiv.org/html/2607.09817#bib.bib25); Jagabathula et al. 2022 (https://arxiv.org/html/2607.09817#bib.bib1)）。Şimşek and Topaloglu (2018 (https://arxiv.org/html/2607.09817#bib.bib11)) 提出了用于MC的EM算法，假设每笔交易独立。我们的框架是Şimşek and Topaloglu (2018 (https://arxiv.org/html/2607.09817#bib.bib11)) 的扩展，利用了同一客户交易之间的相关性，从而改进了MC参数的估计。  

#### 1.2.2 基于面板数据的选择建模与品类规划  

文献中大多数基于面板数据的品类问题都基于多项logit（MNL）模型——MC的一个特例。Chen et al. (2023 (https://arxiv.org/html/2607.09817#bib.bib10)) 考虑了MNL下的多周期品类优化问题，目标是在所有时间周期上最大化期望收益。Jagabathula and Vulcano (2018 (https://arxiv.org/html/2607.09817#bib.bib25)) 开创了基于偏序的客户偏好估计研究，后来被调整用于个性化促销决策（Jagabathula et al. 2022 (https://arxiv.org/html/2607.09817#bib.bib1)）。该框架在MNL下估计基于客户历史交易的条件选择概率，并声称计算精确概率是难解的。我们给出了这一结论的形式化证明，并推导了在MC下计算精确选择概率的闭式表达式。与Jagabathula and Vulcano (2018 (https://arxiv.org/html/2607.09817#bib.bib25); Jagabathula et al. 2022 (https://arxiv.org/html/2607.09817#bib.bib1)) 使用高效启发式方法估计MNL下的选择概率不同，我们专注于在合理规模下对MC进行更细粒度的计算。  

#### 1.2.3 MC选择模型的其他结果  

MC选择模型由Blanchet et al. (2016 (https://arxiv.org/html/2607.09817#bib.bib2)) 开创，他们首次提出了MC下品类优化问题的多项式时间算法。不久后，Feldman and Topaloglu (2017 (https://arxiv.org/html/2607.09817#bib.bib5)) 研究了品类问题的原始和对偶线性规划（LP）性质，以及MC下网络收益管理问题的基于LP的近似方法。MC下的容量受限品类问题是APX-hard的（Désir et al. 2020 (https://arxiv.org/html/2607.09817#bib.bib19)），当MC转移矩阵的秩为常数时，存在完全多项式时间近似方案（FPTAS）（Désir et al. 2022 (https://arxiv.org/html/2607.09817#bib.bib20)）。Désir et al. (2024 (https://arxiv.org/html/2607.09817#bib.bib37)) 开发了MC下鲁棒品类问题的有效算法，目标是在MC参数不确定时最大化最坏情况下的期望收益。Gupta and Hsu (2020 (https://arxiv.org/html/2607.09817#bib.bib39)) 提出了在有限规模品类和无噪声选择概率下识别MC参数的有效算法。Li et al. (2025 (https://arxiv.org/html/2607.09817#bib.bib38)) 提出了MC下动态品类选择问题的在线学习算法，该算法同时涉及在线参数估计和序贯品类决策。  

### 1.3 组织结构  

在第2节 (https://arxiv.org/html/2607.09817#S2) 中，我们介绍面板数据选择建模的基本框架，并介绍MC和MNL。在第3节 (https://arxiv.org/html/2607.09817#S3) 中，我们介绍似然函数以及MNL与MC在利用个体交易信息促进选择模型估计方面的差异。在第4节 (https://arxiv.org/html/2607.09817#S4) 中，我们提出使用面板数据的MC参数估计EM算法。在第5节 (https://arxiv.org/html/2607.09817#S5) 中，我们给出实验结果。在第6节 (https://arxiv.org/html/2607.09817#S6) 中进行总结。在附录A (https://arxiv.org/html/2607.09817#A1) 中，我们给出条件选择预测和条件品类优化的难解性与可计算性结果。  

## 2 预备知识  

在第2.1节 (https://arxiv.org/html/2607.09817#S2.SS1) 中，我们提供面板数据下随机效用模型（RUM）的背景，包括基本设定、基于偏好的线性扩展与有向无环图（DAG）的联系，以及条件选择概率的闭式表达式。在第2.2节 (https://arxiv.org/html/2607.09817#S2.SS2) 中，我们介绍具体的选择模型：马尔可夫链（MC）和多项logit（MNL）。我们通过给出在MC和MNL下观测到特定交易集的概率的闭式表达式来结束本节。  

在RUM中，有\(n\)个可替代产品，记为集合\([n] = \{1,2,\ldots,n\}\)。不购买选项记为产品0。客户对产品\(j\)有随机效用\(u_j \in \mathbb{R}\)，遵循某个底层概率分布。根据RUM的不同，随机效用可能独立或不独立。设\(S \subseteq [n]\)是提供给客户的产品子集。不购买选项始终可用，因此我们使用记号\(S_+ := S \cup \{0\}\)。客户从\(S_+\)中选择效用最高的产品。也就是说，如果\(j = \arg \max_{i \in S_+} \{u_i\}\)，则从\(S_+\)中选择\(j\)。¹¹footnotemark:1我们用\(\pi(j,S)\)表示从\(S_+\)中选择\(j\)的概率。  

### 2.1 基于面板数据的选择建模  

传统研究主要集中在给定RUM类别的选择概率计算、假设每笔交易独立的参数估计，以及在给定RUM参数时的品类优化。我们提出这些问题的变体，其中每笔交易都与特定客户相关联，从而可能捕获同一客户交易之间的相关性。设\(c\)表示一个客户，\([C] = \{1,2,\ldots,C\}\)表示客户集合。设\(k_c\)表示与客户\(c\)相关联的观测交易数量。