Persistent Homology

Центральный метод TDA: вместо одного порога ε рассматривается вся фильтрация, и отслеживается, когда топологические особенности рождаются и умирают.

Ключевые тезисы

Долгоживущие особенности — сигнал, короткоживущие — обычно шум.
Результат не зависит от произвольного выбора одного порога.
Теорема устойчивости: малое возмущение данных даёт малое изменение диаграммы.

Подробный разбор

3 подтем — раскройте любую, чтобы увидеть объяснение, формулы, примеры и интерактивные графики.

Фильтрация вместо одного порога

Главная идея TDA: не выбирать ε, а рассмотреть все ε сразу.

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

VR_{ε_{1}} (X) \subseteq VR_{ε_{2}} (X) \subseteq \dots \subseteq VR_{ε_{m}} (X), ε_{1} < ε_{2} < \dots < ε_{m}

Особенность, живущая долго (большая разность «смерть − рождение»), устойчива к шуму и считается сигналом. Короткоживущие особенности — как правило, шум дискретизации.

ε0.12

β₀ (компоненты)1

β₁ (циклы)1

рёбер в комплексе22

Радиус фильтрации ε0.12

Ведите ε от 0 вверх: сначала β₀ падает с 22 до 1 (компоненты сливаются), затем существует цикл, потом дыра заклеивается

Теорема устойчивости

Почему на диаграммы можно опираться при шумных данных.

d_{B} (Dgm (X), Dgm (Y)) \leq d_{G H} (X, Y)

Расстояние между диаграммами не превосходит расстояния между самими данными

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

Как это считают на практике

Библиотеки, сложность и разумные ограничения.

from gtda.homology import VietorisRipsPersistence
from gtda.diagrams import PersistenceEntropy

vr = VietorisRipsPersistence(homology_dimensions=[0, 1, 2])
diagrams = vr.fit_transform(point_clouds)       # (n_samples, n_features, 3)
features = PersistenceEntropy().fit_transform(diagrams)
# features -> обычная матрица признаков для любой ML-модели

giotto-tda: от облаков точек до признаков в две строки

Сложность в худшем случае экспоненциальна по размерности, но Ripser и алгоритмы с редукцией матрицы делают $H_{0}$ и $H_{1}$ практичными на тысячах точек.
Обычно ограничиваются размерностями 0 и 1 — они дают почти весь полезный сигнал.
Для больших выборок используют подвыборку (witness-комплексы) или сжатие по плотности.

Связанные темы

Плотностная кластеризация · Топология данных

Ключевые тезисы

Подробный разбор

Фильтрация вместо одного порога

Теорема устойчивости

Как это считают на практике

Связанные темы

Topology basics90%

Simplicial complexes90%

Homology90%

Persistence Diagrams90%

Persistence Landscapes90%

Betti Numbers90%

Mapper90%

Topological features90%

TDA + Machine Learning90%

TDA + Time Series90%

Metric spaces90%

HDBSCAN85%

Spectral Clustering85%

DBSCAN85%

Dimensionality Reduction85%

Eigenvector85%