RTB实时竞价算法

《RTB实时竞价算法》由会员分享，可在线阅读，更多相关《RTB实时竞价算法（17页珍藏版）》请在装配图网上搜索。

1、1.算法简介1.1 算法用途21.2 算法概述22_ 算法详细说明3.1.1 广告活动匹配31.2 实时竞价算法 43. 算法改进方向10.3.1 特征属性的选择1.0.3.2 点击率预测1.03.3 竞价调整方式104. 补充问题1.Q4.1 无历史数据阶段1.0.4.2 利用历史数据阶段.10.4.3 展示的分布控制1.0.5. 参考文献1.Q6. 附件1.16.1 名词1.16.2 算法总体流程图1.16.3 输入输出表1.1.6.4 数据预处理流程1.36.5 计算权重算法流程.15.6.6 模型检验1.61 .算法简介1.1 算法用途RTB （Real-Time Bidding ）实

2、时竞价，是一种利用第三方技术在数以百万计的媒体上针对每一个用户展示行为进 行评估以及出价的竞价技术。与大量购买投放频次不同，实时竞价规避了无效的受众到达，只针对有意义的用户进行购 买。它的核心是DSP平台（需求方平台），在DMP数据的支持下根据媒体，广告特点和人的属性进行定向投放。RTB对于媒体来说，可以带来更多的广告销量、实现销售过程自动化及减低各项费用的支出。而对于广告商和代理公司来说， 最直接的好处就是提高了效果与投资回报率。RTB算法有几种常见的策略：展现优化（针对品牌推广）目标，点击率（ CTR）优化目标和ROI（投资回报率）优化 目标。其核心都是要做到合适的广告展现给合适的人。RO

3、I优化是最直接能体现广告主的投资收益率的指标，但是目前情况下受RTB业界技术限制和公司数据支持情况的限制，点击率优化是现实可行的RTB竞价方法。虽然该方法不能直接体现在用户的投资收益率指标上，但是优良的点击率很大程度上会带来良好的收益。目前针对RTB算法中的点击率预测有很多种方法，如：逻辑回归，决策树，两阶段广义线性模型，非线性规划模型， 典型方程等。选用逻辑回归的主要原因在于该算法成熟，对输入变量要求较低，既可以处理枚举型变量，又可以处理连 续型变量。输出结果较稳定可靠。本算法主要以点击率（CTR）为优化目标，并选择逻辑回归作为主模型进行设计。1.2 算法概述首先对RTB的竞价流程总结如下图

4、所示:图1 RTB竞价流程图站长/网站从上图中可以看出，实时竞价算法的输入主要包括以下信息:1） Exchange端提供的广告位信息;2） 用户id, DMP收集的用户属性信息；3） 广告主发布的活动信息及竞价策略；4） 竞价历史（媒体信息，广告位，获胜竞价，用户id等）。表1: RTB算法输入之竞价历史广告媒体信息用户ID时间戳是否点是否成功报价成交价击格创意类型权重尺寸日实时竞价算法的输出主要是获胜的（广告活动信息，竞价）组。实时竞价算法主要由两部分构成，一是广告活动的匹配，二是根据媒体，广告活动及用户属性等进行出价。图2 RTB竞价算法流程2. 算法详细说明2.1 广告活动匹配广告活动匹

5、配的目的是为了筛选出满足媒体广告位要求，以及符合用户属性特征的广告活动集合。首先，根据请求 中的媒体广告位信息对广告活动进行初步筛选，过滤掉一些无效的广告活动，如：不满足广告位要求的广告活动等。然 后，利用DMP系统中查找到的用户特征信息，以及广告活动的投放人群属性定向再次筛选广告活动。广告活动的投放 人群属性定向主要包括访客所在地区，年龄，性别，婚姻状况，教育程度，兴趣爱好，购买偏好等。主要包括以下步骤：第一步，将请求中的媒体广告位信息与DSP系统中的广告活动信息进行初步匹配，筛选出满足条件的广告活动集合; 如果不存在广告活动，则不参与此次请求的竞价。第二步，利用DMP系统，根据用户id,获

