【知识图谱】详解知识图谱关键技术与应用、AI图谱技术在知乎的应用实践、如何构建多快好省的“知识图谱即服务”

2 月 10 日 产业智能官

达观洪桂冠:一文详解知识图谱关键技术与应用

 集智AI学园


讲师 | 桂洪冠

来源 | AI科技大本营在线公开课


前言

本课程从知识图谱的历史由来开展,讲述知识图谱与人工智能的关系与现状;知识图谱辐射至各行业领域的应用;在知识图谱关键技术概念与工具的实践应用中,本课程也会讲解知识图谱的构建经验;以及达观在各行业领域系统中的产品开发和系统应用。


以下是公开课文本版整理


大家晚上好!我是达观数据的桂洪冠,负责达观的搜索技术团队。非常高兴今天晚上能给大家做一个分享,分享的主题是“知识图谱的关键技术和应用”。


达观数据是一家专注于文本智能处理的人工智能技术企业,我们为企业提供完善的文本挖掘、知识图谱、搜索引擎、个性化推荐的文本智能处理技术服务。



言归正传,进入今天的演讲环节。今天的演讲主题是“知识图谱关键技术与应用”,分成几个环节:


  • 一、知识图谱的相关概述;

  • 二、知识图谱的基本概念;

  • 三、知识图谱行业方面的应用和场景介绍,着重讲一下知识图谱构建的相关技术;

  • 四、达观在知识图谱构建方面的经验、心得和相关案例。

  • 最后是与大家的Q&A互动环节。 




一、知识图谱概述




我们先直观的来看一下什么是知识图谱,下面有一张图,从这张图里可以看到,这个图里圆圈是节点,节点之间有一些带箭头的边来连成,这个节点实际上相当于知识图谱里的实体或者概念,边连线表示实体之间的关系。


知识图谱本质上是一种大型的语义网络,它旨在描述客观世界的概念实体事件以及及其之间的关系。以实体概念为节点,以关系为边,提供一种从关系的视角来看世界。



语义网络已经不是什么新鲜事,早在上个世纪就已经出现了,但为什么重新又提到知识图谱?


知识图谱本质上是一种语义网络,但是它最主要的特点是一个非常大规模的语义网络,之前的语义网络受限于我们处理的方法,更多是依赖于专家的经验规则去构建,在规模方面受限于特定领域的数据。大规模网络,谷歌在2012年首先提出知识图谱的概念,在freebase的基础上扩展了大量来自互联网的实体数据和关系数据。据说目前实体的数据已经达到数十亿级,有达到千亿级的实例关系,规模是非常巨大的。

 


我们再看一下,知识图谱背后是怎么表示的,我们看到的是一个巨大的语义网,背后是怎么存储或者表示的呢?


首先,它是由三元组构成的,构成知识图谱的核心其实就是三元组,三元组是由实体、属性和关系组成的(由Entity、Attribute、Relation组成)


具体表示方法为,实体1跟实体2之间有某种关系,或者是实体属性、属性词。


举个例子,“达观数据是一家人工智能公司”,其实就可以表示成这样的三元组:


<达观数据,is-a,人工智能公司>。


“人工智能公司是一种高科技公司”可以表示成:


<人工智能公司,subclass,高科技公司>。


“达观数据成立于2015年”,也可以把这个属性表示成一个三元组,就是:


<达观数据,start-time,2015年>。


基于已有的三元组,它可以推导出新的关系,这个对构建知识图谱来说是非常重要的。我们知道,知识图谱要有丰富的实体关系,才能真正达到它实用的价值。完全靠人工去做的话是不太现实的,所以内部一定有一个自动推理的机制,可以不断的去推理出新的关系数据出来,不断的丰富知识图谱。


来看一些具体的例子。


“人工智能公司是一种高科技公司”,subclass的关系。


还有一个三元组是谷歌是一家人工智能公司,<Google is-a人工智能公司>,可以由这两个三元组推导出谷歌是一家高科技公司,<Google is-a高科技公司>。因为subclass的实例之间是一种继承的关系。


<翅膀part-of鸟>,<麻雀kind-of鸟>,可以推导出<翅膀part-of麻雀>。


为什么要用三元组来描述知识图谱?


三元组是一个人和计算机都易于理解的结构,人是可以解读的,计算机也可以通过三元组去处理,所以它是一个既容易被人类解读,又容易被计算机来处理和加工的结构,而且它也足够的简单,如果说你扩充成四元组、五元组,它整个结构就会变得比较复杂,那是综合的一种复杂性和人的易理解性、和计算机的易出理性来综合的考虑,决定用三元组的结构来去作为它的一个存储。


那么,AI为什么需要知识图谱?


人工智能分为三个阶段,从机器智能到感知智能,再到认知智能。


机器智能更多强调这些机器的运算的能力,大规模的集群的处理能力,GPU的处理的能力。


在这个基础之上会有感知智能,感知智能就是语音识别、图像识别,从图片里面识别出一个猫,识别人脸,是感知智能。感知智能并非人类所特有,动物也会有这样的一些感知智能。


再往上一层的认知智能,是人类所特有的,是建立在思考的基础之上的,认知的建立是需要思考的能力,而思考是建立在知识的基础之上,必须有知识的基础、有一些常识,才能建立一些思考,形成一个推理机制。



AI需要从感知智能迈向认知智能,本质上知识是一个基础,然后基于知识的推理,刚好知识图谱其实是具备这样的一个属性。


知识图谱其实是富含有实体、属性、概念、事件和关系等信息,它能够基于一定的推理。且比较关键的是,它能够基于一定的推理为AI的可解释性,带来全新的一个视角。


可解释性已被一些领域AI大规模使用,比如医疗领域,AI进行癌症的诊断的结果,如果没有给出一个合理的一个理由,或者是给出一个解释的一个方法,医生是不敢贸然的用AI给出的癌症诊断的结果去给病人直接做下一步的措施。包括金融领域也一样,AI如果给投资人推荐了一个投资的方案,但是没有给出任何的一个解释跟说明的话,也会存在巨大的一个风险。同样,在司法领域也是一样,用AI进行判案,AI给一个案件判定一个结果,但是没有给出任何的一个解释,也是不能作为结果来采用的,因为司法强调的就是一种可解释性,对法律的解释性、可推理性。


为什么说知识图谱可以做这样一个可解释性呢?


举个例子,我们问“C罗为什么那么牛?”


C罗为什么那么牛?这个是一个问题,要解释回答这个问题,人通常是怎么样去回答这样的问题呢?上图,通过知识图谱的简单的推理,就可以回答这样一个问题,因为C罗获得过金球奖,C罗跟金球奖之间的关系是获得奖项的一个关系,金球奖跟影响力最大的足球评选奖项之一有这样一个地位的关系,它具有这样的一个非常高的地位,C罗又获得过这个奖项,所以可以得出,C罗是很牛的。这是一种知识图谱来解释、来回答这样一个“为什么”的一个问题。


同样还有一些问题,比如,“鳄鱼为什么那么可怕?”


人类是有一样这样的常识,所有的大型的食肉动物都是很可怕,这是个常识。鳄鱼是一种大型的食薄动物,鳄鱼跟大型食肉动物概念之间是一种instance的关系。通过这样的一个常识和概念之间的关系,可以推导出鳄鱼是很可怕的。同样的,“鸟儿为什么会飞?”因为它有翅膀,鸟儿这个实体它的属性是有翅膀,利用一个实体跟属性之间的关系,可以做这样一个推理。


之前微博上关晓彤跟鹿晗非常的火,经常被刷屏,这是为什么?


因为关晓彤跟鹿晗之间是男女朋友这样的关系,明星之间的男女朋友的关系就最容易被大家追捧,也最容易被刷屏。这个就是通过关系也好,通过实体的属性也好,通过实体的概念也好,就可以去解释、去回答一些问题。这些是知识图谱在AI在可解释性方面的一些具体的例子。


深度学习的可解释性非常差的,深度学习里面内部的语义表达、向量的表达都是一些浮点数,人类是非常难以理解的。深度学习出来的结果,它的可解释性也是非常少的。


尽管我们现在在研究可视化的技术,把中间的它的结果呈现出来、可视化出来,但是真正能达到对人有效的解释性进展还是比较缓慢的。知识图谱实际上是有望能够消除人类的自然语言跟深度学习黑盒之间的语义鸿沟。也就是深度学习的底层的特征空间和上层的人的自然语言空间这种巨大的语义鸿沟,通过深度学习跟知识图谱结合起来,有望能够消除。这也是为什么AI要结合知识图谱的一个原因。




二、知识图谱的典型行业应用




1. 金融行业的应用。



知识图谱在金融行业里面比较典型的应用就是风控反欺诈


(1)知识图谱可以进行信息的不一致性检查,来确定是不是存在可能的借款人欺诈的风险,比如第一个图里面的借款人甲和乙来自于不同的公司,但是他却非常诡异地留下了相同的公司的电话号码,这时审核人员就要格外留意了,有可能会存在欺诈的风险。


(2)组团欺诈,甲乙丙三个借款人同一天向银行发起借款,他们是互不相关的人,但是他们留了相同的地址,这时有可能是组团的欺诈。


(3)静态的异常检测,它表示的是在某个时间点突然发现图中的某几个节点的联系异常的紧密,原来是互相联系都比较少、比较松散的,突然间有几个点之间密集的联系,有可能会出现欺诈组织。


(4). 动态的异常检测(第二行中间图),是随着时间的变化,它的几个节点之间图的结构发生明显的变化,原来它是比较稳定的,左边黑色的上三角、下三角,然后中间连线,但过了一段时间之后,它整个图的结构变成了右边的这样结构,此时很可能是异常的关系的变化,会出现一个欺诈组织。


