课程地址:计算广告学
广告交易平台:
关键特征:用实时竞价(RTB)方式链接广告和(上文,用户);按照展示上的竞价收取广告主费用
实时竞价 Real time bidding(RTB) RTB 的流程可以分为cookie mapping 和Ad
call两个过程 cookie mapping的作用是沟通Adx和DSP,使得两边都了解有哪些cookie ad call是正式的广告投放
这里面有一些潜在的风险,如有些公司加入RTB目标就是用非常廉价的方式拿到用户数据,而非投广告。并且,由于多了一次访问请求返回,会增加浏览者的网页响应时间。对于用户来说,等待大约多了 100ms,这样对用户 ctr 是有影响的,并且增加了Demand端的成本和server的成本
第一个例子:DSP和adExchange 之间进行Cookie Mapping,由DSP发起,在广告主控制的网站上发起,mapping表存在DSP端,目的是为了获取DSP cookie和Adx cookie之间的对应关系。 当用户浏览含有DSP代码的网页的时候,网页向DSP提出询问请求, DSP cookie服务确认该网页用户的cookie很久没有更新过了,就向该页面提出我需要同步你的cookie 然后该页面将相关信息提交给ad exchange,xid= adx cookie id(这个不明白,dsp端是怎么获得的,是否xid是代表exchange的ID),did(demand cookie id),dck = demand cookie adx把对应的xck= adx cookie返回给DSP端 到此为止,DSP端就把自己的cookie和ADX端的cookie对应起来了,存在DSP端的表里面。
当以后广告需求产生的时候,ADX把xck发给DSP,DSP在自己的表里查,这个人是不是我要的,是要的,我再出价购买。
第二个例子:
网站想了解访问自己网站用户的更多消息,或者用户的分类,标签等等,所以需要向dmp询问 网站自己存自己的用户cookie和dmp cookie的映射 如果网站想了解用户,就先查表,获得dmp cookie,然后向dmp发送这个用户的dmp cookie,dmp就返回这个用户标签等等
课时34 Supply Side Platform
对于媒体,有四种变现模式:
大媒体,直接GD销售,变现能力最高(按天销售)
分类流量后,按照GD销售(按CPM销售,target)
流量托管给广告联盟
RTB
SSP等于是同时做这4个,收益统一管理,灵活接入多种变现方式。Sell-Side Platform,即供应方平台。供应方平台能够让网络媒体也介入广告交易,从而使它们的库存广告可用。通过这一平台,网络媒体希望他们的库存广告可以获得最高的有效每千次展示费用,而不必以低价销售出去。
需求方平台 Demand Side Platform:需求方平台允许广告客户和广告机构更方便地访问,以及更有效地购买广告库存,因为该平台汇集了各种广告交易平台的库存。
目的:Allows digital advertisers to manage multiple ad exchange and data exchange accounts through one interface
关键特征:
定制化用户划分
跨媒体流量采购
通过ROI估计来支持RTB
代表:InviteMedia, MediaMath
开放的问题:如何利用历史投放数据估计流量?(没有公认的合适的方法)
点击价格估计的应用场景:
DSP的实时出价
广告网络的出价工具
智能定价:广告网络方需要对不同质量的流量估计一个相对的价值,方便对广告主打折(比如说上下文的5折,搜索引擎的全价)。
这个问题作为机器学习的挑战:
数据非常稀疏
与广告主类型强烈相关的行为模式 点击价值估计若干原则
模型估计时,用较大的bias换较小的variance,已达到稳健估计的目的
充分利用广告商类型的层级结构,以及转化流程上的特征
DSP:DSP大致有3个功能,重定向、人群标签、相似用户。
重定向的分类:
1、网站重定向:根据浏览的网站的内容进行重定向。对做品牌的够用了。比如进入过京东商城,到别的网站去给你推荐京东的东西。
2、搜索重定向: 根据搜索行为
3、个性化重定向:
根据浏览、关注、购买等各阶段,进行适合的推荐。 个性化重定向:粒度是商品。没下单,激励下单,已下单,推荐相关。
和推荐不同的是,推荐是按照上下文推荐,比如说前一个页看到,而这个主要是给user打标签
推荐算法概述:
1、协同过滤:
2、基于内容方法
3、推荐算法的本质? 对{user、a}的co-occurence这一稀疏矩阵的参数或非参数化的描述。
4、推荐算法选择的关键:探索较合适的bias和variance的平衡,以适应问题的数据稀疏性
广告交易市场中的问题还没有形成系统的体系,所以主要介绍概念,算法和技术还不成定论。
广告流量交易方式
1.程序交易(programmatic trade) 实时竞价(RTBS RTBD)、Adx、优选、网络优化、组合优化、ad network
2.优先销售(premium sale) CPT、Guaranteed Delivery担保投送、Ad server 趋势是市场向demand方向发展,并且越来越侧重于程序购买
课程地址:计算广告学
搜索广告的特点:1. 用户定向标签f(u):远远弱于上下文影响,一般可以忽略,但是因为搜索广告中query的信息已经很强了,用query已经足够了。2. Sesion内的短时用户搜索行为作用很重要,3. 上下文定向标签f(c):关键词。 查询词扩展 从缺点来讲,是搜索广告的运营商希望通过查询词扩展以攫取更多的利润。 做查询扩展后的广告点击的价值是要低于不做查询扩展的点击价值,但如果扩展的关键词相关的广告如果出价更高或一样高,那么对搜索广告运营商做扩展是会收入更多的。另一点从宏观上讲,通过做查询扩展,使得每一个广告主的竞价范围变大了。 方法:
在Storm中,一个实时应用的计算任务被打包作为Topology发布,这同Hadoop的MapReduce任务相似。流式计算是调度数据的,而Hadoop核心是调度计算
广告购买平台(trading desk):链接不同媒体和广告网络,不能提供非实时的ROI广告网络Demand端。
广告购买平台(Trading Desk)
非实时竞价campaign的ROI优化能力 经常由代理公司孵化出来
课程地址:计算广告学
计算广告领域的探索与利用要解决的问题是:因为长尾(a,u,c)组合极大部分在系统中并没有出现过,所以没有这些长尾(a,u,c)的统计量,所以要探索性地创造合适的展示机会以积累统计量,从而更准确地估计其CTR。但探索性的展示的过程是没有按当前的eCPM最大化方法进行广告投放,即探索的展示会让收入下降,那么如何控制探索的量和探索的有效性,使得系统长期的,整体的收入增加,就是探索与利用的核心问题。
这个问题在学术界讨论的比较多,它是Reinforcement Learning中的一个具体问题,学术界通常把它描述成为一个Multi-arm Bandit(MAB)问题。这个名字的起源来自由laohuji上的扳手,扳哪个Arm赢的概率比较大,在开始的时候是不知道的,所以要用钱去探索,看哪个扳手能提供的收益最高,但试的过程是在损失自己的钱,所以用这个名字很形象地来称这个E&E问题。
Multi-arm Bandit通常描述为:有限个arms(或称收益提供者)a(即上例中,laohuji的扳手是有限的,在广告系统中它就是广告),每个有确定有限的期望收益E(rt,a),在每个时刻t,我们必须从arms中选择一个,最终目标是优化整体收益。MAB最基本的方法学术界称为ε-greedy,它是一个很简单的方法,就是将ε比例的小部分流量用于随机探索。如果提出一种新的E&E算法,当然首先要和这种方法进行比较。
广告问题中有两个主要挑战,但它们不一定能很好地在这个框架下解决。1. 海量的组合空间需要被探索,因为要探索的是(a,u,c)这个组合空间,甚至不能认为是一个有限的空间(不是指数学上的无限),2. 因为在MAB问题中假设了各个arm的期望收益是确定的,但对于广告来讲,每个arm的收益绝对不是确定的,比如在双11促销前的ROI与其它时间的ROI相比,差的就很远了。
E&E 算法 - UCB
UCB方法的思路从直觉上非常合理,它是在时间t,通过以往观测值以及某种概率模型,计算每个arm的期望收益的upper confidence bound(UCB),并选择UCB最大的arm。先不关注这句话中的术语,它其实也是一个bayesian的理念,在估计某个arm收益的时候,不再把它认为是一个确定的数,而是把它认为是一个分布。UCB的意思是在选择的时候,并不是按照期望收益最大的一点去选择,而是按照分布的收益上界去选择。在体会这个策略的过程中,会发现它是一个很聪明的策略,它对每个arm都是选择它最有可能达到的收益点来进行投放,随着时间的推移,随着观察值的增加,分布曲线会越来越窄,最终收敛成一个固定的值。假设一个广告的期望收益并不高,换言之,它的表现可能不是最优的,我们在UCB方法下不会永远出这个广告,因为经过几次探索,它就分布曲线会迅速收敛,当发现有别的广告比它更好的时候,就不会再出这个广告了,但这种方法不会漏掉真正好的广告,因为好的广告在没有观察的时候,它是非常宽的一个函数分布,它的upper confidence是一个很大的值,所以总是有机会选中它,选中之后,分布会迅速收敛到实际的确定的收益。Paper中主要探讨的是具体的UCB策略,比如β-UCB策略,它是证明选择非最优的arms存在着一个上界,该上界与总的选择次数无关。还有一个改进的策略,UCB-tuned,它证明了如果已经选择的次数越多,就越可能自信地抛弃不太有前途(但仍可能最优)的arm。
课程地址:计算广告学
点击的概率可以很自然地用条件概率来表达,given a(广告),u(用户), c(页面),p of click。我们可以用统计来预测点击率,我个人计为Regression比Ranking的方法更合适,我们知道在搜索中,Ranking的方法被广泛地研究,利用机器学习的方法得到更好的排序结果。但我们知道广告的排序是根据eCPM,所以,广告的排序并不能仅考虑CTR,因为eCPM还要考虑Bid,换言之,对广告网络而言,竞价广告系统需要准确地估计CTR。,如果是对DSP而言,对点击率的预测要求就更高了,因为DSP需要同时估计CTR和点击价值,CTR 和点击价值决定了DSP出价,即是向Exchange报的出价。
逻辑回归
Click的概率是服从Bi-nominal分布的,它的取值只能是0或1,我们很自然的想法就是用Logistic Regression模型。虽然有很多其它更Fancy的算法,但工程中常常使用的恰是这种简单的模型。 如果我们忽略二分类问题中y的取值是一个离散的取值(0或1),我们继续使用线性回归来预测y的取值。这样做会导致y的取值并不为0或1。逻辑回归使用一个函数来归一化y值,使y的取值在区间(0,1)内,这个函数称为Logistic函数(logistic function),也称为Sigmoid函数(sigmoid function)。
逻辑回归表达式
逻辑回归本质上是线性回归,只是在特征到结果的映射中加入了一层函数映射,即先把特征线性求和,然后使用函数g(z)将最为假设函数来预测。g(z)可以将连续值映射到0到1之间。线性回归模型的表达式带入g(z),就得到逻辑回归的表达式:
让x0 = 1,表达式就转换为:
分类
现在我们将y的取值h(x)通过Logistic函数归一化到(0,1)间,y的取值有特殊的含义,它表示结果取1的概率,因此对于输入x分类结果为类别1和类别0的概率分别为:
对上面的表达式合并一下就是:
梯度上升
得到了逻辑回归的表达式,下一步跟线性回归类似,构建似然函数,然后最大似然估计,最终推导出θ的迭代更新表达式。
我们假设训练样本相互独立,那么似然函数表达式为:
同样对似然函数取log,转换为:
转换后的似然函数对θ求偏导,在这里我们以只有一个训练样本的情况为例:
这个求偏导过程第一步是对θ偏导的转化,依据偏导公式:y=lnx y’=1/x。
第二步是根据g(z)求导的特性g’(z) = g(z)(1 - g(z)) 。
第三步就是普通的变换。
这样我们就得到了梯度上升每次迭代的更新方向,那么θ的迭代表达式为:
LGFGS:
http://www.hankcs.com/ml/l-bfgs.html
静态特征举一个例子,上文提到过静态特征可以通过组合得到,比如年龄等于15岁并且广告是电商广告,如果user和ad满足这两个条件,则特征值为1,否则为0。而动态优化是统计出这个组合在历史上它的表现是什么情况,即年龄等于15岁且为电商广告在历史上点击率如何,历史上的点击率显示是一个特别强的指标,或者说它比1或是0代表的信息要多。动态特征即是在标签组合维度上聚合点击反馈统计作为CTR预测的特征。也可以换一个角度去理解,我们可以认为这种聚合维度上的CTR是一个弱分类器,比如上例中只知道年龄和广告类型对点击率进行预测。我们对成千上万的组合特征就可以训练得到成千上万的弱分类器,这种弱分类器再作为最后learning模型的输入特征。
动态特征的优势有:1. 工程架构扩展性比较强,因为生成动态特征,只需要在历史数据上作统一的挖掘流量,只需要进行配置就可以实现对任意特征的挖掘,它与在线学习相比,上文讲到,特征上的任何一个方案,都对应模型上的一个方案,如果在模型上快速地变weight与在特征集合上快速变特征,变特征会简单的多,因为变模型在广告投放的过程中还涉及多台机器通信的问题,变特征没有这个问题,即使你需要计算的很快速,也可以用流式计算平台实现。2. 对于新的(a, u, c)组合有较强的back-off能力,比如有一种广告素材是没有出现过的,如果想在模型中把这个特征加进去,把权重更新出来,过程是比较复杂的。如果是仅仅在特征端对它进行描述,这个素材对不同的人群的CTR都作为动态特征放在系统里,只要流式计算做的足够快,只要广告上线,就可以迅速地就可以在模型中做出正确的决策。动态特征的缺点是,因为特征都是动态的,是需要一个很大的Cache去存储,存储的量是巨大的,因为所有的组合都可以生成动态特征,另外,更新的速度要求也比较高。
A and B are the only two candidates competing in a certain election. We know from polls that exactly N voters support A, and exactly M voters support B. We also know that N is greater than M, so A will win.
Voters will show up at the polling place one at a time, in an order chosen uniformly at random from all possible (N + M)! orders. After each voter casts their vote, the polling place worker will update the results and note which candidate (if any) is winning so far. (If the votes are tied, neither candidate is considered to be winning.)
What is the probability that A stays in the lead the entire time – that is, that A will always be winning after every vote?
Input
The input starts with one line containing one integer T, which is the number of test cases. Each test case consists of one line with two integers N and M: the numbers of voters supporting A and B, respectively.
Output
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the probability that A will always be winning after every vote.
y will be considered correct if y is within an absolute or relative error of 10-6 of the correct answer. See the FAQ for an explanation of what that means, and what formats of real numbers we accept.
1 ≤ T ≤ 100.
Small dataset
0 ≤ M < N ≤ 10.
Large dataset
0 ≤ M < N ≤ 2000.
Input
2
2 1
1 0
Output
Case #1: 0.33333333
Case #2: 1.00000000
In sample case #1, there are 3 voters. Two of them support A – we will call them A1 and A2 – and one of them supports B. They can come to vote in six possible orders: A1 A2 B, A2 A1 B, A1 B A2, A2 B A1, B A1 A2, B A2 A1. Only the first two of those orders guarantee that Candidate A is winning after every vote. (For example, if the order is A1 B A2, then Candidate A is winning after the first vote but tied after the second vote.) So the answer is 2/6 = 0.333333…
In sample case #2, there is only 1 voter, and that voter supports A. There is only one possible order of arrival, and A will be winning after the one and only vote.
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
int main() {
freopen("E:/B-small-practice.in","r",stdin);
freopen("E:/B-small-practice.out","w",stdout);
int T, N, M;
cin >> T;
for (int i = 0; i < T; i++) {
cout << "Case #" << i + 1 << ": ";
cin >> N >> M;
cout << (N-M)*1.0/(N+M) << endl;
}
return 0;
}
The Constitution of a certain country states that the leader is the person with the name containing the greatest number of different alphabet letters. (The country uses the uppercase English alphabet from A through Z.) For example, the name GOOGLE has four different alphabet letters: E, G, L, and O. The name APAC CODE JAM has eight different letters. If the country only consists of these 2 persons, APAC CODE JAM would be the leader.
If there is a tie, the person whose name comes earliest in alphabetical order is the leader.
Given a list of names of the citizens of the country, can you determine who the leader is? Input
The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line with an interger N, the number of people in the country. Then N lines follow. The i-th line represents the name of the i-th person. Each name contains at most 20 characters and contains at least one alphabet letter.
Output
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the name of the leader.
1 ≤ T ≤ 100.
1 ≤ N ≤ 100.
Small dataset
Each name consists of at most 20 characters and only consists of the uppercase English letters A through Z.
Large dataset
Each name consists of at most 20 characters and only consists of the uppercase English letters A through Z and ‘ ‘(space).
All names start and end with alphabet letters.
Sample
Input
2
3
ADAM
BOB
JOHNSON
2
A AB C
DEF
Output
Case #1: JOHNSON
Case #2: A AB C
In sample case #1, JOHNSON contains 5 different alphabet letters(‘H’, ‘J’, ‘N’, ‘O’, ‘S’), so he is the leader.
Sample case #2 would only appear in Large data set. The name DEF contains 3 different alphabet letters, the name A AB C also contains 3 different alphabet letters. A AB C comes alphabetically earlier so he is the leader.
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
int main() {
freopen("E:/A-large-practice.in","r",stdin);
freopen("E:/A-large-practice.out","w",stdout);
int T, N;
string s;
cin >> T;
for (int i = 0; i < T; i++) {
cout << "Case #" << i + 1 << ": ";
cin >> N;
int count = 0;
string res = "";
for (int j = 0; j <= N; j++) {
getline(cin, s);
set<char> charS;
for (char c: s)
if (isalpha(c))
charS.insert(c);
if (charS.size() > count) {
count = charS.size();
res = s;
} else if (charS.size() == count) {
if (s.compare(res) < 0)
res = s;
}
}
cout << res << endl;
}
return 0;
}