6、取用户特征信息。第三步，将筛选出的广告活动集合与用户特征进行匹配，进一步筛选广告活动集合。图3广告匹配流程表2广告活动匹配需要考虑的信息广告位信息广告活动用户属性属性1广告位宽投放媒体偏好性别属性2广告位高访客所在地区年龄属性3不允许的属性id集合访客年龄地域属性4允许的广告技术类别访客性别婚姻属性5排除的敏感类别访客婚姻状况教育程度属性6排除的产品类别访客教育程度兴趣属性7媒体提供的限制列表访客兴趣爱好属性8访客购买偏好关于匹配度的计算问题涉及到商业策略及广告本身估值，用户的估值，媒体的估值及DSP端广告集合的分析等情况，在综合分析的情况下，才能给出在特定商业策略上的匹配度，该部分计算放在后

7、续进行。2.2 实时竞价算法通过广告匹配算法能够筛选出符合媒体信息和用户特征的广告活动，接下来需要对筛选出的广告活动进行竞价，并 排序，返回一系类（广告活动，竞价）结果组。广告活动的投放类型一般有 CPC和CPM两种，目前只考虑CPC投放类型，如果是投放类型是CPM，可以将CPM 转化为CPC进行竞价，转换原则为：CPM = CPC*CTR*1000总体来说，实时竞价算法可以分为以下两个步骤：1 .获得每次广告展示的价值，即在给定的相关展现水平和需求数据的情况下，对该次广告展现预期成本，表示形式 如下：其中eCPI表示每次展现的预期成本，即最优竞价估值。CPC在给定的广告系列中是已设定的常数。

8、预测CTR是一个关键的步骤：其中条件中的impression包括了与该次展示机会相关的数据，比如用户信息；campaign包括了广告活动的相关数据。2 .实时竞价的调整根据竞价策略以及历史竞价数据调整实际竞价。2.2.1广告展示估值为了准确地评估每次广告展示的价值，需要对该广告的点击率进行预测。初次使用系统时，由于缺乏获胜的历史 竞价信息，可以使用默认的点击率，如：该品牌往常的点击率或其他平台媒体经验值等。随着历史数据的增加，需要根 据用户和媒体等信息，对每次展示机会预测点击率。当获得足够多的历史数据时，可以利用媒体特征信息（如：广告位置等） ，用户特征（如：年龄，兴趣等），广告 活动特征（如

9、：创意，关键字等）构建点击率预测模型。由于特征属性信息非常多，首先需要进行属性特征提取，获得 有价值的属性特征。然后根据历史数据，构建点击率预测模型。当获得一个展示机会的时候，针对每个广告活动，根据 用户和媒体的属性值进行点击率预测。图4点击率预测流程2.2.1.1 特征提取在一个广告系统中，每一次出价和服务事件，包括广告机会，拍卖的获胜者，以及浏览该广告展现的用户都能够被记录。每一个广告机会通过其属性进行描述，包括 url,出版商，广告位置以及用户统计信息，geo位置信息。获胜 信息包括获胜的竞价值，实际的花费等。通常，有很多的目标属性值。它们中的大多数是复杂的布尔逻辑规则来匹配广 告商想作

10、为目标的广告库存，作为竞价需要考虑的因素也不应过多，造成算法的复杂程度过大，难以满足实时竞价的时 间要求。因此，特征选择是系统中至关重要的一个因素。在选择特征的时候，有两个方面的方法可以选用。1）经验法。通过对行业的了解及属性的分析，对属性进行筛选。2）采用适当的算法对属性对竞价的影响进行分析，计算每个属性对竞价的影响程度。选择影响因素大的属性作 为特征属性。表3需要考虑的特征属性信息广告位信息广告活动用户属性属性1媒体id投放类型性别属性2广告所属频道活动创意年龄属性3广告位宽广告主id地域属性4广告位高广告类型兴趣属性5广告位的可视性活动人群属性消费水平属性6地理信息投放媒体偏好我们采用基

