Umsetzung wissenschaftlicher Arbeiten: Erkenntnisse aus Elasticsearch und Lucene

Nahtlose Verbindung mit führenden KI- und Machine-Learning-Plattformen. Starten Sie eine kostenlose Cloud-Testversion, um die Funktionen der generativen KI von Elastic zu erkunden, oder testen Sie sie jetzt auf Ihrem Rechner.

Dieser Beitrag stellt Strategien zur Implementierung wissenschaftlicher Arbeiten in einer Softwareanwendung vor. Es greift auf Beispiele von Elasticsearch und Lucene zurück, um anderen Ingenieuren zu helfen, aus unseren Erfahrungen zu lernen. Sie lesen diese Strategien vielleicht und denken: „Aber das ist doch nur Softwareentwicklung!“ Und das wäre in der Tat richtig: Als Ingenieure verfügen wir bereits über die richtigen Vorgehensweisen und Werkzeuge, diese müssen lediglich an eine neue Herausforderung angepasst werden.

Hintergrund

Bei der Entwicklung von Elasticsearch stoßen wir gelegentlich auf wichtige Probleme, für die es keine einfache oder etablierte Lösungsmethode gibt. Es liegt nahe zu fragen: „Hmm, gibt es dazu eine wissenschaftliche Arbeit?“ Manchmal ist die akademische Arbeit auch eine Quelle der Inspiration. Wir stoßen auf eine wissenschaftliche Arbeit, in der ein neuer Algorithmus oder eine neue Datenstruktur vorgeschlagen wird, und denken: „Das wäre so nützlich!“ Hier sind nur einige Beispiele dafür, wie Elasticsearch und Apache Lucene akademische Arbeiten integrieren:

• HyperLogLog++ für Kardinalitätsaggregationen
• C3-Algorithmus zur adaptiven Replikaauswahl
• Hierarchische navigierbare Small-World-Graphen (HNSW) für die Suche nach dem nächsten Vektor in Lucene
• MIC-Statistik zur Verbesserung der Klassifizierung durch maschinelles Lernen
• Block-max WAND für schnelleres Abrufen von Top-Hits in Lucene
• ... und viele mehr

Wissenschaftliche Artikel sind eine unschätzbare Ressource für Ingenieure, die datenintensive Systeme entwickeln. Doch ihre Umsetzung kann einschüchternd und fehleranfällig sein – Algorithmenbeschreibungen sind oft komplex, und wichtige praktische Details werden ausgelassen. Und das Testen stellt eine echte Herausforderung dar: Wie können wir beispielsweise einen Algorithmus für maschinelles Lernen gründlich testen, dessen Ausgabe stark vom Datensatz abhängt?

Bewerten Sie das Dokument wie eine Softwareabhängigkeit.

Das Hinzufügen einer neuen Softwareabhängigkeit erfordert eine sorgfältige Prüfung: Wenn das andere Paket fehlerhaft, langsam oder unsicher ist, könnte unser Projekt es auch sein. Bevor Entwickler eine Abhängigkeit einbinden, stellen sie sicher, dass sie deren Qualität bewerten.

Das Gleiche gilt für wissenschaftliche Arbeiten, deren Umsetzung Sie erwägen. Man könnte meinen, dass ein Algorithmus, nur weil er in einer wissenschaftlichen Arbeit veröffentlicht wurde, korrekt sein und gut funktionieren muss. Doch selbst wenn eine wissenschaftliche Arbeit den Begutachtungsprozess durchlaufen hat, kann sie Mängel aufweisen. Vielleicht beruht der Korrektheitsbeweis auf Annahmen, die nicht realistisch sind. Oder vielleicht zeigt der Abschnitt „Experimente“ eine deutlich bessere Performance als die Basislinie, aber das gilt nur für einen bestimmten Datensatz. Auch wenn die Arbeit von hoher Qualität ist, passt ihr Ansatz möglicherweise nicht zu Ihrem Projekt.

