Seminar Ähnlichkeitssuche in großen Datenmengen

In diesem Seminar wollen wir uns mit der Ähnlichkeitssuche in (hochdimensionalen) Daten beschäftigen. Anwendung findet dies beispielsweise in aktuellen Sprachmodellen wie dem Retrieval-Enhanced Transformer (RETRO) von Google/Deepmind, Implementierungen dazu finden sich bspw. in der FAISS Bibliothek von Facebook/Meta. Eine aktuell wichtige Technik ist der Index Scalable Nearest Neighbors (SCANN) von Google, Amazon hat eine eigene Technik mit dem Namen FINGER veröffentlicht.

Die Integration von Ähnlichkeitssuche in moderne Sprachmodelle (bspw. ChatGPT) verspricht dabei gleich zwei deren größten Probleme zu lösen: die aktuellen Sprachmodelle halluzinieren, weil sie kein "Verständnis" für Fakten haben, sondern rein oberflächlich Text auf syntaktische Plausibilität optimieren, und sie sind so aufwändig zu trainieren, dass man sie nur langsam an aktuelle Informationen anpassen kann. Daher kann ChatGPT beispielsweise keine Fragen zum Ukraine-Krieg beantworten. Mit Hilfe von Retrieval-Ansätzen, bei denen das Sprachmodell zur Eingabe relevante Quellen als zusätzliche Eingabe bekommt, hofft man hier sowohl eine bessere Faktentreue zu erreichen (weil Suchergebnisse von dem Modell als Fakten verarbeitet werden können), als auch dem Modell ohne Neutraining Zugriff auf aktuelle Informationen geben zu können.

Lernziele

Sie beschäftigen sich in diesem Seminar intensiv mit aktueller wissenschaftlicher Literatur, arbeiten sich selbständig in den Kontext ein, und präsentieren ihre Rechercheergebnisse in einem Vortrag sowie in einer schriftlichen Ausarbeitung.

Literatur und Themen

Unter anderem:

• Azizi, Ilias, Karima Echihabi, and Themis Palpana. "ELPIS: Graph-Based Similarity Search for Scalable Data Science." PVLDB, 16(6): 1548 - 1559, 2023. doi:10.14778/3583140.3583166
• Chen, Patrick H., et al. (Amazon) "FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor Search." arXiv preprint arXiv:2206.11408 (2022).
• Hyvönen, Ville, Elias Jääsaari, and Teemu Roos. "A Multilabel Classification Framework for Approximate Nearest Neighbor Search." Advances in Neural Information Processing Systems 35 (2022): 35741-35754.
• Pham, Ninh, and Tao Liu. "Falconn++: A Locality-sensitive Filtering Approach for Approximate Nearest Neighbor Search." Neural Information Processing Systems (NeurIPS), (2022).
• Borgeaud, Sebastian, et al. "Improving language models by retrieving from trillions of tokens." International conference on machine learning. PMLR, 2022.
• Guo, Ruiqi, et al. (Google) "Accelerating large-scale inference with anisotropic vector quantization." International Conference on Machine Learning. PMLR, 2020.
• Johnson, Jeff, Matthijs Douze, and Hervé Jégou (Facebook AI). "Billion-scale similarity search with GPUs." IEEE Transactions on Big Data 7.3 (2019): 535-547.
• Jayaram Subramanya, Suhas, et al. (Microsoft) "DiskANN: Fast accurate billion-point nearest neighbor search on a single node." Advances in Neural Information Processing Systems 32 (2019).
• Douze, Matthijs, Alexandre Sablayrolles, and Hervé Jégou. "Link and code: Fast indexing with graphs and compact regression codes." Proceedings of the IEEE conference on computer vision and pattern recognition. 2018.
• Malkov, Yu A., and Dmitry A. Yashunin. "Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs." IEEE transactions on pattern analysis and machine intelligence 42.4 (2018): 824-836.
• Hyvönen, Ville, et al. "Fast nearest neighbor search through sparse random projections and voting." 2016 IEEE International Conference on Big Data (Big Data). IEEE, 2016.
• Santoyo, Francisco, Edgar Chávez, and Eric S. Téllez. "A compressed index for hamming distances." Similarity Search and Applications: 7th International Conference, SISAP 2014, Los Cabos, Mexico, October 29-31, 2014. Proceedings 7. Springer International Publishing, 2014.
• Dasgupta, S., & Sinha, K. (2013, June). Randomized partition trees for exact nearest neighbor search. In Conference on learning theory (pp. 317-337). PMLR.
• Dong, Wei, Charikar Moses, and Kai Li. "Efficient k-nearest neighbor graph construction for generic similarity measures." Proceedings of the 20th international conference on World wide web. 2011.
• Jegou, Herve, Matthijs Douze, and Cordelia Schmid. "Product quantization for nearest neighbor search." IEEE transactions on pattern analysis and machine intelligence 33.1 (2010): 117-128.
• Muja, Marius, and David G. Lowe. "Fast approximate nearest neighbors with automatic algorithm configuration." VISAPP (1) 2.331-340 (2009): 2.
• Dasgupta, Sanjoy, and Yoav Freund. "Random projection trees for vector quantization." IEEE Transactions on Information Theory 55.7 (2009): 3229-3242.

Struktur und Ablauf

Termine werden noch festgesetzt!

Das Seminar besteht aus folgenden Komponenten:

• Vorbesprechung und Themenvergabe
• Entwurf des Vortrags
• Peer-Feedback dazu
• Präsentationen
• Entwurf der Ausarbeitung
• Peer-Feedback dazu
• Abgabe der schriftlichen Ausarbeitung

Bewertung

Die Abschluss-Note setzt sich wie folgt zusammen:

• 25% der Note für die Vorträge
• 25% der Note für die Mitarbeit im Seminar (inkl. peer review)
• 50% der Note für die schriftliche Ausarbeitung

Hilfsmittel

Primär sollen Sie mit den (wissenschaftlichen) Originalquellen arbeiten.

Die Verwendung von ChatGPT ist nicht ausgeschlossen, aber keinesfalls empfohlen, da ChatGPT in der Regel nicht die nötige Faktentreue erreicht. Es gibt zahlreiche Beispiele wo GPT Fakten ebenso wie Quellen "halluziniert". Daher müssten Sie die erzeugten Passagen genau prüfen, und Fehler ebenso wie Plagiate in diesen Passagen selbst verantworten! Durch ChatGPT erzeugte Passagen sind in der Regel als Internetquelle kenntlich zu machen und mit Datum/Version und Prompt zu kennzeichnen. Wenn Sie urheberrechtlich geschütztes Material in ChatGPT eingeben begehen Sie ggf. eine Urheberrechtsverletzung, und es entbindet Sie nicht davon, die Originalquellen zu zitieren, da es sich immer noch um Paraphrasen handeln kann. Der Einsatz von KI nur zur Rechtschreib- und Grammatikkorrektur stell hingegen kein Problem dar.

Für genauere Fragen zum Einsatz von ChatGPT finden Sie Einschätzungen in einem aktuellen Gutachten zum Einsatz von KI in der Hochschulbildung.