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

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

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

Если считать, что данные (объекты) живут в близкой окрестности маломерного многообразия (топологического пространства), а нейросеть — это не что иное, как просто композиция функций (слоёв), то можно исследовать, как именно меняется топология пространства объектов при последовательном применении слоёв сети.

Этим вопросом задались авторы статьи "Topology of Deep Neural Networks", и про неё я расскажу на докладе

n—мерное многообразие называется гиперэллиптическим, если на нём существует инволюция, пространство орбит которой гомеоморфно сфере. Такая инволюция называется гиперэллиптической. Пользуясь понятиями гамильтоновых цикла, тэта-подграфа и K_4-подграфа на трёхмерном прямоугольном многограннике,  А.Д.Медных  и А.Ю.Веснин построили примеры трёхмерных гиперэллиптических многообразий в геометриях R^3, S^3, L^3, L^2xR и S^2xR.

Мы обобщаем эту конструкция на n-мерный случай. В этом случае мы вводим понятие гамильтонова C(n,k)-подкомплекса в границе простого n-мерного многогранника c m гипергранями и показываем, что каждый такой подкомплекс  Г отвечает некоторой подгруппе ранга m-k-1 в Z_2^m, свободно действующей на  вещественном момент-угол многообразии RZ_P, пространство орбит N(P,Г) которой является многообразием, склеенным из 2^{k+1} копий многогранника. На N(P,Г) действует группа Z_2^{k+1}, и в ней есть гиперэллиптическая инволюция.  

Для произвольных n>3 мы показываем, что прямоугольные многогранники в L^n, R^n, L^3xR, L^2xR^2 не допускают гамильтоновых C(n,k)-подкомплексов. В то же время существуют прямоугольные многогранники с такой структурой в геометриях S^n, S^pxR,  S^pxR^2, S^kxS^l, S^pxS^qxR, S^2xL^2, L^2xL^2.  

Особый интерес представляют гамильтоновы C(n,n-1)-подкомплексы в границе простого n-мерного многогранника. Они отвечают гиперэллиптическим малым накрытиям. Каждый такой комплекс задаётся гамильтоновым циклом в многограннике, трансверсально пересекающим дизъюнктный набор из m-n+1 граней коразмерности два, каждая из которых допускает раскраску гиперграней в n-2 цвета (эквивалентно, все её двумерные грани имеют чётное число сторон).  Первый пример такой структуры построил Алексей Корецкий на 4-мерном многограннике с 9 гипергранями. Открытым является вопрос, существуют ли такие структуры на прямоугольных многогранниках в размерности больше трёх и произвольных многогранниках в размерностях больше четырёх.

Преобразование «звезда-треугольник» играет достаточно важную нетривиальную роль как в теории электрических цепей, так и в статистической физике. Если в первом случае преобразование согласует токи, протекающие в системе, то в статистической физике данное преобразование может служить ключом к точному решению определенных классов моделей на решетках. Такая топологическая изменчивость системы, связанная с дуальностью преобразования «звезда-треугольник» и сохраняющая некоторые свойства системы, безусловно, интересна при рассмотрении вероятностных переходов в сложных системах, например, в марковских цепях. Марковские цепи являются, в каком-то смысле, обобщением обычных электрических цепей, поскольку в общем случае существует вероятность не изменить своего состояния на каждом шагу. Эффективно добавить данную особенность в электрические цепи можно, однако классические формулы преобразования «звезда-треугольник» этого не учитывают. Было показано, что в марковских цепях преобразование «звезда-треугольник» накладывает существенные ограничения на стохастическую матрицу переходов в случае «треугольника», связанные как с классическим симплексом, так и с сохранением детального баланса. Более того, в марковских цепях эквивалентом протекающего между узлами тока служит среднее время первого попадания (mean first-hitting time). Тем самым устанавливается эквивалентность среднего времени первого попадания в случае «звезды» и «треугольника», однако естественным образом появляется вопрос о том, как ведут себя высшие моменты распределения времени первого попадания.

In toric geometry and topology, a key example is the complex projective space with the standard torus action. A natural generalization of this example is the Grassmannian G_n,2 of projective lines in complex projective space with the standard action of an n-dimensional torus. Describing the equivariant topology of this manifold is a hard problem, the solution of which requires the involvement of various combinatorial structures: graphic matroids and matroid polytopes within the hypersimplex \Delta_n,2. This talk aims to provide an overview of the combinatorial results obtained in the context of this problem, as well as their applications to the well-known Johnson graph J(n,2).

