学习笔记: Building, Maintaining, and Using Knowledge Bases: A Report from the Trenches

Citation: Deshpande O, Lamba D S, Tourn M, et al. Building, maintaining, and using knowledge bases: a report from the trenches[C]//Proceedings of the 2013 international conference on management of data. ACM, 2013: 1209-1220.

学习者:金柳颀

知识库是一组概念、实例和关系的集合。本文主要讲解了如何根据维基百科(Wikipedia)构建一个全局实体性知识库、如何维护更新这个知识库、如何运用这个知识库到实际饮用中。最后本文讨论了如何组织一个团队来开发、维护知识库。

现在虽然已经有许许多多的知识库在工业级产品中得到了应用,但是很少有文献在讨论如何构建这种产品级的知识库,更没有文献讨论如何对实际运用的知识库进行维护与管理。这篇文章弥补了这个方面的空白。

下面我将分四个方面具体阐述文章的内容。

一、构建知识库

构建知识库分为以下几步:

1.根据维基百科构建分类树

作者他们维护了一个维基百科的内部镜像,所以可以随时检测到维基百科的内容改动。首先,维基百科由一个个条目(Article)组成,每一个条目会属于一个或者多个分类(Category),每一个分类也可能会从属于一个或多个更高层的分类,很显然,这些条目和分类就组成了一棵树,这就是所谓的分类树。但是这并不是一棵严格意义上的树,因为每个节点可以有多个父节点,而且节点之间是有向有环的,所以这其实是一个有向有环的图。另外一个问题是,维基百科的顶层分类对我们来说太大了,我们不需要,所以我们要自己创建顶层分类,并把对应的下层分类移上来。

作者的团队先根据维基百科将这张图完整构建了出来,然后在图的基础上构建分类树:根据一些算法,计算每个边的权值(算法不赘述),边的权值有很多种,每条边的这些权值组成了一个权值向量,我们根据边的权值向量来比较边的重要性。这个在边上加上了权值向量的图就是我们的分类树。

2.在分类树的基础上构建DAG(有向无环图)

这一步需要解决两个问题:

(1)每个节点有多条到根节点的路径

文章的目的是构建一个模糊的有向无环图,也就是每个条目确实可能有多种分类方式,而且它们都是正确的。所以我们要保留所有的路径,但是我们会计算权值之和最大的路径作为默认路径(最优化路径),也就是这个条目默认的完整分类层次。

(2)这是一个有环图

我们不允许环的出现,不然在寻找分类的时候会出现麻烦。所以我们会深度遍历整个图,在出现环的地方,去掉那些权值最小的边,消除所有的环,这会有一定的信息丢失,但是我们不得不这样处理。

解决了这两个问题,我们就完成了DAG的构建。

3.从维基百科中提取关系

这一步就是在各个节点之间加上关系。众所周知,维基百科其实就是文本数据,而从这种非平凡文本中挖掘实体的关系是非常困难的。好在维基百科提供了一些结构化数据,比如信息框啊,模板啊,等等,我们可以从这些地方找到和某一个条目相关的其它条目。除此以外,我们还可以直接从条目文本内容中找到出现的其它条目(可能在语义上没有关系,但是出错的几率比较小)。这样我们就可以建立起两个条目之间的关系了。关系的命名方式也比较特别,命名为<条目名称,关联条目名称,关系类型>,其中最有趣的是关系类型。信息框和模板是由一个个属性组成的,就直接用相应的属性名就可以了,而从正文中提取的实体就比较麻烦了,他们直接选取章节名作为关系类型(当然会有点问题,不过这也确实是一个解决方案)。

这些关系也有强弱,比如从信息框提取的关系强于从模板提取的关系,而模板强于正文。另外,如果有双向关系,且关系类型相同,这个关系就更强。

4.添加元数据

条目还有很多类型的元数据,不同的元数据处理方法也不同。

(1)同义词、同音异意词(比如人名):

对于这些元数据,我们只要在图中添加额外的节点就可以解决问题

(2)每个节点的元数据

