离散价格模型与价格空间预测

本文为笔记。

原论文：《Deep Landscape Forecasting for Real-time Bidding Advertising》
Authors: Kan Ren, Jiarui Qin, Lei Zheng, Zhengyu Yang, Weinan Zhang, Yong Yu
https://arxiv.org/abs/1905.03028
KDD2019

这篇文章讲的是广告竞价里，怎么预测整个价格空间。
现在的二次竞价制度，第一名的出价是第二名的出价+一个很小的增益值。
也就是说，第二名的价格就是胜者面对的“市场价格”，超过这个市场价格，就能获胜。

怀疑原文应该是笔误了，有多处符号的下标序号写错。
所以我按自己的理解再推一次。

一、理论部分

1.1

先定义market price (市场价格) 为变量z，显然z>0
于是z的概率密度函数可以定义为
$p(z) ,z>0$p(z),z>0
为了简便起见，概率密度函数 Probability Density Function下文简称 P.D.F. （笑出声）。

于是可以推导出以出价b获胜与竞价失败的概率。

$w(b) \doteq Pr(z&lt;b) = \int_{0}^{b} p(z)dz \qquad$w(b)≐Pr(z<b)=∫0b​p(z)dz
$s(b) \doteq Pr(z&lt;b) = \int_{0}^{b} p(z)dz \qquad$s(b)≐Pr(z<b)=∫0b​p(z)dz
(公式4)

1.2

整个市场价格空间中，分布着一系列的价格 $b1,b2,b3,...,bl$b1,b2,b3,...,bl ，为了使模型更合理，我们显然可以在某一个角度，把这些价格全部看做整数，即 $b_{l}-b_{l-1} =1$bl​−bl−1​=1。

个人补充

为什么可以看做整数？因为人类社会存在精度precision概念。
哪怕你的cpc广告出价是1块3毛每千次点击，这个1块3毛也可以转成1.03（元），转成103（分）。那么下一个出价就是104(分)。
在max精度的视角下，总可以得到一系列离散的整数。

我们人为地约定 $b_{0} = 0$b0​=0

然后，定义离散价格区间（internal）
$V_{l} = \lbrack b_{l},b_{l+1})$Vl​=[bl​,bl+1​)

这里原文是左开右闭，我认为应该是左闭右开才符合逻辑。
因为z = b的时候，当前b就成了第二名的出价，显然b无法获胜。
你们也可以自己推一遍

那么现在我们就有了新的win和lose概率公式

给定出价bl：
$w(b_{l}) = Pr(z&lt;b_{l}) = \sum_{j=0}^{l-1} (z \in V_{j}) \qquad$w(bl​)=Pr(z<bl​)=j=0∑l−1​(z∈Vj​)
$s(b_{l}) = Pr(z&gt;=b_{l}) = \sum_{j=l}^{\infty} (z \in V_{j}) \qquad$s(bl​)=Pr(z>=bl​)=j=l∑∞​(z∈Vj​)

我们再定义，z恰好落在$V_{l}$Vl​区间内的概率为
$p_{l} \doteq Pr(Z \in V_{l}) = W(b_{l+1}) - W(b_{l}) \\ = [1-S(b_{l+1}) ] - [1-S(b_{l})] \\ =S(b_{l}) - S(b_{l+1})$pl​≐Pr(Z∈Vl​)=W(bl+1​)−W(bl​)=[1−S(bl+1​)]−[1−S(bl​)]=S(bl​)−S(bl+1​)
(公式5)

于是我们的模型转化为了
给定一组数据 ${(x,b,z)}$(x,b,z) ，求概率密度函数$p(z)$p(z)。
细一点说就是，对 $i \ th \ samle$i th samle，求 $P.D.F. of z^i，p(z^i | x^i)$P.D.F.ofzi，p(zi∣xi)。

其中作为label的z对win case是可见的，对lose case是不可知的，被设为null。
因为广告竞价失败的广告主，只知道自己这个价格不行，不知道哪个价格可以。

