Вернулся к одному из своих исследований в области векторизации текста. Возможно, расскажу о нём позже, а пока, в поисках ответа на вопрос насколько моё исследование повторяет уже существующие разработки, изучил два интересных алгоритма.
SimHash: про то, как векторизовать текст в плотный вектор из нулей и единиц.
MinHash: про то, как транслировать разряжённый (sparse) бинарный вектор в компактный отпечаток, состоящий из целых чисел.
Кроме того, что оба алгоритма работают с бинарными векторами, у них есть еще одна общая черта.
Они оба гениальны в своей простоте и потому потрясающе красивы!
Это именно то, что меня вдохновляет в ML, и потому не могу сдержаться, чтобы не рассказать о них, хоть инфы в инете и так полно. Данная статья, написанная почти полностью пальцами, задумана как первая из двух, и я расскажу в ней про MinHash.
Итак, на какой же вопрос является ответом MinHash?
Алгоритм позволяет транслировать разряжённые (sparse) бинарные векторы большой размерности в целочисленные векторы многократно меньшей размерности с сохранением информации, позволяющей оценить похожесть исходных векторов.
При этом, данный набор чисел, называемый сигнатурой (signature):
Хоть и, строго говоря, по-прежнему будет являться вектором в математическом пространстве, но не будет нести правильной геометрической информации;
Сохранит информацию, позволяющую приблизительно высчитать коэффициент и расстояние Жаккара для исходных векторов;
Может быть произвольной размерности, но чем длиннее, тем лучше.
Вводные. С чем будем работать?
Допустим, есть у нас пара миллиардов разряжённых векторов, а размерность у них, при этом, тоже какая-нибудь субрелятивистская, скажем, 40 тысяч. Или 140 тысяч, и такое бывает. В наших примерах далее всё будет много компактнее, но именно на таких масштабах преимущества и смысл MinHash проявляются наиболее полно.
Мы рассмотрим 4 вектора размерности 20. В каждом из них от 5 до 7 единиц, остальные разряды выставлены в ноль. Два вектора (V1 и V2) будут похожи друг на друга, они различаются лишь в 18 и 19 разрядах. и еще два вектора — уникальны.
Вектор | Бинарное представление | Позиции единиц |
|---|---|---|
V1 |
| 2, 5, 8, 12, 15, 18 |
V2 |
| 2, 5, 8, 12, 15, 19 |
V3 |
| 1, 4, 7, 10, 13, 16 |
V4 |
| 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 |
|
V2 |
|
V3 |
|
V4 |
|
Напомню, что в продакшене это всё будут обращения к семейству хэш-функций.
Действительно ли всё работает?..
Давайте теперь убедимся, что идея действительно сработала, а потом поймём что мы можем делать с получившимися сигнатурами, и чего не можем.
Высчитаем коэффициент Жаккара для пар исходных векторов:
V1 и V2: 0.714
V1 и V3: 0
V1 и V4: 0
Возвращаемся к сигнатурам
V1 vs V2: сигнатуры
[2, 1, 4]и[2, 1, 6]совпали на 2 из 3 позиций → оценка сходства = 2/3 ≈ 0.667V1 vs V3: сигнатуры
[2, 1, 4]и[7, 3, 2]совпали на 0 из 3 → 0V1 vs V4: сигнатуры
[2, 1, 4]и[1, 8, 1]совпали на 0 из 3 → 0
Всё сходится. Однако, еще раз напомню, что я просто подобрал пример, на котором хорошо сработали столь короткие сигнатуры. В реальной жизни они должны быть сильно длиннее.
...Но что именно работает?
Сигнатуры сравнивают не как геометрические векторы, а по числу совпавших компонент. Именно эта идея лежит в основе семейства алгоритмов LSH.
Вот тут начинаются тонкости, которые заставляют перечитывать Мерфи и Кострикина по несколько раз. На самом деле, любая последовательность целых чисел принадлежит Zn , и, следовательно, является математическим вектором.
Вот только наши вектора созданы очень кастомным способом, и своим расположением в n-мерном пространстве не несут никакой информации, а значит, привычные методы, такие как вычисление евклидова или косинусного расстояния, не могут быть использованы.
Что делать? А так и сравнивать их, численно.
Сигнатуры сравнивают не как геометрические векторы, а по числу совпавших компонент. Именно эта идея лежит в основе семейства алгоритмов LSH. Возможно, расскажу и про них однажды.
Кто это придумал и зачем?
ML -- это потрясающе интересно. И математика тоже. Жаль, что в 39 лет мне уже трудновато всё это разгрызать. А вот моему тёзке Андрею Бродеру, работавшему в 1997 году в AltaVista, было, видимо, вполне даже норм.
Олдфаги помнят, что АльтаВиста -- это когда-то был такой поисковик. Даже я его не застал, а лишь слышал про него. А поскольку поискови, то и Андрей решал задачу, требующую оценки схожести веб-страниц и поиска клонов.
Он вывел лемму:
Если π — случайная перестановка множества, то вероятность того, что минимальный элемент перестановки для двух множеств A и B совпадёт, в точности равна коэффициенту Жаккара этих множеств.
Впоследствии, в соавторстве с другими математиками это было оформлено в полноценную математическую работу.
Таким образом, бинарные вектора, которые в данной статье рассматривались как исходные, в задаче, которую решал Андрей, являлись one-hot представлением веб-страниц.
----
Здесь не будет рекламы телеграм канала, который у меня, конечно же, есть. Просто расскажу о себе, наконец.
Меня, как вы уже догадались, тоже зовут Андрей, я сотрудник Сбера, и сейчас работаю в рабочей группе, никак не связанной с ИИ. Работал и в таких, которые были связаны.
Всегда рад пообщаться про ML, готов к аргументированной критике данной небольшой статьи. Пожалуйста, указывайте на возможные ошибки и неточности. Приветствуется распространение на прочих ресурсах.