Mapper algorithm: топологический скелет высокоразмерных данных

Цели урока

• Понимать четыре шага pipeline Mapper
• Выбирать подходящую lens function для исследовательской задачи
• Подбирать resolution и gain с учётом стабильности
• Применять Mapper для интерпретации нейросетей и биомедицинских данных

Предварительные знания

• Базовая версия Mapper (top-29)
• Bottleneck и Wasserstein distances (top-33)
• Кластеризация (DBSCAN, single-linkage)
• Dimensionality reduction (PCA, UMAP)

• Алгоритм Mapper (basic)
• Bottleneck/Wasserstein
• Stability theorem

Mapper нашёл новый подтип рака груди, который не видел ни один кластеризатор - 9 пациенток с 100 процентов выживаемостью.

• **Genomics**: breast cancer subtype discovery с 100 процентами выживаемости в выявленной flare-группе
• **Neuroscience**: fMRI brain dynamics через циклические Mapper-структуры
• **Drug discovery**: картирование 100 тысяч молекул в химическом пространстве
• **Explainable AI**: топологическая интерпретация активаций нейросетей
• **Finance**: анализ корреляционных матриц финансовых инструментов

Mapper от Stanford до Ayasdi

Алгоритм Mapper был представлен Гурджит Сингхом, Факундо Мемоли и Гуннаром Карлссоном на Symposium on Point-Based Graphics в 2007 году. В 2008 году Карлссон, Сингх и Дара Энтехаби основали компанию Ayasdi для коммерциализации TDA-инструментов, включая Mapper. Поворотным моментом стала статья Николау, Левине и Карлссона в PNAS 2012 года: Mapper выявил подтип рака груди с превосходной выживаемостью у 9 пациенток. Эта работа стала визитной карточкой TDA в биомедицине и привлекла внимание широкой аудитории. Сейчас Mapper реализован в открытых библиотеках (kepler-mapper, scikit-tda, Giotto-TDA) и широко используется в вычислительной биологии и нейронауках.

Pipeline Mapper: от данных к графу

2012 год. Моника Николау и её соавторы из Стэнфорда запускают Mapper на 295 профилях экспрессии генов больных раком груди. Стандартная кластеризация k-means находит ожидаемые 3 подтипа. Но Mapper выявляет нечто иное - flare, маленькую связную ветвь топологического скелета, отщеплённую от основной сети. В этой ветви 9 пациенток. У этой группы 100 процентов пятилетней выживаемости при том, что у остальной когорты от 60 до 70 процентов. Mapper нашёл новый подтип рака груди, который не видел ни один кластеризатор. Статья вышла в PNAS и стала визитной карточкой TDA в биомедицине.

Mapper работает в четыре шага, каждый из которых имеет ясный смысл. Lens сжимает данные до низкоразмерного представления, cover разрезает образ в перекрывающиеся куски, кластеризация в прообразах превращает куски в узлы графа, нерв из узлов и пересечений даёт финальный топологический скелет. Результат - симплициальный комплекс, обычно визуализируемый как граф.

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

Mapper визуализирует пространство активаций последнего слоя нейросети. Каждый узел - кластер похожих по активациям тестовых примеров. Цвет узла - доминирующий класс. Mapper-граф показывает топологическую структуру решений: какие классы соседствуют, где decision boundary, какие примеры не вписываются ни в один кластер.

В отличие от persistence diagrams, Mapper-граф зависит от трёх произвольных выборов: lens, cover, кластеризации. Один и тот же датасет даёт разные графы при разных параметрах. Это одновременно сила (можно увидеть разные аспекты) и слабость (нет канонического ответа).

Выбор lens function

Lens - самый влиятельный параметр Mapper. Один и тот же датасет, разные lens, разные графы, разные открытия. В оригинальной статье 2012 года использовалась L2-эксцентриситет: расстояние от каждой точки до центра масс облака. Эта lens подсветила периферийные пациенты - именно flare-группа была в самой дальней части эксцентриситета.

Стандартные варианты lens: (1) L2-эксцентриситет - расстояние до центра, (2) density - количество соседей в фиксированном радиусе, (3) PCA-проекция - первая или первые две главные компоненты, (4) UMAP/t-SNE embedding в R^2, (5) предметно-специфические - выживаемость, время до события, экспрессия конкретного гена.

Bottleneck автоэнкодера на тех же данных, на которых будет работать Mapper, даёт оптимальную lens для нелинейных структур. Для генома 20000 генов в эмбеддинг 2-3 размерности. Mapper на этом эмбеддинге выявляет траектории дифференцировки клеток.

Если lens сам содержит ошибки (например, плохо обученный автоэнкодер), Mapper-граф наследует все эти артефакты. Lens лучше валидировать отдельно: например, проверить устойчивость к bootstrap-перевыборкам данных.

