Цель

Я предполагаю, что вы слышали об алгоритме k-ближайших соседей для задачи классификации (см. Учебник: модель K-ближайших соседей).

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

Существуют очень продвинутые алгоритмы поиска ближайшего соседа, такие как ScaNN от Google и Faiss от Facebook.

Это алгоритм поиска приближенных ближайших соседей (ANN), потому что они ускоряют производительность поиска во времени, жертвуя некоторым запасом точности. Общий подход обычно заключается в создании индекса для ускорения поиска, чтобы система никогда не сканировала весь набор данных.

В этой статье будет рассмотрен пример простой идеи реализации поиска ANN.

Хэш-таблицы

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

Например, если вы знакомы с Набором данных Iris Flow, то входное измерение равно 4, потому что есть 4 функции:

  • длина чашелистика в см
  • ширина чашелистика в см
  • длина лепестка в см
  • ширина лепестка в см

Если у нас может быть функция f(x1, x2, x3, x4), которая возвращает один int32. Тогда это считается хэш-функцией.

Разделение гиперплоскостей

Следующая идея, которая нам нужна, — это разделяющее гиперпространство. В примере с Iris Flow мы можем думать о гиперместе в 4-мерном пространстве, которое может разделить пространство на 2.

Каждая гиперплоскость может быть представлена ​​своим нормальным (ортогональным) вектором.

Взяв скалярное произведение вектора на вектор нормали и проверив сигнал, мы можем сказать, попадает ли вектор на положительную или отрицательную сторону гиперплоскости.

  • dot_product(нормальный вектор, положительный вектор) › 0. Синий вектор падает на положительную сторону гиперплоскости
  • dot_product(нормальный вектор, отрицательный вектор) ‹ 0. Красный вектор падает на положительную сторону гиперплоскости
  • dot_product(нормальный вектор, нулевой вектор) = 0. Зеленый вектор падает на вершину гиперплоскости

Вывод здесь заключается в том, что проверить, на какую сторону гиперместа падает вектор, довольно просто, взяв скалярное произведение.

Использование гиперплоскостей в качестве механизма хеширования

Поскольку каждая гиперплоскость может возвращать двоичное значение, которое принимает вектор в 4-мерном пространстве. Мы можем использовать несколько гиперплоскостей для кодирования нескольких цифр целого числа. Таким образом, int32 может представлять 32 гиперплоскости.

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

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

Хеширование с учетом местоположения (LSH)

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

Приблизительный поиск ближайшего соседа

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

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

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

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

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

Заключение

Мы показали фундаментальную идею того, как ИНС ускоряют поиск ближайшего соседа. Это имеет широкое применение при работе со встроенным пространством в системах ML и производственных системах ML, которые необходимо обслуживать в режиме реального времени.

Первоначально опубликовано на https://datajello.com 6 сентября 2022 г.