Locality-Sensitive Hashing (LSH): Математика поиска похожих объектов
Классические криптографические хеш-функции (MD5, SHA-256) созданы с одной целью: обеспечить строгий лавинный эффект. Изменение всего одной запятой в томе "Войны и мира" приведет к совершенно другому, неузнаваемому хешу. Однако в машинном обучении, биоинформатике и системах рекомендаций нам нужно нечто диаметрально противоположное. Нам нужно, чтобы похожие объекты получали одинаковые хеши. Эту математическую магию обеспечивает Locality-Sensitive Hashing (LSH).
Когда у вас есть база из 10 миллионов фотографий или 10 миллионов профилей пользователей, и вам нужно найти "похожие" на новый запрос, классический метод KNN (K-Nearest Neighbors) требует вычисления расстояния между новым объектом и каждым из 10 миллионов существующих. Если объекты описываются тысячами признаков (векторами высокой размерности), мы сталкиваемся с "Проклятием размерности", и поиск становится невыносимо долгим. Деревья поиска (KD-trees) в многомерных пространствах деградируют до полного перебора.
LSH использует вероятностный подход. Мы соглашаемся на крошечную долю ошибки взамен на феноменальную скорость. Суть LSH — создать семейство хеш-функций со следующим свойством: вероятность коллизии (что хеши совпадут) для двух элементов строго пропорциональна их физическому или логическому сходству.
Один из самых популярных алгоритмов LSH для анализа текстовых документов — MinHash. Он оценивает сходство множеств по Метрике Жаккара (Jaccard similarity) (отношение мощности пересечения множеств к мощности их объединения).
Алгоритм работает так:
- Текст разбивается на токены (шинглы).
- К токенам применяется N случайных перестановок (или N обычных хеш-функций).
- Для каждой перестановки мы находим токен с минимальным значением хеша. Эти N минимальных значений образуют "сигнатуру" документа.
- Теорема доказывает: вероятность того, что элементы сигнатуры совпадут, в точности равна индексу Жаккара исходных текстов!
Чтобы не перебирать все сигнатуры при поиске, используется техника Banding (Группировка). Сигнатура режется на b полос по r чисел в каждой. Каждая полоса хешируется в отдельную корзину хеш-таблицы. Если хотя бы одна полоса (часть сигнатуры) у двух документов совпала — они попадают в одну корзину и объявляются "кандидатами на проверку".
Это позволяет системе сузить круг поиска с 10 миллионов документов до пары сотен кандидатов за O(1) времени. LSH лежит в основе систем "Антиплагиат", алгоритмов рекомендаций YouTube (для поиска похожих пользователей) и аудио-поисковика Shazam.
Последнее от Александр
- Английский сленг: фразы и выражения на английском с переводом
- Промышленная безопасность - как теория вероятностей помогает прогнозировать аварии на ОПО
- Финансовая математика печати: как рассчитать реальную стоимость владения принтером
- Лучшие нейросети для написания текстов
- Гнеденко Борис Владимирович