Конференция FOSDEM, состоявшаяся 3 февраля 2024 года, включала презентацию о векторном поиске Manticore, которую представили Петр Зайцев , соучредитель Manticore, и Сергей Николаев , генеральный директор Manticore. Это событие продемонстрировало последние достижения в области векторного поиска в базах данных. Для более детального ознакомления запись выступления Зайцева доступна выше. Ниже вы можете увидеть более подробное резюме темы в виде статьи.

Введение

За последние два-три года ландшафт баз данных претерпел несколько ключевых изменений:

• Появилась новая категория «векторных баз данных», в которую входят платформы с открытым исходным кодом, такие как Milvus в 2019 году, Vespa в 2020 году, Weaviate в 2021 году и Qdrant в 2022 году, а также облачные решения, такие как Pinecone, представленное в 2019 году. Эти базы данных предназначены для векторного поиска, сосредотачиваясь на использовании различных моделей машинного обучения. Однако им могут недоставать традиционных возможностей баз данных, таких как транзакции, аналитика, репликация данных и так далее.
• Elasticsearch добавил возможности векторного поиска в 2019 году.
• Затем, с 2022 по 2023 год, устоявшиеся базы данных, включая Redis, OpenSearch, Cassandra, ClickHouse, Oracle, MongoDB и Manticore Search, а также облачные сервисы от Azure, Amazon AWS и Cloudflare, начали предлагать функциональность векторного поиска.
• Другие известные базы данных, такие как MariaDB, находятся в процессе интеграции возможностей векторного поиска.
• Для пользователей PostgreSQL существует расширение 'pgvector', которое реализует эту функциональность с 2021 года.
• Хотя MySQL не объявил о планах по внедрению нативной функциональности векторного поиска, доступны проприетарные расширения от таких провайдеров, как PlanetScale и AlibabaCloud.

Векторное пространство и векторное сходство

Давайте обсудим, почему так много баз данных недавно включили функциональность векторного поиска и что это вообще такое.
Начнем с наглядного примера. Рассмотрим два цвета: красный с RGB кодом (255, 0, 0) и оранжевый с RGB кодом (255, 200, 152). Чтобы сравнить их, давайте изобразим их на трехмерном графике, где каждая точка представляет собой другой цвет, а оси соответствуют красным, зеленым и синим компонентам цветов. Затем мы проведем векторы от начала координат графика к точкам, представляющим наши цвета. Теперь у нас есть два вектора: один представляет красный, а другой - оранжевый.

Если мы хотим найти сходство между этими двумя цветами, один из подходов может заключаться в простом измерении угла между векторами. Этот угол может варьироваться от 0 до 90 градусов, или, если мы нормализуем его, взяв косинус, он будет варьироваться от 0 до 1. Однако этот метод не учитывает величину векторов, что означает, что косинус даст одно и то же значение для цветов A, A1, A2, даже если они представляют собой разные оттенки.

Чтобы решить эту проблему, мы можем использовать формулу косинусного сходства, которая учитывает длины векторов - скалярное произведение векторов, деленное на произведение их величин.

Эта концепция является сутью векторного поиска. Это легко визуализировать с цветами, но теперь представьте, что вместо трех цветовых осей у нас есть пространство с сотнями или тысячами измерений, где каждая ось представляет собой конкретную характеристику объекта. Хотя мы не можем легко изобразить это на слайде или полностью визуализировать, математически это осуществимо, и принцип остается тем же: у вас есть векторы в многомерном пространстве, и вы вычисляете сходство между ними.

Существуют и другие формулы для нахождения векторного сходства: например, сходство по скалярному произведению и евклидово расстояние, но, как говорят в документации API OpenAI, разница между ними обычно не имеет большого значения.

Скриншот: https://platform.openai.com/docs/guides/embeddings/which-distance-function-should-i-use

Векторные характеристики: разреженные векторы

Итак, объект может иметь различные характеристики. Цвет с компонентами Красный, Зеленый и Синий - самый простой пример. В реальной жизни это обычно более сложно.

В текстовом поиске, например, мы можем представлять документы как высокоразмерные векторы. Это приводит нас к концепции "Мешок слов". Эта модель преобразует текст в векторы, где каждое измерение соответствует уникальному слову, а значение может быть бинарным индикатором присутствия слова, количеством вхождений или весом слова на основе его частоты и обратной частоты документа (называемого TF-IDF), который отражает, насколько важно слово для документа в коллекции. Это так называемый разреженный вектор, поскольку большинство значений равны нулю, так как большинство документов не содержат много слов.

