Про то, почему не работал бимсерч и чем санта 24 отличается от санты 23

В прошлом (2023) «Санте» требовалось собрать многомерный кубик Рубика в упорядоченное положение кратчайшим путём. Это классическая задача поиска кратчайшего пути: при наличии подходящего алгоритма и отсутствии отрицательных циклов её можно решить в полиномиальное время. Даже если точное решение найти затруднительно, задачу можно разбить на подзадачи и последовательно ограничивать поиск, отсекая пути, которые уже заведомо не могут быть короче найденного решения, а потом искать оптимизации между промежуточными пунктами с помощью бимсерча.

В «Санте» 2024 года мы имеем более сложную задачу: нужно переставить заданные слова в таком порядке, чтобы минимизировать перплексию для модели Gemma-2-9b. Иначе говоря, это задача коммивояжёра (TSP) (а еще лучше задача о Питербуржских мостах): надо обойти «города» (здесь — слова) и вернуться к начальному условию или достичь некоторого состояния, при этом пропускать слова нельзя. TSP относится к классу NP-трудных задач, и при более чем 66 «городах» (в нашем случае слов около 100) её невозможно точно решить перебором за разумное время: потребуются миллиарды лет вычислений даже на гипотетическом сверхмощном компьютере.

Почему beam search (и аналогичные алгоритмы поиска кратчайшего пути) в данном случае не помогают? Основная причина в том, что в задаче коммивояжёра, по сути, могут существовать «отрицательные циклы» с точки зрения нашей целевой функции (перплексии). В классическом поиске кратчайшего пути алгоритмы гарантированно работают только при условии, что нет отрицательных циклов, т.е. нет подпути, который имеет отрицательную длину. D 2024 же нам специально нужно найти такую последовательность (цикл посещения всех «городов»), при которой итоговая «стоимость» (перплексия) окажется минимальной. Метод beam search, который хорош в задачах без отрицательных циклов, не способен эффективно отсеивать невыгодные ветви в условиях просто потому, что не обладает достаточной информацией, где каждое добавление нового «города» может кардинально изменить оценку перплексии.

Поскольку слова пропускать нельзя, обойти «сложные» участки не получится. Задача действительно носит характер TSP, а он, не допускает эффективных точных решений при большом количестве вершин. Поэтому для «Санты» 2024 года оправдано применение эвристических или стохастических методов (например, отжига или других метаэвристик), которые не гарантируют точное решение, но на практике позволяют получить приемлемый результат за разумное время.

TLDR: бимсерч не сможет развернуться, потому что задизайнен для отсутствия негативных циклов. Это не мешает ему хорошие решения искать в ЛЛМках, потому что там набор слов не ограничен и можно их использовать сколько угодно раз. Кстати, я тут понял, что задача этого года- это задача поиска гамильтонова пути, но они в одном классе эквивалентности.

Влетел на 390 место и 16,616 рейтинга. ВКУСНО 🎲

Сейчас проходит еще одна сорева NIPS.
Это RL-соревнование, так что участники соревнуются напрямую против друг друга и можно посмотреть реплеи своего бота.

Второй на лб кагглер пишет ГГ прямо на доске если выигрывает или проигрывает 3-0 (потому что раундов 5 и он уже победил/проиграл)

Кстати, всем любителям дешевого дофамина вчера раздали еще и бейджи за Санту. Причем за всех сант- одинаковый бейдж

Забыл вам сказать подписчики. Видимо это сейчас важно. Все это время мне было 17 лет

Админу LDT 16, он у нас в школе на воротах на футбике стоит и шитпостит
Валера Бабушкин наш физрук

Тати оказывается тоже завела канал. Это человек, с которым я нафармил свою первую медальку в 2019 году за компетишны и стафф инженер Linkedin. Когда мы решали Lyft Тати созванивалась с нами из декрета и решала кагл, пока ребенок спит.

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

Альфа-тест — это когда ты настолько не уверен в своём апдейте, что сначала платишь людям за то, чтобы они его попробовали.

Сигма-тест — это когда ты сразу выкатываешь и сразу наблюдаешь за падающими графиками.

Вот времена
В го дженерики
В питоне можно выключить GIL
Скоро в плюсах появится лайфтаймы

В соревнова LUX 3 забавная ситуация:
1. Осталось 12 дней до дедлайна
2. 5 дней до конца соревы
3. До сих пор в ноутбуках нет работающего решения на РЛ, только хороший бейзлайн бот на эмпириках. У меня вот RL тоже не заводится, особенно self-play
4. Из топовых команд кажется у топ 10-2 только получилось завести разного уровня рльные решения
5. Простая докрутка публичного бота на эмпириках дает бронзу

