Топология-2. Лекция 2

Смотреть на YouTube

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

Топологический анализ данных

Данные – это большое конечное множество точек $V$ в пространстве, скажем, очень большой размерности; между ними есть расстояние. Букву $V$ я выбрал потому, что это будут вершины симплициального комплекса. Хочется проанализировать форму этого множества, shape of data. Что имеется в виду? Допустим, мне дали много точек на плоскости, и верится, что они лежат на окружности: точки насэмплированы, это выборка из независимых одинаково распределённых случайных величин с распределением, сосредоточенным вблизи некоторого многообразия. Ожидается, что это многообразие интересное, какое-то нетривиальное топологическое пространство. На плоскости мы это видим глазами, а в реальности точек может быть сто тысяч в пространстве размерности миллион. Есть алгоритмы понижения размерности: незначительно исказив расстояния, понизить размерность объемлющего пространства и дальше рисовать графики. Здесь идея другая.

Топологию дискретного множества изучать бессмысленно, она тривиальна. Поэтому каждую точку заменяем на шар маленького радиуса и рассматриваем пространство

B_{ε} (V) = v \in V ⋃ B_{ε} (v),

объединение шаров радиуса $ε$ с центрами в точках $V$ ; открытые они или замкнутые, не особенно важно. Шары берутся в объемлющем пространстве; вообще $R^{N}$ можно заменить на любое метрическое пространство, в которое вложено $V$ ; метрики бывают разные.

Если $ε$ совсем маленький, это плохо: $B_{ε} (V)$ гомотопически эквивалентно дискретному множеству точек. Если $ε$ слишком большой, тоже плохо: окрестность множества стягиваема, точки слипаются в один большой шар, мы на них смотрим издалека. Поэтому хочется посмотреть на промежуточные значения; в нашем примере при подходящем $ε$ объединение шариков вполне отражает топологию окружности, вблизи которой лежат точки. Но заранее неизвестно, какое значение брать; значит, надо рассмотреть все значения сразу. (Вопрос: а если интересна сама динамика топологии по $ε$ ? Она тоже может быть интересна, но изначальная идея в том, что есть «правильный» $ε$ , не слишком большой и не слишком маленький.)

TikZ diagram — Точки, насэмплированные вблизи окружности, и $B_{ε} (V)$ при трёх значениях $ε$ : дискретное множество, что-то вроде окружности, стягиваемое пятно.

Персистентные модули

Мы в этом курсе изучаем гомологии и поймём, что каждому топологическому пространству соответствует набор абелевых групп, его группы гомологий, а отображениям пространств отвечают гомоморфизмы групп гомологий. Гомологии есть то, что в действительности можно посчитать. Так что рассмотрим гомологии каждого из пространств $B_{ε} (V)$ при всех $ε$ . Они образуют то, что называется персистентным модулем.

Определение (Персистентный модуль). Персистентный модуль – набор абелевых групп $A_{ε}$ , по одной для каждого $ε > 0$ , и гомоморфизмов $A_{ε} \to A_{δ}$ для всех $ε \leq δ$ , согласованных друг с другом: гомоморфизм $A_{ε} \to A_{ε}$ тождественный, а композиция $A_{ε} \to A_{δ} \to A_{η}$ равна $A_{ε} \to A_{η}$ .

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

Ровно это происходит с гомологиями объединений шаров. Если $ε < δ$ , есть естественное вложение $B_{ε} (V) \subset B_{δ} (V)$ , и мы обсудим, почему оно даёт гомоморфизм $H_{n} (B_{ε} (V)) \to H_{n} (B_{δ} (V))$ : мы докажем, что любое непрерывное отображение топологических пространств индуцирует гомоморфизм групп гомологий. Согласованность следует из того, что взятие гомологий – функтор: вложения $B_{ε} \subset B_{δ} \subset B_{η}$ образуют коммутативную диаграмму, а коммутативная диаграмма под действием функтора переходит в коммутативную. Для симплициальных гомологий мы этого не обсуждали, это задача в листочке; это довольно нетривиальный сюжет: даже смена порядка вершин нетривиальна, там симплексы надо домножать на знаки перестановок.

Итак, набору точек сопоставлен персистентный модуль. Как его себе представлять и что с ним делать? Оказывается, алгебраическая структура тут довольно простая, если считать гомологии с коэффициентами в поле; над целыми числами всё сложнее. Упрощаем: приводим к каноническому виду.

