【IT168 专稿】本文根据【2016 第七届中国数据库技术大会】现场演讲嘉宾叶祺老师分享内容整理而成。录音整理及文字编辑IT168@ZYY@老鱼

　　讲师简介

▲叶祺

　　2011年博士研究生毕业于北京邮电大学计算机系，毕业后即加盟搜狗广告研发团队。在搜狗从事搜索广告相关策略研究多年，目前在搜狗负责搜索广告的召回与相关性研究的工作与主要策略技术支持。 对于搜索引擎广告中涉及的相关核心技术有较深的理解。在自然语言处理以及大规模数据挖掘的算法设计和实现方面，尤其是在实际系统的工程实践中算法的应用上有较丰富的经验。

　　正文

　　大家好，我是来自搜狗的叶祺，我今天的主题是《基于大数据的查询意图识别其应用》我来自搜狗广告技术团队，我们希望通过大数据的意图识别，最后作用到广告的召回和相关性评估，我的分享分为如下四部分：

　　先讲一下动机和目标，现在的搜索广告主要是基于查询词和广告关键词匹配的搜索模式，这在学术上就会引出一些问题，无论是常用词还是关键词，在学术上来说都属于短文本，由于短文本的特性，处理它时可能会有一些问题。短文本含词较少，一般就两三个，文本处理特征非常稀疏，还有一个问题就是歧义强。由于字面匹配方法缺乏意图相关的特征，所以这时如果仅用文本匹配，就会导致很多广告缺乏相关性。基于关键字匹配的搜索方式常常忽略了对查询背后用户真正意图的识别，这时就会对用户造成不便。比如现在我想要查一个游戏电脑，结果出了一个电脑游戏，这会伤害用户的搜索体验，造成对客户无效消耗，还会浪费我们自己的广告位，引起用户和客户对我们技术能力的质疑。

　　我们的目标就是能够使用海量用户搜索日志，在海量数据里挖掘潜藏的查询之间的结构信息，然后再找到查询聚类。高频查询已经可以通过一定的结构体系识别意图，然后建立长尾查询到意图之间的映射关系，这样就可以处理高频和长尾查询了。

　　这些都是工业界的实际应用，我们非常强调可用性，我们部门有明确的目标，所以我们会要求系统能够独立使用，达到很高的精确性和高覆盖率。

　　这是Google的Google Rephil系统，号称Google广告相关性的头号秘密武器，其实我们的思路基本一样，但技术手段实现上面差别很大，Google系统是不对外公开内容的，但通过研读发明人的博士论文背景和宣传的只言片语，其实可以知道一些大致的行为。描述该系统最详细的一本书是谷歌凯文墨菲的《机器学习概率观点》，其中讲到该系统基于贝叶斯网络的Rephil的系统，基本理论应该是通过查询词或谷歌广告关键词的同现关系，对词或短语片段进行聚类，但该聚类也是基于贝叶斯网络的聚类，然后聚类出百万量级的概念，相当于每个聚类称为一个概念，然后再用一个有监督的方法发现这些概念，可以根据用户的实际查询发现这个百万量级的概念。

　　学术界识别用户查询意图方法主要分为三类，一类是短文本聚类，这个方法主要就是为了发现高频意图，谷歌曾用它做意图发现，并把这种查询和点击的关系做了出来，上面是用一个马尔可夫模型做的聚类，最重要的好处是该方法可以发现很细的用户类查询，但缺乏一个有监督的方法，很难覆盖到长尾查询。

　　另一类方法是Topic Modeling，这个方法往往会把Topic Modeling里面的东西做成feature加入到有监督的方法里，然后增强一些分类效果，但Topic Modeling的问题就是在不同的数据集上很难对应。还有一个问题就是我们发现在处理短文本关键词上，精确度是不足的，这类文本的文本特征很少，有许多词歧义很大，所以如果按照常规办法处理，想独立起来很难。

　　最后一类方法是查询分类，但查询分类最大的问题就是一般含几十到上千个类，粒度较粗。所以我们通过无监督的方法解决这个粒度，然后挖掘出细粒度的用户意图，然后在上面通过有监督的方法覆盖长尾查询。

　　下面就是我们的框架，主要分为三层，上层是query层，我们会通过无监督的聚类方法，把query聚在一个个concept上，这种concept实际上就是概念，它的粒度实际上非常小。

　　为了下一步进行长尾查询，我们会在由query组成的concept长文本中抽出文本特征，我们用的是一个N元语法，再构建一个大规模的分类器，对用户输入的查询进行推断，给出一个最相关的概念。

　　我们把这个系统称为星辰系统，我们主要希望通过海量用户大数据的挖掘，挖掘出星辰般细粒度的概念，看上去就像一个个星星，星星之间往往还有一定关联，就像星座一样，所以我们把整个系统叫做星辰系统。

　　我们把它分成两部分，一是线下训练阶段，主要分为三块，一是抽取当中的结构关系进行预处理，然后基于网络挖掘算法进行挖掘，精度不够人工也修不过来。后面还有一个概念生成，通过算法扔掉检测出来的不好的东西，用文本特征生成这些概念和线上推断模型，线上推断系统分成两步，第一步是相关概念，最重要的一步是需要推断它的概念是不是达到了足够的精度。如果精度不够，我们就会拒绝这个概念的选择，这样实际上是通过牺牲一定的覆盖率，来达到非常高的精确性。

　　实际上我们用的是年级别的查询同点击数据，用到了查询的同现建立一个复杂网络，我们在这个网络上进行聚类，我们聚类用到了图挖掘中的一类方法——社团发现。由于数据规模非常大，所以在网络中查询会有一些细微的噪声，我们希望我们的方法具备一定的抗噪性，经过对比我们了选择近十年出现的最新发现算法——社团发现。