Wenn man darüber nachdenkt, ob man eine Abhängigkeit von einer wissenschaftlichen Arbeit eingehen sollte, ist es hilfreich, dieselben Fragen zu stellen, die man auch bei einem Softwarepaket stellen würde:

• Ist die Bibliothek weit verbreitet und „praxiserprobt“? → Haben andere Softwarepakete diese Arbeit bereits umgesetzt und hat sie sich dabei bewährt?
• Sind Leistungsvergleichswerte verfügbar? Erscheinen diese Angaben zutreffend und fair? → Enthält die Arbeit realistische Experimente? Sind sie gut gestaltet?
• Ist die Leistungsverbesserung groß genug, um die Komplexität zu rechtfertigen? → Lässt sich die Arbeit mit einem soliden Basisansatz vergleichen? Um wie viel übertrifft es diesen Vergleichswert?
• Lässt sich dieser Ansatz gut in unser System integrieren? → Passen die Annahmen und Abwägungen des Algorithmus zu unserem Anwendungsfall?

Seltsamerweise schneidet die Software, die in einem Leistungsvergleich mit der Konkurrenz auftritt, immer am schnellsten ab! Wenn die Benchmarks von einem Dritten entworfen wurden, sind sie möglicherweise ausgewogener. Das gleiche Phänomen trifft auch auf wissenschaftliche Arbeiten zu. Wenn ein Algorithmus nicht nur in der Originalveröffentlichung gut abschneidet, sondern auch in anderen Veröffentlichungen als starke Basislinie auftaucht, dann ist er mit hoher Wahrscheinlichkeit solide.

Werden Sie kreativ beim Testen

Algorithmen aus wissenschaftlichen Artikeln weisen oft ein komplexeres Verhalten auf als die Algorithmen, denen wir im Alltag begegnen. Vielleicht handelt es sich um einen Näherungsalgorithmus, der Genauigkeit gegen höhere Geschwindigkeit eintauscht. Oder vielleicht handelt es sich um eine Methode des maschinellen Lernens, die einen großen Datensatz verarbeitet und (manchmal unerwartete) Ergebnisse liefert. Wie können wir Tests für diese Algorithmen schreiben, wenn wir ihr Verhalten nicht auf einfache Weise charakterisieren können?

Fokus auf Invarianten

Beim Entwerfen von Unit-Tests ist es üblich, in Beispielen zu denken: Wenn wir dem Algorithmus diese Beispieleingabe geben, sollte er diese Ausgabe haben. Leider deckt das Testen anhand von Beispielen das Verhalten der meisten mathematischen Algorithmen nicht ausreichend ab.

Betrachten wir den C3-Algorithmus, den Elasticsearch verwendet, um herauszufinden, welcher Knoten eine Suchanfrage bearbeiten soll. Es bewertet jeden Knoten anhand einer differenzierten Formel, die die bisherigen Service- und Antwortzeiten des Knotens sowie seine Warteschlangengröße berücksichtigt. Das Testen einiger Beispiele bestätigt nicht wirklich, dass wir die Formel richtig verstanden haben. Es hilft, einen Schritt zurückzutreten und über Testinvarianten nachzudenken: Verringert sich der Rang des Knotens, wenn sich die Bedienzeit erhöht? Wird der Rang, wie in der Studie behauptet, durch die Antwortzeit bestimmt, wenn die Warteschlangenlänge 0 beträgt?

Die Konzentration auf Invarianten kann in einer Reihe häufiger Fälle hilfreich sein:

• Soll die Methode unabhängig von der Reihenfolge sein? In diesem Fall sollte die Übergabe der Eingabedaten in einer anderen Reihenfolge zum gleichen Ergebnis führen.
• Erzeugt ein Schritt im Algorithmus Klassenwahrscheinlichkeiten? In diesem Fall müssten sich diese Wahrscheinlichkeiten zu 1 addieren.
• Ist die Funktion symmetrisch um den Ursprung? In diesem Fall sollte das Umkehren des Vorzeichens des Eingangssignals einfach das Vorzeichen des Ausgangssignals umkehren.

