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

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

Введение

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

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



Поиск сходства, часть 5: Хеширование с учетом местоположения (LSH)
Исследуйте, как информация о сходстве может быть включена в хеш-функциюtowardsdatascience.com



Классический алгоритм LSH создает сигнатуры, отражающие информацию об индексе Жаккара векторов.



Поиск сходства, часть 6: случайные прогнозы с помощью LSH Forest
Понимание того, как хешировать данные и отражать их сходство путем построения случайных гиперплоскостейtowardsdatascience.com



Метод случайных проекций строит лес гиперплоскостей, сохраняя косинусное подобие векторов.

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

В качестве бонуса в конце мы рассмотрим, как евклидово расстояние можно включить в LSH.

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

Примечание. Косинусное расстояние формально определяется в диапазоне [0, 2]. Для простоты мы сопоставим его с интервалом [0, 1], где 0 и 1 обозначают наименьшее и максимальное возможное сходство соответственно.

Формальное определение LSH

Учитывая метрику расстояния d, H называется (d₁, d₂, p₁, p₂)-чувствительной функцией LSH, если для случайно выбранных объектов x и y выполняются следующие условия:

  • Если d(x, y) ≤ d₁, то p(H(x) = H(y)) ≥ p₁, т. е. H(x) = H(y) с вероятностью не менее p₁.
  • Если d(x, y) ≥ d₂, то p(H(x) = H(y)) ≤ p₂, т. е. H(x) = H(y) с вероятностью не выше p₂.

Давайте разберемся, что означают эти утверждения. Когда два вектора подобны, расстояние между ними мало. По сути, первое утверждение гарантирует, что вероятность их хэширования в одно и то же ведро выше определенного порога. Таким образом устраняются некоторые ложноотрицательные результаты: если расстояние между двумя векторами больше, чем d₁, то вероятность их хэширования в одно и то же ведро всегда меньше, чем p₁. И наоборот, второй оператор контролирует ложные срабатывания: если два вектора не похожи и расстояние между ними больше, чем d₂, то они имеют верхнюю вероятность p₂ порог появления в том же сегменте.

Учитывая приведенное выше утверждение, мы обычно хотим, чтобы в системе выполнялись следующие утверждения:

  • p₁ должен быть как можно ближе к 1, чтобы уменьшить количество ложноотрицательных результатов.
  • p₂ должен быть как можно ближе к 0, чтобы уменьшить количество ложных срабатываний.
  • Разрыв между d₁ и d₂ должен быть как можно меньше, чтобы уменьшить интервал, в котором нельзя сделать вероятностные оценки данных.

Иногда приведенное выше утверждение вводится с использованием термина сходства s вместо расстояния d:

Учитывая метрику подобия s, H называется (s₁, s₂, p₁, p₂)-чувствительной функцией LSH, если для случайно выбранных объектов x и y выполняются следующие условия:

  • Если s(x, y) ≥ s₁, то p(H(x) = H(y)) ≥ p₁, т. е. H(x) = H(y) с вероятностью не менее p₁.
  • Если s(x, y) ≤ s₂, то p(H(x) = H(y)) ≤ p₂, т. е. H(x) = H(y) с вероятностью не выше p₂.

Примечание. В этой статье будут использоваться оба обозначения (d₁, d₂, p₁, p₂) и (s₁, s₂, p₁, p₂). На основе букв, используемых в обозначениях в тексте, должно быть ясно, подразумевается ли расстояние d или сходство s. По умолчанию используется обозначение (d₁, d₂, p₁, p₂).

пример ЛШ

Для большей ясности докажем следующее утверждение:

Если метрика расстояния s является индексом Жаккара, то H является (0,6, 0,6, 0,4, 0,4)-чувствительной функцией LSH. В принципе, эквивалентные утверждения должны быть доказаны:

  • Если d(x, y) ≤ 0,6, то p(H(x) = H(y)) ≥ 0,4
  • Если d(x, y) ≥ 0,6, то p(H(x) = H(y)) ≤ 0,4

Из 5-й части этой серии статей мы знаем, что вероятность получения одинаковых хеш-значений для двух бинарных векторов равна подобию Жаккара. Следовательно, если два вектора похожи хотя бы на 40%, то гарантируется, что вероятность получения одинаковых значений хеш-функции также будет не менее 40%. Между тем, сходство Жаккара не менее 40% эквивалентно индексу Жаккара не более 60%. В результате первое утверждение доказано. Аналогичные размышления можно провести и для второго утверждения.

Этот пример можно обобщить в теорему:

Теорема. Если d — индекс Жаккара, то H — это (d₁, d₂, 1 — d₁, 1 — d₂)-семейство функций LSH.

Аналогично на основе результатов, полученных из части 6, можно доказать еще одну теорему:

Теорема. Если s — косинусное сходство (между -1 и 1), то H — это (s₁, s₂, 1 — arccos(s₁)/180, 1 — arccos(d₂)/180)-семейство LSH-функций.

