Узнайте, как информация о сходстве может быть включена в хэш-функцию
Поиск по сходству – это задача, в которой задан запрос, целью которого является поиск наиболее похожих на него документов среди всех документов базы данных.
Введение
В науке о данных поиск по сходству часто появляется в домене НЛП, поисковых системах или рекомендательных системах, где для запроса необходимо найти наиболее релевантные документы или элементы. Существует множество различных способов повышения производительности поиска в огромных объемах данных.
В предыдущих частях этой серии статей мы обсуждали инвертированный файловый индекс, квантование продукта и HNSW, а также их совместное использование для повышения качества поиска. В этой главе мы рассмотрим принципиально иной подход, сохраняющий как высокую скорость, так и качество поиска.
Локальное конфиденциальное хэширование (LSH) – это набор методов, которые используются для уменьшения области поиска путем преобразования векторов данных в хеш-значения с сохранением информации об их сходстве.
Мы собираемся обсудить традиционный подход, который состоит из трех шагов:
- Shingling: кодирование исходных текстов в векторы.
- MinHashing: преобразование векторов в специальное представление, называемое подписью, которое можно использовать для сравнения сходства между ними.
- Функция LSH: хэширование блоков подписи в разные сегменты. Если сигнатуры пары векторов хотя бы раз попадают в одно и то же ведро, они считаются кандидатами.
Мы собираемся постепенно погружаться в детали каждого из этих шагов на протяжении всей статьи.
Черепица
Shingling – это процесс сбора k-граммов по заданным текстам. k-gram – это группа из k последовательных токенов. В зависимости от контекста токены могут быть словами или символами. Конечная цель шинлинга — использовать собранные k-граммы для кодирования каждого документа. Для этого мы будем использовать однократное кодирование. Тем не менее, другие методы кодирования также могут быть применены.
Во-первых, собираются уникальные k-граммы для каждого документа. Во-вторых, для кодирования каждого документа необходим словарь, представляющий набор уникальных k-грамм во всех документах. Затем для каждого документа создается вектор нулей с длиной, равной размеру словаря. Для каждой появляющейся k-граммы в документе идентифицируется ее позиция в словаре, и в соответствующую позицию вектора документа помещается «1». Даже если одна и та же k-грамма встречается в документе несколько раз, это не беда: значение в векторе всегда будет равно 1.
Минхеширование
На данном этапе исходные тексты были векторизованы. Сходство векторов можно сравнить с помощью индекса Жаккара. Помните, что индекс Жаккара двух наборов определяется как количество общих элементов в обоих наборах, деленное на длину всех элементов.
Если берется пара закодированных векторов, пересечение в формуле для индекса Жаккара — это количество строк, каждая из которых содержит 1 (т. е. k-грамма появляется в обоих векторах), а объединение — это количество строк. строки хотя бы с одной единицей (k-грамма присутствует хотя бы в одном из векторов).
Текущая проблема сейчас — разреженность закодированных векторов. Вычисление оценки сходства между двумя горячими кодированными векторами заняло бы много времени. Преобразование их в плотный формат сделало бы более эффективной работу с ними позже. В конечном счете, цель состоит в том, чтобы разработать такую функцию, которая будет преобразовывать эти векторы в меньшую размерность, сохраняя при этом информацию об их сходстве. Метод, создающий такую функцию, называется MinHashing.
MinHashing – это хеш-функция, которая переставляет компоненты входного вектора, а затем возвращает первый индекс, в котором компонент переставленного вектора равен 1.
Для получения плотного представления вектора, состоящего из n чисел, можно использовать n minhash-функций для получения n значений minhash, которые формируют подпись.
Поначалу это может показаться неочевидным, но несколько значений minhash можно использовать для приблизительного сходства Жаккара между векторами. На самом деле, чем больше значений minhash используется, тем точнее аппроксимация.
Это просто полезное наблюдение. Оказывается, за кадром кроется целая теорема. Давайте разберемся, почему индекс Жаккара можно рассчитать с помощью подписей.
Доказательство утверждения
Предположим, что данная пара векторов содержит только строки типа 01, 10 и 11. Затем выполняется случайная перестановка этих векторов. Поскольку во всех строках существует хотя бы одна единица, то при вычислении обоих хеш-значений по крайней мере один из этих двух процессов вычисления хэш-значения остановится на первой строке вектора с соответствующим хэш-значением, равным 1.
Какова вероятность того, что второе значение хеша будет равно первому? Очевидно, это произойдет только в том случае, если второе значение хеша также равно 1. Это означает, что первая строка должна быть типа 11. Поскольку перестановка производилась случайным образом, вероятность такого события равна P = count(11) / (count(01) + count(10) + количество(11)). Это выражение абсолютно совпадает с формулой индекса Жаккара. Поэтому:
Вероятность получения одинаковых хеш-значений для двух двоичных векторов на основе случайной перестановки строк равна индексу Жаккара.
Однако, доказывая утверждение выше, мы предполагали, что исходные векторы не содержат строк типа 00. Понятно, что строки типа 00 не меняют значение индекса Жаккара. Точно так же вероятность получения одинаковых хеш-значений с включенными строками типа 00 не влияет на это. Например, если первая переставленная строка равна 00, то алгоритм minhash просто игнорирует ее и переключается на следующую строку до тех пор, пока в строке не будет хотя бы одна единица. Конечно, строки типа 00 могут привести к другим хеш-значениям, чем без них, но вероятность получения одинаковых хеш-значений остается прежней.
Мы доказали важное утверждение. Но как можно оценить вероятность получения одинаковых значений minhash? Определенно можно сгенерировать все возможные перестановки для векторов, а затем вычислить все значения минхэша, чтобы найти желаемую вероятность. По понятным причинам это неэффективно, поскольку количество возможных перестановок для вектора размера n равно n!. Тем не менее вероятность можно оценить приблизительно: давайте просто воспользуемся многими хеш-функциями, чтобы сгенерировать столько-то хэш-значений.
Индекс Жаккара двух бинарных векторов примерно равен количеству соответствующих значений в их сигнатурах.
Легко заметить, что использование более длинных подписей приводит к более точным вычислениям.
Функция ЛШ
В настоящий момент мы можем преобразовать необработанные тексты в плотные подписи равной длины, сохраняя информацию о сходстве. Тем не менее, на практике такие плотные сигнатуры все еще обычно имеют большие размерности, и сравнивать их напрямую было бы неэффективно.
Рассмотрим n = 10⁶ документы с их подписями длиной 100. Если предположить, что для хранения одного номера подписи требуется 4 байта, то для всей подписи потребуется 400 байт. Для хранения n = 10⁶ документов требуется 400 МБ места, что в действительности выполнимо. Но сравнение каждого документа друг с другом методом грубой силы потребует примерно 5 * 10¹¹ сравнений, что слишком много, особенно когда n еще больше.
Чтобы избежать этой проблемы, можно построить хеш-таблицу для ускорения поиска, но даже если две подписи очень похожи и отличаются только 1 позицией, они все равно, вероятно, будут иметь разные хэши (поскольку остатки векторов, вероятно, будут разными). ). Однако обычно мы хотим, чтобы они попадали в одно и то же ведро. И тут на помощь приходит ЛШ.
Механизм LSH создает хеш-таблицу, состоящую из нескольких частей, которая помещает пару подписей в одно и то же ведро, если у них есть хотя бы одна соответствующая часть.
LSH берет матрицу сигнатур и горизонтально делит ее на равные b части, называемые полосами, каждая из которых содержит r строк. Вместо включения всей подписи в единую хэш-функцию подпись делится на b частей, и каждая субподпись обрабатывается хеш-функцией независимо. Как следствие, каждая из субподписей попадает в отдельные корзины.
Если есть хотя бы одно столкновение между соответствующими подвекторами двух разных сигнатур, сигнатуры считаются кандидатами. Как видим, это условие является более гибким, так как для рассмотрения векторов в качестве кандидатов не обязательно, чтобы они были абсолютно равными. Тем не менее, это увеличивает количество ложных срабатываний: пара разных подписей может иметь одну соответствующую часть, но в целом быть совершенно разными. В зависимости от проблемы всегда лучше оптимизировать параметры b, r и k.
Частота ошибок
С помощью LSH можно оценить вероятность того, что две подписи со сходством s будут рассматриваться как кандидаты с учетом количества полос b и количества строк r в каждой полосе. Найдем его формулу в несколько шагов.
Обратите внимание, что в формуле не учитываются коллизии, когда разные подвекторы случайно попадают в одно и то же ведро. Из-за этого реальная вероятность того, что подписи являются кандидатами, может незначительно отличаться.
Пример
Чтобы лучше понять только что полученную формулу, рассмотрим простой пример. Рассмотрим две подписи длиной 35 символов, которые поровну разбиты на 5 полос по 7 строк в каждой. Вот таблица, которая представляет вероятность наличия хотя бы одной равной полосы на основе их сходства Жаккара:
Мы замечаем, что если две похожие подписи имеют сходство Жаккара 80%, то они имеют соответствующую полосу в 93,8% случаев (истинно положительные результаты). В остальных 6,2% случаев такая пара сигнатур является ложноотрицательной.
Теперь возьмем две разные подписи. Например, они похожи только на 20%. Следовательно, они являются ложноположительными кандидатами в 0,224% случаев. В остальных 99,776% случаев у них нет похожей полосы, поэтому они являются истинно отрицательными.
Визуализация
Давайте теперь визуализируем связь между сходством s и вероятностью P того, что две подписи станут кандидатами. Обычно с более высоким сходством подписей s, подписи должны иметь более высокую вероятность быть кандидатами. В идеале это должно выглядеть так:
На основании полученной выше формулы вероятности типичная линия будет выглядеть так, как показано на рисунке ниже:
Можно варьировать количество полос b для смещения линии на рисунке влево или вправо. Увеличение b смещает линию влево и приводит к большему FP, уменьшение — смещает ее вправо и приводит к большему FN. Важно найти хороший баланс, в зависимости от проблемы.
Эксперименты с разным количеством полос и рядов
Ниже построено несколько линейных графиков для разных значений b и r. Всегда лучше настроить эти параметры в зависимости от конкретной задачи, чтобы успешно получить все пары похожих документов и игнорировать документы с разными подписями.
Заключение
Мы рассмотрели классическую реализацию метода LSH. LSH значительно оптимизирует скорость поиска за счет использования низкоразмерных представлений сигнатур и быстрого механизма хеширования для уменьшения области поиска кандидатов. В то же время это происходит за счет точности поиска, но на практике разница обычно незначительна.
Однако LSH уязвим для данных высокой размерности: больше размерностей требует большей длины сигнатуры и большего количества вычислений для поддержания хорошего качества поиска. В таких случаях рекомендуется использовать другой индекс.
На самом деле существуют разные реализации LSH, но все они основаны на одной и той же парадигме преобразования входных векторов в хэш-значения с сохранением информации об их сходстве. По сути, другие алгоритмы просто определяют другие способы получения этих хеш-значений.
Случайные проекции — это еще один метод LSH, который будет рассмотрен в следующей главе и реализован в виде индекса LSH в библиотеке Faiss для поиска по сходству.
Ресурсы
- Хеширование с учетом местоположения | Эндрю Уайли | 2 декабря 2013 г.
- Интеллектуальный анализ данных | Хеширование с учетом местоположения | Университет Сегеда
- Репозиторий Файса
Все изображения, если не указано иное, принадлежат автору.