Во втором докладе мы переходим от топологической линии первой лекции к group-equivariant и gauge-equivariant CNN. Практическая мотивация та же: архитектура эффективнее, когда операторы слоя согласованы со структурой данных. На примере Cohen et al. (2016) и Cohen et al. (2019) покажем, как глобальные симметрии и локальные системы координат задают класс допустимых сверток. Главная идея: топологические и эквивариантные CNN реализуют один и тот же принцип согласования архитектуры с геометрией данных.

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

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

В докладе рассматриваются топологические и эквивариантные сверточные сети и обозреваются общие принципы их построения. Основная практическая мотивация: эффективные архитектуры сетей возникают тогда, когда операторы слоя ограничиваются в соответствии со структурой данных. В центре доклада серия работ (Carlsson et al. 2008 -> ... -> Love et al. 2023), где топология представлений естественных изображений переводится в архитектуру сверточных слоев, что улучшает обучение. Далее будут представлены group-equivariant CNNs (Cohen and Welling 2016), в которых ограничения архитектуры задаются выбранной группой симметрий. Если останется время, то мы кратко обсудим gauge-euqivariant CNNs (Cohen et al. 2019) как возможное обобщение обоих подходов.

В докладе мы попробуем разобрать недавний результат про нижнюю оценку на distortion для графовых покрытий (Tree covers). Мы начнем с достаточно простых случаев, когда количество деревьев в покрытии равняется 1 или 2, где с помощью достаточно красивых комбинаторных идей удается получить хорошие оценки. В оставшееся же время попробуем разобрать случай произвольного количества деревьев. 

В докладе   будут затронуты следующие сюжеты:

- схематичный обзор применений обобщенной модели Изинга в физике (модель Изинга в слуачйном внешнем поле, спиновое стекло), машинном обучении (графические модели, сеть Хопфилда, машины Больцмана) и теории игр(игры с зашумленным дискретным выбором на графах)

- детальный анализ статических равновесий в модели/игре Изинга на полном графе

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

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

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

Для детекции таких ситуаций на Интернет-платформах естественным образом прибегают к сетевому анализу. В работе мы рассматриваем одну из статистических процедур, применяемых для обнаружения тенденции пользователей взаимодействовать именно с “соратниками”. Эта процедура основана на расчёте статистики, называемой “E-I индекс”. Представленные в литературе версии процедуры подразумевают необходимость дорогостоящих симуляций случайных графов – именно таким образом оценивается распределение статистики, соответствующее верной нулевой гипотезе. Мы показываем, как можно избежать симуляций и вывести получаемые в их процессе распределения аналитически, сведя таким образом вычислительно затратную процедуру к формульному виду. Пользуясь этим результатом, мы на реальных данных исследуем процедуру на предмет устойчивости к выбросам, к неточности разметки (какой пользователь к какому лагерю принадлежит) и к иным вещам – чего ранее не делалось. На наших данных процедура показывает себя достаточно устойчивой, что подтверждает результаты авторов, использовавших её ранее, а также упрощает использование процедуры в будущих исследованиях.

Перекладывания отрезков (IET) возникли в 60-х годах как обобщение поворотов окружности, а также как отображения первого возвращения на трансверсаль для бильярдных потоков в рациональных многоугольниках. Перекладывание называется минимальным, если все его бесконечные орбиты всюду плотны. М. Кин показал, что почти все IET минимальны. Впоследствии Г. Мазур и У. Вич доказали, что почти каждое перекладывание отрезков строго эргодично.
Перекладывания отрезков с флипами (FIET) являются обобщением классических IET. Динамика FIET отличается от динамики классических IET. Так, А. Ногейра доказал, что типичное FIET не является минимальным. Вследствие этого класс минимальных FIET остается малоизученным. Тем не менее, определенный прогресс был достигнут. Хаусдорфова размерность множества минимальных FIET была оценена А. Скрипченко и С. Трубецким. Также А. Линеро Бас и Г. Солер Лопес установили существование минимального нестрого эргодичного примера FIET на 6 отрезках, имеющего две различные инвариантные эргодические меры.
В докладе речь пойдет о нестрого эргодичных примерах IET с максимально допустимым числом различных инвариантных эргодических мер, а также о некоторых методах, позволяющих строить новые нестрого эргодичные примеры FIET.

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