Современный ландшафт анализа данных характеризуется экспоненциальным ростом как объёмов, так и размерности обрабатываемой информации. Классические статистические методы и традиционные подходы машинного обучения, оперирующие главным образом метрическими и вероятностными характеристиками данных, всё чаще обнаруживают свою ограниченность при попытке уловить глобальную структуру, форму и, в конечном счёте, семантику изучаемых явлений. В этой связи закономерным представляется обращение к аппарату алгебраической топологии – дисциплины, изначально созданной для изучения свойств пространств, инвариантных относительно непрерывных деформаций, таких как растяжение или сжатие, но не разрыв.
Долгое время применение топологии к анализу данных сдерживалось фундаментальным препятствием: классические гомотопические и гомологические инварианты чрезвычайно чувствительны к малейшим возмущениям, что делало их бесполезными для работы с дискретными, зашумлёнными выборками. Прорыв произошёл с развитием теории устойчивых гомологий, которая позволила преодолеть этот разрыв. Ключевая идея, лежащая в основе этого подхода, заключается в отказе от анализа данных на каком-то одном фиксированном масштабе. Вместо этого рассматривается мультимасштабное семейство топологических пространств, параметризованное некоторым порогом близости, и отслеживается эволюция топологических инвариантов при изменении этого порога. Фундаментальная теорема устойчивости, доказанная Коэном-Стейнером, Эдельсбруннером и Харером, утверждает, что малое изменение исходных данных в смысле расстояния Хаусдорфа приводит к малому изменению диаграммы устойчивости в смысле bottleneck-расстояния. Именно это свойство робастности открыло дорогу для широкого применения топологических методов в анализе данных.
Целью данной статьи является построение единого, математически строгого фреймворка, охватывающего обе эти задачи, формулировка соответствующих теорем устойчивости и описание вычислительных алгоритмов, пригодных для практической имплементации.
1. Математический фундамент: от симплициальных комплексов к устойчивости
Пусть нам дано конечное множество точек, представляющее собой выборку из некоторого неизвестного многообразия или аттрактора. Наша цель – извлечь информацию о топологии этого неизвестного объекта. Поскольку конечный набор точек топологически тривиален (это просто набор несвязных компонент), необходимо построить непрерывный объект, аппроксимирующий лежащее в основе пространство. Для этого мы обратимся к понятию симплициального комплекса.
Напомним, что геометрическим kk-мерным симплексом называется выпуклая оболочка k+1k+1 аффинно независимых точек. Вершины – 0-симплексы, рёбра – 1-симплексы, треугольники – 2-симплексы, и так далее. Симплициальным комплексом KK называется конечный набор симплексов в RdRd, такой что: (1) любая грань симплекса из KK также принадлежит KK; (2) пересечение любых двух симплексов из KK является либо пустым множеством, либо их общей гранью. Топология такого комплекса, называемая полиэдральной, наследуется из RdRd.
Центральным для нас будет комплекс Вьеториса-Рипса, который определяется исключительно на основе попарных расстояний между точками содержательная топологическая информация заключена в промежуточных стадиях этого процесса. Следующий шаг – вычисление алгебраических инвариантов для каждого члена фильтрации. Группа kk-мерных гомологий с коэффициентами в поле FF является векторным пространством, размерность которого, называемая kk-м числом Бетти, неформально интерпретируется как количество kk-мерных «дыр». Так, β0β0 – число компонент связности, β1β1 – число одномерных замкнутых петель, не являющихся границами, β2β2 – число трёхмерных пустот, и т. д. Главное преимущество гомологий перед прямым геометрическим подсчётом заключается в их функториальности: отображение включения.
2. Топологический анализ временных рядов: реконструкция аттрактора и шум
Перейдём к первой из заявленных прикладных задач. Пусть мы наблюдаем скалярный временной ряд, порождённый некоторой неизвестной динамической системой с непрерывным временем, или являющийся дискретной по времени выборкой из такой системы. Применим описанную выше процедуру вычисления устойчивых гомологий. Рассмотрим классический пример – аттрактор Лоренца. Его топология характеризуется наличием двух различных «дыр», что отражается в диаграмме устойчивости для размерности 1 наличием двух точек, значительно отстоящих от диагонали. При этом 0-мерные гомологии, отвечающие компонентам связности, устроены относительно тривиально: аттрактор представляет собой одну связную компоненту, что проявляется в наличии одного очень долгоживущего 0-мерного класса.
3. Топологическая регуляризация в глубоких нейронных сетях
Обратимся теперь к совершенно иной области – обучению глубоких нейронных сетей прямого распространения. Рассмотрим стандартную задачу классификации. Нейронную сеть можно концептуально разделить на две части: кодировщик, отображающий входные данные в скрытое представление в пространстве, и классификатор, выполняющий линейное разделение классов в этом скрытом пространстве. В процессе обучения, путём минимизации эмпирического риска, сеть деформирует входное многообразие данных, стремясь сделать его удобным для финального линейного слоя. Скрытое представление Z для обучающей выборки образует облако точек, топологию которого мы теперь можем изучать. С какой топологии следует желать? Ответ зависит от априорных предположений о задаче. Во многих случаях разумно ожидать, что данные каждого класса в исходном пространстве формируют своё связное многообразие, возможно, с определённой внутренней структурой (например, класс «цифра 8» топологически отличен от «цифры 0» наличием одной одномерной дыры). В идеальном сценарии хороший кодировщик должен сохранять эту значимую топологию, упрощая геометрию, то есть «распрямляя» многообразие, но не разрывая и не склеивая его критические части. Альтернативный, и часто более практичный сценарий, особенно для задач тонкой классификации, состоит в том, что мы вообще хотим получить тривиальную топологию скрытого представления: каждый класс должен стягиваться в плотный, односвязный кластер, чтобы максимизировать линейную разделимость.