На практике множество $V$ конечно. Для каждого момента времени $ε$ есть своё пространство, и их топология разная: сначала пять точек, потом пять шаров, потом пять шаров, два из которых пересекаются, потом ещё что-то, потом всё слиплось. Но понятно, что гомотопический тип меняется конечное число раз: если $V$ конечно, гомотопический тип $B_{ε} (V)$ меняется конечное число раз. Про гомологии мы докажем, что у гомотопически эквивалентных пространств они одинаковые, – значит, вплоть до критического момента, когда два шара коснутся, гомологии не меняются. Отсюда персистентный модуль тоже меняется конечное число раз: есть критические моменты, когда какие-то шары начинают касаться, и только в эти моменты что-то происходит. Поэтому можно думать не про континуальный набор, а про цепочку групп и гомоморфизмов

A_{ε_{1}} ⟶ A_{ε_{2}} ⟶ \dots ⟶ A_{ε_{m}},

где к каждой группе приписан момент времени $ε_{i}$ , в который она взята. Такие персистентные модули будем называть кусочно постоянными (слово выбрано голосованием: «конечного типа» не подходит, так стоило бы называть модули, у которых каждая группа конечно порождена). Мы запускаем процесс раздувания шаров из изучаемых точек; в конце концов получим стягиваемое пространство, но пока мы его получим, много всего интересного произойдёт.

Структурная теорема и баркод

Пусть теперь гомологии считаются с коэффициентами в поле $k$ , так что все $A_{ε}$ суть векторные пространства над $k$ . Очевидные персистентные модули, которые можно себе придумать: везде нули; потом в какой-то момент $s$ родился одномерный модуль $k$ ; дальше он изоморфно отображается в себя; в какой-то момент $t$ умер, и больше ничего нет. Он мог родиться и сразу умереть, а мог никогда не умереть.

Определение (Интервальный модуль). Для $0 < s < t \leq + \infty$ интервальный модуль $k [s, t)$ – персистентный модуль, у которого $A_{ε} = k$ при $ε \in [s, t)$ и $A_{ε} = 0$ иначе, а все отображения между ненулевыми членами тождественные.

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

Теорема (Структурная теорема). Любой кусочно постоянный персистентный модуль над полем $k$ с конечномерными $A_{ε}$ – прямая сумма конечного числа интервальных модулей $k [s, t)$ .

Модуль, который никогда не умирает, это, например, нулевые гомологии: они не умирают никогда; в нашем примере все остальные, конечно, умирают.

Доказательств два. Первое: такая цепочка $k$ -модулей и линейных отображений есть градуированный модуль над кольцом многочленов $k [t]$ от одной переменной. Если все отображения обозначить одной буквой $f$ , то многочлен, скажем $t^{2} - 5 t + 7$ , действует на элемент $x$ по определению как $f (f (x)) - 5 f (x) + 7 x$ . Кольцо многочленов над полем от одной переменной есть кольцо главных идеалов, дальше используется структурная теорема о конечно порождённых модулях над такими кольцами, в градуированном варианте, поскольку изоморфизм должен сохранять градуировку. (Из зала заметили, что обычная структурная теорема градуировку не сохраняет и неразложимые представления колчана $A_{n}$ устроены не так же, как градуированные; лектор взял ссылку на структурную теорему в кавычки: для градуированных модулей над градуированными кольцами главных однородных идеалов «что-то в таком духе есть», а можно подходить и через теорию колчанов.)

Второе доказательство: явный алгоритм, линейная алгебра первого курса. Идём по индукции по цепочке слева направо. Каждый модуль рисуем полосочкой, $ε$ растёт; дожив до момента $ε_{0}$ , мы уже верим, что модуль до этого момента есть прямая сумма интервальных: каждая полосочка это одномерный модуль, который в какой-то момент родился и, может быть, умер. В момент $ε_{0}$ у нас конечномерное пространство $k^{n}$ с базисом $e_{1}, \dots, e_{n}$ из тех, кто дожил, отсортированным по времени рождения, сначала родившиеся раньше. В следующий момент возникает $k^{m}$ и линейный оператор $A : k^{n} \to k^{m}$ , матрица $m \times n$ . Хочу привести $A$ к диагональному виду, где на диагонали сколько-то единиц, потом нули, а всё остальное нули, то есть к нормальной форме Смита: тогда какие-то полосочки выживут, какие-то умрут, и картинка снова будет как раньше. Что разрешено?

