Топология
Bottleneck и Wasserstein distances на persistence diagrams
Цели урока
- Понимать структуру persistence diagrams как метрического пространства
- Вычислять bottleneck distance через bipartite matching
- Различать Wasserstein и его sliced-аппроксимацию
- Векторизовать диаграммы для использования в ML pipeline
Предварительные знания
- Stability theorem (top-32)
- Persistent homology и баркоды
- L_p нормы и метрические пространства
- Основы оптимального транспорта
Без метрик на диаграммах TDA не интегрируется в ML pipelines.
- **Сравнение белковых структур**: Wasserstein на persistence diagrams классифицирует структурные классы
- **Anomaly detection**: bottleneck distance выявляет outliers в production мониторинге
- **Нейросетевые слои**: PersLay и TopNet используют sliced Wasserstein как дифференцируемый loss
- **Медицинская визуализация**: persistence images подаются в CNN наряду с raw сканами
Метрики на диаграммах
В 2009 году в книге Computational Topology Эдельсбруннер и Харер формализовали persistence diagrams как метрические пространства, сделав ключевой шаг от чисто комбинаторного объекта к статистическому. В 2011 году Mileyko, Mukherjee, Harer ввели Wasserstein-метрики и доказали их математические свойства - полноту, сепарабельность, существование барицентра Frechet. В 2017 году Hofer и соавторы продемонстрировали первое дифференцируемое обучение нейросетей с Wasserstein на persistence diagrams. В том же году Carriere с коллегами ввели sliced Wasserstein - быстрое приближение, открывшее путь к интеграции TDA в крупномасштабные ML-системы.
Persistence diagrams как метрическое пространство
Два препарата для химиотерапии испытываются на культуре опухолевых клеток. Оба дают persistence diagrams с одинаковым количеством длинных особенностей в H_0 (компоненты колоний) и H_1 (циклы клеточных коммуникаций). Но врачу нужно знать: эффекты этих препаратов действительно похожи, или один из них работает принципиально иначе? Ответ требует количественной метрики на пространстве диаграмм - не визуального впечатления, а числа со свойствами расстояния.
Persistence diagram D - это мультимножество точек (b_i, d_i) в R^2 с b_i меньше d_i. Каждая точка - особенность с рождением b и смертью d. Чтобы превратить пространство всех таких диаграмм в метрическое пространство, нужно дополнить каждую D всей диагональю Delta = (x,x) с бесконечной кратностью. Это даёт пространство biections между расширенными диаграммами и формальный аппарат для определения расстояний.
Аксиомы метрики выполняются для bottleneck и Wasserstein: неотрицательность очевидна по определению inf, симметрия следует из обратимости биекций, неравенство треугольника доказывается композицией оптимальных матчингов.
Визуальная интуиция
Две диаграммы на одной картинке
На плоскости birth-death рисуются точки двух диаграмм разными цветами. Оптимальный матчинг изображается отрезками между сматченными точками. Точки, оставшиеся без пары, соединяются с их проекциями на диагональ короткими вертикальными отрезками. Самый длинный отрезок на картинке - это и есть bottleneck distance.
Каждый класс в датасете имеет среднюю persistence diagram (барицентр по Frechet или Karcher). Расстояние между классовыми барицентрами - топологическая мера отделимости. Если bottleneck distance между барицентрами меньше внутриклассового разброса - топология не даёт сигнала для классификации.
Пространство диаграмм с bottleneck distance не является евклидовым: барицентр не единственный, среднее может не существовать. Это создаёт сложности для статистических методов и требует специальных алгоритмов (например, Frechet mean через градиентный спуск).
Почему цена матчинга off-diagonal точки (b,d) с диагональю в L_infinity равна (d-b)/2?
L_infinity-расстояние от (b,d) до точки (m,m) равно max(|b-m|, |d-m|). Минимум по m даёт m = (b+d)/2 и значение (d-b)/2. Геометрически проекция в L_infinity отличается от евклидовой, но даёт ту же формулу для перпендикуляра к диагонали.
Bottleneck distance: формальное определение и алгоритм
Bottleneck distance - это инфимум по биекциям между расширенными диаграммами от супремума пар расстояний. Хитрая комбинация inf-sup делает её устойчивой к выбросам в выборе биекции, но крайне чувствительной к одному плохому матчу: одна пара с большим расстоянием поднимает всю метрику.
Алгоритм Hopcroft-Karp на двудольном графе с n вершинами и m рёбрами работает за O(m * sqrt(n)). Бинарный поиск по epsilon требует log(N) итераций, где N - количество различных расстояний. Итоговая сложность для n точек - O(n^{2.5} log n) в худшем случае, в среднем быстрее за счёт пространственных структур.
Anomaly detection в промышленности
Контроль качества литья
На производственной линии алюминиевого литья делается компьютерная томография каждой 100-й детали. Из 3D-объёма извлекается persistence diagram H_1 (полости в металле). Эталонная диаграмма деталей без дефектов хранится в системе контроля. Bottleneck distance новой детали до эталона выше порога 0.5 мм сигнализирует о крупной полости и автоматически отправляет деталь в брак. Метрика реагирует только на самый крупный дефект - это её сила в anomaly detection.
k-Nearest Neighbors на persistence diagrams с bottleneck distance даёт устойчивый baseline-классификатор. Не требует векторизации, обходится без дифференцируемости. Используется как сравнительный референс для более сложных TDA-моделей.
Когда персистентность близка к нулю, bottleneck distance чувствительна к шуму вычисления: тривиальные точки могут случайно повышать расстояние. Практическое решение - предфильтрация по минимальной persistence (например, отбросить особенности с persistence меньше 0.01).
В библиотеке Gudhi bottleneck реализован через линейный алгоритм Kerber et al. (2017) с асимптотикой O(n * log^2 n) для типичных входов. Это делает bottleneck distance практичной даже для диаграмм с десятками тысяч точек, что критично для крупномасштабных биоинформатических задач.
Какова вычислительная сложность точного bottleneck distance для двух диаграмм по n точек?
Bottleneck distance сводится к bottleneck matching: бинарный поиск по порогу плюс проверка существования полного паросочетания за O(m * sqrt(n)). При плотном графе с n^2 рёбрами и log(n) итерациями получаем O(n^{2.5} log n). Современные алгоритмы (Kerber) дают почти линейное время на практике.
p-Wasserstein distance и sliced варианты
Bottleneck distance отвечает на вопрос насколько плох худший матч. Wasserstein-метрики отвечают на более сложный вопрос: насколько в целом отличаются две диаграммы. Wasserstein-расстояние - это минимальная стоимость перевести массу одной диаграммы в массу другой, где стоимость - сумма (или Lp-сумма) индивидуальных перемещений.
Mileyko, Mukherjee, Harer (2011) ввели Wasserstein-метрики на persistence diagrams формально и доказали их свойства. Carriere et al. (2017) ввели sliced Wasserstein - быстрое и дифференцируемое приближение.
PersLay в нейросетях
Топологический слой
Архитектура PersLay принимает persistence diagram как вход слоя нейросети. Каждая точка диаграммы пропускается через обучаемое embedding-преобразование. Sliced Wasserstein-loss между батчем диаграмм и обучаемым эталоном даёт градиенты на параметры embedding. Так нейросеть учится представлять топологические признаки в формате, оптимальном для следующих fully-connected слоёв.
Эмпирические наблюдения: p=1 (EMD) лучше всего работает на текстурных задачах, p=2 - на формах и медицинских изображениях, p=infinity (bottleneck) - на anomaly detection. p=2 наиболее популярен в современных архитектурах из-за хорошего градиентного поведения.
Sliced Wasserstein - это аппроксимация, не полный W_p. На простых распределениях ошибка мала, на сложных может быть существенной. В критичных задачах (медицинская диагностика) лучше использовать точный Wasserstein даже если он медленнее.
Это предельное соотношение объясняет, почему bottleneck distance можно рассматривать как W_infinity: при p стремящемся к бесконечности сумма p-х степеней доминируется максимальным слагаемым. На практике W_p при больших p (например, p=50) даёт результат близкий к bottleneck, но с лучшей градиентной стабильностью для оптимизации.
Почему sliced Wasserstein используется в нейросетях вместо полного Wasserstein?
Для обучения нейросетей нужны быстрые градиенты. Sliced Wasserstein реализуется проекциями плюс 1D сортировками, всё дифференцируемо и параллелизуемо на GPU. Полный Wasserstein требует решения задачи оптимального транспорта на каждом forward pass.
Векторизация диаграмм и вычислительные аспекты
Прямое вычисление bottleneck или Wasserstein между большими диаграммами дорого. В production-системах TDA редко работают с парными расстояниями напрямую. Вместо этого диаграммы векторизуются - превращаются в фиксированноразмерные представления, совместимые с любой ML-библиотекой. Это даёт огромный прирост скорости и совместимость с GPU.
Три популярные техники векторизации: (1) persistence image - сетка над birth-death плоскостью, веса по persistence, сглаживание гауссианом, (2) Betti curve - функция beta_k(epsilon) от уровня фильтрации, (3) persistence entropy - один скалярный признак типа дисперсии распределения времени жизни.
Pipeline для 10000 белков
Топологическая классификация структур
10000 PDB-структур белков, каждая преобразуется в облако из 1000-5000 атомов. Vietoris-Rips persistence считается для каждой структуры с GPU-ускоренной библиотекой Ripser++. Каждая диаграмма векторизуется в persistence image 50x50 = 2500 фичей. XGBoost обучается классифицировать структурные классы (alpha-helix, beta-sheet, mixed). Accuracy около 92 процентов на тестовой выборке. Без векторизации pairwise Wasserstein был бы 10000^2 / 2 = 50 миллионов вычислений.
Persistence image - это серая картинка фиксированного размера. Convolutional Neural Network легко принимает её на вход. Архитектуры типа ResNet18 на persistence images дают конкурентные результаты на классификации медицинских изображений с минимумом инженерной работы.
Любая векторизация теряет часть структуры. Persistence image размывает близкие точки - тонкие особенности могут слиться. Betti curve игнорирует совместную информацию точек. Persistence entropy сводит всё к одному числу. Выбор векторизации - инженерное решение, зависящее от задачи.
Для разреженных диаграмм (несколько десятков точек) практичнее использовать прямые метрики: bottleneck или Wasserstein. Для плотных диаграмм (тысячи точек) - векторизация плюс классические ML-алгоритмы. Для дифференцируемых пайплайнов - sliced Wasserstein. Выбор делается на основе размера, требования к скорости и доступности GPU.
Почему persistence images удобнее прямых метрик для классификации на 10000+ образцов?
Pairwise bottleneck на N образцах - это N^2 / 2 вычислений, каждое O(n^{2.5}). Это неподъёмно при N выше пары тысяч. Векторизация делает фичи независимыми по образцу: считается N штук векторов, дальше любая sklearn/pytorch модель.
Куда идёт линия метрик
Метрики на диаграммах открывают доступ к TDA из любого ML pipeline.
- Mapper advanced — Связанная тема
- TDA для временных рядов — Связанная тема
- TDA в нейросетях — Связанная тема
- Witness complexes — Связанная тема
Ключевые идеи
- Persistence diagrams формируют метрическое пространство с дополнением до диагонали
- Bottleneck distance смотрит на худший матч, Wasserstein - на сумму всех
- Sliced Wasserstein дифференцируем и встраиваем в нейросети
- Векторизация (persistence image, Betti curve) делает диаграммы совместимыми с ML
- Выбор метрики и представления зависит от размера данных и задачи
Вопросы для размышления
- В каких случаях лучше использовать прямые метрики, а в каких - векторизацию?
- Почему дифференцируемость sliced Wasserstein важна для современных архитектур?
- Как изменился бы статус TDA, если бы Wasserstein-метрики не существовали?