可是我们知道，p(z)不好直接求，需要对其进行进一步的转化。

我们构造辅助变量$h_{l}$hl​，约定其现实意义为，已知出价$b_{l-1}$bl−1​失败，那么出价$b_{l}$bl​ 恰好获胜的概率。

$h_{l} = Pr(z \in V_{l-1} | z \ge b_{l-1}) \\ = \frac {Pr(z \in V_{l-1})}{Pr(z \ge b_{l-1})} = \frac {p_{l-1}}{S_{b_{l-1}}}$hl​=Pr(z∈Vl−1​∣z≥bl−1​)=Pr(z≥bl−1​)Pr(z∈Vl−1​)​=Sbl−1​​pl−1​​
(公式6)

备注

原文定义的 $h_{l} = \frac {p_{l}}{ s_{b_{l-1}}}$hl​=sbl−1​​pl​​
可是若按照$V_{l}$Vl​的空间划分和$h_{l}$hl​的现实意义来看，分子的下标应该是$l-1$l−1而非$l$l

1.3

完成了上面的准备公式，下面可以正式将问题的数学建模，转换成神经网络可以操作的形式。

作者引入RNN模型，因为一堆参考文献123456789都表现的挺好，而且我们的公式中可以看出来，离散价格区间有明显的序列特征。用n-1去推n正是RNN擅长的事情。

将RNN网络看成一个大的函数 $f_{\theta}$fθ​，则可以将公式（6）进一步写成。

$h_{l}^i = Pr( z \in V_{l-1} | z \ge b_{l-1},x^i;\theta) \\ =f_{\theta} (x^i,b_{l} | r_{l-1})$hli​=Pr(z∈Vl−1​∣z≥bl−1​,xi;θ)=fθ​(xi,bl​∣rl−1​)
公式（7）

第二步的下标为什么加一了？

我们的$h_{l}$hl​的现实意义是，已知出价$b_{l-1}$bl−1​失败，那么出价$b_{l}$bl​ 恰好获胜的概率。
对应到 $f_{\theta}$fθ​中，$r_{l-1}$rl−1​就是上一个RNN Cell传过来的 "$b_{l-1}$bl−1​失败了"的信息， $f_{\theta}$fθ​要去计算出价$b_{l}$bl​ 恰好获胜的概率。

本文选用的RNN Cell是标准的LSTM Unit。