Менять базис в $k^{m}$ как угодно, то есть любые преобразования строк: там ещё ничего не разложено.
В $k^{n}$ заменять $e_{i}$ на $e_{i} + \sum_{j < i} λ_{j} e_{j}$ , то есть прибавлять к базисному вектору тех, кто родился раньше него. Полосочки это прямые слагаемые модуля до момента $ε_{0}$ ; если к новой порождающей, родившейся в какой-то момент, прибавить более старую, всю цепочку до этого момента можно оставить как была: разложение до $ε_{0}$ не меняется. Это преобразования столбцов: к столбцу прибавляются предыдущие.

Берём любую матрицу $A$ . Элементарными преобразованиями строк приводим её к улучшенному ступенчатому виду. Затем каждому столбцу прибавляем предыдущие с нужными коэффициентами и стираем все звёздочки; получается диагональная матрица из единиц и нулей. Всё. Это не обязательно запоминать, но так видно, что всё работает.

Это случай кусочно постоянных модулей с конечномерными группами. Люди разобрались и с общим случаем, когда нет ни кусочной постоянности, ни конечномерности, но всё ещё над полем; там тоже работают аналогичные теоремы; на практике всё конечномерно и кусочно постоянно.

Вывод: всякий такой персистентный модуль над полем есть прямая сумма модулей $k [s, t)$ , и его можно нарисовать: каждому слагаемому отвечает полуинтервал от $s$ до $t$ , то есть отрезочек, луч или точка.

Определение (Баркод). Диаграмма, на которой персистентный модуль $⨁_{i} k [s_{i}, t_{i})$ изображён набором полуинтервалов $[s_{i}, t_{i})$ , называется его баркодом.

Bar значит перекладина, линия, code значит код; по-английски barcode это буквально штрихкод, как в аэропорту. Откуда слово «персистентный»: persistence, устойчивость в смысле «ты никуда не деваешься».

В примере, где точки накиданы вблизи окружности, можно посчитать гомологии получающихся пространств. Сначала точки понемногу склеиваются, потом склеиваются во что-то вроде окружности (я описываю гомотопический тип), потом оно всё склеивается в точку. Следим за нулевыми гомологиями: сначала столько копий, сколько точек; в конце концов выживает одна, а остальные умирают – кто раньше, кто позже. Ещё есть первые гомологии. Мы выясним, что $H_{1}$ окружности – это $Z$ , а у стягиваемого множества первые гомологии тривиальны. Значит, в какой-то момент родилась окружность, и она живёт, пока всё не стянется в точку.

Если накидать много точек вблизи окружности и проделать эту процедуру, получатся мусорные данные, которые надо игнорировать, и ценные для нас данные, фичи, про которые мы верим, что это что-то осмысленное. Понятно, что чем больше $t - s$ , тем больше шансов, что это не мусор. Если точки накиданы на окружности радиуса $R$ , длина полоски первых гомологий будет примерно $R$ , а длина мусорных полосок – примерно расстояние $r$ между соседними точками. Когда точек много, $r$ маленькое и уменьшается, а $R$ остаётся; при триллионе точек мусора почти не будет видно.

Итак, пайплайн: конечное множество точек $V$ ; по нему фильтрованное топологическое пространство, цепочка вложенных друг в друга пространств $B_{ε} (V)$ ; его гомологии образуют персистентный модуль; из него получается баркод $B (V)$ :

V ⟼ {B_{ε} (V)}_{ε > 0} ⟼ {H_{n} (B_{ε} (V))}_{ε > 0} ⟼ B (V) .

Баркод это уже чисто конечный набор данных, набор вещественных чисел: отрезочки, лучи и точки. Это наша фича, инструмент, который можно анализировать, запускать на нём классификаторы и так далее.

Замечание (персистентный не значит фильтрованный). Персистентный модуль не является фильтрованным модулем, и путать эти понятия не надо. Фильтрованный модуль это цепочка модулей, которые вкладываются друг в друга; здесь же отображения могут иметь ядра, гомологии умирают.

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

Комплексы Виеториса–Рипса и Чеха

Посчитать на компьютере группы гомологий $B_{ε} (V)$ по множеству $V$ и расстояниям между точками сложно: у нас есть пространство, склеенное из шаров, по нему надо ещё построить что-то, гомологии чего можно посчитать. Идея в том, чтобы вместо этих пространств рассматривать симплициальные комплексы: комплекс Виеториса–Рипса и комплекс Чеха. Оказывается, гомологии $B_{ε} (V)$ такие же, как гомологии комплекса Чеха; у комплекса Виеториса–Рипса гомологии другие, но его проще считать, и в каком-то смысле он близок к комплексу Чеха. Это фильтрованные симплициальные комплексы, а для них гомологии уже можно посчитать: это симплициальные гомологии, которые мы обсуждали.

