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

Реальные проблемы

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

Такие данные обычно характеризуются высокой размерностью. Например: модель новостей Google обучается на наборе данных, состоящем примерно из 100 миллиардов слов. Модель содержит 300-мерные векторы на 3 миллиона слов и словосочетаний.

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

Веб-поиск и интеллектуальный анализ текста
Классификация документов
Плагиат
Чат-боты

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

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

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

Обнаружение почти дублирования: LSH обычно используется для дедупликации большого количества документов, веб-страниц и других файлов.
Полногеномное ассоциативное исследование. Биологи часто используют LSH для выявления похожих выражений генов в геномных базах данных.
Широкомасштабный поиск изображений: Google использовал LSH вместе с PageRank для создания своей технологии поиска изображений VisualRank.
Отпечатки аудио / видео. В мультимедийных технологиях LSH широко используется в качестве метода снятия отпечатков пальцев для аудио- и видеоданных.
Обнаружение мошенничества: Uber использует LSH для быстрого обнаружения злоупотреблений платформой, от спама до поддельных учетных записей и мошенничества с платежами.

Представление документов в виде числовых векторов

Векторные пространства являются фундаментальными во многих приложениях НЛП. Если мы хотим представить документ, чтобы мы могли применять математические модели для анализа содержимого, нам нужно закодировать его как вектор, где размеры - это слова или n-граммы, которые формируют документ.

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

Документ 1. Кот преследует крысу
Документ 2. Собака преследует кошку
Запрос: Кто гонится за крысой

После предварительной обработки документов мы представляем их в виде векторов слов.

Документ 1: (кот, погоня, крыса)
Документ 2: (собака, погони, кошка)
Запрос: (кто, погоня, крыса)

Соответствующий документ, который нужно извлечь, будет тем документом, который имеет более высокую оценку сходства между.

оценка сходства (Document1, Query) ›оценка подобия (Document2, Query)

Мы можем представить указанные выше векторы документов в числовом формате как матрицу условных документов.

Есть некоторые дополнительные шаги, такие как Stemming, лемматизация, TF-IDF при создании матрицы документа терминов, которые мы пропустим, чтобы упростить задачу.

А теперь представьте, если бы мы хотели отобразить данные реального мира, например, весь корпус Википедии содержит около 3 миллиардов слов, а набор данных новостей Google - более 100 миллиардов слов. Вы можете найти оба этих набора данных по адресу https://code.google.com/archive/p/word2vec/.

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

Проклятие размерности

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

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

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

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

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

Что такое хеширование

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

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

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

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

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

Что зависит от местности

Значение слова зависит от контекста или «местонахождения» слова, в котором оно используется.

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

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

В зависимости от типа данных существуют разные функции хеширования с учетом местоположения:

Битовая выборка LSH (расстояние Хэмминга)
MinHashing LSH (сходство по Жаккару)
Евклидово и манхэттенское LSH (евклидово (L2) и манхэттенское (L1) расстояния)
Кластеризация или K-среднее LSH (изучает хэш-функции с помощью K-средних)
Знаковые случайные проекции (косинусное подобие)

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

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

Мотивация к LSH

Предположим, нам нужно найти почти одинаковые документы среди N = 1 миллиона документов.

Наивно, нам пришлось бы вычислять попарные сходства для каждой пары документов, то есть N (N-1) / 2 ≈ 5 * 10¹¹ сравнений. Даже с самыми продвинутыми процессорами на это уйдут дни.

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

Даны документы D1 и D2
Если мы сможем найти хеш-функцию h такую, что:
если sim (D1, D2) высокий, то с большой вероятностью h (D1) = h (D2)
если sim (D1, D2) низкий, то с большой вероятностью h (D1) ≠ h (D2)
Затем мы могли бы хэшировать документы в сегменты и ожидать, что «большинство» пар почти дублированных документов будут хешировать в один и тот же сегмент, а затем у нас есть набор пар-кандидатов документов в каждом сегменте, чтобы увидеть, действительно ли они похожи.

Косинусное расстояние для сходства документов

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

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

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

Косинус между векторами можно вычислить по следующей формуле.

Функция подобия косинуса выражается как:

И 𝐵 представляют собой векторы слов, а 𝐴𝑖 или 𝐵𝑖 представляют индекс i этого вектора. & Обратите внимание, что если A и B идентичны, вы получите 𝑐𝑜𝑠 (𝜃) = 1.

В противном случае, если они полностью противоположны, то есть 𝐴 = −𝐵, тогда вы получите 𝑐𝑜𝑠 (𝜃) = - 1.
Если вы получили 𝑐𝑜𝑠 (𝜃) = 0, это означает, что они ортогональны (или перпендикулярны).
Цифры от 0 до 1 указывают оценку сходства.
Числа от -1 до 0 указывают на оценку несходства.

LSH для косинусного подобия

Знаковые случайные проекции (SRP) выводят двоичные значения, но SRP чувствителен к угловому расстоянию между векторами.

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

Подписи для косинусного расстояния

Выберите некоторое количество случайных векторов и хешируйте свои данные для каждого вектора. Результатом является подпись (эскиз) +1 и -1 для каждой точки данных.

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

Затем подпись может быть усилена с помощью конструкций И и ИЛИ или хеш-функции.

На рисунке ниже показано, почему случайная проекция со знаком чувствительна к углам.

Вероятность того, что h (v1) ≠ h (v2) - это вероятность того, что случайно выбранная линия окажется между V1 и V2.

Если мы случайно выберем угол, есть вероятность θ / π, что он окажется между двумя точками и разделит их.

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

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

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

Заключение

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

Мы видим, как LSH может быть высокоэффективным методом поиска или запроса крупномасштабных текстовых данных. LSH может работать с данными большого размера, эффективно уменьшая размеры и ускоряя поиск за постоянное время.

LSH используется многими приложениями реального мира для запроса или поиска в больших базах данных в любом масштабе.