А у вас как дела?

Хочу сильно стукаться и объявляю Waaagh в секторе Lux AI Season 3

А вот из ржомб из моей дс-жизни:
Раз в пару месяцев ко мне приходит в лс бот из AISender. Это такой провайдер этих всех духовных ботов, заманивающих вас по ссылке в комментах. Но иногда они приходят в лс и предлагают свои «услуги»
Обычно такие боты используют API (опенаи например) и у них есть бюджет на количество запросов. В прошлый раз я кормил его сценарием Шрека до тех пор, пока у бота не кончились токены.
В этот раз я нашел СЕО AISender в линкдине и кормил бота утверждением в нечастивости формата «Рустам Габидуллин XXX”

Видимо Рустам делает работу над ошибками, потому что через пару часов после ухода бота в оффлайн (токены кончились), бот мне ответил «Дмитрий Руденко ХХХ» и кинул в чс.

Мораль:
Рустам обучается, но в наших силах истратить все его токены на сценарии уже почти пяти частей Шрека

А вы как боретесь с этим порождением гениальных маркетологов?

Сходка админов тг каналов
Предлагаю перечислить их всех в комментах

Смотрю решения прошлого года по March Mania. Ежегодное соревнование по предсказанию исходов баскетбольных матчей, мощное как четвертый форвард, резкое как V-cut. В свое время ходил на секцию лет 8, так что грех не поучаствовать.

Ну так вот, бекграунды победителей прошлых лет:
1. Я учитель статов и победил околослучайно через симуляции из паблик кернела
2. Я работаю в гемблинге и это мой третий год участия. В прошлый раз я взял 7 место. В позапрошлый- сотое
3. Адам, город Мачиган, это мое первое соревнование после титаника. Ваще то я на си пишу
4. Нефритовый стержень партия удар (十有五而志于学- это цитата Конфуция)
5. Стефан, город Бруклин, 18 лет, я взял фичи и чет с ними сделал и даже чет завелось
6. Пхд студент, у которого тема тезиса- беттинг на соревнованиях
7. РУЧНОЙ ЧЕРВЬ (Самсон, если ты подписан и читаешь это, то напиши в лс)
8. Безликий анонимный японец

Разбор решений NeuralPS Lux 3

#lux

Начинаем с третьего места, которое занял @aDg4b, загала называемый нами "Ворона в шляпе". Он уже не раз участвовал в simulation-соревнованиях, в том числе выиграл первый Lux и Kore 2022. В личной беседе @aDg4b отметил, что симуляционные задачи для него – самые интересные.

Основная идея
Решение построено на Imitation Learning (IL). Вместо того, чтобы учить награды или другие механики, модель просто обучается повторять действия сильных соперников, основываясь на их наблюдениях игрового поля.

Архитектура
Модель состоит из двух частей, которые не удалось объединить в единый end-to-end пайплайн:

1. World-wise UNet – предсказывает действия для всех агентов сразу.
2. Unit-wise SAP-UNET – дополнительная сеть, работающая как "модуль наведения". Если первый UNet приказывает стрелять, этот модуль решает, куда именно.
(Если у кого-то есть идеи, как объединить такие компоненты в end-to-end модель, напишите!)

Первая сеть: World-wise UNet
Входные данные:
Полный набор информации о мире (размерность 28×24×24):
24×24 – игровое поле.
28 каналов – различные характеристики среды (тип клетки, количество энергии и т. д.), а также память о прошлых позициях кораблей, времени сколько времени не наблюдали клетоку и прочее.
Глобальные параметры матча (инжектятся в bottleneck):
Дальность видимости кораблей, дальность стрельбы, параметры "ветра" и тд.

Выход сети:
6×24×24 – вероятности каждого действия для каждой клетки.

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

Вторая сеть: Unit-wise SAP-UNET
Входные данные:
Полный feature map + маска позиции юнита.

Выходные данные:
24×24 – вероятности выбора клетки для стрельбы.

IL
В качестве "донора" для IL использовались топ-2 команды (о которых мы еще поговорим):
1. С помощью Kaggle API загружались данные о матчах
2. Отбирались только те, где донор победил
3. В них фильтровались победы, где результат матча еще не предрешен.
Этого оказалось достаточно для сходимости модели, что для меня удивительно.

"Хорошие кагглеры думают, великие — воруют" (с) Фанаты Плескова