Comparison-based methods in machine learning

Abstract

Diese Dissertation befasst sich mit der Entwicklung und Analyse von Algorithmen in einem neuen Ansatz des maschinellen Lernens, den wir „vergleichbasiertes“ Lernen nennen. In den letzten Jahrzehnten gab es eine Fülle von Methoden und Analysen für Datensätze, die entweder eine euklidische Darstellung oder eine Distanz zwischen den Objekten besitzen. Im Gegensatz zu dieser traditionellen Herangehensweise betrachten wir den Fall, wenn keine euklidische Darstellung der Objekte gegeben ist. Wir sagen, dass im Allgemeinen die Objekte aus einem beliebigen metrischen Raum (X,δ) stammen. Wir haben allerdings keinen direkten Zugriff auf die Metrik δ, und können lediglich von einem Orakel einen Tripletvergleich abfragen: „Ist das Objekt x näher an Objekt y oder an Objekt z?“. Wir nehmen an, dass das Orakel auf diese Weise den folgenden Vergleich entscheidet: δ(x,y)>δ(x,z). In der Einführung in Kapitel 1 gehen wir auf die verschiedenen Aspekte des vergleichbasierten Lernens ein. Wie wichtig und nützlich vergleichsbasierte Methoden sind, zeigen wir anhand mehrerer Anwendungsfälle. Außerdem geben wir ein intuitives Beispiel für eine Machine Learning-Aufgabe, die mit Tripletvergleichen durchgeführt wird. Wir diskutieren die wenigen bisherigen Ansätze, vergleichsbasiertes maschinelles Lernen durchzuführen. Diese Arbeit ist in zwei Teile aufgeteilt. Im ersten Teil, den Kapiteln 2 und 3, befassen wir uns mit der Entwicklung und Analyse von Algorithmen, die klassische Aufgaben des maschinellen Lernens durchführen, wobei nur die Antworten auf die Tripletvergleiche verwendet werden. In Kapitel 2 schlagen wir eine Baumstruktur für die Suche nach dem nächsten Nachbarn vor, wobei nur Tripletvergleiche verwendet werden. Wir beweisen, dass, wenn der metrische Raum bestimmte Expansionsbedingungen erfüllt, die Höhe des Baumes mit hoher Wahrscheinlichkeit logarithmisch in der Anzahl der Eingabeelemente ist, was zu einer effizienten Suchleistung führt. Wir liefern auch eine obere Schranke für die Wahrscheinlichkeit, den falschen nächsten Nachbarn zurückzugeben. Kapitel 3 erweitert die Idee dieses Suchbaumes auf den Bau mehrerer Bäume als Random Forests für Klassifizierungs-/Regressionsprobleme. Wir beweisen die Konsistenz einer vereinfachten Version der Bäume, die zur Konsistenz des Random Forest führt. Darüber hinaus zeigen wir die erwünschte Leistung des vorgeschlagenen Random Forests durch umfassende Experimente in verschiedenen Szenarios. Im zweiten Teil der Arbeit, den Kapiteln 4 und 5, wenden wir den vergleichsbasierten Ansatz auf das Skalierungsproblem in der Psychophysik an. Das Ziel der psychophysikalischen Skalierung ist es, die funktionelle Beziehung zwischen einem physischen Reiz und der Wahrnehmung desselben Reizes für einen menschlichen Beobachter zu finden. Tatsächlich ist das relative Feedback in Form von Tripletvergleichen in der Psychophysik nicht neu. Die vorgeschlagenen Ansätze zur Nutzung der Tripletvergleiche sind in der psychophysikalischen Literatur jedoch sehr begrenzt. In Kapitel 4 wenden wir ordinale Einbettungsmethoden, die in der Literatur des maschinellen Lernens vorgeschlagen werden, auf das Skalierungsproblem der Psychophysik an. Wir demonstrieren die erwünschte Performance der ordinalen Einbettungen mit Hilfe umfangreicher Simulationen und eines realen psychophysikalischen Experimentes. Kapitel 5 untersucht das Potenzial von Crowdsourcing-Plattformen für psychophysikalische Skalierungsaufgaben in einem vergleichsbasierten Szenario. Traditionell werden die Experimente der Psychophysik unter gut kontrollierten Laborbedingungen durchgeführt. Wir führen ein repräsentatives Experiment der Psychophysik sowohl in unserem Psychophysik-Labor als auch auf der Mechanical Turk (MTurk) Plattform von Amazon durch. Wir vergleichen die Qualität der gesammelten Tripletvergleiche aus dem Labor und der MTurk-Plattform. Die Ergebnisse zeigen, dass die MTurk-Plattform Daten produziert, die eine etwas geringere – aber akzeptable – Qualität aufweisen.

This thesis focuses on developing and analyzing novel algorithms for a new setting of machine learning, which we call the “comparison-based” setting. There has been a plethora of methods and analysis over the last decades concerning machine learning tasks for datasets that either have a Euclidean representation or a distance/dissimilarity matrix between pairs of items in the dataset. In contrast to this traditional setting, we consider the setting in which no Euclidean representation of the items is available. We consider a general setting where items come from an arbitrary metric space(X,δ). We have no access to the metric function δ, however, we can ask an oracle triplet comparisons of the form: “Is item x closer to item y or to item z?” This implies that the oracle can make a judgment on the following distance comparison: δ(x,y) > δ(x,z).In Chapter 1, the introductory chapter, we elaborate on various aspects of the comparison-based setting. We emphasize on the importance and usefulness of the comparison-based methods, by enumerating numerous applications. We also provide an intuitive example of a machine learning task performed with triplet comparisons. We briefly discuss the few existing approaches to perform machine learning in the comparison-based setting. The contributions of the thesis are arranged in two parts. In the first part, Chapters 2and 3, we are concerned with the development and analysis of algorithms which per-form common machine learning tasks using only the answers to triplet comparisons. In Chapter 2, we propose a tree structure for the nearest neighbor search problem,using only triplet comparisons. We prove that if the metric space satisfies certain expansion conditions, then with high probability the height of the tree is logarithmic in the number of input items, leading to efficient search performance. We also provide an upper bound for the failure probability to return the true nearest neighbor. Chapter 3 extends the idea of constructing trees for nearest neighbor search to building an ensemble of trees as random forests for classification/regression tasks. We prove the consistency of a simplified version of the proposed trees leading to the consistency of the random forest. In addition, we demonstrate the desirable performance of the proposed random forest through comprehensive experiments in different settings. In the second part of the thesis, Chapters 4 and 5, we apply the comparison-based approach to the scaling problem in psychophysics. The goal of psychophysical scaling is to find the functional relation between a physical stimulus and the perception of a human observer. The relative feedback in the form of triplet comparisons is not new in psychophysics. However, the approaches based on triplet comparisons are very limited in the psychophysics literature. In Chapter 4, we apply ordinal embedding methods, proposed in the machine learning literature, to psychophysical scaling. We demonstrate the satisfactory performance of ordinal embedding using extensive simulations and a real-world psychophysical scaling experiment. Chapter 5 examines the potential capability of crowdsourcing platforms for psychophysical scaling tasks using the comparison-based setting. Traditionally, the experiments of psychophysics are conducted in well-controlled Lab conditions. We run a representative experiment of psychophysics in both our psychophysics Lab and Amazon’s Mechanical Turk (MTurk) platform. We compare the quality of the collected triplet comparisons from the Lab and the MTurk platform. The results show that the MTurk platform produces data which has slightly lower — however acceptable — quality.