注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Koala++'s blog

计算广告学 RTB

 
 
 

日志

 
 

查询词相关推荐  

2009-12-18 17:34:21|  分类: 搜索引擎 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

选译自《Query Suggestion Using Hitting Time》,随机游走以前没接触过,翻译术语上应该还是有问题的,应该不是很影响理解。我把作者的第2节放到了后面,所以看不懂可以到后面再看第二节的翻译。(翻译完也有几天了,今天看了一下,发现翻译的非常难懂,我想词汇量在5000以内的人,借着电子词典看这篇论文都会比读我翻译的要容易)

 

给定一个查询log数据库,从每一条记录中我们可以得到一对<Query, URL>。通过合并这些对(pairs),我们可以建立起一个二分图G=<V,E>,其中V=V1 UNION V2。显然V1对应所有的查询,而2对应所有的URLs。对于每一条边e=(i,j)对应一个<Qi,Uj>对,这个对对应一个频率值,频率值为正值。我们用w(I,j)=C(Qi, Uj)作为边的权重,也就是这个对出现的次数。

一个简单的图例如下所示:

           查询的相关推荐 - quweiprotoss - Koala++s blog

         从图1 可以看到,每一个query都连着一定量的URLs,这些URLs就是用户在提交查询给搜索引擎后,用户点击的URLs。在边上的权重表现了用户s用这个查询访问了这个URL多少次。请注意图中没有边连接两个查询,或两个URLs

         标记的查询表示我们想要产生推荐的查询。直观的,对于所有我们用一个查询去访问的所有URLs,其它人互斥地用另一个查询去访问,那这另一个查询就是对原查询的一个好的推荐,比如,图1 中的”American airline””aa”是一个好的推荐。

         QT是原始查询。我们可以令A={QT},并基于图对所有其它的查询Qi计算Hitting time hA(i),用它来对Qis来排序,选择前面的k个查询做来对QT的推荐。但是我们还有两个需要关注的问题:

1.       G会非常大(比如,500M个查询和URLs)。事实上,大多数点是与原查询无关的,但是它们增大了计算消耗。

2.       解线性系统会非常耗时,当线性系统的变量数达到百万级,它要得到准确解会非常低效。

为了克服这两个问题,我们提出了下面高效的算法:

算法1 用击中时间做查询推荐:

一个二分图G(V1 UNION V2)由查询集合V1URL集合V2组成。如果这个URL k是通过查询i点击的那么就在边的集合E中有一条边连接ik,这条边的权重是频率w(i,k)

1.       给定一个查询sV1中,一个用深度优先搜索的方法建立子图。当查询s的数量达到一定预定义的量n时停止。

2.       通过定义两个查询ijV1的转换概率形成一个在子图上的一个随机转移为:

                      查询的相关推荐 - quweiprotoss - Koala++s blog

3.       对于除了给定的查询外所有的查询s,迭代:

                    查询的相关推荐 - quweiprotoss - Koala++s blog

hi(0)=0开始迭代到一个预定义的值m

4.       h*(t)hi(t)的最终值,输出前k个最小的h*i为推荐词。

 

一个选择比较好的k值可以控制排序高的k个查询是稳定的。在第4节,我们可以看到k不需要太大的值,这样可以保证算法的高效。

        

一个二分图G=(V,E)表示有一个V=V1 UNION V2,每一条在集合E中的边连接两个分别在V1V2中的顶点,也就是没有边连接同一个集合(V1V2)中的两个顶点。令w: V1*V2为正实数表示权重函数。给定一个属于V1的点i和属于V2的点j,如果有一条边连接ij,那么w(i,j)是正值;否则w(i,j)=0

给定一个二分图,一个随机游走可以如下定义。假设当前的位置在V1中的一个顶点。然后一条连接这个顶点的边中,每条连以正比于它自己的权重被选中,通过这条边,随机游走到达V2中的一个顶点。然后类似的,一个连接V2的连被选中,然后随机游走回到V1。给定V1中的一个点iV2中的一个点j,转换的概率为:

                        查询的相关推荐 - quweiprotoss - Koala++s blog

其中:

                查询的相关推荐 - quweiprotoss - Koala++s blog

如果只关心在一边的顶点(也就是只关心V1或是V2中的顶点关系),那么一个随机游走基于上面公式可以如下表示:

             查询的相关推荐 - quweiprotoss - Koala++s blog

可以很容易地验证静态概率pai­i是与di成比例的(我不知道什么意思,我硬译的,pai没再见过了),在下面我们讨论在一个图G={V,E}上的击中时间。下面的内容都是独立的,如果你懂,就可以跳过。

AV的一个子集。令Xt表示在时间t游走的位置。击中时间TA是首次随机游走到达顶点A的时间,所以TA=min{t: Xt BELONG TO A, t >=0}。很显然TA是一个随机变量。从击中时间的定义来看给定i不属于A,我们马上得到:

查询的相关推荐 - quweiprotoss - Koala++s blog

击中时间的均值hiATAX0=i的条件下TA的期望,即hiA=E[TA|X0=i]

        查询的相关推荐 - quweiprotoss - Koala++s blog

显然:

             查询的相关推荐 - quweiprotoss - Koala++s blog

计算第二项,一定要注意到:

查询的相关推荐 - quweiprotoss - Koala++s blog

那么就有:

        查询的相关推荐 - quweiprotoss - Koala++s blog

下面公式也是显然成立的:

                 查询的相关推荐 - quweiprotoss - Koala++s blog

将所有的东西组合起来,我们得到一个计算击中时间的线性系统。

这个线性系统有一个唯一的解,事实上它可以很好地用离散位势论(我没有学过)中的极大值原理,唯一性原理来证明。

 

这种方法还可以处理特定用户搜索,这个我不关心,也不想翻译,下面是这种模型还具有的功能。

选译自《Random Walks on the Click Graph

1. ‘Query-to-document ‘search’. Given a query, find relevant documents, as in adhoc search. Relevant documents should be ranked highly regardless of whether they are adjacent to the query. Search is the focus of this paper.

2.  Query-to-query ‘suggestion’. Given a query, find other queries that the user might like to run. This is more difficult to evaluate, but approaches already exist for finding related queries using the click graph [4, 13].

3.  Document-to-query ‘annotation’. Given a document, attach related queries to it. This method for creating document surrogates, based entirely on the click graph, was studied in [15].

4.  Document-to-document ‘relevance feedback’. Given an example document that is relevant to the user, find additional relevant documents.

 

l  查询到文档 搜索。给定一个查询,找相关的文档,相关的文档会被排序地高而不管它们是与与查询相近。

l  查询到查询 推荐给定一个查询,找到其它用户可以喜欢去搜索的查询,这个更难去评价。

l  文档到查询 注释给定一个文档,将相关的查询附加到它上。这个方法用于创建文档的surrogates

l  文档到文档 相关反馈给定一个文档是与用户需求相关的,找其它相关的文档。

  评论这张
 
阅读(1237)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017