11、于过滤的Fast-Correlation（FCBF）方法选择特征子集1,该方法对处理特征数目较大时非常有效。其基 本原理描述如下：设数据集D有n条记录，且每条记录由m个非目标特征和一个目标特征 C来刻画。如果非目标特征与目标特征之间的相关性过低（给定阈值），则将该特征作为不相关特征去除，如果两个非目标特征之间的相关性过大, 超过了这两个特征与目标特征的相关性时，则认为两个特征之间存在冗余，这两种情况均需要进行删除。FCBF是一个确定性算法来消除与目标值相关度较低的属性或非目标属性过度相关的属性冗余。它能使我们在很大程度上消减特征搜索时间。它依据对称不确定性计算特征和目标值的相关性，定义如下：其

12、中IG是信息增益（Information Gain）, H是嫡（Entropy ）。IG（X |Y）的值是Y给X带来的信息增益，并且 IG（X |Y） IG（Y | X）。SU是IG的一个归一化值。通过对目标属性与非目标属性及非目标属性之间 SU的计算, 在给定的阈值基础上，进行属性选择。2.2.1.2 点击率预测在特征子集选择的基础上，对点击率进行预测。点击率预测问题可以看成是一个分类问题，把 （媒体，广告活动，用户）看成是一个多元组，针对每一个多元组，有 一个预测目标，是否点击。该问题可以看成是一个典型的逻辑回归问题。假设有n个训练样本集，D （f j他，aj,uj）,cj）； 1 ,其中

13、f j（pj,aj,uj）d表示由多元组（媒体，广告活动，用户）属性值构成的一个 d维向量，cj 0,1是相应的分类标签（+1，点击，或者0:没有点击）。给定一 个媒体p,广告活动a,以及用户u,需要计算点击的概率 p（c| p,a,u）。采用逻辑回归模型，表示形式如下：其中fi （ p, a, u）表示从多元组（p, a, u）获得的第i个属性的值，wi W关于它的权重。给定训练样本集合，模型通过 减少数据中的总损失计算权重向量 W,公式如下：可以用L-BFGS算法网求解这种大规模的凸优化问题。具体方法如下。L-BFGS算法步骤如下:Step1:选初始点 W 0，允许误差0,存储最近迭代次数

14、m （一般取6）;Step2: k 0, H0 I ,rf (W0)；其中：令 xj=f j(pj,aj,uj)，则 f(w)ncj1xj jTT (c1+eW xxj1)Tj1+e-W xStep3:如果 | f (Wk 1 )|，则返回最优解Wk1 ,否则转Step4 ;(注：|x| = ( n=1|xi|2)/2)Step4:计算本次迭代白可行方向：pkr；Step5:计算步长k0 ,对下面式子进行Backtracking线性搜索:f(Wkkpk) min f (wkpk)；需要删除（SkStep6:更新权重 W : Wk 1 Wk kpk ；Step7:如果k m,只保留最近 m次的向

15、量对,Step8:计算并保存：SkWk 1 Wk , ykf (Wk 1)f (Wk)；Step9:用 two-loop recursion算法近似计算 rk=k+1 ,转 Step3。two-loop recursion 算法:令 qf(Wk1)，步骤1 ：对i1,L ,m ,循环以下运算:TiSk 1 iq，q iyk 1步骤2 ： rH01q ;步骤3 ：对im,L ,1 ,循环以下运算:Tk 1 i yk 1 i rr rSk其中:k 1/ yTSk，SkWk 1 Wk，yk f (Wk 1)f (Wk)，Backtracking线性搜索算法:任选 0, ,c (0,1),令重复直到

