Bias, Effizienz und Hubness: Herausforderungen in der Anwendbarkeit von Metriken

Abstract

Metriken spiegeln die Ähnlichkeiten bzw. Unterschied zwischen Objekten in Merkmal- räumen wider. Es gibt in dieser Hinsicht drei Hauptprobleme: Erstens existieren hunderte von Me- triken, die verschiedene Aspekte der Ähnlichkeit berücksichtigen, was den Bedarf an einer formalen Auswahlmethodik für Metriken motiviert. Für dieses Problem präsentieren wir eine detaillierte Analyse von 20 Metriken und präsentieren eine neue formale Methode für Metrikauswahl vor. Zweitens gibt es rechenintensive Metriken, deren ineffiziente Laufzeit in Verbindung mit großen Objekten ein Problem darstellt. Wir schlagen einen neuen beinahe zeit-linearen Algorithmus zur Be- rechnung der exakten Hausdorff-Distanz zwischen beliebigen Punktwolken vor. Drittens taucht in hoch-dimensionalen Featurespaces eine Kategorie von Schwierigkeiten auf, die als curse of dimensionality bekannt ist. Eine dieser Schwierigkeiten ist Hubness. Wir präsentieren eine neue Erklärung für die Ursache von Hubness, die auf einem neuen Modell der Distanzstruktur in hoch dimensionalen Datenräumen beruht. Auf Grundlage dieser Erklärung leiten wir einen Schätzer für Hubness ab, bzw. schlagen wir Verfahren zur Verringerung von Hubness vor.