Первый номер «Трудов Института системного программирования РАН» в этом году открывает статья Игоря Буянова, Василия Ядринцева и Ильи Соченкова «Нейросетевые методы сжатия векторов для задачи приближенного поиска ближайших соседей» (ссылка). Соседей 73 отдел ФИЦ ИУ РАН ищет уже давно, как минимум с 2019 года; на прошлогодней DAMDID, например, Илья с Василием предлагали использовать автокодировщики для улучшения поиска на больших датасетах. Заранее просим не беспокоиться их соседей по дому/участку: поиск ближайшего соседа (Nearest Neighbor Search) охватывает исключительно метрическое пространство, задачи классификации и кластеризации, а приближённый поиск ближайших соседей (Approximate Nearest Neighbor) применяется в системах рекомендаций, компьютерном зрении и т. п.
Там, где точные алгоритмы поиска вычислительно затратны и непрактичными для больших наборов данных. Поиск приближённых алгоритмов требует построения дерева или графа для эффективного сужения пространства поиска и избегания проверки всех возможных кандидатов, либо тестирования методов сжатия векторов. Но общая размерность векторов варьируется от сотен до нескольких тысяч, что чревато завышенными требованиями к размеру хранилища и оперативной памяти. Что делать? Авторы решились исследовать нейронные сети с архитектурой автокодировщика в качестве компрессора векторов для поиска ближайших соседей, несмотря на их высокие вычислительные затраты. Ради чего провели обширные тесты различных методов с использованием нескольких автокодировщиков на нескольких наборах данных.
Команда воспользовалась реализациями индексов из библиотеки Faiss, где тестовые случаи используют автокодировщик в сочетании с индексом и/или квантования из Faiss либо используют только компоненты Faiss. В качестве индексов были задействованы Flat, IVFPQ, HNSW и NSG, а в качестве автокодировщиков — варианты Vanilla, которые лучше сохраняют геометрию пространства при сжатии. Эксперименты проводились на синтетически сгенерированных данных с известной внутренней размерностью и показали, что использование кодировщиков в некоторых случаях позволяет сохранить вектор меньшей размерности с уверенностью, что выбранная метрика качества сохраняет тот же уровень. За подробностями отсылаем к материалу, поддержанному грантом Фонда содействия инновациям в рамках проекта открытой библиотеки ExactusVectorIndex (ссылка) — о ней мы тоже писали в репортаже с Вечера памяти Геннадия Осипова.