Сочетание хеширования с учетом местоположения и эластичного поиска для масштабируемого онлайн-поиска K-ближайших соседей

Алекс Клибиш - выпускник первой программы Insight Data Engineering в Бостоне и присоединится к CiBO Technologies. До прихода в Insight он работал консультантом по науке о данных.

Для своего проекта Insight Data Engineering я создал плагин Elasticsearch, чтобы упростить реализацию крупномасштабных K-Nearest Neighbours (KNN) в онлайн-приложениях. Ключевые особенности включают в себя:

  1. Выполнение приблизительного поиска KNN в корпусе из 7 миллионов элементов со временем поиска менее секунды и поддержкой множества параллельных поисков.
  2. Постоянно добавляя новые элементы в корпус и немедленно делая их доступными для поиска.
  3. Предоставление всех функций через конечные точки HTTP.
  4. Горизонтальная масштабируемость для поиска, индексации и хранения элементов.

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

Знакомство с K-ближайшими соседями

K-Nearest Neighbours (KNN) - это метод извлечения похожих элементов из корпуса, где каждый элемент представлен как вектор признаков (список чисел с плавающей запятой фиксированной длины). Характеристики могут быть интерпретируемыми, как измерения растений в наборе данных Iris, и они также могут быть скрытыми, как выходные данные скрытого слоя в глубокой нейронной сети или векторы, которые представляют песни, исполнителей и пользователей в музыке. потоковая платформа.

Чтобы выполнить простейший поиск KNN, я создаю корпус векторов, выбираю вектор запроса, вычисляю его расстояние до каждого из векторов в корпусе (обычно евклидово расстояние или косинусное подобие) и возвращаю k векторов ( например, k = 10) с наименьшим расстоянием до вектора запроса.

Мотивация для ближайших соседей ElastiK

Давайте рассмотрим вариант использования для мотивации этого проекта. Скажем, я работаю на сайте электронной коммерции, где продавцы часто публикуют новые товары с изображениями. Я могу использовать предварительно обученную сверточную сеть для преобразования каждого изображения в вектор признаков и запускать поиск KNN по векторам для получения визуально похожих изображений. Теперь я хочу добавить на сайт функцию, чтобы, когда пользователь просматривает элемент, я использовал KNN, чтобы рекомендовать десять визуально похожих элементов. Эта проблема распространяется и на другие приложения. Например, я мог бы представить пользователей и элементы в виде векторов и получить K-ближайшие элементы для пользователя.

Если я реализую это в каком-либо значимом масштабе, я быстро столкнусь с проблемами. Получение ближайших соседей для элемента - это операция O (N), где N - размер корпуса и, следовательно, количество элементов, которые я должен проверить. Корпус растет, поэтому запуск KNN при загрузке страницы происходит слишком медленно. Я создал задание, которое запускает KNN для всех элементов один раз в день и кэширует ближайших соседей для быстрого поиска. Но теперь у меня нет соседей для всех новейших элементов, которые были опубликованы с момента последнего задания, и задание занимает больше времени при каждом запуске. Я мог бы и дальше пытаться обойти проблему, но быстро становится очевидным, что этот относительно простой алгоритм поиска трудно масштабировать для онлайн-приложения с растущим корпусом.

Хеширование с учетом местоположения для более быстрого KNN

Для ускорения поиска разработаны приблизительные методы KNN. Они возвращают приблизительный набор соседей со значительно более быстрым временем поиска и достаточной точностью.

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

Введение в перевернутый индекс

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

Комбинирование LSH с инвертированным индексом

LSH позволяет мне представлять вектор функций как набор дискретных хэшей, а инвертированный индекс позволяет мне извлекать документы, сопоставляя слова с документами. Отсюда следует, что я могу построить инвертированный индекс для отображения хэшей в векторы. Когда я получаю новые векторы, я хеширую их и добавляю в индекс. Чтобы запустить поиск KNN, я беру хэши вектора запроса, извлекаю подмножество совпадающих векторов из инвертированного индекса, вычисляю точное расстояние до каждого вектора и возвращаю идентификаторы K-ближайших из них. Я получил отличные результаты, даже когда подмножество на несколько порядков меньше, чем полный корпус!

Внедрение LSH в Elasticsearch

Теперь, когда я могу использовать LSH для хеширования векторов и инвертированный индекс для их хранения и извлечения, давайте рассмотрим причины использования Elasticsearch:

  1. Хранение данных: векторы и хэши должны где-то храниться. Elasticsearch позволяет легко сохранять каждый вектор в виде документа, содержащего вектор, хэши и произвольные метаданные о векторе. Я указываю, что Elasticsearch должен индексировать хеши, а не вектор.
  2. Использование вычислений для данных. Плагины Elasticsearch запускаются на узлах кластера Elasticsearch. Это означает, что после сохранения векторов они никогда не передаются по сети, что было бы узким местом.
  3. RESTful API. Встроенные конечные точки RESTful в Elasticsearch - удобный способ хранить документы и выполнять поиск из любого приложения. Мне удалось раскрыть все функции моего плагина как набор конечных точек RESTful.
  4. Горизонтальная масштабируемость: Elasticsearch создан для работы в кластере. Это означает, что я могу установить плагин на каждом узле и запускать запросы к каждому из них параллельно. Более того, каждый отдельный узел также может обрабатывать несколько параллельных запросов без изменения кода.
  5. Инженеры уже используют Elasticsearch: во многих запросах инженерных команд уже есть кластер Elasticsearch. Установить подключаемый модуль в кластере проще, чем развертывать и контролировать совершенно новое программное решение.