16、f(wkpk) f(wk) cTfk pk，结束（重复）终止 kLogistic 回归分析。如：多表4:点击率预测输入向量媒体(impression )属性 p广告活动（campaign ）属性a用户（user）属性u类型权重创意人群性别地域收入兴趣注：如果属性值是分类型变量，特别是名义型变量，则需要将其转化为哑变量，再进行分类变量有四个取值（A/B/C/D ）,这时需要设置三列哑变量，比如 D2,D3,D4,如果变量值是B,则D2=1 ,否则取0, 如果是C,则用D3=1 ,否则取0,如果是D,则D4=1 ,否则取0o可以以如下的矩阵方式进行存储。ABCDD20100D30010D40001

17、如果属性值是连续型变量，则需要对变量进行标准化处理，以消除因数据单位不同而引起的计算结果的偏差，一般采用z-score标准化方法，方法如下：令 xmaxmax xi , xmin min xi, R xmaxxmin J 则xixmin如果属性值是连续型变量，则需要对变量进行标准化处理，以消除因数据单位不同而引起的计算结果的偏差，一般采用z-score标准化方法，方法如下：经变换，各变量落入0, 1区间。2.2.2竞价调整为了获得实时竞价调整参数值，利用历史数据建立线性规划模型，通过对偶理论将其转化为一个低维数形式，求解 得到竞价调整参数的初值，然后利用控制论方法，基于一些误差函数调整竞价与满

18、足限制条件的水平。2.2.2.1 线性规划模型的建立为了得到在线竞价算法的调整参数，首先建立展示广告优化的线性规划模型，其中，展示机会是分别估价和分配的, 需求方约束依据的是展示投放目标。定义符号标记如下：1 :展示机会（impressions） , 1,2,., nj :广告活动系列（campaigns） , 1,2,., m自：展示机会i分配给广告活动j的CTRqj ：广告活动j的cpc用 :分配方案的期望值eCPI, vijpijqjgj:广告活动j的展示投放目标（有时有可能会用预算代替）内：决策变量，展示机会i是不是分配给广告j, （0,1变量）根据给定的符号标记，构建原始的线性规划问

19、题如下：其对偶问题可以表示如下：i表示出对偶变量可以解释如下：j表示活动j获取一个额外的目标展示机会的经济值（如：通过增加预算）版商购买一个额外展示机会i的经济值（如：通过吸引更多访问者）。通过解对偶问题可以获得最优解，但还存在一些问题，比如在线情况下，怎么通过对偶问题的最优解获得原问题 的最优解。2.2.2.2 竞价调整调整方案1基础算法中假定展示机会是平稳的，这就意味着给定足够多的历史数据，通过解离线对偶问题可以获得最优竞价j, j o实际上，由于市场是动态的，展示机会的到达不是平稳的，比如：供应随季节变化。另一方面，需求方的估 值也是一个不固定的过程，比如：旧的广告过期，新的广告开始。这

20、些不固定性不满足完备松弛条件，从而历史最优的j对于未来并不一定是最优的。为了解决这个问题，利用历史数据的离线最优解初始化j ,然后利用一种控制方法在线更新j ,以满足动态的供应方和需求方约束水平。在实践中，由于在线计算的效率和展示机会到达的离散性，时间 t不需要立即被追踪。令t 1,2,L ,T表示足 够小的时间区间，T表示整个在线竞价时期内的区间个数，在每一个区间内更新一次j。受Water-Level算法4启发,采用更新公式如下：其中Xj（t）表示广告活动j在时间区间t内获得的展示数目，指数因子是一个调节参数，控制算法对误差Xj（t）/gj 1/T的响应速度。如果初始的j对未来也是最优白1可

