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

Вот важная новость с фронта ИИ: SkywardFire 28 минут назад Красота математики и ML (part 1/2): алгоритм MinHash Простой 5 мин 634 Алгоритмы * Математика * Машинное обучение * Обзор Recovery Mode Вернулся к одному из своих исследований в области векторизации текста. Возможно, расскажу о нём позже, а пока, в поисках ответа на вопрос насколько моё исследование повторяет уже существующие разработки, изучил два интересных алгоритма. SimHash: про то, как векторизовать текст в плотный вектор из нулей и единиц.

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

Технические детали

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

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

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

Отраслевые последствия

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

и еще два вектора — уникальны. ВекторБинарное представлениеПозиции единицV10 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 02, 5, 8, 12, 15, 18V20 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 02, 5, 8, 12, 15, 19V31 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 01, 4, 7, 10, 13, 16V40 0 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 13, 6, 9, 11, 14, 17, 20Отсчёт индексов в данной статье решил вести с единицы. Алгоритм действительно гениально прост, и состоит из 3 шагов.

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

Событие, по словам экспертов, усилит конкуренцию в сфере ИИ.