Kd-Trees rapides pour la divergence de Kullback-Leibler et d'autres divergences de Bregman décomposables

Les contributions de cet article englobent des résultats théoriques et d'implémentation. Tout d'abord, nous prouvons que les Kd-trees peuvent être étendus à ℝᵈ avec la distance mesurée par une divergence de Bregman arbitraire. Peut-être étonnamment, cela montre que l'inégalité triangulaire n'est pas nécessaire pour un élagage correct dans les Kd-trees. Deuxièmement, nous proposons un algorithme efficace et une implémentation en C++ pour la recherche de voisins les plus proches pour les divergences de Bregman décomposables. L'implémentation prend en charge la divergence de Kullback-Leibler (entropie relative) qui est une distance populaire entre les vecteurs de probabilité et est couramment utilisée en statistiques et en apprentissage automatique. Cela représente un pas vers l'élargissement de l'utilisation des algorithmes de géométrie computationnelle. Nos benchmarks montrent que notre implémentation gère efficacement à la fois les requêtes de voisins les plus proches exactes et approximatives. Comparé à une recherche linéaire, nous obtenons un gain de deux ordres de grandeur pour des scénarios pratiques dans des dimensions allant jusqu'à 100. Notre solution est plus simple et plus efficace que les méthodes concurrentes.