Практичный и оптимальный алгоритм хеширования с учетом углового расстояния и местности

Оригинальный адрес:Eat020031308.GitHub.IO/papers/2015…

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

Cross-polytope LSH

Метрика расстояния для кросс-многогранника LSH — это угловое расстояние, эквивалентное расстоянию Эйлера, нормализованному к единичной сфере.
Алгоритм определяется как случайная инициализация матрицы A с N (0, 1), вычисление y = Ax / ||Ax|| (то есть случайное вращение), а затем принятие ближайшего положительного или отрицательного единичного вектора в качестве его хеш-значения. (То есть argmax[Ax, -Ax]).

Три небольших улучшения кросс-политопа LSH

Это не имеет особого смысла:

1. Псевдослучайное вращение:$A = HD_3HD_2HD_1$, где H — матрица Адамара ($\pm 1$Ортогональная квадратная матрица), три диагональных элемента D являются случайными$\pm 1$диагональная матрица
   • Пробел: H фиксирован, не считая пробела. Д - диагональ. Итак, О($d^2$) до O(d)
   • Время: с помощью быстрого преобразования Адамара (классический алгоритм в области кодирования видео, я не знаю) можно вычислить за O($d^2$) до О($d \log d$)
   • Автор не доказывает эквивалентность этого метода оригинальному методу, только то, что двух Н недостаточно, три Н могут
2. Хэш функции: если это разреженный вектор, сначала сделайте случайный хеш (для каждого столбца есть только один$\pm 1$), чтобы уменьшить размерность
3. Частичный кросс-многогранник LSH: в конце берется только ближайшая часть единичного вектора, что эквивалентно удалению части размеров [Ax, -Ax]

Multiprobe LSH

идея:

• Для LSH, если p, q подобны, то h(p) и h(q) должны находиться в одинаковых корзинах, даже если они не находятся в одной корзине.
• Для Cross-polytope LSH распределение h(p) в порядке вероятности должно быть таким же, как sort[Aq, -Aq], т.е. наиболее вероятно столкновение с argmax[Aq, -Aq], а второе вероятно столкновение с [Aq, -Aq] ] (обозначается как z) во втором по величине позиционном столкновении, ...

Вышеизложенное является качественным анализом, и автор количественно подсчитал, что, исходя из предположения, что элементы в A удовлетворяют распределению Гаусса, существует приблизительно$P\{h(p) = i\} \propto \exp{-|\max z - z_i|^2}$

Обычно LSH должен пройти несколько раундов хеширования.Предыдущий метод заключается только в том, чтобы увидеть, сталкивается ли максимальная позиция в каждом раунде хеширования.
Но с предыдущими количественными выводами результаты нескольких раундов ротации можно объединить и отсортировать по вероятности, и чтобы увидеть, сталкиваются ли позиции с наибольшей вероятностью, можно лучше использовать результаты операции ротации. Как показано на рисунке:

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

Дополнение: Поскольку исходный текст не ясен, просто скажите, что после нахождения вероятности используйте его с "Multiprobe LSH-индексирование в многомерном поиске подобия", чтобы построить последовательность. Я догадался, что нарисовал предыдущую картинку, но прочитав процитированную статью, обнаружил, что рисунок неправильный и не стал его менять.