21、以令 0。更进一步，基于Water-Level的更新公式有一个很好的链接属性：调整方案21 .按照广告维度和媒体维度对价格分布和点击率进行统计，得出点击率和价格分布的分布情况（需要根据数据情况确定是用哪个维度的统计信息）。2 .如果是回头客和商品关联，在计算出的价格上乘以一定的系数（系数方式为乘以（11）,1为经验值），以增加展示成功率。3 . 根据上一天的竞价成功率与目标成功率之间的差异对价格进行调整（预期成功率和实际成功率进行比较，增加或减少一个系数）。调整公式如下：其中, 预期成功率-实际成功率，、,2 预期成功率目前选用方案2作为竞价调整策略。2.2.3选择广告活动在线情况下，每一次展

22、示机会i到达的时候，计算匹配成功的广告活动组（a,a2,L，斗）的竞价值：bidj, j 1,2,L ,n,并按竞价值由高到低进行排序，给出竞价列表。3. 算法改进方向3.1 特征属性的选择可以用决策树，属性相关性的特征加权等方法来评估属性特征。3.2 点击率预测有多种方式可以预测点击率，如：利用对数线性模型LMMH 来估计稀有事件点击率等。3.3 竞价调整方式还可以利用统计学方法进行竞价调整，通过获取展现的成功竞价的历史数据，根据统计学方法描述出竞价的分布情况，然后在满足限制条件下，为达到最大可能竞价成功做出竞价调整。4. 补充问题4.1 无历史数据阶段算法中 eCPI 和调整参数 的计算均

23、依赖历史数据，在系统运行的初始阶段由于缺少历史数据的积累，运行前一段时间采用经验数据进行竞价。建议eCPI=CTR*CPC ，给定 CTR 进行竞价，也不做调整。4.2 利用历史数据阶段利用历史数据阶段采用本文中算法计算eCPI 和调整参数 。由于 eCPI 的计算量比较大，可以采用较大的周期进行计算，推荐计算周期为1 天， 的计算量较小，可以实时或每小时计算一次。4.3 展示的分布控制为有效控制展示的分布情况，需要在算法中加入调节机制，防止展示过分集中的发生。最初可以采用每小时展示数量作为调节阈值进行控制。如某个广告的展示目标为每个月展示/ 点击1 万次，则可以将这个点击数量根据流量情况或客

24、户要求分布到每个小时中去，使得展示可以满足要求。5. 参考文献1 L. Yu and H. Liu. Feature selection for high-dimensional data: A fast correlation-based filter solution. In Proceedings of the Twentieth International Conference on Machine Learning (ICML-2003), pages 856-863, 2003.2 A. L. Berger and V. J. D. Pietra. A maximum entrop

25、y approach to natural language processing. Computational Linguistics, 22:3971, 1996.3 D. C. Liu and J. Nocedal,“ On the limited memory BFGS method for large scale optimization,528, 1989.Mathematical Programming, vol. 45, no. 3, pp. 5034 D. Charles, M. Chickering, N. R. Devanur, K. Jain, and M. Sangh

26、i. Fast algorithms for finding matchings in lopsided bipartite graphs with applications to display ads. Proceedings of the 11th ACM Conference on Electronic Commerce (EC 2010), 2010.5 Y.Chen, P .Berkin, and B.Anderson. Real-Time Bidding Algorithms for Performance-Based Display Ad Allocation. KDD 11,

27、2011.6 D. Charles, M. Chickering, N. R. Devanur, K. Jain, and M. Sanghi. Fast algorithms for finding matchings in lopsided bipartite graphs with applications to display ads. Proceedings of the 11th ACM Conference on Electronic Commerce (EC 2010), 2010.6. 附件6.1 名词1. RTB: real time bidding实时竞价2. CTR:

28、click-through rate点击率3. CPC: cost-per-click 每点击成本4. CPM : cost per one thousand impression千次展现成本5. eCPI: expected cost per impression每次广告展现预期成本，定义为：6. CPM 与 CPC 的转换公式推导：CPM = CPC*CTR*1000CPM 表示白是 Cost Per 1000 Impression ,即： CPM = Cost / Impressions * 1000(1)CPC 表示白向是 Cost Per Click ,即： CPC = Cost /

