Empty Set of Ideas

Начинаем чтение Mathematics without Numbers: Towards a Modal-Structural Interpretation, Hellman К сожалению, мы не нашли у Хеллмана никакой статьи, в которой он бы высказал свою позицию, поэтому решили попробовать за 3-4 недели прочитать его книгу. Своим главным источником вдохновения он называет статью Путнама "Mathematics without Foundations". Хеллман выделяет Сциллу и Харибду в философии математики: платонизм и конструктивизм. Первый хорош относительно вопросов математических истин, но проблематичен, когда речь идет о математическом знании. Второй же имеет преимущества и недостатки с точностью до наоборот. Хеллман хочет найти позицию, которая будет совмещать основные плюсы противоположных позиций и к тому же избежит их проблем. Встречаемся на нашем дискорд-сервере в пятницу 12 июля, в 19:00 по Москве, прочитать главу "1. The Natural Numbers and Analysis". Книга в первом комменте. Сервер: https://discord.gg/Pa4az2e7MC

Предыдущий пост "От моноидов к ∞-монадам" в виде pdf.

От моноидов к ∞-монадам Один коллега вовлёк меня в проект, где мне нужно пользоваться ∞-категориями, и ∞-монадами. В меня как-то ∞-монады с трудом заходили, и это побудило меня начать писать этот пост. Замысел был в том, чтобы рассказать про то, как идея моноида развивается на разных уровнях: обычный моноид, моноид в категории, моноидальная категория, моноид в моноидальной категории, монада, моноидальная ∞-категория, моноид в моноидальной ∞-категории, ∞-монада. Хотелось красиво показать, что это такая непрерывная спираль развития идей, в которой предыдущий этаж необходим для следующего. Однако в процессе написания этого поста я узнал, что есть эквивалентное определение ∞-монады, для которого не обязательно знать, что такое моноидальная ∞-категория. К тому моменту пост уже был очень большим, и мне он показался какой-то совершенно бессмысленной графоманией, и я передумал его постить. Но потом я вспомнил, что группа называется свалкой, и решил его запостить всё равно. Можете считать, что это что-то типа дневника моих попыток понять, что такое ∞-монада, и просто рассуждения на тему моноидального. ∙ Моноиды ∙ Моноидальные категории ∙ Моноиды в моноидальных категориях ∙ Монады ∙ Ходячий моноид ∙ О бухгалтерском учёте ∙ Расслоения Гротендика ∙ Псевдофункторы и расслоения ∙ Моноидальные категории как оп-расслоения ∙ Моноиды как сечения оп-расслоений ∙ Выпрямление-развыпрямление ∙ Моноидальные ∞-категории и моноиды в них ∙ Моноидальная ∞-категория эндофункторов ∙ ∞-монады ∙ Список литературы https://medium.com/@ivanov.s.o.1986/от-моноидов-к-монадам-46cac1e0fae6

Статья Gunnar Carlsson и Facundo Mémoli