(5)客户关系管理。怎么样去做失联客户的管理?图中的例子有一个借款的用户,银行可能现在没有办法直接找到他,甚至通过他的直接联系人也没办法找到他,那这个时候是不是可以再进一步的通过他的二度联系人来间接的来找到他?通过这样的图结构是可以快速找到他的二度联系人,比如张小三或者是王二,再去联系他们,尝试把李四这个人给找到。


2.辅助信贷审核和投研分析



左边是辅助审贷。


知识图谱会融合多个数据源,从多个维度来维护关联人员的信息,来避免数据不全与数据孤岛,把它整合到一个大的网络结构里面去,借助知识图谱的搜索,审核人员可以快速的获取到信贷申请人张三的相关的信息,住址、配偶、就职公司、他的朋友等等。这比原来到各个异构且散落的数据源去进行搜集的效率要高得多,且能够从整体上来看到关键实体相互之间的关联关系。


第二个是用于辅助投研的。


知识图谱能够实时地串联起来这个公司相关的上下游公司,供应商的关系、竞争者的关系、客户的关系、投融资那些关系等,然后进行快速实时的定位。中兴通讯这家公司前不久被美国政府进行合规性审查,这个时候投研人员通过知识图谱搜索到中兴通讯公司实体,进而可以非常快地得到跟中兴通讯相关的上下游公司实体,包括关联的子公司、供应商、客户、竞争对手、合作伙伴,有助于投研人员快速的做决策。


3.精准营销应用


知识图谱能够比较全面的记录客户的非常详细的信息,包括名字,住址,经常和什么样的人进行互动,还认识其它什么样的人,网上的行为习惯、行为方式是什么样的,这样就可以知识图谱挖掘出更多的用户的属性标签和兴趣标签,以及社会的属性标签,形成全面的用户洞察,基于知识图谱就可以进行个性化的商品或者活动的推送,或者基于用户的分群分组做定向营销,从而实现精准营销。



4. 知识图谱在搜索引擎里面的应用,最典型的就是在谷歌搜索引擎里面应用。



谷歌是在2012年率先提出来知识图谱的概念。提出这个概念的最主要的目的就是改善它的搜索引擎的体验。从这个图就可以看到,用户搜索的是泰姬陵,泰姬陵是印度的非常著名的,也是世界八大奇迹之一的景点。


不一样的地方,在搜索引擎的右侧,会以知识卡片的形式来呈现跟泰姬陵相关的结构化的信息,包括泰姬陵的地图、图片、景点的描述、开放时间门票等等,甚至在下面会列出跟泰姬陵相类似或者相关联的景点,比如中国的万里长城,同样是世界的几大奇迹,还有金字塔等等。同时,它还可以进行知识的扩展,比如泰姬陵不光是印度的景点,它还可以是一张音乐专辑,它甚至是国外某城市的街区街道。这样通过知识图谱可以不断的去探索发现新的非常新奇的东西,让用户在搜索引擎里面能够不断的去进行知识的关联和发现,激发起用户的搜索的欲望。原来我们搜索引擎讲究的是说快速的找到它的结果,然后关掉就完了,谷歌通过知识图谱,实际上是把搜索引擎变成了知识的探索和发现引擎,这是概念和理念上的非常大的变迁与升级。


5.知识图谱应用于推荐系统



我们比较熟悉的是个性化推荐,即所谓的千人千面,比如根据游戏来推荐游戏的道具。对于小白用户和骨灰级的用户,推荐的东西显然是不一样的,这是个性化的推荐。个性化推荐之外,还有场景化的推荐,比如用户购买了沙滩鞋,存在用户可能要去海边度假这样的场景,基于这样的场景可以继续给他推荐游泳衣、防晒霜或者其它的海岛旅游度假的产品。


任务型的推荐。比如用户买了牛肉卷或者羊肉卷,假设他实际上是要为了做一顿火锅,这时候系统可以给他推荐火锅底料或者是电磁炉。


冷启动问题。推荐系统的冷启动一直是比较难以处理的问题,通常的做法是根据新用户的设备类型,或者他当前的时间位置等等,或者外面的关联数据来做推荐。可以基于知识图谱的语义关联标签进行推荐,比如旅游和摄影实际上是语义相近的两个标签,再比如相同的导演或者相同演员的电影在语义上也是比较相近的。


跨领域的推荐问题。微博的信息流里会推荐淘宝的商品,然而微博和淘宝是两个不同的领域,它是怎么做到的呢?新浪微博有些用户会经常去晒黄山、九寨沟、泰山等这些照片,这个时候我们就知道他有可能是一位登山的爱好者,这个时候淘宝就会可以给他推荐登山的装备,登山杖、登山鞋等等这些装备,利用这些背景知识,能够打通不同的平台之间的语义鸿沟。


知识型的推荐,是基于知识的。比如清华大学、北京大学都是顶级名校,复旦大学也同样是,这个时候是可以推荐复旦大学,再比如百度、阿里和腾讯都属于BAT级互联网公司,基于百度、阿里就可以推荐腾讯。


有了知识图谱以后,我们可以从基于行为的推荐,发展到行为跟语义相融合的智能推荐。




三、如何构建知识图谱




构建知识图谱是包括这样的生命周期或这样的部分,包括定义、知识的抽取、知识的融合、存储、知识的推理、知识的应用,这样的循环迭代的过程。


我们先来理解一下本体的概念,本体是用于描述事物的本质的,维基百科里面对于计算机科学领域当中的本体给出的定义是这样的,即:对于特定领域真实存在的实体的类型、属性,以及它们之间的相互关系的一种定义。



我们再来看看知识图谱和本体的关系,下面这张图,我们看到有两个层,就下面是本体层,上面是事实层,那本体层是基于特定领域的概念的定义,包括概念的属性,概念之间的关系,一般概念之间的关系是一种父子关系,也有叫做上下位的关系。事实层是具体的真实存在的实体,包括实体的属性以及实体之间的关系,每个实体都会映射到本体层相应的概念。面向对象大家都比较熟悉,给大家举例说明一下,本体层的概念就好比面向对象里的类的概念,然后事实层的实体就好比面向对象里面的对象,对象是从类当中派生出来的,同时继承了类的一些属性和关系。这就是本体的概念。



为什么要讲本体的概念?一个更直观的例子,就是要对知识图谱来进行模式或者Schema的定义。这里的领域是科技,在这科技领域下面是我们划分的若干个主题,比如互联网主题、通讯主题、手机主题,在每个主题下面又有若干的概念,就是下面的概念层,比如互联网里面有深度学习、人工智能等等这些概念,然后通讯里面有智能手机这些概念。在概念下面就是具体的事实层面,就是实体层,比如特斯拉modelS、苹果iPhone7、华为P10等等,这些都是具体的实体,然后实体之间有关系,它继承的概念之间的关系。最下面一层是事件层,这就是整个本体层的例子。



给大家介绍一款比较好的开源本体编辑工具,叫Protégé。这个工具是斯坦福大学开源的,它的功能非常强大,也是目前最流行的本体编辑工具,有网页版和桌面版,桌面版是免安装的,大家直接下载下来就可以试用。


它的好处是什么?它屏蔽了具体的本体描述语言,用户只需要在概念层次上面进行本体的模型构建,同时也比较灵活,能够支持各种插件来扩展特定的功能。比如推理的功能可以基于插件来扩展。不过这个工具对中文的支持不是很友好。



下面一个非常重要的关键的步骤就是知识的抽取,首先要抽取实体,然后是实体之间的关系。我们看一下NER实体的抽取,我们知道NER可以转化为序列标注的问题,传统的机器学习的方法,CRF等都可以做,而且CRF做的效果还是不错的。不过CRF通常只能学习到相邻词位置比较近的上下文的特征,它无法获取整个句子甚至更长的上下文的特征。


目前业界比较主流的,包括学术界比较主流的一种做法是什么?是深度循环神经网络加上结合CRF,这样的做法更多的是双向的循环神经网络,它可以分别从前往后以及从后往前这两个方向来去学习上下文的特征,然后进行序列信号的记忆和传递,这是一种比较常见的做法。



华为发布了新一代的麒麟处理,通过从前往后就可以推理出最后面的文字,然后从后往前也可以推理出最前面的文字,第一个字“朝”实际上是从后往前去进行预测推理。顶层用CRF对循环神经网络的结果进行约束就可以,对这个输出进行更好的控制。然后输入层通常是词向量或者字向量,embedding能可以把单个字或者词转化为低维的稠密的语义向量。



下面讲一下关系抽取的技术。它有几种方法,第一种是基于有监督的方法,把关系抽取当做分类问题来看待,根据训练数据设计有效的特征,来学习各种分类模型,这是传统的分类。这个方法不好的地方,是需要大量的人工标注的训练语料,语料的标注是非常的耗时耗力的。所以在有监督的基础上,又提出了一种半监督的方式,对于要抽取的关系,首先基于手工设定若干的种子的实例,然后迭代性的从数据当中抽取关系对应的关系模板和更多的实例,通过不断迭代的方式来抽取越来越多的这些实例。


还有一种是无监督的方法。无监督的方法本质上是一种聚类的方法,用拥有相同语义关系的实体,它拥有相似上下文的信息是它的假设,因此它可以利用每个实体的上下文的信息来代表实体的语义关系,对实体进行语义关系的聚类。


这三种方法当中,有监督的方法能够抽取出有效的特征,然后在准确率和召回率方面是更有优势的,半监督和无监督的方法一般情况下,效果都不是特别的好,所以业界现在用的比较多的还是有监督的学习的方法。