Определение (Комплекс Виеториса–Рипса). Пусть $V$ – конечное метрическое пространство и $ε > 0$ . Комплекс Виеториса–Рипса $VR_{ε} (V)$ – симплициальный комплекс на множестве вершин $V$ , в который входят те наборы вершин $I \subset V$ , точки которых попарно находятся на расстоянии не больше $ε$ , то есть $diam I \leq ε$ .

Аксиома симплициального комплекса, очевидно, выполнена. Если $ε$ примерно такой, что расстояния между тремя точками все меньше $ε$ , добавляем весь треугольник; если от четвёртой точки до одной из них тоже не больше $ε$ , добавляем это ребро, а ребро до более далёкой точки не добавляем; если четыре точки близки, рисую весь тетраэдр.

Когда $ε$ растёт, комплекс ведёт себя похоже на объединение шаров: $VR_{ε} (V)$ вкладывается в $VR_{δ} (V)$ при $ε \leq δ$ как симплициальный комплекс, и что-то в нём происходит: там тетраэдр возник, там ещё что-то. Там, где у объединения шаров была окружность, точки соединятся в окружность, но добавятся всякие дурацкие симплексы больших размерностей; получится образование, которое даже не плоское, в нём есть тетраэдры; это абстрактный симплициальный комплекс, но видно, по крайней мере интуитивно, что он гомотопически эквивалентен окружности. Спустя какое-то время он опять превратится в стягиваемый полиэдр, а при совсем большом $ε$ комплекс Виеториса–Рипса это весь симплекс $2^{V}$ . Из симплициальных гомологий этой цепочки получается персистентный модуль: отображения симплициальных комплексов тоже иногда приводят к отображениям симплициальных гомологий; этого мы ещё не обсуждали.

Ясно, как это вычислять на компьютере. Меряем попарные расстояния между точками; комплекс меняется только в те моменты, когда $ε$ равен одному из этих расстояний. В каждый такой момент строим комплекс и считаем его гомологии: получается набор свободных абелевых групп или векторных пространств, приводим матрицы к правильной форме, считаем ядра и образы, факторизуем. Гомологии вычисляются – вычисляется и баркод. Есть программа Ripser (на Python), которая по попарным расстояниям или координатам точек это делает; она легко вычисляет $H_{0}$ и $H_{1}$ , а дальше начинает мучиться: с ростом $n$ симплексов становится много, их все надо найти. Для нулевых и первых гомологий достаточно знать, какие в комплексе точки, отрезки и треугольники; это проще запомнить. На практике люди работают с $H_{0}$ , $H_{1}$ , $H_{2}$ , и им этого достаточно. Кольцо коэффициентов берут полем из двух элементов или из трёх: так находится всё, что связано с $2$ -кручением, а $3$ -кручения обычно нет, топология не настолько изощрённая.

Замечание (имена). Виеторис тот самый, что в теореме Майера–Виеториса. Илья Рипс тот самый, что занимался геометрической теорией групп; о нём можно услышать в курсе геометрической теории групп.

Это первая комбинаторная аппроксимация к тому, что происходит с шарами. Это уже не оно (гомологии комплекса Виеториса–Рипса с гомологиями $B_{ε} (V)$ напрямую не связаны), но тоже персистентный модуль, и тоже можно строить баркод. Второй пример, более затратный алгоритмически: комплекс Чеха.

Определение (Комплекс Чеха). Пусть $V$ – конечное подмножество метрического пространства и $ε > 0$ . Комплекс Чеха $\overset{ˇ}{C}_{ε} (V)$ – симплициальный комплекс на $V$ , в который входят те наборы вершин $I \subset V$ , для которых шары радиуса $ε$ с центрами в точках $I$ имеют общую точку:

v \in I ⋂ B_{ε} (v) \neq = \emptyset .

Чтобы понять, добавляем ли треугольник, нужно нарисовать шары и понять, пересеклись ли они в совокупности. Три шара могут пересекаться попарно, но не иметь общей точки; тогда в комплексе Чеха три ребра без треугольника. Аналогично возникает персистентный модуль симплициальных гомологий комплексов Чеха и соответствующий баркод.

Две конструкции, обе суть комбинаторные аппроксимации к объединению шаров, обе дают симплициальные комплексы, и у каждой свои достоинства и недостатки.

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

