Distances are pervasive in machine learning. They serve as similarity measures, loss functions, and learning targets; it is said that a good distance measure solves a task. When defining distances, the triangle inequality has proven to be a useful constraint, both theoretically-to prove convergence and optimality guaranteesand empirically-as an inductive bias. Deep metric learning architectures that respect the triangle inequality rely, almost exclusively, on Euclidean distance in the latent space. Though effective, this fails to model two broad classes of subadditive distances, common in graphs and reinforcement learning: asymmetric metrics, and metrics that cannot be embedded into Euclidean space. To address these problems, we introduce novel architectures that are guaranteed to satisfy the triangle inequality. We prove our architectures universally approximate norm-induced metrics on R n , and present a similar result for modified Input Convex Neural Networks. We show that our architectures outperform existing metric approaches when modeling graph distances and have a better inductive bias than non-metric approaches when training data is limited in the multi-goal reinforcement learning setting. Published as a conference paper at ICLR 2020 Blah Blah M1 (Non-negativity). d(x, y) ≥ 0. M2 (Definiteness). d(x, y) = 0 ⇐⇒ x = y. M3 (Subadditivity). d(x, z) ≤ d(x, y) + d(y, z). M4 (Symmetry). d(x, y) = d(y, x). Since we care mostly about the triangle inequality (M3), we relax other axioms and define a quasimetric as a function that is M1 and M3, but not necessarily M2 or M4. Given weighted graph G = (V, E) with non-negative weights, shortest path lengths define a quasi-metric between vertices. When X is a vector space (we assume over R), many common metrics, e.g., Euclidean and Manhattan distances, are induced by a norm. A norm is a function · : X → R satisfying, ∀x, y ∈ X , α ∈ R + : An asymmetric norm is N1-N3, but not necessarily N4. An (asymmetric) semi-norm is nonnegative, N2 and N3 (and N4), but not necessarily N1. We will use the fact that any asymmetric semi-norm · induces a quasi-metric using the rule, d(x, y) = x − y , and first construct models of asymmetric semi-norms. Any induced quasi-metric d is translation invariant-d(x, y) = d(x + z, y + z)-and positive homogeneous-d(αx, αy) = αd(x, y) for α ≥ 0. If · is symmetric (N4), so is d (M4). If · is N1, d is M2. Metrics that are not translation invariant (e.g., Bi et al. (2015) ) or positive homogeneous (e.g., our Neural Metrics in Section 3) cannot be induced by a norm. A convex function f : X → R is a function satisfying C1: ∀x, y ∈ X , α ∈ [0, 1]: f (αx+(1−α)y) ≤ αf (x) + (1 − α)f (y). The commonly used ReLU activation, relu(x) = max(0, x), is convex. It is easy to see that any N2 and N3 function is convex-thus, all asymmetric semi-norms are convex. This motivates modeling norms as constrained convex functions, using the following proposition. Proposition 1. All positive homogeneous convex functions are subadditive; i.e., C1 ∧ N2 ⇒ N3.
In REF , classes of neural networks are proposed to define pseudo-distances which satisfy the triangle inequality while not being necessarily symmetric.
An Inductive Bias for Distances: Neural Nets that Respect the Triangle Inequality
ArXiv
ArXiv
Mathematics Computer Science