Extending Causal Metamodeling to a non-Markovian Queue

技术摘要：将因果元建模扩展至非马尔可夫队列

问题陈述
离散事件模拟元建模通过近似复杂的模拟行为，以实现快速预测和优化，这一能力对于“数字孪生”应用至关重要。模块化动态贝叶斯网络（MDBN）此前已被引入作为一类因果元模型，能够从单个训练好的模型中回答丰富的概率和因果查询（PCQ）。然而，先前的 MDBN 实现仅限于马尔可夫系统（如 M/M/1 队列），即未来状态仅取决于当前状态。现实世界的系统通常采用一般性（非马尔可夫）的到达间隔或服务时间分布（如 Gamma、Weibull、Beta 分布），这些分布违反了马尔可夫性质。在这些非马尔可夫设置中，系统具有记忆性（例如，距离下一次服务完成还剩多少时间取决于当前服务已经进行了多久），这使得标准的两时刻切片 MDBN 结构不足以进行准确建模。

方法论
本文启动了将 MDBN 扩展至非马尔可夫队列的研究，特别侧重于 G/M/1 队列（一般到达间隔，指数服务）。所提出的方法通过三种主要的数学机制解决了由于失去马尔可夫性质带来的问题：

1. 相态近似（Phase-Type Approximation）： 为了恢复 MDBN 所需的马尔可夫结构，使用相态分布来近似一般性（非马尔可夫）的到达间隔分布。具体而言，作者采用广义埃尔朗分布（GED）来建模到达间隔时间，将其视为一系列指数阶段的序列。这使得系统可以通过增加一个追踪到达过程当前阶段的相位变量 $S$ 来表示为一个连续时间马尔可夫链（CTMC）。

   • 对于 Gamma 分布，使用一种匹配前两个矩的闭式 GED 构建方法。
   • 对于 Weibull 和 Beta 分布，采用矩匹配法，通过求解非线性方程或优化问题来最小化 Jensen-Shannon 散度，从而确定相位速率。

2. 增强型 MDBN 结构： 对 MDBN 进行修改，使其除了队列长度 $L$ 之外还包含相位变量 $S$。定义转换动力学，使 $S(j+1)$ 取决于 $S(j)$ 和分布参数，而 $L(j+1)$ 取决于 $L(j)$、$S(j)$ 以及服务率 $\mu$。这恢复了 MDBN 推理所需的两时刻切片依赖结构。

3. 高效学习与参数选择：

   • 最优采样间隔： 不同于以往工作中经验性调整采样间隔 $\delta$ 的做法，本文利用 CTMC 离散化理论推导出了 $\delta_{optimal}$。选择该间隔是为了确保生成的离散时间转换矩阵是有效且有界的，同时最小化整个参数空间内无穷小生成矩阵 $Q$ 的最大对角元素。
   • 参数外推（Parameter Extrapolation）： 为了解决高维状态空间下条件概率分布（CPD）估计的扩展性挑战，作者引入了“参数外推”技术。观察到当 $L(j) = \ell$ 时，队列长度转换的分布近似为 $L(j) = \ell-1$ 时分布的平移版本，该方法汇总了 $\ell > 1$ 时的观测数据。通过学习单个分布并进行平移，来填充更高队列长度的 CPD 条目，从而显著减少了需要估计的参数数量并提高了数据效率。

核心贡献
本文对模拟元建模领域做出了三项创新贡献：

1. 结构扩展： 描述了对 MDBN 的结构性修改，使其能够在保持可处理推理的同时，适应非马尔可夫队列增加的状态复杂度。
2. 学习效率： 提出了提高 CPD 学习效率的方法，包括有效的相态近似、新颖的“参数外推”技术，以及具有理论依据的最优采样间隔选择方法。
3. 实证验证： 提供了首个将因果图模型技术应用于非马尔可夫模拟元建模的应用，证明了 MDBN 可以为 G/M/1 队列产生准确的 PCQ 答案。

实验结果
作者在采用 Gamma、Weibull 和 Beta 到达间隔分布的 G/M/1 队列上评估了扩展后的 MDBN。评估过程涉及 500 个 PCQ，包括条件查询、参数干预查询和队列长度干预查询。基准真相是通过每个查询进行 50,000 次蒙特卡洛重复实验建立的。

• 准确性： MDBN 在所有分布下均能产生准确的答案。Weibull/M/1 队列表现最佳（平均 Jensen-Shannon 距离 [JSD] = 0.166），而 Beta/M/1 队列由于近似其有界支撑集的复杂性，更具挑战性（平均 JSD = 0.236）。统计量（平均队列长度和四分位距）紧密追踪基准值，平均绝对误差（MAE）通常低于 1.3。
• 效率： 最显著的结果是推理速度的提升。MDBN 的推理时间比直接蒙特卡洛模拟快约四个数量级（例如，每个查询约 0.05 秒 vs. 600–1600 秒）。即使通过并行化模拟，MDBN 仍至少快一个数量级。

意义与主张
本文声称提供了首个针对非马尔可夫系统的因果元建模技术。通过成功地将 MDBN 扩展到 G/M/1 场景，作者证明了“相位法”（method of phases）可以弥合因果图模型的理论要求与非马尔可夫模拟的实际需求之间的差距。这项工作确立了在非马尔可夫语境下平衡元建模准确性与可处理性的可能性，为那些传统模拟过于缓慢、无法进行迭代决策的系统提供了一种快速进行“假设分析”和优化的工具。文中提到的技术被认为适用于更广泛的 G/G/1 类队列，这为未来建模更复杂的非马尔可夫系统指明了路径。