Говоря о полнотекстовом поиске в библиотеках и поисковых системах, таких как Lucene , Elasticsearch и Manticore Search , разреженные векторы помогают ускорить поиск. В основном, вы можете создать специальный тип индекса, который игнорирует документы без поискового термина. Таким образом, вам не нужно проверять каждый отдельный документ на соответствие вашему запросу каждый раз. Разреженные векторы также легко понимаемы, их можно, в определенном смысле, обратным образом инженерить. Каждое измерение соответствует конкретной четкой характеристике, поэтому мы можем проследить путь от нашего векторного представления к оригинальному тексту. Эта концепция существует уже около 50 лет.

Изображение: https://www.researchgate.net/figure/Figure4DocumentrepresentationintheVectorSpaceModel22_fig1_312471174

Векторные характеристики: плотные векторы

Traditional text search methods like TF-IDF , which have been around for decades, produce sparse word vectors that depend on term frequency. Основная проблема? Они обычно игнорируют контекст, в котором используются слова. Например, термин "яблоко" может быть связан как с фруктом, так и с технологической компанией, не делая различий, что потенциально может привести к их схожему ранжированию в поиске.

Но рассмотрим эту аналогию: в векторном пространстве, какие два объекта будут ближе друг к другу: кошка и собака, или кошка и машина? Традиционные методы, которые генерируют разреженные векторы — как тот, что показан в верхней части изображения ниже — могут испытывать трудности с предоставлением значимого ответа. Разреженные векторы часто имеют высокую размерность, при этом большинство значений равны нулю, что представляет собой отсутствие большинства слов в данном документе или контексте.

Затем произошла революция глубокого обучения, которая представила контекстные встраивания. Это плотные векторные представления, как показано в нижней части изображения. В отличие от разреженных векторов, которые могут иметь десятки тысяч размерностей, плотные векторы имеют меньшую размерность (например, 784 размерности на изображении), но насыщены непрерывными значениями, которые захватывают тонкие семантические отношения. Это означает, что одно и то же слово может иметь разные векторные представления в зависимости от его контекста, и разные слова могут иметь схожие векторы, если они разделяют контексты. Технологии, такие как BERT и GPT , используют эти плотные векторы для захвата сложных языковых особенностей, включая семантические отношения, различение синонимов и антонимов, а также понимание иронии и сленга — задач, которые были довольно сложными для более ранних методов.

Более того, глубокое обучение выходит за рамки текста, позволяя обрабатывать сложные данные, такие как изображения, аудио и видео. Эти данные также могут быть преобразованы в плотные векторные представления для задач, таких как классификация, распознавание и генерация. Появление глубокого обучения совпало с взрывом доступности данных и вычислительной мощности, что позволило обучать сложные модели, которые выявляют более глубокие и тонкие паттерны в данных.

Image: https://cdn.sanity.io/images/vr8gru94/production/96a71c0c08ba669c5a5a3af564cbffee81af9c6d-1920x1080.png

Embeddings

Векторы, которые предоставляют такие модели, называются "встраиваниями". Важно понимать, что в отличие от разреженных векторов, показанных ранее, где каждый элемент может представлять собой четкую характеристику, такую как слово, присутствующее в документе, каждый элемент встраивания также представляет собой конкретную характеристику, но в большинстве случаев мы даже не знаем, что это за характеристика.
Например, Джей Алламер провел интересный эксперимент и использовал модель GloVe для векторизации Википедии, а затем визуализировал значения для некоторых слов с разными цветами. Мы можем увидеть здесь, что:

1. Последовательная красная линия появляется среди различных слов, указывая на схожесть по одному измерению, хотя конкретный атрибут, который она представляет, остается неопределенным.
2. Такие термины, как "женщина" и "девочка" или "мужчина" и "мальчик", демонстрируют схожесть по нескольким измерениям, что предполагает родство.
3. Интересно, что "мальчик" и "девочка" имеют схожести, отличные от "женщины" и "мужчины", намекая на скрытую тему юности.
4. За исключением одного случая с термином "вода", все проанализированные слова относятся к людям, при этом "вода" служит для различения концептуальных категорий.
5. Явные сходства между "королем" и "королевой" в отличие от других терминов могут указывать на абстрактное представление о королевской власти.

Image: https://jalammar.github.io/illustrated-word2vec/

Таким образом, плотные векторные встраивания, генерируемые с помощью глубокого обучения, захватывают огромное количество информации в компактной форме. В отличие от разреженных векторов, каждое измерение плотного встраивания обычно не равно нулю и несет некоторую семантическую значимость. Эта насыщенность имеет свою цену - с плотными встраиваниями, поскольку каждое измерение плотно заполнено значениями, мы не можем просто пропустить документы, которые не содержат конкретный термин. Вместо этого мы сталкиваемся с вычислительной интенсивностью сравнения векторного запроса с каждым вектором документа в наборе данных. Это грубый подход, который естественно требует много ресурсов.