重点
由公式(4),(6),(7)可以推出以出价$b_{l}$bl​失败的概率
$S(b_{l} | x^i;\theta) = Pr( z \ge b_{l} | x^i;\theta) \\ = Pr( z \notin V_{1}, z \notin V_{2},...,z \notin V_{l-1} | x^i ;\theta) \\ = Pr(z \notin V_{1} |x^i ;\theta)*Pr(z \notin V_{2},...,z \notin V_{l-1} | z \notin V_{1},x^i ;\theta ) \\ =Pr(z \notin V_{1} | x^i ;\theta)*Pr(z \notin V_{2} | z \notin V_{1},x^i;\theta)*Pr(z \notin V_{3},...,z \notin V_{l-1} | z \notin V_{1},z \notin V_{2},x^i ;\theta ) \\ = Pr(z \notin V_{1} | x^i ;\theta)*Pr(z \notin V_{2} | z \notin V_{1},x^i;\theta)*Pr(z \notin V_{3} | z \notin V_{1},z \notin V_{2}, x^i ;\theta)*...*Pr(z \notin V_{l-1} | z \notin V_{1},z \notin V_{2}, ...,z \notin V_{l-2},x^i ;\theta) \\ =Pr(z \notin V_{1} | x^i ;\theta) *Pr(z \notin V_{2} | z \ge b_{2},x^i ;\theta)*Pr(z \notin V_{3} | z \ge b_{3},x^i;\theta)*...*Pr(z \notin V_{l-1} | z \ge b_{l-1},x^i;\theta)\\ =\prod_{k=1}^{l-1} Pr(z \notin V_{k} | z \ge b_{k},x^i;\theta) \\ =\prod_{k=1}^{l-1} [ 1 - Pr (z \in V_{k} | z \ge b_{k},x^i;\theta) ]\\ \xlongequal{公式(6),(7)} \prod_{k=1}^{l-1} [1-h_{k+1}^i] \\ \xlongequal{} \prod_{0&lt;k&lt;l}^{} [1-h_{k+1}^i]$S(bl​∣xi;θ)=Pr(z≥bl​∣xi;θ)=Pr(z∈/​V1​,z∈/​V2​,...,z∈/​Vl−1​∣xi;θ)=Pr(z∈/​V1​∣xi;θ)∗Pr(z∈/​V2​,...,z∈/​Vl−1​∣z∈/​V1​,xi;θ)=Pr(z∈/​V1​∣xi;θ)∗Pr(z∈/​V2​∣z∈/​V1​,xi;θ)∗Pr(z∈/​V3​,...,z∈/​Vl−1​∣z∈/​V1​,z∈/​V2​,xi;θ)=Pr(z∈/​V1​∣xi;θ)∗Pr(z∈/​V2​∣z∈/​V1​,xi;θ)∗Pr(z∈/​V3​∣z∈/​V1​,z∈/​V2​,xi;θ)∗...∗Pr(z∈/​Vl−1​∣z∈/​V1​,z∈/​V2​,...,z∈/​Vl−2​,xi;θ)=Pr(z∈/​V1​∣xi;θ)∗Pr(z∈/​V2​∣z≥b2​,xi;θ)∗Pr(z∈/​V3​∣z≥b3​,xi;θ)∗...∗Pr(z∈/​Vl−1​∣z≥bl−1​,xi;θ)=k=1∏l−1​Pr(z∈/​Vk​∣z≥bk​,xi;θ)=k=1∏l−1​[1−Pr(z∈Vk​∣z≥bk​,xi;θ)]公式(6),(7)k=1∏l−1​[1−hk+1i​]0<k<l∏​[1−hk+1i​]
$W(b_{l} | x^i;\theta) = 1 - S(b_{l} | x^i;\theta) \\ = 1- \prod_{0&lt;k&lt;l}^{} [1-h_{k+1}^i]$W(bl​∣xi;θ)=1−S(bl​∣xi;θ)=1−0<k<l∏​[1−hk+1i​]公式(8)

对公式(8)的备注

在现实生活中，市场价格不可能为0，所以我们知道$z\ge b_{1}$z≥b1​是必然事件，
$Pr(z\ge b_{1})=1$Pr(z≥b1​)=1
所以公式中的推导中的第一项可以写成
$Pr(z \notin V_{1} | x^i ;\theta) = Pr(z \notin V_{1} | z\ge b_{1}, x^i ;\theta)$Pr(z∈/​V1​∣xi;θ)=Pr(z∈/​V1​∣z≥b1​,xi;θ)
所以可以合并为k=1时，连乘号里的项。

再放一次图防止忘记。

现在有了公式(8)，它的价值在于，现在我们可以用RNN 网络的输出值 $h_{l}$hl​ 来计算测试集的某条记录的win和lose概率了。相当于是一个连接器bridge。

我们再由公式(5),(6)可知，对第i个样本而言，$z^i$zi刚好落在区间$V_{l-1}$Vl−1​的概率:
$p_{l-1}^i = Pr(z^i \in V_{l-1} | x^i;\theta) = h_{l}^i \cdot S_{b_{l-1}}^i \\ =h_{l}^i \prod_{0&lt;k&lt;l-1}^{} [1-h_{k+1}^i] \\ =h_{l}^i \prod_{1&lt;k&lt;l}^{} [1-h_{k}^i]$pl−1i​=Pr(zi∈Vl−1​∣xi;θ)=hli​⋅Sbl−1​i​=hli​0<k<l−1∏​[1−hk+1i​]=hli​1<k<l∏​[1−hki​]
公式(9)

1.4

完成了RNN网络的准备部分，现在我们可以引入loss function了。