Объединение функций LSH

Давайте обратимся к полезным концепциям, которые мы узнали в предыдущих частях LSH:

  • Возвращаясь к части 5 о минхешировании, каждый вектор был разбит на несколько полос, каждая из которых содержала набор строк. Чтобы пара векторов считалась кандидатами, должна существовать по крайней мере одна полоса, в которой все строки векторов равны.
  • Что касается части 6 о случайных проекциях, два вектора считались кандидатами только в том случае, если существовало по крайней мере одно дерево, в котором все случайные проекции не разделяли исходные векторы.

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

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

И оператор

Учитывая n независимых LSH-функций H₁, H₂, … Hₙ, оператор И рассматривает два вектора как пару-кандидатов, только если все из n соответствующих хэш-значений обоих векторов равны. В противном случае векторы не рассматриваются как кандидаты.

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

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

Теорема. Рассмотрим r независимых (s₁, s₂, p₁, p₂)-чувствительных функций LSH. Объединение этих r LSH-функций с оператором AND приводит к новой LSH-функции с такими параметрами, как

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

оператор ИЛИ

Учитывая n независимых LSH-функций H₁, H₂, … Hₙ, оператор ИЛИ рассматривает два вектора как пару-кандидатов только в том случае, если по крайней мере одно из n соответствующих хэш-значений обоих векторов равно равный. В противном случае векторы не рассматриваются как кандидаты.

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

Теорема. Рассмотрим b независимые (d₁, d₂, p₁, p₂)-функции LSH семейства. Сочетание этих b LSH-функций с оператором AND приводит к новой LSH-функции с такими параметрами, как

Мы не будем доказывать эту теорему, потому что полученная аналогичная формула вероятности была получена и объяснена в части 5 этой серии статей.

Состав

Имея операции И и ИЛИ, можно комбинировать их вместе различными способами, чтобы лучше контролировать ложноположительные и ложноотрицательные ставки. Давайте представим, что функции r LSH используются комбинатором И, а функции b LSH используются комбинатором ИЛИ. Используя эти основные комбинаторы, можно построить две разные композиции:

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

Пример композиции

Давайте рассмотрим пример, чтобы понять, как комбинации И и ИЛИ могут значительно повысить производительность. Предположим, что используется комбинация ИЛИ-И с параметрами b = 4 и r = 8. Основываясь на соответствующей формуле выше, мы можем оценить, как преобразовывается начальная вероятность двух векторов-кандидатов после композиции:

Например, если при определенном значении сходства между двумя векторами одна функция LSH хеширует их в один и тот же сегмент в 40% случаев, то после композиции ИЛИ-И они будут хешироваться в 32,9 % случаев.

Чтобы понять, что такого особенного в композициях, рассмотрим (0,4, 1,7, 0,8, 0,2)-зависимую функцию LSH. После преобразования ИЛИ-И функция LSH преобразуется в (0,4, 1,7, 0,0148, 0,987)-чувствительный формат.

По сути, если бы изначально два вектора были очень похожи и имели расстояние менее 0,4, то они считались бы кандидатами в 80% случаев. Однако с применением композиции они теперь являются кандидатами в 98,7% сценариев, что приводит к гораздо меньшему количеству ложноотрицательных ошибок!

Аналогично, если два вектора сильно отличаются друг от друга и имеют расстояние больше 1,7, то теперь они считаются кандидатами только в 1,48% случаев (по сравнению с 20% ранее). Таким образом, частота ложных срабатываний снижается в 13,5 раз! Это огромное улучшение!

В общем, имея (d₁, d₂, p₁, p₂)-зависимую функцию LSH, можно преобразовать ее в (d₁, d₂, p'₁, p'₂ )формат, в котором p'₁близок к 1, а p'₂близок к 0. Чтобы приблизиться к 1 и 0, обычно требуется большее количество композиций. использовал.

LSH для других показателей расстояния

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

Тем не менее, схема LSH существует для евклидова расстояния — одной из наиболее часто используемых метрик в машинном обучении. Поскольку он часто используется, мы собираемся изучить, как получить хеш-значения для евклидова расстояния. Используя введенные выше теоретические обозначения, мы докажем важное свойство LSH для этой метрики.

LSH для евклидова расстояния

Механизм хеширования точек в евклидовом пространстве включает их проецирование на случайную прямую. Алгоритм предполагает, что

  • Если две точки расположены относительно близко друг к другу, то их проекции также должны быть близки.
  • Если две точки находятся далеко друг от друга, то и их проекции должны быть далеко.

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

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

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

Геометрически возможно доказать, что если a — длина одного отрезка в евклидовом пространстве, то H равно (a / 2, 2a, ½, ⅓)-чувствительная функция LSH.

Заключение

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

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

Ресурсы

Все изображения, если не указано иное, принадлежат автору.