Анализ графов, сетей, функций сходства (курс лекций, А.И. Майсурадзе)

Материал из MachineLearning.

Спецкурс для учащихся магистратуры и аспирантуры факультетов ВМК и КИ МГУ.
- Аспиранты факультета ВМК МГУ ранее слушали его как «Метрические методы интеллектуального анализа данных».
Экзамен с оценкой.
Преподаватели: к.ф.-м.н. Арчил Ивериевич Майсурадзе.

Аннотация

Рассматриваются модели, задачи и методы анализа систем, описание которых базируется на попарном или множественном взаимодействии объектов. Эти объекты могут быть однотипными (гомогенные системы) или разнотипными (гетерогенные системы). В математике приняты 3 основные способа формализации упомянутого взаимодействия.

Когда важно само наличие или отсутствие взаимодействия, формализация проводится на языке теории графов. Расширении графового описания различными характеристиками вершин и рёбер приводит к сетям.
Если считается, что каждый набор объектов может быть охарактеризован численно, говорят о расстояниях или сходствах.
Также описанием взаимодействия объектов может быть порядок на них.

Представлена теоретическая основа для формализации задач и построения, реализации и анализа широкого спектра моделей и методов ИАД. Исследуются эвристические модели данных, описывающие исходную информацию об объектах распознавания на основе различных реализаций понятия сходства. Рассматриваются задачи, требующие решения при реализации указанных моделей. Изучаются специальные структуры данных и алгоритмы, позволяющие эффективно настраивать и использовать изучаемые модели. Идея сходства свойственна человеческому мышлению, это породило целый комплекс подходов для всех фундаментальных задач ИАД — так называемые метрические методы. Рассмотрены методы построения и вычисления функций сходства, согласование сходства на различных множествах объектов, синтез новых способов сравнения объектов на базе уже имеющихся. Рассмотрен комплекс приёмов, предназначенный для эффективного представления и обработки метрической информации вычислительными системами. Рассматриваются характеристики графов, активно используемые при их анализе. Изучаются алгоритмы на графах — как теоретически, так и с точки зрения эффективной реализации. Различные модели роста графов. Построение репрезентативных выборок на графах. Генерация графов с заданными характеристиками. Существенное внимание в курсе уделено многочисленным формализациям кластерного анализа. Показано, какие задачи решают распространённые методы. Проведена типологизация широкого спектра задач кластеризации для гомогенных и гетерогенных систем (бикластеризация, кокластеризация).

Зачёт

Для получения зачёта учащийся должен защитить работу по одной из предложенных в ходе учебного курса тем. Работа может быть представлена как реферат (в жанре lecture notes).

Примеры тем работ:

Алгоритмы сгущения графа
Проверка согласия со степенным распределением
Сложность алгоритма Дейкстры
Описание и теоретические свойства алгоритма А*
Двунаправленные алгоритмы поиска кратчайшего пути
Последовательное и параллельное вычисление остовного дерева
Поиск сообществ (community detection)
Методы выборки репрезентативного подграфа
Наделение метрического пространства свойствами ЛВП
Нормализация метрик
Нормировка метрик
Способы оценки по выборке различных инвариантов метрических пространств
Связь между теорией метрик и теорией потоков, использование алгоритмов из теории потоков для метрик
Обучение метрик с учетом цели
Обучение метрик для реконструкции исходных описаний
Точный поиск ближайших соседей (NNS)
Приближенный поиск ближайших соседей (ANNS)
Алгоритмы реализации метрик
Коррекция локальных возмущений в конечных метриках
Обоснование и оценка качества метрических алгоритмов