我们刚刚提到有监督学习方法,比较困难的地方就是怎么样获取大量分类的训练样本,完全通过人工去标注的方式显然不是比较好的方式。


有什么样好的处理的方法?用远程监督的一种方法,典型的工具Deepdive,也是斯坦福大学InfoLab实验室开源的知识抽取的系统,通过弱监督学习的方法,从非结构化的文本当中可以抽取出结构化的关系的数据。开发者不需要理解它里面的具体的算法,只要在概念层次进行思考基本的特征就可以了,然后也可以使用已有的领域知识进行推理,也能够对用户的反馈进行处理,可以进行实时反馈的一种机制,这样能够提高整个预测的质量。背后用的是也是一种远程监督的技术,只要少量的运训练的数据就可以了。



我们来具体来看一下它是怎么样来做这样一件事情的。首先,下面看到Mention的句子就是“奥巴马和米歇尔结婚”,它是句子,但Mention就是这些词的标记,奥巴马米歇尔都是Mention,我们要推测它之间是不是配偶的关系。这个时候要对Mention:奥巴马和米歇尔,去对应到知识图谱里面具体的实体,看一下这两个实体在知识图谱里面是不是存在着配偶的关系?如果是的话,就把它拿过来作为正的训练样本,如果不是,它就是负的样本。前提假设就是知识图谱里面的它的实体之间的关系都是正确的,以这个为依据,去做样本的标注。



目前进行实体关系抽取有两大类方法,有一类是基于流水线式的抽取,输入一个句子,首先抽取这实体,再对实体进行两两组合,然后再进行分类,最后识别出实体之间的关系。这种做法是有缺点的,第一,它容易造成错误的传播,比如在第一步的时候,实体如果识别错误了,后面的关系肯定也是错误的。第二,会产生没有必要冗余的信息,因为要对实体进行两两的配对,然后再进行关系的分类,很多配对之间实际上就没有这样的关系,就是它会带来了这样非常多的冗余的信息,错误率也会被放大、被提升。


现在用的比较多的另一种方法,是联合学习的方法,输入一个句子,通过实体识别和关系抽取的联合模型,可以直接得到有效的三元组。通常我们是基于神经网络的联合标注的学习的方法,里面涉及到两个关键的工作,一个是模型的参数共享的问题,还有一个就是标注策略,怎么样进行有效的标注。模型共享是指的是在实体训练的时候能够进行实体识别和关系分类这两个任务,都会通过反向传播来匹配来进行关系的分类,然后同时来实现这两个参数之间的依赖,两个子任务之间的依赖。参数共享的方法,它本质上还是两个子任务,只是说它们这两个任务之间通过参数共享有了交互,而且在训练的时候还要预先进行实体识别,识别实体之后再根据预测信息进行两两匹配,来进行关系的分类,所以仍然会产生无关系时候冗余的信息存在。



现在我们新提出了一种端到端序列标注的策略,把原来涉及到序列标注和分类的两个任务变成了完全的端到端的序列标注的问题,通过端到端的神经网络模型,可以直接得到关系的三元组,即实体关系的三元组。


新的标注策略是像下面这张图里面有三个部分来组成的,第一部分是实体中的词的位置,比如b是表示开始,i表示是在实体的内部,e表示是实体的结尾,s表示是单个的实体。第二部分就是关系类型的信息,预定义的关系类型的编码,比如里面的CP、CF,CP是国家总统,CF是公司创立者,这样两种的关系。还有实体的角色的信息,它表示是实体1还是实体2?实体跟关系之外的其它的这些字符都用O来表示,这样就进行了实体的标注。



接下来我们讲一下实体的融合,这里最主要就是实体的对齐。


首先是实体对齐,也叫实体归一化,是把具有不同的标识的实体,但是在现实世界当中可能是表达同样意思的,把它做归一化。比如中华人民共和国、中国和China,这个三个指的是同一实体,尽管它的表述方式不一样,就把它归一化为具有全局唯一标识的实例对象,然后添加到知识图谱当中去。


现在实体对齐普遍采用的还是一种聚类的方法,关键在于定义合适的相似度的阈值,一般从三个维度来依次来考察的,首先会从字符的相似度的维度,基于的假设是具有相同描述的实体更有可能代表同实体。第二个维度,是从属性的相似度的维度来看的,就是具有相同属性的和以及属性词的这些实体,有可能会代表是相同的对象。第三个维度,是从结构相似度的维度来看,基于的假设是具有相同邻居的实体更有可能指向同对象。


进行融合的时候要考虑各个数据源的数据的可靠性,以及在各个不同数据源当中出现的频度来综合决定选用哪个类别或者哪个属性词。还有一种方法就是是用来自LD(LinkedData),LD是很多人工标记好的数据,是非常准确的,其中有种关联叫owl:sameAs,它表示前后两个是同实体的,利用这个作为训练数据来发现更多相同的实体对,是比较好的方法。最后要说的是,无论用哪种方法,都不能保证百分之百的准确率,所以最后也要有人工审核和过滤。

 


知识存储,就是如何选择数据库,从选择层面,我们有图数据库,有NoSQL的数据库,也有关系型数据库,数据库有很多选择。具体什么样的情况下选择什么样的数据库?通常是如果说知识图谱的关系结构非常的复杂、关系非常的多,这时候建议使用这个图数据库,比如Neo4J这样的数据库。另外一种就是它的关系并不是很复杂,关系可能也就是1度、2度的关系,更多的它是有非常多的属性的数据,这个时候可以考虑关系式数据库,或者是ES这样的存储。如果要考虑到知识图谱的性能、可扩展性、可分布式,是可以结合NoSQL的数据库,比如TiTan。根据实际的情况,一般是综合起来使用的,根据我们的经验,我们会结合Neo4J和ES来综合来使用,同时还结合这关系型数据库MySQL等等,根据不同的数据的特点来进行选型,而不是说一味的追求图数据库。



顺便了解一下目前主流的几款图数据库,Titan、Graph Engine、Neo4J这个三个分别都是开源的,然后Titan是Apache旗下的,Graph Engine是MIT的License,Neo4J是GPL开源的,既有商业版,也有也有开源免费版。然后它们的平台,像Titan是Linux,Graph是windows。而数据的支撑量级,像Titan是后端存储,基于Cassandra/Hbase/BDB这样的分布式存储引擎,可以支持更大的数据量,千亿级的数据量级;Neo4J商业版也可以支持到百亿级的,但是它的非商业版在数据量级比较大的时候,一般是在几千万级的时候就可能会出现一些问题。



再看一下知识推理,知识推理这边有几种方法,首先是基于符号推理,我们上面说的三元组的结构,比如左边的RDF,有概念,然后基于概念符号进行推理。



这个是基于OWL进行本体推理的例子,这个背后是基于OWL本体的推理,最常见的OWL推理工具是Jena, Jena 2支持基于规则的简单推理,它的推理机制支持将推理器(inference reasoners)导入Jena,创建模型时将推理器与模型关联以实现推理。

 


还有一种是基于图(PRA)的推理的方法,更直观的一种方法,思想是比较简单的,就是以连接两个实体的已有路径作为特征构建分类器,来预测它们之间可能存在的潜在关系。


比如左边这个图里面Charlotte Bronte,我们要预测他的职业是不是作家。在这个图里面已知存在关系是什么呢?他写过一篇小说,它写过一篇小说Jane Eyre,然后双城记也是一部小说,狄更斯是写了双城记这部小说,狄更斯是作家,同时它下面还有他的父亲职业也是作家,所以基于这样图之间的关系,就可以较大概率的推理出Charlotte Bronte的职业很有可能就是作家,这就是基于图之间的关系的特征构建分类器来进行预测的。 PRA提取特征的方法主要有随机游走、广度优先和深度优先遍历,特征值计算方法有随机游走probability,路径出现/不出现的二值特征以及路径的出现频次等。PRA方法的优点是直观、解释性好,但缺点也很明显,有三个主要缺点:首先,很难处理关系稀疏的数据,其次,很难处理低连通度的图,最后,是路径特征提取的效率低且耗时。

 

 

还有是基于分布式的知识语义表示的方法,比如像Trans系列的模型,在这个模型基础上进行语义的推理。TransE这个模型的思想也比较直观,它是将每个词表示成向量,然后向量之间保持一种类比的关系。比如上面这个图里面的北京中国,然后类比巴黎法国,就是北京加上首都的关系就等于中国,然后巴黎加上capital的关系等于France。所以它是无限的接近于伪实体的embed]ding。这个模型的特点是比较简单的,但是它只能处理实体之间一对一的关系,它不能处理多对一与多对多的关系。



后来提出了TransR的模型了,TransR实际上是解决了上面提到的一对多或者多对一、多对多的问题,它分别将实体和关系投射到不同的空间里面。一个实体的空间和一个关系的空间,然后在实体空间和关系空间来构建实体和关系的嵌入,就对于每个元组<h,r,t>首先将实体空间中实体通过Mr向关系空间进行投影得到hr和Tr,然后Hr加上r是不是约等于或者近似的等于Tr,通过它们在关系空间里面的距离,来判断在实体空间里面,H和T之间是不是具有这样的关系?


除了TransE、TransR,还有更多的Trans系列的,像TransH、TransN、TransG等等这些模型。清华大学的自然语言处理实验室发布了一款这个叫openKE的平台,openKE它是开源的知识表示学习的平台,是基于TensorFlow的工具包来开发的。它整合了Trans系列的很多算法,提供统一的接口。它也是面向了预训练的数据来表示模型的。