原文分为2个视角进行定义。

吐槽，C.D.F.的概念第一次出现在第5页，却在第9页才写备注，还得猜半天这什么意思

1.4.1 先从P.D.F. 概率密度函数的角度看。

我们使用negative log-likehood (负对数似然)作为loss。
显然给定一个win样本，我们就知道了出价$b_{l}$bl​能获胜。
鉴于二次竞价游戏规则中，胜者价格只比第二名高出一点点，那么市场价格是$b_{l-1}$bl−1​。
我们就希望网络预测的 $Pr(z \in V_{l-1} | x^i;\theta) \to 1$Pr(z∈Vl−1​∣xi;θ)→1

把m个样本的$Pr(z \in V_{l-1} | x^i;\theta)$Pr(z∈Vl−1​∣xi;θ)全部乘起来，得到
$L1 = -log \prod_{ x^i,z^i \in \Bbb{D}_{win}} Pr(z^i \in V_{l-1} | x^i;\theta) \\ = -log \prod_{ x^i,z^i \in \Bbb{D}_{win}} p_{l-1}^i \\ \xlongequal{公式(9)} -log \prod_{ x^i,z^i \in \Bbb{D}_{win}} \{ h_{l}^i \prod_{1&lt;k&lt;l}^{} (1-h_{k}^i) \} \\ = - \sum_{x^i,z^i \in \Bbb{D}_{win}} \{ logh_{l}^i + log \prod_{1&lt;k&lt;l} (1-h_{k}^i) \} \\ = - \sum_{x^i,z^i \in \Bbb{D}_{win}} \{ logh_{l}^i + \sum_{1&lt;k&lt;l} log(1-h_{k}^i) \}$L1=−logxi,zi∈Dwin​∏​Pr(zi∈Vl−1​∣xi;θ)=−logxi,zi∈Dwin​∏​pl−1i​公式(9)−logxi,zi∈Dwin​∏​{hli​1<k<l∏​(1−hki​)}=−xi,zi∈Dwin​∑​{loghli​+log1<k<l∏​(1−hki​)}=−xi,zi∈Dwin​∑​{loghli​+1<k<l∑​log(1−hki​)}
公式(10)

于是我们可以用RNN的输出$h_{k}^i$hki​来计算L1损失，其中k表示第k个价格区间。

1.4.2 视角2 从C.D.F的角度看

先解释C.D.F. (corresponding winning probability)，简而言之就是获胜概率。
整篇文章的公式只有2类。
第1类就是P.D.F.的，以z为主体，问 $z \in V_{l}$z∈Vl​的概率。
第2类就是C.D.F的，以bid为主体，问以出价$b_{l}$bl​获胜、失败的概率。
举例就去看1.3部分，里面的公式(8)属于C.D.F获胜概率，公式(9)属于P.D.F.落在某个价格区间的概率。

显然，对win case而言，我们希望
$Pr(z^i &lt;b^i_{l} | x^i;\theta) \to 1$Pr(zi<bli​∣xi;θ)→1
对lose case而言，我们希望
$Pr(z^i \ge b_{l}^i | x^i;\theta) \to 1$Pr(zi≥bli​∣xi;θ)→1

于是可以定义:
$L_{win} = -log \prod_{x^i,b^i \in \Bbb{D}_{win}} Pr(z^i &lt; b_{l}^i | x^i;\theta) \\ = - log \prod_{x^i,b^i \in \Bbb{D}_{win}} W(b_{l} | x^i;\theta) \\ = - \sum _{x^i,b^i \in \Bbb{D}_{win}} log[ 1- \prod_{0&lt;k&lt;l}^{} (1-h_{k+1}^i)]$Lwin​=−logxi,bi∈Dwin​∏​Pr(zi<bli​∣xi;θ)=−logxi,bi∈Dwin​∏​W(bl​∣xi;θ)=−xi,bi∈Dwin​∑​log[1−0<k<l∏​(1−hk+1i​)]