Комплекс Чеха. Сложнее посчитать: нужно объемлющее пространство и надо проверять, имеет ли данный набор шаров общую точку, а это комбинаторно более сложная задача; кажется, там нужно сначала посчитать разбиение Вороного и потом смотреть на расстояния в его вершинах, а для Виеториса–Рипса ничего такого делать не надо. Зато есть замечательный плюс.

Теорема (комплекс Чеха вычисляет гомологии объединения шаров). Геометрическая реализация комплекса Чеха гомотопически эквивалентна объединению шаров:

∣ \overset{ˇ}{C}_{ε} (V) ∣ ≃ B_{ε} (V) .

Это следствие общей теоремы, теоремы о нерве; о ней ниже. То есть комплекс Чеха вычисляет тот самый баркод, который мы хотели.

Комплексы связаны между собой: если попарные расстояния между точками не больше $ε$ , то любая из точек лежит во всех замкнутых шарах радиуса $ε$ с центрами в них, а если шары радиуса $ε$ имеют общую точку, попарные расстояния не больше $2 ε$ ; итого

VR_{ε} (V) \subset \overset{ˇ}{C}_{ε} (V) \subset VR_{2 ε} (V) .

Комплексы близки друг к другу в некотором смысле, поэтому можно ожидать, что близки и гомологии, а значит, в некотором смысле близки и баркоды. Отмечу, что всё зависит от метрики: я рисую евклидовы шары, а можно брать норму $L^{1}$ , $L^{\infty}$ , $L^{p}$ , и тогда у этих комплексов возникают специфические свойства.

Устойчивость баркода

Ещё один сюжет из анализа данных. Мы построили некоторый инвариант датасета; вопрос в том, насколько он чувствителен к изменению начальных условий. Это вопрос об устойчивости, а с математической точки зрения о непрерывности некоторого отображения. Пайплайн можно пройти через объединение шаров, через комплекс Чеха или через комплекс Виеториса–Рипса; на самом деле практики, конечно, считают Виеториса–Рипса. Значит, есть отображение

V ⟼ B (V), {конечные метрические пространства} ⟶ {конечные наборы интервалов},

сопоставляющее набору точек его баркод (по Виеторису–Рипсу). Это просто отображение множеств. Непрерывно ли оно? Правда ли, что если чуть пошевелить точки или добавить новую точку близко к одной из старых, баркод изменится мало? Может ли быть так, что я точку чуть-чуть подвинул, а гомологии сразу взорвались?

Ответ: нет, отображение непрерывно. Это теорема об устойчивости, stability theorem; давайте по-русски: об устойчивости. На самом деле это теорема о липшицевости: если правильно ввести метрики, отображение липшицево. Уточнение из зала: это не совсем про то, что мало меняются гомологии; это про то, что мало меняются интервалы, на которых они живут. Сами гомологии могут сильно поменяться, но на незначительное время, так что мы не успеем заметить: могло добавиться много очень коротеньких отрезочков. Страшен один длинный отрезок: про него мы скажем «ага, есть что-то», а про короткие «ошибки».

Теорема (об устойчивости). Для конечных метрических пространств $V$ , $W$

d_{B} (B (V), B (W)) \leq C \cdot d_{G H} (V, W),

где слева стоит расстояние между баркодами ( $\infty$ -метрика Васерштейна, она же bottleneck distance), справа расстояние Громова–Хаусдорфа между конечными наборами, с которых мы стартовали.

Определения этих метрик даются по голосованию: никто не признался, что он чистый математик, который не хочет пачкаться в грязи и знать определения каких-то вещей.

Расстояния Хаусдорфа и Громова–Хаусдорфа

Определение (Расстояние Хаусдорфа). Пусть $K$ и $L$ – компакты в метрическом пространстве $X$ . Расстояние Хаусдорфа между ними –

d_{H} (K, L) = x \in K max d (x, L) + y \in L max d (y, K) .

Чтобы запомнить формулу, картинка: беру точку в $K$ , самую далёкую от $L$ , и точку в $L$ , самую далёкую от $K$ , и складываю эти два расстояния. Приятная задача: проверить, что это метрика на множестве всех компактов в $X$ .

Если же $K$ и $L$ абстрактные компактные метрические пространства, никуда не вложенные, можно рассмотреть все возможные способы вложить их в какое-нибудь метрическое пространство и там посчитать расстояние между ними. Скажем, единичный диск и единичный квадрат: насколько близко я могу изометрично положить диск к квадрату в каком-либо метрическом пространстве? Скорее всего, ближе всего получится, если положить их концентрически. Это идея наилучшего наложения одного на другое в объемлющем пространстве, так, чтобы оба отображались туда изометрически.

