Interpolated Discretized Embedding of Single Vectors and Vector Pairs for Classification, Metric Learning and Distance Approximation

Published on Aug 8, 2016in arXiv: Learning
Ofir Pele9
Estimated H-index: 9
Yakir Ben-Aliz1
Estimated H-index: 1
We propose a new embedding method for a single vector and for a pair of vectors. This embedding method enables: a) efficient classification and regression of functions of single vectors; b) efficient approximation of distance functions; and c) non-Euclidean, semimetric learning. To the best of our knowledge, this is the first work that enables learning any general, non-Euclidean, semimetrics. That is, our method is a universal semimetric learning and approximation method that can approximate any distance function with as high accuracy as needed with or without semimetric constraints. The project homepage including code is at: this http URL
  • References (32)
  • Citations (1)
📖 Papers frequently viewed together
2008ICML: International Conference on Machine Learning
7 Citations
152 Citations
78% of Scinapse members use related papers. After signing in, all features are FREE.
#1Wei YangH-Index: 1
#2Luhui XuH-Index: 1
Last. Yang LiuH-Index: 1
view all 5 authors...
Learning a proper distance metric for histogram data plays a crucial role in many computer vision tasks. The chi-squared distance is a nonlinear metric and is widely used to compare histograms. In this paper, we show how to learn a general form of chi-squared distance based on the nearest neighbor model. In our method, the margin of sample is first defined with respect to the nearest hits (nearest neighbors from the same class) and the nearest misses (nearest neighbors from the different classes...
5 CitationsSource
Sep 6, 2014 in ECCV (European Conference on Computer Vision)
#1Michaël Perrot (Jean Monnet University)H-Index: 3
#2Amaury Habrard (Jean Monnet University)H-Index: 19
Last. Marc Sebban (Jean Monnet University)H-Index: 19
view all 4 authors...
Having perceptual differences between scene colors is key in many computer vision applications such as image segmentation or visual salient region detection. Nevertheless, most of the times, we only have access to the rendered image colors, without any means to go back to the true scene colors. The main existing approaches propose either to compute a perceptual distance between the rendered image colors, or to estimate the scene colors from the rendered image colors and then to evaluate perceptu...
9 CitationsSource
#1Marco Cuturi (Kyoto University)H-Index: 27
#2David Avis (Kyoto University)H-Index: 29
Optimal transport distances have been used for more than a decade in machine learning to compare histograms of features. They have one parameter: the ground metric, which can be any metric between the features themselves. As is the case for all parameterized distances, optimal transport distances can only prove useful in practice when this parameter is carefully chosen. To date, the only option available to practitioners to set the ground metric parameter was to rely on a priori knowledge of the...
50 Citations
#1Brian Kulis (OSU: Ohio State University)H-Index: 30
The metric learning problem is concerned with learning a distance function tuned to a particular task, and has been shown to be useful when used in conjunction with nearest-neighbor methods and other techniques that rely on distances or similarities. This survey presents an overview of existing research in metric learning, including recent progress on scaling to high-dimensional feature spaces and to data sets with an extremely large number of data points. A goal of the survey is to present as u...
395 Citations
#1Aurélien Bellet (SC: University of Southern California)H-Index: 13
#2Amaury HabrardH-Index: 19
Last. Marc SebbanH-Index: 19
view all 3 authors...
The need for appropriate ways to measure the distance or similarity between data is ubiquitous in machine learning, pattern recognition and data mining, but handcrafting such good metrics for specific problems is generally difficult. This has led to the emergence of metric learning, which aims at automatically learning a metric from data and has attracted a lot of interest in machine learning and related fields for the past ten years. This survey paper proposes a systematic review of the metric ...
383 Citations
Jun 16, 2013 in ICML (International Conference on Machine Learning)
#1Ofir Pele (UPenn: University of Pennsylvania)H-Index: 9
#2Benjamin Taskar (UPenn: University of Pennsylvania)H-Index: 51
Last. Michael Werman (HUJI: Hebrew University of Jerusalem)H-Index: 33
view all 4 authors...
Linear classifiers are much faster to learn and test than non-linear ones. On the other hand, non-linear kernels offer improved performance, albeit at the increased cost of training kernel classifiers. To use non-linear mappings with efficient linear learning algorithms, explicit embeddings that approximate popular kernels have recently been proposed. However, the embedding process is often costly and the results are usually less accurate than kernel methods. In this work we propose a non-linear...
11 Citations
#1Subhransu Maji (Toyota)H-Index: 34
#2Alexander C. Berg (SBU: Stony Brook University)H-Index: 47
Last. Jitendra Malik (University of California, Berkeley)H-Index: 117
view all 3 authors...
We show that a class of nonlinear kernel SVMs admits approximate classifiers with runtime and memory complexity that is independent of the number of support vectors. This class of kernels, which we refer to as additive kernels, includes widely used kernels for histogram-based image comparison like intersection and chi-squared kernels. Additive kernel SVMs can offer significant improvements in accuracy over linear SVMs on a wide variety of tasks while having the same runtime, making them practica...
152 CitationsSource
Dec 3, 2012 in NeurIPS (Neural Information Processing Systems)
#1Søren Hauberg (MPG: Max Planck Society)H-Index: 16
#2Oren Freifeld (Brown University)H-Index: 14
Last. Michael J. Black (MPG: Max Planck Society)H-Index: 86
view all 3 authors...
Multi-metric learning techniques learn local metric tensors in different parts of a feature space. With such an approach, even simple classifiers can be competitive with the state-of-the-art because the distance measure locally adapts to the structure of the data. The learned distance measure is, however, non-metric, which has prevented multi-metric learning from generalizing to tasks such as dimensionality reduction and regression in a principled way. We prove that, with appropriate changes, mu...
45 Citations
Dec 3, 2012 in NeurIPS (Neural Information Processing Systems)
#1Dor Kedem (WashU: Washington University in St. Louis)H-Index: 2
#2Stephen Tyree (WashU: Washington University in St. Louis)H-Index: 18
Last. Kilian Q. Weinberger (WashU: Washington University in St. Louis)H-Index: 56
view all 5 authors...
In this paper, we introduce two novel metric learning algorithms, Χ2-LMNN and GB-LMNN, which are explicitly designed to be non-linear and easy-to-use. The two approaches achieve this goal in fundamentally different ways: Χ2-LMNN inherits the computational benefits of a linear mapping from linear metric learning, but uses a non-linear Χ2-distance to explicitly capture similarities within histogram data sets; GB-LMNN applies gradient-boosting to learn non-linear mappings directly in function space...
130 Citations
Oct 7, 2012 in ECCV (European Conference on Computer Vision)
#1Fan Wang (Stanford University)H-Index: 8
#2Leonidas J. Guibas (Stanford University)H-Index: 98
The Earth Mover's Distance (EMD) is an intuitive and natural distance metric for comparing two histograms or probability distributions. It provides a distance value as well as a flow-network indicating how the probability mass is optimally transported between the bins. In traditional EMD, the ground distance between the bins is pre-defined. Instead, we propose to jointly optimize the ground distance matrix and the EMD flow-network based on a partial ordering of histogram distances in an optimiza...
37 CitationsSource
Cited By1
#1Matthieu HeitzH-Index: 1
#2Nicolas BonneelH-Index: 16
Last. Gabriel Peyré ('ENS Paris': École Normale Supérieure)H-Index: 43
view all 5 authors...
Optimal transport (OT) distances between probability distributions are parameterized by the ground metric they use between observations. Their relevance for real-life applications strongly hinges on whether that ground metric parameter is suitably chosen. Selecting it adaptively and algorithmically from prior knowledge, the so-called ground metric learning GML) problem, has therefore appeared in various settings. We consider it in this paper when the learned metric is constrained to be a geodesi...