从图谱搜索看搜索技术的发展趋势

标签: 技术 | 发表时间:2013-09-11 09:29 | 作者:微软亚洲研究院
出处:http://blog.sina.com.cn/msra

编者按:图谱搜索(Graph Search)是基于社交图谱构建起来的搜索服务,与基于关键词匹配的传统网络搜索引擎相比,图谱搜索能够支持更自然、复杂的查询输入,并针对查询直接给出答案。在微软亚洲研究院副研究员段楠眼中,这样的高效个性化搜索会越来越多。文章中,他从基础架构、自然语言接口、相关研究、发展趋势等几个方面,对计算搜索的现在和未来进行了总结和展望。

作者微软亚洲研究院 段楠

 

脸谱(Facebook) 于2013 年1 月15 日推出了图谱搜索(graph search) 测试版[1],该功能可以看作是基于社交图谱(social graph) 的语义搜索[2] 服务。登录用户在使用脸谱搜索框时,能在下拉菜单中使用好友、照片、地点和兴趣等新的搜索选项。例如,当用户输入“Restaurants liked by my friends”(我朋友们喜欢的餐馆)时,图谱搜索将呈现用户的全部脸谱好友所推荐的餐厅列表。与基于关键词匹配的传统网络搜索引擎相比,图谱搜索能够支持更自然、复杂的查询输入,并针对查询直接给出答案。与搜索引擎关键词自动补足功能类似,图谱搜索会在用户输入时同步预测用户搜索意图,并根据用户选择进行查询扩展。例如,在用户输入“My friends who”后,图谱搜索会询问用户是否希望继续搜索“My friends who live in Beijing”或“My friends who work at Microsoft”等。对此,脸谱的凯斯·佩里斯(Keith Peiris) 表示:“我们希望用户能忘记以往使用搜索引擎的方式,即输入若干模糊的关键词;相反,他们可以准确表达希望获得什么。”此外,图谱搜索还具备个性化的特点,即针对用户提出的查询,图谱搜索仅仅在与用户直接相关的事物中进行搜索并给出答案。这样做既能解决潜在的隐私问题,又能为用户提供与其自身社交网络密切相关的信息。

 

目前,图谱搜索还处于测试阶段,仅支持英文查询,搜索内容也仅限于好友、照片、地点和兴趣等相对简单的数据源。当图谱搜索无法提供任何返回结果时,微软公司的必应搜索引擎就使用常规搜索结果填补空白。

 

社交图谱

图谱搜索是基于社交图谱构建起来的搜索服务。社交图谱由脸谱数据中的实体以及实体与实体之间的关系构成。其中,实体是节点,关系是边。脸谱中的用户、页面、地点、照片、网帖等信息均可由节点表示,实体之间的关系(例如朋友关系、雇佣关系等)则由边表示。从语言学的角度来描述,实体可以类比为名词短语,而边可以类比为动词短语[8]。根据2013 年1 月的统计,社交图谱包含约10 亿个用户、1500 亿条朋友链接、2400 亿张照片(照片以每天3.5 亿张的数量增加)以及27 亿条推荐信息。由此可见,社交图谱的数据量巨大。

 

基础架构

倒排索引系统Unicorn 是图谱搜索的核心。它基于倒排索引框架,提供从建立索引到从索引数据中查询结果的功能,每一个Unicorn 实例被称为一个vertical。由于索引数据的大小通常远超一台计算机的内存容量上限,因此vertical 会将索引数据分别部署在多个索引服务器上。当一次新的查询触发时,Unicorn 首先会将查询语句传递给vertical 聚合器(aggregator),并由此模块将该查询进一步分发至不同的索引服务器;然后,每台索引服务器根据接收到的查询进行检索,并将检索结果返回至聚合器;最后,聚合器负责对全部索引服务器的返回结果进行整合,并将最终整合结果返回。由于脸谱对不同类型实体的排序有不同的需求,图谱搜索会针对每类实体分别创建一个vertical。在所有vertical 的上层,一个名为顶级聚合器的模块负责对用户查询进行改写,并对改写后的查询按照类型进行切分,然后将切分结果分发至不同vertical 进行检索。在接收到全部vertical 的返回结果后,顶级聚合器还要负责对结果进行打分及合并操作。图1 是Unicorn 的工作流程图[3]。


