Microsoft открыл код библиотеки векторного поиска, используемой в Bing

Компания Microsoft опубликовала исходные тексты библиотеки машинного обучения SPTAG (Space Partition Tree And Graph) с реализацией алгоритма приблизительного поиска ближайшего соседа. Библиотека разработана в исследовательском подразделении Microsoft Research и центре разработки поисковых технологий (Microsoft Search Technology Center). На практике SPTAG применяется в поисковой системе Bing для определения наиболее релевантных результатов с учётом контекста поисковых запросов. Код написан на языке С++ и распространяется под лицензией MIT. Поддерживается сборка для Linux и Windows. Имеется обвязка для языка Python.

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

В состав библиотеки включены средства для построения индекса и организации поиска векторов, а также набор инструментов для сопровождения распределённой системы online-поиска, охватывающей очень большие коллекции векторов. Предлагаются следующие модули: index builder для индексации, searcher для поиска с использованием индекса, распределённого в кластере из нескольких узлов, сервер для запуска обработчиков на узлах, Aggregator для объединения нескольких серверов в одно целое и клиент для отправки запросов. Поддерживается включение новых векторов в индекс и удаление векторов на лету.

Библиотека подразумевает, что обрабатываемые и представленные в коллекции данные оформлены в виде связанных векторов, которые можно сравнивать на основе евклидовых (L2) или косинусных расстояний. При поисковом запросе возвращаются векторы, расстояние между которыми и исходным вектором минимально. В SPTAG предоставляется два метода организации векторного пространства: SPTAG-KDT (K-мерное дерево (kd-tree) и граф относительных окрестностей) и SPTAG-BKT (дерево k-средних (k-means tree и граф относительных окрестностей). Первый метод требует меньше ресурсов при работе с индексом, а второй демонстрирует более высокую точность результатов поиска при очень больших коллекциях векторов.

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

Источник: opennet.ru