SIGCOMM 2023 | Veritas: 通过视频流媒体记录进行因果推理

用户1324186

发布于 2023-11-13 17:16:03

4410

发布于 2023-11-13 17:16:03

作者：Purdue University 来源：ACM SIGCOMM '23 论文题目：Veritas: Answering Causal Queries from Video Streaming Traces 论文链接：https://dl.acm.org/doi/pdf/10.1145/3603269.3604828 代码连接：https://github.com/Purdue-ISL/Veritas 内容整理：王柯喻

引言

在目前的视频流媒体的研究中，因果查询通常用来研究不同因素之间的因果关系，这种分析可以帮助视频流媒体服务提供商了解特定因素如何影响用户体验，从而优化服务。但在实际场景中，很难进行完全随机的实验来确定不同因素之间的因果关系，特别是当涉及到网络性能、用户行为和视频质量等复杂因素时。本文提出了 Veritas 框架，该框架利用现有的记录数据，因果推理和反事实查询，来推断不同设计选择（不同的 ABR 算法、ABR 算法中新的视频质量选项等）对视频流媒体性能的影响，因此，Veritas 框架能通过不同的设计来推断对视频流媒体性能的影响，有助于改善视频流媒体服务的高效性和稳定性。

挑战

在视频流媒体的因果推理中，具有诸多限制因素与技术挑战如：

传统机器学习具有局限性。如神经网络和决策树仅仅判断了已收集数据的相关性，限制了它们只能进行关联性预测，不满足因果推理的要求。
存在混淆因素。ABR算法决策依赖于网络条件。由于其自适应性质，会话期间遇到的网络条件会作为潜在的混淆变量，导致数据中出现复杂的伪相关关系。
级联效应。不同 video chunk、bitrate 的选择会对缓冲区占用、比特率选择以及未来块的下载产生级联影响。

面对上述挑战，本文提出了 Veritas 框架，Veritas 是一种用于视频流媒体中因果推理的新型框架。与复杂的机器学习模型或 RTC （随机对照实验）不同，Veritas 仅依赖于简单易懂的机器学习模型，并且只需要预录制的数据。

Veritas框架

视频流中的因果关系

图1 视频流中的因果图

上图为描述视频流中因果依赖关系的有向无环图，这些变量之间的因果依赖关系可以总结如下：