针对图谱搜索的特定需求,脸谱对Unicorn 进行了若干功能扩展,主要包括:

 

强化“or”操作,弱化“and”操作 在很多情况下,查询操作往往需要通过弱化“and”操作来避免因约束条件过强而造成的查询结果丢失,而需要强化“or”操作来获取更多的结果。

 

查询改写 由于用户输入的查询语句并不是Unicorn 标准查询语言,因此需要在对用户意图及其社交图谱上下文充分理解的基础上,将其转化为结构化的查询语言。

 

打分 默认情况下,Unicorn 按照返回实体的静态排名对搜索结果进行打分。图谱搜索对这一打分机制进行了扩展,更多地考虑了查询语句与实体之间的相关性信息。

 

向前索引 Unicorn 为每个实体保留与其相关的若干信息,用于辅助对查询结果的打分和排序。

 

合并 对不同vertical 返回的检索结果,顶级聚合器首先对结果打分进行归一化处理,然后将全部结果重新排序,并据此生成一组统一的结果集合。

 

嵌套查询 对于某些查询语句,需要进行多次检索并将检索结果合并才能得到最终结果。例如:对于查询“Restaurants liked by Facebook employees”,图谱搜索需要首先获得“Facebook employees”对应的中间结果“[internal results]”,然后再通过搜索“Restaurants liked by [internal results]”来获得最终结果。Unicorn 提供了对此类嵌套查询语句进行分解、多步搜索和结果合并的功能。

 

自然语言接口

社交图谱是以结构化方式存储的数据,而用户查询往往使用自然语言。因此,如何将自然语言查询转化为机器能够理解的结构化查询便成为图谱搜索的核心任务和挑战。图谱搜索的自然语言接口[4] 用于完成上述转化任务,其主要包括3 个模块:

 

实体识别和实体消歧 图谱搜索目前将实体划分成20 多个类别,包括用户、组别、应用、城市、大学等。给定输入查询语句,实体识别模块会对其进行切分,并基于n 元语言模型对查询片段标注类别及其对应的概率信息。实体消歧模块将具有较高可信度的实体候选发送给Typeahead,Typeahead 会根据实体静态排名以及查询上下文、用户社交和地理位置等返回与实体候选相对应的实体列表。

 

词汇分析 在自然语言中,相同含义的语句往往对应多种不同的表述方式。针对此问题,词汇分析模块能通过使用同义词表、相关词表、时态变换等相关资源和信息,对各种不同的表达方式进行“规范”。

 

语义解析 语义解析模块将自然语言输入查询转化为最有可能的N 条结构化查询语句。图2 描述了图谱搜索如何将自然语言查询转化为结构化查询。给定输入查询“Friends in San Francisco”,图谱搜索使用加权的上下文无关文法(weighted context free grammar, WCFG) 对其进行语义分析。该查询对应一个树形结构,该结构中每个非叶子节点都由3 部分信息构成:蓝色部分代表该节点对应的非终结符部分,黑色部分代表该节点对应的(规范化后的)自然语言查询语句,红色部分代表该节点对应的结构化查询语句。原始查询语句在经过自然语言接口模块处理后,对应的规范化自然语言查询语句和结构化查询语句分别为:“my friends who live in [id:12345]”和“intersect(friends(me),residents(12345))”。其中,“12345”代表“San Francisco”在社交图谱上对应的ID。在将结构化查询语句进一步转化为Unicorn 查询语言后,图谱搜索就可以在索引数据上执行搜索并获取最终结果了。


相关研究