最后介绍一种基于深度学习的推理模型,这个模型利用了卷积神经网络对实体进行关系的分类的,把句子的依存树作为输入,就是将词在树中的不同的位置的嵌入式的表示拼接到这个词向量当中来学习,同时对面向树结构设计了独特的卷积核。这种方法在实体分类的任务上,相较于未使用位置关系的信息,效果会有一定的提升。




四、达观经验与案例




1.知识图谱在达观的知识问答当中的应用


我们的智能问答是融合了是知识图谱问答和基于检索的问答两种方法进行融合。


首先,左边会把用户的语音经过语音转成文字以后,进行一个预处理,预处理主要是做了分词、纠错、词性标注、实体属性的识别,对这个句子进行依存句法树的结构分析。



预处理完了以后,引擎会首先尝试根据问句的句法结构进行问句模板的匹配,如果说能够匹配到合适的问句模板,这个时候再根据在预处理阶段得到的问句的实体属性和关系,对匹配到的问题模板进行实例化,然后再根据实例化以后的问句模板来生成知识图谱的图数据库的查询语言,然后在图数据库里面就可以把这个答案查出来了。


另外一种情况是没有匹配到合适的问句模板,这个时候会进入到基于检索的问答模块,最后是把基于知识图谱和基于检索的两种的结果进行融合。


2. 在HR人岗精准匹配里面的应用


HR创建的JD能够自动的匹配到简历库里面最合适的候选人的简历,也即把JD的内容和简历库里面简历的内容做语义的匹配。


这里有一个问题,JD对技能的描述和不同的人的简历中对技能的描述存在很多表达方式造成的语义方面的差异。我们分别对JD和简历构建技能图谱,通过技能图谱的子图匹配,就可以比较好地来解决语义匹配的问题。


我们在知识图谱建设当中的一些经验:


  • 第一,界定好范围,就是要有一个明确的场景和问题的定义,不能说为了知识图谱而知识图谱。如果没有想清楚知识图谱有什么样的应用的场景,或者能解决什么样的问题,这样的知识图谱是比较难以落地的。一些明确的场景,比如解决商品数据的搜索问题,或者从产品说明书里面做相关问题的回答。


  • 第二,做好schema的定义,就是上面讲到的对于schema或者本体的定义。第一步确定好场景和问题以后,就基于这样的场景或者问题,再进行相关领域的schema的定义。定义这个领域里概念的层次结构、概念之间的关系的类型,这样做是确保整个知识图谱是比较严谨的,知识的准确性是比较可靠的。知识的模型的定义,或者schema的定义,大部分情况下是通过这个领域的知识专家的参与,自上而下的方式去定义的。


  • 第三,数据是知识图谱构建基础。数据的梳理就比较重要,最需要什么样的数据?依赖于我们要解决的问题是什么,或者我们的应用场景是什么?基于问题和场景,梳理出领域相关的问题、相关的数据,包括结构化的数据、半结构化数据、无结构化的数据,结合百科跟这个领域相关的数据,领域的词典,或者领域专家的经验的规则。


  • 第四,不要重复去造轮子,很多百科的数据和开放知识图谱的数据,是可以融合到我们的领域知识图谱中。


  • 第五,要有验证和反馈机制,需要有管理后台,用户可以不断的和知识图谱系统进行交互,不断的进行确认和验证,确保知识图谱每一步推理和计算都是准确的。


  • 第六,知识图谱构建是持续迭代的系统工程,不可能一蹴而就。


最后给大家介绍中文开放知识图谱,达观数据也是中文开放知识图谱发起单位之一,这里面有很多开放的数据和开源的工具,其中的文章也是非常好的学习材料。




答听众问:(向下滑动查看更多)



Q:用知识图谱来做反欺诈,和深度学习的方法相比,或者是其它机器学习的相比,知识图谱是否有优势?


A:反欺诈是整个风控流程中的一个非常重要的环节。其主要难点在于如何基于大数据把多个不同来源的数据(内部、外部,格式化、非格式化)有机整合在一起,并对这些数据之间的各种复杂且动态变化的关系进行建模,从而构建起一个反欺诈引擎。知识图谱作为关系的直接表示方式,可以提供一种非常直观的可视化的手段以及内部的推理机制来有效地分析各种复杂关系下可能存在的潜在风险。


我们知道深度学习的表示是基于一种低维稠密的数值向量,模型本身是一个“黑盒”,我们无从知道内部的各种特征的非线性组合是如何形成的。相比于知识图谱,深度学习的不可解释性是最大的缺点。此外深度学习要真正达成效果,需要依赖已经标注过的大样本数据进行训练,但在很多领域(包括反欺诈)这样的数据获取门槛极高。


当然,深度学习和知识图谱也是不完全互斥的,知识图谱的构建中的实体、属性、关系抽取等关键过程也会用到深度学习的循环神经网络等自然语言处理技术。

 

Q:知识图谱的查询跟关系数据库的查询感觉都一样,这两个有什么样的关系?


A:在关系型数据库里面,如果要联合多个表执行复杂查询,特别在数据量比较大的情况下是非常慢的。如果涉及到多种很复杂的关联关系,图数据库是比较好的选择。图数据库基于图的遍历,内置对图搜索的优化算法,可以非常快速进行子图的搜索。相较于传统的关系数据库,其性能会有多个数量级的提升。


Q:纯文本怎么进行抽取?


A:关于抽取,我在前面讲到了有很多的方法,包括实体抽取里面有NER的方法,NER有传统的CRF的方法,有基于循环神经网络+CRF的方法,也有端到端的联合标注的抽取方法,这种方法同时输出实体和实体之间关系的三元组。


Q:知识图谱怎么和其它算法相结合,应用在搜索推荐上面?


A:在搜索里面,更多的是基于知识图谱去回答问题,它可以对query所表达的实体和属性进行识别,比如查询“华为P10手机的内存是多少?”这就是实体属性值的查找。华为P10是实体,内存是P10这个实体的属性,对应到知识图谱里面,可以快速定位到这个实体叫P10,就可以直接把P10的内存(属性值)返回出来,就可以直接给出64G或32G这样的答案。


Q:实体有哪些属性是怎么定义的?


A: 从如何定义的角度看,主要有两种方法,一种是自上而下的方法,比如我们进行模式(Schema)定义的时候,首先会对其中的各种概念进行定义,概念有哪些属性,概念之间的关系是什么样的。后面抽取的各个实体都会映射到模式层的一个概念上去,实体会自动继承所属概念的属性。还有一种是自下而上的方法,实体的属性是从原始数据中不断抽取提出来的,并对不同数据源的属性与属性值进行融合(归一化)。实际使用中,这两种方法往往是同时使用互相补充的。


Q:知识图谱中的时间和空间关系怎么表达?


A:知识图谱表达的是动态的数据,比如美国总统是特朗普对吧?现在是的,但三年前不是,五年后也不一定是。随着时间的推移,它的三元组的关系是会有变化的,那这个时候怎么样去表达?通常是在三元组的基础上再扩展一个维度形成四元组这样的做法,但是它会大大增加系统处理的复杂度。也有一些其他的方法,比如可以是跟关系数据库相结合的方式进行扩展。


Q:如何衡量一个知识图谱建立以后的效果?如何有效的进行学习改进?


A:我们建立一个知识图谱,建立一个机器学习的算法模型,对它的效果进行衡量是非常关键的。在知识图谱这里,一定是基于某个场景具体的应用,然后再看这个场景或者这个具体的应用使用了知识图谱以后跟原来的做法来做一个比较,或者有一个管理后台,人可以定期对知识图谱系统的推理和计算的结果做一些检测和验证,然后对这些验证的结果再反馈到这个系统里面去,让系统重新来进行学习、改进,建立人跟系统之间不断的反馈、验证和自动学习的过程。


Q:可不可以用知识图谱进行分类?


A:这个问题很有意思。上面提到,一方面我们可以基于分类的方式来做知识图谱中实体关系的学习。另一方面,我们是否可以利用知识图谱辅助进行文本的分类?这样方面我们有一些经验。对于文本分类中的特征工程,我们的做法是通过知识图谱进行语义的关联扩充以获取更多的语义特征,尤其是对于短文本,对分类效果能有比较好的提升。








黄波:AI技术在知乎的应用实践

AI中国 

导语:本文根据知乎知乎AI团队技术负责人黄波于第十届中国系统架构师大会(SACC 2018)的现场演讲《知乎如何利用AI理解内容和用户》内容整理而成。

讲师介绍


黄波,知乎AI团队技术负责人。负责知乎NLP与用户画像相关技术与业务。硕士毕业于北京大学智能科学系,曾在JMLR、ICLR等国际顶级期刊及会议发表多篇学术论文。在加入知乎前,曾任百度自然语言处理部门高级算法工程师,从事智能交互、语义表示、语义标签、内容质量的研发工作,参与了度秘、百度feed流等产品的关键技术突破。

正文:

大家下午好,非常感谢SACC大会的邀请,我今天演讲的主题是AI技术在知乎的应用,内容重点介绍偏底层的相关技术,包括知识图谱、内容分析与用户分析。最后会简单介绍这三块技术在相关业务线的应用。

一、知识图谱的构建与应用

我们先来看一下知识图谱,知识图谱的构建包括三个核心要素:本体、本体属性以及本体间的关系。其构建过程大概分三步:第一步基于互联网上结构化和半结构化数据抽取本体信息,再通过知识融合构建统一的本体库,这里本体通常包括实体、概念、事件等;第二步我们会挖掘本体的属性以及本体间的关系,比如本体“勒布朗 詹姆斯”的类型属性是”人物”、领域属性是”体育“,与本体”德怀恩 韦德“有较强的相似性,与本体”NBA“属于上下位关系等;第三步是知识图谱的表征,我们可以利用离散的 RDF 规则语言和基于神经网络的 embedding 方式来表示知识图谱。