Тем не менее, были разработаны специализированные индексы, адаптированные для плотных векторов. Эти индексы, такие как KD-деревья, Ball-деревья или более современные подходы, такие как HNSW (Hierarchical Navigable Small World) графы, довольно умные, но иногда им приходится немного угадывать, чтобы быть быстрыми. Это угадывание может означать, что они не всегда получают ответ на 100% правильно. Наиболее популярный индекс, который принимают базы данных, это HNSW, что означает Hierarchical Navigable Small World. Он используется расширением pgvector для Postgres, Lucene , Opensearch , Redis , SOLR , Cassandra , Manticore Search и Elasticsearch . Его алгоритм строит многоуровневую графовую структуру. Каждый уровень представляет собой граф, где каждый узел (представляющий собой точку данных) соединен с ближайшими соседями. Нижний уровень содержит все узлы (точки данных), а каждый последующий верхний уровень содержит подмножество узлов из нижнего уровня. На верхнем уровне наименьшее количество узлов. Поиск начинается с верхних уровней и постепенно перемещается вниз к нижним уровням. Этот иерархический подход делает процесс поиска эффективным. В двух словах, HNSW, как и любой другой индекс, просто предварительно генерирует некоторые ярлыки, которые вы затем можете использовать для более быстрого обработки запросов. Существуют и другие векторные индексы, такие как Annoy , поддерживаемый Spotify и другими, каждый из которых имеет свои плюсы и минусы с точки зрения производительности, потребления ресурсов и потери точности.

Image: https://cdn.sanity.io/images/vr8gru94/production/d6e3a660654d9cb55f7ac137a736539e227296b6-1920x1080.png

K-ближайшие соседи

Поиск векторов на самом деле является обобщающим термином, который включает в себя различные задачи, такие как кластеризация и классификация и другие. Но обычно первой функцией, которую база данных добавляет для поиска векторов, является 'Поиск K-ближайших соседей' (KNN) или его близкий аналог, 'Приблизительный поиск ближайших соседей' (ANN). Это привлекательно, потому что позволяет базам данных находить документы, которые наиболее похожи на вектор данного документа, что улучшает базы данных с мощными возможностями поисковой системы, которых у них ранее не было.

Традиционные поисковые системы, такие как Lucene, Elasticsearch, SOLR и Manticore Search, обрабатывают различные задачи обработки естественного языка — такие как морфология, синонимы, стоп-слова и исключения — все направлено на нахождение документов, которые соответствуют данному запросу. KNN достигает аналогичной цели, но другими средствами - просто сравнивая векторы, связанные с документами в таблице, которые обычно предоставляются внешней моделью машинного обучения.
Давайте рассмотрим, как выглядит типичный поиск векторов в базах данных, взяв Manticore Search в качестве нашего примера.

Сначала мы создаем таблицу с колонкой под названием image_vector:

create table test ( title text, image_vector float_vector knn_type='hnsw' knn_dims='4' hnsw_similarity='l2' );

Этот вектор имеет тип float , что важно, потому что базы данных, которые не поддерживают этот тип данных, должны сначала его добавить, так как плотные векторы обычно хранятся в массивах float. В это время вы также обычно настраиваете поле, указывая размерность вектора, тип индекса вектора и его свойства. Например, мы указываем, что хотим использовать индекс HNSW, вектор будет иметь размерность 5, а функция сходства будет l2, что является евклидовым расстоянием.

Затем мы вставляем несколько записей в таблицу:

insert into test values ( 1, 'yellow bag', (0.653448,0.192478,0.017971,0.339821) ), ( 2, 'white bag', (-0.148894,0.748278,0.091892,-0.095406) );

Каждая запись имеет заголовок и соответствующий вектор, который в реальном сценарии может быть результатом работы модели глубокого обучения, кодирующей какую-либо форму высокоразмерных данных, таких как изображение или звук, встраивание из текста или что-то еще из API OpenAI. Эта операция сохраняет данные в базе данных и может вызвать перестройку или корректировку индекса.

Далее, мы выполняем поиск векторов, используя функцию KNN :

select id, knn_dist() from test where knn ( image_vector, 5, (0.286569,-0.031816,0.066684,0.032926) );

+------+------------+
| id   | knn_dist() |
+------+------------+
|    1 | 0.28146550 |
|    2 | 0.81527930 |
+------+------------+
2 rows in set (0.00 sec)

