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

SimHash: про то, как векторизовать текст в плотный вектор из нулей и единиц.

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

Кроме того, что оба алгоритма работают с бинарными векторами, у них есть еще одна общая черта.

Они оба гениальны в своей простоте и потому потрясающе красивы!

Это именно то, что меня вдохновляет в ML, и потому не могу сдержаться, чтобы не рассказать о них, хоть инфы в инете и так полно. Данная статья, написанная почти полностью пальцами, задумана как первая из двух, и я расскажу в ней про MinHash.

Итак, на какой же вопрос является ответом MinHash?

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

При этом, данный набор чисел, называемый сигнатурой (signature):

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

Вводные. С чем будем работать?

Допустим, есть у нас пара миллиардов разряжённых векторов, а размерность у них, при этом, тоже какая-нибудь субрелятивистская, скажем, 40 тысяч. Или 140 тысяч, и такое бывает. В наших примерах далее всё будет много компактнее, но именно на таких масштабах преимущества и смысл MinHash проявляются наиболее полно.

Мы рассмотрим 4 вектора размерности 20. В каждом из них от 5 до 7 единиц, остальные разряды выставлены в ноль. Два вектора (V1 и V2) будут похожи друг на друга, они различаются лишь в 18 и 19 разрядах. и еще два вектора — уникальны.

Вектор	Бинарное представление	Позиции единиц
V1	`0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0`	2, 5, 8, 12, 15, 18
V2	`0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0`	2, 5, 8, 12, 15, 19
V3	`1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 0`	1, 4, 7, 10, 13, 16
V4	`0 0 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 1`	3, 6, 9, 11, 14, 17, 20

Отсчёт индексов в данной статье решил вести с единицы.

Real action!

Алгоритм действительно гениально прост, и состоит из 3 шагов.

Генерация вспомогательных последовательностей
Применение каждой вспомогательной последовательности к каждому вектору
Запись получившегося значения в результирующую сигнатуру

Поехали.

1. Генерация вспомогательных последовательностей

Так их называю только я, и это самый точный термин. Официально они называются перестановками, и далее вы поймёте почему.

Прелесть алгоритма (кроме прочих) состоит в том, что размерность сигнатур мы можем делать буквально какую захотим. Однако, как уже было сказано, чем длиннее будет сигнатура, тем точнее мы потом сможем оценить схожесть векторов на её основе.

Мы с вами сейчас будем высчитывать сигнатуры размерностью 3. Значит, нам сначала нужно сгенерировать 3 вспомогательные последовательности. Это будут наши "ключи кодирования", еще один довольно точный синоним.

Каждая последовательность — это просто числа от 1 до 20, случайным образом перемешанные. Потому и называют их "перестановками". Обратите внимание, что размерность 20 здесь именно потому, что такова размерность наших исходных векторов!

Выпишем их полностью:

P1: 14 3 19 7 2 11 20 5 16 8 1 12 18 4 9 15 6 13 10 17

P2: 5 12 8 19 1 15 3 11 20 7 14 2 16 9 18 4 10 13 6 17

P3: 18 7 11 2 20 5 14 9 1 16 3 12 8 19 6 15 10 4 17 13

В реальном коде вместо готовых последовательностей применяют хэш-функции, но это исключительно для оптимизации, чтобы быть более CPU-bound, и не хранить все перестановки в памяти. Суть та же: каждая хэш-функция, являясь, по сути, ключом кодирования, детерминированно отображает каждый индекс в некоторое число, обращаемся к ней, вместо того, чтобы хранить в памяти набор чисел (и потом всё равно дёргать функцию для работы с этим набором).

Мы для наглядности продолжим именно с готовыми вспомогательными последовательностями.

2. Применяем каждую вспомогательную последовательность к каждому вектору

Вспомним наш первый вектор, V1: 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0

А вот наша первая последовательность P1: 14 3 19 7 2 11 20 5 16 8 1 12 18 4 9 15 6 13 10 17