接下来看下知乎怎么做知识图谱的构建,我们主要围绕着知识图谱的要素来做,首先是一个本体,本体我们以知乎的话题为核心,同时会把互联网上百科词条相关的一些实体与话题进行融合,做一个映射。还有一个要素是内容,就是这个对象本身的一些名字、描述、解释。另外一个要素包括本体的类型,它是人物还是地点。然后所属的领域也是一个要素,是互联网、还是体育。最后更重要的是各种要素之间,我们可以去构建不同关系。

比如话题,我们可以构建两种关系。第一种是话题的上下位的关系,上图中可见,韦德的上位话题是NBA球员。另外话题之间也可以有一个相似度的一个关系,比如说韦德这个话题和詹姆斯这话题他们就相似的非常高。上下位是有方向的,相似度是没有方向的一个关系。另外我们话题和领域也都有一个单向的关系,詹姆斯属于二级领域,NBA它属于一级领域。话题和类型也有关系,如詹姆斯这一个话题是人物的类型。

我们围绕这些要素去做一个知识图谱的构建,构建完之后,需要对知识图谱进行表示。常用的知识图谱表示有两种,一种是离散的方法,我们可以通过各种RDF或者这种规则的方式去表示知识图谱。它的优点是表示方法很直观,可以很好地解释知识图谱的内部逻辑。另外通过各种复杂的规则,它也可以很好的支持很多很复杂的知识结构。这种离散的表示法有它自己的缺点,比如说非常稀疏,还有扩展性也比较差。

另外一个最近比较流行的是通过各种Embedding和神经网络的方法,对整个知识图谱做一个连续向量的表示,把知识图谱的关系或者说本体的一些概念映射到一个低维空间里面。它的优点就很直观了,就是我们得到表示是一个低维稠密的,对于各种深度学习模型非常友好。缺点是它得到的表示,可解释性没有离散表示强,表示能力也稍微弱一点,对于很复杂的知识结构不能够很好去支持。

我们知乎怎么去做这个知识表示的工作,我们主要围绕话题为核心来做语义表示。下图是一个例子,这是问题的标题,“科比和詹姆斯的区别在哪里?”会打上对应的五个话题,有NBA有科比,有詹姆斯……等等。这里我们模型的输入层包括一个话题的表示,以及一个窗口的构造词,把他们的Embedding加起来去预测窗口中心的词。另外在我们的目标层还有两个其他任务,一个是我们要通过这个话题去预测另外一个话题,这个也是我们模型的一个预测目标。另外是之前知识图谱构建的一个类型,也会放到我们这个目标里面来作为模型的预测。

最终这个模型训练完之后,我们的话题“詹姆斯”和所有的词以及其他话题都会映射到同一个语义空间里面。有什么用呢?就是大家都在同一个语义空间里了,最直观的用法就是我可以得到一个话题的相关性图谱,任何两个话题之间,都可以给你算一个相关性得分。比如说这里的话题Facebook,可以把跟Facebook这个话题很相关的其他话题拿出来,比如说扎克伯格、Facebook广告类似的这些话题。这里就可以用在用户推荐里面,用户感兴趣的一个图谱,或者说用户信息的一个扩展。

二、内容分析实践

讲完知识图谱,接下来讲内容分析。什么是内容分析呢?简单来说就是给内容打上各种各样的标签。比如说语义层面的一二级领域、话题、实体、关键词。举个例子,是关于物理的——“有哪些看似荒谬的事,却有着合理的物理解释?”话题。它的一级领域是自然科学,二级领域是物理学,同时会有其他细粒度话题,科普、物理科普、冷知识等等。除了语义标签这一个维度的标签以外,我们还会打上质量的标签。我们模型会判断某个回答是不是一个很专业的回答,给出一个专业性得分;另外还会去算这个回答跟问题的相关性,给出一个提问相关性的得分。然后,还会有一个时效性得分,可以用在推荐系统里面,做一些长期的推荐,如果是低时效的内容,可以一直在推荐系统里流通,如果是高时效的内容,过一段时间之后,我们不再让它流通了。

关于语义标签,我们由粗到细构建了一个语义标签体系。从领域、话题到实体/关键词,它们的粒度是从粗到细的。为什么要做这种多粒度的语义标签?其实在不同的业务场景,大家对于这种语义标签是有不同要求的,粒度越粗的,比如说一二级领域,我们希望它是一个粒度相对较粗,并且是一个尽量完备正交的分类体系,这样对于任何一个问题和文章,我们都能保证把它对应到某个一二级领域。话题这块我们希望的是模型能够高准确度地打出结果,并且同一个问题和文章可以打上多个话题。针对实体/关键词,也是类似的,我们只是要求模型的准确度比较高,优先保证热门的实体/关键词被召回就可以了。

接下来会具体展开讲几个模型,我们怎么去做内容分析的。

内容分析——领域分类

首先是领域分类,我们当时做的时候面临一个问题,我们梳理出一个分类体系了,但分类体系是没有训练数据的,短期内也不想通过人为去标很多训练数据,那要怎么构建训练数据?我们就是把原始语料和之前构建的知识图谱结合在一起,去构建一个带噪声的新的数据。如下面这个例子,“零基础如何学绘画?”这个问题关于绘画和自学,绘画在知识图谱里面所属的一级领域是艺术;自学所属的一级领域是教育。这样的话,这条训练数据就有两个level,一个是艺术,一个是教育。可以看到教育可能在这条数据上是错的,就是我们得到训练数据是带有噪声的。为了解除这种噪声,我们在设计的时候加入两个降噪层来对噪声进行降噪。同时预测阶段我们也用了一个ensemble的模型来进行模型的预测。


上图是我们文本分类的一个模型。文本分类有一个传统方法,就是我们去进行一些简单的预处理,然后加一些人工特征,再把这个特征出到上层的一个浅层模型。最近几年比较流行的是通过深度学习方法来做一个分类,比如说通过FastText,TextCNN和RNN/LSTM相关的一些模型。这个模型用在我们这个数据产品上有一个问题,它没办法去除我们训练数据里面的噪声,所以说我们单独设置了一个降噪的模型来对这个数据进行降噪。针对降噪层,我们加入两个东西,第一个是,这个模型最左边是问题的标题(question title),通过问题标题有一个embedding,embedding通过一个LSTM再过一个Attention得到这一个问题标记的一个表示。右边是对于问题的自带的话题(question topic),做一个话题的表示,再把话题表示加起来,然后通过一个Identity+L1的一个Noise的一个降噪层去得到这一个topic的表示。

这两个表示我们把它结合在一起去做一个损失函数计算。这个损失函数计算,我们包括两两层,第一层是一个交叉熵,通过交叉熵我们发现就有一个问题,因为之前构建的训练数据,同一个数据可能会出现多个标签,这种标签有些是对的、有些错的,单纯通过交叉熵模型去很难去降低这种噪声的影响。我们这里在损失函数里引入了一个降噪逻辑,具体来说是加入了sigmoid的损失和一个最小熵的正则。这里我可以详细解释一下,比如刚才“绘画”例子的数据,它打了两个标签,如果用交叉熵来算损失,这个是不太好计算的,噪声也没办法去除掉。我们通过sigmoid,不限制预测的结果,加起来等于1,大家都可以是1。比如说我的模型分类,你的数据是艺术教育,我模型都可以去分,这两个概率都接近1。加上这个之后又有一个问题,就是说模型倾向于把所有的数据都去打上1,那这样我们就加了一个最小熵的正则,这样我保证在最终输出才能得到结果。它是一个熵比较小的,也就是说某一个值比较大,其他比较小,这样就限制了模型把所有数据都打成1的情况。

在另外是一个在预测阶段,我们采用了ensemble的方式,这里是利用了知乎数据特有的特点。因为知乎的数据每一条数据带有话题,这个话题是人打的,有好有坏。人打的好处就是可以引入额外的一些知识,坏处是也会引入一些噪声,所以说我们就是把话题和标题两个模型去ensemble起来,进行预测。

内容分析——话题匹配

我们再看一下话题匹配。话题匹配是一个文本的做标签的任务,它的定义是给定一段文本,从给定话题集合中匹配出相应的话题。它的应用场景就非常直观,我们可以对问题和文章进行话题标注,比如这里有个例子,“如何评价美剧西部世界”,我们可以打“西部世界”、“西部世界第二季”、“美剧”、“人工智能”等。如果大家平时用知乎提问,你去梳理一个问题之后会推荐相应的候选集,那个也是整个话题的一个模型。

另外一个层面,我们针对用户输入搜索的一个Query,也可以去匹配出相应题。一方面可以用于搜索的一些特征,另外一方面也可以去沉淀出用户的兴趣画像,另外也可以对Live和私家课等相关的其它资源做一个相关的话题标注。

这一个话题匹配我们在做的时候,分析这个问题非常难,到底难在哪?我们大概把难点拆成三块:第一,话题本身语义粒度的差异特别大。大到领域级别的“娱乐”这种话题,小到“吴亦凡”这种实体级别话题,这样模型其实很难去学习这种差异性特别大的一个目标;第二,话题集合数也非常大,大概是10万量级,长尾话题(出现次数小于10)特别多,占比大概80%以上;第三,话题之间语义相似度特别高,比如说“Python”和“Java”,还有“插画”和“绘画”这种,通过深度学习模型很难去捕捉这种细微的差异。我们其实中间也尝试过很多端到端的深度学习方法来做这个事情,比如说通过FastText、Matching CNN和LSTM+Attention的方法来做。但这些方法都有一个问题,就是模型倾向于预测偏高频的一些话题,针对于低频的、针对长尾话题,它们效果都比较差。

