Stochastic Low-Rank Tensor Bandits for Multi-Dimensional Online Decision Making¶
作者: Jie Zhou, Botao Hao, Zheng Wen, Jingfei Zhang, Will Wei Sun
来源: Journal of the American Statistical Association
主题: 因果推断
相关性: 6/10
链接: 期刊页 · arXiv
一、领域脉络与小综述¶
这个方向是什么¶
本方向研究多维度在线决策问题,即每个时间点需要从多个实体类型(如用户、商品、广告位)的组合中选择一个决策,目标是最大化累积奖励。这类问题被建模为随机低秩张量Bandit:每个时间点的奖励是一个随机变量,其均值由一个低秩张量给出。该问题与因果推断中的动态处理策略(如个性化治疗分配)有直接联系,低秩张量结构可用于建模高维异质性处理效应。当前该方向处于方法提出与理论分析阶段,已有一些工作将矩阵(2维)低秩结构引入Bandit,但扩展到更高维张量的工作较少,且缺乏对上下文(context)信息的整合。
发展脉络(history)¶
根据论文引言,该方向的发展脉络如下:
-
奠基工作:矩阵Bandit。
Kveton et al. (2017)首次将低秩矩阵结构引入Bandit问题,提出了Low-rank matrix bandits,并给出了有限时间遗憾界。这是将低秩假设与在线学习结合的开创性工作。作者引用其作为“将低秩结构引入Bandit”的起点。 -
主要进展:张量Bandit的初步探索。
Hao et al. (2020a)研究了Stochastic low-rank tensor bandits,提出了TOFU(Tensor Online Learning with Fast Updates)算法,并给出了遗憾界。这是本文最直接的前身。作者指出,TOFU的遗憾界在张量维度上存在指数级依赖(即随张量阶数K指数增长),这是其核心瓶颈。 -
当前Frontier:改进遗憾界与引入上下文。本文(
Zhou et al., 2023)在Hao et al. (2020a)的基础上,提出了两种新算法:tensor elimination和tensor epoch-greedy。tensor elimination实现了最优的整体遗憾界(消除了对张量阶数K的指数依赖),而tensor epoch-greedy在张量维度上具有更尖锐的依赖关系(从指数降为多项式)。此外,本文首次将上下文信息引入张量Bandit,提出了tensor ensemble sampling算法。 -
被淡化的竞争路线:作者在引言中提及了
Lu et al. (2021)的Low-rank generalized linear bandits,但将其定位为“仅适用于矩阵(2维)情形”,从而淡化了其在广义线性模型下的扩展性。作者也提及了Jun et al. (2019)的Spectral bandits,但指出其假设奖励矩阵是稀疏的而非低秩的,从而将本文的低秩假设定位为更自然的替代方案。
子线索聚类¶
这些被引文献大致落在以下3条子线索上:
-
低秩矩阵/张量Bandit:核心是假设奖励均值矩阵/张量是低秩的,并设计算法利用该结构进行探索-利用权衡。代表工作:
Kveton et al. (2017)(矩阵)、Hao et al. (2020a)(张量,TOFU)、本文(张量,tensor elimination & epoch-greedy)。这条线索是本文的直接定位。 -
上下文Bandit:核心是利用上下文信息(如用户特征)来个性化决策。代表工作:
Li et al. (2010)(LinUCB)、Agrawal & Goyal (2013)(Thompson sampling)。本文的tensor ensemble sampling算法属于此线索,但将上下文与决策的交互建模为低秩张量。 -
贝叶斯Bandit与Ensemble Sampling:核心是使用贝叶斯方法(如Thompson sampling)或其后验近似(如ensemble sampling)来处理不确定性。代表工作:
Lu & Van Roy (2017)(Ensemble sampling for linear bandits)。本文的tensor ensemble sampling算法直接借鉴了Lu & Van Roy (2017)的ensemble sampling框架,并将其扩展到张量设定。
这个方向在追问的核心问题¶
-
如何设计算法实现最优的遗憾界? 即,在低秩张量假设下,能否达到与线性Bandit(参数数量为
d)相当的遗憾界O~(d√T),而非与张量条目总数(∏_k d_k)相关的界?本文的tensor elimination回答了这个问题,实现了O~(√(K R T ∏_k d_k))的界,其中R是秩,K是张量阶数,d_k是第k维的大小。这个界在∏_k d_k上是最优的(与线性Bandit的d对应),但引入了√K的因子。 -
如何将上下文信息整合到张量Bandit中? 在现实应用中,决策往往依赖于上下文(如用户画像)。如何将上下文建模为张量的一个或多个模式,并设计算法利用低秩结构进行高效学习?本文的
tensor ensemble sampling是首次尝试,但其遗憾界分析是开放问题。 -
如何设计计算高效的算法? 张量操作(如CP分解)的计算复杂度随阶数K指数增长。如何设计算法使得每轮决策的计算时间在
poly(K, R, d_k)内,而非指数级?本文的tensor epoch-greedy通过分阶段探索-利用,避免了每轮都进行张量分解,从而降低了计算成本。
⚠️ 作者的 framing¶
作者将缺口frame成:“现有张量Bandit算法(TOFU)的遗憾界在张量阶数K上是指数依赖的,且无法处理上下文信息。” 因此,本文的贡献被定位为“显然的下一步”:提出两种新算法,分别实现最优整体遗憾界(消除指数依赖)和更尖锐的维度依赖,并首次引入上下文设定。
被淡化或回避的竞争路线:
- 广义线性模型(GLM)Bandit:作者提及Lu et al. (2021)的Low-rank GLM bandits,但仅说其“适用于矩阵情形”,回避了将其扩展到张量情形的可能性。实际上,GLM框架可以自然地处理非高斯奖励(如二值奖励),而本文仅假设奖励是次高斯的。
- 稀疏张量Bandit:作者提及Jun et al. (2019)的Spectral bandits,但将其定位为“稀疏”而非“低秩”,从而回避了稀疏假设与低秩假设在Bandit问题中的优劣比较。在现实应用中,奖励张量可能既是稀疏的又是低秩的,但本文未讨论这种混合结构。
什么明显该被引/该存在、却没出现在intro里?
- Agarwal et al. (2014)的Tensor completion:该工作是低秩张量补全的奠基性论文,其理论(如SGD算法、incoherence条件)与本文的tensor elimination算法有直接联系。作者在正文中引用了Jain & Oh (2014)(张量补全的SGD),但未引用Agarwal et al. (2014),这可能是一个遗漏。
- Koltchinskii et al. (2011)的Nuclear norm penalization:该工作为矩阵/张量补全提供了nuclear norm正则化的理论分析。本文的tensor elimination算法本质上是一种“先估计再优化”的策略,与nuclear norm方法有相似之处,但未引用该经典工作。
张力¶
未见明显对立引用。所有被引工作均支持“低秩结构有助于加速Bandit学习”这一共识。唯一的张力在于遗憾界的依赖形式:Hao et al. (2020a)的TOFU算法在K上是指数依赖,而本文的tensor elimination将其降为多项式依赖。这并非矛盾,而是改进。
二、最核心、最简单的例子 / 数学问题¶
第一步:把符号、模型、可观测数据交代清楚¶
-
符号:
K:张量的阶数(模式数),例如K=3表示用户、商品、广告位三个模式。d_k:第k个模式的大小(类别数),例如d_1=100个用户,d_2=50个商品,d_3=10个广告位。[d_k]:集合{1, ..., d_k}。(i_1, ..., i_K):一个K元组,表示一个具体的决策(如用户i_1、商品i_2、广告位i_3的组合)。T:总时间步数。t:当前时间步,t = 1, ..., T。a_t = (a_{t,1}, ..., a_{t,K}):时间t选择的决策(K元组)。r_t:时间t观察到的奖励,是一个随机变量。Θ:真实的奖励均值张量,大小为d_1 × ... × d_K。其条目Θ_{i_1, ..., i_K}是决策(i_1, ..., i_K)的期望奖励。R:张量Θ的秩(CP秩),即Θ可以表示为R个秩一张量的和:Θ = Σ_{r=1}^R u^{(1)}_r ∘ ... ∘ u^{(K)}_r,其中u^{(k)}_r ∈ ℝ^{d_k}是第r个因子在第k个模式上的向量。U^{(k)}:大小为d_k × R的因子矩阵,其第r列是u^{(k)}_r。λ:次高斯参数,用于控制奖励噪声的尾部行为。Δ:最小奖励差距(gap),即最优决策与次优决策的期望奖励之差的最小值。Regret(T):累积遗憾,定义为Σ_{t=1}^T (Θ_{a^*} - Θ_{a_t}),其中a^*是最优决策(Θ的最大条目)。
-
模型:
- 数据生成机制:在每个时间步
t,平台选择一个决策a_t,然后观察到一个随机奖励r_t,满足E[r_t | a_t] = Θ_{a_t},且r_t - Θ_{a_t}是λ-次高斯的(即尾部衰减快于高斯分布)。 - 低秩假设:真实的奖励均值张量
Θ是低秩的,即rank(Θ) = R << min_k d_k。这意味着Θ可以被分解为R个秩一张量的和。 - 已知量:
K,d_k,R(假设已知或可估计),λ(次高斯参数)。 - 待估对象:
Θ本身,或者更直接地,其因子矩阵{U^{(k)}}_{k=1}^K。
- 数据生成机制:在每个时间步
-
可观测数据:
- 可观测:每个时间步
t,研究者观测到选择的决策a_t和对应的奖励r_t。这是标准的Bandit反馈。 - 不可观测:研究者无法观测到未选择的决策的奖励(反事实)。这是Bandit问题的核心困难。此外,真实的因子矩阵
U^{(k)}也是不可观测的潜在变量。
- 可观测:每个时间步
第二步:讲最小内核¶
最简特例:K=2(矩阵Bandit),R=1(秩1矩阵),d_1 = d_2 = d(对称情形)
在这个特例下,问题退化为:有一个d × d的矩阵Θ,其条目Θ_{i,j} = u_i * v_j,其中u, v ∈ ℝ^d。目标是找到使u_i * v_j最大的(i, j)对。
核心思路:由于Θ是秩1的,其所有条目由两个向量u和v决定。因此,我们不需要探索所有d^2个条目,而只需要估计u和v。这相当于一个线性Bandit问题,其中参数向量是u和v的某种组合。
算法(tensor elimination的简化版):
1. 探索阶段:随机选择O(d)个决策(i, j),观察奖励。利用这些观测值,通过最小二乘法估计u和v(例如,将问题视为Θ_{i,j} = u_i * v_j的矩阵补全问题,使用SGD或SVD)。
2. 利用阶段:基于估计的û和v̂,计算所有d^2个条目的估计值Θ̂_{i,j} = û_i * v̂_j,然后选择使Θ̂_{i,j}最大的决策(î, ĵ)。
3. 重复:将时间划分为多个阶段,每个阶段重复上述探索-利用过程,并随着时间推移减少探索的比例。
为什么这个特例能体现核心困难:
- 维度灾难:即使K=2,直接探索所有d^2个条目也是不可行的(遗憾界为O(d^2√T))。低秩假设(R=1)将有效参数数量从d^2降为2d,使得遗憾界可以降为O(d√T)。
- 估计与决策的耦合:在探索阶段,我们需要估计u和v,但估计误差会直接影响利用阶段的选择。tensor elimination的核心思想是,通过精心设计的探索策略,确保估计误差足够小,从而使得利用阶段的选择接近最优。
- 张量分解的复杂性:当K>2时,张量分解(如CP分解)比矩阵分解(SVD)更复杂,存在非凸性和局部最优问题。本文的tensor elimination算法通过使用SGD进行张量补全,避免了直接进行CP分解的困难。
一般情形下的推广:当K>2且R>1时,核心思路不变:利用低秩结构将有效参数数量从∏_k d_k降为R * Σ_k d_k。tensor elimination算法通过分阶段探索-利用,在每个阶段使用SGD估计因子矩阵,然后基于估计值选择最优决策。其遗憾界为O~(√(K R T ∏_k d_k)),其中√(∏_k d_k)项是不可避免的(因为需要估计所有条目的信息),而√K项是本文改进的代价。
三、这篇论文做了什么¶
三句话¶
- 研究了什么问题:多维度在线决策问题,建模为随机低秩张量Bandit,包括无上下文和带上下文两种设定。
- 核心工具/方法:提出了三种算法——
tensor elimination(基于分阶段探索-利用和张量补全的SGD)、tensor epoch-greedy(基于分阶段探索-利用和直接采样)、tensor ensemble sampling(基于贝叶斯后验近似的上下文Bandit算法)。 - 主要结论:
tensor elimination实现了最优的整体遗憾界O~(√(K R T ∏_k d_k));tensor epoch-greedy实现了在张量维度上更尖锐的依赖关系O~(K R √(T ∏_k d_k))(将√K因子从根号内移到根号外,但引入了K因子);tensor ensemble sampling在仿真和真实数据上优于忽略低秩结构的基线方法。
关键设定与假设¶
在第二节最小记号的基础上,补全完整设定:
-
无上下文设定:
- 假设1(低秩):
rank(Θ) = R,且R已知。这是核心假设。 - 假设2(次高斯噪声):奖励噪声
r_t - Θ_{a_t}是λ-次高斯的。这是进行高概率遗憾界分析的标准假设。 - 假设3(incoherence条件):因子矩阵
U^{(k)}是μ-incoherent的,即其行向量的范数有界:max_{i,k} ||U^{(k)}_{i,:}||_2 ≤ μ √(R/d_k)。这是张量补全理论中的标准条件,用于确保低秩张量的条目不会过于集中在少数行上,从而使得随机采样能够有效估计整个张量。 - 与已有文献的对比:相比
Hao et al. (2020a)的TOFU算法,本文的假设更弱(TOFU假设奖励是[0,1]有界的,而本文假设次高斯),且tensor elimination的遗憾界消除了对K的指数依赖。
- 假设1(低秩):
-
带上下文设定:
- 设定:张量的前
M个模式是上下文(如用户特征),后K-M个模式是决策(如商品、广告位)。在每个时间步t,平台观察到上下文c_t = (c_{t,1}, ..., c_{t,M}),然后选择一个决策a_t = (a_{t,M+1}, ..., a_{t,K})。奖励均值由Θ_{c_t, a_t}给出。 - 假设:
Θ仍然是低秩的,且上下文和决策共享同一个低秩结构。这意味着,即使上下文模式不同,其因子矩阵也共享相同的低秩分解。 - 与无上下文设定的区别:在带上下文设定下,最优决策依赖于上下文,因此算法需要根据上下文信息进行个性化决策。
tensor ensemble sampling通过维护因子矩阵的后验分布,并从中采样来生成决策,从而自然地处理了上下文依赖性。
- 设定:张量的前
主要结果¶
定理1(tensor elimination的遗憾界):
- 陈述:在假设1-3下,tensor elimination算法以至少1-δ的概率满足:
Regret(T) ≤ C * √(K R T ∏_k d_k * log(T/δ)),其中C是依赖于μ和λ的常数。
- 直觉:这个界与线性Bandit的O~(d√T)界形式相同,其中d被替换为∏_k d_k(张量条目总数)。这直观上是最优的,因为即使知道低秩结构,也需要估计所有∏_k d_k个条目的信息(通过因子矩阵的乘积)。√K因子是本文改进的代价,相比Hao et al. (2020a)的指数依赖,这是一个巨大的进步。
- 必要条件:需要T足够大,使得探索阶段能够收集到足够多的样本以准确估计因子矩阵。具体地,需要T ≥ Ω( (μ^2 R^2 K / min_k d_k) * log(T/δ) )。
- 解决的技术难点:如何将张量补全的SGD算法与Bandit的探索-利用框架结合,并推导出高概率的遗憾界。关键在于,SGD的估计误差需要被控制,并且与探索策略的采样分布相匹配。
定理2(tensor epoch-greedy的遗憾界):
- 陈述:在假设1-3下,tensor epoch-greedy算法以至少1-δ的概率满足:
Regret(T) ≤ C' * K R √(T ∏_k d_k * log(T/δ))。
- 直觉:这个界在∏_k d_k上的依赖与tensor elimination相同(都是√(∏_k d_k)),但在K上的依赖更尖锐:tensor elimination是√K,而tensor epoch-greedy是K。然而,tensor epoch-greedy的界中没有√(∏_k d_k)项中的√K因子,因此当K较大时,tensor epoch-greedy可能更优。具体地,tensor epoch-greedy的界是O~(K R √(T ∏_k d_k)),而tensor elimination的界是O~(√(K R T ∏_k d_k))。当K固定时,两者都是O~(√(T ∏_k d_k));当K增长时,tensor epoch-greedy的界更差(K vs √K),但tensor elimination的界中√(∏_k d_k)项内的√K因子可能被常数吸收。
- 必要条件:与定理1类似。
- 解决的技术难点:tensor epoch-greedy通过在每个阶段直接采样所有决策(而非先估计再优化),避免了张量补全的复杂性,从而得到了更简单的遗憾界分析。其代价是引入了K因子。
定理3(tensor ensemble sampling的遗憾界):
- 陈述:本文未给出tensor ensemble sampling的遗憾界,仅给出了仿真和真实数据实验。作者在文中指出:“Providing a rigorous regret bound for tensor ensemble sampling is an important future work.”
- 直觉:ensemble sampling是一种近似Thompson sampling的方法,其遗憾界分析通常比Thompson sampling更复杂。在张量设定下,由于后验分布的非凸性,分析更加困难。
证明路线与技术技巧¶
整体路线(以tensor elimination为例):
- 分阶段:将时间
[1, T]划分为L个阶段,每个阶段l的长度为τ_l。在每个阶段开始时,算法进行探索(随机采样),然后利用探索得到的样本估计因子矩阵,最后在阶段剩余时间内利用估计结果选择最优决策。 - 探索阶段:在每个阶段
l,算法从所有∏_k d_k个决策中均匀随机采样N_l个决策,并观察其奖励。这保证了探索的覆盖性。 - 估计阶段:利用所有历史探索样本(包括当前阶段和之前阶段的),使用张量补全的
SGD算法(Jain & Oh, 2014)估计因子矩阵{Û^{(k)}}_{k=1}^K。SGD的输入是探索样本的决策-奖励对,输出是因子矩阵的估计。 - 利用阶段:基于估计的因子矩阵,计算所有
∏_k d_k个条目的估计值Θ̂_{i_1, ..., i_K},然后选择使Θ̂最大的决策â。在阶段剩余时间内,一直选择â。 - 遗憾分析:将总遗憾分解为每个阶段的探索遗憾和利用遗憾。探索遗憾由探索样本数量控制。利用遗憾由估计误差控制:如果估计误差小于最小奖励差距
Δ的一半,则利用阶段不会选错决策。通过精心选择阶段长度τ_l和探索样本数量N_l,可以平衡探索和利用,得到最优的遗憾界。
关键跳跃点:
- 从探索样本到因子矩阵估计的误差控制:这是最吃功夫的部分。需要证明,在incoherence条件下,使用SGD进行张量补全,其估计误差||Θ̂ - Θ||_F(Frobenius范数)以高概率被O(√(K R N / ∏_k d_k))控制,其中N是探索样本总数。这个界依赖于SGD的收敛性分析,以及incoherence条件对采样分布的要求。
- 从估计误差到利用遗憾的控制:需要证明,如果||Θ̂ - Θ||_∞(最大条目误差)小于Δ/2,则利用阶段不会选错决策。这需要将Frobenius范数误差转化为最大条目误差,这通常需要额外的incoherence条件或union bound。
技术技巧点名:
- 张量补全的SGD:用于从部分观测中估计低秩张量。其核心是迭代更新因子矩阵,以最小化观测条目上的平方损失。本文使用了Jain & Oh (2014)的SGD算法,并证明了其在Bandit设定下的收敛性。
- 分阶段探索-利用:这是Bandit问题中的标准技巧,用于将探索和利用分离,从而简化遗憾分析。本文将其与张量补全结合。
- union bound与concentration inequality:用于控制估计误差和遗憾的高概率界。具体地,使用了Hoeffding's inequality和Bernstein's inequality。
- incoherence条件:用于确保低秩张量的条目不会过于集中,从而使得随机采样能够有效估计整个张量。这是张量补全理论中的标准工具。
真实例子与应用¶
数据:在线广告数据,来自一个真实的广告平台。数据包含K=3个模式:用户(d_1=100)、广告位(d_2=10)、广告创意(d_3=20)。奖励是点击率(CTR),即用户点击广告的概率。这是一个无上下文设定。
方法应用:
1. 数据预处理:将历史CTR数据整理成一个100 × 10 × 20的张量,其条目是每个用户-广告位-广告创意组合的平均CTR。这个张量被假设为低秩的(R=5)。
2. 算法运行:在模拟的在线环境中,每个时间步,算法选择一个用户-广告位-广告创意组合,并观察一个二值奖励(点击/不点击)。算法使用tensor elimination或tensor epoch-greedy进行决策。
3. 基线方法:与忽略低秩结构的算法进行比较,包括:
- Uniform:均匀随机选择。
- Greedy:基于历史平均CTR选择当前最优决策。
- Epsilon-greedy:以概率ε随机探索,否则选择当前最优决策。
- LinUCB:将问题视为线性Bandit,但将张量展平为向量(维度为100*10*20=20000),这忽略了低秩结构。
结果:
- tensor elimination和tensor epoch-greedy的累积遗憾显著低于所有基线方法。
- tensor epoch-greedy在早期阶段表现更好(因为其探索更高效),而tensor elimination在后期阶段表现更好(因为其估计更准确)。
- 忽略低秩结构的LinUCB表现最差,因为其需要估计的参数数量(20000)远大于低秩假设下的有效参数数量(R * Σ_k d_k = 5 * (100+10+20) = 650)。
这个例子想说明什么:
- 验证理论:实验结果表明,利用低秩结构可以显著降低遗憾,与理论分析一致。
- 展示相对优势:与忽略低秩结构的基线方法相比,本文算法在真实数据上取得了更好的性能,证明了低秩假设在实际应用中的合理性。
- 算法比较:展示了tensor elimination和tensor epoch-greedy在不同阶段的性能差异,为实际应用中的算法选择提供了指导。
🔎 结论是否比证明窄¶
tensor ensemble sampling的遗憾界:作者在结论中声称“tensor ensemble sampling在实践中有效”,但未给出任何遗憾界证明。这是一个明显的“结论比证明窄”的例子。作者在文中明确将其列为未来工作。tensor elimination的最优性:作者声称tensor elimination具有“最优的整体遗憾界”。这个结论是有条件的:它是在incoherence假设下,与线性Bandit的O~(d√T)界类比得出的。严格来说,本文并未证明Ω(√(K R T ∏_k d_k))的下界,因此“最优”一词应理解为“与线性Bandit的界形式一致”,而非“已证明的minimax最优”。tensor epoch-greedy的维度依赖:作者声称tensor epoch-greedy具有“更尖锐的维度依赖”。这个结论需要仔细解读:其界是O~(K R √(T ∏_k d_k)),而tensor elimination的界是O~(√(K R T ∏_k d_k))。当K固定时,两者都是O~(√(T ∏_k d_k));当K增长时,tensor epoch-greedy的界更差(Kvs√K)。因此,“更尖锐”仅指其界中没有√(∏_k d_k)项内的√K因子,但引入了额外的K因子。这是一个trade-off,而非绝对的改进。
四、开放问题¶
-
tensor ensemble sampling的遗憾界:本文未给出tensor ensemble sampling的遗憾界。需要证明其在上下文设定下的有限时间遗憾界,这可能涉及贝叶斯后验近似的误差分析,以及张量分解的非凸性带来的挑战。(扎根于:Section 5,作者明确将其列为未来工作。) -
未知秩
R的设定:本文假设秩R已知。在实际应用中,R通常是未知的。如何设计自适应算法,在不知道R的情况下实现接近最优的遗憾界?这可能涉及秩的在线估计,或使用nuclear norm正则化等自动选择秩的方法。(扎根于:Section 6,作者提及“extending to unknown rank is an important direction”。) -
非次高斯奖励:本文假设奖励噪声是次高斯的。在许多实际应用中,奖励可能是二值的(如点击/不点击)或重尾的。如何将本文的算法扩展到广义线性模型(如逻辑回归)或重尾分布?这可能需要使用不同的估计方法(如
MLE)和不同的遗憾分析工具。(扎根于:Section 1,作者提及“extending to generalized linear models is a natural next step”。) -
计算-统计权衡:本文的
tensor elimination算法需要每轮进行张量补全的SGD,其计算复杂度为O(N * K * R * max_k d_k),其中N是探索样本总数。当T很大时,计算成本可能成为瓶颈。是否存在计算复杂度更低(如O(poly(K, R, max_k d_k)))的算法,同时保持接近最优的遗憾界?这可能涉及使用更高效的张量分解算法(如ALS)或设计新的探索策略。(扎根于:Section 4,作者提及“computational efficiency is a practical concern”。)
Maintained by 陈星宇 · Homepage · Source on GitHub