Платформа Shop'n'SEO предлагает перевод статьи, напечатанной в блоге Google.
Мы представляем MUVERA — современный алгоритм поиска, который сводит сложный многовекторный поиск к поиску максимального внутреннего произведения с одним вектором.
Модели нейронного встраивания стали краеугольным камнем современного информационного поиска (ИИ). При запросе пользователя (например, «Какова высота горы Эверест?») целью ИИ является поиск информации, релевантной запросу, из очень большой коллекции данных (например, миллиардов документов, изображений или видео в Интернете). Модели встраивания преобразуют каждую точку данных в одновекторное «встраивание», так что семантически похожие точки данных преобразуются в математически похожие векторы. Встраивания обычно сравниваются с помощью сходства внутреннего продукта , что обеспечивает эффективный поиск с помощью оптимизированных алгоритмов поиска максимального внутреннего продукта (MIPS). Однако недавние достижения, в частности, введение многовекторных моделей, таких как ColBERT , продемонстрировали значительное улучшение производительности в задачах ИИ.
В отличие от одновекторных вложений, многовекторные модели представляют каждую точку данных с помощью набора вложений и используют более сложные функции подобия, которые могут захватывать более богатые связи между точками данных. Например, популярная мера подобия Chamfer, используемая в современных многовекторных моделях, фиксирует, когда информация в одном многовекторном вложении содержится в другом многовекторном вложении. Хотя этот многовекторный подход повышает точность и позволяет извлекать более релевантные документы, он вносит существенные вычислительные проблемы. В частности, возросшее количество вложений и сложность оценки многовекторного подобия делают извлечение значительно более дорогим.
В статье «MUVERA: Multi-Vector Retrieval via Fixed Dimensional Encodings» мы представляем новый алгоритм многовекторного поиска, разработанный для преодоления разрыва в эффективности между одно- и многовекторным поиском. Мы преобразуем многовекторный поиск в более простую задачу, создавая фиксированные размерные кодировки (FDE) запросов и документов, которые представляют собой отдельные векторы, внутренний продукт которых приближается к многовекторному сходству, тем самым сводя сложный многовекторный поиск обратно к одновекторному поиску максимального внутреннего продукта (MIPS). Этот новый подход позволяет нам использовать высокооптимизированные алгоритмы MIPS для получения начального набора кандидатов, которые затем могут быть повторно ранжированы с точным многовекторным сходством, тем самым обеспечивая эффективный многовекторный поиск без ущерба для точности. Мы предоставили реализацию нашего алгоритма построения FDE с открытым исходным кодом на GitHub .
Проблема многовекторного поиска
Многовекторные модели генерируют несколько внедрений на запрос или документ, часто одно внедрение на токен. Обычно вычисляется сходство между запросом и документом с помощью сопоставления Chamfer, которое измеряет максимальное сходство между каждым внедрением запроса и ближайшим внедрением документа , а затем суммирует эти сходства по всем векторам запроса (стандартный метод вычисления многовекторного сходства). Таким образом, сходство Chamfer обеспечивает «целостную» меру того, как каждая часть запроса соотносится с некоторой частью документа.
Хотя многовекторные представления обладают такими преимуществами, как улучшенная интерпретируемость и обобщение, они создают значительные проблемы при поиске:
- Увеличение объема внедрений: генерация внедрений на токен значительно увеличивает количество обрабатываемых внедрений.
- Сложная и требующая больших вычислительных ресурсов оценка сходства: сопоставление фасок — это нелинейная операция, требующая матричного произведения, что обходится дороже, чем простое векторное скалярное произведение .
- Отсутствие эффективных методов сублинейного поиска: Одновекторный поиск выигрывает от высокооптимизированных алгоритмов (например, основанных на разбиении пространства ), которые одновременно достигают высокой точности и сублинейного времени поиска, избегая исчерпывающих сравнений. Сложная природа многовекторного сходства препятствует прямому применению этих быстрых геометрических методов, затрудняя эффективный поиск в масштабе.
К сожалению, традиционные одновекторные алгоритмы MIPS не могут быть напрямую применены к многовекторному поиску — например, документ может иметь токен с высокой степенью сходства с токеном одного запроса, но в целом документ может быть не очень релевантным. Эта проблема требует более сложных и ресурсоемких методов поиска.
MUVERA: Решение с фиксированными размерными кодировками
MUVERA предлагает элегантное решение, сводя многовекторный поиск сходства к одновекторному MIPS, чтобы сделать поиск по сложным многовекторным данным намного быстрее. Представьте, что у вас есть большой набор данных «многовекторных наборов» (т. е. наборов векторов), где каждый набор описывает некоторую точку данных, но поиск по каждому из этих наборов медленный. Хитрость MUVERA заключается в том, чтобы взять всю эту группу многовекторов и сжать их в один, более простой в обращении вектор, который мы называем фиксированным размерным кодированием (FDE). Ключевой частью является то, что если вы сравните эти упрощенные FDE, их сравнение близко соответствует тому, что вы получили бы, если бы сравнили исходные, более сложные многовекторные наборы. Это позволяет нам использовать гораздо более быстрые методы поиска, разработанные для отдельных векторов.
Вот упрощенное описание того, как работает MUVERA:
- Генерация FDE: MUVERA использует отображения для преобразования многовекторных наборов запросов и документов в FDE. Эти отображения предназначены для захвата существенной информации о сходстве в векторе фиксированной длины.
- Поиск на основе MIPS: FDE документов индексируются с использованием стандартного решателя MIPS. При наличии запроса вычисляется его FDE, и решатель MIPS эффективно извлекает наиболее похожие FDE документов.
- Повторное ранжирование: исходные кандидаты, извлеченные MIPS, повторно ранжируются с использованием исходного сходства Chamfer для повышения точности.
Ключевым преимуществом MUVERA является то, что преобразование FDE не обращает внимания на данные. Это означает, что оно не зависит от конкретного набора данных, что делает его одновременно устойчивым к изменениям в распределении данных и подходящим для потоковых приложений. Кроме того, в отличие от одиночных векторов, созданных моделью, FDE гарантированно приближают истинное сходство Chamfer с точностью до указанной ошибки. Таким образом, после этапа повторного ранжирования MUVERA гарантированно найдет наиболее похожие многовекторные представления.
Иллюстрация построения FDE-запросов. Каждый токен (показанный как слово в этом примере) отображается в вектор высокой размерности (2-D в примере для простоты). Пространство высокой размерности случайным образом разбивается на гиперплоскостные разрезы. Каждой части пространства назначается блок координат в выходном FDE, который устанавливается в сумму координат векторов запроса, которые попадают в эту часть.
Иллюстрация построения FDE документа. Построение такое же, как и построение запроса, за исключением того, что векторы, попадающие в заданную часть разделенного пространства, усредняются вместе, а не суммируются, что точно отражает асимметричную природу сходства Chamfer.
Теоретические основы
Наш подход вдохновлен методами, используемыми в вероятностных вложениях деревьев , мощном инструменте в теории геометрических алгоритмов. Однако мы адаптируем эти методы для работы со внутренними произведениями и сходством Chamfer.
Основная идея генерации FDE заключается в разбиении пространства встраивания на секции (показано на рисунке выше). Если похожие векторы из запроса и документа попадают в одну и ту же секцию, мы можем эффективно аппроксимировать их сходство. Однако, поскольку мы заранее не знаем оптимального соответствия между векторами запроса и документа, мы используем рандомизированную схему разбиения.
Мы также предоставляем теоретические гарантии для MUVERA, доказывая, что FDE предлагают сильную аппроксимацию сходства Chamfer (подробнее в статье ). Это важный результат, поскольку он обеспечивает принципиальный способ выполнения многовекторного поиска с использованием одновекторных прокси с доказуемой точностью.
Экспериментальные результаты
Мы оценили MUVERA на нескольких наборах данных поиска информации из бенчмарков BEIR . Наши эксперименты показывают, что MUVERA последовательно достигает высокой точности поиска со значительно сокращенной задержкой по сравнению с предыдущим передовым методом, известным как PLAID .
Наши основные выводы включают в себя:
Улучшенный отзыв: MUVERA превосходит эвристику с одним вектором, распространенный подход, используемый в многовекторном поиске (который также использует PLAID), достигая лучшего отзыва, при этом извлекая значительно меньше документов-кандидатов (показано на рисунке ниже). Например, FDE извлекают в 5–20 раз меньше кандидатов, чтобы достичь фиксированного отзыва.
Вспомните фиксированные размерные кодировки (FDE) различных размерностей против одновекторной эвристики (SV). Обратите внимание, что 10240-мерные FDE имеют почти такой же размер представления, как и исходное представление MV (используемое в эвристике SV), при этом требуя значительно меньше сравнений при поиске (это справедливо даже для 20k-мерных FDE).
Сокращение задержки: по сравнению с PLAID, высокооптимизированной многовекторной системой поиска, основанной на одновекторной эвристике, MUVERA обеспечивает в среднем на 10% более высокую полноту при значительном сокращении задержки на 90% по всем наборам данных BEIR (показано на рисунке ниже).
MUVERA против PLAID по показателям BEIR.
Более того, мы обнаружили, что FDE MUVERA можно эффективно сжимать с помощью квантования продуктов, что позволяет сократить объем памяти в 32 раза при минимальном влиянии на качество извлечения.
Эти результаты подчеркивают потенциал MUVERA для значительного ускорения многовекторного поиска, что делает его более практичным для реальных приложений.
Заключение
Мы представили MUVERA, новый и эффективный алгоритм многовекторного поиска с доказуемыми гарантиями качества аппроксимации и хорошей практической производительностью. Уменьшая многовекторный поиск до одновекторного MIPS, MUVERA использует существующие оптимизированные методы поиска и достигает передовой производительности со значительно улучшенной эффективностью. Заинтересованные читатели могут найти реализацию нашего алгоритма построения FDE с открытым исходным кодом на GitHub .
Наша работа открывает новые возможности для эффективного многовекторного поиска, что имеет решающее значение для различных приложений, включая поисковые системы, системы рекомендаций и обработку естественного языка. Мы считаем, что дальнейшие исследования и оптимизация MUVERA приведут к еще большему повышению производительности и более широкому внедрению методов многовекторного поиска.
Комментарии