Что общего между машинным обучением, золотым миллиардом и Brawl Stars?

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

Правда от лёгкости и увлекательности я безумной скоростью перешёл к рейтинговому режиму, в котором для успешной игры против таких же безумцев нужно анализировать карты, на которых происходят сражения — узнавать, какой боец на этой карте самый сильный и какие тактики за него будут наиболее действенными

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

➡️ Решающие деревья
"Как понять, что мы разбили пользователей по наиболее прибыльным категориям?"

Деревья решений делят объекты по сценариям (например, «богатый» или «бедный» клиент для выдачи кредита). Нам нужно, чтобы разбиение было «чистым» — то есть в одной ветке преобладала одна категория.

Получается, что хорошо то разбиение, при котором объекты, проходящие и по одному сценарию, и по другому, имеют доминирующую категорию (например, если разделение на богатых и бедных сразу хорошо отвечает на вопрос "Надо ли выдавать кредит?").

Мера этой однородности и есть критерий Джини:

1 - Д1² - Д2²

(где Д1, Д2 — доля разных категорию после разбияния) стремится к нулю, если одна категория доминирует. Чем меньше число, тем эффективнее сработало дерево. Понятно, что эту формулу можно обобщить и на бОльшее количество категорий


➡️ Brawl stars
"Как понять, кого мейнить на карте?"

Пу-пу-пу.... Это всё замечательно, но причём здесь мобильная игра про мультяшных микрочелов? Дело в том, что в ней критерий Джини применяется не к долям объектов одной категории после разбиения, а к доле матчей, в которых брали того или иного героя, то есть "категорий" в данном случае столько, сколько героев существует в игре

Получается, что посчитав критерий Джини мы узнаём, насколько однородно на карте берут бойцов. Да это же мера "сбалансированности" карты, ведь если на карте всегда берут одного и того же бойца, значит он на этой карте слишком силён!!!

Бум! Элегенатное и совсем не сложное переложение "меры однородности" с сухой задачи машинного обучения на ранкед в донатной дрочильне. Однако даже это не самый интересный способ применения этого коэфициента...


➡️ Эконометрика
"Обидно, что я живу в стране, где учебник стоит дороже brawl pass+"

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

Уже догадались? Применяем коэфифицент Джини для определения неравномерности распределения ресурсов в рамках стран. А почему бы и нет?

Считаем это число для разных стран и оказывается, что Россия имеет коэфициент Джини 0.408, В картах бравл старс это где-то около dueling beetles и backyard bowl (и чуть выше США и Китая)

⏹️ Как вы думаете, к чему ещё было бы интересно приложить коэфициент Джини и как линейкой замерить неоднородность? Распределение букв в этом посте, напечатанных левой и правой рукой? Сбалансированность использования турникетов на Тургеневской? Равномерность покупки разных вкусов Ritter Sport в ближайшей пятерочке?

Пишите ваши предложения в комментариях!

На днях произошло важное событие в области искусственного интеллекта -- модель от OpenAI собственноручно доказала нетривиальную теорему из области комбинаторной геометрии. Звучит скучно, но на деле оказывается, что задача понятна и проста, а прорыв действительно ощутим. Давайте попробуем разобраться, чё вообще произошло

➡️ Предыстория
Жил в 20м веке удивительный математик Пол Эрдёш. Он посвятил математике буквально всего себя -- вместо того, чтобы жить спокойную и понятную семейную жизнь, Пол десятилетиями колесил по всему миру и писал статьи со своими корешами из научного сообщества у них на квартирах (⚠ дисклеймер для поколения альфа ⚠ -- в 20м веке ещё не были изобретены видеоконференции). А ещё он любил амфетамин и был членом большого количества математических коллегий

А ещё, насколько я понимаю, он написал столько статей, сколько не написал ни один математик в истории (~1400)

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

Бросим N точек на плоскость как хотим. Сколько единичных отрезков между точками мы сможем получить?

Задача звучит абсолютно базово. Казалось бы, ставим точки кучно друг к другу на единичном расстоянии и -- вуаля -- Отрезков стало очень-очень много. Однако эта задача при всей своей простоте оказалась сложнейший математической проблемой, которая терзала умы лучших математиков последние 80 лет

И вот буквально на наших глазах проблема решилась. Но почему же это действительно круто и важно?

➡️ Это первая задача такой популярности и сложности, которую решил ИИ

➡️ Модель OpenAI не тренировали специально под эту задачу. Её просто попросили её решить, обычным запросом

➡️ Решение модель придумала, связав комбинаторную теорию чисел (к которой принадлежит задача) с абсолютно далёкой и обособленной алгеброй. Сам Пол неоднократно говорил о далёкости этих двух наук

➡️ Используя более абстрактный механизм алгебры, модель воспользовалась теоремой Голода-Шафаревича. Первый -- предполагаемый родственник моего коллеги, второй -- отец декана мехмата МГУ и дед моего друга (кому интересно, само доказательство)

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