29、 Click .(2)CTR表示白是 Click-Through Rate ,即 CTR = Click/Impression(3)将(3)式代入(2)式:CPC = Cost / (CTR * Impression) = (Cost / Imp.) * (1 / CTR)6.2 算法总体流程图6.3 输入输出表eCPI计算输入参数表：用户属性名称消费偏好消费消费消费总额线上消费习惯消费等级兴趣平均消费水平频率次数偏好重要度*DMP类型StringDoubleIntDoubleIntIntStringDouble算法类型枚举连续值连续值连续值枚举枚举枚举枚举（有顺序）广告活动属性名称类型（创意

30、）重要度*算法类型枚举媒体属性名称类型（频道）权重广告位宽广告位高重要度*算法类型枚举枚举枚举枚举竞价历史（流水数据）广告媒体信息用户ID竞价方是否成问是否点击报价成交价格时间戳创意类型权重尺寸（在计算时，取用竞价成功数据）计算周期可以以天为单位a计算所需输入:指定广告指定时间段内的点击次数（以小时为间隔）竞价历史统计（计算与分析用-广告维度）：广告ID竞价次数成功率平均价格（成功）平均价格（出价）最后一次成功价格最后一次出价点击率竞价历史统计（计算与分析用-媒体维度）：媒体ID竞价次数成功率平均价格平均价格最后一次最后一次出点击率（成功）（出价）成功价格价需要提供的默认（/初始）值（媒体维度

31、）媒体ID平均（/初始）出价最高出价平均点击率需要提供的默认（/初始）值（广告维度）广告ID平均（/初始）出价最高出价平均点击率在线计算输入:用户属性，媒体属性，广告活动属性，是否回头客，是否商品关联。6.4 数据预处理流程数据预处理增加中间变量的生成，目前中间变量有两个：媒体类型与用户购买兴趣关联度及媒体类型与用户兴趣关联度。这两个变量的计算方法将在下文中给出。6.4.1 离线数据预处理6.4.1.1 数据选取需要选取竞价成功的数据作为训练数据和验证数据，由于模型主要跟媒体，广告活动，用户三方面的属性值有关， 因此做应尽可能选取包含这三方面属性值的数据，不选取用户属性完全缺失的数据。6.4.

32、1.2 缺失值填充如果单条记录中某个属性的属性值缺失，则需要对其进行填充。如果该属性值是枚举型变量，则用其众数进行填充（注：众数表示的是整列变量值中出现次数最多的数据，如果有多个，采用最先出现的那一个）；如果该属性值是连续型变量，则用均值进行填充（注：均值指的是该列数据的算术平均值（列均值）。6.4.1.3 中间变量的生成1）消费属性预处理由于用户消费属性可能有多个值，并且只凭借用户消费属性不能确定其对点击率预测的影响，需要把它与媒体类 型关联起来进行考虑。首先通过一定的转换，建立媒体类型和用户消费属性之间对应关系表，然后，通过对应关系将用 户消费属性转换为0,1区间的数。具体方法如下：假设媒

33、体类型为p ( p1, p2,L , pn),对应的权重为w (w1,w2,L ,wn),用户的消费属性为u (u1,u2,L ,um)，如果pDuj具有一定的对应关系，对应值用vij表示，计算某一媒体类型pi与用户消费属 性u的关系如下：vij(1)*( j 1)其中，fj(pi,uj) 1 -,表示用户最后一个消费属性的权重 01,默i 1 vijm认为0.5。计算所有媒体类型与用户消费属性的关系值并进行加权求和，就可以把用户的消费属性转换为一个确定的0,1区间的数。公式如下：其中，f ( pi ,u)表示第i个媒体类型与用户消费属性的关系值，通过上式计算得出，wi表示第i个媒体类型的权重