我们在做的时候把这一个问题拆解成了一个系统性的工作,类似于推荐系统一样,我们把它做成一个召回+排序的一个过程。召回的逻辑是你先给一个资源过来,我们从标签库里面去召回出候选的数十个话题,再通过这数十个话题进行一个精细的排序模型,来得到最终的结果。最终我们这个效果是非常不错的,准确是93%,召回是83%。

具体来看我们怎么做的?在召回层分三个策略,第一个是比较简单,就是我直接去做一个AC多模匹配,把匹配出的话题作为候选集合;另外一个是比较有意思的,我们在经典的点互信息(PMI)的算法上做了一个优化,提出了一个两趟对齐算法,这个就能解决类似“Python”和“Java”的这种问题;还有一个是我们会利用之前构建的知识图谱,把话题的上位话题也作为候选集合召回回来。


在排序的时候,因为刚才提到了,单一的深度学习模型对于我们特定的话题匹配学这个问题是不太适用的,所以说我们在深度学习的模型基础上,也加入其他的一些规则,去做一个多策略融合的排序工作。这个深度学习排序模型比较经典,如上图,左侧是文本的词,过一个embedding,再过LSTM,再过一个Attention,得到这一个文本,这段我们表示。右侧是分别是这个话题的样本,这边是正样本的一个表示,上层再过一个全连接,跟着一个文本的表示算一个相似度。副样本也跟着一个,我们的表示算一个相似度,这两个像素之间再算一个损失。我们加的这三个规则分别是什么意思?第一个规则是说我这个话题需要跟候选召回回来的话题集合算一个相似度得分。其实有一个趋同效应,如果你这个话题是对的,你应该跟周围大部分话题都比较像。还有一个规则是我们通过话题图谱的权重有一个得分,另外一个规则就比较直观了,完全匹配的,这种我们会给他加权。

内容分析——专业性

剩下一个是内容专业性的分析。专业性这个非常重要,因为我们知乎其实鼓励大家去生产专业性的内容,同时去鼓励专业内容在知乎得到更多的流通,但是有个难点,机器怎么知道你那个内容是不是专业性,或者推荐算法怎么能知道这个内容是不专业的,那我们就需要去做一个前置的工作,去通过模型来判断这个文章是否专业。这个问题比较难,难在哪儿,第一个是专业性这个定义非常模糊,就是我给你一个数据,你可以告诉我它是不是专业性的,但是制定一个标准,什么东西是专业性的?这就非常难,因为专业性随着不同的领域差异特别大。另外一个是训练数据的获取成本也很大,因为标准不明,也很难去标一个高质量的训练数据。

我们在做的时候拆成两个阶段,第一个阶段是通过用户行为,这里主要是通过用户收藏的行为,因为我们发现专业性的内容,用户倾向于去收藏,然后通过用户收藏夹去做一个配置算法,去算出每一个收藏夹的一个权重和对应收藏夹里面的文章的一个权重,当做专业性的得分。

这个方法它的优点是准确度非常高,缺点是覆盖相对较低。因为是基于用户行为的,会有一定的滞后性,我们对于新的内容没法去判断它是不是专业。在第二个阶段,我们就用了一个纯的文本语义的模型来做。这里有没有传统的文本分类的一个方法,为什么不用深度学习来做专业性的识别?因为刚才提到训练数据成本很大,我们现在可能就只有几万条训练数据,专业性的回答和文章又特别强,如果你直接用深度学习不断地堆上去,直接就过拟合了。这里我们做了很多人工相关的特征,主要包括两个层面。第一个是文本风格的特征,包括词性,还有标点相关的。另外一个这个是非常重要的,语义特征,我们通过大量的数据去做一个词的聚类,把类簇当作专业性模型的一个基本特征,这个特征在我们后面随机森林模型里面特别重要。所以最终我们专业性的效果现在只是初版,针对专业性内容识别准确是84%,召回是60%。

三、用户分析实践

讲完内容层面,用户层面也类似,其实我们要做用户分析,也是想去给用户打上各种各样的标签,以及用户之间的一些关系,包括用户的姓名度。具体展开来讲,三个层面,包括用户的基本画像的一个预测,像性别年龄以及用户本身的一些登陆地、设备信息相关等等这种基本的属性。还有一个跟推荐系统相关的,就是用户兴趣的画像,这里我们分了三大块,第一大块是用户的一个被动兴趣,这可以解释下,我们把它叫做用户在推荐流里面的浏览和点击的行为,这种行为我们把它叫做被动兴趣。主动兴趣这里,因为知乎有它的特殊性,就是很多用户会去搜索,也会关注也会收藏,我会把单独这些行为在做一套兴趣出来,就是抽象成一个主动的兴趣。

另外根据之前的一些标签,比如专业的标签,我们可以去算出用户对于专业性内容的一个偏好以及对于类型的偏好,比如这里一个例子,“程序员张三”性别是男,兴趣标签有AI、机器学习,类型偏好是偏好于比较喜欢看专栏文章,对于回答和视频,他的偏好相对较弱,专业度内容偏好是0.8非常高,说明他在知乎里面可能只看专业性的内容。另外一个用户“运营小丽”她可能就是看一些综艺和电视剧相关的一些资讯,它对专业性内容偏好就叫弱。还有一个层面是用户社交的一个表示和挖掘,因为知乎它也有一定的有很强的社交属性。我们通过用户的社交行为去学习用户的一个表示,进而来做一些用户聚类、用户亲密度相关的一些工作。

用户分析这个问题,其实它离不开一个东西,是大数据的处理,因为用户的日志量其实太大,所以说我们需要做一个比较完善的服务架构,才能支撑我们上层很多用户画像的计算。这里我们大概设计了三大块,第一个是实时计算,包括用户实时行为的存储,用户实时兴趣的计算。另外是离线计算这一块,就是一些模型的预测,有可能是“天”级别的,有可能是“月”级别的,包括用户的基本发行的预测和用户表示,还有用户聚类与人群划分相关的工作。


最后是在线服务这一块,我可以解释一下Hbase多集群同步什么意思?因为离线计算是一个批量的过程,是我批量预测所有用户的性别或者说人群属性的结果,我需要“灌到”线上服务里面去让业务方去用,那这样我们不能直接灌到在线集群,你直接打到在线集群就崩了,所以说我们需要先灌到离线集群,再做一个流式的同步,去把离线集群的结果同步到在线平台,这样就能保证线上的服务是稳定的。另外我们也会去做一些缓存相关的工作,来支持一些线上高并发的请求。

下面讲的是我们通过streaming的方式来进行用户实时兴趣计算的流程。大概逻辑是,我们会把用户的点击日志、展现日志以及搜索日志拿过来做实时分析,抽象出用户和对应的内容的Token,以及它对应的行为,抽成一个三元组。这个三元组抽取完之后,我们再去对内容进行进一步的分析,提取这个内容对应的话题和关键词相关的一些标签。针对于问题、文章、回答,我们直接通过之前缓存算好的内容画像里面去获取它的标签就可以了。针对用户搜索的query,因为这个东西没有没办法提前算好,所以说我们这里需要去调用语义理解的相关一些模块,比如说关键词提取模块,以及话题匹配的这一个模块,得到query对应的话题和关键词。

提取了内容的标签之后,我们会得到一个用户以及标签,还有行为三元组的一个聚合结果,这个结果就作为最终用户兴趣计算的输入。用户信息计算在算什么?主要是包括一个新兴趣的叠加,还有老兴趣的衰减,这里会去做一些参数平滑以及打压热门,一些热门话题或者热门关键词的一些工作。

然后是用户表示和聚类,主要思想还是想通过一个神经网络或者各种embedding方法去把用户表示在一个低维空间里面,表示完之后我们就可以去做很多的应用。知乎在做这个事情,有必然的优势,我们训练数据非常多,第一个是用户社交关系,不管是单向还是双向的。还有用户有很多关注问题/专栏的数据,另外用户也会收藏相关的回答/文章,我们把这三种数据揉到一起就组成了一个图,针对这个图,我们利用了一个graph embedding方法去获取每个用户的表示。

四、典型业务应用场景

关于用户表示,它的应用场景非常多,第一个场景就是受众的扩展,第二个是我们可以得到一个简单的用户聚类,这个聚类如果进一步分析,就可以给每一个类打上一个人群的标签,用于做人群或者圈子的划分。

刚才提到了知识图谱,还有内容分析和用户分析,其实都是最终有应用目标的,它最大的一个应用目标就是在首页信息流的推荐。整个内容分析和用户分析会作为整个推荐系统的一个底层的很重要的特征,用于召回和排序。当然召回除了基于标签这种召回方式,也会有基于协同算法和最近比较流行的基于神经网络的一些召回方式来做。在排序的时候,我们不只可以去优化时长,CPR作为目标,也可以把我们标签识别出专业性的占比去做一个目标来进行优化。

刚才也提到,推荐系统不用这个标签也可以,用协同和神经网络也可以做,那么我们用标签来做推荐系统召回有什么优点和缺点?优点我这里列了四点,第一个,可解释性强,粒度越细越准确;第二、会越用越准,能积累长期兴趣;第三、可以对各种标签做比例的精准控制,比如说我就强制要求你召回,在这里面专业性的内容占比必须达到多少;第四,没有内容冷启的问题,任何一个内容我通过标签都可以被召回被推荐。

但是基于标签有它自己的缺点,就是泛化性相对较差一些,也不是所有内容都能打成这种形式的标签。