Про функторы и кластеризацию В работе "An Impossibility Theorem for Clustering" (2002) Jon Kleinberg определяет три простых свойства, которым должна удовлетворять любая кластеризация, а затем доказывает, что ни один алгоритм кластеризации не может обладать всеми тремя свойствами одномоментно. Пусть дано множество S, состоящие из n ≥ 2 точек и некоторая полуметрика (без неравенства треугольника) на нем d:S×S→R. Пусть D(S) — множество полуметрик на S, а Π(S) — множество разбиений S на дизъюнктные подмножества. Тогда кластеризацией назовем функцию f: D(S) → Π(S), которая каждой полуметрике на S ставит в соответствие некоторое диз.разбиение. Kleinberg предложил следующие три свойства, которым должна отвечать каждая такая функция f: 1. Инвариантность относительно гомотетии (scale invariance): f(d) = f(alpha * d) для любых d из D(S) и alpha > 0 из R; 2. Насыщенность (?) или richness: f сюръекция; 3. Непротиворечивость или consistency: пусть есть две полуметрики d и d', а Г некоторое разбиение S. d' это Г-трансформация d, если d'(i,j)≤d(i,j) для всех пар из одного кластера в Г, аналогично d'(i,j) ≥ d(i,j) для всех пар в различных кластерах, тогда d и d' не противоречат друг друг, если d' это f(d) трансформация d, то f(d) = f(d'), т.е. кластеры уплотняются и расползаются при замене метрики d на d'; Существуют алгоритмы кластеризации, которые сочетают в себе любые 2 из 3 перечисленных свойств. Допустим S — множество вершина графа, а d(i,j) — вес ребра. Рассмотрим три функции кластеризации, которые находят подграфы, выбирая некоторое подмножество ребер: 1. выберем произвольное 1<k<n и упорядочим ребра по весу, будем добавлять ребра в подграф из упорядоченного списка ребер, пока он не будет иметь ровно k связных компонент; 2. выберем произвольное r и будем добавлять ребра с весом не меньшим r, полученные компоненты связности и назовем кластерами; 3. выберем произвольное 1 > alpha > 0 и пусть R это max(d). Будем сохранять ребра с весом не более alpha * d; Утверждение: Функция 1 удовлетворяет 1 и 3 (число кластеров ограничено k сверху), функция 2 удовлетворяет 2 и 3 (варьируем r, получаем разные разбиения и теряем инвариантность относительно гомотетии), а функция 3 удовлетворяет 1 и 2. И тут в дело врывается топологический анализ данных, с уже классической статьей "Classifying Clustering Schemes" (2013) by Gunnar Carlsson & Facundo Memoli. Ключевая идея их работы заключается в том, что эти свойства кластеризации могут быть закодированы как морфизмы в категории конечных метрических пространств таким образом, что ответом будет не функция кластеризации, а функтор кластеризации в подходящую категорию и он будет обладать уже всеми желанными свойствами.

Рассмотрим две категории: FinMetric конечных метрических пространств с морфизмами монотонными невозрастающими функциями и категорию Cluster состоящую из разбиений на кластеры S и морфизмов-подразбиений. Carlsson и Mémoli обнаружили, что единственные инвариантные относительно гомотетии функторы между FinMetric → Cluster это тривиальные разбиения на дискретные одноэлементные кластеры (число кластеров = числу точек в объекте) или антидискретное разбиение в один кластер, состоящий из всех объектов. Оба функтора не удовлетворяли условию 2 на сюръективность алгоритма кластеризации их статьи Клейнберга. Поэтому авторы решили заменить кластеры в привычном смысле на новый объект – персистентные кластеры. Персистентный кластер на S это функтор из частично-упорядоченной категории ([0, ∞), ≤) в чум кластеров на S, где φ ≤ ψ iff разбиение φ получается уточнением/подразбиением разбиения ψ. Идея состоит в том, что когда параметр r ∈ [0, ∞) мал, разбиение S может быть очень грубым и близким к дискретному, но кластерам разрешено расти при варьировании параметра r. Вместо категории Cluster необходимо рассматривать категорию PCluster, чьи объекты это уже персистентные кластеры, а морфизмы аналогичны морфизмам в Cluster, но для каждого выбранного r ∈ [0, ∞). Carlsson и Mémoli доказали, что существует единственный функтор из FinMet в PCluster, который удовлетворяет всем трем свойствам из статьи Клейнберга.

Why can't you tickle yourself? (2000) Уже ставшая классической работа с 1000+ цитирований про механизмы обратной связи, регулирующей восприятие согласно информации о наших собственных движениях. Существует предсказательная модель, которая говорит нам, что тот или иной сенсорный опыт важен, где важность опыта пропорциональна его новизне для организма: чем более неожиданный сенсорный сигнал мы получаем, тем больше внимания на него обращаем. Когда же мы щекочим себя сами, то новизна опыта стремится к нулю, так как мы с точностью можем предсказать данный сенсорный опыт. В статье они посмотрели на активность соматосенсорной коры (и еще пары областей), которая значительно падала в моменты самощекотания и наоборот при щекотании испытуемых кем-то.

Топология бассейна притяжения Lets switch gears Есть очень красивый чисто топологический сюжет, описанный Ветровым. Вот есть машобуч. В нем как правило надо подогнать какие-то параметры, так чтобы функция, заданная с помощью этих параметров хорошо интерполировала/экстраполировала обучающую выборку. Как правило это решается введением лосса - функции потерь, и минимизации этой функции методом градиентного спуска (или какими-нибудь инженерными свистелками, вроде стохастического градиента). С одной стороны, градиентный спуск - это превосходная вещь, интерпретируемая, легко прогается, связана с хорошей математикой вроде теории Морса. С другой стороны, мы учим студентов быть осторожными: если стоит задача найти глобальный минимум, то градиентный спуск может быть плохим помощником - вдруг мы свалимся в неправильный локальный минимум? И тут приходят машинщики и такие говорят "Мы применяем градиентный спуск, и он прямо очень хорошо работает, лучше, чем ожидается. Мы не сваливаемся в плохие локальные минимумы (где лосс маленький на трейне, и большой на тесте), а те, в которые сваливаемся - они прямо очень похожи на глобальные." Почему так? Полного ответа нет, но есть интересное наблюдение. Для функции f:R^d-->R (стремящейся к +∞ при x-->∞ и с глобальным минимумом 0 для простоты) рассмотрим фильтрацию подуровня LS(t)={x|f(x)<t}, lower set filtration, прямо как в топологическом анализе данных. Затапливаем график функции водой грубо говоря. И вот интуиция из матана, теории Морса и т.д. нам говорит, что при увеличении t вначале - в момент t=0 - возникнет озеро вокруг точки глобального минимума, потом возникнет озеро где-то в другом месте - в неправильном локальном минимуме, возникнут еще сколько-то озер. Потом, когда параметр t начнет проходить через критические значения в седловых точках, наши озера начнут объединяться в озера побольше и т.д. Однако, если размерность d равна 100500 триллионов, то картинка происходящего будет другой. При затоплении за очень малое время возникнут гуголы локальных минимумов, которые в это же самое время слипнутся в связный кластер. Концептуально это довольно понятно: морсовских значений должно быть настолько дохрена, что любой отрезок [0,ε] содержит как кучу значений индекса 0, так и кучу значений индекса 1, перестройки на которых сразу же соединяют болота в минимумах. Математически - есть про это интересные работы, например вот тут https://arxiv.org/abs/1110.5872 злой матан. Обсуждают про связь этих эффектов со спиновыми стёклами. Практически, есть работа Ветрова https://arxiv.org/abs/1802.10026 где показано, что если взять два случайных минимума функции потерь большой модели, то между ними можно проложить путь, целиком проходящий "по минимумам". Говоря иначе, множество LS(ε) при малых ε - связно. Более того, в качестве пути можно тупо взять двузвенную ломаную. Это всё, конечно, не означает, что теория Морса не работает. Но это означает, что на больших размерностях и "компьютерных" порядках малости теория Морса может дать неверные интуиции о происходящем.