Для реализации плагина я использовал Java API Elasticsearch и абстрагировал функциональность как набор из трех конечных точек:

  1. Конечная точка для отправки образца набора векторов, используемых для определения хэш-функций LSH. Эта выборка должна быть репрезентативной для векторов, которые позже будут сохранены и опрошены. После определения хэш-функций их параметры также сохраняются в виде документа в Elasticsearch.
  2. Конечная точка для хранения новых векторов. Новые векторы немедленно хешируются с использованием заранее подготовленных хэш-функций LSH. Каждый вектор хранится как отдельный документ, содержащий вектор и хеши.
  3. Конечная точка для поиска KNN. Пользователь указывает вектор запроса, который уже был сохранен, размер подмножества и значение для k. Я использую Bool Query для получения подмножества векторов, которые соответствуют наибольшему количеству хэшей, вычисляю точное расстояние до каждого из них и возвращаю k-ближайшие.

Плагин относительно прост в установке. В текущем состоянии вы клонируете репозиторий, запускаете сборку Gradle для создания zip-файла и используете интерфейс командной строки Elasticsearch для установки плагина из zip-файла.

Количественная оценка производительности

Это работает, но насколько хорошо? Для онлайн-приложений KNN меня в первую очередь интересуют два показателя производительности:

  1. Время поиска как функция размера корпуса: как изменяется время поиска по мере роста корпуса?
  2. Время поиска как функция напоминания: напоминание - это доля точных ближайших соседей, найденных в результате приблизительного поиска. Отзыв 0,6 при k = 10 означает, что мой приблизительный поиск вернул 6 из 10 истинных ближайших соседей. Плагин использует три параметра, которые могут увеличить отзыв за счет дополнительного времени поиска. Цель состоит в том, чтобы найти конфигурацию, которая дает адекватный отзыв с минимальным увеличением времени поиска.

Я провел тесты с использованием 25-мерных векторов слов GloVe с размерами корпуса 10 тысяч, 100 тысяч и 1 миллион. Результаты показывают:

  1. Время поиска сублинейно зависит от размера корпуса, что является критическим свойством для онлайн-приложений.
  2. Я могу добиться почти идеального отзыва для всех трех размеров корпуса со временем поиска менее 250 миллисекунд.

Будущие направления

На данный момент плагин все еще является доказательством правильности концепции. Некоторые потенциальные улучшения включают:

  1. Реорганизация кода для упрощения расширения и тестирования. Я также подумал о том, чтобы переписать текст на менее подробном языке JVM, таком как Scala или Kotlin.
  2. Добавление других показателей расстояния (например, косинусного расстояния), поскольку в настоящее время поддерживается только евклидово расстояние.
  3. Объединение запроса KNN с другими запросами (например, получение только ближайших соседей, которые были добавлены за последние два дня).

Спасибо Insight Data Engineering!

Я хочу выразить благодарность компании Insight Data Engineering за предоставленную мне поддержку и ресурсы для обучения и профессионального роста за последние двенадцать недель. Обязательно ознакомьтесь с программой, если вас интересуют такие проекты, как мой, и вы хотите продолжить карьеру в области инженерии данных!

Дальнейшее чтение

Чтобы узнать больше о KNN, я рекомендую этот пост в блоге Джейсона Браунли, первую задачу, поставленную в Стэнфордском курсе CS231n и лекции по машинному обучению из Введение в вычислительное мышление MIT 6.0002.

Чтобы узнать больше об Elasticsearch, я рекомендую эту замечательную серию в блоге Insight Data Engineering и Курс Elasticsearch Essential Training по LinkedIn Learning. Официальная документация по созданию плагинов Elasticsearch ограничена, поэтому я рекомендую Стартовый репозиторий Александра Рилсена и Репозиторий плагинов Carrot2 в качестве отправных точек.

Чтобы узнать больше о локальном хешировании, я рекомендую Лекционные видео Виктора Лавренко, презентации Эрика Бернхардссона о Annoy и его репозиторий Ann-Benchmarks.

Хотите перейти к карьере в области разработки данных?
Узнайте больше о программе Insight Data Engineering Fellows Program в Бостоне, Нью-Йорке и Кремниевой долине. Подайте заявку сегодня , или подпишитесь на обновления программы.