发帖
雷达卡
首先，必须有数据要知道对于什么样的游戏什么样的用户对于它来说是有效的。但是这里似乎就存在一个循环，对于游戏开发它会针对用户的喜好去开发游戏，如果开发的游戏受到用户的喜欢，游戏开发者就有利润，好像是一个矛盾，既然游戏是针对特定的用户群体开发的对于游戏开发者，他有能力去理解这个群体怎么到了游戏开发出来却找不到这个群体了？原因在这里，游戏开发者大多是游戏高端用户，即便是去和他可能的用户做焦点访问，那也只是若干个特定的“焦点小组”，不可能触及潜在的所有用户，所以这里就需要广告帮他找到潜在用户了。
接下去，怎样判断一个impression是一款游戏的潜在用户，而且要判断潜在程度是多少，这里就可以用某款用户潜在用户的可能性是多少了度量，同时impression有很多个，你购买多少次就足够了，也就是你怎么判断一个impression已经起到作用了，接下去怎么做，依然是要判断这个impression起到作用的程度，只要你判断经过几次的impression已经起到作用了，就在不用展示了，因为再展示就成为骚扰，在这里依然是程度的问题，对于不同的用户展示超过起作用怎样的程度就成为骚扰了，你需要让自己的展示次数恰到好处，即目标达到即可，程度不够不行，程度超过更不行。
---------------------------------------------------------------------------------------------------------------------------------
所以需要定义潜在用户。可以用一个一致性模型来描述特定的游戏的潜在用户群体。如果这个用户是个搜索用户的话，我们这样去细化这个场景模型：
当一个用户使用一次搜索引擎，输入一组搜索条件算一次搜索，对应的产生一次impression、产生一次投放广告的机会。一个用户在较短的时间内只能使用一种搜索引擎，当他的注意力划过某次的搜索结果之后，这次展示机会就结束了。用户输入完关键字，搜索引擎获得关键字，点击搜索——显示结果，这个过程用时很少。系统就需要在这么短的一个时间内去做出判断，应该展示哪几个广告。
当用户看到广告，如果他觉得是他搜索的内容他就有可能点进去，如果他觉得不是他想要的内容，他就会忽略掉。如果他点击了广告，广告主就要付费了。
按理说广告主自己最了解自己的用户，他可以选定一些关键字说，这些关键字搜索的时候你就可以帮忙出我的广告，当然对于同一关键字买他的广告主会有很多的，此时，还是需要系统帮忙判断应该展示谁的广告更好。更好有几层意思，一个方面，对于搜索引擎来说，当然是谁出价高就给放谁的广告啊，这里系统的假设就是价钱的高低能够代表，这次的展示机会对于不同广告主的价值，越高代表给这个用户这次的展示价值越高。另一个方面，搜索引擎又不能完全仅仅依靠谁出价高就给谁展示，有的用户不懂得搜索关键字的用法，或者，它的代理商不负责任，帮他出一个很高的价值，价格没有反应价值，这造成广告主对于这种商业模式不信任，他可能会觉得说拿预算玩一次试一下就好了，我怎么可能是真的傻。其实这里就涉及到对于搜索引擎而言该如何设定自己的系统优化目标。反正，不管怎么着搜索引擎总是需要预测某个关键字对应某个广告时候的点击率，需要去除掉不利于自己商誉的那部分广告售卖。总之，就是要调好自己的系统。这里我们总结到，搜索广告是两主体之间的匹配，两主体是关键字和广告。而点击率预测就是评价这种匹配好不好，好的程度是多少？
---------------------------------------------------------------------------------------------------------------------------------
Web-Scale Baysian Click-Through Rate Prediction for Sponsored Search Adverting in Microsoft's Bing Search Engine
文章结构
第二部分：点击率预测怎样在关键字竞价的框架中起作用的，在搜索广告领域应用的限制和挑战在哪里。
第三部分：线上贝叶斯概率单位回归算法，即adPredictor，在一个factor graph里面做了一个更新之后过往信息的引申。
第四部分：用准确的剪枝和平行训练说明算法是怎么在大范围网络内起作用的。
第五部分：讨论预测将如何影响未来训练数据的构成，以及对交易数据的探索和利用。
第六部分：用calibrated Naive Bayes classifier比较从live的系统得到试验结果和adPredictor的预测。
第七部分：总结。
ps:必应的点击率预测算法一年之间换了一个新的。一年10^10~10^11方的展示量。
---------------------------------------------------------------------------------------------------------------------------------
第二部分：
数学记号：
Advertiser——i
Bid of the Advertiser——bi
Probability of click of the advertiser——pi
Rank Score ——bi*pi {为什么？因为将出价和点击率当成了两个独立的事件！}
广义第二高价的付费—— ci=frac{b_i+1*p_i+1}{pi}{为什么？}
特定领域内的挑战：
估计：孤立的去评估，已经使用的方法有log-likelihood、receiver-operator curve（AUC），和naive bayes进行比，还是
用navie bayes比现实和adPredictor。adPredictor的作用不在预测行为。三方意图。受到子系统的影响：错误检查系统，检索拓展、关键字-查询匹配系统。受到各种参数影响：保留价格和排名得分。所以需要孤立的评估。
动态和探索：人们行为不断在变，就有必要追踪这种变化——季节、口味兴趣、内容、经济环境Batchlearning algorithm
CTR预测基本上是个推论问题？广告选择系统的表现是和做出的决定相关联的信息测量的。是通过CTR预测来实际决定投放的广告的，CTR预测的结果决定了未来的训练数据。所以广告选择机制必须强调对交易数据的探索和开拓：依据CTR的贪婪的广告筛选会忽略所有广告存储长期利润。
计算规模和成本：全球搜索广告市场机会庞大。百万级的广告需要存储、变形、升级、检索。十亿计的用户行为在他们的隐私协议条款之下需要追踪。每小时百万的广告展示机会等待服务，每次需要在100毫秒之内完成，要展示这么多，评估的的量肯定会大于每小时百万。另外，每次请求需要相当的CPU时间和RAM中的数据存储。要做这个生意花费是很大的。
CTR的预测也是意味着需要相应的一个花费比较低的学习算法。训练算法需要处理那些可能有十亿计值的features，而且它必须要把输入的feature和广告条件能够关联起来。预测算法本身需要在RAM里面有有界的memory footprint这样才能在整个产品系统里面连续的运营。
--------------------------------------------------------------------------------------------------------------------------------
第三部分：在线贝叶斯概率单位回归
预测binary outcome！
3.1问题描述和记号：
首先做了一个广告展示机会到预测的点击率的映射：
\Chi —>[0,1]
N个离散的多值特征以及特征值：(广告特征、搜索特征、背景特征在一起？——搜索特征和背景特征)
\[M_i,i\in\{1,2,3,...,N\}\]
针对一次给定的展示机会，用一个稀疏二进制特征向量组来表示，每个向量和一个特征值去对应：
\[\chi:=\left(\chi_1^T,...,\chi_N^T\right)\\\chi_i=\begin{pmatrix}\chi_{i,1}\\.\\.\\.\\\chi_{i,M}\end{pmatrix},\sum_{j=1}^{M_i} \chi_{i,j}=1\]
点击与否的集合，点击是正1：
\[y\in\{-1,+1\}\]
3.2概率模型和因子图：
出发点是有概率单位链接函数的一般化线性模型。
模型的样本分布如下：
\[p\left(y|\chi,\omega\right):=\Phi\left(\frac{y \cdot \omega^T\chi}{\beta}\right)\]
此处\Phi(t)是标准正态分布的分布函数，被用作链接全体实数和区间[0,1].
参数\beta度量了反链接函数的梯度。
为了得到一个贝叶斯线上算法，我们对这个模型的权重做了假设的高斯先验分布:
\[p(\omega)=\prod_{i=1}^N\prod_{j=1}^{M_i}N(\omega_{i,j};u_{i,j},\sigma_{i,j}^2)\]
有了样本分布有了先验分布就可以算后验分布：(不懂—>线性)
\[p(\omega|\chi,y)\propto p(y|\chi,\omega)p(\omega)\]
密度函数p(y,t,s,\omega|x)的因式分解是：
\[p(y,t,s,\omega|x)=p(y|t)p(t|s)p(s|\chi,\omega)p(\omega)\]
几个因子代表的含义：
\[\begin{alignat}{1}&Factor\ f_i:样本权重\omega来自高斯先验分布p(\omega)\\&
Factor\ g:为x通过内积计算得分s=\omega^T\chi,使得p(s|\chi,\omega)=\delta\\&
Factor\ h:给s下的观测t添加高斯零均值噪音，使得p(t|s):=N(t;s,\beta^2)\\&
Factor\ q:确定y=sign(t),使得p(y|t):=\delta\\\end{alignat}\]
PS:我们仔细看了上面的式子发现\omega是features的服从多元正态分布的随机向量，或者随机矩阵。
PS:我们发现图模型里面特殊标示的含义是这样子的，圆圈里面是条件概率的条件，黑块里面是所谓的因子，更像是一
种操作的标示。Exciting，希腊字母真是太好看啦~不过这个图模型的理解不是显而易见的，我们决定先往下走了。
PS：这论文还有点学术水平。原来只是个特殊情形，不原创啊。
3.3推论
因子图允许我们分解了在权重\omega下的后验分布使之适用于信息的本地计算。在另外的论文里详述。事实上，正因为后
验分布比较棘手，我们才做了近似在同族的分布中选了一个先验。近似的信息在假设的高斯密度筛选下通过算法传播期望值。
在因子图里面需要计算两类的边际分布：
\[(1)对给定的训练样本(\chi,y)和先验p(\omega)计算新的后验p(\omega|\chi,y)\]
\[(2)对得到的后验分布p(\omega|\chi,y)和特征向量\chi计算预测分布p(y|\chi)\]
我们通过权重\omega表达高斯假设，稀疏矩阵\omega只存储不一样的值，它们的均值向量和方差向量如下：
\[\mu:=(\mu_{1,1},...,\mu_{N,M_N})^T\\\sigma^2:=(\sigma_{1,1}^2,...,\sigma_{N,M_N}^2)^T\]
没有给出方程细节的来历。输入features对应一队游戏玩家，每一个活动权重代表每个玩家在队伍中的水平。AdPredictor中
的Inference on the weights和Trueskill中的inference on the player skills假设了竞争对手team skill是0之后是等价的。我们能从
上述的因子图中得到更新的方程。
3.3.1为线上学习更新方程式
更新的方程表示成了从先验到后验分布的映射，参数值来自输入输出值：
\[(\mu,\sigma^2,\chi,y)\mapsto (\tilde{\mu},\tilde{\sigma}^2)\]
图模型就可以被看成是信息在权重\omega下被传播的过程。
我们定义对于给定输入\chi总的方差：(为什么？—>如此定义：噪声的方差+\omega的方差)
\[\Sigma^2:=\beta^2+\chi^T\sigma^2\]
后验参数被计算出来就是：(为什么？两个式子竟然都不懂—>需要根据2个假设推导1)正态2)方差值)
\[\tilde{\mu}_{i,j}=\mu_{i,j}+y \chi_{i,j}\cdot \frac{\sigma_{i,j}^2}{\Sigma}\cdot \nu\left(\frac{y\cdot \chi^T\mu}{\Sigma}\right) \]
\[\tilde{\sigma}_{i,j}^2 \gets \sigma_{i,j}^2 \cdot \left\{1-\chi_{i,j}\cdot\frac{\sigma_{i,j}^2}{\Sigma^2}\cdot \omega \left(\frac{y \cdot \chi^T\mu}{\Sigma}\right) \right\}\]
其中呢，\mu和\nu的函数是如下定义的：（为什么如此定义\omega?）
\[\nu(t):=\frac{N(t;0,1)}{\Phi(t;0,1)}, \omega(t):=\nu(t)\cdot\big(\nu(t)+t\big)\]
方程是如何更新变化的：
(1)变化的程度在于观测值有多么出乎意料，如若y\cdot \chi^T\mu<0,那么\nu几乎是线性的。（如何证明？）
(2)变化的程度是和\tilde{\sigma}_{i,j}^2成比例的（？），所以\frac{\tilde{\sigma}_{i,j}^2}{\Sigma}可以作为权衡学习率
的一个指标。
(3)观测的增多会导致方差的减小，正的观测增加权重均值，负的观测减少权重均值。
这些更新方程的作用：它们导致了一个自然的线上学习算法，在这算法中先验权重分布(\mu,\sigma_2)的参数被初始化成能
反应任何的先验信息(比如历史均值CTR)。对于第一个训练样本(\chi,y)，后验参数(\tiled{\mu},\tiled{sigma}^2)就根据它们
算出来了。之后就可以根据后验分布做下一次的更新，像这样：
\[\mu \gets \tilde{\mu} ， \sigma^2 \gets \tilde{\sigma}^2\]
3.3.2预测分布
预测方程用后验分布和输入\chi到y的分布的映射：
\[(\mu,\sigma^2,\chi) \mapsto p(y)\]
利用前面将后验分布的分解，就可以对分解后分布进行积分得到预测点击率：
\[p(y|\chi)=\int_{-\infty}^{+\infty}\dots\int_{-\infty}^{+\infty}p(y|\chi,\omega)\cdot p(\omega)\,d\omega\]
这个正好可以解出来解析解：(推导过程是怎样的？)
\[p(y|\omega)=\Phi \left(\frac{y\cdot \chi^T \mu}{\Sigma}\right)\]
和样本分布的表达式进行比较，从后验分布多出来的方差会有这样的作用：就是将预测的概率推向0.5，遂是增加了
两种选择的熵。在零方差的极限情形就重新得到样本分布。
3.3.3动态化
这里动态性指让权重方差随着时间增加而增加。动态模型不满足：权重的后验方差很少会比先验方差大。
过往数据：
\[D:=(\chi_1,y_1),...,(\chi_T,y_T)\]
在IIDcase下有：
\[p(\chi|D)=p(\chi)\cdot\prod_{t=1}^{T}p(\chi_t,y_t|\chi)\]
假设存在一个参数是\epsilon噪音使得它（单位时间内过往数据对后验的影响的可能性）在线性的减弱。
这样的动态模型会让参数收敛于先验的情形（\mu_0,\sigma_0^2）(如何证明)
计算下来，两种情形的动态更新会被延迟，渐增地应用到下一次权重相关项的更新中。
ps:在比较复杂的式子里面，Latex编辑小括号，总是需要强调它是括号要加左右标记\left和\right，同时小括号前面再不加\。
ps:这里的中括号好像不能编译,只好用小括号和大括号代替了。
---------------------------------------------------------------------------------------------------------------------------------
[剩余部分在7楼]
京公网安备 11010802022788号
