您现在的位置是:首页 >学无止境 >CausalSim (NSDI ‘23 Best Paper)论文阅读笔记网站首页学无止境
CausalSim (NSDI ‘23 Best Paper)论文阅读笔记
前言
论文:CausalSim: A Causal Framework for Unbiased Trace-Driven Simulation (NSDI '23)
开源仓库:GitHub - CausalSim/Unbiased-Trace-Driven-Simulation
介绍:
CausalSim是NSDI '23的Best Paper。其主要工作是基于矩阵/张量完成和对抗学习设计了一个无偏的trace-driven模拟框架。CausalSim通过显示建模算法对于trace的影响,消除了传统模拟器中存在的偏差,从而实现与真实世界更为一致的模拟效果。CausalSim可以应用于ABR算法、异构服务器负载均衡等场景之中。
背景及相关资料:
该文章的主要篇幅均以ABR算法[1]为例进行叙述。在ABR算法中,由于码率决策(视频块大小)会对视频块吞吐量产生影响影响[2][3],因此采集现有算法的trace并在传统模拟器(如Pensieve[4]的模拟器)进行回放会引入额外的偏差。为了消除这种影响,CausalSim将视频块吞吐量和底层网络环境进行区分[3],并基于因果模型表征码率和网络环境选择对于吞吐量的影响。CausalSim基于Puffer[2][5]平台及数据集进行了详细的分析和实验验证。
- [1] DASH标准&ABR算法介绍
- [2] Learning in situ: a randomized experiment in video streaming (NSDI '20)
- [3] Lumos: towards Better Video Streaming QoE through Accurate Throughput Prediction (INFOCOM '22)
- [4] Neural Adaptive Video Streaming with Pensieve (SIGCOMM '17)
- [5] Puffer
注:
- 本笔记主要内容是基于原论文的总结、梳理和翻译。原论文内容比较复杂,行文偏晦涩。为了便于读懂,本笔记补充了个人理解和文章内容之外的补充叙述(由“【】”标出)。由于本人对于因果推断、反事实估计、张量完成和对抗学习等相关知识并不熟悉,因此部分内容仅供参考,不保证准确性
- 关于翻译:
- “simulate”统一翻译为“模拟”而非“仿真”,避免与“emulate”(如Mahimahi)混淆
- “trace”和“intervention”不太好在中文中找到合适的对应词汇,因此不作翻译
- “trajectory”翻译为“轨迹”,在本文中其含义与“trace”类似
- 本笔记省略了原论文§6.3及以后的内容
1 Introduction
研究背景概述
背景:基于trace的模拟(trace-driven simulation)
- 优势:相对于全系统模拟(如NS3)更为简便
- 组成:trace + intervention
- trace:在intervention运行过程中采集的数据(如视频块码率、吞吐量等),在模拟中用于表征外部环境变化
- intervention:表征感兴趣的组件(component of interest),如新设计、算法、架构等
问题:在真实系统中,很难保证外源trace假设成立。若该假设不成立,则模拟会产生偏差(bias)
- 外源trace假设(exogenous trace assumption)是过去的trace-driven模拟中存在一个关键假设,即假设intervention不会影响trace数据
- 例子:对于ABR算法而言,通常采集真实视频流的吞吐量作为trace,但trace中的吞吐量受到两方面因素的影响1:
- 底层网络的潜在因素(latent factors):网络路径的瓶颈容量、竞争流量等
- intervention,如算法的决策动作(action):ABR算法的码率选择(对应不同的视频块大小)
解决思路:模拟新intervention时,需要考虑潜在因素和intervention(如算法动作)的影响,并且预测新intervention对于trace的影响
CausalSim介绍
方法:CausalSim,一个用于无偏trace-driven模拟的因果框架
- CausalSim显式建模intervention对trace数据的影响,因此放宽了外部trace假设
- CausalSim基于在一组固定算法下从随机控制试验 (randomized control trial,RCT) 中收集的trace,推断出:
- 潜在因素(latent factors):包含系统底层状况,如网络环境
- 因果模型(causal model):包括潜在因素、算法决策和观察到的trace数据
- 为了消除trace数据中的偏差,CausalSim模拟新算法时分为两步过程:
- (i) 估计每个trace的每个时间步长的潜在因素
- (ii) 基于估计的潜在因素,来预测感兴趣组件(intervention)的trace、动作(action)和观察(observation)变量的交替演变
- 这里的潜在因素与收集trace时的相同
CausalSim的优势:提高了RCT trace的可用性,即可以基于有限的RCT数据来从中学习底层环境的潜在因素,从而帮助评估新算法
- 当intervention可能影响trace数据时,提高了trace-driven模拟的准确性(评估部分以ABR作为案例)
- 当外源trace无法定义时,支持对系统进行trace-driven模拟(评估部分以服务器负载均衡作为案例)
【以Puffer为例,其每个trace都是一个算法在RCT下得到的吞吐量,而非网络本身的可用带宽(即文中所说的潜在因素)】
CausalSim的核心:矩阵/张量完成(matrix / tensor completion)
- 观察:无偏的trace-driven模拟可以被视作矩阵(或张量)完成问题
- 考虑一个traec矩阵M(如果traec的维度更高则为张量),行对应于可能的动作,列对应于traec数据中的不同时间步长。对于每一列,一个动作的条目是“显示的(revealed)”,但其他所有条目(即未被算法执行的动作)都丢失了
- CausalSim的任务可以看作是恢复丢失的条目【即预测新算法采取的新动作(可能未在trace中出现过)对应的条目】
大量的工作表明,在满足关于矩阵和缺失数据模式的某些假设下,有可能从稀疏的观察中恢复矩阵
挑战:矩阵完成的典型假设不完全成立
- 典型假设:(1)矩阵是低秩的(low rank)【可以简单粗暴地理解为包含较多冗余的信息】,(2)显示的条目是随机的,并且(3)显示的条目足够多
- 分析:即便假设(1)广泛存在,但假设(2)(3)在本文的问题中并不成立(§4.3)
- 每列仅有一个条目,低于低秩矩阵完成的信息理论约束(甚至对于秩为1的矩阵而言也不够)
- 在本文的问题中,显示的条目不仅不是随机的,而且取决于矩阵的其他条目,因为行动由基于观察的算法所确定
CausalSim利用了两个关键insight来解决这个挑战:
- 基于外源潜在(latent)假设建立因果模型 (§3):潜在因素是外源(exogenous)的,并且不受intervention的影响
- 外源潜在(latent)假设放宽了标准trace-driven模拟中的外源trace假设
- 例如:网络路径上的瓶颈链路速度等潜在因素不受ABR算法的影响,而ABR决策会影响观察到的轨迹(即视频块吞吐量)
- 基于RTC trace的潜在因素的分布不变性完成矩阵/张量填充
- 由于每个trace对应的算法在RCT中完全随机,对于运行不同算法采集的trace,其潜在因素的分布应该相同,即潜在分布对于不同算法保持不变
- RCT数据需要满足一些条件(如算法的数量和多样性),以基于分布不变性来保证低秩矩阵的可恢复性
- CausalSim使用学习方法(learning method),基于对抗(adversarial)神经网络训练技术利用该分布不变性进行模拟(§5)
评估:
- 场景:ABR、服务器负载均衡
- 数据集及环境:真实世界和合成(synthetic)数据集,并在Puffer视频流测试平台上进行真实场景测试
- baseline(忽略了偏差):专家知识模拟器ExpertSim【类似于Pensieve的模拟器】,标准监督学习模拟器SLSim
- 评价指标:(相对于真实环境的)模拟准确率
- 结果:
- ABR案例研究:使用CausalSim对BOLA12进行调优,基于贝叶斯优化调整BOLA1参数并在Puffer上进行部署,使其达到与BBA相似的质量,但只有其0.7x的卡顿率(相比原版优化了2.6x);作为对比,ExpertSim调优后的BOLA的卡顿率是BBA的1.34x。这表明消除偏差对于从trace-driven模拟中得出准确结论至关重要
- Puffer真实实验:CausalSim预测卡顿率的误差在28%以内,baseline则为49–68%和29–187%;视频质量与缓冲区占用水平也显示出相似的结果
- 服务器负载均衡案例研究:使用合成环境对异构服务器作业负载均衡问题进行建模,CausalSim将平均模拟误差降低5.1x,而baseline的中值误差为124.3%。这表明CausalSim可以将trace-driven模拟应用于外源trace假设失效的系统
本文工作已开源:https://github.com/CausalSim/Unbiased-Trace-Driven-Simulation
2 Motivation
例子:预测BBA的缓冲区占用率
trace-driven模拟的目标:基于不同算法收集的trace(假设其潜在因素分布相同),预测新算法的系统轨迹(trajectory),如缓冲区、码率等
任务:仅使用来自其他(源)算法的trace数据,预测Puffer数据集中BBA(目标算法)的缓冲区占用分布
- 源算法:采集trace时运行的算法;目标算法:模拟的对象
Strawman1: ExpertSim
ExpertSim对每个视频块的缓冲区(buffer)动态进行建模,形如下式:
b
t
+
1
=
max
(
0
,
b
t
−
s
t
c
^
t
)
+
T
b_{t+1}=max(0,b_t-frac{s_t}{hat{c}_t})+T
bt+1=max(0,bt−c^tst)+T
- b t b_t bt:下载第t个视频块前的缓冲区水平
- s t s_t st:第t个视频块的视频块大小
- T T T:视频块时长
- c ^ t hat{c}_t c^t:第t个视频块的吞吐量
【这个建模源自MPC (SIGCOMM '15),并被Pensieve (SIGCOMM '17)的模拟器使用。简单来说就是,在下载每个视频块的过程中,播放缓冲区按照下载时间1:1匀速下降,最低为0(之后就卡顿了);当视频块下载完成后,缓冲区水平增加一个视频块的时长】
ExpertSim依赖于外源trace假设(exogenous trace assumption):假设不同算法的决策不会影响观察到的吞吐量,即对于源算法(BOLA2)和目标算法(BBA)而言, c ^ t hat{c}_t c^t是一样的
Strawman2: SLSim
SLSim使用监督学习来训练神经网络 (NN),对系统动态进行建模
- 网络结构:全连接神经网络,包括2个隐层,每个隐层有128个ReLU激活神经元
- 输入特征:第 t t t个视频块的缓冲区级别 b t b_t bt,吞吐量 c ^ t hat{c}_t c^t,块大小 s t s_t st
- 输出:第 t t t个块的下载时间,以及由此产生的缓冲区级别 b t + 1 b_{t+1} bt+1
训练数据中排除了BBA的trace数据
预测效果
结果:ExpertSim和SLSim与目标算法之间存在偏差
- ExpertSim的预测更接近源算法(BOLA2)的缓冲区占用率分布,但距离目标算法(BBA)的缓冲区占用率分布比较远
- SLSim表现与ExpertSim相似
原因:ABR算法决策会影响视频块的吞吐量(下图),导致外源trace假设失效
解决思路
- 如果trace中已包含网络容量(而非视频块吞吐量)【比如采集可用带宽trace而非吞吐量trace】,则外源trace假设成立
- 否则,需要从观察的吞吐量trace数据中推断出底层网络的潜在因素。具体而言,基于码率、块大小、吞吐量等观察值,估计每个视频块的网络容量
- 推断此类潜在混杂因素(latent confounders)并将其用于反事实预测(counterfactual prediction),是因果推断(causal inference)领域的核心问题【此处反事实预测的大概意思是,预测trace中不存在的动作对应的观测值】
方法:CausalSim,一个用于无偏trace-driven模拟的因果框架
- CausalSim放宽了外源trace假设,显示建模intervention对trace数据的影响,并推断出系统动态的潜在因素和因果模型
- 因此,CausalSim可以在模拟intervention时纠正trace数据中的偏差
- 效果(上文的图):CausalSim能够更准确地匹配BBA的真实分布
总结
过去的simulator依赖于外源trace假设(exogenous trace assumption),忽略了模拟对象对于trace的影响,如下图所示(图中的箭头表示因果关系):
- a a a:模拟的对象,如算法的动作(action)
- o o o:观察到的状态
- u u u:潜在外部状态,不在模拟的范围内
- m m m:采集的trace(变量可以是多维的,并随时间变化)
CausalSim采用外源潜在假设(exogenous latent assumption),考虑了模拟对象对于trace的影响(
a
→
m
a
arr m
a→m)
注:
- a a a和 u u u可以相关(如网络环境变化会导致ABR算法决策变化),但二者之间存在相关性不代表二者存在因果关系
- CasualSim假设 a a a和 u u u之间不存在因果关系,即ABR无法影响网络环境
3 Model and Problem Statement
3.1 因果模型
模型定义
离散时间动态模型(类似于POMDP,即部分可观测马尔可夫决策过程):
m
t
=
F
t
r
a
c
e
(
a
t
,
u
t
)
(1)
ag{1} m_t = mathcal{F}_{trace}(a_t,u_t)
mt=Ftrace(at,ut)(1)
o
t
+
1
=
F
s
y
s
t
e
m
(
o
t
,
m
t
,
a
t
)
(2)
ag{2} o_{t+1} = mathcal{F}_{system}(o_t,m_t,a_t)
ot+1=Fsystem(ot,mt,at)(2)
定义:
- m t m_t mt:trace
- u t u_t ut:潜在因素
- a t a_t at:intervention
- o t o_t ot:观测到的感兴趣组件的状态
- F t r a c e mathcal{F}_{trace} Ftrace:表征intervention对trace的影响(传统方法所忽略的部分)
- F s y s t e m mathcal{F}_{system} Fsystem:表征感兴趣组件的动态
当intervention改变感兴趣的组件中的算法时,可以将 a t a_t at视为该算法在时间t采取的行动(action)
隐含假设:intervention不会影响系统其余部分的内部状态
适用场景
该因果模型适用于trace可能受到intervention影响的任何trace-driven模拟设置,例如
- 作业调度(Job scheduling):在不同类型的机器下模拟工作负载的性能
- trace:作业性能(如runtime)
- intervention:调度决策
- 潜在因素:每个作业的内在属性(如计算强度)或机器的潜在方面,例如并列的干扰工作负载
- 网络模拟(Network simulation):模拟网络设计的某些方面(如拥塞控制、数据包调度、流量工程等)如何影响应用程序性能
- trace:应用程序的流量模式
- intervention:网络设计
- 潜在因素:决定其流量需求的应用程序内部结构
外源trace假设不成立的影响:
- 对于ABR而言,有时可能影响不大,但会得到错误的结论
- 对于异构服务器的作业调度/负载均衡而言,给定特定机器上的作业性能trace,不可能仅仅通过为新机器分配重放trace完成模拟
不适用场景
该因果模型依赖于外源潜在假设,即假设潜在因素不受intervention影响,但这个假设不一定在所有系统中都成立,例如:
- 模拟网络路由策略(如 BGP)对观察到的视频流吞吐量的影响:改变路径会改变影响视频流的潜在网络条件
- 模拟分支预测器等CPU功能对指令吞吐量的影响:不能将指令/数据缓存的状态建模为外源潜在因素,因为更改分支预测器会显着改变它们的内部状态
模拟设计人员需要推理观察量和潜在量的因果结构,按照式(1)(2)的形式定义适当的模型
不过,不需要精确指定潜在或动态的含义(
F
t
r
a
c
e
mathcal{F}_{trace}
Ftrace和
F
s
y
s
t
e
m
mathcal{F}_{system}
Fsystem),CausalSim会从观察数据中学习
3.2 问题形式化
【这部分看不懂的话略过也可以】
假设有
N
N
N个轨迹(trajectory)【对应于trace】,使用
K
K
K个特定策略采集【对应于算法】
对每个轨迹
i
∈
{
1
,
…
,
N
}
iin{1,dots,N}
i∈{1,…,N},观察
(
m
t
i
,
o
t
i
,
a
t
i
)
t
=
1
H
i
(m_t^i,o_t^i,a_t^i)_{t=1}^{H_i}
(mti,oti,ati)t=1Hi,其中
H
i
H_i
Hi表示轨迹
i
i
i的长度
假设轨迹是使用RCT生成的,即每个轨迹随机分配给
K
K
K个策略之一
目标:在任意给定intervention(如新算法)下,估计
N
N
N中每条轨迹的观察结果
形式化表述:对于任何给定的轨迹
i
i
i和给定的一系列动作
{
a
~
t
i
}
t
=
1
H
i
{ ilde{a}_t^i}_{t=1}^{H_i}
{a~ti}t=1Hi,从观察
o
1
i
o_1^i
o1i开始,在相同的潜在因素序列
{
u
t
i
}
t
=
1
H
i
{u_t^i}_{t=1}^{H_i}
{uti}t=1Hi下,估计与式(1)和(2)一致的反事实观察
{
o
~
t
i
}
t
=
1
H
i
{ ilde{o}_t^i}_{t=1}^{H_i}
{o~ti}t=1Hi
- { u t i } t = 1 H i {u_t^i}_{t=1}^{H_i} {uti}t=1Hi:轨迹 i i i的外源潜在因素
这是一个反事实估计问题(counterfactual estimation problem),因为它需要
- (i) 估计观察到的轨迹 i i i的潜在 { u t i } t = 1 H i {u_t^i}_{t=1}^{H_i} {uti}t=1Hi因素,并基于估计的潜在因素和反事实动作 { a ~ t i } t = 1 H i { ilde{a}_t^i}_{t=1}^{H_i} {a~ti}t=1Hi【新算法的动作,不存在于原trace中】,预测反事实trace { m ~ t i } t = 1 H i { ilde{m}_t^i}_{t=1}^{H_i} {m~ti}t=1Hi,对应式(1)
- (ii) 基于反事实trace { m ~ t i } t = 1 H i { ilde{m}_t^i}_{t=1}^{H_i} {m~ti}t=1Hi和反事实动作 { a ~ t i } t = 1 H i { ilde{a}_t^i}_{t=1}^{H_i} {a~ti}t=1Hi,预测反事实观察 { o ~ t i } t = 1 H i { ilde{o}_t^i}_{t=1}^{H_i} {o~ti}t=1Hi【模拟的最终目标,如BBA的缓冲区水平】,对应式(2)
分析:
- 对于(ii),学习 F s y s t e m mathcal{F}_{system} Fsystem是一个监督学习任务,因为其输出和输出都可以被观察到
- 但对于(i), { u t i } t = 1 H i {u_t^i}_{t=1}^{H_i} {uti}t=1Hi是无法观察的,因此无法通过监督方式学习 F t r a c e mathcal{F}_{trace} Ftrace
因此最终的任务是:估计 { u t i } t = 1 H i {u_t^i}_{t=1}^{H_i} {uti}t=1Hi(潜在因素)并学习 F t r a c e mathcal{F}_{trace} Ftrace(intervention对trace的影响)
4 CausalSim: Theoretical Insights
4.1 反事实估计->矩阵完成
§3.2中明确了任务为估计反事实trace { m ~ t i } t = 1 H i { ilde{m}_t^i}_{t=1}^{H_i} {m~ti}t=1Hi,本节将反事实估计作为矩阵完成问题的变体
考虑一个 A × U A imes U A×U的矩阵 M M M,其在因果推断中被称为潜在结果矩阵:
- 行 A ≥ 2 Ageq2 A≥2:对应潜在动作。即第1行对应动作1,第 A A A行对应动作 A A A
- 列
U
=
∑
i
=
1
N
H
i
U=sum_{i=1}^{N}H_i
U=∑i=1NHi:对应数据集中的不同潜在因素,即不同
i
i
i和
t
t
t下的
u
t
i
u_t^i
uti
- 为了对列进行排序,将 u t i u_t^i uti索引为元组 ( i , t ) (i,t) (i,t),并按照字典顺序排序
- 【相当于是把所有trace不同时间步的潜在因素数据全部放在了一行里,该行中每一列代表一个trace的一个时间步的数据,形如: ( 1 , 1 ) , ( 1 , 2 ) , … , ( 1 , H 1 ) ( 2 , 1 ) , ( 2 , 2 ) , … ( N , H N − 1 ) , ( N , H N ) (1,1),(1,2),dots,(1,H_1)(2,1),(2,2),dots(N,H_N-1),(N,H_N) (1,1),(1,2),…,(1,H1)(2,1),(2,2),…(N,HN−1),(N,HN)】
在第 i i i个轨迹的第 t t t步:
- 观察量:
m
t
i
=
F
t
r
a
c
e
(
a
t
i
,
u
t
i
)
m_t^i=mathcal{F}_{trace}(a_t^i,u_t^i)
mti=Ftrace(ati,uti),在矩阵
M
M
M中为
a
t
i
a_t^i
ati对应的行和
u
t
i
u_t^i
uti对应的列中的条目
- a t i ∈ { 1 , … , A } a_t^iin{1,dots,A} ati∈{1,…,A},为有限多个动作之一
- 感兴趣的反事实量: m ~ t i = F t r a c e ( a ~ t i , u t i ) ilde{m}_t^i=mathcal{F}_{trace}( ilde{a}_t^i,u_t^i) m~ti=Ftrace(a~ti,uti),注意 a ~ t i ≠ a t i ilde{a}_t^i eq a_t^i a~ti=ati,是矩阵 M M M中 u t i u_t^i uti列中缺失的条目(trace不包含这部分数据)
总之,观察到的矩阵 M M M中每一列仅有一个条目,因此目标是估计矩阵中的缺失值
思路:根据部分观察到的条目填充矩阵中缺失值的任务称为矩阵完成
挑战:标准矩阵补全方法不适用于该反事实估计问题(详见§4.3)
解决:使用RCT收集的数据的分布不变性(distributional invariance property)来完成潜在结果矩阵
M
M
M
- 关键观察:在RCT中,在每个策略下收集的轨迹的潜在因素具有相同的分布【因此潜在因素(列)不受潜在动作(行)影响】
- 例如:在Puffer的RCT中,用户被随机分配一个ABR算法,因此每个 ABR 算法都将“体验”相同的底层潜在网络条件分布
【*这部分有个问题:不同action会对应的时间步长(传输时间)实际上是不一样的,因此不同trace的同一步对应的潜在因素并不相同。这是建模引入的偏差,即用步作为时间的基本单位不能保证不同trace数据在时间轴上的对齐。但这个问题的影响可能不大,因为CausalSim使用了神经网络(下文)而且需要很大的数据量进行训练,或许能把这部分偏差掩盖掉或者学出来。】
4.2 利用RCT完成矩阵
例子
考虑一个简单示例,其中 A = 2 A=2 A=2且 U = 2 n U = 2n U=2n,并且潜在结果矩阵 M M M的秩等于1
- 秩等于1表明,对于某些 a ∈ R 2 ainmathbb{R}^2 a∈R2和 u ∈ R 2 n uinmathbb{R}^{2n} u∈R2n且 M α , β = a α ⋅ u β M_{alpha,eta}=a_{alpha}cdot u_{eta} Mα,β=aα⋅uβ,有 M = a u T M=au^T M=auT
有
K
=
2
K=2
K=2个策略,其中每个策略持续选择两个动作之一。假设分配给两个策略的轨迹中潜在因素的分布是相同的。对
M
M
M的列进行重新排序,使得前
n
n
n列对应于策略1轨迹的潜在因素,后
n
n
n列对应策略2。
观察到的条目矩阵
M
M
M如下:(其中⋆表示缺失值):
[
M
1
,
1
M
1
,
2
…
M
1
,
n
⋆
…
⋆
⋆
⋆
⋆
…
⋆
M
2
,
n
+
1
…
M
2
,
2
n
−
1
M
2
,
2
n
]
egin{bmatrix} M_{1,1} & M_{1,2} & dots & M_{1,n} & ⋆ & dots & ⋆ & ⋆ \ ⋆ & ⋆ & dots & ⋆ & M_{2,n+1} & dots & M_{2,2n-1} & M_{2,2n} end{bmatrix}
[M1,1⋆M1,2⋆……M1,n⋆⋆M2,n+1……⋆M2,2n−1⋆M2,2n]
考虑恢复矩阵中丢失的观测值
M
2
,
1
M_{2,1}
M2,1。对于第1列,已知
M
1
,
1
M_{1,1}
M1,1,由于矩阵的秩为1,有:
M
2
,
1
M
1
,
1
=
a
2
u
1
a
1
u
1
=
a
2
a
1
(3)
ag{3} frac{M_{2,1}}{M_{1,1}}=frac{a_2u_1}{a_1u_1}=frac{a_2}{a_1}
M1,1M2,1=a1u1a2u1=a1a2(3)
因此,为了恢复
M
2
,
1
M_{2,1}
M2,1,需要估计
a
2
a
1
frac{a_2}{a_1}
a1a2
考虑到RCT的分布不变性,当
n
n
n足够大时,样本
u
1
,
…
,
u
n
u_1,dots,u_n
u1,…,un与样本
u
n
+
1
,
…
,
u
2
n
u_{n+1},dots,u_{2n}
un+1,…,u2n来自同一个分布。因此,二者的期望值相等,即:
1
n
∑
β
=
1
n
u
β
≈
1
n
∑
β
=
n
+
1
2
n
u
β
(4)
ag{4} frac{1}{n} sum_{eta=1}^{n} u_{eta} approx frac{1}{n} sum_{eta=n+1}^{2n} u_{eta}
n1β=1∑nuβ≈n1β=n+1∑2nuβ(4)
由于
M
α
,
β
=
a
α
⋅
u
β
M_{alpha,eta}=a_{alpha}cdot u_{eta}
Mα,β=aα⋅uβ,有:
∑
β
=
1
n
M
1
,
β
∑
β
=
n
+
1
2
n
M
2
,
β
=
∑
β
=
1
n
a
1
⋅
u
β
∑
β
=
n
+
1
2
n
a
2
⋅
u
β
≈
a
2
a
1
(5)
ag{5} frac{sum_{eta=1}^{n} M_{1,eta}}{sum_{eta=n+1}^{2n} M_{2,eta}} = frac{sum_{eta=1}^{n} a_1 cdot u_{eta}}{sum_{eta=n+1}^{2n} a_2 cdot u_{eta}} approx frac{a_2}{a_1}
∑β=n+12nM2,β∑β=1nM1,β=∑β=n+12na2⋅ uβ∑β=1na1⋅ uβ≈a1a2(5)
可以根据该式,基于观察到的条目,精确地计算式(3)中感兴趣的量,以完成矩阵
【注意:
n
n
n较小的情况下,偏差可能会比较大】
形式化结果
上文中简单示例的idea可以推广更为复杂的场景。令
D
D
D表示测量值数量,则
M
α
,
β
,
γ
∈
R
A
×
U
×
D
M_{alpha,eta,gamma} in mathbb{R}^{A imes U imes D}
Mα,β,γ∈RA×U×D是一个张量。
其中:
- α alpha α:动作
- β eta β:潜在因素
- γ gamma γ:测量值
以下定理提供了完成秩为
r
r
r的张量的可能条件(详细信息和证明在附录A中)
定理4.1:如果满足以下条件,可以通过仅观察每一列中的一个
D
D
D维元素(对应于一个潜在因素和动作)来恢复
M
M
M的所有条目:
- 低秩分解(Low-Rank Factorization): M M M是一个低秩张量(秩为 r r r),即其与允许以下因式分解: M α , β , γ = ∑ ℓ = 1 r a α ℓ u β ℓ z γ ℓ M_{alpha,eta,gamma} = sum_{ℓ=1}^{r} a_{alpha ℓ} u_{eta ℓ} z_{gamma ℓ} Mα,β,γ=∑ℓ=1raαℓuβℓzγℓ
- 可逆性(Invertibility):因式分解意味着存在一个从潜在编码到trace每个动作的线性映射,这种线性映射是可逆的
- 足够的测量: D ≥ r D geq r D≥r
- 充足且多样(diverse)的策略(略)
4.3 讨论(略)
- 标准的张量完成不适用的原因
- 定理 4.1 的局限性
5 CausalSim: Algorithm
CausalSim建立在前面提出的见解的基础上,但用基于神经网络(NN)的学习算法取代了因式分解模型【可能是因为潜在因素不容易直接量化?】。
结构
CausalSim的目标是从观察到的轨迹
(
o
t
+
1
,
o
t
,
m
t
,
a
t
)
(o_{t+1},o_{t},m_{t},a_{t})
(ot+1,ot,mt,at)中提取
u
t
u_t
ut并学习
F
t
r
a
c
e
mathcal{F}_{trace}
Ftrace和
F
s
y
s
t
e
m
mathcal{F}_{system}
Fsystem,其算法结构如下图所示:
组成部分:三个神经网络
- E θ mathcal{E}_ heta Eθ(潜在因素提取器,Latent Factor Extractor):提取潜在因素,以 a t a_t at和 m t m_t mt作为输入,计算 u t u_t ut的估计值 u ^ t hat{u}_t u^t
- W γ mathcal{W}_{gamma} Wγ(策略鉴别器,Policy Discriminator):以预测的潜在因素 u ^ t hat{u}_t u^t作为输入,预测 u ^ t hat{u}_t u^t对应的策略(算法)。如果分布不变性成立,则该预测无法做到准确
-
P
φ
mathcal{P}_{varphi}
Pφ:将
F
t
r
a
c
e
mathcal{F}_{trace}
Ftrace和
F
s
y
s
t
e
m
mathcal{F}_{system}
Fsystem组合为一个函数(对应一个NN)以简化学习问题,以反事实行动
a
~
t
ilde{a}_t
a~t、观察
o
t
o_{t}
ot和预测的潜在因素
u
^
t
hat{u}_t
u^t作为输入,计算反事实观察
o
~
t
+
1
ilde{o}_{t+1}
o~t+1
- 如果需要计算反事实trace m ~ t ilde{m}_t m~t的话,也可以为 F t r a c e mathcal{F}_{trace} Ftrace和 F s y s t e m mathcal{F}_{system} Fsystem分别使用单独的NN
【
W
γ
mathcal{W}_{gamma}
Wγ和
P
φ
mathcal{P}_{varphi}
Pφ两个NN的设计思想源自于对抗学习(adversarial learning)。具体而言,二者的损失函数有关联且符号相反,因此有对抗的效果,详见下文。】
【CausalSim对抗学习的思想:用一个神经网络
W
γ
mathcal{W}_{gamma}
Wγ来尽可能降低分布不变性(寻找对抗样本,即违背不变性的情况),用另一个神经网络
P
φ
mathcal{P}_{varphi}
Pφ(学习对抗样本)来尽可能提高分布不变性,其目的是使整体算法的分布不变性更强(具有对抗鲁棒性)。】
【补充分析:
将式(1)代入式(2)可得:
o
t
+
1
=
F
s
y
s
t
e
m
(
o
t
,
F
t
r
a
c
e
(
a
t
,
u
t
)
,
a
t
)
o_{t+1} = mathcal{F}_{system}(o_t, mathcal{F}_{trace} (a_t, u_t), a_t)
ot+1=Fsystem(ot,Ftrace(at,ut),at),其中
o
t
o_{t}
ot(包括
o
t
+
1
o_{t+1}
ot+1)和
a
t
a_{t}
at已知,而
u
t
u_t
ut、
F
t
r
a
c
e
mathcal{F}_{trace}
Ftrace和
F
s
y
s
t
e
m
mathcal{F}_{system}
Fsystem均未知。
回想§2中的任务是利用BOLA2的RCT trace来预测BBA的缓冲区水平分布,因此CausalSim算法思想的抽象描述为:对于trace给出的观察值
(
m
t
,
o
t
,
a
t
)
(m_t,o_t,a_t)
(mt,ot,at),通过完成潜在结果矩阵
M
M
M中缺失的
u
t
u_t
ut,预测每个反事实动作
a
~
t
ilde{a}_t
a~t(目标算法的动作,未在原trace中出现)对应的反事实观察
o
~
t
ilde{o}_t
o~t(包括
o
~
t
+
1
ilde{o}_{t+1}
o~t+1)。
因此,为了实现任务目标,CausalSim需要预测
u
t
u_t
ut,并学习
F
t
r
a
c
e
mathcal{F}_{trace}
Ftrace和
F
s
y
s
t
e
m
mathcal{F}_{system}
Fsystem。】
训练及推理开销:
- 在A100 Nvidia GPU上,CausalSim在56M数据点(230K streams)上的收敛时间不到10分钟
- 推理中的每个模拟步骤(在CPU上)花费的时间不到150μs
- 对相同数据量进行完整推理在单核CPU上花费不到6小时,在32核上不到20分钟
训练过程
CausalSim 的训练过程交替进行(算法1):
- (i) 使用鉴别损失 L d i s c mathcal{L}_{disc} Ldisc训练策略鉴别器( W γ mathcal{W}_{gamma} Wγ)
- (ii) 使用聚合损失 L t o t a l mathcal{L}_{total} Ltotal训练其他模块( P φ mathcal{P}_{varphi} Pφ)
训练策略鉴别器
原理:分布不变性意味着潜在因素 u u u的分布在不同策略上保持不变。为了确保分布不变,首先使用 E θ mathcal{E}_ heta Eθ来提取潜在因素 u ^ t hat{u}_t u^t,然后通过鉴别器搜索违反不变性(invariance violations)的情形,这是对抗性学习(adversarial learning)范式中的一种标准方法
目标:根据估计的潜在因素 u ^ t hat{u}_t u^t,预测采取行动 a t a_t at的策略 π i pi_i πi【鉴别器预测越准确,说明分布不变性越不成立】
损失函数:交叉熵(cross-entropy)
L
d
i
s
c
=
E
B
[
−
log
W
γ
(
π
∣
u
^
)
]
mathcal{L}_{disc} = mathbb{E}_B [-log mathcal{W}_gamma (pi | hat{u})]
Ldisc=EB[−logWγ(π∣u^)]
- 其中 B B B为数据集 D D D中采样的minibatch
- 为了最小化该损失,需要重复梯度衰减num_disc_it次,因为策略鉴别器需要多次迭代才能捕捉潜在因素的变化
训练模拟模块
原理:在这一步中,需要与观察结果保持一致,同时保持分布不变性。因此,用 E θ mathcal{E}_ heta Eθ计算潜在因素 u ^ t hat{u}_t u^t,并用 P φ mathcal{P}_{varphi} Pφ模拟轨迹的下一步 o ^ t + 1 hat{o}_{t+1} o^t+1
损失函数:聚合(aggregated)损失,将取负的鉴别损失
L
d
i
s
c
mathcal{L}_{disc}
Ldisc与使用混合超参数
κ
κ
κ的二次一致性(quadratic consistency【感觉类似于MSE】)损失相结合
L
d
i
s
c
=
E
B
[
(
o
t
+
1
−
o
^
t
+
1
)
2
]
−
κ
L
d
i
s
c
mathcal{L}_{disc} = mathbb{E}_B [(o_{t+1} - hat{o}_{t+1})^2] - κmathcal{L}_{disc}
Ldisc=EB[(ot+1−o^t+1)2]−κLdisc
- 二次一致性损失可以换为适合特定类型变量的任何一致性损失,如Huber损失、交叉熵等
- 注意鉴别损失 L d i s c mathcal{L}_{disc} Ldisc前的负号,这代表 P φ mathcal{P}_{varphi} Pφ的目标是最大化鉴别损失,即欺骗策略鉴别器 W γ mathcal{W}_{gamma} Wγ以确保分布不变性。如果提取的潜在因素对于不同策略而言是不变的,那么策略鉴别器的表现不会比随机猜测更好
反事实估计
为了产生反事实估计,首先从观察到的数据中提取估计的潜在因素 u ^ t hat{u}_t u^t。之后,使用提取的潜在因素 u ^ t hat{u}_t u^t以及学习到的组合函数 P γ mathcal{P}_{gamma} Pγ,从 o 1 o_1 o1开始一次一步地预测反事实观察 o ^ t + 1 hat{o}_{t+1} o^t+1
6 Evaluation
6.1 ABR模拟准确性
任务:选择Puffer中5种算法的trace数据,基于其他4种源算法的trace来模拟目标算法
- 5种算法:BBA, BOLA1, BOLA2, Fugu-CL, Fugu-2019
- 3种目标算法:BBA, BOLA1, BOLA2
模拟BBA、BOLA1和BOLA2的卡顿率与视频质量(SSIM),CausalSim与Ground Truth之间的最为接近(误差线表明在4种源算法下取得的数值的最大值和最小值)
不同源算法的影响:对于ExpertSim和SLSim而言,它们表现最好的情况是源算法为BOLA2、目标算法为BOLA1的情形,但CausalSim对于在源算法不同的情况下表现都一样好
6.2 BOLA1性能调优
任务:在simulation中调整BOLA1的超参数来探索其帕累托边界曲线(Pareto frontier curve),对BOLA1进行性能优化(这部分是Puffer上的真实实验结果)
模拟结果:
- CausalSim发现BOLA1在Puffer上的性能不如BBA其实是参数设置问题(图中的点),通过调整参数,有希望对BOLA1实现性能提升
- ExpertSim则表明BOLA1的性能始终差于BBA
Puffer真实实验结果:经过参数调优后的BOLA1-CausalSim在与BBA取得了相似的视频质量的情况下,降低了卡顿率,证明了模拟的准确性
关于视频流中可用带宽与吞吐量的区别,可以参阅Lumos (INFOCOM '22)的Motivation部分 ↩︎
对于BOLA的介绍,可以参阅BOLA (INFOCOM ’16) 论文阅读笔记和Implementing BOLA-BASIC on Puffer ↩︎