Используем исходный вектор как битовую маску, накладываем её на вспомогательную последовательность, получая в итоге наборы целочисленных значений.

Распишу это по шагам.

Единицы в векторе V1 стоят в позициях: 2, 5, 8, 12, 15, 18.

Теперь выписываем значения из P1 строго для этих позиций:

Позиция 2 -> значение *3**

Позиция 5 -> значение *2**

Позиция 8 -> значение *5**

Позиция 12 -> значение *12**

Позиция 15 -> значение *9**

Позиция 18 -> значение *13**

Соответственно, вот наш искомый набор для V1: 3, 2, 5, 12, 9, 13.

3. Забираем минимальное значение в результирующую сигнатуру

Берём min() от перечисленных значений.

Из набора [3, 2, 5, 12, 9, 13] минимум — это 2.

Повторяем шаги 2 и 3 для каждого исходного вектора и для каждой вспомогательной последовательности

А именно, берём вторую перестановку, применяем к тому же, первому векторую, минимальное значение из получившихся интов будет равно 1, потому, что в пятой позиции нашей перестановки стоит значение 1.

И так далее. Чтобы не утомлять вас арифметикой, я просто сведу все расчеты в итоговую таблицу. Представим, что мы честно прогнали все 4 вектора через все 3 перестановки:

Вектор	Сигнатура
V1	`[2, 1, 4]`
V2	`[2, 1, 6]`
V3	`[7, 3, 2]`
V4	`[1, 8, 1]`

Напомню, что в продакшене это всё будут обращения к семейству хэш-функций.

Действительно ли всё работает?..

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

Высчитаем коэффициент Жаккара для пар исходных векторов:

V1 и V2: 0.714

V1 и V3: 0

V1 и V4: 0

Возвращаемся к сигнатурам

V1 vs V2: сигнатуры [2, 1, 4] и [2, 1, 6] совпали на 2 из 3 позиций → оценка сходства = 2/3 ≈ 0.667
V1 vs V3: сигнатуры [2, 1, 4] и [7, 3, 2] совпали на 0 из 3 → 0
V1 vs V4: сигнатуры [2, 1, 4] и [1, 8, 1] совпали на 0 из 3 → 0

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

...Но что именно работает?

Сигнатуры сравнивают не как геометрические векторы, а по числу совпавших компонент. Именно эта идея лежит в основе семейства алгоритмов LSH.

Вот тут начинаются тонкости, которые заставляют перечитывать Мерфи и Кострикина по несколько раз. На самом деле, любая последовательность целых чисел принадлежит Zⁿ , и, следовательно, является математическим вектором.

Вот только наши вектора созданы очень кастомным способом, и своим расположением в n-мерном пространстве не несут никакой информации, а значит, привычные методы, такие как вычисление евклидова или косинусного расстояния, не могут быть использованы.

Что делать? А так и сравнивать их, численно.

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

Кто это придумал и зачем?

ML -- это потрясающе интересно. И математика тоже. Жаль, что в 39 лет мне уже трудновато всё это разгрызать. А вот моему тёзке Андрею Бродеру, работавшему в 1997 году в AltaVista, было, видимо, вполне даже норм.

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

Он вывел лемму:

Если π — случайная перестановка множества, то вероятность того, что минимальный элемент перестановки для двух множеств A и B совпадёт, в точности равна коэффициенту Жаккара этих множеств.

Впоследствии, в соавторстве с другими математиками это было оформлено в полноценную математическую работу.

Таким образом, бинарные вектора, которые в данной статье рассматривались как исходные, в задаче, которую решал Андрей, являлись one-hot представлением веб-страниц.

----

Здесь не будет рекламы телеграм канала, который у меня, конечно же, есть. Просто расскажу о себе, наконец.

Меня, как вы уже догадались, тоже зовут Андрей, я сотрудник Сбера, и сейчас работаю в рабочей группе, никак не связанной с ИИ. Работал и в таких, которые были связаны.

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

Красота математики и ML (part 1/2): алгоритм MinHash