包括网页URL、Twitter ID、网络特征、社会特征等等,这些直接作为属性添加在对应的节点上。

5.添加其它的数据源

我们还可以添加其它的数据源来为我们的知识库添加更多的相关知识。难点在于如何将我们的节点和数据源中的数据进行匹配,详细的匹配算法比较复杂,这里就不过多阐述了。

二、维护知识库

1.更新知识库

我们知道,维基百科会不断更新,那么我们的知识库也要随着进行相应的更新。而更新的方式有两种,一是每隔一段时间,将知识库构建程序完全重新运行一遍,优点是简单,缺点是花费时间比较多;第二个方法是选择性地更新差异部分,优点是快,缺点是实现困难。最后作者选择了第一种方法。这种方法的问题就在于耗时长,因此作者的团队使用了很多方法来提高程序的速度,比如使用多线程并行运算等,在一台256G内存,32核,单核主频0.8GHz处理器的机器上,每次运行要花12.5个小时,速度还是比较可观的,之后还考虑利用MapReduce进行多机器并行处理。

2.人工修改知识库

但是大家都知道,这个知识库是一个模糊而非精确的知识库,其中肯定存在一些错误,所以为了保证知识库的质量,作者团队还聘请了数据分析师来帮助分析、评估、人工修改维护数据。

他们聘请了一个数据分析师,每周来随机抽查一些节点的默认路径,节点和节点的关系等等,并人工对这些数据进行调整。

但是我们知道,这个知识库每天都会更新一遍,这样就会产生一个问题:数据分析师手动修改的数据怎么保存下来呢?

他们的解决方案是:为数据分析师设计了一系列的命令,数据分析师需要使用这些命令来修改数据。他可以使用命令来添加删除节点或者边,可以改变边的权重,可以改变关系等等。数据分析师需要将这些命令保存在一个脚本里,而生成知识库的程序会在特定阶段自动运行这个脚本,这样数据分析师的人工改动就被巧妙地保留下来了。

另外,分析师的命令可能会产生冲突,系统也会自动检测到这些冲突并向分析师发送警告,分析师需要手动解决掉这些冲突。

通过这些方法,自动构建和手动更新就比较好地结合在了一起。

三、使用知识库

这个知识库也被运用到了很多的实际领域当中,比如在Kosmix中应用来理解用户的查询,进行深度网络搜索,在Twitter中用于社会媒体的事件监测,在沃尔玛中用于商品搜索和推荐,在Facebook中用于朋友礼物推荐,另外还有社会挖掘等等。

这个知识库的构建和维护使用了C++程序语言与Boost核心库,使用Boost的邻接链表用于进行内存缓存(大概占用了25G),使用Cassandra存储预计算的数据。

最后作者也说明了,这个知识库只是构建其它程序的基础,因为这个知识库是模糊非精确的,而实际的应用程序需要将这些知识根据实际情况精确化,因此,基于这个知识库来构建实际的应用程序还是要花费很多精力的。

四、团队组织与得到的经验

Kosmix的开发团队由25-30个开发者组成。除此以外还有一个4人的核心团队负责管理知识库,一个数据分析师手动评估修改数据,一个开发者开发新的功能,一个人花费50%的时间来维护数据源和维基百科的镜像,还有一个UI专家花费50%的时间进行工具的观感设计。最后有一个团队来负责管理和协调工作。

开发不同的知识库需要不同规模的团队,但是上面的团队组织有很大的借鉴意义。

最后,作者总结了一些重要经验:

  • 普通的硬件和团队就可以开发出这么一个知识库
  • 人工的修改和维护很重要
  • 一个不完美的知识库对现实世界的应用程序非常有用
  • 一个不完美的关系图对现实世界的应用程序非常有用
  • 构建一个实体知识库是很重要的
  • 上下文分析对于处理社区媒体至关重要
  • 一个清晰的,经过证明的方法论对于构建和维护知识库非常重要
anyShare分享到:
This entry was posted in 学习笔记, 研究探索 and tagged , , . Bookmark the permalink.

发表评论