除了首页推荐的场景以外,我们这种标签也可以用于其他的一些数据分析和决策用,比如说我们可以去分析专业性内容在生产和消费的一个分布情况,另外也可以去按领域维度来对内容生产和消费进行分析,还有一个是我们可以按人群来看,比如说我可以看大学生对于各种内容的生产/消费情况。

这里是一个受众扩展的例子,就是我们把用户的表示训完之后,这是一个很直观的应用场景,就是我们有一些私教课,它有一批已经点击或者已经购买人群,现在我们需要在针对这个私家课会发一些优惠券,这个优惠券肯定不能发给已经支付的用户,我们需要发给跟这些已经点击或者已经购买的人比较相似的人,我们通过刚才的用户,对人群做一个受众扩展,再把优惠券发给相应的一些人群。这一个是跟知识图谱比较相关的,就是显示的一个用法,隐式的用法就是用在推荐系统里面的信息库,这里也是一个私家课的案例,比如说我有私家课是想推给演讲和口才相关的一个用户群,这里我们就会通过这两个话题去匹配对这个话题比较感兴趣的用户群出来,但是也不够,我们发现在知识图谱里面辩论跟演讲特别相关或者特别相似,这样我们也可以把这一个私家课推送给对辩论感兴趣的用户群,这样我们就把这个话题投放的人群做了一个扩展。

以上是我今天讲的内容,欢迎大家进一步交流,谢谢!



如何构建多快好省的“知识图谱即服务”?这里有独家的经验分享

 微软亚洲研究院 

编者按:知识图谱作为一种特殊的图数据,不仅人类可以识别且对机器友好。信息检索、问答系统、推荐系统、电子商务、金融风控,这些生活中常见的应用场景都离不开知识图谱的支持。如何构建一个“多快好省”的知识服务系统?微软亚洲研究院机器学习组的研究员们基于自己的经验,给出了他们的建议。

近年来,随着人工智能技术在科研和实践中的广泛发展和应用,知识图谱作为人工智能的重要课题也得到迅速发展。包含上亿条事实的公开知识图谱已经非常常见,并且不同的数据源又互相联结相通,形成了数以百亿计的超大规模知识图谱。与此同时,随着自然语言处理、深度学习等技术的发展,知识图谱的抽取技术也在不断进步,增量的知识图谱数据不断汇入。

一方面,知识的普遍性和关联性等特点决定了知识图谱只有在到达一定的数量级和覆盖率时才能真正发挥其能量;另一方面,常用知识表示方法(比如三元组)的灵活性和碎片化等特点,也让知识图谱数据的管理变得困难。在知识图谱数据已经成为一个不断快速生长的庞然大物的背景下,如何让海量知识变得可用且好用已经成为当前知识型应用的紧迫需求。

同一套知识图谱数据可以在不同应用中通用,同时对于用户而言,构建一套全新的数据系统是一项冗余和繁杂的工作。因此,为知识型应用提供在线可用或下载即可用的数据服务成为一种知识图谱的高效应用方式。本文中,我们将这种在线或离线提供知识图谱数据服务的方式称为“知识图谱即服务”

本文将从数据、应用及挑战等角度详细阐述如何高效地管理和服务超大规模知识图谱数据,并分享作者所在团队在设计和实现百亿量级知识图谱实时服务中的一些案例经验。

知识图谱:图视角下的知识

英国哲学家弗朗西斯·培根有句名言:“知识就是力量”。Stuart J.Russell 和 Peter Norvig 在《人工智能:一种现代方法》一书中指出,人工智能包括自然语言处理、知识表示、自动推理、机器学习、计算机视觉以及机器人技术。知识表示对于人工智能的重要性不言而喻。实际上,机器学习得到的模型也是一种用计算结构和数值表示的知识。

在众多知识表示方式中,知识图谱作为一种语义网络拥有极强的表达能力和建模灵活性:首先,知识图谱是一种语义表示,可以对现实世界中的实体、概念、属性以及它们之间的关系进行建模;其次,知识图谱是其衍生技术的数据交换标准,其本身是一种数据建模的“协议”,相关技术涵盖知识抽取、知识集成、知识管理和知识应用等各个环节。

知识图谱是一种特殊的图数据,它是语义的和可复用的:知识图谱数据一经获取即可被多领域应用重复使用,这也是知识图谱服务的构建动机。那么,知识图谱具体来说是什么呢?

首先,知识图谱是一种特殊的图数据。具体来说,知识图谱是一种带标记的有向属性图。知识图谱中每个结点都有若干个属性和属性值,实体与实体之间的边表示的是结点之间的关系,边的指向方向表示了关系的方向,而边上的标记表示了关系的类型。例如,“汤姆·克鲁斯”和“碟中谍”是两个实体,“出演”则是这两者之间的关系。两个实体分别对应着现实世界中的人和电影,而边则对应了他们所表示的人和电影之间的现实关联。前者是关系的起始结点,后者是关系的目标结点。实体“汤姆·克鲁斯”具有“出生日期”等属性,其属性值为“1962年7月3日”等。

其次,知识图谱是一种人类可识别且对机器友好的知识表示。知识图谱采用了人类容易识别的字符串来标识各元素;同时,图数据表示作为一种通用的数据结构,可以很容易地被计算机识别和处理。

再次,知识图谱自带语义,蕴涵逻辑含义和规则。知识图谱中的结点对应现实世界中的实体或者概念,每条边或属性也对应现实中的一条知识。在此之上,我们可以根据人类定义的规则,推导出知识图谱数据中没有明确给出的知识。比如,已知“张三是个人”,我们就可以根据“人都有父母,都有大脑,需要呼吸”等规则得到很多新知识,而无需在知识图谱中逐条给出。再比如,“外公”的“儿子”是“舅舅”,据此可以推导出很多实体之间的亲属等关系。

下面介绍一下广泛使用的知识图谱表示框架和查询语言:资源描述框架 (ResourceDescriptionFramework, RDF) 和 SPARQL 查询语言 (SPARQLProtocolandQueryLanguage, SPARQL) 。

资源描述框架中的基本元素格式为: <主, 谓, 宾> 或 <s, p, o>。它采用主语、谓词和宾语的方式来表示和陈述一条知识,这种表示方式简单且灵活。由于资源描述框架的英文缩写为 RDF,知识图谱数据集也经常被称为RDF数据集,而其管理工具通常被称为RDF Store或Triple Store。在RDF中,我们可以用<Tom_Cruise, Acting, Mission:Impossible>和<Tom_Cruise, Date_Of_Birth, ”July 3, 1962”>等来表示实体“汤姆·克鲁斯”的关系和属性。一个 RDF 数据可以分为两个部分:

一:显式三元组。这部分由数据集直接给定。例如:

<Sky, Color, blue>

<Alice, Friend, Bob>

二:隐含三元组。这部分由推理规则隐含表示。规则可作用于显式三元组,其推导出的三元组数量可能巨大,甚至超过原始数据数倍。例如:

  • 如果?x 是一种?y, 而?y是?z的子类型,那么?x 也是一种?z: (?x, IsA, ?y) & (?y, SubclassOf, ?z) => (?x, IsA, ?z)

  • 如果?y是?x的朋友,那么?x 是?y的朋友: (?x, Friend, ?y) => (?y, Friend, ?x)

代表性的 RDF 数据集包括 Freebase、DBpedia、WikiData、Yago2、Cyc、PubChemRDF以及UniProt等。已有知识图谱数据中的数据量已达到空前规模,例如 Freebase 包含大约19亿的三元组,DBpedia 包含大约30亿三元组,而 Bio2RDF 拥有约100亿三元组。这些数据集因为链接开放数据倡议 (Linked Open Data initiative, LOD) 而互相连通,形成了一个超过1490 亿三元组的超大知识图谱。如果算上它们遵循标准规则集 (如ρdf, RDFSPlus, RDFSFull, OWL DL 等) 可得的隐含三元组,实际的数据量将更为庞大。

SPARQL是一种广泛使用的知识图谱查询语言。它的主要功能是做声明式的子图匹配,即只描述最终需要的结果模式,而具体执行的过程由底层数据管理系统决定。一个 SPARQL 查询的主要组成部分是基本图模式,比如 (?s, p, ?o),三个元素分别对应主、谓、宾,其中需要匹配的元素用带问号的变量表示。通过集合交、并、差等操作符号实现组合逻辑。此外,其它的图查询语言比如 GraphQL 和Cypher 也可以用于查询知识图谱。

知识图谱应用

国内外各大公司、高校以及研究机构都对知识图谱进行了探索和构建,比如谷歌的 Google Knowledge Graph、微软的 Bing Knowledge Graph、搜狗的知立方、 百度知心、阿里巴巴的商品知识图谱、复旦大学的 CN-DBpedia、东南大学的 Zhishi.me、清华大学的 Xlore 以及开放中文知识图谱社区 OpenKG 的 cnSchema.org 等。知识图谱的发展同时也得到了政府的关注和支持,例如中国国务院在《新一代人工智能发展规划》 (国发〔2017〕35号) 一文中就明确提出了知识图谱相关的发展规划。

作为一种应用型技术,知识图谱支撑了很多行业中的具体应用。例如:

信息检索:搜索引擎中对实体信息的精准聚合和匹配、对关键词的理解以及对搜索意图的语义分析等;

自然语言理解:知识图谱中的知识作为理解自然语言中实体和关系的背景信息;

问答系统:匹配问答模式和知识图谱中知识子图之间的映射;

推荐系统:将知识图谱作为一种辅助信息集成到推荐系统中以提供更加精准的推荐选项;

电子商务:构建商品知识图谱来精准地匹配用户的购买意愿和商品候选集合;

金融风控:利用实体之间的关系来分析金融活动的风险以提供在风险触发后的补救措施(如联系人等);

