Векторные пространства и поиск ближайших соседей на production

Введение

Иногда при решении задач классификации необходимо применять алгоритм kNN в векторных пространствах. И если при обучении всё просто и знакомо, то при выводе в production люди сталкиваются с проблемами.

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

Что такое kNN?

Алгоритм kNN (k-nearest neighbours или k-ближайших соседей) – алгоритм классификации, основанный на оценке схожести объектов. Схожесть объектов определяется расстоянием в некотором векторном пространстве: чем ближе к представителям класса находится вектор объекта, тем больше вероятность, что объект относится к этому классу.

В чём основное преимущество kNN перед другими алгоритмами?

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

Для этого обычные модели приходится переобучать для каждого нового набора классов. Зачастую это может быть долго и дорого.

Решения, построенные на алгоритме kNN, лишены этого недостатка: они начинают предсказывать новые классы, как только появляется достаточное количество их представителей.

Примеры задач

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

Алгоритм

У всех вышеперечисленных задач во время работы в production будет 2 фазы решения:

1. Наполнение некоторого пространства векторами объектов:

   1. Векторизуем объект;

   2. Добавляем в пространство.

2. Определение класса объекта:

   1. Векторизуем объект;

   2. Ищем k-ближайших соседей в векторном пространстве;

   3. По k векторов и их атрибутам определяем целевое значение.

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

Таким образом после обучения нам нужно получить:

• Модель для векторизации;

• Функцию расстояния: это может быть косинусное расстояние, евклидова метрика или любая другая;

• Policy для итогового определения класса: это может быть как простое правило (возвращать класс, который встречается чаще всего), так и сложная модель (которая по разным статистикам умеет определять, какой класс нужно вернуть).

Вывод на production

Решение будет состоять из следующих компонент:

• Некая абстракция над векторным пространством, которая позволяет обновлять его (динамически добавлять и удалять векторы) и делать поиск;

• Сервиc с моделькой для векторизации;

• Демон, который будет загружать объекты, получать для них векторы из сервиса для векторизации (1) и обновлять пространство (2);

• Сервис, который будет принимать объект, получать вектор из сервиса для векторизации (3), искать для него k-ближайших соседей в абстракции (4), применять какую-то логику к ним и возвращать ответ.

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

Базовая реализация

Основные требования к абстракции над векторным пространством:

• Метод для поиска k-ближайших соседей.

• Метод для обновления пространства: важен, потому что без него теряются преимущества, которые даёт алгоритм kNN.

Существует много разных библиотек (faiss, annoy, nmslib), которые умеют решать эти задачи. Для использования их в production необходимо либо обернуть их в сервис (для синхронного предсказания), либо обернуть в приложение, которое читает объекты из одной очереди и пишет результат в другую очередь. Для своих задач мы выбрали HTTP API, т.к. нам важна скорость предсказания.

Важный нюанс! Многие библиотеки имеют такой контракт: на входе – вектор, на выходе – некий внутренний идентификатор. Поэтому для поиска и обновления нужно реализовать маппинг (в памяти или базе) между внутренними id и нашими объектами.

После этого можно выкатывать абстракцию на production, но вскоре вы столкнётесь с новыми трудностями.

Продвинутая реализация

Версионирование

Со временем вы захотите обновить алгоритм, например, изменить векторизацию или метрику поиска. При этом лучше иметь в production одновременно несколько версий, чтобы в случае ошибок иметь возможность быстро откатиться на прошлую. К тому же это позволит проводить a/b-тестирование. В любом случае необходимо будет реализовать версионирование, причём как самого пространства, так и алгоритма поиска в нём.

Масштабирование

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

Фильтрация

Для некоторых задач необходимо искать не во всём пространстве векторов, а только в какой-то маленькой его части. Вместо того, чтобы делать много маленьких векторных пространств (что неудобно поддерживать), можно научиться принимать фильтры в поисковых запросах и применять их во время поиска в пространстве.

Vektonn

Мы столкнулись со всеми этими проблемами сами, когда запускали разные алгоритмы в production. Сегодня мы хотим поделиться нашим Vektonn с сообществом.

Vektonn уже сейчас умеет:

• Искать k-ближайших соседей в векторных пространствах;

• Динамически обновлять векторные пространства;

• Версионировать как векторные пространства, так и индексы над ними;

• Работать с сотнями миллионов векторов;

• Фильтровать результаты поисковых запросов.

Ссылка на наш сайт: https://vektonn.io

Ссылка на наш Telegram: https://t.me/vektonn