《论文解读-Never-Ending Learning》

 

当前自己仅是简单翻译一下。

0. 论文出处

1. 概要

虽然人们多年来从不同的经验中学习了许多不同类型的知识,但是大多数当前的机器学习系统仅仅从一个数据集中获得一个函数或数据模型。

我们为机器学习提出了一个永不停歇的学习范式,以更好地反映由人类执行的更有雄心和更广泛的学习类型。

作为一个案例研究,我们描述了永不停息的语言学习者(NELL),它实现了永不停息的学习者所期望的一些特性,我们讨论了所学到的教训。

NELL从2010年1月开始每天24小时学习网络阅读,到目前为止,它已经掌握了8000多万个信心加权信念(例如,随茶、饼干)的知识库。

NELL还学会了数百万的特性和参数,使它能够从网上阅读这些信念。

此外,它还学会了对这些信念进行推理以推断出新的信念,并能够通过综合新的关系谓词来扩展其本体。

可以通过 http://rtw.ml.cmu.edu 在线跟踪NELL,也可以通过@CMUNELL在Twitter上跟踪它。

2. 引言

机器学习是人工智能的一个非常成功的分支,机器学习软件现在被广泛应用于从垃圾邮件过滤、语音识别、信用卡欺诈检测到人脸识别的任务中。

尽管取得了这样的成功,但与人类学习相比,今天计算机学习的方式仍然出奇地狭隘。

本文探索了一种新的机器学习范式,它更紧密地模拟了人类学习的多样性、能力和累积性。我们称这种替代范式为无止境的学习(never-ending learning)。

为了说明这一点,请注意,在上面的每个示例中,计算机只学习单个函数来独立执行单个任务,通常是从该函数的输入和输出的人工标记的训练示例中学习。例如,在垃圾邮件过滤中,训练示例包括特定的电子邮件和每个邮件的垃圾邮件或非垃圾邮件标签。

这种学习方式通常被称为监督函数逼近,因为抽象的学习问题是逼近某个未知函数f : X → Y(例如,垃圾邮件过滤器),给定该函数的输入/输出对{}。

其他的机器学习范例也存在(例如,无监督聚类、主题建模),但是这些范例通常也只从单个数据集获取单个函数或数据模型。