34、值。注：无历史数据之前，对应关系表可以人工给出。具有了一定的历史数据后，可以通过统计信息计算出媒体类型与用户 消费属性之间的对应值。媒体属性与用户属性对应关系表形式如下：消费属性媒体属性票务旅游运动户外Sports01Travel10.62)兴趣属性预处理同上建立媒体类型与用户兴趣属性的对应表，将用户兴趣属性转换为0,1区间的数，需要注意的是有可能不同。6.4.1.4 广告位预处理根据广告位的宽高按一定标准将其转换成一个枚举型变量，如：根据广告位大小，将其分为大、中、小三种情况。(注：可以根据实际数据进行划分)。6.4.1.5 数据标准化如果属性值是枚举变量，需要将其转化为哑变量，再进行Log

35、istic回归分析。如：多分类变量有四个取值(A/B心/D ), 这时需要设置三列哑变量，比如 D2,D3,D4,如果变量值是B,则D2=1 ,否则取0,如果是C,则用D3=1 ,否则取0, 如果是D,则D4=1 ,否则取0o可以采用如下的矩阵方式进行存储。ABCDD20100D30010D40001如果属性值是连续型变量，则需要对变量进行标准化处理，以消除因数据单位不同而引起的计算结果的偏差，一般 采用z-score标准化方法，方法如下：经变换，各变量落入0, 1区间。6.4.2 在线数据预处理6.4.2.1 缺失值填充在线情况下，如果用户属性数据完全缺失或缺失超过一定比例的时候(如：60%

36、),通过模型预测的点击率很有可能不准确，这种情况下只能采用媒体或广告活动默认的点击率。其它情况下，采用离线预处理记录中的默认属性值进行填 充。6.4.2.2 中间变量的生成与离线部分的预处理方式相同。6.4.2.3 广告位预处理与离线部分的广告位预处理方法相同。6.4.2.4 数据标准化根据离线预处理记录对属性值进行标准化，如果属性值是枚举型变量，通过哑变量矩阵进行转换。如果属性值是连 %Xj续型变量，通过预处理记录查找到标准差和均值xj,标准化后的变量 为 0.5 需要注意的是由于在线数据多样性，有可能经过预处理的属性值不在0,1 区间，这时需要将其调整到0,1区间，调整方法如下：如果标准化

37、后的属性值大于1,调整其为1,如果属性值小于0,将其调整为0o6.5 计算权重算法流程采用L-BFGS算法计算逻辑回z归预测模型中的权重向量，算法流程图如下：T4注1： w0(0,0,0) ;10 ；m 一般取 6n jxjjxj注2： h0为阶数和输入向量相同的单位阵，f(w)cJw? (cJ 1)WT7】j 11+ew *1+e-w *其中：xj=f j(Pj,aj,Uj)；注3 :k的计算参见Backtracking线性搜索算法注 4： % 的计算参见 two-loop recursion 算法6.5.1 Backtracking 线性搜索算法任选一0, ,c (0,1),令 一，重复直

38、到 f(Wk Pk) f(Wk) c fT(Wk)Pk，结束(重复)终止 k 注1 :一初始值取1 , 取0.5, c取16.5.2 two-loop recursion 算法令q f (wk 1), n min(k 1,m)步骤1：对i 1,L , n ,循环以下运算：i k 1 iST 1 iq , q q yk 1 i ；步骤 2 ： r H 0 1q ;步骤3：对i n,L ,1,循环以下运算：k 1 iyT 1 J，r rsk 1 i( i )其中：skwk 1 wk ,yk f (wk 1) f(wk) ,k1/yTsk，k 1(sTyk)/(yTyk),H：i流程图：6.6 模型检验A%,则认为计算出的权重计算出权重之后，抽取一部分数据作为验证数据，计算它们的点击率，如果准确性达到合理，模型正确。否则，采用竞价历史中的点击率或默认点击率。(准确度A需要根据实际情况确定)