Семинар Лаборатории топологии и сложных сетей

Мы рассмотрим функционал свободной энергии для эластичной мембраны, приходящий из теории упругости для тонких пластинок по Тимошенко—Войновскому-Кригеру и Ландау—Лифшицу. Рассматривая этот функционал как Гамильтониан в статистической

В докладе будет рассмотрена модификация задачи о справедливом дележе (EFX), в которой игроки представлены вершинами графа, предметы — ребрами, а ориентация задает, кому достается предмет. Оказывается, что в такой постановке существование справедливого дележа зависит от хроматического числа графа: при 2 он всегда существует, в то время как при 4 и более для любого графа существуют оценки предметов, приводящие к его отсутствию.

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

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

Авторы предлагают новый геометро-топологический дескриптор — миксап-штрихкод. Он описывает не только форму облака точек, но и то, как это облако взаимодействует с другим облаком, вложенным в то же пространство. Технически, миксап-штрихкод обогащает стандартный штрихкод персистентной гомологии информацией об образе персистентной гомологии включения одного облака в объединение. В трёх измерениях он улавливает такие явления, как перекрытие, окружение и заключение одного облака внутри другого; в более высоких размерностях — более тонкие, пока не получившие названия взаимодействия.

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

Я расскажу про reservoir computing и echo state networks — довольно необычный подход к рекуррентным нейросетям, где почти ничего не обучается

Идея в том, что внутренняя часть сети остаётся случайной и фиксированной, а обучается только линейный выходной слой, но при этом сеть всё равно умеет работать с временными рядами, памятью и даже хаотическими системами. Поговорим про то, что такое echo state property, почему это вообще работает, и разберём классическую статью Jaeger’а 2001 года, с которой всё началось. 

Cohomological networks

In many applications, electrical networks appear with boundary conditions other than the usual Dirichlet and Neumann ones, and their mixture. For instance, in networks on surfaces, one often prescribes voltage drops along topologically nontrivial loops on the surface. Special boundary conditions also arise in electromagnetic circuits, introduced by Milton and Seppecher.  

We develop a general framework for working with such cohomological boundary conditions in the discrete setup. We adopt the classical concepts and theorems, such as the response matrix and the existence and uniqueness theorem. Our main result is a generalization of all-minors Kirchhoff's matrix-tree theorem, a combinatorial formula for the minors of the response matrix in terms of certain subgraphs, in the spirit of Kenyon and Wilson's enumeration of groves. This generalization is challenging because the subgraphs can now contribute with arbitrary integer coefficients. The proof uses tools from statistical physics, such as Smirnov's parafermionic observables and the double-dimer model.

This is joint work with P. Pylyavskyy and S. Shirokovskikh.

 ссылка на семинар

Градиентный спуск является основным алгоритмом машинного обучения, и динамика градиентных потоков в больших задачах представляет значительный интерес. Мы пытаемся развить новый метод ее исследования, основанный на разложении функции потерь в степенной ряд по времени. При стандартной гауссовой инициализации модели коэффициенты такого разложения можно описать с помощью теоремы Вика в виде некоторых диаграмм, аналогичных диаграммам Фейнмана. Далее, переходя к пределу большого размера модели, можно найти различные формальные пределы этого разложения в зависимости от взаимного масштабирования параметров задачи. Эти пределы можно связать с различными качественными режимами обучения - например, свободной эволюцией или т.н. режимом NTK. Кроме того, получаемые предельные разложения в некоторых случаях допускают формальное суммирование, дающее явную аналитическую формулу динамики. Для этого мы записываем рекуррентные соотношения между коэффициентами в виде УрЧП, и если оно имеет первый порядок, решаем его с помощью метода характеристик. В задаче факторизации тензора порядка 4 такое интегрирование дает явную аналитическую функцию, определенную для отрицательных времен, т.е. для "градиентного подъема". Решение показывает, что есть два разных режима подъема, сходящийся и расходящийся, и дает конкретный количественный критерий их разделения. В целом, теория в текущем виде вызывает много математических вопросов, но получаемые результаты хорошо согласуются с численными экспериментами. Работа выполнена совместно с Е. Голиковым и Я. Гусевым.

На семинаре я расскажу немного о том, какие актуальные проблемы есть в задаче планирования маршрутизации в оптических сетях. Поговорим о том, как моделировать инфраструктурные сети, какие есть проблемы в том чтобы смоделировать поток на них (и как их можно решить), а также о том как решать задачи маршрутизации многих запросов (multi-commodity flow) для ситуаций когда важно понимать как перепрокладывать маршруты в случае падений в сети.

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

Доклад начнётся с пересказа основных результатов исследований графов Эрдёша–Реньи: критериев их связности/несвязности, а также связности компонент. Затем мы сместимся к моделям предпочтительного присоединения, в частности к моделям типа Барабаши–Альберт: средней степени вершины (конкретной, первой, не первой), распределению степеней вершин. А также будут затронуты обобщения модели БА, а именно модель Айелло и модели БА с привлекательностью.

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

Мы поговорим про Monte Carlo Tree Search и его последователя – алгоритм AlphaZero.

AlphaZero был разработан командой DeepMind и позволил компьютерам в 2016 году впервые достичь superhuman-уровня в игре Go. Этот же алгоритм, обученный играть в шахматы, с разгромом превзошел лучший на тот момент шахматный движок Stockfish. Главная и самая впечатляющая особенность их решения – отсутствие у алгоритма каких-либо начальных знаний об этих играх, кроме правил!

Никакие теоретические пререквизиты к слушателям не предъявляются.

Мы обсудим некоторые аспекты сжатия графов. Начнем со статьи ''Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations'' и обзора общих принципов сжатия больших графов. Также мы попробуем разобраться в некоторых отдельных алгоритмах (пока точно планируется GraphZIP).

Теория графовых комплексов  возникла на стыке алгебраической топологии, гомологической алгебры и математической физики. Самые известные графовые комплексы были придуманы Максимом Концевичем в контексте решения проблемы деформационного квантования Пуассоновых структур на многообразиях. Позднее они нашли применение в теории квантовых групп (классифицируют гомотопические классы квантований Ли биалгебр), в теории длинных узлов, в теории гомологий пространств модулей алгебраических кривых, и пр.

Лекция посвящена элементарному введению в эту теорию. Требуется только понимание, что такое комплекс, и что такое (ко)гомологии комплекса.

Лапласиан — это оператор, изначально определённый для многообразий в контексте дифференциальной геометрии, однако в последние годы получили развитие его дискретные аналоги. Так, самый известный из них, графовый Лапласиан, применяется, например, для кластеризации вершин графа. А оператор уже на  симплициальных комплексах (комбинаторный / Ходж-Лапласиан) позволяет следить за структурой старших размерностей.

В дискретном случае по Лапласиану можно восстановить информацию о топологических особенностях комплекса, так как его ядро совпадает с гомологиями. И, более того, его собственные вектора с ненулевыми значениями связаны с геометрической структурой облака данных / графа.

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

Таким образом персистентный Лапласиан вбирает в себя топологическую составляющую (через информацию о его ядре и фильтрацию), а также дополнительно несёт информацию и о геометрической структуре. Такое слияние подходов оказалось не просто интересным теоретическим объектом, но и показало лучшие результаты в контексте feature engineering в машинном обучении.
В рамках доклада я расскажу про обычный Лапласиан, фильтрации и конструкцию их объединения в виде персистентного Лапласиана.