Топологический анализ данных

Бакалавриат 2024/2025

Статус: Курс по выбору (Экономика и анализ данных)

Направление: 01.03.02. Прикладная математика и информатика

Кто читает: Департамент больших данных и информационного поиска

Где читается: Факультет экономических наук

Когда читается: 3-й курс, 3, 4 модуль

Формат изучения: без онлайн-курса

Охват аудитории: для всех кампусов НИУ ВШЭ

Преподаватели: Безродная Елена Сергеевна

Язык: русский

Кредиты: 6

Полная версия программы учебной дисциплины Задать вопрос

Аннотация

Топологический анализ данных - дисциплина на стыке прикладной и теоретической математики, основанная на идее, что алгебраические и геометрические инварианты метрических пространств можно использовать как признаки облаков точек. Это позволяет количественно оценивать и придать смысл словосочетанию “форма данных”. Курс будет состоять из двух частей. В первой, более теоретической, мы расскажем математические сюжеты, раскрывающие с разных сторон суть алгоритмов прикладной топологии. Во второй части курса мы свяжем алгебраическую базу из первой части со статистикой, оптимальным транспортом и нейросетями и разберем современные приложения в анализе данных.

Цель освоения дисциплины

Использовать имеющиеся пакеты для работы с гомологиями
Уметь писать алгоритм для вычисления гомологий с нуля

Планируемые результаты обучения

Знать основы топологии, гомологической алгебры, и теории представлений колчанов
Уметь пользоваться основными методами и алгоритмами непосредственно топологического анализа данных

Содержание учебной дисциплины

Вводная часть: что такое топологический анализ данных. Основные необходимые понятия из топологии: компактность, связность, гомеоморфизм, гомотопическая эквивалентность. Общая идея, почему бывает полезно добавить в топологию временную параметризацию.
Симплициальные комплексы и симплициальные гомологии: мотивация, определения. Гомотопическая инвариантность, функториальность.
Фильтрации симплициальных комплексов и устойчивые гомологии. Теорема о классификации устойчивых модулей и модифицированный алгоритм Гаусса для вычисления устойчивых гомологий. Диаграмма устойчивости -геометрически интерпретируемый инвариант фильтрации.
Математические обобщения: зигзаг-устойчивые гомологии, мультипараметрическая устойчивость. Относительные гомологии.
Важные математические дополнения. Введение в теорию Морса. Информационное содержание устойчивых гомологий: почему устойчивые гомологии с алгоритмической точки зрения - это не про гомологии и даже не совсем про топологию.
Оператор Ходжа-Лапласа и его связь с гомологиями и числами Бетти. Теория Ходжа.
Устойчивый оператор Ходжа-Лапласа, его связь с устойчивыми гомологиями и устойчивыми числами Бетти.
Теория симплициальных сетей
Алгоритм вычисления устойчивых гомологий, эвристики для его ускорения. Параллельный алгоритм вычисления устойчивых гомологий. Минимальное остовное дерево и алгоритм вычисления нулевых гомологий.
Представители классов устойчивых гомологий. Оптимальные представители.
Векторные представления диаграмм устойчивости. Дифференцируемость отображения устойчивых гомологий.
Топологический анализ данных в виде облаков точек. Геометрические комплексы. Geometry score, MTD и RTD. Снижение размерности с сохранением топологии данных.
Топологический анализ данных в виде графов и симплициальных комплексов. Расширенные устойчивые гомологии. Нейросети на графах и симплициальных комплексах.
Топологический анализ данных в виде временных рядов. Вложение временных рядов в R^n скользящим окном. Анализ матрицы корреляции.
Кластеризация как задача топологического анализа данных. Иерархическая кластеризация, дерево слияния. Упрощение и обрезка дерева слияния с использованием диаграммы устойчивости. Алгоритмы ToMaTo, Mapper.
Многопараметрические фильтрации. Аппроксимация многопараметрических фильтраций однопараматрическими. Многопараметрические фильтрации для кластеризации, алгоритм Persistable.

Элементы контроля

Домашнее задание 1
Листы по темам семинаров Оценивается каждый пункт домашнего задания. Возможно набрать 0-100% оценки за пункт, суммы оценок за пункты суммируются в оценку за ДЗ. Возможны начисления до 20% бонусов за ДЗ за выполнение необязательных пунктов ДЗ.
Домашнее задание 2
Первая часть ДЗ2 посвящена вычислению признаковых описаний симплициальных комплексов, вторая часть – базовым алгоритмам вычисления устойчивых гомологий и их использованию в моделях машинного обучения. Первая часть выдается после лекций 6-8, вторая часть – после лекций 9-11.
Домашнее задание 3
ДЗ3 состоит из двух частей и посвящено использованию методов ТАД для задач машинного обучения на типах данных рассмотренных в лекциях 13-16. Первая часть выдается после лекций 13-14, вторая часть – после лекций 15-16.
Проект, предзащита
Предзащита проектов проходит очно (в аудитории или дистанционно), в формате доклада на 10 минут. В докладе необходимо раскрыть задачу, необходимую теорию и план работы над проектом. Проекты рассчитаны для индивидуальной работы, либо в команде из двух человек. Слайды доклада необходимо выслать ассистенту курса
Проект, защита
Защита проектов проходит очно (в аудитории или дистанционно), в формате доклада на 15 минут. В докладе необходимо напомнить содержание задачи, привести рабочую гипотезу и продемонстрировать ее проверку. При выполнении проекта в команде необходимо раскрыть индивидуальный вклад каждого из участников. Слайды доклада, код, ноутбуки необходимо выслать ассистенту курса.

Промежуточная аттестация

2024/2025 4th module
Итог = Округление(0.2 * ДЗ1 + 0.15 * ДЗ2 + 0.15 * ДЗ3 + 0.15 * ПзП + 0.35 * ЗП), где: ДЗx — оценки за домашние задания, ПзП — оценка за предзащиту проекта, ЗП — оценка за защиту проекта.

Список литературы

Авторы

Безродная Елена Сергеевна

Программа дисциплины