An Inductive Bias for Distances: Neural Nets that Respect the Triangle\n Inequality

2020/02/13 by Silviu Pitis, Harris Chan, Pitis, Silviu +5 · 4 citations
Computer Science · #Advanced Graph Neural Networks #Domain Adaptation and Few-Shot Learning #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and ELM

paper · pdf · doi:10.48550/arxiv.2002.05825

openalex publication_date 2020/02/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Distances are pervasive in machine learning. They serve as similarity\nmeasures, loss functions, and learning targets; it is said that a good distance\nmeasure solves a task. When defining distances, the triangle inequality has\nproven to be a useful constraint, both theoretically--to prove convergence and\noptimality guarantees--and empirically--as an inductive bias. Deep metric\nlearning architectures that respect the triangle inequality rely, almost\nexclusively, on Euclidean distance in the latent space. Though effective, this\nfails to model two broad classes of subadditive distances, common in graphs and\nreinforcement learning: asymmetric metrics, and metrics that cannot be embedded\ninto Euclidean space. To address these problems, we introduce novel\narchitectures that are guaranteed to satisfy the triangle inequality. We prove\nour architectures universally approximate norm-induced metrics on\n\ℝⁿ, and present a similar result for modified Input Convex Neural\nNetworks. We show that our architectures outperform existing metric approaches\nwhen modeling graph distances and have a better inductive bias than non-metric\napproaches when training data is limited in the multi-goal reinforcement\nlearning setting.\n

Citations

• Nearest neighbor pattern classification
• Artificial intelligence: a modern approach
• Prototypical Networks for Few-shot Learning
• Multi-Goal Reinforcement Learning: Challenging Robotics Environments and\n Request for Research
• On Evaluation of Embodied Navigation Agents

Cited by

• Goal Reaching with Eikonal-Constrained Hierarchical Quasimetric Reinforcement Learning
• Multistep Quasimetric Learning for Scalable Goal-conditioned Reinforcement Learning
• Learning The Minimum Action Distance
• Offline Goal-Conditioned Reinforcement Learning with Projective Quasimetric Planning

Related

• Neural Networks Learn Distance Metrics
• Towards Certified Robustness of Distance Metric Learning
• Neural Bregman Divergences for Distance Learning
• A Tutorial on Distance Metric Learning: Mathematical Foundations, Algorithms, Experimental Analysis, Prospects and Challenges (with Appendices on Mathematical Background and Detailed Algorithms Explanation)
• Neural Networks Use Distance Metrics