一、广告计算的基本概念
1、广告的形式
在互联网发展的过程中，广告成为了互联网企业盈利的一个很重要的部分，根据不同的广告形式，互联网广告可以分为：
- 展示广告(display ads)
- 赞助商搜索广告(sponsored search)
- 上下文广告(contextual advertising)
2、竞价模型
对于在线广告，主要有如下的几种竞价模型：
- 按展示付费(pay-per-impression)：直观来讲，按展示付费是指广告商按照广告被展示的次数付费，这是一种最普遍的竞价模型；
- 按行为付费(pay-per-action)：按行为付费是指只有在广告产生了销售或者类似的一些转化时，广告商才付费；
当然，对于以上的两种竞价模型各有其局限性：在按展示付费模型中，压根没有考虑到广告的效果，只是按照广告流量进行售卖的模式；对于按行为付费模型，虽然其考虑到了广告效果，但其的条件是产生了某种转化，这种转化有时很难追踪和记录。此时，为了解决这两种模型的局限性，通常可以按照一个用户是否会点击广告作为最终的度量标准，即按点击付费模型(pay-per-click)。
- 按点击付费(pay-per-click)：根据用户是否会点击广告来付费。
这里便出现了一个重要的概念，便是广告点击率(the click-through rate, CTR)。
3、广告点击率(CTR)
广告点击率CTR是度量一个用户对于一个广告的行为的最好的度量方法，广告点击率可以定义为：对于一个广告的被点击(click)的次数于被展示(impression)的次数的比值。
CTR=#click#impression
CTR=frac{#; click}{#; impression}
广告点击率对于在线广告有着重要的作用，在网络中，对于有限的流量，通常要选择出最优质的广告进行投放，此时，CTR可以作为选择广告和确定广告顺序的一个重要的标准。
但是在计算CTR时，由于数据的稀疏性，利用上述的计算方法得到的CTR通常具有较大的偏差，这样的偏差主要表现在如下的两种情况：
- 1、例如展示impression的次数很小，如11次，其中，点击的次数也很小(这里的很小是指数值很小)，如11，按照上述的CTR的计算方法，其CTR为11，此时的点击率就被我们估计高了；
- 2、例如展示的次数很大，但是点击的次数很小，此时，利用上述的方法求得的CTR就会比实际的CTR要小得多。
出现上述两种现象的主要原因是我们对分子impression和分母click的估计不准确引起的，部分原因可能是曝光不足等等，对于这样的问题，我们可以通过相关的一些广告的展示和点击数据对CTR的公式进行平滑处理。
二、CTR的平滑方法
1、数据的层次结构——贝叶斯平滑
假设有NN个相同的账号(a1,a2,⋯,aN)left ( a_1,a_2,cdots , a_N right )，对于网页pp，对于这样的网页和账号组(p,ai)left ( p,a_i right )。假设(C1,C2,⋯,CN)left ( C_1,C_2,cdots , C_Nright )为观测到点击数据，(r1,r2,⋯,rN)left ( r_1,r_2,cdots , r_Nright )为隐含的CTR的值，为点击率，点击率在此是一个隐含的参数，广告是否被点击满足二项分布，即Binomial(Ii,ri)Binomialleft ( I_i,r_i right )，其中，IiI_i表示广告被展示的次数。
贝叶斯思想认为，隐含的参数不是一个具体的值，而是满足某个分布，我们知道贝叶斯参数估计的基本过程为：
先验分布 数据的知识=后验分布
已知二项分布的共轭分布为Beta分布，对此，有以下的两点假设：
- 1、对于一个广告，其点击CiC_i符合二项分布Binomial(Ii,ri)Binomialleft ( I_i,r_i right )，其中，IiI_i表示的是展示的次数，rir_i表示的是广告被点击的概率；
- 2、对于所有的广告，有其自身的CTR，其CTR满足参数是αalpha 和βbeta 的贝塔分布Beta(α,β)Betaleft ( alpha , beta right )。
假设有NN个广告，广告被展示的次数为(I1,I2,⋯,IN)left ( I_1,I_2,cdots , I_N right )，广告被点击的次数为(C1,C2,⋯,CN)left ( C_1,C_2,cdots , C_N right )，上述的两个假设可以表示为如下的形式：
其对应的概率图模型为：
点击率rir_i不仅与(Ii,Ci)left ( I_i,C_i right )相关，而且与参数αalpha 和参数βbeta 相关，我们可以通过计算得到参数αalpha 和参数βbeta 的估计α^hat{alpha }和β^hat{beta }，一旦α^hat{alpha }和β^hat{beta }被确定后，则rir_i的估计为：
ri=Ci α^Ii α^ β^
r_i=frac{C_i hat{alpha }}{I_i hat{alpha } hat{beta }}
所以，现在，我们需要求解参数αalpha 和参数βbeta 的估计α^hat{alpha }和β^hat{beta }。
点击CC的似然函数为：P(C1,C2,⋯,CN∣I1,I2,⋯,IN,α,β)mathbb{P}left ( C_1,C_2,cdots ,C_Nmid I_1,I_2,cdots ,I_N,alpha ,beta right )，由于点击的次数以及展示的次数之间都是相互独立的，因此上式可以表示为：
P(C1,C2,⋯,CN∣I1,I2,⋯,IN,α,β)=∏i=1NP(Ci∣Ii,α,β)=∏i=1N∫riP(Ci,ri∣Ii,α,β)dri=∏i=1N∫riP(Ci,∣ri,Ii)P(ri∣α,β)dri
begin{matrix} mathbb{P}left ( C_1,C_2,cdots ,C_Nmid I_1,I_2,cdots ,I_N,alpha ,beta right )\ =prod_{i=1}^{N}mathbb{P}left ( C_imid I_i,alpha ,beta right )\ =prod_{i=1}^{N}int_{r_i} mathbb{P}left ( C_i,r_imid I_i,alpha ,beta right )dr_i\ =prod_{i=1}^{N}int_{r_i} mathbb{P}left ( C_i,mid r_i,I_i right ) mathbb{P}left ( r_imid alpha ,beta right )dr_i end{matrix}
已知
P(Ci,∣ri,Ii)=rCii(1−ri)Ii−Ci
mathbb{P}left ( C_i,mid r_i,I_i right )=r_i^{C_i}left ( 1-r_i right )^{I_i-C_i}
P(ri∣α,β)=Γ(α β)Γ(α)Γ(β)rα−1i(1−ri)β−1
mathbb{P}left ( r_imid alpha ,beta right )=frac{Gamma left ( alpha beta right )}{Gamma left ( alpha right )Gamma left ( beta right )}r_i^{alpha -1}left ( 1-r_i right )^{beta -1}
则上式可以写成：
=∏i=1N∫riP(Ci,∣ri,Ii)P(ri∣α,β)dri=∏i=1N∫rirCii(1−ri)Ii−CiΓ(α β)Γ(α) Γ(β)rα−1i(1−ri)β−1dri=∏i=1N∫riΓ(α β)Γ(α)Γ(β)rCi α−1i(1−ri)Ii−CI β−1dri=∏i=1NΓ(α β)Γ(Ii α β)Γ(Ci α)Γ(α)Γ(Ii−Ci β)Γ(β)
begin{matrix} =prod_{i=1}^{N}int_{r_i} mathbb{P}left ( C_i,mid r_i,I_i right ) mathbb{P}left ( r_imid alpha ,beta right )dr_i\ =prod_{i=1}^{N}int_{r_i} r_i^{C_i}left ( 1-r_i right )^{I_i-C_i}frac{Gamma left ( alpha beta right )}{Gamma left ( alpha right ) Gamma left ( beta right )}r_i^{alpha -1}left ( 1-r_i right )^{beta -1}dr_i\ =prod_{i=1}^{N}int_{r_i}frac{Gamma left ( alpha beta right )}{Gamma left ( alpha right )Gamma left ( beta right )}r_i^{C_i alpha-1}left ( 1-r_i right )^{I_i-C_I beta-1}dr_i\ =prod_{i=1}^{N}frac{Gamma left ( alpha beta right )}{Gamma left (I_i alpha beta right )}frac{Gamma left ( C_i alpha right )}{Gamma left ( alpha right )}frac{Gamma left ( I_i-C_i beta right )}{Gamma left ( beta right )} end{matrix}
此时，我们需要求得该似然函数的最大值，首先，我们对上述的似然函数取对数，即为：
logP(C1,C2,⋯,CN∣I1,I2,⋯,IN,α,β)=∑i=1NlnΓ(α β)−lnΓ(Ii α β) lnΓ(Ci α)−lnΓ(α) lnΓ(Ii−Ci β)−lnΓ(β)
begin{matrix} log; mathbb{P}left ( C_1,C_2,cdots ,C_Nmid I_1,I_2,cdots ,I_N,alpha ,beta right )\ =sum_{i=1}^{N}ln;Gamma left ( alpha beta right )-ln; Gamma left (I_i alpha beta right ) ln; Gamma left ( C_i alpha right )-ln; Gamma left ( alpha right ) ln; Gamma left ( I_i-C_i beta right )-ln; Gamma left ( beta right ) end{matrix}
将上述的log似然函数分别对αalpha 和βbeta 求导数，即为：
dlogP(C1,C2,⋯,CN∣I1,I2,⋯,IN,α,β)dα=∑i=1NΨ(α β)−Ψ(Ii α β) Ψ(Ci α)−Ψ(α)
begin{matrix} frac{d; log; mathbb{P}left ( C_1,C_2,cdots ,C_Nmid I_1,I_2,cdots ,I_N,alpha ,beta right )}{d; alpha}\ =sum_{i=1}^{N}Psi left ( alpha beta right )-Psi left (I_i alpha beta right ) Psi left ( C_i alpha right )-Psi left ( alpha right ) end{matrix}
dlogP(C1,C2,⋯,CN∣I1,I2,⋯,IN,α,β)dβ=∑i=1NΨ(α β)−Ψ(Ii α β) Ψ(Ii−Ci β)−Ψ(β)
begin{matrix} frac{d; log; mathbb{P}left ( C_1,C_2,cdots ,C_Nmid I_1,I_2,cdots ,I_N,alpha ,beta right )}{d; beta}\ =sum_{i=1}^{N}Psi left ( alpha beta right )-Psi left (I_i alpha beta right ) Psi left ( I_i-C_i beta right )-Psi left ( beta right ) end{matrix}
其中，Ψ(x)=ddxlnΓ(x)Psi left ( xright )=frac{d}{d; x}ln; Gamma left ( x right )。通过the fixed-point iteration方法，可以得到如下的结果：
αnew=α∑Ni=1[Ψ(Ci α)−Ψ(α)]∑Ni=1[Ψ(Ii α β)−Ψ(α β)]
alpha ^{new}=alphafrac{sum_{i=1}^{N}left [ Psi left ( C_i alpha right )-Psi left ( alpha right ) right ]}{sum_{i=1}^{N}left [ Psi left ( I_i alpha beta right )-Psi left ( alpha beta right ) right ]}
βnew=β∑Ni=1[Ψ(Ii−Ci β)−Ψ(β)]∑Ni=1[Ψ(Ii α β)−Ψ(α β)]
beta ^{new}=beta frac{sum_{i=1}^{N}left [ Psi left ( I_i-C_i beta right )-Psi left ( beta right ) right ]}{sum_{i=1}^{N}left [ Psi left ( I_i alpha beta right )-Psi left ( alpha beta right ) right ]}
上述的求解过程是一个迭代的过程，一旦求出了参数αalpha 和参数βbeta 的估计α^hat{alpha }和β^hat{beta }，便可以求出点击率的估计：
ri=Ci α^Ii α^ β^
r_i=frac{C_i hat{alpha }}{I_i hat{alpha } hat{beta }}
2、数据在时间上的一致性——指数平滑
相比上述的贝叶斯平滑，指数平滑相对要简单点，对于CTR中的点击，这是个与时间相关的量，假设对于一个广告，有MM天的点击和展示数据(I1,I2,⋯,IM)left ( I_1,I_2,cdots ,I_M right )，(C1,C2,⋯,CM)left ( C_1,C_2,cdots ,C_M right )。若要估计第MM天的CTR的值，我们需要对分别对II和CC进行平滑，得到平滑后的I^hat{I}和C^hat{C}。其计算方法如下：
{C^j=CjC^j=γCj (1−γ)C^j−1 if j=1 if j=2,⋯,M
begin{cases} hat{C}_j=C_j & text{ if } j=1 \ hat{C}_j=gamma C_j left ( 1-gamma right ) hat{C}_{j-1}& text{ if } j=2,cdots , M end{cases}
{I^j=IjI^j=γIj (1−γ)I^j−1 if j=1 if j=2,⋯,M
begin{cases} hat{I}_j=I_j & text{ if } j=1 \ hat{I}_j=gamma I_j left ( 1-gamma right ) hat{I}_{j-1}& text{ if } j=2,cdots , M end{cases}
其中，γgamma 称为平滑因子，且0<γ<10< gamma <1。对于上述的公式，若要计算第MM天的平滑点击，可以得到下面的公式：
C^M=γCM (1−γ)C^M−1=γCM (1−γ)(γCM−1 (1−γ)C^M−2)=γCM γ(1−γ)CM−1 ⋯ γ(1−γ)jCM−j ⋯ γ(1−γ)M−1C1
begin{matrix} hat{C}_M=gamma C_M left ( 1-gamma right )hat{C}_{M-1}\ =gamma C_M left ( 1-gamma right )left ( gamma C_{M-1} left ( 1-gamma right ) hat{C}_{M-2}right )\ =gamma C_M gamma left ( 1-gamma right )C_{M-1} cdots gamma left ( 1-gamma right )^jC_{M-j} cdots gamma left ( 1-gamma right )^{M-1}C_1 end{matrix}
参考文献
- Click-Through Rate Estimation for Rare Events in Online Advertising.Xuerui Wang, Wei Li, Ying Cui, Ruofei (Bruce) Zhang, Jianchang Mao Yahoo! Labs, Silicon Valley United States