再定义：
$L_{los} = -log \prod_{x^i,b^i \in \Bbb{D}_{lose}} Pr(z^i \ge b_{l}^i | x^i;\theta) \\ = - log \prod_{x^i,b^i \in \Bbb{D}_{win}} S(b_{l} | x^i;\theta) \\ = - \sum _{x^i,b^i \in \Bbb{D}_{win}} log[ \prod_{0&lt;k&lt;l}^{} (1-h_{k+1}^i)] \\ = - \sum_{x^i,b^i \in \Bbb{D}_{win}} \sum_{0&lt;k&lt;l} log(1-h_{k+1}^i)$Llos​=−logxi,bi∈Dlose​∏​Pr(zi≥bli​∣xi;θ)=−logxi,bi∈Dwin​∏​S(bl​∣xi;θ)=−xi,bi∈Dwin​∑​log[0<k<l∏​(1−hk+1i​)]=−xi,bi∈Dwin​∑​0<k<l∑​log(1−hk+1i​)
公式(11)

备注

原文这里应该是写错了，下标不应该有等于号。

为了把$L_{win}$Lwin​与$L_{lose}$Llose​结合起来，我们引入一个记号数$w$w，它的作用相当于二分类的指示器 （indicator ）。

对第i个样本：
$w^i = \begin{cases} 1, &amp;\text{if } b^i&gt;z^i \\ 0, &amp;\text{otherwise } b^i \le z^i \end{cases}$wi={1,0,​if bi>ziotherwise bi≤zi​
于是可以推出
$L_{2} = L_{win}+L_{lose} \\ = -log\prod _{x^i,b^i \in \Bbb{D}_{win}} Pr(z^i &lt; b_{l}^i | x^i;\theta) -log \prod_{x^i,b^i \in \Bbb{D}_{lose}} Pr(z^i \ge b_{l}^i | x^i;\theta) \\ =-log\prod _{x^i,b^i \in \Bbb{D}} Pr(z^i &lt; b_{l}^i | x^i;\theta)^{w^i} \cdot Pr(z^i \ge b_{l}^i | x^i;\theta)^{1-w^i} \\ =- \sum_{x^i,b^i \in \Bbb{D}} \{ w^i \cdot log W(b^i|x^i;\theta) + (1-w^i)\cdot log[1-W(b^i|x^i;\theta)] \}$L2​=Lwin​+Llose​=−logxi,bi∈Dwin​∏​Pr(zi<bli​∣xi;θ)−logxi,bi∈Dlose​∏​Pr(zi≥bli​∣xi;θ)=−logxi,bi∈D∏​Pr(zi<bli​∣xi;θ)wi⋅Pr(zi≥bli​∣xi;θ)1−wi=−xi,bi∈D∑​{wi⋅logW(bi∣xi;θ)+(1−wi)⋅log[1−W(bi∣xi;θ)]}
公式(14)

于是总的目标方程：
$\arg \min_{\theta} \alpha L_{1} + (1- \alpha ) L_{2}$argθmin​αL1​+(1−α)L2​

在作者的github代码里，$\alpha = 0.25$α=0.25
理论部分，完毕。

补充
L2其实是一个二分类视角了，这不就是某种意义上的交叉熵吗。

L1其实是一个商业领域的要求了。
回到广告业务上，我们不仅仅希望知道当前的bid，能否赢得这次auction。
我们还希望以最小的价格获胜。
那么我们希望预测出的关于z的概率密度，能在$z \in V_{l-1}$z∈Vl−1​这个价格区间内，无限接近于1，这样才能使损失项L1接近于0。
而$Pr(z \in V_{l-1}) \to1$Pr(z∈Vl−1​)→1可以让我恰好用价格$b_{l}$bl​来获胜，这是最完美的答卷。

若在$Pr(z \in V_{l-1})$Pr(z∈Vl−1​)概率离1越远，我们就越有可能多付钱才能获胜，这便是L1损失的实际含义。

二.代码部分

原作者开源地址:
https://github.com/rk2900/DLF

原文这里为什么要加个点？