Люди работают, понимать надо ...

Нежданно-негаданно решил с друзьями: Сережей и Германом, залететь на Всероссийский хакатон от Цифрового прорыва в Нижнем, на кейс от РЖД. Необходимо было придумать модель для координации вагонопотока между жд станциями.

Мы посидели-посидели, и в итоге заняли 3-е место, выйграли килограмм варенья, килограмм печенья, а также поездку куда-то 🥳🥳

Аспирантура:

Очень жизненно

Если по какой-то причине вам не знакома фамилия Прокудина-Горского, то утро субботы воскресенья -- отличное время для того, чтобы побольше о нем узнать

Еще в июле я и Герман решили принять участие в ICML 2023 Topological Deep Learning Challenge -- соревновании на одной из самых крупных конференций по машинному обучению, суть которого заключалась в реализации топологических нейросетей.

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

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

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

В частности, на соревновании мы реализовывали две архитектуры гиперграфовых нейросетей: HyperGAT и HyperSage. В рамках соревнования предполагалось реализовать эти нейросети с использованием фреймворка TopoModelX, таким образом способствуя его развитию и популяризации. Ну, кажется, мы справились!

И вот спустя пару месяцев наконец вышел сhallenge white paper, где описано само соревнование и полученные результаты. В качестве авторов статьи засветились и мы с Германом (правда я почему-то подписан как Paul, хоть и просил назвать меня Pavel 😡). В общем, это было весело и познавательно! Я думаю, что без участия в соревновании, я бы не погрузился настолько хорошо в тему топологических сеток, так что это того стоило.

Год назад мы с друзьями устраивали мини-курс по маломерной топологии, на котором Андрей Рябичев рассказывал всякое.
В этом же году мы стали больше, и делаем конференцию по топологии и анализу данных! Это все дело начнется завтра и будет идти 3 дня, по вечерам. Короче, приходите 😈

Уже прошло больше недели с того, как мы организовали конференцию по топологии, комбинаторике и анализу данных. По ощущениям, в этот раз пришло меньше людей, чем в прошлом, но в итоге все равно вышло круто!
Я рассказывал про устойчивые гомологии и топологический анализ данных, что, в общем, не удивительно. Правда рассказал не лучшим образом: готовился рассказывать одно, а рассказывал другое и по-другому. Что-то, что хотел осветить, просто не успел. Наверное, это приходит с опытом.
Мы записывали доклады, они уже выложены, и там даже есть какие-то просмотры 😼

Наконец решил по-нормальному вкатиться в этот ваш кеггл, а тут как раз идет подходящее соревнование: The Polytope Permutation Puzzle. Его суть заключается в нахождении оптимальных (в смысле числа шагов) решений головоломок по типу кубика Рубика.

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

Многие знают, что преобразования стандартного кубика Рубика (кубика размеров 3х3х3), то есть всякие повороты граней и все такое, образуют группу с нехитрым названием: группа кубика Рубика. Аналогично обстоит дело с кубиками Рубика и других размеров: 2х2х2, 4х4х4, 128х128х128 и т.д. Все (известные мне) алгоритмы так или иначе опираются теорию групп.