Определение (Расстояние Громова–Хаусдорфа). Для компактных метрических пространств $K$ , $L$

d_{G H} (K, L) = X, f, g in f d_{H} (f (K), g (L)),

где инфимум берётся по всем метрическим пространствам $X$ и всем изометрическим вложениям $f : K \to X$ , $g : L \to X$ .

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

С этим определением невозможно работать на практике, но, к счастью, для конечных множеств есть явная формула.

Теорема (явная формула для конечных пространств). Пусть $K$ и $L$ – конечные метрические пространства. Тогда

d_{G H} (K, L) = \frac{1}{2} C min (x_{1}, y_{1}), (x_{2}, y_{2}) \in C max d (x_{1}, x_{2}) - d (y_{1}, y_{2}),

где минимум берётся по всем соответствиям $C$ между $K$ и $L$ , то есть подмножествам $C \subset K \times L$ , проекции которых на $K$ и на $L$ сюръективны.

Соответствие есть обобщение функции: многозначная функция из $K$ в $L$ , сколь угодно многозначная, но всюду определённая и принимающая все значения. Расстояние Громова–Хаусдорфа вычисляется перебором всех соответствий. Выражение под минимумом называется искажением соответствия $C$ : пара точек $x_{1}, x_{2}$ как будто перешла в пару $y_{1}, y_{2}$ , и я смотрю, насколько при этом изменилось расстояние; в идеале хочу равенства. Искажение измеряет, насколько $C$ далеко от того, чтобы быть изометрическим: если $C$ – изометрическое соответствие, искажение равно нулю, и расстояние Громова–Хаусдорфа тоже. Мы перебираем все соответствия и ищем самое близкое к изометрии. Это и есть то, насколько разные метрики на моих конечных наборах точек.

Расстояние Васерштейна между баркодами

Теперь метрика на баркодах. Мне нравится думать о ней в терминах экономики; пришла она из оптимального транспорта. Решается такая задача: дан баркод номер один, из него хочу сделать баркод номер два, потратив как можно меньше долларов. Разрешено:

сдвинуть конец интервала на $δ$ , потратив $δ$ долларов: интервал $[s, t)$ заменить на $[s, t + δ)$ или $[s + δ, t)$ ;
добавлять и убирать точки (интервалы нулевой длины) бесплатно.

Если нужно один баркод превратить в другой, я трачу сколько-то долларов, чтобы лишний отрезок сжать в точку, и сколько-то, чтобы сдвинуть концы остальных. Два отрезка, $[s, t)$ и $[s^{'}, t^{'})$ , недалеко друг от друга: выгоднее всего сдвинуть конец в конец, расстояние $∣ s - s^{'} ∣ + ∣ t - t^{'} ∣$ . Два отрезка далеко друг от друга: можно сдвинуть один в другой, но невыгодно; дешевле оба сжать в точки, и расстояние равно сумме их длин. С константами я мог немного провраться (где-то тариф, может быть, в два раза больше), но математически это мелочь: такая метрика естественна на множестве наборов отрезков. Если стоимости перемещений складывать, получится $1$ -метрика Васерштейна; если брать максимальную из них, то $\infty$ -метрика, bottleneck distance, которая и стоит в теореме об устойчивости.

Ещё один способ про это думать. Рассмотрим на плоскости с координатами $(s, t)$ диаграмму: каждый отрезочек $[s, t)$ баркода даёт точку $(s, t)$ выше диагонали. Чем точка ближе к диагонали, тем больше она похожа на мусор. Баркоду сопоставим объединение множества этих точек с диагональю, подмножество не плоскости даже, а расширенной плоскости $[0, + \infty]^{2}$ : интервал, который родился и никогда не умрёт, даёт точку на бесконечности. Это метрическое пространство в обобщённом смысле, с бесконечными расстояниями. Тогда расстояние между баркодами более-менее то же самое, что расстояние Хаусдорфа между этими множествами: точки на диагонали разрешено добавлять бесплатно, сжимание отрезка в точку есть приближение точки к диагонали, а сдвиг концов есть сдвиг точки по вертикали или горизонтали. Здесь именно расстояние Хаусдорфа, а не Громова–Хаусдорфа: диагональ зафиксирована на плоскости, перемещать её запрещено. Мелочи насчёт кратностей (могут ли точки совпадать, метрика это или псевдометрика) я игнорирую, и точную формулировку, можно ли так выразить расстояние Васерштейна между баркодами, не помню.