𝐶𝑡 是在时间区间 ( (𝑡 − 1)𝛿, 𝑡𝛿] 内的平均 INB (内在网络带宽）。
𝐵𝑡（缓冲区量）表示视频播放器中的缓冲区大小。它受到先前块的下载时间和缓冲区状态的影响。
𝑊𝑡（TCP状态）包括 cwdn（拥塞窗口）、RTT（往返时延）和 min RTT 等参数，影响数据传输的稳定性和速度。
𝑆𝑛（块大小）影响下载时间 𝐷𝑛，它受到前一块的观察到的吞吐量和缓冲区状态的影响。
𝐷𝑛（下载时间）表示第 𝑛 块的下载时间，受到块大小 𝑆𝑛 的影响。
𝑌𝑛（观察到的吞吐量）是在下载期间观察到的数据传输速率，可以通过块大小 𝑆𝑛 和下载时间 𝐷𝑛 计算得到。

s_{n}/e_{n}

(块开始/结束下载的时间):

𝑠_{𝑛} ∈\{1, . . . ,𝑇\}

同时

e_{𝑛} ∈\{s_{𝑛}, . . . ,𝑇\}

处理绑架问题

绑架问题

绑架问题是因果推理中的关键概念，它使我们能够在观察到的结果和潜在原因之间建立因果关系，帮助我们理解和解释现实世界中的复杂现象。

处理方法

在处理绑架问题(abduction)时，主要包括两方面的要求：（1）推断潜在变量：推断一组与观察结果一致的潜在变量，这些潜在变量能反映视频会话中的内在随机过程。（2）对提出的变化建模：通过之前推断的潜在变量，对提出的改变建模，从而回答提出的what-if 问题（因果推理）。
而Veritas框架的关键点在于: （1）选择一组能简化因果问题的潜在变量（在数据块开始传输时的TCP参数与状态）通过视频流的因果依赖图，

C_{1：T}

能直接或间接影响所有其他变量，但不受其他变量的影响。因此

C_{1:T}

作为一组混淆变量，可以通过推断其值来回答提出的因果查询：

C_{1：T} ∼ P (C_{1：T}= c_{1:T} |⟨All\quad Observed\quad Variables⟩) \quad（1）

其中 𝐶 ∼ 𝑃 (𝐶 = 𝑐|𝐻 = ℎ) 表示在 H=h 的条件下，按其分布抽取 C 的值。然后对提出改变进行建模，在这些样本上模拟因果查询的影响。（2）高阶嵌入隐藏马尔可夫模型（HoEHMM）：该模型将潜在的随机过程（TCP稳定时可实现的内在带宽）与实际观察值相关联。

HoEHMM模型：

HoEMHH主要特点以及创新部分

变量维度高阶隐藏状态：HoEHMM包含一组变量的高阶隐藏状态，包括

{(𝐶_{(𝑠_{𝑛}:𝑠_{𝑛+1}−1)} , 𝐵_{𝑠𝑛} , 𝑆_{𝑛},𝑊_{𝑠_{𝑛}} )}^{𝑁}_{ 𝑛=1}

，其中可以通过观察测量得到 B、S、W 来简化模型。

扩展 HMMs：传统的 HMMs （马尔可夫模型）通常要求发射变量只依赖于单个隐藏变量，但在 HoEMHH 中，每个 INB 状态(

C_{t}

)依赖于多个观察变量。

d-separation：HoEHMM 通过 d -分离（在图中路径上引入隔离变量）来处理变量之间的复杂依赖关系。
模型简化：HoEHMM 仅观察在块下载时相关的隐藏状态，即𝐵𝑡、𝑆𝑛和𝑊𝑡。这些观察结果帮助降低了模型的复杂性。
Emission process（生成观测值的概率分布函数）：与传统的HMMs（分布函数为多项式、高斯函数）不同，HoEHMM 使用特定于领域的模型来描述观察结果如何从隐藏状态生成，这样可以更好地捕捉视频流媒体中的特定特性。

估计隐藏状态

图2 状态转移分布图

由于其他变量可观测，故只需求取状态转移时的概率分布来推断潜在变量，即

P(𝐶_{(𝑠_{𝑛+1}−1):𝑠_{𝑛}} |𝐶_{(𝑠_{𝑛} −1):𝑠_{𝑛−1}} )

。本文选取一阶时间齐次的马尔可夫过程，即考虑

𝑃 (𝐶_{𝑡+1} |𝐶_{1:𝑡}) = 𝑃 (𝐶_{𝑡+1} |𝐶_{𝑡}), 1 ≤ 𝑡 ≤ T

作为转移概率。而对于

𝑡 ∈ {1, . . . ,𝑇 }

，不再建模

𝑃 (𝐶_{𝑡+1} |𝐶_{𝑡})

，而是建模转移概率

𝑃(𝐶𝑠_{𝑛}|𝐶𝑠_{𝑛−1})

。对于不同的数据块，定义了

𝑃(𝐶_{𝑠𝑛}=𝑗\epsilon |𝐶_{𝑠_{𝑛−1}} = 𝑖\epsilon) = (𝐴^{\Delta n})_{𝑖,𝑗}

，其中 Δ𝑛 =

𝑠_{n}

−

𝑠_{n-1}

为状态转移矩阵（如下所示）。

HoEHMM的状态转移矩阵

转移矩阵

中

A_{i,j}

由参数

{\theta}

定义，具体公式如（2）所示。其中

\theta^2

是通过学习得到的高斯分布的方差，

\eta

是一个平滑度参数(实验中本文固定为0.05),

Z_{i}

是保证

\Sigma_{j}A_{i,j}=1

的归一化因子。

A_{i,j}\quad(\theta)=\frac{1-\eta}{Z_{i}}e^{-\frac{(j-i)^{2}}{\theta^{2}}}+\eta \quad (2)

生成概率分布函数

模型首先使用 INB,

𝐶_{𝑠_{𝑛}:𝑒_{𝑛}}

和

W^{minRTT}_{𝑠_{𝑛}}

计算带宽延迟乘积（BDP）。在生成观测值时：

W^{minRTT}_{𝑠_{𝑛}}

和 𝑆𝑛 均大于 BDP，则 𝑌𝑛 接近于 INB。

W^{minRTT}_{𝑠_{𝑛}}

较大， 𝑆𝑛 小于 BDP，则 TCP 连接受到限制，此时 𝑌𝑛 接近于

\frac{S}{W^{minRTT}_{𝑠_{𝑛}}}

。

当吞吐量受到拥塞窗口限制（

W^{minRTT}_{𝑠_{𝑛}}

小于 BDP）时，计算传输大小为𝑆𝑛 所需的传输轮次，并使用传输轮次、

W^{minRTT}_{𝑠_{𝑛}}

和 𝑆𝑛 估算 𝑌𝑛。

该模型

用于估算通过给定输入缓冲（INB）、TCP 状态和相关下载块的大小时的吞吐量（Yn）。

𝑃(𝑌_{𝑛}=𝑦|𝑊_{𝑠𝑛},𝑆_{𝑛},𝐶_{𝑠_{𝑛}:𝑒_{𝑛}})=1 \{𝑦=𝑓( 𝐶_{𝑠_{𝑛}:𝑒_{𝑛}},𝑊_{𝑠𝑛},𝑆_{𝑛}) \} \quad (3)

其中

1\{\}

为指示函数(当括号内的条件成立时返回1，否则返回0)。为了考虑不确定性，本文引入了高斯白噪声，在实验中，对于会话开始阶段的前几个数据块，使用了更高的方差，以模拟 TCP 连接在开始时的慢启动效应。具体如下：

图3 概率分布函数

而模型中的 𝑓 作为 Veritas 的一个超参数，可以根据特定的 TCP 算法细节灵活调整，以及可以考虑更多的 TCP 状态信息（例如 ssthresh、上次丢包事件的时间等）。本文提供了

的估计器

的伪代码：

图4 估计器的伪代码

抽样与推断

当参数学习完成后，Veritas 根据这些参数对

𝐶_{1:𝑇}

抽样来进行推断。根据方程（1）中的后验概率使用传统的贝叶斯抽样方法来抽样

𝐶_{1:𝑇}

。其中（1）中的联合概率需要计算

𝑃(𝐶_{𝑠𝑛} = 𝑖\epsilon,𝐶_{𝑠_{𝑛+1}} = 𝑗\epsilon | 𝑌_{1:𝑁} ,𝑊_{𝑠_{1:𝑁}} \quad, 𝑆_{1:𝑁} )

，它分为两个步骤，具体算法见论文附录。

首先抽样

𝐶_{𝑠_{1}:N}

。

然后根据基于块样本

𝐶_{𝑠_{1}:N}

的转移矩阵 𝐴 来抽样中间值 𝐶𝑡，其中

𝑡 ∈∪^𝑁_{n=2}\{𝑠_{𝑛−1} + 1, 𝑠_{𝑛} − 1\}

。根据需要，可以在时间 𝑇 之后抽样 INB 值。

Veritas 工作流程

图5 Veritas 工作流程图

如图5所示，部署的系统生产 setting A 包括每个块的(𝑆𝑛、

s_{n}/e_{n}

、cwdn、minRTT等），传输到 Veritas 中进行抽样与推断，再使用抽样的 INB 轨迹

𝐶_{1:𝑇}

，在新的 setting B（对应不同的算法或者缓冲区大小）进行视频会话，Veritas 的模拟为反事实查询提供了 𝐾 个结果，确定了在给定观察数据的情况下推断步骤中固有的不确定性。

实验

通过两组实验来评估 Veritas 回答各种假设性问题的能力：

模拟实验：比较 Veritas 的预测与实际情况。这些实验可以回答各种假设性问题（视频质量、缓冲区大小和自适应比特率（ABR）算法的变化），还允许评估反事实问题（如在trace 完全相同时存在替代配置）。
现实世界实验：在这组实验中，使用 Veritas 来预测由 Puffer 收集的现实视频会话日志上的假设性问题的结果。这里，对于反事实查询，真实情况不可用，但数据集允许对干预查询进行评估（即，关于具有相似特征的会话的预测），尽管只能验证涉及 ABR 算法变化的一类查询。

比较对象

Ground Truth（真实数据）：使用模拟的真实网络带宽（INB）的度量数据作为理想标准。
Baseline（基线）：使用每个视频块下载期间观察到的吞吐量来估计 INB。在非下载期间，使用前后两个视频块的吞吐量进行线性插值。（不考虑未观察到的混杂因素）
CausalSim：利用传统机器学习进行因果推理的方法，需要使用随机对照试验（RCT）获得的训练数据，会随机将会话分配给 K 个 ABR 算法。

训练和参数设置：

CausalSim训练：使用来自两种不同ABR算法的RCT训练数据，以评估在Setting B中目标算法的性能。
Veritas训练：使用 Setting A 中的视频日志数据，采用本文的 HoEHMM 模型。本文使用本地梯度下降算法来优化 HoEHMM 模型。在实验中使用不同的 INB 量化值（0.05、0.5、1 Mbps）和时间步长（1、5秒）。在构建 HoEHMM 的转移矩阵时，假设最大容量是观察到的会话中的吞吐量最大值的1.5倍。
使用 FCC(美国联邦通信委员会) 的数据吞吐量来模拟视频播放，包括 TCP CUBIC 协议和 80ms 的端到端时延。
FCC 数据的带宽在 1 Mbps 到 5 Mbps 之间变化，这个范围通常用于非常规比特率调整。

评估标准

SSIM（结构相似度）、rebuffering ratios（重缓冲率）、buffer occupancy distribution、chunk download times distribution

实验结果

与 baseline 对比

图6 与 baseline 对比结果

可以明显看出，Veritas 的样本轨迹比 Baseline 更接近INB，特别是在ABR算法选择较小块时 baseline 的估计更为保守。

改变视频质量

图7 改变视频质量的对比结果

Veritas 在所有指标上都优于其他方法，且可以观察出 baseline 预测的 Buffer 较低、Rebuf ratio 较高、SSIM 较低，这是因为 Baseline 使用观察到的吞吐量一般较为保守。而 CausalSim 预测的 SSIM 更高、Rebuf ratio 更低、Buffer 更低，是由于 CausalSim 的训练数据主要包含低质量视频，而在预测高质量视频时，会出现预测范围不够的情况。突显了使用机器学习进行反事实查询预测的局限性。