Два алгоритма для поиска ближайшего соседа с локально-чувствительным хешированием, какой?

Question

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

1- Используйте L количество хеш-таблиц с L числом случайных функций LSH, таким образом увеличивая вероятность того, что два документа, которые похожи, получат одну и ту же подпись Например, если два документа похожи на 80%, то с 80% вероятностью они получат одинаковую подпись от одной функции LSH. Однако, если мы используем несколько функций LSH, тогда больше шансов получить одну и ту же подпись для документов от одной из функций LSH. Этот метод объясняется в википедии, и я надеюсь, что мое понимание верно:

http://en.wikipedia.org/wiki/Locality-sensitive_hashing

2. В другом алгоритме используется метод из статьи (раздел 5), который называется: "Методы оценки подобия из алгоритмов округления" Моисея С. Чарикара. Он основан на использовании одной функции LSH для генерации подписи, а затем применения к ней перестановок P и сортировки списка. На самом деле я не очень хорошо понимаю этот метод и надеюсь, что кто-нибудь сможет уточнить его.

Мой главный вопрос: зачем кому-то использовать второй метод, а не первый? Как я считаю, это проще и быстрее.

Я действительно надеюсь, что кто-то может помочь!!!

РЕДАКТИРОВАТЬ: На самом деле я не уверен, что @Raff. Эдвард смешивал между "первым" и "вторым". Потому что только во втором методе используется радиус, а в первом - новое хеш-семейство g, состоящее из хеш-семейства F. Пожалуйста, проверьте ссылку в Википедии. Они просто использовали много g-функций для генерации разных сигнатур, а затем для каждой g-функции имеется соответствующая хеш-таблица. Чтобы найти ближайшего соседа точки, просто дайте точке пройти через g функции и проверьте соответствующие хеш-таблицы на наличие коллизий. Таким образом, как я понял это как больше функции... больше шансов для столкновений.

Я не нашел упоминания о радиусе для первого метода.

Для второго метода они генерируют только одну сигнатуру для каждого вектора признаков и затем применяют к ним P-перестановки. Теперь у нас есть P списков перестановок, каждая из которых содержит n подписей. Затем они сортируют каждый список из P. После этого, получив заданную точку запроса q, они генерируют для нее сигнатуру и затем применяют к ней перестановки P, а затем используют бинарный поиск в каждом переставленном и отсортированном P-списке, чтобы найти наиболее похожую сигнатуру для запрос q. Я пришел к выводу, прочитав много статей об этом, но я до сих пор не понимаю, зачем кому-то использовать такой метод, потому что кажется, что он не быстро находит расстояние Хэмминга!!!!

Для меня я бы просто сделал следующее, чтобы найти ближайшего соседа для точки запроса q. Учитывая список подписей N, я сгенерирую подпись для точки запроса q, а затем просканирую список N и вычислю расстояние Хемминга между каждым элементом в N и подписью q. Таким образом, я бы в конечном итоге с ближайшим соседом для q. И это занимает O(N)!!!

Answer 1

Ваше понимание первого немного неверно. Вероятность столкновения не пропорциональна подобию, но независимо от того, меньше ли оно заранее определенного радиуса. Цель состоит в том, чтобы все, что находится в радиусе, имело высокую вероятность столкновения, а все, что находится за пределами радиуса * (1+eps), будет иметь низкую вероятность столкновения (а область между ними немного мутная).

Первый алгоритм довольно сложно реализовать хорошо, но он может дать хорошие результаты. В частности, первый алгоритм предназначен для метрик L1 и L2 (и технически еще нескольких).

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

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

Второй, на самом деле, гораздо проще для понимания и реализации, чем первый, статья просто очень многословна.

Краткая версия: возьмите случайный вектор V и присвойте каждому индексу независимую случайную единицу нормального значения. Создайте столько векторов, сколько хотите, чтобы длина подписи была. Подпись является признаком каждого индекса при создании продукта Matrix Vector. Теперь расстояние Хэмминга между любыми двумя сигнатурами связано с косинусным сходством между соответствующими точками данных.

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

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

РЕДАКТИРОВАТЬ: Отвечая на ваши изменения. Статья в Википедии не очень хороша для LSH. Если вы читаете оригинальную статью, первый метод, о котором вы говорите, работает только для фиксированного радиуса. Хеш-функции затем создаются на основе этого радиуса и объединяются для увеличения вероятности сближения точек при столкновении. Затем они строят систему для выполнения k-NN поверх этого, определяя максимальное значение k, которое они хотят, и затем находя наибольшее разумное расстояние, на котором они находят k-го ближайшего соседа. Таким образом, поиск радиуса с большой вероятностью вернет набор k-NN. Чтобы ускорить это, они также создают несколько очень маленький радиус, так как плотность часто неодинакова, и чем меньше радиус, который вы используете, тем быстрее результат.

Раздел Википедии, на который вы ссылаетесь, взят из описания статьи для раздела "Стабильное распределение", в котором представлена ​​хеш-функция для поиска радиуса r=1.

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

Если вам нужна помощь, то убедить себя в хорошей форме можно быстрее, даже если вы все еще использовали грубую силу - просто взгляните на это так: допустим, у среднего разреженного документа есть 40 общих слов с другим документом (по моему опыту, это очень консервативное число). У вас есть n документов для сравнения. В таком случае сходство косых сил косинуса будет включать около 40*n умножений с плавающей точкой (и некоторую дополнительную работу). Если у вас есть 1024-битная подпись, то это всего 32 целых числа. Это означает, что мы могли бы выполнять поиск LSH методом грубой силы в 32*n целочисленных операциях, которые значительно быстрее, чем операции с плавающей запятой.

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

Ваш O(n) - наивный способ, который я использовал в своем блоге. И это быстро. Однако, если вы отсортируете биты до этого, вы можете выполнить двоичный поиск по O(log(n)). Даже если у вас есть L из этих списков, L << n, и так должно быть быстрее. Единственная проблема заключается в том, что он приближает вас к NN Хэмминга, который уже аппроксимирует сходство косинусов, поэтому результаты могут стать немного хуже. Это зависит от того, что вам нужно.