Это одна из немногих собственно теорем в этой науке: баркод есть липшицев инвариант конечного метрического пространства, при маленьких изменениях он мало меняется.

Теорема о нерве

Дальше занимаемся математикой. У нас осталась одна теорема без доказательства: что комплекс Чеха гомотопически эквивалентен объединению шаров. Доказывать я её всё равно не буду, но объясню, откуда она берётся: из теоремы о нерве покрытия. Идея в том, что шары выпуклые и пересечения шаров тоже выпуклые; именно это позволяет заменить объединение шаров на симплициальный комплекс. Это общетопологическое понятие, покрытия.

Теорему называют теоремой Александрова о нерве, хотя в нынешней формулировке её, кажется, доказал Борсук; обычно её формулируют для паракомпактов, а паракомпакты придумал Дьёдонне.

Покрытия и нерв

Покрытия у нас будут открытые: открытое покрытие пространства $X$ – набор открытых множеств $U = {U_{v}}_{v \in V}$ , индексированный множеством $V$ (оно может быть бесконечным), объединение которых – всё $X$ . В терминах покрытий определяется, например, компактность: из любого открытого покрытия можно выбрать конечное подпокрытие; есть счётная компактность и другие ослабления. Я же хочу связать с покрытием комбинаторную структуру, симплициальный комплекс. Это идея Александрова.

Для конечного $I \subset V$ обозначим

U_{I} = v \in I ⋂ U_{v}

пересечение соответствующих элементов покрытия. Некоторые пересечения пустые, некоторые нет.

Определение (Нерв покрытия). Нерв открытого покрытия $U = {U_{v}}_{v \in V}$ – симплициальный комплекс на множестве вершин $V$

N (U) = {I \subset V конечное ∣ U_{I} \neq = \emptyset} .

Это симплициальный комплекс: если $U_{I} \neq = \emptyset$ и $J \subset I$ , то $U_{J} \supset U_{I}$ тоже непусто. Конечность $I$ требуется потому, что симплициальный комплекс мы определяли как набор конечных множеств.

В этом примере видно, что нерв гомотопически эквивалентен объединению дисков, если это были диски, конечно. Это и есть содержание теоремы о нерве, но нужно условие.

Определение (Покрытие Лере). Открытое покрытие $U$ называется покрытием Лере (Leray, по-французски), если все пересечения $U_{I}$ пусты или стягиваемы.

Теорема (о нерве). Пусть $X$ – хаусдорфов паракомпакт, $U$ – его открытое покрытие Лере. Тогда

X ≃ ∣ N (U) ∣.

То есть если пересечения достаточно хорошие, покрытие можно моделировать нервом.

Пример (покрытие, не являющееся покрытием Лере). Возьмём кольцо и покроем его двумя множествами $U_{1}$ , $U_{2}$ , верхней и нижней половинами с перекрытием. Пересечение $U_{12}$ состоит из двух кусков, оно не стягиваемо. Нерв есть отрезок: $U_{1}$ и $U_{2}$ непусты, их пересечение непусто. Отрезок стягиваем, а кольцо нет: нерв не гомотопически эквивалентен пространству. Стягиваемость принципиальна.

К нашему сценарию анализа данных теорема применима: возьмём $X = B_{ε} (V)$ и покроем его самими шарами. Все конечные пересечения суть пересечения выпуклых множеств, а пересечение выпуклых множеств выпукло, значит, пусто либо стягиваемо: из выпуклости получается покрытие Лере. Нерв этого покрытия есть в точности комплекс Чеха $\overset{ˇ}{C}_{ε} (V)$ , и теорема о нерве даёт $B_{ε} (V) ≃ ∣ \overset{ˇ}{C}_{ε} (V) ∣$ .

Категория покрытий и паракомпактность

В теореме есть слово, которое должно было вас испугать; я его объясню. Кто знает, что такое паракомпакт? Существование разбиения единицы это теорема; определение паракомпакта немножко другое и даётся в терминах покрытий. Для этого нужны структуры на покрытиях: покрытия данного пространства образуют категорию, а не просто частичный порядок.

Определение (Измельчение). Пусть $U = {U_{α}}_{α \in I}$ и $W = {W_{β}}_{β \in J}$ – два открытых покрытия $X$ . $W$ называется измельчением $U$ , если для любого $β \in J$ найдётся $α \in I$ такое, что $W_{β} \subset U_{α}$ .