Здесь мы запрашиваем базу данных, чтобы найти векторы, которые ближе всего к нашему заданному входному вектору. Числа в скобках определяют конкретный вектор, для которого мы ищем ближайших соседей. Этот шаг критически важен для любой базы данных, которая стремится реализовать возможности поиска векторов. На этом этапе база данных может либо использовать специфические методы индексации, такие как HNSW, либо выполнять поиск методом грубой силы, сравнивая вектор запроса с каждым вектором в таблице, чтобы найти ближайшие совпадения.

Возвращенные результаты показывают заголовки ближайших векторов к нашему входному вектору и их соответствующие расстояния от запроса. Более низкие значения расстояния указывают на более близкие совпадения с поисковым запросом.

Вычисление встраивания

Большинство баз данных и поисковых систем до сих пор полагаются на внешние встраивания. Это означает, что когда вы вставляете документ, вы должны заранее получить его встраивание из внешнего источника и включить его вместе с другими полями документа. То же самое касается поиска похожих документов: если поиск осуществляется по запросу пользователя, а не по существующему документу, вам нужно использовать модель машинного обучения для вычисления встраивания для него, которое затем передается в базу данных. Этот процесс может привести к проблемам совместимости, необходимости управлять дополнительными слоями обработки данных и потенциальной неэффективности в производительности поиска. Операционная сложность этого подхода также выше, чем необходимо. Вместе с базой данных вам может потребоваться поддерживать другую службу для генерации встраиваний.

Некоторые поисковые системы, такие как Opensearch, Elasticsearch и Typesense, теперь упрощают задачу, автоматически создавая встраивания. Они могут даже использовать инструменты от других компаний, таких как OpenAI, для этого. Я думаю, что мы скоро увидим больше этого. Больше баз данных начнут создавать встраивания самостоятельно, что действительно может изменить то, как мы ищем и анализируем данные. Это изменение означает, что базы данных будут делать больше, чем просто хранить данные; они действительно будут их понимать. Используя машинное обучение и ИИ, эти базы данных станут умнее, смогут предсказывать и адаптироваться, а также обрабатывать данные более продвинутыми способами.

Гибридные подходы к поиску

Некоторые поисковые системы приняли метод, известный как гибридный поиск, который сочетает в себе традиционный поиск по ключевым словам с современными методами нейронных сетей. Гибридные модели поиска превосходят в ситуациях, которые требуют как точных совпадений ключевых слов, как это обеспечивается традиционными методами поиска, так и более широкого распознавания контекста, как это предлагается возможностями поиска векторов. Этот сбалансированный подход может повысить точность результатов поиска. Например, Vespa измерила точность своего гибридного поиска , сравнив его с классической оценкой BM25 и моделью ColBERT по отдельности. В своем подходе они использовали классическую BM25 в качестве модели ранжирования первой фазы и вычисляли гибридный балл только для документов с наивысшим ранжированием K в соответствии с моделью BM25. Было установлено, что режим гибридного поиска превзошел каждую из них в большинстве тестов.

Другой более простой метод - это Обратное Ранговое Слияние (RRF), техника, которая объединяет ранжирования из различных поисковых алгоритмов. RRF вычисляет балл для каждого элемента на основе его ранга в каждом списке, где более высокие ранги получают лучшие баллы. Балл определяется по формуле 1 / (ранг + k), где 'ранг' - это позиция элемента в списке, а 'k' - это константа, используемая для корректировки влияния более низких рангов. Суммируя эти модифицированные обратные ранги из каждого источника, RRF подчеркивает консенсус между различными системами. Этот метод сочетает в себе сильные стороны различных алгоритмов, что приводит к более надежным и комплексным результатам поиска.

Table: https://blog.vespa.ai/improving-zero-shot-ranking-with-vespa-part-two/
Formula: https://plg.uwaterloo.ca/~gvcormac/cormacksigir09-rrf.pdf

Заключение

Векторный поиск - это не просто концепция или нишевая функция поисковых систем; это практический инструмент, который трансформирует способ, которым мы извлекаем данные. В последние годы в области баз данных произошли значительные изменения, с появлением новых баз данных, ориентированных на векторы, и существующие добавляют функции векторного поиска. Это отражает сильную потребность в более продвинутых функциях поиска, потребность, которую может удовлетворить векторный поиск. Продвинутые методы индексирования, такие как HNSW, сделали векторный поиск быстрее.

Смотря в будущее, мы ожидаем, что базы данных будут делать больше, чем просто поддерживать векторный поиск; они, вероятно, будут создавать встраивания сами. Это упростит использование баз данных и сделает их более мощными, превращая их из простых хранилищ в умные системы, которые могут понимать и анализировать данные. Короче говоря, векторный поиск - это значительный сдвиг в управлении данными и их извлечении, что является захватывающим развитием в этой области.