Топология данных

Задача

Дано облако точек в многомерном пространстве: результаты измерений, изображения, показания датчиков, профили экспрессии генов. Вопрос: какой формы это облако?

Не «где его центр» и не «какова дисперсия» — а есть ли в нём петли, полости, разветвления; лежит ли оно вблизи окружности, сферы, тора или чего-то иного.

Вопрос не праздный. Форма данных отражает структуру порождающего процесса: замкнутая петля означает цикличность, две компоненты — два разных механизма, тор — два независимых параметра.

Стандартные методы статистики к нему не приспособлены: они меряют расстояния и дисперсии, а расстояние зависит от единиц измерения, от выбора координат, от нормировки. Форма — не зависит. Это ровно то, чем занимается топология.

Препятствие

Прямо применить гомологии к конечному набору точек нельзя: у конечного множества гомологии тривиальны, оно распадается на отдельные точки и никаких «дыр» не имеет.

Естественный ход — «раздуть» точки в шарики радиуса $\varepsilon$ и посмотреть на гомологии объединения (или на построенный по нему комплекс Вьеториса — Рипса: симплекс проводится там, где все попарные расстояния меньше $\varepsilon$).

Но тут возникает главная трудность: ответ зависит от $\varepsilon$. При малом радиусе всё распадается на точки, при большом всё сливается в один ком, а посередине — как повезёт. Никакого объективного способа выбрать $\varepsilon$ нет.

Решение: не выбирать

Идея, на которой всё держится, проста и радикальна: не выбирать $\varepsilon$, а проследить за всеми сразу.

Будем увеличивать $\varepsilon$ от нуля до бесконечности. Комплексы вложены друг в друга, значит их гомологии связаны гомоморфизмами — получается фильтрация. Каждый топологический признак (компонента, петля, полость) в какой-то момент рождается и в какой-то умирает.

$$\text{признак}\ \longleftrightarrow\ \text{пара }(\varepsilon_{\text{рожд}},\ \varepsilon_{\text{смерть}}).$$

Изобразим все пары точками на плоскости — получится диаграмма персистентности. Признаки с коротким временем жизни (близко к диагонали) — шум; с долгим — настоящая структура данных.

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

Ключевая теорема, делающая метод пригодным для практики, — устойчивость (Кон-Оксой, Эдельсбруннер, Харер, 2007): малое изменение данных вызывает малое изменение диаграммы. Без неё метод был бы бесполезен: реальные измерения всегда с шумом.

Кто и когда

Хронология складывалась так.

• 2002 — Эдельсбруннер, Летчер и Зомородян вводят персистентность и первый алгоритм её вычисления.
• 2005 — Афра Зомородян и Гуннар Карлссон дают алгебраическое обоснование: доказывают, что персистентный модуль над полем однозначно раскладывается в набор «интервалов», то есть диаграмма — полный инвариант. Это превратило вычислительный приём в теорию.
• 2009 — Карлссон публикует обзор «Topology and Data» в «Bulletin of the AMS», формулирует программу и даёт области имя. С этого момента говорят о топологическом анализе данных (TDA).

Гуннар Карлссон (род. 1952) — стэнфордский тополог, до того занимавшийся алгебраической K-теорией и теорией эквивариантных гомотопий, то есть максимально чистой математикой. В 2008 году он с коллегами основал компанию Ayasdi, применявшую TDA к промышленным данным, — редкий случай, когда алгебраический тополог становится основателем стартапа.

Второй столп области — алгоритм Mapper (Сингх, Мемоли, Карлссон, 2007): облако данных превращается в граф, наглядно показывающий его структуру. Именно им был получен самый известный прикладной результат: на данных по раку молочной железы обнаружилась группа пациентов с особым профилем выживаемости, не выделявшаяся стандартной кластеризацией.

Где работает

• Нейронауки. Анализ активности нейронов места у грызунов топологическими методами показал, что данные лежат на торе — что напрямую подтвердило гипотезу о том, как мозг кодирует положение в пространстве.
• Материаловедение. Форма пустот в аморфных материалах, структура пористых сред.
• Фармакология и геномика. Классификация вирусных штаммов, где обычные деревья не работают из-за рекомбинации: топология видит петли, которых у дерева быть не может.
• Машинное обучение. Топологические признаки как входные данные для моделей; анализ формы функции потерь.

Замыкание круга

Здесь линия заканчивается, и стоит перечислить, что в ней сошлось.

Первое: предмет собирался из курьёзов. Мосты Кёнигсберга, многогранник с дыркой, бумажная лента с полуоборотом — сто с лишним лет это были занятные задачи без общей теории, и ЭйлерЛеонард Эйлершвейцарский математик, работавший в Петербурге и Берлине · 1707–1783Самый плодовитый математик в истории: около 900 работ, половина языка современной математики — от знака $\pi$ до записи $f(x)$ — и способность считать, не глядя. сам считал задачу о мостах не математической. Дисциплина, которую сегодня преподают на всех математических факультетах, выросла из вещей, не казавшихся серьёзными никому.

Второе: главный приём — перевод формы в алгебру. Числа БеттиЭнрико Беттиитальянский математик · 1823–1892Ввёл числа, меряющие, сколько в пространстве независимых «дыр» каждой размерности. Пуанкаре назвал их числами Бетти, и под этим именем они стоят в основании алгебраической топологии., группы гомологий, гомотопические группы, характеристические классы, полиномы узлов — всё это способы сопоставить фигуре алгебраический объект так, чтобы разные объекты доказывали различие фигур. Побочным следствием этой программы стала теория категорий — язык, на котором сегодня говорит вся математика.

Третье: самое очевидное оказалось самым трудным. Что кривая делит плоскость надвое (Жордан), что $\mathbb{R}^{2}$ и $\mathbb{R}^{3}$ разные (Брауэр), что односвязное трёхмерное многообразие — сфера (Перельман): три утверждения, очевидные всякому и потребовавшие соответственно десятилетий, полувека и столетия. Топология платит за общность необходимостью доказывать то, что видно.

Четвёртое: размерность ведёт себя наоборот. Гипотеза ПуанкареАнри Пуанкарефранцузский математик, физик и философ науки · 1854–1912Последний универсал математики: создал топологию, увидел хаос там, где все видели порядок, и подошёл к теории относительности вплотную, не сделав последнего шага. покорилась сначала в размерностях от пяти (Смейл), потом в четвёртой, и только потом в исходной третьей. Гладкая структура единственна везде, кроме четвёрки. Наша размерность — самая тесная и самая трудная.

Пятое, и его стоит помнить. Начиналось всё с прогулки по мостам, а кончается инструментом, которым медики ищут подгруппы больных, а нейрофизиологи — форму пространственной памяти. Между этими точками сто с лишним лет чистой мысли, ни один шаг которой не делался ради применения. Топология — лучший на этой карте аргумент в пользу того, что бесполезного знания не бывает; просто срок окупаемости у него измеряется веками.

Задача. Возьмите десяток точек, расставленных по окружности, и мысленно раздувайте вокруг каждой круг радиуса $\varepsilon$. При каком $\varepsilon$ родится «петля» (первая гомология станет нетривиальной) и при каком она умрёт?
(Ответ: петля рождается, когда соседние круги начинают пересекаться — то есть при $\varepsilon$ около половины расстояния между соседями, — и умирает, когда круги заполняют серединную дырку, то есть при $\varepsilon$ порядка радиуса окружности. Длинный интервал жизни и означает, что окружность — настоящая структура, а не шум.)