您现在的位置是:首页 >学无止境 >CausalSim (NSDI ‘23 Best Paper)论文阅读笔记网站首页学无止境

CausalSim (NSDI ‘23 Best Paper)论文阅读笔记

Green Lv 2024-06-17 10:22:13
简介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]平台及数据集进行了详细的分析和实验验证。

注:

  • 本笔记主要内容是基于原论文的总结、梳理和翻译。原论文内容比较复杂,行文偏晦涩。为了便于读懂,本笔记补充了个人理解和文章内容之外的补充叙述(由“【】”标出)。由于本人对于因果推断、反事实估计、张量完成和对抗学习等相关知识并不熟悉,因此部分内容仅供参考,不保证准确性
  • 关于翻译:
    • “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,btc^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数据

预测效果

image.png
结果:ExpertSim和SLSim与目标算法之间存在偏差

  • ExpertSim的预测更接近源算法(BOLA2)的缓冲区占用率分布,但距离目标算法(BBA)的缓冲区占用率分布比较远
  • SLSim表现与ExpertSim相似

原因:ABR算法决策会影响视频块的吞吐量(下图),导致外源trace假设失效
image.png

解决思路

  • 如果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的影响,如下图所示(图中的箭头表示因果关系):
image.png

  • a a a:模拟的对象,如算法的动作(action)
  • o o o:观察到的状态
  • u u u:潜在外部状态,不在模拟的范围内
  • m m m:采集的trace(变量可以是多维的,并随时间变化)

CausalSim采用外源潜在假设(exogenous latent assumption),考虑了模拟对象对于trace的影响( a → m a arr m am
image.png
注:

  • 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 A2:对应潜在动作。即第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,HN1),(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 aR2 u ∈ R 2 n uinmathbb{R}^{2n} uR2n 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,1M1,2M1,nM2,n+1M2,2n1M2,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β=1nuβn1β=n+12nuβ(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 Dr
  • 充足且多样(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,其算法结构如下图所示:
image.png
组成部分:三个神经网络

  • 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分钟

训练过程

image.png
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+1o^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

image.png
模拟BBABOLA1BOLA2的卡顿率与视频质量(SSIM),CausalSim与Ground Truth之间的最为接近(误差线表明在4种源算法下取得的数值的最大值和最小值)

image.png
不同源算法的影响:对于ExpertSim和SLSim而言,它们表现最好的情况是源算法为BOLA2、目标算法为BOLA1的情形,但CausalSim对于在源算法不同的情况下表现都一样好

6.2 BOLA1性能调优

任务:在simulation中调整BOLA1的超参数来探索其帕累托边界曲线(Pareto frontier curve),对BOLA1进行性能优化(这部分是Puffer上的真实实验结果)

image.png
模拟结果:

  • CausalSim发现BOLA1在Puffer上的性能不如BBA其实是参数设置问题(图中的点),通过调整参数,有希望对BOLA1实现性能提升
  • ExpertSim则表明BOLA1的性能始终差于BBA

image.png
Puffer真实实验结果:经过参数调优后的BOLA1-CausalSim在与BBA取得了相似的视频质量的情况下,降低了卡顿率,证明了模拟的准确性


  1. 关于视频流中可用带宽与吞吐量的区别,可以参阅Lumos (INFOCOM '22)的Motivation部分 ↩︎

  2. 对于BOLA的介绍,可以参阅BOLA (INFOCOM ’16) 论文阅读笔记Implementing BOLA-BASIC on Puffer ↩︎

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。