Конференция 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, разница между ними обычно не имеет большого значения.
Screenshot: https://platform.openai.com/docs/guides/embeddings/which-distance-function-should-i-use
Векторные особенности: разреженные векторы
Итак, объект может иметь различные характеристики. Цвет с компонентами красного, зеленого и синего является самым простым примером. В реальной жизни это обычно более сложно.
В текстовом поиске, например, мы можем представлять документы как высокоразмерные векторы. Это подводит нас к концепции “мешка слов”. Эта модель преобразует текст в векторы, где каждое измерение соответствует уникальному слову, а значение может быть бинарным индикатором наличия слова, количеством вхождений или весом слова на основе его частоты и обратной частоты документа (называемого TF-IDF), который отражает, насколько важно слово для документа в коллекции. Это так называемый разреженный вектор, поскольку большинство значений равны нулю, так как большинство документов не содержит много слов.
Когда речь идет о полнотекстовом поиске в библиотеках и поисковых системах, таких как Lucene , Elasticsearch и Manticore Search , разреженные векторы помогают ускорить поиск. В основном, вы можете создать специальный тип индекса, который игнорирует документы без поискового термина. Таким образом, вам не нужно проверять каждый отдельный документ против вашего поиска каждый раз. Разреженные векторы также легко понимаемы, они могут быть, в определенном смысле, обратимо инженированы. Каждое измерение соответствует конкретной четкой характеристике, так что мы можем проследить обратно от нашего векторного представления к исходному тексту. Эта концепция существует уже около 50 лет.
Векторные особенности: плотные векторы
Traditional text search methods like TF-IDF , которые существуют уже несколько десятилетий, производят разреженные векторные представления слов, которые зависят от частоты терминов. Основная проблема? Обычно они игнорируют контекст, в котором используются слова. Например, термин “яблоко” может быть связан как с фруктом, так и с технологической компанией без различия, потенциально ранжируя их аналогично в поиске.
Но рассмотрим эту аналогию: в векторном пространстве какие два объекта будут находиться ближе друг к другу: кошка и собака или кошка и автомобиль? Традиционные методы, которые генерируют разреженные векторы — такие как тот, что показан в верхней части нижнего изображения — могут испытывать трудности с предоставлением значимого ответа. Разреженные векторы часто имеют высокую размерность, при этом большинство значений равно нулю, что представляет собой отсутствие большинства слов в данном документе или контексте.
Затем пришла революция глубокого обучения, введя контекстные векторы. Это плотные векторные представления, как показано в нижней части изображения. В отличие от разреженных векторов, которые могут иметь десятки тысяч размерностей, плотные векторы имеют меньшую размерность (например, 784 размерности на изображении), но наполнены непрерывными значениями, которые захватывают нюансированные семантические отношения. Это означает, что одно и то же слово может иметь разные векторные представления в зависимости от контекста, и разные слова могут иметь схожие вектора, если они разделяют контексты. Технологии, такие как BERT и GPT , используют эти плотные векторы для захвата сложных языковых особенностей, включая семантические отношения, различение синонимов от антонимов и понимание иронии и сленга — задачи, которые были довольно сложными для более ранних методов.
Более того, глубокое обучение выходит за рамки текста, позволяя обрабатывать сложные данные, такие как изображения, аудио и видео. Их также можно преобразовать в плотные векторные представления для таких задач, как классификация, распознавание и генерация. Появление глубокого обучения совпало с взрывом доступности данных и вычислительной мощности, что позволило обучать сложные модели, которые выявляют более глубокие и тонкие паттерны в данных.
Векторы
Векторы, которые предоставляют такие модели, называются “векторами встраивания”. Важно понимать, что в отличие от показанных ранее разреженных векторов, где каждый элемент может представлять четкую характеристику, такую как слово, присутствующее в документе, каждый элемент вектора встраивания также представляет собой конкретную характеристику, но в большинстве случаев мы даже не знаем, что это за характеристика.
Например,
Джей Алламер провел интересный эксперимент
и использовал модель GloVe для векторизации Википедии, а затем визуализировал значения для некоторых слов с помощью разных цветов. Мы можем увидеть здесь, что:
- Постоянная красная линия появляется у различных слов, указывая на сходство по одной размерности, хотя конкретный атрибут, который она представляет, остается неопределенным.
- Такие термины, как “женщина” и “девочка”, или “мужчина” и “мальчик” показывают сходства по нескольким размерностям, что предполагает их связанность.
- Интересно, что “мальчик” и “девочка” имеют сходства, отличные от “женщины” и “мужчины”, намекая на скрытую тему юности.
- Кроме одного случая с термином “вода”, все проанализированные слова относятся к людям, при этом “вода” служит для различия между концептуальными категориями.
- Явные сходства между “королем” и “королевой” по сравнению с другими терминами могут предполагать абстрактное представление о royalty.
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 и другими, каждый из которых имеет свои плюсы и минусы с точки зрения производительности, потребления ресурсов и потерь точности.
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
, что важно, потому что базы данных, которые не поддерживают этот тип данных, сначала должны его добавить, поскольку плотные векторы обычно хранятся в массивах с плавающей точкой. В это время вы также обычно настраиваете поле, указывая размерность вектора, тип индекса вектора и его свойства. Например, мы указываем, что хотим использовать индекс 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, сделали векторный поиск быстрее.
Смотрят в будущее, мы ожидаем, что базы данных будут делать больше, чем просто поддерживать векторный поиск; они, вероятно, будут создавать эмбеддинги самостоятельно. Это упростит использование баз данных и сделает их более мощными, превращая их из простых хранилищ в умные системы, способные понимать и анализировать данные. Короче говоря, векторный поиск является значительным сдвигом в управлении данными и их извлечении, что обозначает захватывающее развитие в этой области.