為什麼需要平滑？

某個物品CTR（click-Through-Rate）定義為“物品被點選的機率”。CTR是某個物品在其他條件保持不變下自身的屬性。但是機率我們不好確定，能確定的是頻率。根據大數定理，隨著實驗次數的增加，頻率會逐漸穩定到機率附近。所以我們用一般物品被點選的頻率

\frac{Click}{Imp}

來表示它的CTR，即

CTR=\frac{Click}{Imp}

（公式1）

我們當然希望CTR越大越好，由上面的公式我們可知CTR的大小實際上由兩部分決定。首先是展示的次數，英文裡用了impression，直譯為給人留下的印象，我們可以理解為曝光並且被使用者看到，是有效的曝光。其次是被點選的次數。如果有一件物品a 曝光了1次，並且被點了，那它的CTR就是100%。而另外一件物品b曝光了1000次，被點選了100次，它的CTR就是10%。那我們能說物品a的CTR比物品b的CTR更高嗎？顯然不能，一次被曝光並且被點選，這其中包含了很大的不確定性。根據大數定律，在實驗次數不斷增加下，頻率才會穩定在機率附近。顯示CTR等於100%這個資料，只是在一次實驗中得到，它偏離真實CTR的可能性非常高。

那麼怎麼能獲得更可靠的結論呢？一種顯然的想法是提高物品a的曝光，增大實驗次數，讓頻率更接近機率。但是大多數時候曝光不是你想增加，增加就能增加的。

指數平滑

另外一種樸素的想法是我們假定物品的CTR在一定時間內是不變的，我們可以利用歷史的資料來修正今天的CTR。今天的CTR實際上CTR的觀測值。根據這個思路我們首先想到了指數平滑

\begin{align} CTR_{t} & = p*CTR_{t-1} + (1-p)\frac{Click}{Imp} \\ & = \sum_{T=1}^{t}p^{t-T}\frac{Click_{T}}{Imp_{T}} \\ \end{align}

（公式2）

可以看出來隨著時間的推移，歷史的資訊在很快的衰減。

為什麼利用beta分佈得到的結果是

\frac{\alpha+C-1}{\alpha+\beta+I-2}

beta分佈是在0-1之間

CTR平滑的原理，包懂！！！附程式碼

beta分佈的機率密度函式

我們假設某件物品的CTR服從引數為

\alpha和\beta

的beta分佈，即有

CTR _{r} \sim Beta(\alpha,\beta)

p(r|\alpha,\beta) = \frac{\Gamma(\alpha+\beta)}{\Gamma(\alpha)\Gamma(\beta)}r^{\alpha-1}(1-r)^{\beta-1}

（公式3）

那麼每次曝光可以看成從服從

\alpha

和

\beta

的beta分佈裡的一次隨機抽樣。顯然被點選的次數服從引數為

I

和r的n重伯努利分佈，其中

I

和r都是已知條件

C \sim Binomial(I,r),P(C|I,r)= \dbinom{I}{C}r^{C}(1-r)^{I-C}

（公式4）

曝光

Imp

和點選率是獨立的，

p(I,r)=p(I)*p(r)

（公式5）

明確我們的目標是要求在已知曝光

Imp

和點選

Click

下點選率

r

的估計，根據貝葉斯公式

\begin{align} p(r|I,C) & = \frac{p(r,I,C)}{p(I,C)} \\ & = \frac{p(C|I,r)*p(I,r)}{p(I,C)} \\ & = \frac{p(C|I,r)*p(r)*p(I)}{\int_{0}^{1} p(C|I,r)*p(I)*p(r)\, dr}\\ & = \frac{p(C|I,r)*p(r)}{{\int_{0}^{1} p(C|I,r)*p(r)\, dr}} \\ &= \frac{\binom{I}{C}r^{C}(1-r)^{I-C}*\frac{1}{B(\alpha,\beta)}r^{\alpha-1}(1-r)^{\beta-1}}{\int_0^1 \binom{I}{C}r^{C}(1-r)^{I-C}*\frac{1}{B(\alpha,\beta)}r^{\alpha-1}(1-r)^{\beta-1}\,dr} \\ &=\frac{r^{C+\alpha-1}(1-r)^{I+\beta-C-1}}{B(C+\alpha,I+\beta-C)} \\ &= Beta(r|C+\alpha,I+\beta+C) \end{align}

（公式6）

其中B表示Beta函式，可見新的點選率也服從Beta分佈，當我們得到

\alpha和\beta

之後，就可以確定點選率的分佈了。

對於引數為

\alpha和\beta

的Beta分佈的它的眾數是

