On the Definiteness of Earth Mover's Distance and Its Relation to Set Intersection
Positive definite kernels are an important tool in machine learning that enable efficient solutions to otherwise difficult or intractable problems by implicitly linearizing the problem geometry. In this paper we develop a set-theoretic interpretation of the Earth Mover's Distance (EMD) and propose Earth Mover's Intersection (EMI), a positive definite analog to EMD for sets of different sizes. We provide conditions under which EMD or certain approximations to EMD are negative definite. We also present a positive-definite-preserving transformation that can be applied to any kernel and can also be used to derive positive definite EMD-based kernels and show that the Jaccard index is simply the result of this transformation. Finally, we evaluate kernels based on EMI and the proposed transformation versus EMD in various computer vision tasks and show that EMD is generally inferior even with indefinite kernel techniques.
Code (0)
등록된 구현이 없습니다.
Tasks
RelationSimilar Papers 제목 키워드 기반
Efficient Tracking of Sparse Signals via an Earth Mover's Distance Dynamics Regularizer
Tracking algorithms such as the Kalman filter aim to improve inference performance by leveraging the temporal dynamics in streaming observations. However, the tracking regularizers are often based on the $\ell_p$-norm wh…
Embedding Signals on Knowledge Graphs with Unbalanced Diffusion Earth Mover's Distance
In modern relational machine learning it is common to encounter large graphs that arise via interactions or similarities between observations in many domains. Further, in many cases the target entities for analysis are a…
Graph EmbeddingKnowledge Graph EmbeddingKnowledge GraphsEarth Mover's Distance Minimization for Unsupervised Bilingual Lexicon Induction
Cross-lingual natural language processing hinges on the premise that there exists invariance across languages. At the word level, researchers have identified such invariance in the word embedding semantic spaces of diffe…
Bilingual Lexicon InductionCross-Lingual TransferWord EmbeddingsSquared Earth Mover's Distance-based Loss for Training Deep Neural Networks
In the context of single-label classification, despite the huge success of deep learning, the commonly used cross-entropy loss function ignores the intricate inter-class relationships that often exist in real-life tasks …
Age ClassificationGeneral ClassificationMoverScore: Text Generation Evaluating with Contextualized Embeddings and Earth Mover Distance
A robust evaluation metric has a profound impact on the development of text generation systems. A desirable metric compares system output against references based on their semantics rather than surface forms. In this pap…
Data-to-Text GenerationImage CaptioningMachine TranslationText Generation+1