Топология
Witness complexes и multi-parameter persistence
Цели урока
- Понять конструкцию witness complex и роль landmarks/witnesses
- Освоить maxmin селекцию для качественного покрытия данных
- Разобраться, что такое 2-параметрический персистентный модуль
- Узнать про теорему Карлсона-Зомородяна об отсутствии полного инварианта
- Изучить RIVET и применения multi-parameter persistence
Предварительные знания
- Vietoris-Rips комплекс и его комбинаторная сложность
- Persistent homology и barcodes
- Основы линейной алгебры над полем
- Понятие фильтрации топологического пространства
Vietoris-Rips на 10000 точках - 166 миллиардов треугольников. Witness complex - 100000. Сжатие в миллион раз без потери топологии.
- **Astronomy**: TDA на каталогах Sloan Digital Sky Survey с миллионами галактик через witness complexes
- **Single-cell genomics**: топологический анализ scRNA-seq данных с миллионами клеток - landmarks как репрезентативные клетки
- **Medical imaging**: сегментация органов через witness TDA на воксельных облаках
- **Social networks**: bifiltration по частоте и недавности для динамических графов
Витнес комплексы и multi-parameter
Витнес комплексы введены де Сильвой и Карлсоном в 2004 году специально для TDA на больших облаках точек. Multi-parameter persistence формализована Карлсоном и Зомородяном в 2009 - в той же статье они доказали отсутствие полного дискретного инварианта (в отличие от 1D barcode). Программа RIVET для визуализации 2-параметрической persistence выпущена Lesnick и Wright в 2015. Область multi-parameter TDA остаётся одним из самых активных фронтов исследований - дедлайны NeurIPS workshop по TDA каждый год.
Определение witness complex
Облако из 10000 точек теоретически порождает C(10000, 3) = 166 миллиардов треугольников в Vietoris-Rips комплексе. Ни один компьютер на планете не способен такое хранить целиком. Witness complexes решают эту проблему радикальным упрощением: выбираем 100 опорных точек (landmarks), а остальные 9900 точек служат свидетелями (witnesses), которые подтверждают существование симплексов между landmarks. Топология восстанавливается из крошечного подмножества.
Идея де Сильвы и Карлсона (2004): landmarks - это вершины комплекса, а witnesses - близкие к ним точки данных, которые поддерживают существование симплекса. Результирующий комплекс на порядки меньше Rips, но захватывает ту же топологию.
Сравнение размеров
Сколько симплексов остаётся после witness конструкции
Облако X из 10000 точек, выбрано L = 100 landmarks. Vietoris-Rips: до 166 миллиардов 2-симплексов. Witness complex: максимум C(100, 3) = 161700 симплексов. Сжатие в миллион раз. При этом первые несколько Betti чисел и большие persistent features сохраняются с ограниченной погрешностью.
Strong witness complex требует, чтобы witness был строго ближе к sigma, чем к любому другому landmark - даёт меньший, но более точный комплекс. Weak версия с epsilon допуском устойчивее к шуму.
Зачем нужен witness complex?
Witness complex радикально уменьшает количество симплексов, сохраняя топологические особенности через свидетельства от внешних точек.
Выбор landmarks и сложность
Качество witness complex напрямую зависит от того, как выбраны landmarks. Случайная выборка работает быстро, но даёт неравномерное покрытие. Maxmin селекция - стандарт индустрии: первый landmark выбирается случайно, далее на каждом шаге берётся точка, максимально удалённая от уже выбранных. Это жадная аппроксимация epsilon-net.
Maxmin даёт более равномерное покрытие, чем случайная выборка, и обеспечивает теоретические гарантии: для любой точки данных существует landmark на расстоянии не больше epsilon-net радиуса.
Алгоритм maxmin
Пошаговая селекция landmark множества
Дано облако X = 10000 точек, нужно выбрать |L| = 100. Шаг 1: случайный l_1. Шаг 2: для каждой точки x вычислить d(x, l_1), выбрать аргмакс - это l_2. Шаг k: для каждой точки x вычислить min расстояние до уже выбранных landmarks, выбрать точку с максимальным таким расстоянием. Сложность O(|L| * |X|) = O(100 * 10000) = миллион операций. Сравнить с Rips: 166 миллиардов.
Для хороших landmark множеств (maxmin или epsilon-net) persistence диаграммы witness complex аппроксимируют диаграммы полного Rips комплекса с ограниченной ошибкой по bottleneck метрике.
Случайная выборка может пропустить целые регионы данных. Если в облаке есть редкий, но топологически значимый кластер - случайные landmarks могут его не зацепить. Maxmin защищает от этого.
Применения в ML: scalable TDA на миллионных датасетах - астрономические каталоги Sloan Digital Sky Survey, single-cell genomics с миллионами клеток, медицинская сегментация изображений где каждый воксель - точка облака. Witness complexes делают TDA практически применимым там, где Rips невозможен.
В чём идея maxmin селекции landmarks?
Maxmin минимизирует максимальное расстояние до ближайшего landmark - это жадная аппроксимация epsilon-net.
Multi-parameter persistence
Один параметр фильтрации часто недостаточен для разделения сигнала и шума. Что если нужно одновременно учитывать расстояние И плотность? Точка может быть близко к другим, но в области низкой плотности - возможно, это шум. Или наоборот: далеко, но в плотном кластере - значимая структура. Multi-parameter persistence отвечает на этот вопрос.
Карлсон и Зомородян (2009) формализовали multi-parameter persistence: модуль персистентности над R^n вместо R^1. Для двух параметров получаем функтор из R^2 в Vect - 2D персистентный модуль.
Карлсон и Зомородян доказали: в отличие от 1D persistence (где barcode - полный инвариант), для multi-parameter persistence НЕ существует простого полного дискретного инварианта. Это фундаментальное препятствие, не недостаток алгоритмов.
Density-Rips bifiltration
Двухпараметрическая фильтрация по расстоянию и плотности
Параметр r - радиус Rips, параметр k - порог плотности (например, k-ближайший сосед). Симплекс sigma включается в комплекс на уровне (r, k), если все вершины sigma имеют плотность не меньше k И попарные расстояния не больше r. Получаем 2D решётку комплексов и 2D персистентный модуль.
Если данные содержат шум разной природы (например, выбросы И плотностной шум), один параметр не разделит сигнал. Multi-parameter позволяет фильтровать по обоим измерениям одновременно.
Почему multi-parameter persistence сложнее, чем 1D?
Карлсон и Зомородян доказали невозможность полного дискретного инварианта - это математическое препятствие, не вычислительная проблема.
Применения и состояние области
Multi-parameter persistence на практике - sublevel set bifiltrations для сигналов с переменным уровнем шума. Vineyard - отслеживание персистентных особенностей при изменении параметров во времени. Persistence vineyard визуализирует, как barcode эволюционирует вдоль кривой в пространстве параметров. Программа RIVET (Lesnick и Wright, 2015) - стандартный инструмент для визуализации 2-параметрической persistence.
RIVET вычисляет slice-and-project: фиксирует прямую в пространстве параметров и вычисляет 1D persistence вдоль неё. Интерактивная визуализация позволяет двигать прямую и видеть, как меняется barcode.
Социальная сеть с временем
Bifiltration по частоте и недавности взаимодействий
Граф социальной сети: вершины - пользователи, рёбра - взаимодействия. Параметр f - частота (число сообщений), параметр t - недавность (время с последнего сообщения). Получаем 2-параметрическую фильтрацию. Loops в H_1 соответствуют циклическим паттернам общения. Multi-parameter позволяет различать активные циклы (high f, low t) от затухающих (low f, high t).
Active research: вычислимые инварианты multi-parameter persistence (Hilbert function, signed barcodes, decomposition theorems для interval modules). Связь с representation theory колчанов. Это одна из самых активных областей TDA.
ML применения: обучение оптимальной пары параметров фильтрации из данных - вместо ручного выбора radius и density порогов градиентно оптимизируем по downstream loss; multi-parameter TDA для гетерогенных датасетов, где разные признаки имеют разные масштабы шума; топологические признаки для гетерогенных временных рядов с разной частотой обновления.
Multi-parameter persistence существенно дороже 1D - не только из-за отсутствия barcode-инварианта, но и из-за роста размера комплексной решётки. На практике используют 2-параметрические случаи; 3+ параметров - исследовательский фронтир.
Что делает RIVET с 2-параметрической persistence?
RIVET использует slice-and-project: интерактивно выбирается прямая, вдоль которой вычисляется обычная 1D persistence.
Куда это ведёт
Witness complexes делают TDA практическим инструментом для миллионных датасетов. Multi-parameter persistence открывает новое математическое измерение - топологическая теория представлений колчанов.
- Sliding window TDA — Связанная тема
- TDA в нейросетях — Связанная тема
- Persistent homology — Связанная тема
- Vietoris-Rips — Связанная тема
Ключевые идеи
- Witness complex заменяет Rips для больших |X|: landmarks как вершины, witnesses подтверждают симплексы
- Maxmin селекция даёт equispaced покрытие данных и теоретические гарантии
- Persistence witness аппроксимирует Rips persistence с ограниченной ошибкой
- Multi-parameter persistence - функтор R^n в Vect, нет полного дискретного инварианта (Карлсон-Зомородян)
- Rank invariant и Hilbert function - частичные инварианты для 2D модулей
- RIVET вычисляет 1D срезы 2-параметрического модуля интерактивно
- Density-Rips bifiltration разделяет шум плотности от шума расстояния
- Активный фронт research: signed barcodes, interval decomposition, learning filtrations
Вопросы для размышления
- Какие свойства данных делают maxmin селекцию предпочтительнее случайной выборки?
- Почему отсутствие полного инварианта для multi-parameter persistence - математическая проблема, а не вычислительная?
- Какие гарантии стабильности дают witness complexes по сравнению с полным Rips?
- В каких задачах ML 2-параметрическая фильтрация даст преимущество над 1D?
- Как можно использовать landmark selection как форму активного обучения?