\frac{\alpha-1}{\alpha+\beta-2}

，它的平均數是

\frac{\alpha}{\alpha+\beta}

。所以我們可以拿

\frac{\alpha+C-1}{\alpha+\beta+I-2}

或者

\frac{\alpha+C}{\alpha+\beta+I}

來作為平滑之後的CTR。

如何計算

\alpha和\beta

？

假設我們擁有的是時間序列格式的資料，每天點選數獨立同分布，所以有如下的機率密度函式，根據極大似然估計的原理。我們使下式取到最大值

\begin{align} p(C_1,...,C_T|I_1,...,I_T,\alpha,\beta) & = \prod_{i=1}^T p(C_i|I_i,\alpha,\beta) \\ & =\prod_{i=1}^T \int_0^1 \,p(C_i,r_i|I_i,\alpha,\beta)dr_i \\ &=\prod_{i=1}^T\int_0^1 p(C_i|I_i,r_i)p(r_i|\alpha,\beta)\,dr_i \\ & =\prod_{i=1}^T\int_0^1\binom{I_i}{C_i}r^{C_i}(1-r)^{I_i-C_i}\frac{1}{B(\alpha,\beta)}r^{\alpha-1}(1-r)^{\beta-1}\,dr_i \\ &= \prod_{i=1}^T\binom{I_i}{C_i}\frac{B(C_i+\alpha,I_i-C_i+\beta)}{B(\alpha,\beta)} \end{align}

（公式7）

上式對

\alpha和\beta

求導有

\frac{d\log P(C_1,C_2,..,C_N|I_1,I_2,..,I_N)}{d\alpha}=\sum_{i=1}^{N}[\Psi(\alpha+\beta)-\Psi(I_i+\alpha+\beta)+\Psi(C_i+\alpha)-\Psi(\alpha)]

\frac{d\log P(C_1,C_2,..,C_N|I_1,I_2,..,I_N)}{d\beta}=\sum_{i=1}^{N}[\Psi(\alpha+\beta)-\Psi(I_i+\alpha+\beta)+\Psi(I_i-C_i+\beta)-\Psi(\beta)]

其中

\Psi(x)=\frac{d}{dx}\ln\Gamma(x)

對

\alpha和\beta

迭代求解

\alpha_{new}=\alpha\frac{\sum_{i=1}^N[\Psi(C_i+\alpha)-\Psi(\alpha)]}{\sum_{i=1}^N[\Psi(I_i+\alpha+\beta)-\Psi(\alpha+\beta)]}

\beta_{new}=\beta\frac{\sum_{i=1}^N[\Psi(I_i-C_i+\beta)-\Psi(\beta)]}{\sum_{i=1}^N[\Psi(I_i+\alpha+\beta)-\Psi(\alpha+\beta)]}

import

scipy。special

as

special

def

update

（

clicks

，

imps

，

init_alpha

，

init_beta

，

epoches

，

epsilon

）：

assert

len

（

clicks

）

==

len

（

imps

），

print

（

“length not equal”

）

alpha

，

beta

=

init_alpha

，

init_beta

last_alpha

=

last_beta

=

0

for

i

in

range

（

epoches

）：

normalization

=

sum

（［

special

。

digamma

（

imps

［

i

］

+

alpha

+

beta

）

-

special

。

digamma

（

alpha

+

beta

）

for

i

in

range

（

len

（

clicks

））］）

alpha

=

alpha

*

（

1

/

normalization

）

*

sum

（［

special

。

digamma

（

clicks

［

i

］

+

alpha

）

-

special

。

digamma

（

alpha

）

for

i

in

range

（

len

（

clicks

））］）

beta

=

beta

*

（

1

/

normalization

）

*

sum

（［

special

。

digamma

（

imps

［

i

］

-

clicks

［

i

］

+

beta

）

-

special

。

digamma

（

beta

）

for

i

in

range

（

len

（

clicks

））］）

if

abs

（

last_alpha

-

alpha

）

<

epsilon

or

abs

（

last_beta

-

beta

）

<

epsilon

：

break

last_alpha

=

alpha

last_beta

=

beta

return

alpha

，

beta

寫在最後

計算

\alpha和\beta

時用到的極大似然函式也可以用我們在推導平滑CTR用到的公式6，最後對

\alpha和\beta

的迭代求求我也沒太搞清楚，有興趣的朋友可以看下第一個參考文獻。

參考文獻

Environmental I S 。 Click-Through Rate Estimation for Rare Events in Online Advertising［J］。 Online Multimedia Advertising Techniques & Technologies， 2011。

如何理解Beta分佈和Dirichlet分佈？-czxttkl-搜狐部落格