Приближённый поиск ближайших соседей в рекомендательных системах
Введение
В феврале 2024 года на SF Unstructured Data Meetup мы услышали выступление Yury Malkov об Approximate Nearest Neighbor (ANN) и его ключевой роли в рекомендательных системах. ANN-поиск уже интегрирован в production-стеки самых популярных в мире инструментов. Yury помогает нам понять ключевые концепции и контекст, которые способствовали внедрению ANN в крупномасштабные рекомендательные системы.
Ссылка на запись выступления Yury Malkov на YouTube: Смотреть выступление на YouTube
Почему вам стоит интересоваться ANN?
Yuri Malkov — буквально гений. Если не верите, посмотрите его профиль в Google Scholar https://scholar.google.com/citations?user=KvAyakQAAAAJ&hl=en. Физик, исследователь лазеров и изобретатель HNSW — алгоритма индексации на основе графов, который теперь встроен во все основные векторные базы данных из коробки. Сейчас он работает в OpenAI в качестве Research Scientist. Скажите, разве это не звучит как правдоподобная биография Tony Stark в 2024 году?
А теперь давайте разберем выступление Yuri на тему «Approximate Nearest Neighbor Search in Recommender Systems».
Что такое ANN Search?
Мы будем кратки, поскольку уже рассмотрели основы ANN Search кратко и подробно.
Поиск ближайших соседей — это набор статистических методов, которые можно использовать для поиска по сходству в приложениях машинного обучения или data science. В отличие от их особого K-родственника KNN, который при выполнении поиска сравнивает каждую точку данных в системе со всеми остальными, алгоритмы ANN-поиска используют различные методы индексации, чтобы возвращать приблизительных ближайших соседей. ANN-поиск стал основой многих приложений и технологий, ориентированных на пользователей сегодня. От поисковых систем (таких как Google, а не векторный поиск) до социальных сетей — ANN и рекомендательные системы уже интегрированы по всему стеку, в production.
ANN был не единственным решением для рекомендательных систем. Так как же мы пришли к этому? Мы рассмотрим зрелые ANN-решения на рынке сегодня, что делает рекомендательные системы сложной задачей для алгоритмов ближайших соседей, как разработчики структурировали рекомендательные системы и как исследователи используют ANN, чтобы переписать стек рекомендательных систем. Yuri отмечает в своем выступлении, что существует множество зрелых ANN-решений. Многие из этих тем подробно рассмотрены в нашем визуальном руководстве по выбору векторного индекса, но я составил таблицу инструментов, перечисленных в презентации Yuri.
Таблица упомянутых ANN-индексов
| ANN Index | Классификация | Сценарий |
|---|---|---|
| LSH | Индекс на основе графов | - Большие, очень сложные многомерные наборы данных - Использует евклидово расстояние для распределения точек данных по корзинам - Возвращает только ближайшие результаты |
| HNSW | Индекс на основе графов | - Очень высокоскоростной запрос - Требуется максимально высокий показатель recall - Большие ресурсы памяти |
| SCANN | Индекс на основе квантования | - Очень высокоскоростной запрос - Требуется максимально высокий показатель recall - Большие ресурсы памяти |
| IVF_PQ | Индекс на основе квантования (инвертированный) | - Инвертированный индекс - Очень высокоскоростной запрос - Ограниченные ресурсы памяти - Допускает существенный компромисс в показателе recall |
| IVF_HSNW | Индекс на основе графов (инвертированный) | - Инвертированный индекс - На основе HSNW - Требуется максимально высокий показатель recall - Большие ресурсы памяти |
| DiskANN | Несколько индексов ближайших соседей | - Модификации ANN и инструментарий для ANN-поиска |
| ANNOY | Несколько индексов ближайших соседей | - Реализации LSH или KDtrees - Эффективный по памяти и быстрый поиск в пространствах высокой размерности |
| Many More | - | - FAISS, cuHNSW, ngt, song |
О бенчмарках ANN
Юрий молниеносно пробегает по бенчмаркингу ANN, указывая на ANNBenchmarks с оговоркой, что бенчмаркинг обратных алгоритмов ANN может быть непростым. Давайте замедлимся:
Что такое ANN-Benchmarks?
ANN-Benchmarks — это среда бенчмаркинга, которая оценивает различные алгоритмы приближённого поиска ближайших соседей, предоставляя на своём сайте результаты, разделённые по метрике расстояния и набору данных. Бенчмарки отображают метрики производительности, такие как показатель recall и количество запросов в секунду, а пользователи могут внести вклад, отправляя свой код через pull request’ы в GitHub .
Хотя данные бенчмаркинга алгоритмов ANN можно найти во многих местах (github, ANN-Benchmarks, даже документации продукта), вы всегда увидите диаграммы с QPS - запросами в секунду. Больше QPS — лучше! Врум-врум!
Заметка о выборе алгоритмов ANN (и других алгоритмов векторного поиска)
Если от просмотра бенчмарков алгоритмов у вас идёт кровь из носа, вы не одиноки. Именно поэтому команда Milvus создала Knowhere. Knowhere — это базовый open-source движок векторного выполнения Milvus, который включает несколько библиотек поиска векторного сходства, включая Faiss, Hnswlib и Annoy. Knowhere управляет тем, на каком оборудовании (CPU или GPU) выполнять построение индекса и поисковые запросы. Так Knowhere получил своё название — зная, где выполнять операции. В будущих версиях будет поддерживаться больше типов оборудования, включая DPU и TPU.
На основе Knowhere команда Zilliz Cloud выпустила Cardinal — основной движок векторного поиска Zilliz. Этот поисковый движок уже продемонстрировал трехкратное увеличение производительности по сравнению с предыдущей версией, обеспечивая производительность поиска (QPS), которая достигает десятикратного показателя Milvus. ANN-поиск давно интегрирован в рекомендательные системы. Чтобы понять, почему алгоритмы ANN-поиска стали настолько популярны в рекомендательных системах в production, нужно сделать шаг назад и рассмотреть мотивацию, архитектуру и новые решения, которые ANN превзошел.
Приложения рекомендательных систем в масштабе: мотивация и вызовы
Цель: Базовая цель всех рекомендательных систем — вернуть элемент (видео, продукт, документ, сообщение) для запроса (пользователь, приложение, контекст). Запомните эту связь элемент-запрос — она важна для понимания алгоритмов поиска (рекомендаций).
Рынок: Рекомендательные технологии представляли и представляют собой крупный рынок благодаря своей способности формировать поведение потребителей.
Типичные вызовы в масштабе:
Обобщаемость:
- Традиционно рекомендательные системы имели низкую обобщаемость — в основном из-за зависимости от внутренних данных, моделей и инфраструктуры.
Огромные корпуса:
Большие наборы данных (от миллионов до триллионов элементов, запросов) порождают большие затраты на инференс.
Эффективность и ограничение затрат на инференс очень важны.
Тяжелая обработка видео и изображений требовала выделенных инженеров для поддержания инфраструктуры.
Решения, зрелость:
Собственные решения/инфраструктура обычно разрабатываются внутри компаний (например, Google, Meta, X,)
Как правило, используется многоэтапная воронка рекомендаций (см. ниже), чтобы снизить затраты на инференс
Готовые инструменты набирают популярность и распространение на фоне роста векторных баз данных и LLM.
Типичная многоэтапная воронка
Юрий подробно разбирает диаграмму типичной рекомендательной системы в production. В приведенном ниже примере для видеорекомендаций приложению передаются элементы и запрос, и оно должно вернуть закрепленную видеорекомендацию. Эти приложения представляют собой многоэтапные воронки, где кандидаты-элементы генерируются и проходят через последовательные ранжирующие модели для уточнения результатов поиска.
Шаг 1: Генерация кандидатов - ANN + Light Model
На этом начальном этапе система использует approximate nearest neighbors, чтобы быстро просеять огромную базу видео и определить предварительный список видео-кандидатов, релевантных запросу пользователя. Этот процесс спроектирован как быстрый и эффективный, позволяя работать с потенциально миллионами элементов за счет фокуса на тех, которые с наибольшей вероятностью соответствуют характеристикам запроса. 'Light Model', используемая на этом шаге, обычно представляет собой более простую, менее вычислительно затратную модель, которая помогает сузить пул кандидатов до тех, которые лучше всего соответствуют интересам пользователя или поисковым словам.
Шаг 2: Легковесное ранжирование - Brute Force + Middle Model
После того как набор кандидатов сгенерирован, следующий шаг включает более детальное рассмотрение этих кандидатов. Это выполняется с использованием подхода 'Brute Force', при котором каждый кандидат оценивается более тщательно с помощью 'Middle Model', которая сложнее, чем Light Model, использованная на первом шаге. Эта модель учитывает дополнительные признаки, такие как метрики вовлеченности пользователя, контекстная релевантность и качество контента, чтобы ранжировать кандидатов так, чтобы наиболее релевантные видео продвигались к верхним позициям списка рекомендаций. Этот шаг обеспечивает баланс между производительностью и точностью, уточняя выбор за счет большего фокуса на качестве и релевантности.
Шаг 3: Полное ранжирование - Brute Force + Heavy Model
Финальный шаг в процессе рекомендаций — этап полного ранжирования (Full Ranking), в котором используется «тяжелая модель» (Heavy Model) — самая сложная и ресурсоемкая из применяемых моделей. Эта модель учитывает широкий спектр сигналов и точек данных, включая более глубокий анализ профиля пользователя, долгосрочные предпочтения, детальный анализ контента и, возможно, данные в реальном времени, такие как текущие тренды просмотров. Метод полного перебора (Brute Force), применяемый здесь, обеспечивает всестороннюю оценку и ранжирование каждого видео, гарантируя, что итоговые рекомендации будут максимально персонализированными и релевантными. Этот шаг обеспечивает рекомендации наивысшего качества, но требует больше вычислительных ресурсов и времени, что делает его подходящим для финальной доработки списка рекомендаций.
Почему HSNW дает сбои в традиционных рекомендательных системах и (несовершенные) решения Зная, что крупномасштабные производственные рекомендательные системы ограничены большими наборами данных и связанными с ними затратами, Юрий утверждает, что элементы и запросы лежат в двух — несовместимых плоскостях. Когда запросы и элементы находятся в разных и несовместимых пространствах, традиционные алгоритмы поиска по сходству, такие как Hierarchical Navigable Small World (HNSW), сталкиваются с трудностями, поскольку эти алгоритмы зависят от измеримого отношения или функции расстояния непосредственно между запросом и элементами. Без четкой метрики для оценки близости HNSW не может эффективно выполнять свою функцию, которая заключается в навигации по графу элементов для поиска наиболее близких совпадений с запросом.****
Обзор новых решений проблемы несовместимости элементов и запросов
L2-расстояние на векторах данных
Как это работает: Использует L2-расстояние между векторизованными входными данными для создания суррогатной графовой структуры для рекомендательных систем.
Плюсы: Упрощает процесс за счет использования простого вычисления расстояния, обеспечивая преимущество в скорости на этапах генерации кандидатов и повторного ранжирования.
Минусы: Может не так эффективно улавливать сложные взаимосвязи или нюансы между элементами и запросами, как более продвинутые модели, что потенциально приводит к менее персонализированным рекомендациям.
Ранжирование двудольного графа
Как это работает: Проецирует элементы и запросы в двудольный граф, где элементы связаны с ближайшими пользователями или запросами, что позволяет генерировать ребра на основе этих связей.
Плюсы: Эффективно структурирует реляционные данные между пользователями и элементами, хотя прямые сравнения с другими методами ограничены.
Минусы: Построение и поддержка двудольного графа могут быть ресурсоемкими, а эффективность может сильно варьироваться в зависимости от плотности и качества связей в графе.
Источник изображения: https://www.vldb.org/pvldb/vol15/p794-tan.pdf
Повторное ранжирование графа (ориентированное на текст)
Как это работает: Использует граф, созданный из векторов для генерации кандидатов, напрямую применяя тяжелый ранжировщик к графу для текстового поиска, что повышает качество результатов.
Плюсы: Устраняет традиционную многоэтапную воронку, позволяя исправлять ошибки, допущенные на более ранних этапах фильтрации кандидатов.
Минусы: В основном эффективно для текстового поиска; может быть менее эффективным в других контекстах, где доминируют нетекстовые признаки, что ограничивает его применимость.
Источник изображения: https://arxiv.org/pdf/2208.08942
Каскадный поиск по графу
Как это работает: Начинается с лёгкой функции расстояния для первоначального поиска и плавно переходит к более тяжёлой функции расстояния в процессе поиска.
Плюсы: Обеспечивает гибкость за счёт адаптации функции расстояния в реальном времени, оптимизируя как скорость, так и точность на протяжении всего процесса поиска.
Минусы: Сложность управления и оптимизации двух функций расстояния может увеличить вычислительные накладные расходы и сложность системы, потенциально влияя на масштабируемость.
Источник изображения: https://arxiv.org/pdf/2202.10226
Почему ANN Search так популярен?
Если объединить всё это, Юрий хорошо показал, почему алгоритмы ANN получили такое широкое внедрение, особенно в приложениях (например, крупномасштабных рекомендательных системах), которые работают с высокоразмерными наборами данных.
Достаточно хорошее (или лучшее) сопоставление - Если вам не нужно идеальное совпадение, разновидность ANN почти всегда является лучшим решением, чем другие алгоритмы NN.
Гибкость - благодаря широкому спектру реализаций разработчик может выбирать стоимость
Зрелость - ANN были реализованы во всех основных языках программирования, и существует несколько популярных фреймворков для выбора и выполнения ANN-поисков.
Дополнительные ресурсы
https://zilliz.com/learn/Local-Sensitivity-Hashing-A-Comprehensive-Guide
https://zilliz.com/learn/how-to-pick-a-vector-index-in-milvus-visual-guide
Ссылка на запись выступления Юрия Малкова на YouTube: Смотреть выступление на YouTube
Читать далее
Announcing VDBBench 1.0: Open-Source VectorDB Benchmarking with Your Real-World Production Workloads
Discover VDBBench 1.0, an open-source tool for benchmarking vector databases with real-world production data, streaming ingestion, and concurrent workloads.
What Exactly Are AI Agents? Why OpenAI and LangChain Are Fighting Over Their Definition?
AI agents are software programs powered by AI that can perceive their environment, make decisions, and take actions to achieve a goal—often autonomously.
Introducing DeepSearcher: A Local Open Source Deep Research
In contrast to OpenAI’s Deep Research, this example ran locally, using only open-source models and tools like Milvus and LangChain.