精华内容
下载资源
问答
  • 存在与任意的关系总结
    千次阅读 多人点赞
    2020-07-31 11:08:14

    写在前面:大家好K。首先为你点进这篇有趣的文章点赞👍!文章在撰写过程中难免有疏漏和错误,欢迎你在下方留言指出文章的不足之处;如果觉得这篇文章对你有用,也欢迎你点赞和留下你的评论。更多内容请点进👉我的博客K。👈阅览。

    本文亮点:本文尽量使用通俗易懂的语言,避免教材式语言描述。本文较长,请耐心阅读。

    摘要:数据库是一门对数据进行有效管理的技术,它研究信息资源如何被安全地储存和如何被高效地利用,它是现代计算机科学的一个重要分支。其中关系数据库是目前被应用最广泛的数据库类型,它看起来类似于一张二维表,通过应用数学的方法来处理数据库中的数据。在关系数据库的设计过程中,最重要的莫过于对数据库的逻辑设计,即针对一个具体的问题,我们应该如何去构造一个适合它的数据库模式。经过科学家的讨论研究,最终形成我们今天所看到的关系数据库的规范化理论。本文通过例举具体事例来探讨关系规范化理论在数据库逻辑设计中的形成和方法。
    关键词:数据库;关系规范化理论;范式;函数依赖;属性

    1 关系规范化理论的几个相关概念

    1.1 数据依赖

    数据库的一张表中,数据之间存在着某种相互关系,也就是数据依赖,是各属性之间的相互约束的关系。把真实世界某一实体的属性的语义抽象出来,换句话说就是对某事物现实属性含义的数字化。研究者到目前为止已经提出了各种类型的许多种的数据依赖,函数依赖(Functional Dependency,FD)和多值依赖(Multi-Valued Dependency,MVD)是其中需要我们重点了解和学习的。

    1.1.1 函数依赖

    假设当前有个关系R(U),如有以下学生关系,属性有学生姓名、学号、学生年龄、科目和科目成绩,即用关系模型符号语言描述为Students(Sname, Sno, Sage, Subject, Grade),再假设属性集合有这两个子集,如X=Sno、Y=Sage。函数依赖是指,两个元组的Sno相同,则Sage一定相同,此时称Sno函数确定Sage或Sage函数依赖于Sno。
    只能根据对真实世界的某一具体关系的描述(语义)来确定一个函数依赖。例如如果说Sname函数确定Sage(两个相同的学生姓名,各自对应的年龄也一定相同),那么就一定要事先说明,在这个关系中,不能存在同名同姓的两同学,否则就会出现两个相同的学生姓名,各自对应的年龄不同的情况,这就不是Sname函数确定Sage。
    同理,此例中就不能说Subject函数确定Grade,因为通常学生选修相同的课程,最后的成绩是不相同的,即同一Subject对应了多个Grade的值,而前一个例子中Sno学号就只对应了该学生自己的Sage年龄。

    1.1.1.1 非平凡函数依赖

    如果X=(Sno, Sname)、Y=Sage,Sage是函数依赖于(Sno, Sname)这个属性集合的,类似这样Y不包含于X的函数依赖,称之为Y非平凡函数依赖于X。如果没有明确说明,一般是只在非平凡函数依赖的范围中讨论。

    1.1.1.2 平凡函数依赖

    如果X=(Sno, Sname, Sage)、Y=Sage,Sage是函数依赖于(Sno, Sname, Sage)这个属性集合的,可以看到Y是X的一个子集,X包含了Y,类似的函数依赖被称为平凡函数依赖。平凡函数依赖在所有的关系模式中都是一定成立的,它是固有的一种函数依赖,并不生成新的语义。

    1.1.1.3 完全函数依赖

    如果存在同名同姓的情况,且X=(Sname, Sage)、Y=Grade,X的真子集有空集∅、Sname和Sage,它们各自都不能函数确定Grade,显然空集∅不能函数确定科目成绩Grade,学生姓名Sname也不能函数确定科目成绩Grade,因为存在同名同姓的情况,学生年龄Sage也不能函数确定科目成绩Grade。类似于这样的,X的任何一个真子集都不能函数确定Y,那么称这样的函数依赖为Y对X的完全函数依赖。

    1.1.1.4 部分函数依赖

    如果存在同名同姓的情况,且X=(Sname, Sage, Sno, Subject)、Y=Grade,X的真子集有空集∅、Sname、Sage、Sno、(Sname, Sage)、(Sno, Subject)等15个,经过前面的讨论,空集∅、Sname和Sage等14个真子集都不能函数确定Grade,但是X的(Sno, Subject)这个子集可以函数确定Grade,因为根据实际语义来说,一个学生有唯一的一个学号,并且本学期只选修一次这门课程,所以学号Sno和课程Subject确定下来时,成绩Grade也将被确定。类似于这样的,X的存在一个真子集能函数确定Y,那么称这样的函数依赖为Y对X的部分函数依赖。

    1.1.1.5 传递函数依赖

    假设有如下学生-系别信息关系,属性有学号、系别、系主任,记为R(Sno, Sdept, Mname)。在这个关系中Sno函数确定Sdept(反之不是,因为一个系别有很多学生),Sdept函数确定Mname(反之不是,因为一个管理人员可能管理多个系别),可以推导出Sno函数确定Mname,类似关系R(U)中U的子集X、Y、Z存在X函数确定Y,Y不函数确定X,Y函数确定Z,Z不函数确定Y这样得出X函数确定Z的,称之为传递函数依赖。如果去掉“Y不函数确定X”、“Z不函数确定Y”这两个限制,那么可以看到X实际上是一般的直接函数确定Z的,就不能称之为传递函数依赖。

    1.1.2 多值依赖

    表1 多值依赖例题表格

    科目C教练T参考书B
    科目一托尼交通标志讲解
    科目一托尼交通处罚讲解
    科目一托尼科目一练习题
    科目一凯文交通标志讲解
    科目一凯文交通处罚讲解
    科目一凯文科目一练习题
    科目四托尼现场急救讲解
    科目四托尼文明驾驶讲解
    科目四托尼科目四练习题
    科目四露西现场急救讲解
    科目四露西文明驾驶讲解
    科目四露西科目四练习题

    在上面的关系模型DTeaching(C, T, B)中,当需要给一个科目(例科目一)添加一名教练时(例艾伦),这里必须插入三个元组:(科目一, 艾伦, 交通标志讲解)、(科目一, 艾伦, 交通处罚讲解)和(科目一, 艾伦, 科目一练习题)。同样在去掉一个科目(例科目四)的参考书(例现场急救讲解)时,必须要删除两个元组:(科目四, 托尼, 现场急救讲解)和(科目四, 露西, 现场急救讲解)。
    像这样增删改相关数据是非常不方便的,有非常大的数据冗余。对于(T, B)对应一个科目C,而实际上参考书B只与科目C有关,与教练T无关,这说的就是多值依赖。令DTeaching关系中所有属性为U,那么T=U-B-C。这时关系模式DTeaching(U)中多值依赖B→→C成立。即C的值只是取决于B,而与T无关。
    例如对于DTeaching关系,(科目一, 交通标志讲解)对应了有两个教练T{托尼, 凯文}的一个组,这一组的值只是取决于科目C的值。即对(科目一, 科目一练习题)来说,对应的教练T也是{托尼, 凯文}这一组,可以发现,即使参考书B变了,科目C也还是对应{托尼, 凯文}这一组教练,说明与参考书B无关。

    1.2 码

    码是数据库概念模型和关系模式中一个非常重要的概念。

    1.2.1 候选码

    如果能用最少的几个属性可以唯一地确定一个元组,换句话说,几个属性的集合K,能够完全函数确定一个元祖,那么这个属性集合K,就是关系R的候选码。例如在上文学生关系Students(Sname, Sno, Sage, Subject, Grade)中,属性集合{Sno, Subject}可以完全函数确定一个学生,例如通过Sno、Subject可以确定某个学生的信息和他这个科目的成绩,则(Sno, Subject)是候选码。

    1.2.2 超码

    通过候选码的介绍可知,候选码是最少的几个属性,集合K是完全函数确定一个元组的。超码与之不同,超码的属性集合J是部分函数确定一个属性。超码的属性集合元素个数比候选码的多,超码的某些真子集可能是候选码。例如上一个例子,候选码是(Sno, Subject),超码可以是(Sno, Subject, Sage),其中Sage属性对于确定一个元组是不必要的一个属性。

    1.2.3 主属性与非主属性(非码属性)

    候选码可能有很多个,例如学生关系Students(Sname, Sno, Sage, Subject, Grade)中,如果不考虑同名同姓的情况,那么通过候选码(Sno, Subject)、(Sname, Subject)都可以唯一确定一个元组。这时候选码有多个,就需要人为选定一个主码来供数据库操作使用。几个候选码中所有的属性都称为主属性,反之为非主属性或非码属性。

    1.2.4 全码

    在某些特殊情况下,某些关系的候选码的就是整个属性组,这称为全码。全码包含的属性数量是做多的;最简单的码是只有单个属性。假设存在一个课程关系,一个任课老师可能教授不同的科目,一个科目可能由多课老师来教,该关系表示为Course(Subject, Teacher),如果想要唯一确定一个元组,则必须要提供两个属性,所以该Course关系的码是全码。

    1.2.5 外部码(外码)

    如果一个关系模式R的某个属性或属性组K不是它的码,但是K是另外一个关系模式的码,那么K就是关系模式R的外部码。例如上文的学生关系Students(Sname, Sno, Sage, Subject, Grade)的码是(Sno, Subject),单独的属性Sno不能作为Students关系的码,但是Sno可以作为学生信息关系模式SInfo(Sno, Sname, Sage, Sex)的码。

    2 关系数据库的规范化

    关系数据库的形式是一张二维表,关系数据库的关系必须要满足一定的要求,最基本的一定要满足第一范式,满足的范式越高级,则该关系数据库的规范化程度就越高。最早E.F.Codd研究范式理论,并里提出了第一范式、第二范式、第三范式,后来他和Boyce提出来更高级的BC范式,随后Fagin提出来第四范式,后面又有一些关系数据库研究人员提出了第五范式。所有范式的级别由高到低是5NF>4NF>BCNF>3NF>2NF>1NF,规范化的过程就是由一个第一级的范式的关系模式,通过模式分解,转化成更高一级范式的关系模式。

    2.1 1NF(第一范式)

    第一范式是关系数据库设计必须要满足的最基本要求,如果没有满足第一范式,那么这个数据库设计就是错误的。第一范式要求关系的每一个分量或称属性必须是不可以再分的。如果把关系型数据库看成一张普通二维表,那么就不能存在一个属性再包含多个子属性。
    例如假设存在一个错误的老师学生的关系,属性有老师姓名、专业和学生姓名,表示为Relationship(Tname, Sdept, Students),如果Students是另一个关系Students(Sname1, Sname2…),这里Students被分为Sname1,Sname2…, 那么就是错误的。所以换句话说,不能使两个关系有嵌套联系。

    2.2 2NF(第二范式)

    2.2.1 定义

    首先某关系R符合第一范式,如果关系R的任何一个候选码能完全函数确定每一个非主属性,那么关系R就符合第二范式。
    假设存在一个集团员工的考核和住处信息关系,每个公司的员工住在一个地方,属性有工号WNum、所在公司WCom、住处WLoc、考核项目Project和考核成绩Grade,表示为W-L-P(WNum, WCom, WLoc, Project, Grade)。
    显然W-L-P关系的候选码是(WNum, Project)。(WNum, Project)能完全函数确定Grade;WCom能函数确定WLoc(因为每个公司的员工住在一个地方);因为Wnum能函数确定WCom,所以(WNum, Project)是部分函数确定WCom;因为Wnum能函数确定WLoc,所以(WNum, Project)是部分函数确定WLoc。可以看到存在两个候选码部分函数确定非主属性,所以关系W-L-P是不符合第二范式的。

    2.2.2 问题提出和解决

    如果某关系不符合第二范式,那么就会产生一些问题。
    插入异常。如果在W-L-P关系中,新插入WNum=123,WCom=AliPay,WLoc=10B303,但是该员工还没设置考核项目,即没有Project,缺少主属性的值,所以就无法插入到该关系中。
    删除异常。如果某员工要删除他的考核项目,但是Project是主属性,一旦删除了,该员工的所有信息都会被删除,这就造成了删除异常。
    修改复杂。如果某员工要转到该集团下的其他公司,那么就要修改该元组的WCom值,那么住处WLoc也需要修改。如果这个员工的考核项目Project有多个,那么WCom和WLoc的值也会被存储多个,转公司时也需要全部修改。这就是数据冗余度大导致数据修改无比复杂。
    显然,我们可以把关系模式W-L-P分解成两个关系模式:WP(WNum, Project, Grade)和WL(WNum, WCom, WLoc)。关系WP的码是(WNum, Project),关系WL的码是WNum,这样各自的码就能完全函数确定各自的非主属性了。

    2.3 3NF(第三范式)

    2.3.1 定义

    上文关系模式WL(WNum, WCom, WLoc)存在传递依赖。WNum能函数确定WCom(反之不能),WCom能函数确定WLoc,所以WNum是传递函数确定WLoc。这不符合第三范式。类似这样的某关系模式R,首先符合第一范式,并且不存在码X,能函数确定任意属性组Y(反之不能),Y能函数确定任意非主属性Z,就符合第三范式。上文中WP是符合第三范式的。

    2.3.2 问题和解决方法

    如果某关系模式不符合第三范式,就会产生类似于不满足第二范式时的问题。以WL关系为例,分解成WC(WNum, WCom)和CL(WCom, WLoc)。这样就不存在传递依赖了,分解结果符合第三范式。

    2.4 BC(Boyce-codd)范式

    BC范式有时被称为扩充的第三范式。符合第三范式的关系有些符合BC范式,有些不符合BC范式。

    2.4.1 定义

    假设一个关系模式R满足第一范式,其中一个属性或属性组X能函数确定一个属性或属性组Y,X不包含Y且X中一定含有码,那么这个关系模式R是符合BC范式的。
    假设存在一个员工、领导和部门的关系WMD(W, M, D),一个领导M只管理一个部门D,一个部门D有多个领导M,一个员工W加入一个部门D,就对应了一个固定的领导M。通过语义可以得出:(W, D)能函数确定M,(W, M)能函数确定D,M能函数确定D。所以该关系的候选码有两个,分别是(W, D)和(W, M)。没有非主属性对码的传递函数依赖或部分函数依赖,该关系是符合第三范式的。但是M能函数确定D,M在这里是决定因素,而M不包含码,所以该关系不符合BC范式。

    2.4.2 问题和解决方法

    关系模式WMB是不符合BC范式的,可以通过把该关系分解成WM(W, M)和MD(M, D),这下它们都满足了BC范式。
    如果某关系模式R不属于BC范式,那么它仍然可能有数据修改复杂的特点。第三范式和BC范式是函数依赖范围内模式分解的最高程度。但是还没有完全解决插入和删除异常。

    2.5 4NF(第四范式)

    第四范式就是对于给定任意关系模式R,R符合第一范式,当任意的属性或属性组X和Y,X→→Y,且X不包含Y、X都含有码,那么这个关系模式R是符合第四范式的。
    例如上文1.1.2节多值依赖的DTeaching关系模式,一个科目如果是有m个教练n本参考书,那么每个科目的元组就一定有m×n个。每个教练被重复存储n次,中参考书被重复存储m次,数据量一多时,数据冗余度非常大,因此即使满足了BC范式,还应该继续规范化使该关系模式达到第四范式。
    如果只考虑函数依赖,BC范式是规范化程度最高的;如果考虑多值依赖,第四范式是规范化程度最高的。还有其他的数据依赖例如连接依赖,会在关系的连接运算中体现出异常问题。满足了第四范式但可能会存在连接依赖,需要用到第五范式来解决,因作者水平有限,这里不再讨论第五范式。

    2.6 小结:关系规范化理论的必要性和重要性

    规范化理论的中心思想是逐渐分步消除数据间依赖中的不妥当部分,使其能够在操作效率上有所提高。模式中的各个关系模式能够变得更纯粹,让一个关系只联系一个概念,使一个具体问题中的概念单一化,来解决更新复杂、删除异常、数据冗余高以及插入异常等问题。2NF、3NF、BCNF、4NF是对于这一认识的逐步深化。数据库设计人员对具体问题设计的规范化的程度直接影响了数据库逻辑设计的成功与否,所以我们研究关系规范化理论对数据库的逻辑设计是非常有必要和重要的。

    3 总结

    关系数据库的规范化理论是数据库逻辑设计的一个强有力的工具,为数据库设计提供了一个理论的指南。 经过了规范化处理的模式通常结构都变得比较简单,数据间的联系也变得更清晰。但是在这里必须要明确的一点是,评价一个数据库设计的是否“得体”,规范化并不是唯一的标准,如果某关系模式在一些应用上不必要地被分解得太高级,极有可能消耗数据库查询的性能,会花太多时间在表的连接操作上。根据具体的问题,数据库的设计者在规范化程度与操作数据库时应有良好的性能之间找到一个恰到好处的平衡点,这时设计质量才是比较高的。而不是单纯地理解为规范化程度越高设计就越好。

    参考文献

    [1] 王珊,萨师煊.数据库系统概论(第5版)[M].高等教育出版社,2014。
    [2] 田进华,杨志强.关系规范化理论在数据库设计中的重要性[J].电脑知识与技术,2009,(24):6616-6617+6624.
    [3] 梅红.浅析规范化理论在数据库设计中的重要作用[J].数字技术与应用,2019,(10):217-218.
    [4] 李志强,苗振青,刘丽萍.关系规范化理论在MIS系统数据库设计中的应用[J].郑州纺织工学院学报,2000,(01):75-78.

    更多相关内容
  • 一、偏序关系、 二、偏序集、 三、可比、 四、严格小于、 五、覆盖、 六、哈斯图、 七、全序关系 ( 线序关系 )、 八、拟序关系、 九、拟序关系相关定理、 十、偏序关系八种特殊元素、 ...十三、链反链示例、



    参考博客 :





    一、偏序关系



    偏序关系 :

    给定非空集合 A A A , A ≠ ∅ A \not= \varnothing A= , R R R 关系是 A A A 集合上的二元关系 , R ⊆ A × A R \subseteq A \times A RA×A ,
    如果 R R R 关系满足以下性质 :

    • 自反 : 关系图中所有顶点 都有环 ;
    • 反对称 : 两个顶点之间 有 0 0 0 个或 1 1 1 个有向边 ;
    • 传递 : 前提 a → b , b → c a \to b , b\to c ab,bc 不成立 默认传递 ; 前提 a → b , b → c a \to b , b\to c ab,bc 成立 必须满足 a → c a \to c ac 存在 ;

    则称 R R R 关系是 A A A 集合上的 偏序关系 ;

    偏序关系表示 : 使用 ≼ \preccurlyeq 符号表示偏序关系 , 读作 “小于等于” ;

    符号化表示 : < x , y > ∈ R ⇔ x R y ⇔ x ≼ y <x,y> \in R \Leftrightarrow xRy \Leftrightarrow x \preccurlyeq y <x,y>RxRyxy , 解读 : < x , y > <x,y> <x,y> 有序对在偏序关系 R R R 中 , 则 x x x y y y 之间有 R R R 关系 , x x x 小于等于 y y y ;


    等价关系 是用于 分类 的 , 偏序关系 是用于 组织 的 , 在每个类的内部 , 赋予一个结构 ;


    参考博客 : 【集合论】序关系 ( 偏序关系 | 偏序集 | 偏序集示例 )





    二、偏序集



    偏序集 :

    ≼ \preccurlyeq 关系 是 A A A 集合上的偏序关系 , 则称 集合 A A A偏序关系 ≼ \preccurlyeq 构成的 有序对 < A , ≼ > <A, \preccurlyeq> <A,> 称为偏序集 ;

    如果集合上有偏序关系 , 那么这个集合就称为偏序集 ;


    参考博客 : 【集合论】序关系 ( 偏序关系 | 偏序集 | 偏序集示例 )





    三、可比



    可比 :

    A A A 集合 , 该集合上存在 偏序关系 ≼ \preccurlyeq 小于等于 ,

    偏序集 是 集合 和 偏序关系 组成的有序对 < A , ≼ > <A, \preccurlyeq> <A,> ,

    x , y x, y x,y A A A 集合中的两个元素 , x , y ∈ A x , y \in A x,yA ,

    要么是 x ≼ y x \preccurlyeq y xy , 要么就是 y ≼ x y \preccurlyeq x yx , 符号化表示是 x ≼ y ∨ y ≼ x x \preccurlyeq y \lor y \preccurlyeq x xyyx , 两种情况必选其一 ,

    则称 x x x y y y 是可比的 ;


    只要 x , y x, y x,y 之间 存在偏序关系 , 不管谁在前 , 谁在后 , 都 统一称 x x x y y y 是可比的 ;


    参考博客 : 【集合论】序关系 ( 偏序集元素之间的关系 | 可比 | 严格小于 | 覆盖 | 哈斯图 )





    四、严格小于



    严格小于 概念需要基于 可比概念


    严格小于 :

    A A A 集合 与 A A A 上偏序关系 ≼ \preccurlyeq , 组成 偏序集 < A , ≼ > <A, \preccurlyeq> <A,> ,

    x , y x, y x,y A A A 集合中的两个元素 , x , y ∈ A x , y \in A x,yA ,

    如果 x , y x , y x,y 是可比的 ( x , y x,y x,y 之间存在偏序关系 ) , 但是 x x x y y y 不相等 , 则称 x x x 严格小于 y y y ;


    符号化表示 : x ≼ y ∧ x ≠ y ⇔ x ≺ y x \preccurlyeq y \land x \not= y \Leftrightarrow x \prec y xyx=yxy


    参考博客 : 【集合论】序关系 ( 偏序集元素之间的关系 | 可比 | 严格小于 | 覆盖 | 哈斯图 )





    五、覆盖



    覆盖 概念需要基于 严格小于概念


    覆盖 :

    A A A 集合 与 A A A 上偏序关系 ≼ \preccurlyeq , 组成 偏序集 < A , ≼ > <A, \preccurlyeq> <A,> ,

    x , y , z x, y , z x,y,z A A A 集合中的元素 , x , y , z ∈ A x , y , z \in A x,y,zA ,

    x x x 严格小于 y y y , x ≺ y x \prec y xy ,

    不存在 z z z , 使 x x x 严格小于 z z z , 并且 z z z 严格小于 y y y ,

    则称 y y y 覆盖 x x x ; ( 注意是 大 覆盖 小 )


    偏序关系中 大 覆盖 小


    符号化表示 : x ≺ y ∧ ¬ ∃ z ( z ∈ A ∧ x ≺ y ≺ z ) x \prec y \land \lnot \exist z( z \in A \land x \prec y \prec z ) xy¬z(zAxyz)


    参考博客 : 【集合论】序关系 ( 偏序集元素之间的关系 | 可比 | 严格小于 | 覆盖 | 哈斯图 )





    六、哈斯图



    A A A 集合 A A A 上偏序关系 ≼ \preccurlyeq , 组成 偏序集 < A , ≼ > <A, \preccurlyeq> <A,> ,

    x , y x, y x,y A A A 集合中的两个元素 , x , y ∈ A x , y \in A x,yA ,


    哈斯图 :

    ① 顶点 : 使用 顶点 表示 A A A 集合中的元素 ;

    ② 无向边 : 当且仅当 y y y 覆盖 x x x , y y y 顶点在 x x x 顶点 上方 , 并且在 x x x 顶点 与 y y y 顶点之间 绘制一条 无向边 ;



    在这里插入图片描述

    上图是 6 6 6 元集 上的偏序关系 ≼ \preccurlyeq

    A A A 元素比 B , C , D B,C,D B,C,D 元素都小

    偏序关系是传递的 , A A A B B B 小 , B B B F F F 小 , 因此 A A A F F F

    最下面的元素 A A A 是最小的 , 所有的元素都比 A A A 大 ( 包括 A A A , 偏序关系是自反的 )

    最上面的元素 F F F 是最大的 , 所有的元素都比 F F F 小 ( 包括 F F F , 偏序关系是自反的 )

    B C D E BCDE BCDE 四个元素互相都不可比



    哈斯图 与 关系图对比 省略的内容 :

    ① 环 : 偏序关系是自反的 , 因此 每个顶点上都有环 , 可以省略掉环

    ② 箭头 : 偏序关系是反对称的 , 因此 两个顶点两两之间肯定没有双向边 , 都是单向边 , 因此可以省略箭头方向

    ③ 默认方向 : 使用上下位置表示箭头的方向 , 箭头默认向上 , 偏序是 小于等于 , 最小的在最小面, 最大的在最上面 ;


    参考博客 :





    七、全序关系 ( 线序关系 )



    A A A 集合与该集合之上的 偏序关系 ≼ \preccurlyeq 组成的有序对是 : < A , ≼ > <A, \preccurlyeq> <A,> 偏序集 ;

    A A A 集合中 任意元素 x , y x, y x,y 都 可比 ;

    则称 ≼ \preccurlyeq 关系是 A A A 集合上的 全序关系, 又称为 线序关系 ;

    < A , ≼ > <A, \preccurlyeq> <A,> 为全序集 ( 线序集 ) ;



    < A , ≼ > <A, \preccurlyeq> <A,> 偏序集 是全序集

    当且仅当

    < A , ≼ > <A, \preccurlyeq> <A,> 偏序集的哈斯图是一条直线


    参考博客 : 【集合论】序关系 ( 全序关系 | 全序集 | 全序关系示例 | 拟序关系 | 拟序关系定理 | 三歧性 | 拟线序关系 | 拟线序集 )





    八、拟序关系



    非空集合 A A A , 二元关系 R R R A A A 集合上的二元关系 ;

    符号化表示 : A ≠ ∅ A \not= \varnothing A= , R ⊆ A × A R \subseteq A \times A RA×A ;

    如果 二元关系 R R R反自反 , 传递 的 ,

    则称 R R R 关系是 A A A 集合上的拟序关系 ,

    使用 ≺ \prec 表示拟序关系 ,

    < A , ≺ > <A , \prec> <A,> 是拟序集 ;


    偏序关系 ≼ \preccurlyeq 是 小于等于 关系 , 拟序关系 ≺ \prec 就是 严格小于 关系 ;


    拟序关系示例 : 大于 , 小于 , 真包含 , 都是拟序关系 ;


    拟序关系 完整的性质是 反自反 , 反对称 , 传递 ,
    之所以概念中没有提 反对称 性质 , 是因为 根据 反自反 , 传递性质 , 可以推导出 反对称 性质 ;

    数学中倾向于使用最小的条件进行定义 , 因此这里将反对称性去掉 ;


    参考博客 : 【集合论】序关系 ( 全序关系 | 全序集 | 全序关系示例 | 拟序关系 | 拟序关系定理 | 三歧性 | 拟线序关系 | 拟线序集 )





    九、拟序关系相关定理



    定理 1 :

    非空集合 A A A , A ≠ ∅ A \not= \varnothing A= ,

    ≼ \preccurlyeq 是非空集合 A A A 上的偏序关系 ,

    ≺ \prec 是非空集合 A A A 上的拟序关系 ;


    ① 偏序关系性质 : ≼ \preccurlyeq 自反 , 反对称 , 传递的

    ② 拟序关系性质 : ≺ \prec 反自反 , 反对称 , 传递的

    ③ 偏序关系 -> 拟序关系 : 偏序关系 减去 恒等关系 就是 拟序关系 , ≼ − I A = ≺ \preccurlyeq - I_A = \prec IA=

    ④ 拟序关系 -> 偏序关系 : 拟序关系 与 恒等关系 的并集就是 偏序关系 , ≺ ∪ I A = ≼ \prec \cup I_A = \preccurlyeq IA= ;





    定理 2 :

    非空集合 A A A , A ≠ ∅ A \not= \varnothing A= ,

    ≺ \prec 是非空集合 A A A 上的拟序关系 ;


    x ≺ y x \prec y xy , x = y x=y x=y , y ≺ x y \prec x yx 中最多有一个成立 ;

    使用反证法 , 任意两个成立都会导致 x ≺ x x \prec x xx ;


    ( x ≺ y ∧ x = y ) ∧ ( y ≺ x ∧ x = y ) ⇒ x = y (x\prec y \land x = y) \land (y \prec x \land x=y) \Rightarrow x = y (xyx=y)(yxx=y)x=y





    定理 3 三歧性 , 拟线序 :

    非空集合 A A A , A ≠ ∅ A \not= \varnothing A= ,

    ≺ \prec 是非空集合 A A A 上的拟序关系 ;


    如果 x ≺ y x \prec y xy , x = y x=y x=y , y ≺ x y \prec x yx 中仅有一个城里 , 那么称 ≺ \prec 拟序关系 具有 三歧性 ;

    有三歧性的 逆序关系 ≺ \prec 称为 A A A 集合上的 拟线序关系 , 又称为拟全序关系 ;

    < A ≺ > <A \prec> <A> 被称为 拟线序集 ;


    参考博客 : 【集合论】序关系 ( 全序关系 | 全序集 | 全序关系示例 | 拟序关系 | 拟序关系定理 | 三歧性 | 拟线序关系 | 拟线序集 )





    十、偏序关系八种特殊元素



    参考博客 : 【集合论】序关系 ( 偏序关系中八种特殊元素 | ① 最大元 | ② 最小元 | ③ 极大元 | ④ 极小元 | ⑤ 上界 | ⑥ 下界 | ⑦ 最小上界 上确界 | ⑧ 最小下界 下确界 )





    十一、链



    < A , ≼ > <A, \preccurlyeq> <A,> 是 偏序集 , B ⊆ A B \subseteq A BA ,

    偏序集中一组元素组成集合 B B B , 如果 B B B 集合中的元素两两都可比 , 则称 B B B 集合是该偏序集 < A , ≼ > <A, \preccurlyeq> <A,> 的链 ;

    符号化表示 : ∀ x ∀ y ( x ∈ B ∧ y ∈ B → x 与 y 可 比 ) \forall x \forall y ( x \in B \land y \in B \to x 与 y 可比 ) xy(xByBxy)


    链的本质是一个集合

    ∣ B ∣ |B| B 是链的长度

    参考博客 :





    十二、反链



    < A , ≼ > <A, \preccurlyeq> <A,> 是 偏序集 , B ⊆ A B \subseteq A BA ,

    偏序集中一组元素组成集合 B B B , 如果 B B B 集合中的元素两两都 不可比 , 则称 B B B 集合是该偏序集 < A , ≼ > <A, \preccurlyeq> <A,> 的 反链 ;

    符号化表示 : ∀ x ∀ y ( x ∈ B ∧ y ∈ B ∧ x ≠ y → x 与 y 不 可 比 ) \forall x \forall y ( x \in B \land y \in B \land x\not= y \to x 与 y 不可比 ) xy(xByBx=yxy)


    反链的本质是一个集合

    ∣ B ∣ |B| B 是反链的长度


    参考博客 :





    十三、链与反链定理



    参考博客 :

    展开全文
  • 近年来,与关系抽取相关的研究势头越来越大,本文讨论了关系抽取的发展过程,并对近年来的关系抽取算法进行了分类。此外,我们还讨论了深度学习、强化学习、主动学习和迁移学习。通过分析监督学习、无监督学习、半...

    信息抽取——命名实体识别

    1 关系抽取介绍

    关系抽取(Relation Extraction)的概念字1988年在MUC大会上提出,是信息抽取的基本任务之一,目的是为了识别出文本实体中的目标关系。

    知识图是语义关联的实体,它将人们对物理世界的认知转化为计算机能够以结构化的方式理解的语义信息。关系抽取通过识别实体之间的关系来提取实体之间的语义关系。在现实世界中,关系的提取要比实体提取复杂得多,自然句子的形式也多种多样,所以关系的提取比实体提取困难得多。

    在这里插入图片描述

    关系抽取主要分为两个任务:

    • 关系分类
      • 基于预先给定的关系,对实体对进行分类匹配。
        Example 1:“Bill Gates works at Microsoft Inc.”
        Person-affiliation (Bill Gates,Microsoft Inc)
    • 开放关系抽取
      • 直接从文本中抽取结构化文本关系
      • 对文本关系映射到知识库的规范关系
        Example 2:Hudson was born in hampstead ,which is a suburb of London.
        (Husdon, w a s b o r n i n \color{red} was\quad born\quad in wasbornin , Hampstead)
        (Hampstead, i s a s u b u r d o f \color{red}is \quad a \quad suburd \quad of isasuburdof, London)

    关系抽取的发展主要也分为三个阶段:基于规则、传统机器学习和基于深度学习。其中机器学习又包括监督学习,无监督学习,半监督学习。深度学习主要是监督学习和远程监督学习。下面分别介绍这三种框架的经典算法。

    2 基于规则的关系抽取算法

    通过手写规则来匹配文本,实现关系的提取。主要是分为两种。

    2.1 基于触发词 (基于模式)

    假设X和Y表示公司类型,可使用如下模板表示收购(ACQUISITION)关系。当满足下述模板,则表示两个实体指称在这个句子中具有收购(ACQUISITION)关系。

    规则内容
    规则1X is acquired by Y
    规则2X is purchased by Y
    规则3X is bought by Y

    当匹配出以上模式时候,就可以根据规则提取出实体之间的关系(X,Acquisition,Y)

    2.2 基于依存关系(语法树)

    以动词为起点构建规则,对节点上的词性和边上的依存关系进行限定。
    在这里插入图片描述
    在这里插入图片描述

    2.3 基于规则的RE优缺点

    • 优点:
      • 人工规则有高准确度
      • 可以针对特定的垂直领域
      • 在小规模数据集哈桑容易实现
    • 缺点
      • 低召回率
      • 特定领域需要专家构建,费时费力
      • 难以维护
      • 每条关系都需要人工构建
      • 鲁棒性差

    3 基于机器学习的RE方法

    根据数据是否标注,可以分为监督学习(Supervised Study)、半监督学习(Semi-Supervised Study)和无监督学习(Unsupervised Study)。

    3.1 监督学习

    监督学习从训练数据中研究模型,并预测测试数据的关系类型。输入时自然语句,输出时预定义的关系集合。由于在RE任务中的向量都是来自非结构化的数据,所以需要对文本不同层次的语言进行形式化,对于文本的处理方法主要是两类:特征向量法(Feture Vectors/Eigenvector )和核函数法。

    3.1.1基于特征向量

    主要是从上下文信息,词性,句法中提取出一系列的特征向量,然后通过分类算法,如:

    • Naive Bayes
    • SVM
    • ME最大熵模型

    所谓的特征向量也就是一个实例的向量表示x, x i x^i xi就是N维特征向量的第i个元素。

    3.1.2 基于核函数

    通过核函数计算两个实体之间的相似度,来训练分类模型。核心在于如何设计核函数。
    在这里插入图片描述
    监督学习方法的准确率和标注数据的质量、数量成正比,且不能拓展新的关系,受限于训练语料库,也不适合在开放领域进行关系抽取,因此学术界开始转向半监督和无监督的学习方法。

    3.3 半监督学习—Booststrap和Snowball

    半监督学习又称弱监督学习,利用模型的假设,对少量的数据进行标注(freebase),在不足的条件下提高模型在标记样本中的泛化能力,未标记的数据为Corpus text。

    在论述Snowball之前,先看Boost strap,他是介于监督学习和半监督学习的算法。

    1 Boost strap

    根据已知的标记数据seed库,生成规则。在利用该规则在text中进行遍历,生成新的规则,新规则入库,作为标记的数据进行重新遍历。缺陷就是如果生成的一个规则不准确,这个错误的规则会在库中逐渐增大,导致正确率逐渐降低。

    在这里插入图片描述
    接下来Snowball基于这个缺陷,进行了改进。

    2 Snowball

    关 于 该 算 法 的 介 绍 看 我 这 篇 博 客 \color{red}关于该算法的介绍看我这篇博客 关系抽取——Snowball
    关于该算法的介绍看我这篇博客 关系抽取——Snowball
    关于该算法的介绍看我这篇博客 关系抽取——Snowball


    snowball在2000年被提出,提供了一种从文本文档生成模式和提取元组的新技术,此外,snowball还介绍了一种策略,用于评估在提取过程的每次迭代中生成的模式和元组的质量,只有那些被认为“足够可靠”的元组和模式才会被雪球保留,用于系统的后续迭代。

    在这里插入图片描述
    算法主要四个步骤

    Step1:生成模式

    定义规则:五元组构成 ( L , 实 体 1 , M , 实 体 2 , R ) \color{red}(L,实体1,M,实体2,R) L1M2R,其中,LMR是向量。
    给定文本按照: L + 实 体 1 + M + 实 体 2 + R \color{red}L+实体1+M+实体2+R L+1+M+2+R 的模板生成规则。
    在这里插入图片描述

    Step2:生成tuple

    在这里插入图片描述

    然后,每个候选tuple都有许多帮助生成它的模式,每个模式都有相应的匹配程度。snowball使用这些信息以及关于模式选择性的信息来决定将哪些候选元组实际添加到它正在构建的表中。

    Step3 :评估模式和tuple

    通过计算模式的置信度来决定该模式是否被选择,反之错误的模式产生更多错误的元组。同样的,错误的元组也可能生成无关的模式,通过不断迭代产生更多错误的tuple,(as the name(Snowball) implies).如果一个元组是由多个高得分的模式所产生的,它的置信度就会高。

    3.4 无监督学习—聚类

    监督和半监督学习都需要提前确定关系的类型,事实上,在大规模语料库中,人们往往无法预测所有类型的实体关系。一些研究者试图通过基于聚类思想来解决这一问题。

    无监督关系提取是由Hasegawa等人在2004年的ACL会议上首次提出的,随后的大多数方法都是在Hasegawa的基础上改进的。结果表明,聚类方法在关系提取中是非常可行的。

    首先,他们通过爬虫获取新闻文本,然后根据文章的来源开始分类。然后,根据句子的语义结构,提取出满足一系列约束条件的基本模式聚类实体,将这些实体按照基本模型进行映射,形成次级聚类,使每个次级聚类包含的实体之间的关系相同。

    无监督方法通常需要大规模的语料库作为支持。利用语料库的冗余度,挖掘可能的关系模式集,确定关系名称。该方法的不足之处在于关联名称难以准确描述,低频关联的召回率低

    4 基于深度学习的RE方法

    参考:鄂海红,张文静,肖思琪,程瑞,胡莺夕,周筱松,牛佩晴.深度学习实体关系抽取研究综述[J].软件学报,2019,30(06):1793-1818.

    基于深度学习的关系抽取,主要是有监督学习和远程监督学习。其中有监督学习主要有pipeline和Joint。

    • 流 水 线 \color{red}流水线 线NER串联RE,在实体识别完成的基础上直接进行实体之间关系的抽取;
    • 联 合 学 习 \color{red}联合学习 :基于神经网络端到端模型,同时完成实体的识别和实体间关系的抽取。
    • 远 程 监 督 方 法 \color{red}远程监督方法 :缺少人工标注数据集,比有监督多一步远程对齐知识库给无标签数据打标的过程。而构建关系抽取模型模型的部分,与有监督领域的流水线方法差别不大。

    基于DL的RE任务框架如下:

    1. 获取有标签数据:有监督方法通过人工标记获取有标签数据集,远程监督方法通过自动对齐远程知识库获取有标签数据集;
    2. 构建词向量表示:将有标签句子分词,将每个词语编码成计算机可以接受的词向量,并求出每个词语与句子中实体对的相对位置,作为这个词语的位置向量,将词向量与位置向量组合作为这个词语的最终向量表示;
    3. 进行特征提取:将句子中每一个词语的向量表示输入神经网络中,利用神经网络模型提取句子特征,进而训练一个特征提取器;
    4. 关系分类:测试时根据预先定义好的关系种类,将特征提取出的向量放入非线性层进行分类,提取最终的实体对关系;
    5. 评估分类性能:最后,对关系分类结果进行评估;

    在这里插入图片描述
    监督实体关系抽取框架演化流程
    在这里插入图片描述

    4.1 监督学习—流水线(Pipeline)

    As the name implies,流水线就是将NER和RE两个任务串联起来进行,在NER的基础上进行RE。首先,针对已经标注好目标实体对的句子进行关系抽取,最后把存在实体关系的三元组作为预测结果输出。主要是基于 RNN,CNN,LSTM 及其改进模型的网络结构。

    1 基于RNN的关系抽取

    RNN 在处理单元之间既有内部的反馈连接又有前馈连接,可以利用其内部的记忆来处理任意时序的序列信息,具有学习任意长度的各种短语和句子的组合向量表示的能力,已成功应用在多种 NLP 任务中。

    基于 RNN 模型进行关系抽取的方法由 Socher 等人[46]于 2012 年首次提出,此方法为分析树中的每个节点分配一个向量和一个矩阵,其中,向量捕获组成部分的固有含义,而矩阵捕捉它如何改变相邻单词或短语的含义.这种矩阵向量 RNN 可以在命题逻辑和自然语言中学习操作符的含义,解决了单词向量空间模型(singleword vector space models)无法捕捉到长短语的构成意义,阻碍了它们更深入地理解语言的问题。

    RNN 相比于前馈网络更适合处理序列化输入,但 RNN 也存在着以下两个缺点:

    • (1) 在网络训练时,RNN 容易出现梯度消失、梯度爆炸的问题,因此,传统 RNN 在实际中很难处理长期依赖,这一点在 LSTM 网络中有所改进;
    • (2) 由于 RNN 的内部结构复杂,网络训练周期较长,而 CNN 结构相对简单,主要包括前置的卷积层和后置的全连接层,训练更快速.

    2 基于CNN的关系抽取

    CNN 的基本结构包括两层:其一为特征提取层,每个神经元的输入与前一层的局部接受域相连,并提取该局部的特征;其二是特征映射层,网络的每个计算层由多个特征映射组成,每个特征映射是一个平面,平面上所有神经元的权值相等,减少了网络中自由参数的个数.由于同一特征映射面上的神经元权值相同,所以 CNN 网络可以并行学习.

    Zeng 等人在 2014 年首次提出了使用 CNN 进行关系抽取,利用卷积深度神经网络(CDNN)来提取词汇和句子层次的特征,将所有的单词标记作为输入,而无需复杂的预处理,解决了从预处理系统中提取的特征可能会导致错误传播并阻碍系统性能的问题.图 3 描述了该论文用于关系分类的神经网络的体系结构.网络对输入句子提取多个级别的特征向量,它主要包括以下 3 个组件:词向量表示、特征提取和输出.图 3 右部分显示了句子级特征向量构建过程:每个词语向量由词特征(WF)和位置特征(PF)共同组成,将词语向量放入卷积层提取句子级特征.图 3 左上部分为提取词汇级和句子级特征的过程,然后直接连接以形成最终的句子特征向量.最后如图3 左下部分,通过隐藏层和 Softmax 层得到最终的分类结果.

    在这里插入图片描述

    3 基于 LSTM的关系抽取

    由于梯度消失、梯度爆炸的问题,传统的 RNN 在实际中很难处理长期依赖,后面时间的节点对于前面时间的节点感知力下降.而 LSTM 网络通过 3 个门控操作及细胞状态解决了这些问题,能够从语料中学习到长期依赖关系.

    Yan 等人在 2015 年提出了基于 LSTM 的融合句法依存分析树的最短路径以及词向量特征、词性特征、WordNet 特征、句法类型特征来进行关系抽取,该论文的模型图如图 4 所示.首先,如图 4 左下部分,利用斯坦福解析器将句子解析为依赖树,并提取最短依赖路径(SDP)作为网络的输入,沿着 SDP,使用 4 种不同类型的信息(称为通道),包括单词、词性标签、语法关系和 WordNet 上位词;在每个通道中(图 4 右部分是每个通道的细节图),词语被映射成向量,捕获输入的基本含义,两个递归神经网络分别沿着 SDP 的左右子路径获取信息,网络中的 LSTM 单元用于有效信息的传播;之后,如图 4 左上部分,最大池化层从每个路径中的 LSTM 节点收集信息,来自不同通道的池化层连接在一起,然后输入到隐藏层;最后,使用 Softmax 输出层用于关系分类。

    在这里插入图片描述

    4 流水线方法存在的问题

    1. 错误传播:实体识别模块的错误会影响到接下来的关系分类性能;
    2. 忽视了两个子任务之间存在的关系:丢失信息,影响抽取效果;
    3. 产生冗余信息:由于对识别出来的实体进行两两配对,然后再进行关系分类,那些没有关系的实体对就会带来多余信息,提升错误率.

    4.2 监督学习—联合学习(Joint)(End2End)

    相比于流水线方法,联合学习方法能够利用实体和关系间紧密的交互信息,同时抽取实体并分类实体对的关系,很好地解决了流水线方法所存在的问题。

    联合学习方法通过实体识别和关系分类联合模型,直接得到存在关系的实体三元组.因在联合学习方法中建模的对象不同,联合学习方法又可以分为参数共享方法和序列标注方法:参数共享方法分别对实体和关系进行建模,而序列标注方法则是直接对实体-关系三元组进行建模.下面分别对这两种方法进行说明。

    针对流水线方法中存在的错误累积传播问题和忽视两个子任务间关系依赖的问题,基于参数共享的实体关系抽取方法被提出.在此方法中,实体识别子任务和关系抽取子任务通过共享联合模型的编码层来进行联合学习,通过共享编码层,在训练时,两个子任务都会通过后向传播算法更新编码层的共享参数,以此来实现两个子任务之间的相互依赖,最终找到全局任务的最佳参数,实现性能更佳的实体关系抽取系统.在联合学习模型中,输入的句子在通过共享的编码层后,在解码层会首先进行实体识别子任务,再利用实体识别的结果,并对存在关系的实体对进行关系分类,最终输出实体-关系三元组.

    1 参数共享

    针对流水线方法中存在的错误累积传播问题和忽视两个子任务间关系依赖的问题,基于参数共享的实体关系抽取方法被提出.在此方法中,实体识别子任务和关系抽取子任务通过共享联合模型的编码层来进行联合学习,通过共享编码层,在训练时,两个子任务都会通过后向传播算法更新编码层的共享参数,以此来实现两个子任务之间的相互依赖,最终找到全局任务的最佳参数,实现性能更佳的实体关系抽取系统。

    在联合学习模型中,输入的句子在通过共享的编码层后,在解码层会首先进行实体识别子任务,再利用实体识别的结果,并对存在关系的实体对进行关系分类,最终输出实体-关系三元组。

    Miwa 等人在 2016 年首次将神经网络的方法用于联合表示实体和关系,其模型图如图 5 所示.在该模型中,实体识别子任务和关系分类子任务共享编码层的 LSTM 单元序列表示(编码层包括 LSTM 单元和隐藏层).该方法将实体识别任务当作序列标注任务,使用双向序列 LSTM 输出具有依赖关系的实体标签;之后,通过在双向序列 LSTM 单元上堆叠双向树结构 LSTM 的方法,使关系分类子任务和实体识别子任务共享编码层的 LSTM单元序列表示,同时,在关系分类子任务中捕获词性标签等依赖特征和实体识别子任务中输出的实体序列,形成依存树,最终根据依存树中目标实体间的最短路径对文本进行关系抽取.但该模型中的关系分类子任务和实体识别子任务仅共享了编码层的双向序列 LSTM 表示,从严格意义上来说不是真正的联合模型.但是该模型的提出,为之后真正意义上联合学习模型的提出奠定了基础,是基于深度学习方法做联合学习模型的启发者。

    在这里插入图片描述

    2 序列标注

    基于参数共享的实体关系抽取方法,改善了传统流水线方法中存在的错误累积传播问题和忽视两个子任务间关系依赖的问题.但因其在训练时还是需要先进行命名实体识别子任务,再根据实体预测信息对实体进行两两匹配,最后进行关系分类子任务,因其在模型实现过程中分开完成了命名实体识别和关系分类这两个子任务,仍然会产生没有关系的实体这种冗余信息.为了解决这个问题,基于新序列标注方法的实体、关系联合抽取方法被提出.

    Zheng 等人在 2017 年提出了基于新的标注策略的实体关系抽取方法,把原来涉及到命名实体识别和关系分类两个子任务的联合学习模型完全变成了一个序列标注问题.在该方法中,共包含 3 种标注信息:

    • (1) 实体中词的位置信息{B,I,E,S,O},分别表示{实体开始,实体内部,实体结束,单个实体,无关词};
    • (2) 实体关系类型信息,需根据实际需要自定义关系类型并编码,如{CF,CP,…};
    • (3) 实体角色信息{1,2},分别表示{实体 1,实体 2}.

    该方法能使用序列标注的方法同时识别出实体和关系,避免了复杂的特征工程,通过一个端到端的神经网络模型直接得到实体-关系三元组,解决了基于参数共享的实体关系抽取方法可能会带来的实体冗余的问题.新序列标注方法的模型图如图 6所示.在该端到端的神经网络模型中,对输入的句子,首先,编码层使用 Bi-LSTM来进行编码;之后,解码层再使用 LSTM 进行解码;最终,输出模型标注好的实体-关系三元组。

    • 在这里插入图片描述

    3 联合学习存在的共性问题

    联合学习方法包括基于参数共享和基于新序列标注的实体关系抽取方法:

    • 前者很好地改善了流水线方法中存在的错误累积传播问题和忽视两个子任务间关系依赖的问题;
    • 而后者不仅解决了这两个问题,还解决了流水线方法中存在的冗余实体的问题.
    • 但这两种方法对于现今有监督领域存在的重叠实体关系识别问题,并未能给出相关的解决方案。

    4 监督学习的关系抽取核心公式

    加粗样式

    4.3 基于远程监督的RE

    Mintz于 2009 年首次提出将远程监督应用到关系抽取任务中,其通过数据自动对齐远程知识库来解决开放域中大量无标签数据自动标注的问题。远程监督标注数据时主要有两个问题:噪声和特征提取误差传播.

    下面按照 PCNN及其扩展模型、LSTM、COTYPE、深度残差网络的顺序来进行远程监督领域实体关系抽取的主流方法介绍.。

    在这里插入图片描述

    1 基于 PCNN 及其扩展模型的实体关系抽取

    • 基于 PCNN 和多示例(MIL)的实体关系抽取
    • 基于 PCNN 和注意力机制(ATT)的实体关系抽取
    • 基于 PCNN、注意力机制和实体表示信息的实体关系抽取

    2 基于 LSTM 的实体关系抽取方法

    He 等人提出一种 SE-LSTM 结合多示例学习的方法来解决远程监督中错误传播、错误积累问题。

    • a) LSTM 网络抽取实体对方向性信息(图 10 左上部分):HE 等人首先将句子的最短依存路径(SDP)分割成两个子路径作为 LSTM 结构的输入,自动地抽取特征,以此来抽取实体对的方向性信息;

    • b) CNN 网络提取句子整体信息(图 10 右部分):尽管 SDP 对关系抽取非常有效,但是这并不能捕捉到句子的全部特征.针对此问题,作者将全部句子放进 CNN 网络,进而抽取句子的全部信息(sentence embedding);

    • c) 特征融合(图 10 左下部分):最后,将 LSTM 隐藏层单元以及 CNN 的非线性单元相融合,通过 Softmax层来标注实体对对应的关系。

    在这里插入图片描述

    3 基于 COTYPE 联合抽取模型的实体关系抽取方法

    还没看论文(参考文献3)

    4 基于深度残差网络的实体关系抽取方法

    还没看论文

    Reference:

    1.《A Review on Entity Relation Extraction》; DOI:10.1109/ICMCCE.2017.14
    2.《A survey of relation extraction of knowledge graphs》;DOI:https://doi.org/10.1007/978-3-030-33982-1
    3. 鄂海红,张文静,肖思琪,程瑞,胡莺夕,周筱松,牛佩晴.深度学习实体关系抽取研究综述[J].软件学报,2019,30(06):1793-1818

    展开全文
  • nlp中的实体关系抽取方法总结

    万次阅读 多人点赞 2020-07-04 21:23:00
    跟随小博主,每天进步一丢丢 来自:知乎 地址:https://zhuanlan.zhihu.com/p/77868938 作者:JayLou 编辑:深度学习自然语言处理公众号 本文已获作者授权,禁止二次转载 本文以QA形式总结了「nlp中的实体关系联合...

    点击上方,选择星标置顶,每天给你送干货

    阅读大概需要35分钟

    跟随小博主,每天进步一丢丢

    来自:知乎

    地址:https://zhuanlan.zhihu.com/p/77868938

    作者:JayLou

    编辑:深度学习自然语言处理公众号

    本文已获作者授权,禁止二次转载

    本文以QA形式总结了「nlp中的实体关系联合抽取方法」。

    为了更好的阅读体验,建议使用PC端浏览。如需下载本篇文档,可以到我的github下载。

    Question List

    Q1:与联合抽取对比,Pipeline方法有哪些缺点?
    Q2:NER除了LSTM+CRF,还有哪些解码方式?如何解决嵌套实体问题?
    Q3:Pipeline中的关系分类有哪些常用方法?如何应用弱监督和预训练机制?怎么解决高复杂度问题、进行one-pass关系分类?
    Q4:什么是关系重叠问题?
    Q5:联合抽取难点在哪里?联合抽取总体上有哪些方法?各有哪些缺点?
    Q6:介绍基于共享参数的联合抽取方法?
    Q7:介绍基于联合解码的联合抽取方法?
    Q8:实体关系抽取的前沿技术和挑战有哪些?如何解决低资源和复杂样本下的实体关系抽取?如何应用图神经网络?
    彩蛋:百度2020关系抽取比赛的baseline可以采取哪些方法?

    实体关系抽取(Entity and Relation Extraction,ERE)是信息抽取的关键任务之一。ERE是级联任务,分为两个子任务:实体抽取和关系抽取,如何更好处理这种类似的级联任务是NLP的一个热点研究方向。

    本文结构

    Q1:与联合抽取对比,Pipeline方法有哪些缺点?

    Pipeline方法指先抽取实体、再抽取关系。相比于传统的Pipeline方法,联合抽取能获得更好的性能。虽然Pipeline方法易于实现,这两个抽取模型的灵活性高,实体模型和关系模型可以使用独立的数据集,并不需要同时标注实体和关系的数据集。但存在以下缺点:

    1. 误差积累:实体抽取的错误会影响下一步关系抽取的性能。

    2. 实体冗余:由于先对抽取的实体进行两两配对,然后再进行关系分类,没有关系的候选实体对所带来的冗余信息,会提升错误率、增加计算复杂度。

    3. 交互缺失:忽略了这两个任务之间的内在联系和依赖关系。

    (基于共享参数的联合抽取方法仍然存在训练和推断时的gap,推断时仍然存在误差积累问题,可以说只是缓解了误差积累问题。)

    Q2:NER除了LSTM+CRF,还有哪些解码方式?如何解决嵌套实体问题?

    虽然NER是一个比较常见的NLP任务,通常采用LSTM+CRF处理一些简单NER任务。NER还存在嵌套实体问题(实体重叠问题),如「《叶圣陶散文选集》」中会出现两个实体「叶圣陶」和「叶圣陶散文选集」分别代表「作者」和「作品」两个实体。而传统做法由于每一个token只能属于一种Tag,无法解决这类问题。笔者尝试通过归纳几种常见并易于理解的 实体抽取解码方式 来回答这个问题。

    1、序列标注:SoftMax和CRF

    本质上是token-level 的多分类问题,通常采用CNNs/RNNs/BERT+CRF处理这类问题。与SoftMax相比,CRF进了标签约束。对这类方法的改进,介绍2篇比较有价值的工作:

    • 针对CRF解码慢的问题,LAN[1]提出了一种逐层改进的基于标签注意力机制的网络,在保证效果的前提下比 CRF 解码速度更快。文中也发现BiLSTM-CRF在复杂类别情况下相比BiLSTM-softmax并没有显著优势。

    • 由于分词边界错误会导致实体抽取错误,基于LatticeLSTM[2]+CRF的方法可引入词汇信息并避免分词错误(词汇边界通常为实体边界,根据大量语料构建词典,若当前字符与之前字符构成词汇,则从这些词汇中提取信息,联合更新记忆状态)。

    但由于这种序列标注采取BILOU标注框架,每一个token只能属于一种,不能解决重叠实体问题,如图所示。

    基于BILOU标注框架,笔者尝试给出了2种改进方法去解决实体重叠问题:

    • 改进方法1:采取token-level 的多label分类,将SoftMax替换为Sigmoid,如图所示。当然这种方式可能会导致label之间依赖关系的缺失,可采取后处理规则进行约束。

    • 改进方法2:依然采用CRF,但设置多个标签层,对于每一个token给出其所有的label,然后将所有标签层合并。显然这可能会增加label数量[3],导致label不平衡问题。基于这种方式,文献[4]也采取先验图的方式去解决重叠实体问题。

    2、Span抽取:指针网络

    指针网络(PoniterNet)最早应用于MRC中,而MRC中通常根据1个question从passage中抽取1个答案片段,转化为2个n元SoftMax分类预测头指针和尾指针。对于NER可能会存在多个实体Span,因此需要转化为n个2元Sigmoid分类预测头指针和尾指针。

    将指针网络应用于NER中,可以采取以下两种方式:

    第一种:MRC-QA+单层指针网络。在ShannonAI的文章中[5],构建query问题指代所要抽取的实体类型,同时也引入了先验语义知识。如图所示,由于构建query问题已经指代了实体类型,所以使用单层指针网络即可;除了使用指针网络预测实体开始位置、结束位置外,还基于开始和结束位置对构成的所有实体Span预测实体概率[6]。此外,这种方法也适合于给定事件类型下的事件主体抽取,可以将事件类型当作query,也可以将单层指针网络替换为CRF。

    第二种:多层label指针网络。由于只使用单层指针网络时,无法抽取多类型的实体,我们可以构建多层指针网络,每一层都对应一个实体类型。

    需要注意的是:

      • 1)MRC-QA会引入query进行实体类型编码,这会导致需要对愿文本重复编码输入,以构造不同的实体类型query,这会提升计算量。

      • 2)笔者在实践中发现,n个2元Sigmoid分类的指针网络,会导致样本Tag空间稀疏,同时收敛速度会较慢,特别是对于实体span长度较长的情况。

    3、片段排列+分类

    上述序列标注和Span抽取的方法都是停留在token-level进行NER,间接去提取span-level的特征。而基于片段排列的方式[7],显示的提取所有可能的片段排列,由于选择的每一个片段都是独立的,因此可以直接提取span-level的特征去解决重叠实体问题。

    对于含T个token的文本,理论上共有  种片段排列。如果文本过长,会产生大量的负样本,在实际中需要限制span长度并合理削减负样本。

    需要注意的是:

    1. 在模型输入层进行片段排列方式,会导致对文本重复编码输入,计算复杂。为了解决这一问题,也可以在模型输出层再进行片段排列,对每一个可能实体span进行分类(这种方式在介绍实体关系联合抽取时会介绍)。

    2. 这种片段排列的方式对于长文本复杂度是较高的。

    4、Seq2Seq:

    ACL2019的一篇paper中采取Seq2Seq方法[3],encoder部分输入的原文tokens,而decoder部分采取hard attention方式one-by-one预测当前token所有可能的tag label,直至输出<eow> (end of word) label,然后转入下一个token再进行解码。

    Q3:Pipeline中的关系分类有哪些常用方法?如何应用弱监督和预训练机制?怎么解决高复杂度问题、进行one-pass关系分类?

    (注:Pipeline方法中,关系抽取通常转化为一个分类问题,笔者这里称之为「关系分类」)

    1、模板匹配:是关系分类中最常见的方法,使用一个模板库对输入文本两个给定实体进行上下文匹配,如果满足模板对应关系,则作为实体对之间的关系。常见的模板匹配方法主要包括:

    • 人工模板:主要用于判断实体间是否存在上下位关系。上下位关系的自然语言表达方式相对有限,采用人工模板就可以很好完成关系分类。但对于自然语言表达形式非常多的关系类型而言,这就需要采取统计模板。

    • 统计模板:无须人工构建,主要基于搜索引擎进行统计模板抽取。具体地,将已知实体对作为查询语句,抓取搜索引擎返回的前n个结果文档并保留包含该实体对的句子集合,寻找包含实体对的最长字串作为统计模板,保留置信度较高的模板用于关系分类。

    基于模板匹配的关系分类构建简单、适用于小规模特定领域,但召回率低、可移植性差,当遇到另一个领域的关系分类需要重新构建模板。

    2、半监督学习

    bootstrapping(自举):利用少量的实例作为初始种子集合,然后在种子集合上学习获得关系抽取的模板,再利用模板抽取更多的实例,加入种子集合中并不断迭代。

      • bootstrapping比较常见的方法有DIPRE和Snowball。和DIPRE相比,Snowball通过对获得的模板pattern进行置信度计算,一定程度上可以保证抽取结果质量。

      • bootstrapping的优点构建成本低,适合大规模的关系任务并且具备发现新关系的能力,但也存在对初始种子较为敏感、存在语义漂移、准确率等问题。

    远程监督:其主要的基本假设是,如果一个实体对满足某个给定关系,那么同时包含该实体对的所有句子(构成一个Bag)都可能在阐述该关系。可以看出,该假设是一个非常强的假设,实际上很多包含该实体对的句子并不代表此种关系,会引入大量噪声。为了缓解这一问题,主要采取「多示例学习」、「强化学习」和「预训练机制」:

    (1)多示例学习:主要基于Bag的特征进行关系分类,主要代表文献包括PCNN[8]、Selective Attention over Instances[9]、Multi-label CNNs[10]、APCNNs[11],其中Bag的表示主要方式和池化方式为:

    以APCNNs为例,采取PCNN模型[8]提取单一句子的特征向量,最后通过attention加权得到Bag级别的特征,关系分类是基于Bag特征进行的,而原始的PCNN模型只选择Bag中使得模型预测得分最高的句子用于模型参数的更新,这会损失很多信息。

    APCNNs

    (2)强化学习:在采用多示例学习策略时,可能会出现整个Bag包含大量噪声的情况。基于强化学习的CNN+RL[12]比句子级别和Bag级别的关系分类模型取得更好效果。

    模型主要由样例选择器和关系分类器构成。样例选择器负责从样例中选择高质量的句子,采取强化学习方式在考虑当前句子的选择状态下选择样例;关系分类器向样例选择器反馈,改进选择策略。

    CNN+RL

    (3)预训练机制:采取“Matching the Blank[13]”方法,首次在预训练过程中引入关系分类目标,但仍然是自监督的,没有引入知识库和额外的人工标注,将实体metion替换为「BLANK」标识符。

    • 该方法认为包含相同实体对的句子对为正样本,而实体对不一样的句子对为负样本。如图,  和构成正样本, 和构成 构负样本。

    • 不同于传统的远程监督,该方法训练中不使用关系标签,采用二元分类器对句子对进行相似度计算。预训练的损失包含2部分:MLM loss 和 二元交叉熵关系损失。

    • 在FewRel数据集上,不进行任何tuning就已经超过了有监督的结果。

    3、监督学习:主要分为基于特征、核函数、深度学习三种方法;基于特征的方法需要定义特征集合,核函数不需要定义特征集合、在高维空间进行计算。笔者主要介绍基于深度学习的方法。

    过去的几年中,很多基于深度学习的有监督关系分类被提出,大致都采用CNN、RNN、依存句法树、BERT的方法,由于这些方法大都很容易理解,笔者这里不再赘述,只选择介绍3篇比较新颖的文献进行介绍。

    3-1 Matching the Blanks: Distributional Similarity for Relation Learning[13]

    这篇文献来自GoogleAI,基于BERT,共采用6种不同结构来进行实体pair的pooling,然后将pooling进行关系分类或关系相似度计算,显示(f)效果最好。

    1. 标准输入+「CLS」输出;

    2. 标准输入+mention pooling输出;

    3. position embedding 输入+mention pooling输出;

    4. entity markers输入+「CLS」输出;

    5. entity markers输入+ mention pooling输出;

    6. entity markers输入+ entity start 输出;

    3-2 Extracting Multiple-Relations in One-Pass with Pre-Trained Transformers[14]

    Pipeline方法下的关系分类,同一个句子会有多个不同的实体对,过去的一些方法构造多个(句子,entity1,entity2)进行多次关系分类,本质上是一个multi pass问题,同一个句子会进行重复编码,耗费计算资源。

    • 本文将多次关系抽取转化为one pass问题,将句子一次输入进行多个关系分类。在BERT顶层对不同的实体对进行不同的关系预测。

    • 本文将还编码词和实体之间的相对距离计算Entity-Aware Self-Attention。如下图所示,  代表实体  到token 间相对距离的embedding。

    Entity-Aware Self-Attention

    3-3 Simultaneously Self-Attending to All Mentions for Full-Abstract Biological Relation Extraction[15]

    与上篇文献[14]类似,这篇文献的依旧采用one-pass对所有实体mention进行关系分类,同时从所有实体mention中定位关系。

    不同的地方是从句子级别拓展到文档级别,同时引入NER辅助进行多任务学习,此外,实体信息在进行mention pooling才给定,而不是输入时就给出 ;进行关系分类时采用Bi-affine方法(sigmoid),而不是采用Softmax。具体地:

    • Bi-affine Pairwise Scores:采用Transformer编码,对每个token通过两个独立MLP进行三元组中的head和tail表征,然后Bi-affine通过计算每个三元组的得分: 

    • 采用LogSumExp计算得分: 

    • 计算loss时,给定E个实体对信息再进行计算: 

    Simultaneously Self-Attending

    Q4:什么是关系重叠&复杂关系问题?

    • a:正常关系问题

    • b:关系重叠问题,一对多。如“张学友演唱过《吻别》《在你身边》”中,存在2种关系:「张学友-歌手-吻别」和「张学友-歌手-在你身边」

    • c:关系重新问题,一对实体存在多种关系。如“周杰伦作曲并演唱《七里香》”中,存在2种关系:「周杰伦-歌手-七里香」和「周杰伦-作曲-七里香」

    • d:复杂关系问题,由实体重叠导致。如《叶圣陶散文选集》中,叶圣陶-作品-叶圣陶散文选集;

    • e:复杂关系问题,关系交叉导致。如“张学友、周杰伦分别演唱过《吻别》《七里香》”,「张学友-歌手-吻别」和「周杰伦-歌手-七里香」

    Q5:联合抽取难点在哪里?联合抽取总体上有哪些方法?各有哪些缺点?

    顾名思义,联合模型就是一个模型,将两个子模型统一建模。根据Q1,联合抽取可以进一步利用两个任务之间的潜在信息,以缓解错误传播的缺点(注意⚠️只是缓解,没有从根本上解决)。

    联合抽取的难点是如何加强实体模型和关系模型之间的交互,比如实体模型和关系模型的输出之间存在着一定的约束,在建模的时候考虑到此类约束将有助于联合模型的性能。

    现有联合抽取模型总体上有两大类[16]

    1、共享参数的联合抽取模型

    通过共享参数(共享输入特征或者内部隐层状态)实现联合,此种方法对子模型没有限制,但是由于使用独立的解码算法,导致实体模型和关系模型之间交互不强。

    绝大数文献还是基于参数共享进行联合抽取的,这类的代表文献有:

    2、联合解码的联合抽取模型

    为了加强实体模型和关系模型的交互,复杂的联合解码算法被提出来,比如整数线性规划等。这种情况下需要对子模型特征的丰富性以及联合解码的精确性之间做权衡[16]

    • 一方面如果设计精确的联合解码算法,往往需要对特征进行限制,例如用条件随机场建模,使用维特比解码算法可以得到全局最优解,但是往往需要限制特征的阶数。

    • 另一方面如果使用近似解码算法,比如集束搜索,在特征方面可以抽取任意阶的特征,但是解码得到的结果是不精确的。

    因此,需要一个算法可以在不影响子模型特征丰富性的条件下加强子模型之间的交互。

    此外,很多方法再进行实体抽取时并没有直接用到关系的信息,然而这种信息是很重要的。需要一个方法可以同时考虑一个句子中所有实体、实体与关系、关系与关系之间的交互。

    Q6:介绍基于共享参数的联合抽取方法?

    在联合抽取中的实体和关系抽取的解码方式与Q2中的实体抽取的解码方式基本一致,主要包括:序列标注CRF/SoftMax、指针网络、分类SoftMax、Seq2Seq等。基于共享参数的联合抽取,实体抽取loss会与关系抽取loss相加。

    由于很多的相关文献实用性不高,我们只介绍其中具备代表性和易于应用的几篇文献,首先归纳如下:

    6-1 依存结构树:End-to-End Relation Extraction using LSTMs on Sequences and Tree Structures[17]

    • 联合抽取顺序:先抽取实体,再进行关系分类

      • 实体抽取:采用BILOU标注,SoftMax解码;

      • 关系抽取:针对实体抽取出的实体对,在当前句子对应的依存句法树中找到能够覆盖该实体对的最小依存句法树,并采用TreeLSTM生成该子树对应的向量表示,最后,根据子树根节点对应的TreeLSTM向量进行SoftMax关系分类。

    • 存在问题:

      • 实体抽取未使用CRF解码,没有解决标签依赖问题。

      • 关系抽取仍然会造成实体冗余,会提升错误率、增加计算复杂度

      • 使用句法依存树,只针对句子级别并且只适用于易于依存解析的语言。

      • 不能解决完整的关系重叠问题,本质上是实体重叠问题没有解决。

    6-2 指针网络,Going out on a limb: Joint Extraction of Entity Mentions and Relations without Dependency Trees[18]

    网络结构图和标注框架
    • 联合抽取顺序:识别实体的同时进行关系抽取,不再采取依存树。

      • 实体抽取:采用BILOU标注,SoftMax解码;解码时利用前一步的label embedding信息。

      • 关系抽取:采取指针网络解码,指针网络实际上有R层(R为关系总数)。对当前实体查询在其位置前的所有实体(向前查询),并计算注意力得分:

    • 存在问题:

      • 只向前查询head实体,会存在对tail实体的遗漏;

      • 在关系指针网络的gold标签中,对于实体span中每一个token平均分配1/N概率,没有充分利用实体边界信息,这会导致注意力分散。

    6-3 Copy机制+seq2seq:Extracting Relational Facts by an End-to-End Neural Model with Copy Mechanism[19]

    • 联合抽取顺序:采用Seq2Seq框架,依次抽取关系、head实体、tail实体。

      • Encoder编码:

      • Decoder编码:

        •  为decoder部分t时刻的输入,,主要有两部分组成:

          •  为attention vector,  为前一步的copy entity 或者 relation embedding;

        • 关系预测:将  直接喂入SoftMax进行;

        • head实体预测(Copy the First Entity):

          • 在当前解码步,从n个token中选择一个作为实体:

          • 为每一个token的编码,加入当前解码的输出;

          • 根据从n个token中选择最大概率的token作为实体;

        • tail实体预测(Copy the Second Entity)

          • 与head实体预测类似,只是需要mask上一步预测的head实体(token)

    • 存在问题:

      • 只考虑token维度的实体,丢失了多个token构成的实体,这是一个明显bug;

    6-4 多头选择机制+sigmoid:Joint entity recognition and relation extraction as a multi-head selection problem[20]

    网络结构

    本篇文献应用较为广泛,与3-3的文献[15]十分类似,只是不再提供实体信息、需要对实体进行预测。

    • 联合抽取顺序:先抽取实体,再利用实体边界信息进行关系抽取。

      • 实体抽取:采用BILOU标注,CRF解码;

      • 关系抽取:采用sigmoid进行多头选择,与文献[15]的做法类似。

        • 对于含n个token的句子,可能构成的关系组合共有  个,其中r为关系总数,即当前token会有多个头的关系组合:

        • 该方法并没有像文献[15]分别构建head和tail实体编码,而是直接通过token的编码表示进入sigmoid layer直接构建「多头选择」。

        • 引入实体识别后的entity label embedding进行关系抽取,训练时采用gold label,推断时采用predict label。

        • 在三元组统一解码时,需要利用实体边界信息组建三元组,因为多头选择机制只能知道token和token之间的关系,但并不知道token隶属的实体类别。

      • 存在问题:

        • entity label embedding在训练和推断时存在gap,文献[21]提出了Soft Label Embedding ,并引入了BERT。

        • 鲁棒泛化问题:原作者在文献[22]引入了对抗训练机制(如今看来,这种对抗训练机制比较简单了)

    6-5 SPO问题+指针网络,Joint Extraction of Entities and Relations Based on a Novel Decomposition Strategy [23]

    • 联合抽取顺序:是一个spo问题,先抽取实体(主体subject,简称s),再抽取关系(关系predicate及其对应的客体object,简称po)。

      • 如上图所示,主体抽取包含「Trump」和「Queens」,然后基于已抽取的主体再进行po抽取。例如对于「Trump」,其对应的关系包含「PO」-「United States」和「BI」-「Queens」;可以看出「Queens」既可以作为subject,也可以是object。

    网络结构图
    • 主体(s)抽取:采用指针网络进行解码。

    • 关系和客体(po)抽取:同样采用指针网络进行解码,但事实上采用的是Q2中提到的多层label指针网络,即每一层是一个关系label对应的指针网络(用来抽取object)。

      • 在对当前的subject抽取对应的po时,采取多种方式加强了对当前subject的实体感知方式,如sentence pooling 、entity pooling、relative position embedding等;在对object的end pos 解码时也引入start pos的编码信息。

    • 存在问题:

      • 在训练时,subject的选择是随机的,并没有将所有subject统一进行po抽取;没有充分利用信息,可能造成信息损失,因此需要延长epoch训练。

    6-6 多轮对话+强化学习 :Entity-Relation Extraction as Multi-Turn Question Answering[24]

    多轮对话设计-实体关系抽取
    • 联合抽取顺序:基于人工设计的QA模板,先提取实体,再抽取关系。

      • 文献指出通常的三元组形式存在问题,并不能充分反应文本背后的结构化信息[25]:如上图的结构化表格,TIME需要依赖Position,Position需要依赖Corp(公司)。进行传统的三元组抽取可能导致依赖关系的间断,因此这种多轮QA方式[25]

        • 能够很好地捕捉层级化的依赖关系。

        • 问题能够编码重要的先验关系信息,对实体/关系抽取有所帮助。

        • 问答框架是一种很自然的方法来同时提取实体和关系。

      • 将联合抽取转为一种对轮问答任务[25]:对每种实体和每种关系都用问答模板进行刻画,从而这些实体和关系可以通过回答这些模板化的问题来进行抽取,采取BIES标注实体,MRC+CRF进行解码(与文献[5]一脉相承,只是不再使用指针网络,而是CRF)。

    • 强化学习:

      • 笔者在前面已经指出,基于共享参数的联合学习仍然不能完全避免在推断时的误差积累,这篇文献采用强化学习机制进行优化。

      • 在多轮QA中[25],Action就是选择一个文本段,Policy就是选择该文本段的概率。对于Reward,使用正确抽取的三元组的数量作为奖励,使用REINFORCE算法寻找最优解。

    • 存在问题:

      • 也许针对三元组形式不能体现文本结构化信息的任务是有一定必要性的,如关系依赖问题。但对于通常的三元组任务,引入question需要对原始文本进行多次编码才能抽取实体和关系,计算复杂度较高。

    6-7 输入端的片段排列: Span-Level Model for Relation Extraction[7]

    • 联合抽取顺序:输入端片段排列抽取实体,然后提取实体对进行关系分类;

      • 将片段排列方式生成的候选实体span,进行实体类型SoftMax分类;对于候选实体span不为None的实体span组成实体pair进行关系SoftMax分类;

      • 笔者在前文介绍实体重叠问题时,已经介绍了这种基于片段排列的方式,基于片段排列的方式[7],显示的提取所有可能的片段排列,由于选择的每一个片段都是独立的,因此可以直接提取span-level的特征去解决重叠实体问题。

    • 存在问题:

      • 在模型输入端进行片段排列,对于含T个token的文本,理论上共有  种片段排列,计算复杂度极高。如果文本过长,会产生大量的负样本,在实际中需要限制span长度并合理削减负样本。

      • 进行关系判断时,也会造成实体冗余,提高错误率。

    6-8 输出端的片段排列:SpERT:Span-based Joint Entity and Relation Extraction with Transformer Pre-training [26]

    SpERT
    • 联合抽取顺序:在输出端进行片段排列进行实体分类,然后进行关系分类。

      • 改进6-7[7]中在输入端进行片段排列的高复杂度问题,在BERT输出端进行片段排列后在进行span分类,过滤实体类型为None的片段然后进行关系分类。

      • 进行关系分类时,融合多种特征组合:包含实体span的pooling,实体span长度,实体pair之间token的pooling;

    • 存在问题:

      • 虽然缓解了片段排列的高复杂度问题,但关系分类仍有实体冗余问题。

    Q7:介绍基于联合解码的联合抽取方法?

    在Q6中的基于共享参数的联合抽取的方法中,并没有显式地刻画两个任务之间的交互,同样训练和推断仍然存在gap。

    为了加强两个子模型之间的交互,一些联合解码算法被提出[16]:文献[27]提出使用整数线性规划(ILP)对实体模型和关系模型的预测结果进行强制约束。文献[28]利用条件随机场(CRF)同时建模实体和关系模型,并通过维特比解码算法得到实体和关系的输出结果。文献 [29]将实体关系抽取看为一个结构化预测问题,采用结构化感知机算法,设计了全局特征,并使用集束搜索进行近似联合解码。文献[30]提出使用全局归一化(Global Normalization)解码算法。文献 [31] 针对实体关系抽取设计了一套转移系统(Transition System),从而实现联合实体关系抽取。由于篇幅限制,对上述文献感兴趣的读者可以详细参考原文。

    下面笔者介绍3种易于应用的统一实体和关系标注框架的联合解码方法。

    7-1 Joint extraction of entities and relations based on a novel tagging scheme[32]

    • 总体标注框架:

      • 统一了实体和关系标注框架,直接以关系标签进行BIOES标注。head实体序号为1,tail实体序号为2;

    • 存在问题:

      • 不能关系重叠问题,比如一个实体存在于多种关系中的情况。这是一个致命的bug。

    7-2 Joint Extraction of Entities and Overlapping Relations Using Position-Attentive Sequence Labeling [33]

    • 总体标注框架:如上图所示,对于含n个token的句子,共有n个不同标注框架。也就是对于每一个位置的token都进行一次标注,无论实体还是关系都采用BIES标注。

      • 当p=5指向第5个token「Trump」时,其对应的实体为「PER」,此时p=5对应的标签实体有「United States」、「Queens」、「New York City 」,分别对应关系「President of」、「 Born in」、「Born in」.

      • 本质上将实体和关系融合为一体,共同采用BIES标注,用CRF解码。

      • 实体关系提取时,对当前指向位置的实体采用position attention 机制进行识别对应的关系实体,该机制融合了 position-aware 和 context-aware 表示:其中  为当前指示的token位置编码,  为上下文编码,  为当前解码位置的编码。

    • 存在问题:对一个句子进行了n次重复编码,复杂度高, 

    7-3 Joint extraction of entities and relations based on a novel tagging scheme[34]

    • 总体标注框架:这个方法来自PaddlePaddle/Research,也是百度2020关系抽取的baseline方法,同样也是统一了实体和关系的SPO标注框架。(SPO问题可参考前文的6-5)

      • 使用方法的是token level 的多label分类,即每一个token对应多个label。

      • 标注框架十分巧妙,如上图示例中形成的2个spo三元组,「王雪纯-配音-晴雯」和「王雪纯-配音-红楼梦」,存在两个关系「配音-人物」和「配音-作品」,多label标签就以关系标签建立:

        • 假设一共存在R个关系,那label一共为(2*R+2个),如果是subject中的第一个token,则标记为「B-S-关系名称」;如果是object中的第一个token,则标记为「B-O-关系名称」;其余的实体token标记为「I」,不隶属于实体的token标记为「O」;

        • 如对于subject王雪纯中,「王」隶属于两个「B-S-配音-作品」和「B-S-配音-人物」;其余的「雪」「纯」用「I」来标注;

        • 如对于object红楼梦中「红」隶属于「B-O-配音-作品」;其余的「楼」「梦」用「I」来标注;

        • 如对于object晴雯中「晴」隶属于「B-O-配音-人物」;其余的「雯」用「I」来标注;

    • 存在问题:

      • 上述标注框架还是无法直接解决一些包含实体重叠的关系抽取?

        • 如:《叶圣陶散文选集》中,叶圣陶-作品-叶圣陶散文选集;

      • 上述标注框架也无法直接解决一个句子中的多重同类关系:

        • 如,‘张学友《吻别》周杰伦《菊花台》梁静茹《吻别》’等,需要加入后处理逻辑。

    总结:上述统一实体和关系标注框架虽然不能完全解决关系重叠等问题,但在特定场景下,引入一些后处理规则进行约束,这种方式简单明了、易于迭代维护。

    Q8:实体关系抽取的前沿技术和挑战有哪些?如何解决低资源和复杂样本下的实体关系抽取?如何应用图神经网络?

    在前文中,笔者叙述了pipeline和联合抽取中的一些实体关系抽取方法,其中面临的挑战,笔者初步总结如下并给出一点建议:

    1、对于pipeline方法中的NER来说:

    虽然很多方法已经很普及,但更需要关注复杂场景下的实体重叠问题;此外,对于NER问题其实应用很广,在很多性能敏感的场景下,使用深度学习的方法似乎不能满足要求,这时就需要我们采取「词典+规则」的方法,例如:

    • 对于医疗场景中的很多实体歧义性并不强,对上下文也不够敏感,这时构建出一个针对目标实体的词表更为有效。

    • 对于通用领域中歧义性的实体,是否可以采用多种分词方式和句法分析等融合的方法去寻找实体边界呢?这都值得我们进一步尝试。

    此外,应用解决NER的方法是否可以解决一些事件段落切割问题,方便我们将复杂任务进行拆解。

    2、对于pipeline方法中的关系分类来说:

    首要问题是怎么降低计算复杂度,关系分类时不再对句子重复编码,而是one-pass。

    在低资源场景下,采取远程监督的方法确实可以自动进行语料构建,但其中针对样本噪音的降噪方法是否还有提升空间?降噪方法能否做到与模型无关,是否可以借鉴图像分类中很有效的置信学习[35]呢?

    此外,预训练语言模型如此火爆,针对关系分类任务,能否在预训练阶段引入更有效的关系分类的目标呢?如前文提到的文献[13]

    3、对于联合抽取任务来说:

    难点是如何加强实体模型和关系模型之间的交互,怎么对需要对子模型特征的丰富性以及联合解码的精确性之间做权衡?

    此外,很多方法再进行实体抽取时并没有直接用到关系的信息,然而这种信息是很重要的。需要一个方法可以同时考虑一个句子中所有实体、实体与关系、关系与关系之间的交互。

    引入图神经网络是否能够解决关系与关系之间的交互呢?由于篇幅原因,本文不再赘述。感兴趣的读者可以参考ACL2019中的系列文献[36][37][38][39]

    4、对于低资源问题和复杂样本问题来说:

    在刘知远老师的《知识图谱从哪里来:实体关系抽取的现状与未来》[40]一文中,详细叙述了这方面的问题:

    • 对于少次关系学习问题:他们提出了FewRel 2.0[41],在原版数据集FewRel的基础上增加了以下两大挑战:领域迁移(domain adaptation)和“以上都不是”检测(none-of-the-above detection)。

    • 对于文档级别的关系抽取问题:提出了DocRED数据集[42],是一个大规模的人工标注的文档级关系抽取数据集,文档级关系抽取任务要求模型具有强大的模式识别、逻辑推理、指代推理和常识推理能力[40]

    此外,如何引入将低资源问题的解决方案引入实体关系抽取中是一个值得探讨的问题,如主动学习、迁移学习(领域自适应、跨语言问题)、元学习、半监督学习等;还有怎么解决不平衡数据下的关系抽取?一些顶会的系列文献[43][44][45][46][47][48]也做了一些尝试,感兴趣的读者可以参考。

    笔者注:对于NLP中的低资源问题、复杂样本问题、数据质量问题等,我们将在《高能NLP之路》专栏的下一篇文章中进行详细介绍,希望大家关注。

    彩蛋:百度2020关系抽取比赛的baseline可以采取哪些方法?

    除了百度官方给出的baseline[34],大家可以参考前文提及的[20][23]

    写在最后

    由于篇幅有限,并为给读者更好的阅读体验,本文删减了大量对模型内部的解读,更为细节的请阅读原文。

    • 如需下载本篇文档,可以到我的github下载。

    • 如有错误,请指正。

    • 未经允许,不得转载。

    参考

    1. ^Hierarchically-Refined Label Attention Network for Sequence Labeling https://arxiv.org/pdf/1908.08676.pdf

    2. ^Chinese NER Using Lattice LSTM https://arxiv.org/pdf/1805.02023.pdf

    3. ^abNeural Architectures for Nested NER through Linearization

    4. ^Nested named entity recognition revisited.

    5. ^abA Unified MRC Framework for Named Entity Recognition https://arxiv.org/pdf/1910.11476.pdf

    6. ^https://zhuanlan.zhihu.com/p/89019478

    7. ^abcdSpan-Level Model for Relation Extraction https://www.aclweb.org/anthology/P19-1525.pdf

    8. ^abDistant Supervision for Relation Extraction via Piecewise Convolutional Neural Networks. EMNLP

    9. ^Selective Attention over Instances (Lin 2016)

    10. ^Relation Extraction with Multi-instance Multi-label Convolutional Neural Networks.

    11. ^Distant Supervision for Relation Extraction with Sentence-Level Attention and Entity Descriptions

    12. ^Reinforcement Learning for Relation Classification from Noisy Data

    13. ^abcMatching the Blanks: Distributional Similarity for Relation Learning https://arxiv.org/pdf/1906.03158.pdf

    14. ^abExtracting Multiple-Relations in One-Pass with Pre-Trained Transformers

    15. ^abcdSimultaneously Self-Attending to All Mentions for Full-Abstract Biological Relation Extraction https://www.aclweb.org/anthology/N18-1080.pdf

    16. ^abc基于深度学习的联合实体关系抽取 http://www.czsun.site/publications/thesis.pdf

    17. ^End-to-End Relation Extraction using LSTMs on Sequences and Tree Structures https://www.aclweb.org/anthology/P16-1105.pdf

    18. ^Going out on a limb: Joint Extraction of Entity Mentions and Relations without Dependency Trees https://pdfs.semanticscholar.org/bbbd/45338fbd85b0bacf23918bb77107f4cfb69e.pdf?_ga=2.119149259.311990779.1584453795-1756505226.1584453795

    19. ^Extracting Relational Facts by an End-to-End Neural Model with Copy Mechanism

    20. ^abJoint entity recognition and relation extraction as a multi-head selection problem

    21. ^BERT-Based Multi-Head Selection for Joint Entity-Relation Extraction

    22. ^Adversarial training for multi-context joint entity and relation extraction

    23. ^abJoint Extraction of Entities and Relations Based on a Novel Decomposition Strategy

    24. ^Entity-Relation Extraction as Multi-Turn Question Answering https://link.zhihu.com/?target=https%3A//arxiv.org/pdf/1905.05529.pdf

    25. ^abcdhttps://zhuanlan.zhihu.com/p/65870466

    26. ^Span-based Joint Entity and Relation Extraction with Transformer Pre-training  https://arxiv.org/pdf/1909.07755.pdf

    27. ^Joint inference for fine-grained opinion extraction

    28. ^Investigating lstms for joint extraction of opinion entitiesandrelations.

    29. ^Incremental joint extraction of entity mentions and relations.

    30. ^End-to-end neural relation extrac- tion with global optimization.

    31. ^Jointextractionofentities and relations based on a novel graph scheme

    32. ^Joint extraction of entities and relations based on a novel tagging scheme. https://arxiv.org/pdf/1706.05075.pdf

    33. ^Joint Extraction of Entities and Overlapping Relations Using Position-Attentive Sequence Labeling

    34. ^abhttps://github.com/PaddlePaddle/Research/tree/master/KG/DuIE_Baseline

    35. ^Confident Learning: Estimating Uncertainty in Dataset Labels

    36. ^Graph Neural Networks with Generated Parameters for Relation

    37. ^GraphRel: Modeling Text as Relational Graphs for Joint Entity and Relation Extraction

    38. ^Attention Guided Graph Convolutional Networks for Relation Extraction

    39. ^Joint Type Inference on Entities and Relations via Graph Convolutional Networks

    40. ^abhttps://www.zhihu.com/search?type=content&q=%E5%85%B3%E7%B3%BB%E6%8A%BD%E5%8F%96

    41. ^ FewRel 2.0: Towards More Challenging Few-Shot Relation Classification

    42. ^DocRED: A Large-Scale Document-Level Relation Extraction Dataset

    43. ^Knowledge-Augmented Language Model and its Application to Unsupervised Named-Entity Recognition

    44. ^Description-Based Zero-shot Fine-Grained Entity Typing

    45. ^Zero-Shot Entity Linking by Reading Entity Descriptions

    46. ^Multi-Level Matching and Aggregation Network for Few-Shot Relation Classification

    47. ^Exploiting Entity BIO Tag Embeddings and Multi-task Learning for Relation Extraction with Imbalanced Data

    48. ^Massively Multilingual Transfer for NER

    添加个人微信,备注:昵称-学校(公司)-方向,即可获得

    1. 快速学习深度学习五件套资料

    2. 进入高手如云DL&NLP交流群

    记得备注呦

    展开全文
  • 华为C语言编程规范(精华总结

    万次阅读 多人点赞 2020-03-24 09:48:55
    4、每一个 .c 文件应有一个同名 .h 文件,用于声明需要对外公开的接口 如果一个.c文件不需要对外公布任何接口,则其就不应当存在,除非它是程序的入口,如main函数所在的文件。 现有某些产品中,习惯一个.c文件对应...
  • 数据库:第二章 《关系模式》概念总结

    千次阅读 多人点赞 2020-03-31 11:27:37
    一、关系数据结构及形式化定义 1. 关系模式的相关概念: 域: 域是一组具有相同数据类型的值的集合 笛卡尔积: 域上的一种集合运算 其中每一个元素(d1,d2,d3,……dn)叫做一个元祖,元祖中的每一个值叫做一个分量。...
  • 设W是域P上的线性空间V的一个非空子集合,若对于V中的加法及域PV的纯量乘法构成域P上的一个线性空间,则称W为V的线性子空间. 定义 设W是域P上的线性空间V的一个非空子集合,若对于V中的加法及域PV的纯量乘法...
  • ( 2 ) 偏序关系 等价关系 ( 等价关系 用于分类 | 偏序关系 用于组织 ) 2. 偏序集定义 ( 1 ) 偏序集定义 二. 偏序关系 示例 1. 小于等于关系 ( 1 ) 小于等于关系 说明 ( 2 ) 小于等于关系 分析 2. 大于等于...
  • 高一数学必修一《全称量词与存在量词》知识点总结一、全称量词全称命题1、全称量词:短语“对所有的”,“对任意的”在陈述中表示整体或全部的含义,逻辑中通常叫做全称量词,并用符号“”表示;2、全称命题:含有...
  • PostgreSQL 是一个免费的对象-关系数据库服务器(ORDBMS),在灵活的BSD许可证下发行。PostgreSQL 开发者把它念作post-gress-Q-L。PostgreSQL 的 Slogan 是 "世界上最先进的开源关系型数据库"。 什么是数据库? ...
  • 数据库关系代数详解

    万次阅读 多人点赞 2021-02-26 16:35:55
    数据库关系代数 1. 关系代数的运算 1.1 传统的关系运算 传统的关系运算起源于数学的集合论,有下面几种: 笛卡尔积运算 差运算 交运算 并运算 1.2 专门的关系运算 选择 投影 连接 除运算 1.2.1 关系运算中的基础...
  • 关系数据库关系型数据库一、数据库概述1、关系型数据库2、非关系型数据库二、数据库区别1、数据存储方式不同2、扩展方式不同3、对事务性的支持不同三、非关系型数据库产生背景四、Redis简介1、Redis 优点五、...
  • 偏导数的存在只能保证坐标轴平行的方向上函数的极限值等于函数值(仅仅是坐标轴平行的方向),但是连续是指函数以任何方向趋近于某一定点,二元函数本身是一个平面型的,趋于某一定点是从四面八方的,而平行于坐标...
  • 自推出后就成为商业应用的主要数据库模型(其他数据库模型,如分级、网络或对象模型相比)。如今已有许多商业关系数据库管理系统(RDBMS),如Oracle,IBM DB2和Microsoft SQL Server等;也有许多免费的开源关系...
  • 物理CPUVCPU的关系梳理总结

    万次阅读 2016-03-11 10:17:35
    背景说明: 在项目和培训中多次被问题FusionSphere物理CPU和vCPU的对应或分配关系,一个物理CPU能虚拟出多少个vCPU,一个vCPU的主频是多少等问题。设置了CPU预留、份额限制之后又是什么情况。 看过之前的一些讨论...
  • Java常见设计模式总结

    万次阅读 多人点赞 2021-09-18 17:18:54
    项目中合理的运用设计模式可以完美的解决很多问题,每种模式在现实中都有相应的原理来之对应,每种模式描述了一个在我们周围不断重复发生的问题,以及该问题的核心解决方案,这也是它能被广泛应用的原因。...
  • 背景说明: 在项目和培训中多次被问题FusionSphere物理CPU和vCPU的对应或分配关系,一个物理CPU能虚拟出多少个vCPU,一个vCPU的主频是多少等问题。设置了CPU预留、份额限制之后又是什么情况。 看过之前的一些讨论...
  • [信息论编码]知识点总结

    千次阅读 多人点赞 2021-12-02 15:42:10
    2021/12/02 from Xwhite 这个是预习完之后,感觉应该掌握的一些知识的总结。总共分成四个大部分吧 ...知识点总结信息量信源熵信道和信道容量信源编码信道编码(难点) 第一章的一些基本概念看书就.
  • 集合论图论 集合论部分 笔记总结

    千次阅读 2019-10-05 02:37:48
    二元关系是单根的定义:对于任意一个属于值域的y,在二元关系f定义中仅存在一个x,使属于f。单值类似。   2.3关系的表示和性质 在集合A上的二元关系f的关系矩阵;关系矩阵的乘法合成关系;可达矩阵; ...
  • 关于秩的等式不等式总结

    万次阅读 多人点赞 2016-10-13 23:58:18
    ,就意味着任意n-1阶子式全为0,由伴随矩阵的组成成分 A i j = 0 A_{ij} = 0 ,所以 r ( A ∗ ) = 0 r(A^*) = 0 当 r ( A ) = n − 1 r(A) = n-1 时, | A | = 0 , A A ∗ = 0 → r ( A ) + r ( A ∗ ) ≤ n → ...
  • 超详细的MySQL三万字总结

    万次阅读 多人点赞 2021-08-22 21:27:51
    文章目录MySQL基础数据库的介绍数据库概述数据的存储方式数据库的概念常见数据库排行榜数据库的安装卸载数据库的安装数据库的卸载数据库服务的启动登录Windows 服务方式启动DOS 命令方式启动控制台连接数据库...
  • 微分方程的阶数、任意常数个数、特征根个数的关系,以及由解倒求各种类型微分方程的方法:倒推法、行列式法、特解代入法、消C法、综合法。
  • 数据结构算法知识总结(一)

    千次阅读 2020-04-24 17:15:07
    下面是对学习数据结构算法一些基础知识总结,主要讲解的是数据结构算法之间的关系。所以我称它为数据结构算法知识总结之数据结构算法之间的关系。如有错误,欢迎指出。 概要: 什么是数据结构?数据结构...
  • 论文总结——因果发现推断

    千次阅读 2019-10-31 08:49:51
    这里写自定义目录标题欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、...
  • JavaScript基础知识全总结

    万次阅读 多人点赞 2019-04-11 10:37:31
    浏览器是指可以显示网页服务器或者文件系统的HTML文件内容,并让用户这些文件交互的一种软件。 通俗的讲:可以显示页面的一个软件, 国内网民计算机上常见的网页浏览器有,QQ浏览器、Internet Explorer、Firefox、...
  • 10万字208道Java经典面试题总结(附答案)

    万次阅读 多人点赞 2021-08-01 16:05:55
    作者简介:哪吒,CSDN2021博客之星亚军、新星计划导师✌、博客专家 哪吒多年工作总结:Java学习路线总结,搬砖工逆袭Java架构师 B站特别推荐:2022年B站Java学习路线一条龙(Java面试篇),如何让自己在【金三银四】...
  • 【知识点总结】大数据技术原理应用

    千次阅读 多人点赞 2020-11-05 10:23:16
    本文是对《大数据云计算导论》课程知识点的应试总结。基本涵盖了《大数据技术原理应用》的重点内容。 思维导图由@福尔摩东整理 第一章 大数据概述 1、三次信息化浪潮 信息化浪潮 发生时间 标志 解决的问题 ...
  • 一、变上限积分原函数的关系? 要弄清楚它们之间的关系,...所以如果能求出一个函数在某个区间 x 轴围成的面积,那么它在这个区间的定积分就是存在的,也可以说这个函数在这个区间是可积的。 3.定积....
  • 定义:对于任意实数x,记函数 F(x) = P{X ≤ x},-∞ < x < +∞,称 F(x)是随机变量X的分布函数。 分布函数的值等于随机变量X在区间 (-∞,x] 上取值的概率,即事件 “X ≤ x” 的概率。...
  • 并发场景可能存在的需求之——任意编排 1 多个执行单元的串行请求 2 多个执行单元的并行请求 3 阻塞等待,串行的后面跟多个并行 4 阻塞等待,多个并行的执行完毕后才执行某个 5 串并行相互依赖...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 188,303
精华内容 75,321
关键字:

存在与任意的关系总结

友情链接: prac3_wr_rd_flash.rar