Привет, Хабр!

Меня зовут Михаил. Я занимаюсь разработкой корпоративных поисковых систем, а также поиском по каталогам в интернет-магазинах. Еще я разрабатываю поисковые системы с открытым кодом Apache Lucene и Apache Solr.

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

Пожалуй, начнем с начала. Люди всегда сталкивались с необходимостью поиска: будь то поиск нужной книги, страницы в ней или даже файла в Norton Commander. Общим для всех этих задач было то, что они требовали полного перебора контента, что занимало много времени. Для поиска нужной информации приходилось просматривать весь доступный материал, чтобы найти соответствие поисковому запросу.

Решением этой проблемы стали различные каталоги и предметные указатели, которые позволяли избежать полного перебора документов. С развитием технологий этот подход эволюционировал. Например, современные операционные системы, такие как Windows и macOS, используют индекс содержимого файлов для ускорения поиска.

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

Системы текстового поиска работают по принципу, аналогичному предметным указателям в книгах.

В основе лежит словарь, содержащий все слова (термины), встречающиеся в условной книге. Каждому слову соответствует список номеров страниц, где это слово встречается. На первом этапе поиска система использует этот словарь для отбора кандидатов — страницы, содержащие искомые термины.

Следующий этап — ранжирование. Его цель — упорядочить найденные совпадения по релевантности, чтобы пользователь в первую очередь увидел наиболее подходящие результаты. Ранжировали эти системы текстового поиска по примитивным статистическим гипотезам.

Основная идея заключалась в том, что, чем больше терминов из запроса встречается в документе и чем эти термины важнее, тем выше релевантность документа. Важность слова определялась частотой его встречаемости: чем реже слово, тем оно считалось важнее. Эти простые гипотезы легли в основу алгоритмов ранжирования, таких как TF-IDF и BM25, которые использовались и развивались на протяжении десятилетий.

Однако у такого подхода есть ряд существенных недостатков. Рассмотрим пример: пользователь ищет «столицу Соединенных Штатов».

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

Ключевая проблема текстового поиска — различие языка документов и языка запросов. Это не значит, что они используют разные языки в буквальном смысле, а скорее то, что одни и те же понятия могут выражаться по-разному. Например, в документах может использоваться полное название «United States», а пользователь ищет по аббревиатуре «US». Текстовый поиск не справится с такими синонимичными запросами без дополнительной настройки словаря синонимов, что зачастую сложно и трудоемко.

Другой пример с иллюстрации выше — направление визы. Для человека всё очевидно, но для текстового поиска это практически одно и то же. Конечно, можно использовать фразовые запросы, но это создает дополнительные сложности.

Наконец, существуют контекстные синонимы (третий пример с той же иллюстрации). Например, в определенном контексте NumPy и SciPy могут быть синонимами. Конечно, не во всех случаях, но вот корреляция Спирмена присутствует только в библиотеке SciPy, а в NumPy этого нет, и запрос пользователя можно удовлетворить, предложив ему такой синоним, привязанный к контексту.

Первый способ применения машинного обучения в поиске назывался «обучением ранжированию» (Learning to Rank), он появился в 90-х годах. Это была довольно сложная многоэтапная процедура.

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

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

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

Новый подход к решению проблем поиска появился в 2013 году с появлением модели Word2Vec, разработанной Google. Эта модель позволяет представлять слова в виде многомерных векторов, состоящих из нескольких сотен дробных чисел.

Для наглядности на иллюстрациях значения этих чисел представлены в виде цветовых полос, аналогично высоте на физической карте. Каждая полоса соответствует многомерному вектору, который модель присваивает слову. На первый взгляд, непонятно, как использовать эти векторы для поиска, но в них заключен определенный смысл.

Например, слова «man» и «woman» имеют схожие значения. И можно заметить, что соответствующие измерения их векторов содержат одинаковые значения. Таким образом, многомерные векторы отражают семантику слов. Хотя механизм работы Word2Vec сложно объяснить в двух словах, эта модель действительно способна улавливать смысловые связи между словами.

Развитие моделей словарных вложений привело к появлению трансформеров. В 2018 году Google представила модель BERT (Bidirectional Encoder Representations from Transformers).

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