Bei der ersten Implementierung von C3 hatten wir einen Fehler in der Formel, bei dem wir versehentlich den Kehrwert der Antwortzeit anstelle der Antwortzeit verwendet haben. Das bedeutete, dass langsamere Knoten höher eingestuft werden konnten! Bei der Behebung des Problems haben wir darauf geachtet, Invariantenprüfungen einzubauen, um zukünftigen Fehlern vorzubeugen.

Vergleich mit einer Referenzimplementierung

Zusammen mit der Veröffentlichung des Artikels haben die Autoren hoffentlich auch eine Implementierung des Algorithmus veröffentlicht. (Dies ist besonders wahrscheinlich, wenn die Arbeit Experimente enthält, da viele Fachzeitschriften von den Autoren die Veröffentlichung des Codes zur Reproduktion der Ergebnisse verlangen.) Sie können Ihren Ansatz anhand dieser Referenzimplementierung testen, um sicherzustellen, dass Sie keine wichtigen Details des Algorithmus übersehen haben.

Während der Entwicklung der HNSW-Implementierung von Lucene für die Nächste-Nachbarn-Suche haben wir diese anhand einer Referenzbibliothek der Autoren des Artikels getestet . Wir haben sowohl Lucene als auch die Bibliothek mit demselben Datensatz ausgeführt und die Genauigkeit ihrer Ergebnisse sowie die Anzahl der durchgeführten Berechnungen verglichen. Wenn diese Zahlen annähernd übereinstimmen, wissen wir, dass Lucene den Algorithmus korrekt implementiert.

Bei der Integration eines Algorithmus in ein System müssen oft Modifikationen oder Erweiterungen vorgenommen werden, wie z. B. die Skalierung auf mehrere Kerne oder das Hinzufügen von Heuristiken zur Leistungsverbesserung. Am besten implementiert man zunächst eine „Standardversion“, testet sie anhand der Referenz und nimmt dann schrittweise Änderungen vor. So können Sie sicher sein, dass Sie alle wichtigen Aspekte erfasst haben, bevor Sie Anpassungen vornehmen.

Duell gegen einen bestehenden Algorithmus

Im letzten Abschnitt wird eine weitere Idee für eine Testinvariante vorgestellt: der Vergleich der Ausgabe des Algorithmus mit der Ausgabe eines einfacheren und besser verstandenen Algorithmus. Nehmen wir beispielsweise den Block-Max-WAND-Algorithmus in Lucene, der die Dokumentensuche beschleunigt, indem er Dokumente überspringt, die nicht in den Top-Ergebnissen erscheinen können. Es ist schwierig, genau zu beschreiben, wie sich block-max WAND in jedem Fall verhalten sollte, aber wir wissen, dass die Anwendung die Top-Ergebnisse nicht verändern sollte! Unsere Tests können also mehrere zufällige Suchanfragen generieren, diese dann sowohl mit als auch ohne WAND-Optimierung ausführen und überprüfen, ob ihre Ergebnisse immer übereinstimmen.

Ein wichtiger Aspekt dieser Tests ist, dass sie zufällige Eingaben generieren, mit denen der Vergleich durchgeführt wird. Dies kann dabei helfen, Fälle durchzuspielen, an die man sonst nicht gedacht hätte, und unerwartete Probleme aufzudecken. Beispielsweise hat der randomisierte Vergleichstest von Lucene für die BM25F-Bewertung dazu beigetragen , Fehler in subtilen Grenzfällen aufzudecken. Die Idee, einen Algorithmus mit zufälligen Eingaben zu füttern, ist eng mit dem Konzept des Fuzzing verwandt, einer gängigen Testmethode in der Computersicherheit.

Elasticsearch und Lucene verwenden diesen Testansatz häufig. Wenn Sie einen Test sehen, der ein "Duell" zwischen zwei Algorithmen erwähnt (TestDuelingAnalyzers, testDuelTermsQuery...), dann wissen Sie, dass diese Strategie zum Einsatz kommt.

