Топология
Stability theorem: почему persistence устойчив к шуму
Цели урока
- Понимать определение bottleneck distance и роль диагонали
- Формулировать stability theorem и распознавать его условия
- Различать ситуации применения Wasserstein и bottleneck
- Применять стабильность для оценки воспроизводимости TDA-фичей
Предварительные знания
- Persistent homology и баркоды
- Vietoris-Rips и Cech фильтрации
- Понятие критической точки и tame function
- L_p нормы на функциональных пространствах
Без stability TDA был бы математической экзотикой без применений к зашумлённым данным.
- **Biomedical imaging**: повторные fMRI/CT/МРТ дают воспроизводимые баркоды одного и того же пациента
- **Drug screening**: молекулярные конформации классифицируются по топологическим инвариантам без чувствительности к thermal noise
- **Anomaly detection**: bottleneck distance используется как метрика контроля качества в производственной томографии
- **ML robustness**: persistence diagrams активаций сравниваются для clean vs adversarial inputs
Доказательство 2007 года
Статья Stability of Persistence Diagrams в Discrete & Computational Geometry стала точкой невозврата для TDA. До этой публикации persistence была изящной математикой с неясным практическим статусом: непонятно было, можно ли вообще применять к реальным данным. Авторы показали, что bottleneck distance между диаграммами ограничена L_infinity-нормой разности порождающих функций. Через несколько лет Эдельсбруннер и Карлссон расширили результат на Rips-фильтрации точечных облаков, и TDA окончательно стал применимой инженерной дисциплиной. В 2009 году Chazal с коллегами получили алгебраическую версию стабильности для произвольных persistence modules.
Bottleneck distance: метрика на диаграммах
Структура белка, измеренная двумя независимыми методами кристаллографии, отличается на наноментры. Облако из тысячи опухолевых клеток выглядит чуть иначе в каждой биопсии. Если persistent homology выдаёт баркод, а каждое новое измерение полностью сдвигает этот баркод - вся дисциплина TDA бесполезна для биологии. Перед TDA в середине 2000-х стоял именно такой экзистенциальный вопрос: устойчив ли инструмент к шуму вообще?
Чтобы ответить, нужно сначала научиться измерять расстояние между двумя persistence diagrams. Диаграмма - это мультимножество точек (b_i, d_i) над диагональю birth = death. Точки на диагонали - это тривиальные особенности, рождающиеся и умирающие одновременно. Любая разумная метрика обязана учитывать: точка одной диаграммы может быть сматчена с точкой другой, либо с её проекцией на диагональ - значит, особенность исчезает или появляется.
Имя bottleneck (узкое горлышко) подчёркивает суть: метрика - это max по парам, а не сумма. Одна плохо сматченная точка определяет всё расстояние, даже если остальные тысячи матчатся идеально.
Геометрическая интуиция
Две диаграммы H_1 для разных биопсий
Первая диаграмма: точки (0.1, 1.2), (0.3, 0.9), (0.2, 0.25). Вторая диаграмма: (0.12, 1.18), (0.31, 0.88), и точка (0.21, 0.23) близка к диагонали. Оптимальный матчинг: первые две пары - между собой, третья точка каждой диаграммы матчится с диагональю. Bottleneck distance определяется максимальным сдвигом среди этих матчей.
Bottleneck distance используется для сравнения топологических сигнатур разных нейросетевых архитектур: считается persistence diagram активаций слоя на тестовой выборке, разные сети сравниваются по d_B. Архитектуры с близкими bottleneck distance обучаются на похожих признаках.
Норма внутри bottleneck distance - это L_infinity на R^2, не евклидова. То есть расстояние между парой (b1, d1) и (b2, d2) - это max(|b1 - b2|, |d1 - d2|). Это связано с природой фильтрации: ошибка по уровням ε сдвигает и рождение, и смерть на ту же величину.
Почему в определении bottleneck distance к диаграммам добавляется вся диагональ?
Persistence diagrams могут содержать разное число off-diagonal точек. Без диагонали биекция между ними просто не существует. Добавление диагонали с бесконечной кратностью решает проблему: лишние особенности сопоставляются с тривиальными.
Stability theorem: формулировка и смысл
Декабрь 2005. Дэвид Коэн-Штайнер, Герберт Эдельсбруннер и Джон Харер заканчивают рукопись с формулировкой, которая до сих пор стоит в основании всего TDA. Идея проста до неприличия: если две скалярные функции f и g отличаются мало в L_infinity, то их persistence diagrams отличаются мало в bottleneck distance. Маленькое возмущение данных - маленькое возмущение топологического портрета.
Геометрическая переформулировка: если два облака точек ε-близки в Hausdorff distance, их Vietoris-Rips persistence diagrams ε-близки в bottleneck distance. Это позволяет применять теорему не только к функциям, но и к реальным датасетам.
Контрольный пример
Шум на сигнале
Пусть f(x) - функция плотности облака точек, g(x) = f(x) + ε * noise(x), где noise имеет амплитуду 0.05. Тогда L_infinity норма разности не более 0.05, и значит bottleneck distance между диаграммами тоже не более 0.05. Длинноживущие особенности с persistence больше 0.1 гарантированно сохранятся - ни одна не пропадёт, и новых не появится.
Для функций без условия tame (с бесконечно осциллирующими критическими точками типа sin(1/x) около нуля) теорема в исходном виде не работает. На практике это редкая ситуация, но при работе с теоретическими функциональными пространствами стоит проверять.
Stability обосновывает применение TDA к зашумлённым данным в production-системах: датчики IoT, биомедицинские измерения, фотографии с разных камер. Длинноживущие топологические особенности являются истинными свойствами объекта, а не артефактами одного конкретного измерения.
Доказательство опирается на простую идею: рассмотреть филтрацию по уровням f и параллельную филтрацию по уровням g, сдвинутым на ε = L_infinity-норму разности. Каждый класс гомологии, существующий в фильтрации f на интервале [b, d], существует в фильтрации g не позднее b - ε и не раньше d + ε. Это даёт оценку на сдвиг каждой точки диаграммы.
Что означает стабильность с практической точки зрения для биологических данных?
Stability ограничивает максимальный сдвиг точек диаграммы. Особенность с persistence p и сдвигом меньше p/2 не исчезнет: её точка не приблизится к диагонали. Это и есть устойчивость биологических топологических признаков к шуму измерений.
Wasserstein stability и липшицевы варианты
Bottleneck смотрит только на самый плохой матч. Но иногда хочется учесть всю диаграмму: если одна особенность сместилась сильно, а тысяча других - чуть-чуть, bottleneck distance не отличит этот случай от случая когда сместилась только одна. Wasserstein-метрики дают более чувствительную оценку, суммируя все индивидуальные сдвиги.
Алгебраическая стабильность (Chazal, de Silva, Glisse, Oudot, 2009): любая 1-липшицева оценка interleaving distance на persistence modules даёт оценку на bottleneck distance. Это обобщает классическую теорему 2007 года на абстрактные модули.
Выбор p
Когда какой метрикой пользоваться
Anomaly detection в производственной линии: одна сильно сдвинутая точка - сигнал брака, остальные мелкие сдвиги - норма. Bottleneck (W_infinity) идеален. Сравнение формы двух молекул: важна полная похожесть, не только worst case. W_2 даёт более информативное расстояние. Поиск дубликатов в датасете 3D-сканов: W_1 наиболее устойчив к ошибкам регистрации.
Вычислить W_p для двух диаграмм с n точками - это задача оптимального транспорта со сложностью O(n^3) венгерским алгоритмом, или O(n^{2.5}) с auction-методом. Для n больше нескольких тысяч нужны аппроксимации (sliced Wasserstein, entropic regularization).
Дифференцируемость sliced Wasserstein сделала возможным обучение нейросетей с топологическими лоссами. Архитектуры PersLay и TopNet встраивают persistence diagrams прямо в forward pass, минимизируя W-метрику между диаграммой батча и шаблоном.
Практически важно: при p=1 алгебраическая стабильность не выполняется в общем случае - нужно дополнительное условие на total persistence. При p=2 неравенство стабильности выполняется почти всегда, но с константой зависящей от диаметра носителя функции. При p=infinity - классическая теорема 2007 года без дополнительных условий.
Какая метрика лучше подходит для anomaly detection, где важна одна сильно отклоняющаяся особенность?
Anomaly detection требует обнаружения одного редкого отклоняющегося признака на фоне нормы. Bottleneck не размывает выброс остальными матчами и сразу выдаёт большое значение, если хоть одна особенность сдвинулась сильно. W_1 и W_2 усреднили бы выброс с тысячью нормальных матчей.
Применения: почему TDA можно доверять
Stability theorem - не абстрактный артефакт чистой математики. Это сертификат качества для всех последующих применений TDA. Без него persistence не отличается от рандомной фичи: красивая, но непредсказуемая. Со stability TDA становится инженерной дисциплиной с гарантиями устойчивости и оценками ошибок.
Три типа реальных применений, в которых stability критична: (1) шумные сенсорные данные где каждое измерение даёт чуть другую кривую, (2) биологические эксперименты с естественной вариабельностью образцов, (3) приближённые вычисления симплициальных комплексов когда полный Чех-комплекс невозможен.
fMRI: повторяемость измерений
Два скана одного мозга
Пациент проходит fMRI дважды с интервалом в час. Сырые временные ряды активности отличаются из-за теплового шума, движений головы, дрейфа сканера. Hausdorff distance между облаками точек активности около 0.03 единиц нормализованного сигнала. По stability theorem bottleneck distance между persistence diagrams тоже не более 0.03. Особенности с persistence больше 0.1 (соответствующие реальным функциональным сетям мозга) гарантированно воспроизведутся. Без stability нельзя было бы утверждать что найденная топология - свойство мозга, а не артефакт конкретного измерения.
Adversarial perturbations меняют активации нейросети по входу. Если topology of decision boundary до и после атаки имеет большую bottleneck distance - модель катастрофически чувствительна. Сравнение persistence diagrams чистых и зашумлённых классификаций даёт количественную оценку adversarial robustness.
Теорема даёт верхнюю оценку, но не гарантирует что особенность сохранит свою позицию. Если особенность близка к диагонали (короткая persistence) и шум того же порядка - она исчезнет полностью. Поэтому в production-системах обычно фильтруют по минимальному persistence.
Drug discovery
Сравнение молекулярных конформаций
Молекула в растворе постоянно меняет конформацию. Молекулярная динамика генерирует тысячи 3D-структур одного белка. Persistence diagrams каждой конформации немного отличаются. Stability theorem даёт оценку: bottleneck distance между диаграммами ограничена средним RMSD конформаций. Это позволяет кластеризовать конформации по топологическим классам и находить функционально различные состояния белка.
В production TDA stability обычно используется неявно: пользователи библиотек Gudhi, Ripser, Giotto-TDA даже не задумываются о теореме. Но именно она обосновывает что pipeline cloud → simplicial complex → persistence diagram → vectorization → ML model работает воспроизводимо.
Почему стабильность даёт TDA преимущество перед классическими дескрипторами формы для биомедицинских данных?
Главное практическое преимущество - количественная гарантия что одинаковые объекты дают одинаковые фичи, и разные объекты дают разные. Без stability эти гарантии пришлось бы проверять эмпирически на каждом датасете заново.
Где stability встречается дальше
Stability theorem - корень доверия ко всем последующим применениям TDA в ML и биологии.
- Bottleneck и Wasserstein детально — Связанная тема
- Mapper advanced — Связанная тема
- TDA в нейросетях — Связанная тема
- TDA для временных рядов — Связанная тема
Ключевые идеи
- Bottleneck distance - метрика на persistence diagrams через оптимальный matching с диагональю
- Stability theorem: d_B(Dgm(f), Dgm(g)) <= ||f - g||_infinity для tame функций
- Wasserstein-метрики дают спектр чувствительности от worst-case до total deviation
- Стабильность - сертификат применимости TDA к шумным реальным данным
- Алгебраическая стабильность распространяется на произвольные persistence modules
Вопросы для размышления
- Какая особенность нынешних production-систем TDA напрямую опирается на 2007 stability theorem?
- Почему bottleneck distance чувствительна к выбросам, а Wasserstein - нет?
- Как поменялся бы статус TDA если бы аналога stability не существовало?