Mesure de similarité

Résumé

En mathématiques et en informatique théorique, une mesure de similarité, plus exactement une mesure de distance entre mots, est une façon de représenter par un nombre la différence entre deux mots, ou plus généralement deux chaînes de caractères. Cela permet de comparer des mots ou chaines de façon simple et pratique. C'est donc une forme de distance mathématique et de métrique pour les chaînes de caractères. En programmation, la mesure la plus simple et la plus courante est la distance de Levenshtein : elle est obtenue en comptant le nombre de modification de caractères individuels (ajout, retrait, ou changement) pour passer d'une chaîne à l'autre. Elle est utilisée dans la recherche approximative ou la comparaison de chaînes, aussi appelée en anglais fuzzy string searching. Définition Pour qu'une mesure de similarité soit une métrique de chaînes de caractères, elle doit satisfaire l'inégalité triangulaire. Le résultat fourni par une métrique est un nombre qui est une

Source officielle

https://fr.wikipedia.org/wiki/Mesure_de_similarit%C3%A9

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (9)

Chargement

Afficher plus

Publications associées

Chargement

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés (5)

Concepts associés

Chargement

Cours associés (6)

Cours associés

Chargement

Séances de cours associées (7)

Séances de cours associées

Chargement

Publications associées (9)

Complexity and Similarity Metrics for Unsupervised Identification of Programming Methods for Robot Cooking Tasks

Josephine Anna Eleanor Hughes, Stefan Ilic

Springer2022

Chargement

The (h, k)-Server Problem on Bounded Depth Trees

Marek Elias

We study the k-server problem in the resource augmentation setting, i.e., when the performance of the online algorithm with k servers is compared to the offline optimal solution with h 0. Surprisingly, however, no o(h)-competitive algorithm is known even for HSTs of depth 2 and even when k/h is arbitrarily large. We obtain several new results for the problem. First, we show that the known k-server algorithms do not work even on very simple metrics. In particular, the Double Coverage algorithm has competitive ratio Omega(h) irrespective of the value of k, even for depth-2 HSTs. Similarly, the Work Function Algorithm, which is believed to be optimal for all metric spaces when k = h, has competitive ratio Omega(h) on depth-3 HSTs even if k = 2h. Our main result is a new algorithm that is O(1)-competitive for constant depth trees, whenever k = (1 + epsilon)h for any epsilon > 0. Finally, we give a general lower bound that any deterministic online algorithm has competitive ratio at least 2.4 even for depth-2 HSTs and when k/h is arbitrarily large. This gives a surprising qualitative separation between uniform metrics and depth-2 HSTs for the (h, k)-server problem.

ASSOC COMPUTING MACHINERY2019

Chargement

Interpretable Social Anchors for Human Trajectory Forecasting in Crowds

Alexandre Massoud Alahi, Parth Ashit Kothari, Brian Alan Sifringer

Human trajectory forecasting in crowds, at its core, is a sequence prediction problem with specific challenges of capturing inter-sequence dependencies (social interactions) and consequently predicting socially-compliant multimodal distributions. In recent years, neural network-based methods have been shown to outperform hand-crafted methods on distance-based metrics. However, these data-driven methods still suffer from one crucial limitation: lack of interpretability. To overcome this limitation, we leverage the power of discrete choice models to learn interpretable rule-based intents, and subsequently utilise the expressibility of neural networks to model scene-specific residual. Extensive experimentation on the interaction-centric benchmark TrajNet++ demonstrates the effectiveness of our proposed architecture to explain its predictions without compromising the accuracy.

2021

Chargement

Afficher plus