公安刑侦:分析实体和实体之间的关系以获得线索等;

司法辅助:法律条文的结构化表示和查询来辅助案件的判决等;

教育医疗:提供可视化的知识表示,用于药物分析、疾病诊断等;

……

那么知识图谱在这些应用中是如何被访问的呢?知识图谱的服务场景按照其对响应时间的要求可以大体分为在线查询和离线分析两类。

在线查询任务包括:1) 针对实体的查询,如“作者为苏轼的诗”;2) 针对属性的查询,如“辛弃疾的生卒年”;3) 针对关系的查询,通过多跳关系搜索实现知识图谱中的关系发现,如“汤姆·克鲁斯和布拉德·皮特一起演的电影所获奖项”;4) 针对子图结构的查询,用于查询具有某种特定关系的一系列实体,如“参与演出过同一部电影并且具有夫妻关系的演员”;5) 针对查询的聚合,如“世界十大最高峰所在的国家列表”。这类查询的特点是:响应延迟敏感,但数据吞吐量低。

离线分析任务包括:1) 基于图结构的计算,如:知识图谱向量化表示、知识图谱数据补全和实体排序等;2) 基于规则的推理;3) 基于整体信息的统计分析等。这类任务对响应时间要求低,但要求高数据吞吐量。

知识图谱服务的挑战

那么,构建知识图谱服务有什么难点呢?主要包括以下三点:

一:并行图处理。作为一类特殊的图数据,知识图谱的存储、查询以及计算都需要处理和图结构相关的如下三方面挑战:

  • 图数据的复杂性。从数据访问的角度看,无论图数据如何表示,对一个图结点邻居结点的访问都会涉及到在连续存储空间中的“跳转”,即大量的随机数据访问。大量程序优化技术依赖于数据的局部性和重用。大量随机数据访问会导致中央处理器的缓存在大部分时间里失效,进而导致系统性能急剧下降。从程序结构的角度看,图的非结构化特性使得并行处理十分困难。值得一提的是,切分图数据本身是一个 NP 难问题,这让分而治之方案的系统设计变得困难。

  • 图结构和计算的多样性。图数据类型很多,图算法的性能会因为图特征不同而大相径庭。图计算的类型也有很多种,有针对性的系统优化适用面比较受限。

  • 图数据规模越来越大。大规模的图数据让很多经典图算法因为低效而不可用。

二:隐含语义信息处理。例如,处理 (?x, Parent, ?y) => (?x, Father, ?y) UNION (?x, Mother, ?y) 和 (?x, Niece, ?y) => (?x, Niece, ?y) UNION (?x, Spouse, ?z) AND (?z, Niece, ?y) 这类基于规则的推理将放大存储、查询代价。处理方法一般分为两类:一类是在查询之前就将所有隐含的三元组推导出来并作为正常三元组存储,这类方法会大量增加存储代价;另一类是在查询时,按照推理规则将一个查询重写成多个查询,最后汇总查询结果,这类方法会大大增加查询代价。而将两种方法融合的折中方法则会同时放大存储和查询代价。

三:复杂的数据模式。知识图谱的数据模式 (Schema)很复杂,如 ‘A dog can be also an actor’ (DEFINE ‘Actor SubClass Person’?);实体可以多角色,如 ‘A director who is also an actor, a singer, and a writer’;属性可以有多值或缺省,如 ‘An actor with many awards’ 和 ‘A person entity without birthday data’ 等。数据模式的复杂使得知识的物理存储和优化变得十分困难。

结合以上对数据特点、查询特点以及数据模式的分析,我们把一个知识服务系统所面临的挑战总结为以下四点:

- 系统架构:实现数据可扩展;

- 存储设计:处理随机数据访问;

- 数据访问:友好的访问接口;

- 高效查询:低延迟和/或高吞吐数据查询。

这四点汇集起来就是:

知识图谱服务的实现

我们先分析底层数据存储介质。常见的内存 (RAM) 和硬盘 (HDD)的响应速度级别分别为10的负7次方秒和10的负2次方秒,而数据吞吐量分别为3GB/s 左右和100MB/s 左右。传统硬盘由于其机械寻道机制的限制,数据的随机化和并行化读写性能差。为了满足高并行和随机化数据访问的需求,对延迟敏感的知识图谱应用一般都选择内存作为主要的存储介质。另一方面,由于单机内存容量的限制,向上扩展代价昂贵,我们更倾向于可扩展的内存云架构。

从存储架构角度看,单机存储系统主要为两类:一类是基于传统关系数据库构建的系统,如SW-Store、Triple Tables 等;另一类是针对知识图谱数据定制的专用存储查询系统,如 RDF-3X、TripleBit等。分布式系统大致可以分为分布式文件系统、键值存储系统、中心化的存储以及混合存储这四种。

对于上层应用,系统需要提供细粒度的访问接口。原因如下:首先这些接口可以作为在线查询的轻量级工具,同时可以作为离线分析的并行化组件,真正实现将N 转换为1 + 1 + … + 1,其中 N 表示批量的操作,而1表示细粒度的操作。这样我们将这些1并行执行,就可以获得与批量处理相当的高吞吐量效果。反之,如果我们只支持批量处理,当系统响应多个细粒度操作时就会变成 N + N + … + N,从而导致资源的浪费和响应速度的下降。

数据存储和处理模块作为中间层,向下它基于底层存储架构(比如内存云),需要考虑存储代价敏感和随机访问友好两个特点;同时向上它需要提供细粒度且高效的访问接口。

数据存储和处理模块最核心的部分是知识图谱数据的物理表示。它负责实现存储、查询和更新在内的数据管理,需要解决的核心问题是管理一个可更新的超大规模稀疏三阶张量:如果将知识图谱数据的主语、谓词和宾语三个部分分别看作三个维度,每一个维度上的取值范围即知识图谱中对应位置出现的所有值,那么整个数据集就可以被一个稀疏的三阶张量表示,而知识图谱的存储问题也可以转换为对这个三阶张量的压缩和索引。这个三阶张量非常稀疏且分布不均匀,其中主语和宾语这两维的数量大,可以达到十亿量级,而谓词通常在几千到上万的量级。我们需要在存储和查询两个方面同时做到高效,并且支持对各个维度的自由更新。

具体的优化目标包括:首先是能够尽量缩小数据存储文件的大小;其次是能够快速地处理各类数据访问请求;最后是支持增量更新。鉴于物理存储模型的复杂性和灵活性,常见的一类方法是直接将这个三阶张量中的元素(即三元组)作为最小存储单元进行压缩表示并建立索引。这种方法对三个元素按位置进行排列组合进行多次存储,已达到空间换时间的目的。这种方法我们不妨称为零阶展平。另一类方法则将三阶张量按某一阶展平,如主语(图数据结构)或谓词(垂直划分、比特矩阵等)。最后一类同时按两阶来展平,如主语和谓词,这一类我们称为强类型的存储方案。前面提到的常见数据存储方案大多属于弱类型系统,如三元表(简单直接)或“谓词-宾语”键值列表等。相比于弱类型系统,强类型系统具有更小的数据存储和访问代价和更少的联结操作 (JOIN) 代价。

后记

设计一个高效的大规模知识服务系统包含大量琐碎的细节。除了通用的系统优化技巧,如果需要把我们的经验总结为一条,那将是:强类型数据建模(软件)+ 分布式内存存储(硬件)

作者简介

何亮,微软亚洲研究院机器学习组副研究员。他参与开发了微软开源分布式内存图处理引擎 Microsoft Graph Engine, 是开源项目分布式知识图谱服务系统 Stylus 的主要作者。主要研究兴趣包括:知识图谱、分布式图数据系统、机器学习、生物信息学等。

邵斌,微软亚洲研究院机器学习组主管研究员。研究方向包括:分布式内存图计算、计算基因组学和免疫学等。

你也许还想看

●推荐算法不够精准?让知识图谱来解决

●企业大数据挖掘:为员工构建职场知识图谱




工业互联网




产业智能官  AI-CPS


加入知识星球“产业智能研究院”:先进产业OT(工艺+自动化+机器人+新能源+精益)技术和新一代信息IT技术(云计算+大数据+物联网+区块链+人工智能)深度融合,在场景中构建状态感知-实时分析-自主决策-精准执行-学习提升的机器智能认知计算系统实现产业转型升级、DT驱动业务、价值创新创造的产业互联生态链



版权声明产业智能官(ID:AI-CPS推荐的文章,除非确实无法确认,我们都会注明作者和来源,涉权烦请联系协商解决,联系、投稿邮箱:erp_vip@hotmail.com。



登录查看更多
点赞 0

Corrado B\"ohm once observed that if $Y$ is any fixed point combinator (fpc), then $Y(\lambda yx.x(yx))$ is again fpc. He thus discovered the first "fpc generating scheme" -- a generic way to build new fpcs from old. Continuing this idea, define an \emph{fpc generator} to be any sequence of terms $G_1,\dots,G_n$ such that $$Y \text{ is fpc } \Longrightarrow YG_1\cdots G_n \text{ is fpc}$$ In this contribution, we take first steps in studying the structure of (weak) fpc generators. We isolate several classes of such generators, and examine elementary properties like injectivity and constancy. We provide sufficient conditions for existence of fixed points of a given generator $(G_1,..,G_n)$: an fpc $Y$ such that $Y = YG_1\cdots G_n$. We conjecture that weak constancy is a necessary condition for existence of such (higher-order) fixed points. This generalizes Statman's conjecture on the non-existence of ``double fpcs'': fixed points of the generator $(G) = (\lambda yx.x(yx))$ discovered by B\"ohm.

点赞 0
阅读1+
Top