Не существует универсально лучшей lens. Выбор - часть исследовательского процесса. Практика: запускать Mapper с несколькими lens, сравнивать графы, искать общие устойчивые структуры. Если все lens показывают одну и ту же ветвь - это сильный сигнал. Если структура исчезает при смене lens - это артефакт конкретного выбора.

Параметры покрытия и стабильность

Cover - вторая половина смысла Mapper. После lens нужно решить: как разрезать одномерный (или k-мерный) образ на куски? Два параметра управляют этим: resolution r - количество интервалов, gain g - доля перекрытия между соседними интервалами. Малое r даёт грубый граф, большое - детализированный. Малое g даёт разорванные графы, большое - сильно связные.

Типичные значения параметров на практике: r от 10 до 50 (зависит от размера датасета), g от 0.3 до 0.5 (стандарт). Большая gain даёт более связный граф, меньшая - больше отдельных компонент. Подбор параметров - итеративный процесс с визуальной обратной связью.

Запуск Mapper на сетке параметров (r, g) даёт ансамбль графов. Стабильные структуры, которые появляются на большой области сетки, считаются надёжными. Технологии MultiNerve и Mapper Interleaving формализуют эту идею: они выбирают параметры, при которых выход Mapper устойчив.

В отличие от persistence diagrams, у Mapper нет универсальной теоремы стабильности уровня 2007 года. Carriere и Oudot в 2018 году доказали ограниченную stability при правильном выборе параметров, но в общем случае Mapper неустойчив. Это означает осторожность при выводах: один Mapper-граф - не доказательство.

Современные библиотеки (kepler-mapper, scikit-tda, Giotto-TDA) автоматизируют подбор параметров: запускают grid search и измеряют похожесть выходов. Если соседние ячейки сетки дают графы с малой Wasserstein-distance между диаграммами Mapper, конфигурация считается устойчивой.

Применения: геномика, нейронауки, drug discovery

За пятнадцать лет существования Mapper стал стандартным инструментом топологического исследования в нескольких научных областях. Геномика использует его для поиска новых подтипов заболеваний. Нейронауки - для анализа функциональной связности мозга. Фарма - для картирования химического пространства потенциальных лекарств. Финансы - для анализа корреляционных структур рынка. Mapper не заменяет статистику и ML - он дополняет их топологической перспективой.

Пять флагманских применений Mapper: (1) breast cancer subtype discovery (Nicolau 2012), (2) T-cell дифференциация (Rizvi 2017), (3) fMRI brain dynamics (Saggar 2018), (4) chemical space mapping в drug discovery, (5) market correlation analysis в финансах.

Mapper-граф активаций последнего слоя ResNet50 на ImageNet показывает: классы организованы не дискретно, а в виде непрерывного многообразия. Кошки и собаки топологически соседствуют, причём через породы. Это объясняет почему сеть путает определённые пары классов - они близки на графе.

Mapper генерирует гипотезы, а не подтверждает их. Любое открытие, сделанное с помощью Mapper (например, flare в breast cancer), требует независимой валидации статистическими методами на держаной выборке. Сам граф - не статистически значимое утверждение.

Современные реализации Mapper: kepler-mapper (Python, активная разработка), scikit-tda (часть scikit-learn ecosystem), Giotto-TDA (промышленный TDA-стэк), TDAMapper (R). Все они поддерживают экспорт в визуализации (NetworkX, Graphviz, D3.js) и интеграцию с pandas/sklearn pipelines.

Расширения и применения Mapper

Mapper интегрирован в современный data science стек как инструмент исследования данных.

• TDA в нейросетях — Связанная тема
• Witness complexes — Связанная тема
• TDA для временных рядов — Связанная тема
• Persistent homology (advanced) — Связанная тема

Ключевые идеи

• Mapper - четырёхшаговый pipeline: lens, cover, кластеризация, нерв
• Lens выбирает аспект данных для исследования - L2-эксцентриситет, density, learned embedding
• Resolution и gain контролируют детализацию и связность графа
• Mapper не имеет универсальной stability - надёжность через grid search и сравнение выходов
• Применения: breast cancer subtypes, brain dynamics, drug discovery, explainable AI
• Mapper генерирует гипотезы, не подтверждает их статистически

Вопросы для размышления

• Какие свойства данных делают Mapper более информативным чем k-means кластеризация?
• Почему в production важна стабильность к параметрам, и как её оценивать для Mapper?
• Какие ограничения у Mapper по сравнению с persistence diagrams?

Связанные уроки

• top-29 — базовая версия алгоритма Mapper
• top-33 — метрики для сравнения Mapper-выходов
• top-32 — stability для Mapper-графов
• top-37 — Mapper для интерпретации нейросетей
• alg-12-bfs