　　社团就是网络中的一群节点，我们用不同的颜色表示不同的社团，这种聚类就是所谓的社团，它的特点就是内部连接的边非常多，但外围连接的边相对较少。实际上图切分问题由来已久，在机器学习领域里面，很早就有人提出基于图的谱切分方法，但我们通过对比发现2008年Newman教授开创的社团发现或者说是图切分算法的分支，效果优秀。因为实际网络中，聚类并不是一个呈正态分布的问题，而是极少的聚类非常大，并且绝大多数都是聚类，个数非常多，但所含的节点很少。传统的聚类方法往往倾向于对网络过往不断的进行二分，所以对均质网络的处理上噪声会非常大，通过实际对比，我们最终还是选择了Newman的切分算法。

　　其实就是定义了一个目标函数，这个目标函数是Q，它可以分成两部分，前面是网络实际密度，后面相同节点的边数在随机网络当中是期望密度，实际密度减期望密度值越高，质量就越好。Q有一个特征，它在随机网络中是一个接近零的数据，社团特征越明显，越接近于1。

　　这个质量函数并不是越优越好，它存在一个问题，它更倾向于把小社团合并在一起成为一个大社团，从而造成Q的质量上升，。为了处理这个问题，我们在这一组算法中提出了修改，设计了一个MMO模型，叫多模块优化算法，它是一个线性迭代算法，用时间复杂度和整个网络的大小，乘上前面的迭代次数就可以了。存储的空间复杂度也只需要存储一个聚类的结果，以及整个网络的大小，这个算法适合于现实数据中上千万的节点和上亿条边的处理。

　　大家可以看到(如上图所示)前面浅蓝的那条线，是现在算法当中最好的情况，黑三角形是我们算法的情况，上面是两种网络，第一个是均值随机网络当中比最好的效果稍微差一点，但是在非均值随机网络中我们的效果是更好的。这个算法可以在Hadoop上做，特别适合公司级别的领域，下面我们会在实际数据当中处理它。

　　我们会处理两年的匿名点击日志，具体处理方法是抽取当中的query-URL关系，它的规模是千万量级的query，如果存在点击关系就在当中建立一条边，产生一个query图，这个图的结构非常复杂，借助上面提出的MMO模型，挖出查询日志的concept，然后进行聚类，我们算法处理的规模是1300万个节点，8亿条边。

　　聚类出来以后还需要修正一下，因为再好的算法还是会造成不如意的结果，所以我们要处理两个问题，一是太大不纯的聚类，我们需要衡量质量度，如果质量度过低的话，我们会对它进行再次切分，如果有一些切得过细的聚类，就要重新合并，所以我们提出两个质量，一是衡量单个聚类的质量，上图中的f是文本相关性函数，也就是说质量越高这个社团越接近于我们认为的概念，还有一个是度量社团之间的相关性。

　　实际上我们用了一个组合有监督的方法，就是用一系列的打分方式。我们会放入各种各样的分类器，然后通过逻辑回归方法，把结果汇总进行学习。

　　以上是一系列输入学习的东西，这里面q1是一个文本，a1是一个查询，m1是相关结果，我们用标注的文本相关性数据学习出来的模型。

　　模型选好以后，我们会扔掉质量差的聚类，质量太差或者太大的再次进行切分，我们再找到各个聚类，我们就把它叫做意图概念，大概是200万的级别，然后在这种概念的query出来以后，接下来的任务就是把它分配到概念当中，找出一个最相关的。或者直接拒绝掉无法判定，下面分成两部分，一部分就是找出候选的分类概念，还有一个就是要确定是不是达到了一定的精度。

　　候选概念的方法上，短文本用类似于贝叶斯的方法找出来的效果是很好的，这也有一些论文提到过。

　　下面是给定了query的一个特征向量Xq，我们希望找到Xq条件概率下的concept，然后用贝叶斯假设把它展开，因为在实际运算中，我们的量会很大，统计的概率一定会非常低，会造成浮点溢出，所以在实际应用中会对它进行log运算。我们认为最后一步加和的分数越大，概念越相关。

　　最后，我们会用传统的信息检索方法，测试我们的query，然后加上TF-IDF打分的概念t之间共同出现的权重在query中占的比例，要求必须大于一个域值。我们还会算query和concept的特征重叠是不是够大，只有这两者都够大的时候，我们才认为我们的推断是准确的。

　　需要测量概念质量好坏的时候，我们要做一个文本相关性算法对比试验。这条红线就是我们的的模型做出来的文本相关性的AUC。概念发现结果如下图所示：

　　星辰系统在处理日常查询的时候，其精确性可以达到97.4%，覆盖率可以达到61.3%。目前，星辰系统已经被部署到搜狗的搜索广告系统中，对多种搜狗商业搜索的线上服务提供支持。

　　对于查询意图的追踪，大家可以看如下的几张图：

　　以下是线上DEMO系统的实例，大家可以看一下：

　　对于其在广告召回中的应用，它可以训练针对概念的商业性分类器，判断每个概念是否适合召回广告，线下计算每个概念和关键词的相关性，线下选择每个概念适合召回的关键词链，线上判断query所属概念，根据概念召回。

　　在广告质量保证中，其具有如下功能：

　　未来，搜狗将继续促进互联网软件开发领域的高效创新，不断吸收国内外前沿的技术，完善并夯实自身实力，以创新的技术型产品为用户不断创造价值，共同见证科技创新的力量，为伙伴和投资者带来高效回报。

　　我的分享到此结束，谢谢大家!