搜索引擎的检索结果页下方一般会提示多个相似的搜索关键词,这些词可以被看作查询关键词query的rewriting。在计算广告中,当某一个query没有对应的bid phase出价广告,或者该query对应的bid phase较少的时候,可以利用query rewriting获取相似query对应的广告进行显示,以期望获得更多的click。相似query的确定可以利用用户session中的搜索关键词上下文,但此方法需要确定query的边界,例如用户搜索过程中可能会突然跳到一个完全不相干的搜索,然后又跳回来。或者利用传统的文本相似度匹配,而由于query一般都很短,传统相似度匹配的语料也不足。

image

Simrank

Simrank算法是一种用于衡量结构上下文中个体相似度的方法,直观上的含义是利用已有个体的相似度来推算其他与有关联个体的相似度。形式化的定义如下:

有向图G={V,E}中,节点a的入边集合记为I(a),而出边集合记为O(a),则两个节点a,b(a != b时)相似度s(a,b)按照如下公式计算,其含义是个体a,b的相似度取决于所有与a,b相连节点的相似度,s(a,b)∈[0,1];当a=b时,s(a,b)=1;如果a != b,且只有同一个入节点c,我们不希望从c计算得到的s(a,b)也为1,因此c做为衰减因子,取值是[0,1],即s(a,b) = C。

image

对于二分图G’ = (V1,V2,E),对于任意的(A,a)∈E,有A∈V1和a∈V2,则所有V1集合中的节点相似度按照出度O(A)计算。V2集合中的节点相似度则按照上述公式,利用入度I(a)计算。

image

在搜索广告中,把query和ad看作节点,当用户搜索某个查询关键词q时,点击了广告a,则建立q至a的一条边,这样构成一个由query和ad组成的二分图G=(V,E),其中V=Vq∪Va,任何边e=(q,a,w),q∈Vq并且a∈Va,可以利用simrank算法来求query之间的相似度。E(q)表示q的边,N(q)表示E(q)的个数:

image

按照上述算法,我们看以下的例子,假设C等于0.8,则利用上述公式计算出的sim(pc,camera)的相似度在前5次迭代中都大于sim(camera,digital camera),但从直观上说,由于camera和digital camera的共同邻居较多,应该具备更高的相似度,而simrank的结果是反直观的。针对上述问题,Antonellis等人在VLDB 08上提出了Simrank在计算广告方面的改进——Simrank++。

image

阅读全文…

, ,

简介

计算广告学于2008年由Yahoo Research的A.Broder提出,详细的定义参看百度百科,广义的定义是通过科学计算来选择最优的广告投放,主要研究的是互联网上的广告投放,其中典型的是在搜索引擎上查询关键词结果页出现的“推广链接”。

计算广告(或者说互联网广告)相比于传统的媒体广告的优势在于以下几点:

  1. 投放的介质范围更广。传统的媒体广告一般只有相对较少的场合,例如报纸、杂志、电视、影院、路边广告牌,而互联网上除了大流量网页的banner等,搜索引擎上的一个词语就是一个投放介质。
  2. 广告价格差距。cctv1的广告价格表,稍微像样的时段,30秒的广告都在10万人民币以上,就不提春晚这种露个脸就要上千万的地了。
  3. 个性化。互联网广告可以根据人查询的关键字、Location以及个人信息等进行较为精确的投放。
  4. 衡量投资回报率(ROI)。传统广告很难去衡量这个东西。

目标:

Find the “best match” between a given user in a given context and a suitable adverstiment.

互联网广告常用的付费方式有如下类型

  • CPM(Cost Per Thousand Impressions),按照展示次数付费,主要用于一些图形广告和首页banner。
  • CPC(Cost Per Click),按点击付费,搜索引擎的关键词广告常用付费方式。
  • CPT/CPA(Cost Per Transcation/Action),针对达到成功的营销效果的事务进行付费,例如购物类网站、酒店机票订购,用户消费后像广告投放商进行付费。
  • 此外还有淘宝等国内网站的一种CPT(Cost Per Time),即时间计费,可以包月包日。

计算广告学主要研究的是文本类广告(Textual Ads),文本类广告的投放主要分为两种,由搜索关键词驱动的广告投放和由页面内容决定的广告投放,即Google大名鼎鼎的Adwords和Adsense。当然随着社交网络和SNS的发展,还会出现基于人际关系以及人的特性、行为的”Ad Profile”,例如之前某Boss去米国,一下飞机登录他的Facebook,发现右侧的广告是有关于“英语学习”和”美国回中国机票”。

文本广告组成

一个完整的搜索竞价广告示例,包括出价词语(Bid Phrase)、出价(Bid),标题(Title),描述(Creative),显示的Url(Display URL),而Landing URL是点击该广告的登录页面URL,Landing Page也经常用于关键词广告匹配过程。

image

检索方法概述

广告也可以看作成是一种信息,因此广告的匹配过程可以根据用户输入的查询关键词以及其他一些信息,例如之前搜索的内容、用户的Location等,采用一些传统的IR方法,将广告的出价词语、标题、描述以及Landing Page当做广告文档的语料,用来和用户输入的query进行文档相似度匹配。

A.Broder在SIGIR 2007提出了一种利用web search的结果来对query进行分类、从而进行广告选择的方法。用户在搜索引擎中输入的查询关键词一般都很短,有时候很难通过关键词了解到用户到底需要寻找什么,而通常如果看到了搜索结果的网页,就会了解用户到底要找什么,例如用户搜索一个v880,通过搜索结果页可以了解用户需要找一款Android的手机,此时就可以投放相应的手机广告了,即利用搜索结果为广告的选择提供额外的信息。

image

该方法需要研究的内容就是如何利用搜索结果页,是利用前几项片段还是利用整个结果页,是利用搜索结果页上的快照信息还是利用原网页信息,以及多个搜索结果并不统一,是采用整合还是投票选择机制。

计算广告学其中有很多问题需要算法来进行解决,包括广告分析、Query分析与重写、广告排序(纯粹谁出价高谁排前面就算了)之类的可以学习,本笔记的学习资料来源在这里

, ,