与这些在短时间内从组织良好的数据集中学习单个函数的范例不同,人类学习许多不同的函数(例如,多年来积累了丰富的经验,使用广泛的背景知识从早期的经验中学习来指导后续的学习。

这篇论文的主题是,我们永远不会真正理解机器或人类的学习,除非我们可以建立一个计算机程序,向人类那样:

  • 学习许多不同类型的知识或功能
  • 从多年的多样化,大多是自我监督的经验
  • 在一种分阶段的课程模式中,以前学到的知识使我们能够学习更多类型的知识,
  • 自我反省和形成新的表现形式和新的学习任务的能力使学习者避免遇到学习瓶颈并停滞不前。

我们把这种学习模式称为“永无止境的学习”。这篇论文的贡献在于:

  1. 更精确地定义了永无止境的学习范式
  2. 以一个名为“永不停息的语言学习者”(NELL)的计算机程序为例,该程序实现了其中的一些功能,并且在四年多的时间里每天24小时地学习阅读web
  3. 识别来自NELL的长处和短处许多关键的设计特点对任何永无止境的学习系统都很重要

3. 相关工作

4. Never-Ending Learning

非正式地说,我们将一个永不停息的学习主体定义为一个系统,它像人类一样,从多年多样的、主要是自我监督的经验中学习多种类型的知识,使用先前学习的知识来改进随后的学习,并进行充分的自我反思,以避免学习时的表现停滞不前。代理所面临的永无止境的学习问题包括一组学习任务,以及将它们的解决方案耦合在一起的约束。

  1. never-ending learning problem形式化定义

其中:

  • 表示一个never-ending learning problem
  • 表示学习任务的集合,即,其中表示给定的表现性评价任务,表示性能度量,表示特定类型的经验
  • 表示上述学习任务的解决方案之间的耦合约束所组成的集合,即,其中是两个或多个学习任务上的实值函数,表示约束的满足程度,是学习任务上的一个指数向量,指定的参数。
  • 的具体含义是定义要学习的函数即的域和范围上的值所组成的对,即
  • 的具体含义是,即定义了对于第i个学习任务的最优学习函数:,其中表示从所有可能函数的集合。

具体示例:略

  1. Never-Ending Learning的定义

  • 学习许多不同类型的知识;也就是说,包含了许多的学习任务

  • 从多年的多样化,大多是自我监督的经验;也就是说,学习所基于的经验实际上是多种多样的,而且大部分是由系统本身提供的

  • 在一种分阶段的课程模式中,以前学到的知识使我们能够学习更多类型的知识;也就是说,不同的学习任务不需要同时解决-解决一个有助于解决下一个

  • 自我反省和形成新的表现形式和新的学习任务的能力使学习者避免遇到学习瓶颈并停滞不前;也就是说,学习者自身可能会添加新的学习任务和新的耦合约束来帮助解决给定的学习问题

  1. NELL的输入-输出规范

初始输入:

  • 一个定义了类别(例如,体育,运动员)和二元关系(例如,AthletePlaysSport(x,y))的初始本体
  • 每个类别和关系大约有12个标记的训练示例(例如,运动的示例可能包括名词短语棒球和足球)
  • 网络(最初的5亿个网页来自ClueWeb 2009集合(Callan和Hoy 2009),每天访问100,000个谷歌API搜索查询)
  • 偶尔与人交互(例如,通过NELL的公共网站http://rtw.ml.cmu.edu)

NELL每天24小时不间断地做:

  • 阅读(从网上提取)更多的信念,并删除旧的错误信念,以填充一个不断增长的知识库,其中包含每个信念的置信度和出处
  • 学会比前一天读得更好

NELL从2010年1月开始,每天从网络中提取更多的信念,然后重新训练自己以提高自己的能力。到目前为止,结果是一个拥有超过8000万个相互关联的信念的知识库(参见下图),连同数以百万计的已学过的短语、形态特征和网页结构,NELL现在用来从网络中提取信念。NELL现在也正在学习对它所提取的知识进行推理,以推断出它还没有读过的新信念,并且它现在能够对它最初手工提供的本体提出扩展。

  1. NELL的学习任务

NELL将学习超过2500个不同的学习任务,其中每个任务都有其对应的,具体来说NELL将对学习到对应的映射函数:。这些学习任务大致可以分为以下几个大类:

  • 类别分类:根据语义类别对名词短语进行分类的函数(例如,一个用于对给定的名词短语是否与食物相关进行分类的布尔值函数)。NELL在其本体中为280个类别中的每个类别学习不同的布尔函数,允许名词短语指代多个语义类别中的实体(例如,apple既可以指代食品,也可以指代公司)。根据名词短语的五种不同视角(五种不同的Xi),NELL对每个类别学习了多达五种不同的预测Yi的功能,分别是:
    • 名词短语的特征(例如,名词短语是否以字符串“…自治市”结尾)。这是由CML系统(Carlson et al. 2010b)执行的,它通过具有数千个字符串特征的向量表示名词短语。
    • 在2009年ClueWeb2009文本语料库(Callan and Hoy 2009)的5亿个英语网页中,这个名词短语周围的文本上下文分布情况(例如,名词短语N在“N的市长”的上下文中出现的频率)。这是由CPL系统执行的(Carlson et al. 2010b)。
    • 通过主动的网络搜索,在这个名词短语周围发现的文本上下文分布。这是由OpenEval系统(Samadi、Veloso和Blum 2013)执行的,它使用与上述CPL系统稍微不同的上下文特性,并使用实时web搜索来收集这些信息。
    • 包含名词短语的网页的HTML结构(例如,名词短语是否出现在HTML列表中,与其他已知的城市一起)。这是由SEAL系统完成的(Wang和Cohen 2007)。
    • 当名词短语被提供给图像搜索引擎时,与该名词短语相关的视觉图像。这是由NEIL系统(Chen, Shrivastava, and Gupta 2013)执行的,并且只适用于NELL的本体类别的子集(例如,不适用于音乐类型)。
  • 关系分类:根据名词短语对对它们是否满足给定的关系进行分类的函数(例如,将这对名词短语<“Pittsburgh”,”U.S.”>是否满足“CityLocatedInCountry(x,y)”关系进行分类)。NELL在其本体论中为327个关系中的每个关系学习不同的布尔值分类函数。对于每个关系,NELL根据输入名词短语对的不同特征视图学习三个不同的分类函数。具体来说,它使用了两种分类方法:CPL和OpenEval,这两种方法是根据网页上两个名词短语之间的文本上下文分布情况来进行分类;它使用了基于网页HTML结构的SEAL分类方法。
  • 实体解析:根据名词短语对是否为同义词(例如,NYC和Big Apple是否可以指同一个实体)对其进行分类的函数。这种分类方法在(Krishnamurthy和Mitchell 2011)中有描述。对于NELL的280个类别中的每一个,它联合训练两个同义词分类器:一个基于两个名词短语之间的字符串相似性,另一个基于它们提取的信念的相似性。
  • 信念三元组之间的推理规则:将NELL的当前知识库映射到应该添加到其知识库中的新信念的函数。对于NELL’s本体中的每个关系,其对应的功能由PRA系统学习到的限制性Horn子句规则集合表示(Lao, Mitchell, and Cohen 2011;Gardner等,2014)。

上面的每个函数表示一个NELL中的性能任务,每个函数映射到获取该函数的学习任务,给定某种类型的经验和在学习期间要优化的性能度量

在所有情况下,只有一个除外,经验的组成:

  • 人工标注训练的例子(NELL本体中每个实体和关系都有十几个标记示例,以及通过NELL网站贡献了一段时间的标注实例)
  • 一组对应NELL当前的知识库的NELL自标记训练例子
  • 大量未标记的web文本。

唯一的例外是通过视觉图像学习,这是由NEIL系统通过它自己的训练程序来处理的。

  1. NELL的耦合约束

NELL的永无止境的学习任务的第二个组成部分是连接其学习任务的耦合约束集。NELL的耦合约束分为五组:

  • 多视角的协同训练的耦合。NELL的对名词短语进行类别分类(以及对名词短语进行关系分类)的多个方法提供了一个自然的协同训练的机制 (Blum and Mitchell 1998), 其中属于同一类别的可替换的众多分类器应该在给定同一输入的预测结果一致,尽管它们的预测基于不同的名词短语特征。
  • 子集/超集耦合。当一个新的类别被添加到NELL的本体论时,它的直接父类(超集)是明确的(例如,饮料被声明为食物的子集)。当类别C1作为类别C2的一个子集添加时,NELL使用耦合约束。这将学习预测C1的任务和学习预测C2的任务结合起来。
  • 多标签互斥耦合。当类别C被添加到NELL的本体论中时,已知与类别C不相交(相互排斥)的类别也是明确的(例如,饮料被声明为与情感、城市等相互排斥)。这些互斥约束通常继承自更一般的类,但是可以由显式断言覆盖。当类别C1被声明为与C2互斥时,NELL采用约束。
  • 将关系耦合到它们的参数类型。当一个关系被添加到NELL的本体时,编辑者必须指定它的参数的类型(例如,zooInCity(x,y)分别需要Zoo和City类型的参数)。NELL使用这些参数类型声明作为其类别和关系分类器之间的耦合约束。
  • Horn子句耦合。每当NELL学习一个Horn子句规则,从现有的信念中推断出新的知识库信念时,该规则作为一个耦合约束来增强NELL的永不结束学习问题。例如,当NELL学习具有概率p的形式的规则时,该规则作为一个新的概率耦合约束作用于学习关系R1、R2和R3的函数。每个习得的Horn子句都要求从名词短语对映射到R1、R2和R3关系标签的习得函数与此Horn子句一致;因此,它们类似于NELL的子集/超集耦合约束,它要求从名词短语到类别标签的映射函数应该与子集/超集约束一致。NELL’s never ending learning problem包含超过2500个学习任务,相互关联的耦合约束超过100万个。事实上,NELL的永无止境的学习问题是开放的,因为NELL有能力以习得的Horn子句(如上所述)的形式添加新的一致性约束和新的学习任务,为其本体发明新的谓词(如下所述)。

9 NELL的软件体系结构

UTOOLS1580442252858png

NELL的增长知识库(KB)作为一个共享的黑板,通过它的各种阅读和推理模块相互作用。NELL的学习周期使用当前的知识库迭代地重新训练这些软件模块,然后使用这些改进的模块更新知识库。

10 NELL的学习方法和架构

NELL的软件架构,如上图所示,包括一个知识库(KB),它充当一个黑板,通过它NELL的各种学习和推理模块进行通信。如图所示,这些软件模块与前一节中提到的不同类型函数的学习方法(CPL、CML、SEAL、OpenEval、PRA、NEIL)紧密映射,使得NELL的各种学习任务在这些模块之间进行了划分。

NELL的学习是对EM的一种近似

NELL处于一个无限循环中,类似于EM算法的半监督学习,在每次迭代中执行类似于m的步骤。在类似的步骤中,每个读取和推断模块都建议对知识库进行更新(添加和删除特定的信念,以及特定的信任和来源信息)。知识整合器(KI)既记录这些单独的建议,又对知识库中分配给每个潜在信念的置信度做出最终决定。然后,在类似m的步骤中,使用特定于模块的学习算法,使用这个精练的知识库对每个软件模块进行再培训。其结果是一个大规模的耦合培训系统,其中数千个学习任务通过共享知识库和耦合约束由彼此的结果引导。

注意!对于NELL系统而言,一个完整的EM算法是不切实际的。NELL经常考虑数千万个名词短语,在名词短语对中产生了$10^{17}$个潜在的关系断言。在每一个类似E的步骤上估计每一个潜在断言的概率是不切实际的。相反,NELL只构造和考虑它最确信的信念,限制每个软件模块仅为任何给定迭代上的任何给定谓词建议有限数量的新候选信念。这使得NELL能够灵活地操作,同时保留在多次迭代中添加数百万个新信念的能力。

NELL中的知识集成器

知识集成器(KI)集成知识库更新的传入建议。为了提高效率,KI只考虑适度的信心候选信念,并使用一致性约束和信念的完整图的有限子图重新评估信心。例如,KI考虑当前知识库中的所有信念,以确保新的关系断言满足参数类型,但不考虑在相同的迭代中对这些参数类型的信念进行可能的更新。

在多次迭代中,约束的影响通过信念和约束的图更广泛地传播。最近(Pujara et al. 2013)证明了一种更有效的算法来解决KI所面临的联合推理问题;我们现在正在升级NELL的KI来使用这个实现。

在NELL中添加学习任务和本体扩展

NELL有能力通过使用OntExt系统发明新的关系谓词来扩展其本体(Mohamed, Hruschka Jr.和Mitchell 2011)。OntExt考虑了NELL当前本体论中的每一对范畴,以寻找经常讨论的范畴范畴之间关系的证据。

  • 提取提及两个类别的已知实例的句子(例如:对于类别对<药物,疾病>而言,如果百忧解偏头痛已经在在NELL当前的知识库中,那么句子百忧解可能导致偏头痛可能被抽取出来

  • 从提取的句子中,通过上下文共现矩阵建立上下文,然后将相关的上下文聚在一起。每个集群对应于两个输入类别实例之间可能的新关系。

  • 在允许新的关系(例如,DrugHasSideEffect(x,y))被添加到NELL的本体之前,使用一个经过训练的分类器,并进行最后阶段的人工筛选。

  • OntExt为NELL的本体增加了62个新的关系。注意,每个新关系都会衍生出相关的新学习任务,包括三个新任务:学习如何分类哪些名词短语对满足该关系(基于名词短语对的不同观点),以及一个学习Horn子句规则的任务,以从其他关系中推断出该新关系。

11 实证性评估

我们对NELL进行实验评估的主要目标是了解NELL在阅读能力、知识库大小和质量方面随着时间的推移在多大程度上得到了提高。

首先,考虑NELL的KB随时间的增长,从2010年1月开始到2014年11月,NELL已经完成了886次迭代。

UTOOLS1580459487308png

NELL的KB很明显在增长,尽管它的高自信信念比它的全部信念增长得更慢。还要注意,在最近的迭代中,高度自信信念的增长有所减少。

这部分是由于NELL已经在他的本体论中渗透了一些范畴和关系。例如,对于类别Country,它在前几百次迭代中提取了大多数实际的国家名称。

第二,考虑NELL阅读能力的准确性。为了评估这一点,我们应用了NELL在其历史上不同迭代中获得的不同版本,从一组固定的文本数据中提取信念,这些文本数据包括2009年ClueWeb2009语料库中的5亿个英语网页,以及截至2014年11月14日的万维网。

然后我们手动评估这些不同历史版本的NELL所提取的信念的准确性,以NELL内尔的阅读能力的发展。为了获得随时间变化的不同版本的NELL,我们依赖于这样一个事实,即NELL在任何给定时间的状态完全由其KB决定。

特别地,在第i次迭代中,对于给定的NELL的KB,我们首先让NELL在KB加上未标记的文本上训练自己,然后让它将其训练过的方法应用到一组固定的未标记的web文本上,从而提出一组排序排序的信心加权信念。我们评估了这些信念的准确性,以衡量NELL在不同的时间点演变的能力。

12 NELL的可优化之处

  • 向NELL添加一个自我反省功能,使它能够检测在什么地方做得好,在什么地方做得不好,什么时候它已经充分地填充了任何给定的类别或关系,使它能够以一种更有针对性的方式分配其工作

  • 扩展NELL用于提取信念的数据范围,例如通过包括英语、图像数据和Twitter之外的语言

  • 通过更多地依赖于发明新的关系和类别的自动化算法,以及将其他开源本体(如DBpedia)合并到NELL的本体来极大地扩展NELL的本体

  • 将新一代的微型阅读方法(可以对单个句子和文本段落进行深度语义分析的方法)添加到NELL中,因此不需要依赖网络冗余来实现准确阅读。

我们目前正在积极探索这些方向。

13 可以从NELL学到的

NELL是一个学习代理,它演示了一些我们认为对任何永无止境的学习系统都很重要的特性,尽管它也有局限性。根据我们与NELL的经验,我们为任何永无止境的学习系统推荐了四个有用的设计特性:

  • 为了实现成功的半监督学习,需要结合许多不同学习任务的训练:NELL成功地从少量的监督中学习了数千种功能的主要原因是,它被设计成同时学习数千种不同的功能,这些功能被大量的耦合约束紧密地连接在一起。当其中一个学习任务开始取得进展时,耦合约束允许所学习的信息约束其他任务的后续学习。

  • 允许代理学习额外的耦合约束:由于耦合对许多函数的训练至关重要,通过自动学习额外的耦合约束可以获得很大的收益。在NELL中,这是通过数据挖掘NELL的KB来学习限制形式的概率性Horn子句来实现的。NELL已经学会了成千上万个概率性的Horn子句,它用这些子句来推断它还没有读过的新的KB信念。作为创造新的信念的一个副作用,这些新的信念后来被用来重新训练NELL的阅读功能,这些Horn子句也作为耦合约束来进一步约束和指导NELL的阅读功能的后续学习。

  • 学习新的表示方法,它涵盖了初始表示之外的相关现象:为了不断改进,并避免在性能上达到稳定状态,一个永不停止的学习系统可能需要将其表示扩展到最初提供的之外。NELL有一种原始但已经有用的能力来扩展它的表示,方法是在现有类别(例如,river,city)之间提出新的关系谓词(例如,RiverFlowsThroughCity(x,y))。NELL所引入的每一种新关系都会导致新的学习任务,如学习从文本中提取这种关系,以及学习从其他信念中推断这种关系的实例。

  • 将一系列的学习任务组织成一门容易却越来越难的课程:给定一组复杂的学习任务,通常会出现这样的情况:有些学习任务比较容易,有些则为其他任务提供了必要的知识。在NELL中,随着时间的推移,我们通过手动引入新的学习任务类型来改进系统。在NELL的头六个月里,它唯一的任务就是把名词短语分成不同的类别,把名词短语对分成不同的关系。后来,一旦它在这些方面达到了某种程度的能力,并相应地增加了它的知识库,它就可以面对更具挑战性的任务。至此,我们介绍了对知识库进行数据挖掘以发现有用的Horn子句规则的任务,以及基于NELL的类别实例知识发现新的关系谓词的任务。一个关键的开放研究问题是学习主体本身如何形成一个有用的学习任务课程。

NELL的一些限制

  • 自我反省和明确的学习目标。目前,NELL在监督自身表现和进步方面的能力非常薄弱。例如,它没有注意到它在过去一年中没有学到任何有用的国家类别的新成员,它继续研究这个问题,尽管它在这方面的知识已经饱和。此外,它没有尝试将其学习努力分配给那些特别有生产力的任务(例如,收集新的web文本来描述那些它只有低信心信念的实体)。很明显,开发一种自我反省的能力来监控和估计自己的准确性,并根据感知到的需求计划具体的学习行动,将允许系统更有效地使用其计算工作。

  • 普遍的可塑性。虽然NELL能够通过学习改变许多方面的行为,但它的其他部分的行为是固定不变的。例如NELL检测名词短语的方法是一个固定的程序,不开放的学习。在设计不断学习的代理时,重要的是理解如何构建代理,使其尽可能多的行为是可塑的,是可以学习的。否则,代理将面临性能停滞不前的风险,在这种情况下,进一步的改进需要对系统中本身无法修改的部分进行修改。

  • 表示和推理。目前,NELL使用一种简单的基于框架的知识表示,并通过PRA推理系统进行扩展,该推理系统基于受限的Horn子句执行可处理但有限类型的推理。NELL的能力已经受到限制,部分原因是它缺乏更强大的推理组件:目前缺乏表示和推理时间和空间的方法。因此,表征和可处理推理的核心AI问题也是不断学习的代理的核心研究问题。

关于never-ending learning的一些重要的的概念和理论问题

  • 一致性和正确性之间的关系。一个自主学习代理永远无法真正感知它是否正确,它最多只能检测到它的内部一致性。例如,即使它观察到它的预测(例如,内尔斯习得Horn子句预测的新信念)与它所感知的一致(例如,内尔从文本中读到的内容),它也不能区分所观察到的一致性是由于正确的预测,还是不正确的感知。这对于理解永无止境的学习很重要,因为它建议组织学习代理随着时间的推移变得越来越一致,而这正是NELL如何使用其一致性约束来指导学习。因此,一个关键的开放理论问题是,在什么条件下可以保证一个越来越一致的学习代理同时也是一个越来越正确的代理?(Platanios, Blum, and Mitchell 2014)为这个方向提供了一个步骤,通过提供一种方法,不久将允许NELL根据所观察到的其学习函数之间的一致性率来估计其准确性,但是对于这个基本的理论问题还有很多需要了解的地方。

  • 趋同在理论上和实践中都是必然的。对于永不停息的学习代理而言,第二个基本问题是,什么样的代理体系结构能够充分保证代理原则上能够生成一系列自修改,从而将其从初始状态转换为日益高性能的代理,而不会达到性能瓶颈?注意,这可能需要体系结构支持普遍的可塑性、改变其表示的能力等。这里的一个问题是,架构是否有足够的自修改操作来允许它在原则上对自身产生不断改进的修改。其次,相关的问题是它的学习机制是否会做出这些潜在的改变,在可处理的计算量和训练经验下,在实践中趋同。

致谢

参考