Модель BERT принимает на вход текст, представляющий собой комбинацию запроса и документа. На основе этого текста модель вычисляет многомерный вектор, который затем подается в классификатор. Классификатор выдает дробное число от 0 до 1, отражающее степень соответствия документа запросу. Таким образом, BERT может определять, насколько документ релевантен запросу.

Такой подход к ранжированию называется Cross-Encoder, поскольку запрос и документ кодируются вместе. Обучение BERT состоит из двух этапов:

• Pre-training (предварительное обучение): Модель обучается на большом объеме текстов из интернета без учителя (unsupervised learning). Это позволяет модели выучить общие закономерности языка.

• Fine-tuning (дообучение): Модель дообучается на конкретных парах запрос-документ с использованием экспертных оценок релевантности. То есть учитель указывал степень соответствия запроса и документов, и эти триплеты, тройки данных (запрос, документ и степень соответствия), отправлялись в эту модель, и она настраивалась на задачи определенного домена.

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

Как же использовать BERT для поиска? Вычислять степень соответствия для каждой пары запрос-документ. Однако, это требует полного перебора всех документов, что неприемлемо с точки зрения производительности, особенно учитывая, что инференс BERT — довольно медленная операция.

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

Для повышения эффективности был разработан другой подход.

Документы, в отличие от запросов, не меняются. Поэтому можно заранее закодировать все документы в векторы (словарные вложения) и использовать их при поиске. В этом случае запрос и документ кодируются по отдельности, что несколько снижает точность, но значительно повышает скорость.

Теперь задача поиска сводится к поиску ближайших векторов в векторном пространстве. Используя метрики схожести, можно найти документы, векторы которых наиболее близки к вектору запроса. Этот подход не только ускоряет поиск, но и открывает новые возможности, такие как кросс-языковой и мультимодальный поиск.

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

В этой таблице строки представляют документы, а столбцы — слова. Единичка в ячейке означает, что данное слово встречается в данном документе. Как можно заметить, единиц в такой матрице гораздо меньше, чем пустых ячеек. Каждый столбец соответствует строке в нашем «предметном указателе». Благодаря разреженности матрицы, списки вхождений слов получаются короткими, что позволяет использовать эффективные алгоритмы и структуры данных (sparse search). Именно поэтому традиционный текстовый поиск работает быстро.

Что же происходит в векторном поиске? Количество измерений вектора, наверное, все же меньше, чем количество слов в языке. При этом каждое измерение присутствует в каждом документе. Это означает, что мы снова сталкиваемся с задачей полного перебора: чтобы найти ближайшие векторы, нужно сравнить вектор запроса со всеми векторами документов. Алгоритмы, оптимизированные для разреженных матриц, здесь не работают. Мы имеем дело с плотной матрицей, и поиск по ней называется dense search.

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

Существуют плагины для интеграции векторного поиска в существующие системы, например, плагин для Postgres. Однако одной векторной базы данных недостаточно. Необходим каркас, который организует индексацию и управляет поисковым конвейером.

В качестве примера рассмотрим архитектуру Vespa.

Vespa — старая векторная база данных. Как она работает? Обработка поискового запроса происходит снизу вверх. В основании лежат два механизма: слева — векторный поиск, справа — текстовый поиск. Векторный поиск, встроенный в Vespa, работает быстро, но с потерей точности, основываясь на приближенных результатах. Текстовый поиск необходим для обработки буквальных совпадений, которые векторный поиск, оперирующий смыслом, может упустить.

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

Здесь представлен общий рейтинг поисковых систем. Как видно из таблицы, неадаптированный BERT может показывать результаты значительно хуже, чем традиционный текстовый поиск. Поэтому этап дообучения и выравнивания модели на собственных данных очень важен.

На картинке представлен список популярных моделей для поиска. Мы в основном говорили о моделях, вычисляющих эмбеддинги (многомерные вектора). На их основе строятся классификаторы, решающие конкретные задачи, такие как оценка релевантности, поиск спама и т.д. Модели типа BERT и CLIP вычисляют словарные вложения, которые затем используются для дальнейшей обработки — например, для классификации документов. Также широкую популярность приобрели GPT-модели, способные генерировать текст. Об их применении в поисковых задачах мы расскажем в следующей части статьи.

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

Спасибо за внимание!