Как понять локальное хеширование?

156

Я заметил, что LSH, кажется, хороший способ найти похожие элементы с большими свойствами.

После прочтения статьи http://www.slaney.org/malcolm/yahoo/Slaney2008-LSHTutorial.pdf я все еще не понимаю эти формулы.

Кто-нибудь знает блог или статью, которая объясняет, что легкий путь?

WoooHaaaa
источник
3
Прочтите Ульман, глава 3 - « НАЙТИ
ПОХОЖИЕ

Ответы:

250

Лучший учебник, который я видел для LSH, находится в книге: Mining of Massive Datasets. Проверьте главу 3 - Поиск похожих предметов http://infolab.stanford.edu/~ullman/mmds/ch3a.pdf

Также я рекомендую следующий слайд: http://www.cs.jhu.edu/%7Evandurme/papers/VanDurmeLallACL10-slides.pdf . Пример на слайде помогает мне понять хэширование сходства косинусов.

Я позаимствовал два слайда у Бенджамина Ван Дурма и Эшвина Лалла, ACL2010, и постараюсь немного объяснить интуицию LSH Families for Cosine Distance. введите описание изображения здесь

  • На рисунке два круга с красным и желтым цветом, представляющие две двумерные точки данных. Мы пытаемся найти сходство их косинусов, используя LSH.
  • Серые линии - это несколько случайно выбранных плоскостей.
  • В зависимости от того, находится ли точка данных выше или ниже серой линии, мы помечаем это отношение как 0/1.
  • В верхнем левом углу есть две строки белых / черных квадратов, представляющих подпись двух точек данных соответственно. Каждый квадрат соответствует биту 0 (белый) или 1 (черный).
  • Поэтому, когда у вас есть пул плоскостей, вы можете кодировать точки данных с их расположением в соответствии с плоскостями. Представьте, что когда у нас в пуле больше плоскостей, угловая разница, закодированная в сигнатуре, ближе к реальной разнице. Потому что только плоскости, находящиеся между двумя точками, будут давать разным битам два значения данных.

введите описание изображения здесь

  • Теперь мы смотрим на сигнатуру двух точек данных. Как и в примере, мы используем только 6 битов (квадратов) для представления каждой информации. Это хэш LSH для исходных данных, которые мы имеем.
  • Расстояние Хемминга между двумя значениями хэширования равно 1, поскольку их сигнатуры отличаются только на 1 бит.
  • Учитывая длину подписи, мы можем рассчитать их угловое сходство, как показано на графике.

У меня есть пример кода (всего 50 строк) в Python, который использует косинусное сходство. https://gist.github.com/94a3d425009be0f94751

greeness
источник
почему он называется чувствительным к локальности? потому что назначение каждого бита зависит от местоположения точки данных по отношению к каждому плану?
Навара
21
чувствительность к локальности - точки данных, расположенные близко друг к другу, отображаются в одинаковые хеши (в том же сегменте с высокой вероятностью).
зелень
2
Извините, я опоздал в этой теме, но у меня возник вопрос о косинусе. В презентации говорится, что значение бита равно единице, если произведение точки между фактическим вектором и вектором плоскости> = 0, или же оно равно 0. Каково направление вектора плоскости, поскольку углы между 90 градусами и 180 градусами также дадут косинус, который является отрицательным. Я предполагаю, что каждая плоскость состоит из двух векторов, и мы берем меньший угол, который сделан с фактическим вектором.
vkaul11
Спасибо. Итак, правильно ли говорить, что h кодирует угловую разницу, а b - «точность»? Таким образом, я понимаю, что h * PI - это тета в лучистом свете, а b - точность угла.
user305883
1
Слайд, который вы предоставили, очень аккуратный: cs.jhu.edu/~vandurme/papers/VanDurmeLallACL10-slides.pdf - не могли бы вы также объяснить математическую логику «трюка с пулом » - или концепции, которые мне следует искать в линейной алгебре чтобы понять это?
user305883
35

Твиты в векторном пространстве могут быть отличным примером многомерных данных.

Прочтите мой пост в блоге о применении Locality Sensitive Hashing к твитам, чтобы найти похожие.

http://micvog.com/2013/09/08/storm-first-story-detection/

А поскольку одна картинка - это тысяча слов, проверьте картинку ниже:

введите описание изображения здесь http://micvog.files.wordpress.com/2013/08/lsh1.png

Надеюсь, поможет. @mvogiatzis

mvogiatzis
источник
21

Вот презентация из Стэнфорда, которая объясняет это. Это имело большое значение для меня. Вторая часть больше о LSH, но первая часть также освещает это.

Картинка обзора (на слайдах их гораздо больше):

введите описание изображения здесь

Поиск в окрестностях соседей в многомерных данных - часть 1: http://www.stanford.edu/class/cs345a/slides/04-highdim.pdf

Поиск в окрестностях соседей в многомерных данных - часть 2: http://www.stanford.edu/class/cs345a/slides/05-LSH.pdf

nilsi
источник
Почему бы просто не использовать minhash напрямую в качестве функции LSH?
Томас Але
1
Я полагаю, потому что число недубликатов в сегменте остается достаточно высоким, в то время как если мы используем m таких независимых хеш-функций, вероятность того, что несопоставленные дубликаты будут отображаться в одном сегменте, значительно уменьшится.
Шату
7
  • LSH - это процедура, которая принимает в качестве входных данных набор документов / изображений / объектов и выводит вид хэш-таблицы.
  • Индексы этой таблицы содержат документы так, что документы, находящиеся в одном индексе, считаются похожи , и те , по разным показателям являются " непохожи ».
  • Где сходство зависит от метрической системы, а также от порогового сходства s, которое действует как глобальный параметр LSH.
  • Это до вас , чтобы определить , что адекватный порог S для вашей проблемы.

введите описание изображения здесь

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

В своем блоге я попытался подробно объяснить LSH для случаев minHashing (мера сходства jaccard) и simHashing (мера косинусного расстояния). Я надеюсь, что вы найдете это полезным: https://aerodatablog.wordpress.com/2017/11/29/locality-sensitive-hashing-lsh/

Карлос Тейшейра
источник
2

Я визуальный человек. Вот что работает для меня как интуиция.

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

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

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

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

Таким образом, с помощью LSH я в конечном итоге проецирую тени объектов в виде точек (0 или 1) на одну строку / битовую строку фиксированной длины.

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

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

То, как я представляю свой объект свету, будет определять, получу ли я хорошо узнаваемую тень или нет. Поэтому я думаю о «хорошем» LSH как о том, что превратит мои объекты перед светом так, чтобы их тень лучше всего узнавалась как представляющая мой объект.

Итак, подведем итог: я думаю о вещах, которые нужно индексировать с помощью LSH, как о физических объектах, таких как куб, стол или стул, и я проецирую их тени в 2D и, в конечном итоге, вдоль линии (битовая строка). А «хорошая» LSH «функция» - это то, как я представляю свои объекты перед источником света, чтобы получить приблизительно различимую форму в 2D равнине, а затем и в моей битовой струне.

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

Филипп Омбредан
источник
0

Как очень короткий ответ TLDR :

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

Вы можете прочитать этот пример, используя scikit-learn: https://github.com/guillaume-chevalier/SGNN-Self-Governing-Neural-Networks-Projection-Layer

Гийом Шевалье
источник