Metric Learning for Ordered Labeled Trees with pq-grams-猫眼课题宝

DOI：

10.3233/faia200254

发表时间：

2020-03

期刊：

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

Hikaru Shindo;Masaaki Nishino;Yasuaki Kobayashi;Akihiro Yamamoto

计算两个数据点之间的相似度在许多机器学习算法中起着至关重要的作用。度量学习的目标是从数据中自动学习一个好的度量。已有的树结构数据度量学习研究大多采用树编辑距离学习的方法。然而，编辑距离不适用于大数据分析，因为它会产生较高的计算成本。在本文中，我们提出了一种新的基于PQ-gram的树型数据度量学习方法。PQ-gram距离是有序标记树的距离，其计算量比树编辑距离小得多。为了实现基于PQ-gram的度量学习，我们提出了一种新的可微参数距离--加权PQ-gram距离。我们还提出了一种基于大间隔最近邻(LMNN)的距离学习方法，这是一种研究得很好且实用的度量学习方案。我们将度量学习问题描述为一个优化问题，并使用梯度下降技术进行度量学习。实验表明，该方法不仅在各种分类问题上取得了与基于编辑距离的方法相当的结果，而且比基于编辑距离的方法更快地解决了分类问题。

Computing the similarity between two data points plays a vital role in many machine learning algorithms. Metric learning has the aim of learning a good metric automatically from data. Most existing studies on metric learning for tree-structured data have adopted the approach of learning the tree edit distance. However, the edit distance is not amenable for big data analysis because it incurs high computation cost. In this paper, we propose a new metric learning approach for tree-structured data with pq-grams. The pq-gram distance is a distance for ordered labeled trees, and has much lower computation cost than the tree edit distance. In order to perform metric learning based on pq-grams, we propose a new differentiable parameterized distance, weighted pq-gram distance. We also propose a way to learn the proposed distance based on Large Margin Nearest Neighbors (LMNN), which is a well-studied and practical metric learning scheme. We formulate the metric learning problem as an optimization problem and use the gradient descent technique to perform metric learning. We empirically show that the proposed approach not only achieves competitive results with the state-of-the-art edit distance-based methods in various classification problems, but also solves the classification problems much more rapidly than the edit distance-based methods.

Metric Learning for Ordered Labeled Trees with pq-grams

文献摘要

相似文献