自动构造词汇继承层次的方法

理论计算机科学电子笔记51（2001）网址：http://www.elsevier.nl/locate/entcs/volume51.html13页一种归纳继承层次Wiebke Petersen1德国杜塞尔多夫HeinrichHeine大学计算机语言学研究所摘要提出了一种自动构造继承层次的方法。它是以数学理论中严格的集合论观点为基础的形式概念分析。由此产生的层次结构是概念格。本文还讨论了非单调遗传网络诱导方法的一个推广。结果表明，形式概念分析的主要思想，即形式概念分析是一种新的概念分析方法.e.形式上下文、概念格和蕴涵集合提供了三种不同的查看要表示的数据的方式，每种方式提供了解决知识表示问题的不同方式1介绍由于在现代语言学理论（如HPSG）中，越来越多的信息被认为是词汇的，词汇的规模和复杂性都在增长。通过分解出由一组符号共享的那些属性并将它们表示在继承层次结构中，可以消除词汇信息的许多冗余。通过这种方式，避免了冗余，捕获了泛化，并且所需的内存最小化。鉴于现实词典的大小，这种层次结构的手动构造是耗时且容易出错的。因此，自动获取词汇知识的技术是可取的。有许多方法可以通过在现有层次结构中插入新对象来自动更新词典：这项任务被称为1994 [9]）。在语言学词典的框架内，主要有两种非增量的方法。Barg提出了一种算法，用于归纳DATR中表示的层次结构（参见。Barg 1996 [1，2]），这是一个1电邮地址： petersew@uni-duesseldorf.de2001年由ElsevierScienceB出版。 诉 操作访问和C CB Y-NC-N D链接。PETERSEN2用于在非单调多重继承网络中表示词汇信息的广泛形式主义（cf. EvansGazdar 1996 [5]）。在这里，用户必须提供选择中间假设的标准，限制搜索空间。根据选择的标准，结果-因此，DATR理论可以非常紧凑。另一种方法，由Sporleder提出，涉及一种算法，该算法推断用于构造 特 征 结 构 层 次 结 构 的 决 策 树 （ 参 见 。S porleder1999[18] ， Lüngen&Sporleder1999 [13]）。本文提出了一种从非结构化数据中自动获取词汇知识的不同方法。本文的主要创新之处在于将形式概念分析（）的数学理论（cf.Ganter Wille1999 [6]）用于提取数据固有的单调继承关系。这种方法的实施，并已成功地通过计算英语resp的派生信息的层次结构进行了测试。词汇数据库CELEX中的德语词元。22从非结构化数据2.1一种诱导紧层次的方法大多数涉及层次结构学习的问题都可以归结为以下问题：假设一组给定的对象-属性对，3它将被组织在一个继承网络中;哪一个继承层次结构最好地捕捉了这些数据之间的内在关系对给定数据的表示至少有两个此外，良好的代表性通过捕获泛化来避免冗余;如果每个属性和每个对象都只声明一次，则表示是无冗余的。此外，可以要求所构造的网络中的节点的数量是最小的。一些使用继承网络表示的理论要求网络具有特殊的性质;例如，它们可以只允许单调或单一的继承关系，或者它们可以要求网络形成一个连接半格，以便每个节点集都有一个最小上界。表1给出了一个示例数据集，该数据集由七个德语名词（Herr2CELEX是荷兰词汇信息中心编制的大型电子数据库（http：//www.kun.nl/celex/）3应用于对象的特征值对可以被视为其属性之一。 这是一个很强的简化，因为一个对象的特征的适当性不再被捕获。一种可能的解决方法是通过添加“特征x在这里是合适的”这类PETERSEN3性别辛农辛根成达新接入普勒诺姆普勒尔根普勒达特普勒尔阿克先生masc** n* n* n* n* n* n* nFriedemasc** ns* n* n* n* n* n* nStaatmasc** s*** n* n* n* n白衬衫neut** s*** n* n* n* nFarbe有限元***** n* n* n* nOnkelmasc** s***** n*Uferneut** s***** n*表1输入数据：多值上下文性别：masc性别：女性性别：中性sing nom：*sing gen：*sing gen：* ssing gen：* nsing gen：*nssing dat：*sing dat：* nsing acc：*sing acc：* n用户名：*plur nom：*nplur gen：*plur gen：* nplur dat：* nplur acc：*plur accc：*n先生XXXXXXXXXFriedeXXXXXXXXXStaatXXXXXXXXX白衬衫XXXXXXXXXFarbeXXXXXXXXXOnkelXXXXXXXXXUferXXXXXXXXX表2输入数据：在单值上下文'shore'）。数据是以与对象相关的特征值对的形式（在形式概念分析中，表2显示了转换后的数据（单值上下文），它将被组织在继承层次结构中。它由七个对象（词素）组成，每个对象都适用于19个属性的子集构造这些数据的一种自然方式是为每个对象获取相应的属性集，并根据超集关系对这些属性集进行排序。可以添加一个底部元素以获得连通偏序。由于示例数据是这样一种形式，4 在本文中，“*”代表派生词形式的根。为例如，如果特征PETERSEN4neut**_s*****_n *Ufermascmasc**_n *_n *_n**_ns *_n *_n*_n *_n *_n *_n *_n *_n *_n *_n先生Friede有限元*****_n *_n *_n *_nFarbeneut**_s***_n *_n *_n *_n白衬衫masC**_s*****_n *OnkelFig. 1. 按属性集图二、按对象集排序的层次结构对应于单个对象的属性集合构成另一个属性集合的超集，这种方法根本不会导致任何层次关系。输出是图1所示的完全可扩展的结构;它显示了与输入数据相同的冗余范围。通过对具有共同属性的对象集进行排序来构造表2中的数据的相反方式导致了所示的层次结构 如图2所示（如果不能从较低的节点继承，则对象名用粗体显示;继承方向是自下而上）。这也不是没有冗余的，因为对象“Staat”、“Hemd”、“Onkel”和“Ufer”必须被声明多次，以确保属性继承正确的对象。这个问题产生于片面的外延观点，只考虑对象集。如果将这两种结构化数据的方法结合起来，就可以获得无冗余的解决方案（见图3）。所构造的网络是一个单调的多重继承的层次结构。它以这样一种方式标记，即每个对象和底部性别：mascplur nom：*_n，plurgen：*_n，plur acc：*_n斯塔特、赫姆德、法布、昂克sing dat：*，sing弗里德先生，斯塔特先生，赫姆德先生，sing nom：*，plur dat：*_nFriedesing gen：*_ns先生sing gen：*_nFarbe性别：femsing gen：*先生，弗里德sing dat：*_n，sing先生，弗里德Staat，Onkel弗里德先生，斯塔特，赫德·法布plur nom：*，plurgen：*，斯塔特、赫姆德、昂克sing gen：*_s赫姆德性别：中性翁克尔PETERSEN5性别：femsing gen：*StaatFriedeFarbe先生OnkelUfersing gen：*_nssing gen：*_n白衬衫sing dat：*_nsing accc：*_nplur nom：* plurgen：*性别：中性sing gen：*_s性别：mascplur nom ：*_nplurgen：*_nsing dat：* singsing nom：* plur dat：图3.第三章。对象和属性概念的偏序每个属性名称只出现一次。这是通过将每个属性附加到最高可能的节点，并将每个对象附加到最低可能的节点来实现的;有关更多细节，请参见第2.2节。以这种方式构造的继承层次结构具有理想的属性，即节点的数量最多扩展属性数量和对象数量之和2，因此它们非常紧凑。此外，它们是数据一致的和完整的，因为表2中表示一个对象的属性的行可以通过收集在用对象名称标记的节点之上的标记节点的所有属性名称来重构。类似地，对应于一个属性的列由可以在属性下面找到的对象名称给出。一些理论要求继承网络是连接半格，其中任何两个元素都有一个最小上界（cf. Carpenter 1992 [3]）。图3所示的偏序不是半格，因为例如标记为“Hemd”和“Staat”的节点没有唯一的最小上界。接下来的部分表明，即使是完整的格也可以通过使用形式概念分析来归纳，形式概念分析是一种将外延和内涵观点结合在一个理论中的集合论方法。2.2用形式概念分析方法构造继承格形式概念分析是一种数学理论，特别设计用于提供知识的形式模型作为交流工具（参见。Zickwolf 1994 [22]）。它旨在结合形式化表示的优点，如机器可读和可处理，以及表示PETERSEN6∈}⊆ ×∈≤ ⇔ ⊆ ⇔⊇{∈| ∀ ∈{∈| ∈∈⊆其可以以人类可读的方式可视地呈现。它已被应用于以下语言问题：meronymy （ cf 。 Priestival 1998 [17] ） ， WordNet （ cf.Priesthood 1998[16]），speech-act-verbs语义学(Gro[8]和动词范例（Großkopf 1996 [7]）。在本文的上下文中，只能列出形式概念分析（FCA）的主要定义;更多细节请参见Ganter Wille 1999[6]。FCA首先将形式背景K定义为三元组（G，M，I），由一组对象G、一组属性M和一个二元关联关系I G M组成，其中（g，m）I表示形式上下文通常用交叉表表示（见表2）。 对于对象A的任何子集G，它们的公共属性集被定义为AJ：= m M g A：（g，m）I。 类似地，属性的子集B M的公共对象的集合是BJ：=GGMB：（g，m）I. 一个形式概念是一个对（A，B），具有属性A=BJ和B=AJ，其中A称为概念的范围，B称为概念的意图上下文的所有形式概念的集合部分地由子概念-超概念-关系排序：（A1，B1）（A2，B2）的1一个2B1B2. 可以证明了形式概念的集合连同这个偏序形式一个完整的格，称为形式概念格（见图4）。在图4中，只有属性和对象概念被标记，其中与属性m相关联的属性概念μ（m）是其意图包含m的最大概念，类似地，与对象g相关联的对象概念γ（g）是其范围包含g的最小概念。如图4所示，概念格可以被视为单调的多重继承层次结构。由于层次结构是建立在子集关系的基础上的，因此排除了从父节点继承的冲突属性。然而，在父节点具有不相交的属性集的意义上，继承不是正交的。由于正交性在HPSG（Pollard Sag 1987 [15]）等理论中有规定，因此当FCA用作构建层次结构的工具时需要特别注意。图3的继承网络是属性和对象概念的偏序集（AOC-偏序集）的图像;因此它是图4的概念格的一个子集。与AOC-偏序集相比，概念格中的节点数量增加，因为节点的插入不引入任何新的属性（或对象），但代表最大的下或上属性（或对象）。最小上限5.如果导出的层次要用在不要求它是格的形式主义中，那么使用AOC-偏序集可能就足够了。然而，应该注意的是，格是众所周知的对象，其易于计算处理，并且许多存在算法此外，由于概念格表示每个5在某些情况下，节点的数量会急剧增加;例如，在概念格中捕捉包含在词汇数据库CELEX中的德语词元的派生信息的节点的数量大于72.000;然而，如果相同的信息被表示在AOC偏序集中，则节点的数量小于4.000。PETERSEN7plur nom：* plurgen：*sing accc：*_nsing dat：*_nFriede先生FarbeOnkelUfersing gen：*_nssing gen：*_n性别：女性sing gen：*Staat白衬衫性别：中性sing gen：*_s性别：mascplur nom：*_nplur gen：*_n plursing dat：* singsing nom：* plur dat：见图4。 概念格一组对象的公共属性，在某些情况下，在层次结构中插入新对象是简单的。3关于从可测数据中3.1一般性评论由于词汇信息可以很好地以规则、次规则和例外形式进行结构化，因此许多理论允许非单调继承的元素，例如DATR中的默认继承（cf. EvansGazdar 1996 [5]）或基于（类型化）特征结构的默认统一理论（例如，Copestake Lascarides 1999 [4]）。在非单调遗传网络中，必须重新解释支配关系。在单继承网络的框架中，这通常是通过规定在冲突属性的情况下，附着到节点的那些属性优先于从父节点继承的那些属性来完成的（关于非单调继承的形式语义，例如，参见Touretzky 1986 [21]中的“推理距离排序”的概念）。在多重继承网络的情况下，继承关系的解释引起了理论问题。其中一个关键问题是如何处理从两个或多个父节点继承的相互矛盾的信息。为了解决这个问题，已经采用了几种策略，例如，通过规定正交继承来排除有问题的情况，显式地标记哪些信息是可废止的并且可以被覆盖，或者显式地对父信息PETERSEN8⊆→∈{} →{}结有一些新的解释，试图避免这些规定（如默认统一）。CopestakeLascarides 1999 [4]）。非单调结构的自动归纳会导致特殊的问题，因为数据不像单调关系那样公开地揭示非单调关系。使用非单调性的可能表示的集合比单调表示的集合大得多。独立的选择se-mantics的非单调继承，它必须决定哪些信息可能会被覆盖。在大多数方法中，其思想是网络的上部区域编码规则或默认情况，而次规则和例外信息被放置在这些节点之下。节点从其祖先继承正则属性，如果它们没有被次正则或异常属性覆盖的话。为了使用默认信息（可废止信息）找到一个“好”的表示，必须找到一种方法来决定在何种情况下可以覆盖哪些信息。一种方法是研究适用于一组对象的属性类的相似性。如果两个类非常相似，其中一个可以成为另一个的子类;通常情况下，将应用于更大对象类的类作为上层（更一般）类会更有利。为了应用这种方法，需要一个相似性度量;在形式概念分析的框架中，相似性度量已经被形式化（参见。Lengnink 1996 [11];Leischner 1999 [10]）。解决决定哪些信息被标记为缺省信息的任务的另一种方法是研究在形式上下文中有效的属性含义集3.2隐含集合提出的缺省信息集合形式上下文的属性蕴涵的形式是“对于属性m1，m2，.， m k适用，属性a1，a2，.， a我也申请”或m1，m2，. MK一个一个二... a我（参见Ganter Wille1999）。 设A和B是属性集M的子集，蕴涵AB有效于上下文当且仅当B AJJ。6在概念格中，这意味着概念（mJ，mJJ）是概念（AJ，AJJ）的超概念，对于每个MB.因为每个前提和最大对应的结论形成了上下文的一个概念的意图，即结构概念格的有效蕴涵集是由概念格到同构的有效蕴涵集决定的。 一些含义可以从其他含义中推导出来，定义有效蕴涵的最小基的概念（参见Ganter Wille 1999）。 表3中给出了示例上下文的最小蕴涵基。7为了解决决定哪一组属性构成可接受集合的任务，6A′′是（A′）′的缩写。7含义1表示示例上下文的所有对象都有两个共同的属性。第15-19节的每一个含义在上下文中都没有支持，这意味着不存在前提的所有属性都适用的对象PETERSEN9联系我们1{}→ {singnom：*，plur dat：* n}2{sing gen：*} 4{ gender：fem}3{gender：fem}→{ sing acc：*，plur nom：* n}4{plur nom：*} 4{ plur gen：*}4{ plur acc：*}5{plur nom：*}→{ sing gen：* s}6{gender：neut} →{ sing gen：* s}7{sing gen：* s} →{ sing acc：*}8{sing acc：*} 4{ sing dat：*}9{sing gen：* ns} →{ sing acc：* n}10{sing gen：* n} →{ sing acc：* n}11{sing acc：* n} 4{ sing dat：* n}12{sing acc：* n}→{ plur nom：* n，gender：masc}13{plur nom：* n} 4{ plur gen：* n} 4{ plur acc：* n}14{gender：masc，sing acc：*}→{ sing gen：* s}15{plur gen：* n，plur nom：*}→{ sing acc：* n}16{sing gen：* s，gender：fem}→{ sing acc：* n}17{gender：masc，gender：neut}→{ sing acc：* n}18{sing acc：* n，sing acc：*}→{ sing gen：* n，sing gen：*ns}19{sing gen：* n，sing gen：* ns}→{ gender：neut，gender：fem，plur nom：*}表3最小有效蕴涵必须考虑精心选择的缺省信息的质量是什么。首先，默认信息不应比非默认信息更具体，即如果某些默认属性暗示其他属性，则后者应属于默认信息集 也另一个假设是，在数据表示中使用默认值应该减少表示的大小，并使结构更加紧凑。最后，默认信息必须一致。在形式概念格的框架中，这些假设导致了以下定义：可接受的缺省信息集D是属性集M的子集，具有以下性质：D=DJJ（包括所有结论）和DJ=(the默认信息是一致的）。 最后一个条件是 至少有一个对象具有所有的默认属性似乎比通常的一致性概念更强，通常的一致性概念只排除单个特征的冲突值。但是，由于在本方法中，每个特征-值对由单个属性表示，并且由于通过第一条件，默认信息形成概念意图，因此放弃第二条件将需要所有属性的集合构成可接受的默认信息集合PETERSEN10}Friede先生FarbeStaatOnkelUfer白衬衫sing gen：*_nssing gen：*_n性别：femsing gen：性别：中性plurnom：*plur gen：sing dat：*_n sing（性别：masc）sing nom：*（plur nom：*_n）（sing gen：*_s）（plurgen：*_n）（sing dat：*）plur dat：*_n（sing acc：*）图五. 默认继承层次结构信息，可能包含冲突的特征值对。默认情况的选择取决于所选择的表示形式、要表示的数据以及表示的设计者关于其紧凑性和其分层结构的特殊愿望。因此，似乎不可能自动找到默认信息的最佳选择。该方法提出了可能的可接受的缺省集，即非空范围的形式概念的意图。范围的大小，i。e.可以选择具有共同的默认信息的对象的数量和意图的大小，以支持选择默认集合的决定。使用上面介绍的方法，甚至可以计算对应于可接受默认集的非单调继承网络。为了避免多重继承冲突信息引起的冲突，应用了显式地将默认信息标记为可废止的策略。非单调网络是通过计算由原始上下文组成的子上下文所对应的格而获得的，其中原始上下文没有那些不适用于所有对象的集合的默认属性。 图5显示了与可接受的默认集对应的继承层次结构{gender：masc，sing nom：*，sing gen：* s，sing dat：*，sing acc：*，plurnom：* n，plurgen：* n，plurdat：* n，pluracc：n，其中可废止属性放在方括号中。为了对子节点和异常进行建模，可以将进一步的默认属性集附加到顶部节点的子节点。在这种情况下，必须特别注意属性的正确继承。除了看有效的含义，还可以看部分含义，除了一定数量的例外对象之外，部分含义都是有效的（参见。1994年[14]）。PETERSEN113.2.1关于属性探索的这个例子展示了另一个有趣的数据表示问题。 作为在大多数关于词汇的语言学任务中，是已知的，并且用于对对象进行分类的特征属性是固定的，但是像往常一样，对象的集合太大而无法检查每个对象-属性对。语言学家寻找的对象的选择，提供了相同的关系方面的属性作为整个宇宙。形式概念分析提供了一种称为属性探索的工具来找到这样一个完整的选择上下文（参见。Stumme 1996 [19，20]，Ganter Wille 1999[6]）。它计算对应于实际上下文的蕴涵的最小基，并询问用户每个蕴涵在对象的宇宙中是否有效，或者是否已知反例。然后将反例添加到上下文中，并重新计算其含义，直到所有含义都被接受。在本示例中，用户将已经拒绝隐含1并且添加例如像“Auto”的名词，其用“* s”构建其所有复数形式。通过这种方式，可以找到一个选择的背景下，所有可能的代表性的示范范例。4结论在本文中，我提出了三种不同的方式来看待同一数据：表格形式（见表1和表2），层次网络（见表4和表3），以及一组属性含义（见表3）。这些视图中的每一个都在数据处理领域提供了不同的优势。数据通常以表格形式存储，因为它允许容易的数据输入。 此外，委员会认为，表格直接展示可用于单个对象的信息。在分层网络中表示数据有助于揭示存储信息的更多隐式结构。由于泛化被捕获，继承层次结构允许紧凑和较少冗余的表示。此外，网络特别适合于分类任务，如对未指定对象进行分类。最后，属性蕴涵系统明确地揭示了属性之间的相互依赖性。如本文所示，蕴涵集可用于支持定义默认集和构造非单调继承层次结构。此外，属性探索可以更容易地以引导的方式有效地探索对象的巨大宇宙，并找到代表整个宇宙的对象的最小选择。我想强调一个显著的性质，即引入的三种数据表示是信息等价的，因为它们中的每一种都可以从彼此获得。事实证明，将形式概念分析的思想应用于知识表示和处理的某些问题（例如，语言学词典）是一种很有前途的方法。PETERSEN12引用[1] Barg，P.，DATR理论的自动推理，在：H.- H. Bock和W. Polasek，编辑，数据分析和信息系统。统计和概念性应用程序（第19届大会通过的关于通用分类方 法 的 第 19 届 大 会 的 决 定 ） 。 V. University of Basel ， 1995-03-8/10 ）（1996），pp. 506-515[2] Barg ， P. ， “ 自 动 化 语 言 学 知 识 。 一 种 分 析 推 理vonDATR-Theorien，”Nieme y er，Tubingen，1996.[3] Carpenter，B.，“类型化特征结构的逻辑。与应用统一文法，逻辑程序和约束解决。剑桥大学出版社，剑桥，1992年。[4] Copestake，A.和A. Lascarides，基于约束的框架中的默认表示，计算语言学25（1999），pp. 55比105[5] 埃文斯河，巴西-地和G.Gazdar，Datr：A Language for Lexical KnowledgeRepresentation，Computational Linguistics22（1996）.167-216[6] 甘特湾和R. Wille，“形式概念分析。数学基础，[7] Großkopf，A.，语言学中动词范式的形式概念分析，在：E.迪代，Y. Lechevallier和O. Opitz，editors，Ordinal and Symbolic DataAnalysis，Springer，Berlin，1996 pp. 70-79.[8] Großkopf，A.和G. Harras，Begri J. Erkundung Semantischer Strukturen vonSprechaktverben， in：G. Stumme 和 R. Wille ， editors， Begri SchoolicheWissensverarbeitung： Methoden und Anwendungen ，Springer， Berlin，1999 pp.273-295.[9] Kilbury，J.，P. Naerger和I. Renz，Simulation lexikalischen Erwerbs，in：S.W. F、 C. Ha bel和G. 李克文主编，《语言学：研究与进展》，西德意志出版社，1994年，第100页。251-271。[10] 莱施纳湖，可加性相似性度量，技术报告FB4预印本2022，Te ch nis cheUniversit？atDarmstadt，Fa c hberei chMathematik（1999）。[11] Lengnink， K. ， “F ormalisierungen v on Aühnli c h k eiten ausder Si c h t der F ormalen Begri sanalysis ， ”Shaker Verlag ，Aachen，1996.[12] 光，M，在基于特征的默认继承层次结构中的分类，在：H. Trost，编辑，KONVENS'94程序设计：VerbeitunnaturlicherSprache。OüsterreichischeGese llschaftfurürArti ficialInte lligen c e（1994），pp. 220-229[13] Lüngen，H. 和DC。 S.porleder，词汇遗传等级的可持续归纳，J. Gippert，编辑 ， GLDV 第 11 届 年 会 论 文 集 ： 多 语 言 语 料 库 。 Codierung ，Strukturierung，Analyse，Prague，1999，pp. 42-52.PETERSEN13[14] Luxenburger，M.，部分含义，技术报告FB4预印本1612，Te ch nis cheUniversit？atDarmstadt，Fa c hberei chMathematik（1994）。[15] 波拉德角和I. Sag，基于信息的句法和语义，技术报告13，语言和信息研究中心（1987）。[16] 普里韦，U.，采用关系概念分析的方法对WordNet进行了形式化描述。Fellbaum，编辑，WordNet：一个电子词汇数据库及其应用，麻省理工学院出版社，1998页。179-196.[17] 普里韦，U.，“Relational concept analysis: semantic structures in dictionaryand lexical[18] Sporleder，C.，“学习词汇概括。《现代机器学习方法的操作评估》，硕士论文，比勒费尔德大学[19] Stumme ，G.， 属性 探索与 背景 的影响 和例外 ， 在：H.- H. Bock 和W.Polasek，编辑，数据分析和信息系统。统计和概念方法（第19届德国分类学会年会论文集）。 诉，巴塞尔大学，1995-03-8/10）（1996），pp.457-469[20] Stumme，G.， 形式概念分析中的探索工具，在：E。迪戴，Y. Lechevallier和O. Opitz，editors，Ordinal and Symbolic Data Analysis，Springer，Berlin，1996 pp. 70比79[21] Touretzky，D.美国，“The Mathematics of Inheritance Systems,” ResearchNotes in Artificial Intelligence, Morgan Kaufmann Publishers, Los[22] Zickwol，M.，形式化的贝格里分析在科学研究中的作用，载R. Wille和M.Zickwol，editors，Begri Wissensverarbeitung：Grundlagen und Aufgaben，BI-Wissenschaftsverlag，Mannheim，1994 pp. 173- 190。