方差削减(Variance Reduction)
在分布p上采样估计f的期望Epf(x)时,可以用一些方法降低通过估计的方差
Epf(x)=Eq[q(x)p(x)f(x)]
方差为
Dq[q(x)p(x)f(x)]=Eq[q(x)p(x)f(x)]2−Ep2f(x)
若f(X)≥0,则由Jensen不等式,当且仅当
q(X)=Epf(X)p(X)f(X)
时方差为0。
直观理解重要性:从未归一项p(X)f(X)可以看出,最稳定的采样应多采概率大且函数值影响大的。
例子:FastGCN, AS-GCN, GraphSAINT等
基线(Baseline)
引入已知期望的函数g(X),令
f^(X)=f(X)−α(g(X)−Eg(X))
易知期望不变Ef^(X)=Ef(X),方差是关于α的抛物线
Df^(X)=Df(X)−2αcov(f(X),g(X))+α2Dg(X)
因此α=αopt=Dg(X)cov(f(X),g(X))时方差最小,为
Df^(X)=(1−corr(f(X),g(X)))Df(X)
由于α=0时f不变,由抛物线的性质知取α∈(0,2αopt)得到的f^都可以减小方差。
因此,选择与f相关的g,取合适的α得到f^可减小方差。f, g的相关性越高,方差越小。
直观理解g:可以理解g为从f中抽取的部分随机性,剩下的部分波动减小、方差变小。
例子:带基线的REINFORCE算法、VR-GCN等