图谱搜索与基于知识库的自动问答(knowledge base - question answering, KB-QA) 系统有很多相似之处:输入的都是自然语言;数据都以结构化的形式管理和存储;需要对输入查询(或问题)进行语义解析,将其转化为机器能够理解的结构化语言;从结构化的数据库中检索结果。KB-QA 系统的任务在于使用结构化的知识库对自然语言问题进行自动回答。在知识库方面,知识以三元组(< 主语,谓词/ 关系,宾语>)的形式进行存储和管理。其中,主语和宾语分别对应两个知识库实体,谓词/ 关系对应两个知识库实体间所存在的关系。例如,对应了知识库中的一个三元组,其含义为:实体“Bill Gates”和实体“Microsoft”之间存在“IsFounderOf”的关系。知识库中的每个实体都对应唯一的ID 标识,用于对具有相同名字的不同实体进行消歧。在自动问答方面,给定自然语言问题,例如,“the company founded by Bill Gates”,KB-QA 系统首先将自然语言问题转化为结构化查询语句“”,其中,自然语言的表述“the company founded by”被转化为抽象的知识库谓词/关系“IsFounderOf”。通过查找知识库,能够找到答案占位符“?”对应的实体“Microsoft”。由于用户描述问题的方式变化多样,问题复杂程度各有不同,自动问答系统同样需要引入诸如实体识别和消歧、结构化查询语句转化、推理、句法和语义分析等模块。可见,在技术层面上,图谱搜索和自动问答是极其相关的。

 

发展趋势

除脸谱外,信息技术领域的其他巨头也先后推出了类似的基于结构化数据的搜索产品或服务,作为其进军和探索下一代搜索引擎技术的桥头堡和试验田。

 

Watson 是由IBM 公司研发的自动问答系统 [6]。在对输入问题计算答案的过程中,基于知识库的问答模块起到了显著作用。实验表明,虽然该模块能够回答的问题数目占全部问题数目的比例并不大,但回答问题的准确度却远高于其他问答模块。可以预见,随着知识库的不断更新,以及对自然语言理解技术的研究深入,基于知识库的问答模块必定会在自动问答系统中起到越来越重要的作用。目前,Watson 已应用于医疗、金融等多个领域。

谷歌提出了知识图谱[5] 的概念,并推出了基于知识图谱的新型搜索服务。知识图谱从本质上讲是一个知识库,基于知识图谱的搜索服务则可以看作是一个典型的自动问答系统。与传统网页搜索相比,基于知识图谱的搜索能够更好地理解用户的搜索意图,并对相关内容和主题进行总结。例如,当输入“Bill Gates”时,用户不仅可以获得这个关键词的全部信息,还能获取关于Bill Gates 的介绍。知识图谱还能够提供搜索结果的详细知识体系,帮助用户从更多角度了解搜索结果的相关信息。

 

微软公司通过提取网页中的非结构化数据,构建了结构化的知识库Satori[7],用于从语义层面提高和改进必应的搜索质量。此外,与谷歌的知识图谱搜索类似,当用户输入的查询语句能够被后台自然语言处理模块解析时,必应将触发自动问答模块,基于Satori 知识库生成答案,并将生成的结果及其相关知识直接返回给用户。

 

互联网上知识的指数级增长使得人们已经不满足于传统搜索服务的模式,即仅仅返回与用户查询相关的若干文档链接,用户更渴望获得针对其所提出问题的准确回答。随着结构化数据库的规模扩大、自然语言理解技术的深化,针对查询进行精确理解和回答的搜索服务必将越来越实用化。基于结构化数据(知识库)和语义理解的搜索技术在一定程度上代表了搜索引擎技术的发展趋势,所具有的特点能够更好地满足用户对搜索服务新的需求:

 

能够对自然语言查询进行深入的理解,并从语义层面解析用户查询意图;

能够利用海量的结构化知识库,针对用户查询提供准确的答案。

 

充分利用结构化大数据,深入理解用户自然语言查询并针对查询给出准确的答案,能够更好地满足人类对知识获取的需求,同时也代表了计算和搜索的未来。

 

申明:《从图谱搜索看搜索技术的发展趋势》一文在微软研究院博客上转载经由《中国计算机学会通讯》同意,版权归《中国计算机学会通讯》所有。原文刊登于《中国计算机学会通讯》2013年8月第90期

 