В чем же прикол соревнования? Ведь, раз есть алгоритмы, наверняка есть их реализации, достаточно просто их применить и все, получим решение?
Ну вот оказывается, что среди представленных головоломок есть не только кубики Рубика (хотя их и большинство). В то же время, солверы кубика Рубика обычно дают не самое оптимальное решение даже для стандартного кубика 3х3х3. Хотя задачу они, конечно, как-то решают. Да и более того, для кубиков Рубика больших размеров даже не известно, за сколько ходов их точно можно собрать (God's number известен только для кубиков 2х2х2 и 3х3х3, для всего остального есть всякие оценки)

Ну вот. А можно ли, имея какое-то решение, как-то его упростить? Ответ: Да! Уж попытаться точно стоит.
Раз каждая головоломка определяет какую-то (конечную) группу, то давайте попробуем эту группу как-то изучить. Например, было бы здорово получить ее копредставление. Образующие нам известны -- это те самые повороты граней кубика. В других головоломках какие-то свои преобразования. Осталось получить соотношения: такие последовательности преобразований, которые никак не меняют состояние головоломки. Получив их, можно будет упрощать любое решение! А именно, если есть некоторое решение, то остается найти в нем эти соотношения и удалить их из него, получив новое решение. Так как соотношения никак не меняют состояние головоломки, то новое решение действительно будет решением, но так как какие-то преобразования из него удаляются, оно будет более оптимальным.

Остается лишь одна проблема: находить соотношения довольно сложно с вычислительной точки зрения. Особенно для каких-то очень больших групп: для одной из групп из соревнования копредставление у меня считалось более 13 часов, после чего я просто его прервал. Для более простых их найти несложно, однако для них известные решения итак оказываются (почти) оптимальными. Наверное тут можно использовать всякие нейронки для поиска соотношений (в духе работ, где применяют нейросети к математике, как эта, эта или эта), как и в целом для ускорения разных алгоритмов компьютерной алгебры.

Про это все я сделал целую тетрадку. Там все это детальнее описано. Такие дела. Накидайте мне апвоутов

​​Graph & Geometric ML in 2024: Where We Are and What’s Next

📣 Two new blog posts - a comprehensive review of Graph and Geometric ML in 2023 with predictions for 2024. Together with Michael Bronstein, we asked 30 academic and industrial experts about the most important things happened in their areas and open challenges to be solved.

1️⃣ Part I: https://towardsdatascience.com/graph-geometric-ml-in-2024-where-we-are-and-whats-next-part-i-theory-architectures-3af5d38376e1

2️⃣ Part II: https://medium.com/towards-data-science/graph-geometric-ml-in-2024-where-we-are-and-whats-next-part-ii-applications-1ed786f7bf63

Part I covers: theory of GNNs, new and exotic message passing, going beyong graphs (with Topology, Geometric Algebras, and PDEs), robustness, graph transformers, new datasets, community events, and, of course, top memes of 2023 (that’s what you are here for, right).

Part II covers applications in structural biology, materials science, Molecular Dynamics and ML potentials, geometric generative models on manifolds, Very Large Graphs, algorithmic reasoning, knowledge graph reasoning, LLMs + Graphs, cool GNN applications, and The Geometric Wall Street Bulletin 💸

New things this year:

- the industrial perspective on important problems in structural biology that are often overlooked by researchers;
- The Geometric Wall Street Bulletin prepared with Nathan Benaich, the author of the State of AI report

It was a huge community effort and we are very grateful to all our experts for their availability around winter holidays. Here is the slide with all the contributors, the best “thank you” would be to follow all of them on Twitter!

Доказательство ссылкой на фильм

Соревнование закончилось больше 2 недель назад, пора подвести итоги:

Под конец соревнования объединился в команду, заняли в итоге 132/1054 место, до медальки не дотянули. Ну и ладно.
Основным нашим методом оказался алгоритм Минквица, с помощью которого мы оптимизировали имеющиеся решения. Strong generating sets и bases считались в GAP очень быстро с пакетом genss, в отличие от вычисления копредставления, о чем я писал в прошлом посте: как и ожидалось, для больших групп найти соотношения было очень тяжело.

Также оказалось, что собирать кубик Рубика/решать permutation puzzle можно с помощью целочисленного линейного программирования! А именно, можно сформулировать задачу сборки кубика как некоторую задачу минимизации, грубо говоря, числа шагов сборки, с кучей ограничений, которые и кодируют разрешенные движения/перестановки. Впрочем, лп-солверы тоже не идеальны, и на многих примерах не находили решение за какое-то разумное время.

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

В итоге, в рамках соревнования я сделал 4 тетрадки:
1. Group Theory of Santa Puzzles - теория групп 101, пару слов про копредставление, про общий подход к оптимизации решений на основе соотношений в группе
2. Group Theory via GAP - логическое продолжение предыдущей тетрадки с установкой GAP, подсчетом соотношений и вычислением bases и strong generating sets для групп паззлов
3. Permutation Puzzles as Integer Linear Programs - представление permutation puzzles как задачек целочисленного программирования и их решение с помощью PySCIPOpt
4. Stable Baselines for Cubes - небольшая попытка завести RL модельки в рамках соревнования (ultimately failed, но все равно вышло познавательно)

Сегодня в 19:00 по Мск на вебинаре Сберлоги будем обсуждать это соревнование тут, заходите, если интересно!

🚀 Субботний нетворкинг.
Позвольте порекомендовать Вам замечательные каналы, которые мы сами читаем сами и рекомендуем Вам:

@ivoryzoo - легендарный канал - "Зоопарк" держит руку на пульсе всего, что происходит в науке и образовании. Как им вообще удается отслеживать столько информации ?

@dealerAI - от одного из лучших специалистов в дата-сайнс и natural language processing - вы узнаете ключевые новости по этим темам

@datastorieslanguages - от не менее замечательного специалиста по дата сайнс, каггл грандмастера и полиглота Андрея Лукьяненко, вы узнаете все не только о дата сайнс, но и о том как изучать иностранные языки и о некоторых аспектах жизни за границей

@smart_lab_news @Nano_by_Nano @Polymer_scientists - Новости биотеха: научные события, конкурсы, конференции, гранты, вакансии и др. От научной группы ИБХФ РАН под руководством Елены Никольской

@finitely_presented - Теория групп, дата-сайнс и все вокгруг от нашего докладчика П.Снопова.

@diagrams_every_day - совершенно замечательный молодой канал - интереснейшие визуализации и объяснения простыми словами современных концепций в физике и математике - кто любит эти науки - обязательно подписывайтесь !

Подписывайтесь на эти замечательные каналы (и не забывайте о нас, Ваша @sberlogabig ) !

Эпичных видео про статьи — это то, что нам не хватало. Смотреть со звуком!

Трудно переоценить влияние работы "Attention is all you need" на развитие области в последние годы. Статья всего лишь набрала 109,160 цитирований, и аттеншн слои используются всего лишь почти в каждой современной архитектуре.

@ai_newz