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

Наконец решил по-нормальному вкатиться в этот ваш кеггл, а тут как раз идет подходящее соревнование: 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

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

Уже прошло больше месяца с нашего мероприятия в Воронеже, а я не написал о том, как оно прошло. Давайте исправлю.

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

Как всегда, у нас есть записи докладов: посмотреть можно тут.

Недавно прошла ICLR 2024. Собрал запоминающиеся и важные статьи по интересным мне темам.

Knowledge Graph Reasoning and Question Answering - рассуждение и генерация ответов на графах знаний.

1. Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning - ответим на вопрос "Кто ребенок Алисы?". Сначала на стадии планирования генерируем LLMкой путь отношений z = {marry to → father of}, затем накладываем его на граф знаний wz = (Alice) marry to → (Bob) father of → (Charlie), из структуры графа получаем ответ Charlie. Т.е. в каком-то смысле паттерн-матчинг. LLM знает про структуру графа и через Planning optimization учится создавать все более релевантные пути отношений.

LLM и все, что в них обитает:

1. Unveiling the Pitfalls of Knowledge Editing for Large Language Models - авторы исследуют проблемы, возникающие в процессе редактирования знаний внутри LLM, более подробно в прошлом посте. Из-за запутанной структуры знаний внутри LLM после редактирования появляются необратимые изменения (метастазы), отражающиеся на множество других сопряженных знаний. Даже если измененный факт отредактировать обратно, то на последствия исходного изменения это не повлияет. Еще рассматриваются логические противоречивые хирургий знаний и их следствия. Тема очень важная в контексте Safety AI.

2. The Geometry of Truth: Emergent Linear Structure in Large Language Model Representations of True/False Datasets - геометрия правды и лжи. По моему мнению, самая интересная статья на конфе. Авторы показывают, что истинные и ложные утверждения образуют разделимые линейные структуры во внутренних представлениях LLM

World Modeling - задача изучения богатого представления, которое учитывает динамику среды, что позволяет агенту прогнозировать будущие состояния и последствия своих действий. Классическое поле тестирования агентов - Minecraft.

1. Mastering Memory Tasks with World Models - продолжение и развитие идеи DreamerV3, В Статье улучшает структуру памяти агента из DreamerV3 и позволяет учитывать более долгосрочные зависимости в Модели Мира, может предсказывать на большее кол-во шагов вперед.

На свободную тематику:

1. Talk like a graph: Encoding graphs for large language models - идея крайне простая, но любопытная: как можно энкодить графы внутрь LLM? Спойлер: если в промпте граф описываешь не просто перечислением вершин и ребер: "G граф с нодами 0...8, и ребрами: (0,1),(0,2)…(7,8).", а через структуру отношений в терминах Игры Престолов: "G граф взаимоотношений разных персонажей Ned, Cat, Daenerys...Jaime. В этом графе: Ned and Cat дружат...Cersei and Jaime дружат.", то LLM лучше воспринимает граф, и может больше про него сказать всякой чисто графовой инфы, типа сколько компонент связности, какая степень вершины итд. Всего Тестировалось 9 способов промптить граф.

2. Interpreting CLIP's Image Representation via Text-Based Decomposition - интерпретация внутренней структуры ViT из CLIP. Авторы определяют, какая голова ViT за какой смысловой аспект отвечает. То, что на головах происходит диверсефикация фичей, т.е. разные головы смотрят на разные объекты и уровни абстракции - это известно еще со статьи, где саму архитектуру ViT предлагали, но в данной работе конкретизируется, какая голова отвечает за форму, какая за цвета, итд. Статья - существенный вклад в explainable AI.

3. ULTRA Towards Foundation Models for Knowledge Graph Reasoning - предлагается архитектура фундаментальной модели GNN. Более подробно в этом посте.

4. Neural Network Expressive Power Analysis Via Manifold Topology - оценивается верхняя граница длины FC сети в терминах топологической сложности (сумма чисел Бетти) обучающих данных. В статье все строго доказывается, и это была бы очень хорошая работа, если бы не ограничение на размерность многообразия = 3, но мб это хороший старт для обобщения на произвольную размерность. Ну и все оценки, завязанные на сумму чисел Бетти для облаков точек тоже достаточно спекулятивные. Статья реджектнута.

Год назад я писал, что поступил в University of Texas Rio Grande Valley: это такой университет в Техасе, рядом: граница с Мексикой, SpaceX Starbase и море, где зима - это когда вместо 25+ градусов, всего лишь 15. После этого я писал про наши мероприятия в Воронеже и все такое. Так что же у меня с Америкой?

В августе мое трехмесячное пребывание в Хуавее окончилось. Мне предложили продлить контракт, но тогда я бы не успел уволиться, чтобы, при положительном решении по визе, я мог улететь в Техас. Поэтому было решено контракт не продлевать. Я доработал в Хуавее, уволился, и начал готовиться: покупать билеты в Астану (я записался в посольство именно туда), прорабатывать ответы на типичные вопросы и все в таком духе.

Поездка в Астану получилась интересной: мы с Сашей там были неделю, и это была наша первая совместная поездка за границу. Контрастный город, уже миллионник, выросший в численности за последние 15-20 лет.

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

Так что вместо Техаса, я уже почти год как являюсь аспирантом в ИППИ.

А тем временем в ИППИ ...