作者介绍

 

 

段 楠

微软亚洲研究院副研究员。

主要研究方向为自然语言理解、自动问答和机器翻译。

nanduan@microsoft.com


  

 

参考文献

[1] http://www.facebook.com/about/graphsearch

[2] Berners-Lee Tim. The semantic Web. Scientific American.2001

[3] Sriram Sankar. Under the hood: indexing and ranking in graph search. 2013, https://www.facebook.com/notes/facebook-engineering/under-the-hood-indexing-andranking-in-graph-search/10151361720763920

 [4] Li Xiao and Maxime Boucher. Under the hood: the natural language interface of graph search. 2013, https://www.facebook.com/notes/facebook-engineering/underthe-hood-the-natural-languageinterface-of-graphsearch/10151432733048920

[5] Sullivan, Danny. Google launches knowledge graph to provide answers, not just links, 2012. http://searchengineland.com/google-launches-knowledge-graph-121585

[6] David Ferrucci, Eric Brown, Jennifer Chu-Carroll, James Fan,David Gondek, Aditya A. Kalyanpur, Adam Lally, J. William Murdock, Eric Nyberg, John Prager, Nico Schlaefer, and Chris Welty. Building Watson: an overview of the DeepQA project. 2010

[7] Gallagher, Sean. How Google and Microsoft taught searchto understand the Web. 2012

[8] Sriram Sankar, Soren Lassen, and Mike Curtiss. Under the hood: building out the infrastructure for graph search. 2013

https://www.facebook.com/notes/facebook-engineering/under-the-hood-building-out-the-infrastructure-for-graphsearch/10151347573598920

[9] Lars Eilstrup Rasmussen. Under the hood: building graph search beta. 2013

https://www.facebook.com/notes/facebook-engineering/underthe-hood-building-graph-search-beta/10151240856103920

____________________________________________________________________________________ 

相关阅读

信息检索盛会微软“领衔主演

社交网搜索成为网络搜索学界最炙手可热的话题

 

欢迎关注

微软亚洲研究院人人网主页: http://page. renren.com/600674137

微软亚洲研究院微博: http://t.sina.com.cn/ msra


  青春就应该这样绽放   游戏测试:三国时期谁是你最好的兄弟!!   你不得不信的星座秘密

相关 [搜索 搜索 技术] 推荐:

从未降级的搜索技术-天猫SKU搜索

- - 搜索技术博客-淘宝
前些天,五福老大的文章《 从未降级的搜索技术》介绍了搜索双11的5件新式武器,其中就包括天猫SKU搜索. 本文就对此做一些更详细的介绍:. SKU,Stock Keeping Unit,库存单元,是商品库存的最小单位. 通俗的讲,一种商品可能有各种规格的货,每一种货就是一个SKU. 比如,iphone6有白色16G、金色16G、白色64G、金色64G、等多种SKU;再比如商家售卖的某款T恤有白色S码、黑色S码、白色M码、黑色S码、等等SKU.

从图谱搜索看搜索技术的发展趋势

- - 微软亚洲研究院
编者按:图谱搜索(Graph Search)是基于社交图谱构建起来的搜索服务,与基于关键词匹配的传统网络搜索引擎相比,图谱搜索能够支持更自然、复杂的查询输入,并针对查询直接给出答案. 在微软亚洲研究院副研究员段楠眼中,这样的高效个性化搜索会越来越多. 文章中,他从基础架构、自然语言接口、相关研究、发展趋势等几个方面,对计算搜索的现在和未来进行了总结和展望.

从未降级的搜索技术

- - 搜索技术博客-淘宝
在搜索我经历过全部的双11,12年和13年这2次大促,GN是开发总指挥,我是在礼台上看各种新武器实弹表演. 过去6年里,我们的引擎体系每年做到100%的性能提升,以淘系搜索为例,从最初3000台机器翻倍到现在区区6000台,但搜索服务却从6千qps增长了40倍到现在的32万qps,同时还填补了算法欲壑(算法数据占用内存从最初的10%到了现在的50%),转化率持续攀升,目前大搜索GMV已经是全网的主体了.