Какой элемент второго покрытия ни возьми, он содержится в каком-то элементе первого. Хочется ввести на множестве всех покрытий предпорядок, используя понятие измельчения, но $α$ по $β$ определяется не единственным образом, и правильнее рассмотреть все возможные выборы того, куда именно засунуть $W_{β}$ , в $U_{α}$ или в $U_{α^{'}}$ .

Определение (Категория покрытий). Категория покрытий $Cov (X)$ : объекты суть открытые покрытия $X$ ; морфизмы из $W$ в $U$ суть все способы вложить $W$ в $U$ , то есть отображения индексирующих множеств $φ : J \to I$ такие, что $W_{β} \subset U_{φ (β)}$ для любого $β \in J$ .

Понятие паракомпактности определяется в этих терминах.

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

Факты. Клеточные комплексы паракомпактны; метрические пространства паракомпактны; это сложные общетопологические теоремы. Если пространство паракомпактно, то у любого его открытого покрытия есть подчинённое разбиение единицы; это несложная теорема, в курсе общей топологии она обычно есть. Именно разбиение единицы нужно, чтобы доказать теорему о нерве.

Как она доказывается. Между $X$ и нервом строится вспомогательное пространство: каждое $U_{v}$ умножаем на соответствующую вершину нерва, а каждое пересечение $U_{I}$ на соответствующий симплекс $Δ_{I}$ :

I \in N (U) ⋃ U_{I} \times Δ_{I} \subset X \times ∣ N (U) ∣.

Если $X$ покрыто двумя множествами, это $U_{1} \times {1}$ и $U_{2} \times {2}$ , к которым приклеен цилиндр $U_{12} \times [1, 2]$ . У этого пространства есть проекция на $X$ и проекция на нерв, и доказывается, что обе они гомотопические эквивалентности: сечение первой строится с помощью разбиения единицы, сечение второй тоже, некоторым образом. Об этом можно прочитать у Хатчера, раздел 4.G; в принципе, вам это должно быть доступно.

Ещё два понятия в терминах покрытий

Размерность по Лебегу. Говорят, что топологическая размерность пространства $X$ не превосходит $n$ , $dim X \leq n$ , если в любое его открытое покрытие можно вписать измельчение, нерв которого имеет размерность не больше $n$ , то есть в котором никакие $n + 2$ элемента не имеют непустого общего пересечения.

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

Гомологии и когомологии Чеха. Эдуард Чех был известный чешский тополог; галочка сверху означает «Чех». Для каждого открытого покрытия $U$ можно посчитать симплициальные гомологии его нерва $H_{n}^{Δ} (N (U))$ . Когда одно покрытие вкладывается в другое (есть морфизм $W \to U$ ), на уровне нервов возникает симплициальное отображение $N (W) \to N (U)$ : отображение на вершинах, $β \mapsto φ (β)$ , которое продолжается на симплексы линейно (мы их ещё не определяли), а оно даёт отображение гомологий. Гомологии Чеха определяются как обратный предел по категории покрытий:

\overset{ˇ}{H}_{n} (X) = U \in Cov (X) lim H_{n}^{Δ} (N (U)),

а когомологии Чеха $\overset{ˇ}{H}^{n} (X)$ как прямой предел соответствующих групп когомологий нервов. Категория покрытий фильтрованная в классическом смысле: у любых двух покрытий есть общее измельчение.

Пример: покрытие тремя множествами с нервом-треугольником; в него вписывается более мелкое покрытие, нерв которого какая-то более странная штука. Две его вершины отображаются в одну вершину треугольника, ещё две – в другую, одна – в третью, а на остальных симплексах отображение продолжается линейно: нерв $W$ отображается в нерв $U$ .

Если $X$ хорошее пространство, гомологии Чеха изоморфны сингулярным, о которых будет наш курс. Если $X$ не очень хорошее, они ведут себя лучше сингулярных, и для некоторых вопросов подходят больше, но чтобы с ними работать, нужна техника прямых и обратных пределов. Идея такая: покрытий очень много и они страшные, но в хорошем пространстве, локально стягиваемом, покрытия Лере образуют финальную подсистему, и считать можно по ним; для когомологий Чеха покрытие Лере тогда даёт ответ сразу, а с гомологиями есть мучение с $lim^{1}$ , производным функтором обратного предела. Так доказывается, что у локально стягиваемого хаусдорфова паракомпакта когомологии Чеха изоморфны сингулярным.

Если всё это для вас страшно, то в нашем курсе эти понятия вряд ли ещё возникнут; разве что про паракомпактность я когда-нибудь что-нибудь скажу, но вряд ли.

Related works