Verwenden Sie die im Artikel verwendete Terminologie.

Wenn ein anderer Entwickler mit Ihrem Code arbeitet, muss er die Dokumentation konsultieren, um die Details zu verstehen. Der Kommentar zur HyperLogLog++-Implementierung von Elasticsearch bringt es gut auf den Punkt: „Der Versuch, die Funktionsweise dieser Klasse zu verstehen, ohne das zugehörige Paper gelesen zu haben, gilt als abenteuerlich.“ Dieser Methodenkommentar ist ebenfalls ein gutes Beispiel. Es enthält einen Link zur wissenschaftlichen Arbeit und hebt hervor, welche Änderungen am Algorithmus im Vergleich zur ursprünglichen Beschreibung vorgenommen wurden.

Da die Entwickler ihr Verständnis des Codes auf dem Papier aufbauen, ist es hilfreich, genau dieselbe Terminologie zu verwenden. Da die mathematische Notation kurz und bündig ist, kann dies zu Namen führen, die im Allgemeinen nicht als „guter Stil“ gelten würden, im Kontext der Arbeit aber sehr verständlich sind. Formeln aus wissenschaftlichen Arbeiten gehören zu den wenigen Fällen, in denen man in Elasticsearch auf kryptische Variablennamen wie rS und muBarSInverse stößt.

Die vom Autor empfohlene Art, einen wissenschaftlichen Artikel zu lesen: mit einer großen Tasse Kaffee.

Sie können dem Autor eine E-Mail schreiben.

Bei der Bearbeitung einer schwierigen Hausarbeit kann es vorkommen, dass man stundenlang über einer Formel grübelt und sich nicht sicher ist, ob man sie falsch verstanden hat oder ob es sich nur um einen Tippfehler handelt. Wenn es sich um ein Open-Source-Projekt handeln würde, könnten Sie eine Frage auf GitHub oder StackOverflow stellen. Aber wo kann man eine wissenschaftliche Arbeit finden? Die Autoren scheinen beschäftigt zu sein und könnten von Ihren E-Mails genervt sein.

Im Gegenteil, viele Akademiker freuen sich, wenn sie hören, dass ihre Ideen in die Praxis umgesetzt werden, und beantworten gerne Fragen per E-Mail. Wenn Sie an einem Produkt arbeiten, mit dem sie vertraut sind, listen sie die Anwendung möglicherweise sogar auf ihrer Website auf!

Es gibt auch einen wachsenden Trend unter Akademikern, wissenschaftliche Arbeiten öffentlich zu diskutieren und dabei viele der gleichen Werkzeuge wie in der Softwareentwicklung zu verwenden. Wenn zu einer Veröffentlichung ein Softwarepaket gehört, finden Sie möglicherweise Antworten auf häufig gestellte Fragen auf GitHub. In den Stack Exchange-Communities „Theoretical Computer Science“ und „Cross Validated“ finden sich auch detaillierte Diskussionen über populärwissenschaftliche Artikel. Einige Konferenzen haben damit begonnen, alle Paper-Reviews online zu veröffentlichen. Diese Rezensionen beinhalten einen Dialog mit den Autoren, der hilfreiche Einblicke in den Ansatz ermöglichen kann.

Fortgesetzt werden

Dieser Beitrag konzentriert sich auf die Grundlagen der Auswahl einer wissenschaftlichen Arbeit und

Die Implementierung erfolgt zwar korrekt, deckt aber nicht alle Aspekte der tatsächlichen Bereitstellung des Algorithmus ab. Wenn der Algorithmus beispielsweise nur eine Komponente in einem komplexen System ist, wie können wir sicherstellen, dass Änderungen an dieser Komponente zu Verbesserungen des gesamten Systems führen? Und was ist, wenn die Integration des Algorithmus wesentliche Änderungen oder Erweiterungen erfordert, die in der Originalveröffentlichung nicht behandelt werden? Dies sind wichtige Themen, über die wir in zukünftigen Beiträgen gerne mehr berichten werden.