豌豆荚工程师谈其新版应用搜索技术

- - InfoQ cn
豌豆荚近日发布了应用搜索的新版本,主要针对安全、隐私等问题做出了改善,InfoQ就相关技术问题对其工程师进行了采访. InfoQ:首先请二位做下自我介绍. 陈兴润:我叫陈兴润,是豌豆荚的后台工程师,和吉昌一样也是早期的团队成员,主要负责应用搜索. 丁吉昌:我叫丁吉昌,我跟兴润是同期来豌豆荚的,现在我们也在一个团队,我现在算是应用搜索的负责人.

搜索引擎的认识误区与技术展望

- - 互联网的那点事
搜索结果越多越好,技术差距决定优劣,SEO可以提高搜索排名……,媒体和公众对搜索引擎的这些普遍认知,其实都是严重的认识误区. 聚合规则,排序方法,展现方式,将成为未来搜索引擎竞争的关键,而竞价排名,将随着竞争的展开逐步退出历史舞台. 随着360搜索的上线以及3B大战的展开,网络爱好者们对搜索引擎技术及市场的讨论成为近期的互联网小热点.

淘宝搜索中Query下拉推荐技术

- - IT技术博客大学习
标签:   推荐   搜索. 作者:元宗 (一淘及搜索事业部-搜索技术-算法技术-主搜索与商城). 什么是Query suggestion.    Query下拉推荐是指搜索引擎系统根据用户当前的输入,自动提供一个Query候选列表供用户选择,Query下拉提示(Query suggestion)在搜索引擎和广告竞价平台中已经是标配的产品.

从未降级的搜索技术-实时之刃

- - 搜索技术博客-淘宝
流量是互联网变现的基石,而流量的资源是有限的,如何实现资源的最大化利用(买家-商品的最高效的匹配)是此次双11搜索技术深度切入的使命,也是第一次在双11通过实时把握资源流动的脉搏来控制资源的收和放. 天猫的业务团队同学,通过针对去年双11细致认真的数据分析,发现了去年双11暴露的一些问题. 小部分商品预热过度,预热期吸引的加购量远超出商品库存能支撑的量,大部分用户虽然加了购物车但当天也抢不到,购物车转化率低;而大部分商品预热不足,没有充分曝光;.

【技术贴】9个基于Java的搜索引擎框架

- - 行业应用 - ITeye博客
9个基于Java的搜索引擎框架. 1.Java全文搜索引擎框架Lucene. 毫 无疑问,Lucene是目前最受欢迎的Java全文搜索框架,准确地说,它是一个全文检索引擎的架构,提供了完整的查询引擎和索引引擎,部分文本分析引 擎. Lucene为开发人员提供了相当完整的工具包,可以非常方便地实现强大的全文检索功能.

京东亿级商品搜索核心技术解密

- - 运维派
作者:王春明,现任京东搜索平台部负责人,2011年加入京东搜索团队,期间一直负责京东搜索引擎研发工作,主导了多次搜索架构升级工作保障其满足京东发展需求,擅长搜索引擎、高性能服务开发、分布式系统架构. 招聘: 京东搜索平台部木有有高级/资深搜索引擎研发工程师(C/C++)  、高级/资深算法工程师(C/C++)、高级/资深数据系统工程师(java)等职位,期待您的加入,一起打造弹性搜索平台.

在线AI技术在搜索与推荐场景的应用

- - 创业邦
  12月6日-7日,由阿里巴巴集团、阿里巴巴技术发展部、阿里云云栖社区联合主办,以“2016双11技术创新”为主题的阿里巴巴技术论坛(Alibaba Technology Forum,ATF)成功在线举办. 在本次分享中,来自阿里巴巴集团的研究员徐盈辉带了题为《在线AI技术在搜索与推荐场景的应用》的精彩演讲,他结合本届双11搜索和推荐场景详细介绍了电商搜索推荐的技术演变、阿里搜索推荐的新技术体系以及未来的发展方向.