Ac ce pt ed m an us cr ip t Learning Probabilistic Models of Tree Edit Distance ⋆-猫眼课题宝

DOI：

发表时间：

2017

期刊：

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

Marc Bernard;L. Boyer;Amaury Habrard;M. Sebban

如今，人们对树结构数据的机器学习和模式识别越来越感兴趣。树实际上提供了一个合适的结构表示来处理复杂的任务，如Web信息提取，RNA二级结构预测，计算机音乐或半结构化数据（例如XML文档）的转换。在这些领域中的许多应用程序需要计算的相似性对树。在这种情况下，树编辑距离（艾德）已调查多年，以提高其计算效率的主题。然而，在其经典形式中使用时，树艾德需要通常难以调整的先验固定编辑成本，这几乎没有为解决复杂问题留下空间。在本文中，为了克服这个缺点，我们专注于自动学习的非参数随机树ED。更确切地说，我们感兴趣的两种概率方法。第一个构建一个生成模型的树艾德从一个联合分布的编辑操作，而第二个作品从一个条件分布，然后提供一个判别模型。为了解决这些任务，我们提出了一个适应的期望最大化算法学习这些分布在原始的编辑成本。进行了两个实验。第一个是实现人工数据和确认的兴趣，学习树艾德，而不是一个先验施加编辑成本;第二个是应用到模式识别任务，旨在分类手写数字。这项工作是正在进行的ARA土拨鼠研究项目的一部分。电子邮件地址：marc. univ-st-etienne.fr（Marc Bernard）、laurent. univ-st-etienne.fr（Laurent Boyer）、amaury. lif.univ-mrs.fr（Amaury Habrard）、marc. univ-st-etienne.fr（Marc Sebban）。2007年10月30日提交给爱思唯尔的预印本

Nowadays, there is a growing interest in machine learning and pattern recognition for tree-structured data. Trees actually provide a suitable structural representation to deal with complex tasks such as web information extraction, RNA secondary structure prediction, computer music, or conversion of semi-structured data (e.g. XML documents). Many applications in these domains require the calculation of similarities over pairs of trees. In this context, the tree edit distance (ED) has been subject of investigations for many years in order to improve its computational efficiency. However, used in its classical form, the tree ED needs a priori fixed edit costs which are often difficult to tune, that leaves little room for tackling complex problems. In this paper, to overcome this drawback, we focus on the automatic learning of a non parametric stochastic tree ED. More precisely, we are interested in two kinds of probabilistic approaches. The first one builds a generative model of the tree ED from a joint distribution over the edit operations, while the second works from a conditional distribution providing then a discriminative model. To tackle these tasks, we present an adaptation of the Expectation-Maximization algorithm for learning these distributions over the primitive edit costs. Two experiments are conducted. The first is achieved on artificial data and confirms the interest to learn a tree ED rather than a priori imposing edit costs; The second is applied to a pattern recognition task aiming to classify handwritten digits. ⋆ This work is part of the ongoing ARA Marmota research project. Email addresses: marc.bernard@univ-st-etienne.fr (Marc Bernard), laurent.boyer@univ-st-etienne.fr (Laurent Boyer), amaury.habrard@lif.univ-mrs.fr (Amaury Habrard), marc.sebban@univ-st-etienne.fr (Marc Sebban). Preprint submitted to Elsevier 30 October 2007 Ac ce pt ed m an us cr ip t

Ac ce pt ed m an us cr ip t Learning Probabilistic Models of Tree Edit Distance ⋆

文献摘要

被引文献

相似文献