Почему сравнивать большие тексты так сложно
В мире обработки текста и машинного обучения стоит неизбежная задача - определять, насколько похожи между собой два документа. Кажется, что для этого достаточно сравнить слова, но при больших коллекциях и длинных текстах прямое сопоставление становится слишком ресурсоёмким.
Наивный подход - перебрать все пары документов и вычислить их пересечение слов - на практике не работает: количество сравниваемых пар растёт как квадрат числа документов, а объём уникальных токенов ещё увеличивает вычислительную нагрузку.
К тому же обычные меры сходства, например, коэффициент Жаккара (отношение размера пересечения множеств слов к размеру их объединения), требуют полного знания наборов слов для каждого документа.
При хранении больших корпусов или потоковой обработке данных это накладывает серьёзные ограничения: память и время растут непропорционально. Нужна более экономная репрезентация множеств, которая бы позволяла быстро оценивать похожесть без точного восстановления всех элементов.
Идея MinHash - сжать множество, сохранив сходство
Алгоритм MinHash предлагает хитрый компромисс: создать компактные подписи для документов так, чтобы вероятность совпадения соответствующих подписей отражала реальное значение коэффициента Жаккара.
Вместо хранения полного списка слов мы формируем для каждого документа вектор хеш-значений, получаемых при применении нескольких независимых хеш-функций к элементам множества.
Для каждой хеш-функции сохраняется минимальное по значению хеш-значение среди всех элементов документа - отсюда и название MinHash (минимальный хеш).
Ключевой момент: если два множества имеют высокий коэффициент Жаккара, то при случайном хешировании их минимальные хеш-значения для данной функции совпадают с вероятностью, равной этому коэффициенту.
Повторив процедуру с несколькими независимыми хешами, мы получаем несколько битов информации о сходстве - чем больше хеш-функций, тем точнее оценка. Это сжатие даёт экономию по памяти и значительно ускоряет сравнение: достаточно сравнить короткие подписи вместо полных множеств.
Как строится подпись и как её использовать
Процесс прост в реализации. Для каждого документа и каждой хеш-функции рассчитываем минимальное значение хеша по всем токенам документа и записываем полученные минимумы в вектор фиксированной длины и есть подпись MinHash.
Для оценки похожести двух документов сравниваем их подписи: доля совпадающих компонент вектора служит оценкой коэффициента Жаккара. Практически это превращает тяжёлую задачу сравнения множеств в лёгкую операцию над векторами фиксированной длины.
Такой подход даёт ещё одно преимущество - подписи легко индексируются и используются совместно с методами локального хеширования (LSH) для быстрого поиска похожих документов в больших коллекциях. С LSH можно сгруппировать подписи по "бакетам", где вероятность попадания двух похожих подписей в один бакет велика, что делает поиск ближайших соседей масштабируемым.
Погрешности и как с ними жить
MinHash даёт оценку, а не точное значение Жаккара, поэтому здесь есть компромисс между точностью и объёмом подписи. Чем больше независимых хеш-функций мы применим, тем точнее будет оценка, но тем длиннее подпись. Типичные реализации находят средний баланс: длина подписи в сотни элементарных хешей обеспечивает приемлемую точность при экономии памяти по сравнению с хранением исходных множеств.
Ещё одна тонкость - выбор хешей и их независимость. На практике используют детерминированные, псевдонезависимые хеш-функции или техники на основе случайных перестановок.
Важно проверять качество хеширования и корректно настроить количество функций под задачу: для поиска почти дубликатов нужен один набор параметров, для грубого кластеринга - другой.
Практическое применение и преимущества в ML
MinHash нашёл широкое применение в инфраструктуре поисковых систем, при дедупликации документов, в рекомендациях и при обработке потоковых данных.
Его сила в том, что он делает возможным эффективный поиск схожих объектов в огромных коллекциях, где классические алгоритмы слишком медленны или дорогие в ресурсоёмкости.
Алгоритм особенно хорош там, где важнее быстро отфильтровать кандидатов, а затем уже более точными методами уточнить результаты. Кроме того, MinHash прекрасно комбинируется с другими методами: его подписи можно использовать в качестве признаков для машинного обучения, применять вместе с LSH для индексирования или интегрировать в пайплайны потоковой обработки.
Благодаря простоте и математической прозрачности он остаётся популярным инструментом - пример того, как аккуратно подобранная математика превращает сложную задача в практичное инженерное решение. В заключение, MinHash яркий пример того, как вероятностные методы и аккуратное сжатие информации позволяют эффективнее справляться с задачами сравнения и поиска похожих объектов в больших данных.
Его логика проста, реализация доступна, а результат заметно улучшает производительность современных систем обработки текста.