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

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

Простое сокращение, которое позволяет использовать библиотеки для поиска ближайшего соседа для эффективного обнаружения векторов с большим внутренним произведением

Мотивация

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

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

Эти две проблемы связаны. Как мы обсудим ниже, если все векторы имеют одинаковую норму, две проблемы становятся идентичными. Но в большинстве приложений векторы имеют разные нормы, и две проблемы становятся разными. На высоком уровне при поиске ближайшего соседа мы ищем векторы с почти одинаковым значением. В то время как при максимальном поиске внутреннего продукта предпочтение отдается векторам, между которыми есть небольшой угол.

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

Формальная установка

Обычно поиск ближайшего соседа формулируется как проблема для векторов в евклидовом пространстве. Норма вектора x определяется как

Для базы данных D ближайшим соседом для вектора запроса q является вектор x в D, такой что

Максимальный поиск внутреннего продукта определяется как:

Мы предполагаем, что нам дана статическая массивная база данных D, которая будет часто запрашиваться. Например, D состоит из всех фильмов Netflix, представленных векторами.

Векторы единичной нормы

Если все векторы в базе данных D имеют единичную норму, то есть || u || = 1, то две проблемы становятся эквивалентными. Заметьте, что

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

Простая редукция для общего случая

В [1] предложена следующая простая редукция:

φ - максимальная норма всех векторов в базе данных. Мы добавляем в качестве первой координаты к каждому вектору разницу между φ и нормой вектора. (Это всегда будет неотрицательным, поскольку φ - максимальная норма.) Мы добавляем 0 в качестве первой координаты к вектору запроса.

Для нормы преобразованных векторов имеем:

Кроме того, поскольку первая координата q_z равна 0, следует, что

Следовательно, евклидово расстояние между векторами в новом пространстве можно переписать как

Мы видим, что единственный термин, который зависит от индекса запроса i, - это внутренний продукт x_i ^ T * q. Следовательно, вектор ближайшего соседа z_i в преобразованном пространстве будет соответствовать вектору с максимальным внутренним произведением x_i в исходном пространстве.

Обратное преобразование

В [1] авторы также показывают, как свести задачу поиска ближайшего соседа к поиску максимального внутреннего продукта. Заинтересованного читателя отсылаем к теореме 2 в [1], но я не буду здесь ее обсуждать, потому что она вряд ли имеет практическое значение.

Выполнение

Для базы данных D просто примените вышеуказанное преобразование ко всем векторам в D. Затем, по запросу q, вызовите алгоритм поиска ближайшего соседа.

Кодировать преобразование действительно просто:

def transform(vecs):
    maxnorm = max([np.linalg.norm(v) for v in vecs])
    new_vecs = []
    for v in vecs:
        new_vecs.append(
           np.insert(v, 0, np.sqrt(maxnorm**2-np.linalg.norm(v)**2))
        )
    return new_vecs

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

from sklearn.neighbors import NearestNeighbors
X = np.array(new_vecs)
nbrs = NearestNeighbors(n_neighbors=1, algorithm='kd_tree').fit(X)
distances, indices = nbrs.kneighbors(np.array([q]))

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

[1] Йорам Бахрах, Иегуда Финкельштейн, Ран Гилад-Бахрах, Лиран Кацир, Ноам Кенигштейн, Нир Найс, Ульрих Паке. Ускорение рекомендательной системы Xbox с помощью евклидова трансформации для пространств внутреннего продукта. RecSys 2014, доступно здесь