Metric Learning for Ordered Labeled Trees with pq-grams

• URL: http://arxiv.org/abs/2003.03960v1
• Date: Mon, 9 Mar 2020 08:04:47 GMT
• Title: Metric Learning for Ordered Labeled Trees with pq-grams
• Authors: Hikaru Shindo, Masaaki Nishino, Yasuaki Kobayashi, Akihiro Yamamoto
• Abstract summary: 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. We empirically show that the proposed approach achieves competitive results with the state-of-the-art edit distance-based methods.
• Score: 11.284638114256712
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  This study introduces a novel guided tree search algorithm with dynamic node selection and node-level exploration budget. Experiments conducted on the GSM8K and TabMWP datasets demonstrate that our approach enjoys significantly lower computational costs compared to baseline methods.
  arXiv  Detail & Related papers  (2024-06-29T05:14:04Z)
• A simple way to learn metrics between attributed graphs [11.207372645301094]
  We propose a new Simple Graph Metric Learning - SGML - model with few trainable parameters. This model allows us to build an appropriate distance from a database of labeled (attributed) graphs to improve the performance of simple classification algorithms.
  arXiv  Detail & Related papers  (2022-09-26T14:32:38Z)
• Deep Relational Metric Learning [84.95793654872399]
  This paper presents a deep relational metric learning framework for image clustering and retrieval. We learn an ensemble of features that characterizes an image from different aspects to model both interclass and intraclass distributions. Experiments on the widely-used CUB-200-2011, Cars196, and Stanford Online Products datasets demonstrate that our framework improves existing deep metric learning methods and achieves very competitive results.
  arXiv  Detail & Related papers  (2021-08-23T09:31:18Z)
• Towards Interpretable Deep Metric Learning with Structural Matching [86.16700459215383]
  We present a deep interpretable metric learning (DIML) method for more transparent embedding learning. Our method is model-agnostic, which can be applied to off-the-shelf backbone networks and metric learning methods. We evaluate our method on three major benchmarks of deep metric learning including CUB200-2011, Cars196, and Stanford Online Products.
  arXiv  Detail & Related papers  (2021-08-12T17:59:09Z)
• Distance Metric Learning through Minimization of the Free Energy [0.825845106786193]
  We present a simple approach based on concepts from statistical physics to learn optimal distance metric for a given problem. Much like for many problems in physics, we propose an approach based on Metropolis Monte Carlo to find the best distance metric. Our proposed method can handle a wide variety of constraints including those with spurious local minima.
  arXiv  Detail & Related papers  (2021-06-10T04:54:25Z)
• Supervised Tree-Wasserstein Distance [21.9998734051455]
  We propose the Supervised Tree-Wasserstein (STW) distance, a fast, supervised metric learning method based on the tree metric. We show that the STW distance can be computed fast, and improves the accuracy of document classification tasks.
  arXiv  Detail & Related papers  (2021-01-27T16:24:51Z)
• Fast Uncertainty Quantification for Deep Object Pose Estimation [91.09217713805337]
  Deep learning-based object pose estimators are often unreliable and overconfident. In this work, we propose a simple, efficient, and plug-and-play UQ method for 6-DoF object pose estimation.
  arXiv  Detail & Related papers  (2020-11-16T06:51:55Z)
• MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
  We present a novel algorithm for learning optimal classification trees based on dynamic programming and search. Our approach uses only a fraction of the time required by the state-of-the-art and can handle datasets with tens of thousands of instances.
  arXiv  Detail & Related papers  (2020-07-24T17:06:55Z)
• Provably Robust Metric Learning [98.50580215125142]
  We show that existing metric learning algorithms can result in metrics that are less robust than the Euclidean distance. We propose a novel metric learning algorithm to find a Mahalanobis distance that is robust against adversarial perturbations. Experimental results show that the proposed metric learning algorithm improves both certified robust errors and empirical robust errors.
  arXiv  Detail & Related papers  (2020-06-12T09:17:08Z)
• A Practical Index Structure Supporting Fr\'echet Proximity Queries Among Trajectories [1.9335262420787858]
  We present a scalable approach for range and $k$ nearest neighbor queries under computationally expensive metrics. Based on clustering for metric indexes, we obtain a dynamic tree structure whose size is linear in the number of trajectories. We analyze the efficiency and effectiveness of our methods with extensive experiments on diverse synthetic and real-world data sets.
  arXiv  Detail & Related papers  (2020-05-28T04:12:43Z)
• Supervised Categorical Metric Learning with Schatten p-Norms [10.995886294197412]
  We propose a method, called CPML for emphcategorical projected metric learning, to address the problem of metric learning in categorical data. We make use of the Value Distance Metric to represent our data and propose new distances based on this representation. We then show how to efficiently learn new metrics.
  arXiv  Detail & Related papers  (2020-02-26T01:17:12Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.