Компания Microsoft опубликовала (https://blogs.microsoft.com/ai/bing-vector-search/) исходные тексты библиотеки машинного обучения SPTAG (https://github.com/Microsoft/SPTAG) (Space Partition Tree And Graph) с реализацией алгоритма приблизительного поиска ближайшего соседа (https://ru.wikipedia.org/wiki/%D0%97%D0%.... Библиотека разработана (https://www.ailab.microsoft.com/vectorsearchexperiment) в исследовательском подразделении Microsoft Research и центре разработки поисковых технологий (Microsoft Search Technology Center).  На практике SPTAG применяется в поисковой системе Bing для определения наиболее релевантных результатов с учётом контекста поисковых запросов. Код написан на языке С++ и распространяется (https://github.com/Microsoft/SPTAG) под лицензией MIT. Поддерживается сборка для Linux и Windows.

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

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

Библиотека подразумевает, что обрабатываемые и представленные в коллекции данные оформлены в виде связанных векторов, которые можно сравнивать на основе евклидовых (https://ru.wikipedia.org/wiki/%D0%95%D0%... (L2) или косинусных (https://ru.wikipedia.org/wiki/%D0%9A%D0%... расстояний. При поисковом запросе возвращаются векторы, расстояние между которыми и исходным вектором минимально. В SPTAG предоставляется два метода организации векторного пространства: SPTAG-KDT (K-мерное дерево (kd-tree (https://ru.wikipedia.org/wiki/K-%D0%BC%D0... и граф относительных окрестностей (https://ru.wikipedia.org/wiki/%D0%93%D1%... и SPTAG-BKT (дерево k-средних (k-means tree (https://ru.wikipedia.org/wiki/%D0%9C%D0%... и граф относительных окрестностей). Первый метод требует меньше ресурсов при работе с индексом, а второй демонстрирует более высокую точность результатов поиска при очень больших коллекциях векторов.

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

URL: https://blogs.microsoft.com/ai/bing-vector-search/
Новость: https://www.opennet.me/opennews/art.shtml?num=50698