КАРТОЧКА ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ

Информация подготовлена на основании данных из Информационно-аналитической системы РНФ, содержательная часть представлена в авторской редакции. Все права принадлежат авторам, использование или перепечатка материалов допустима только с предварительного согласия авторов.

 

ОБЩИЕ СВЕДЕНИЯ

Номер 22-11-00073

НазваниеАнализ неопределенности и оптимизация в моделях интеллектуального анализа данных

РуководительКалягин Валерий Александрович, Доктор физико-математических наук

Организация финансирования, регион федеральное государственное автономное образовательное учреждение высшего образования "Национальный исследовательский университет "Высшая школа экономики", г Москва

Период выполнения при поддержке РНФ 2022 г. - 2024 г. 

Конкурс№68 - Конкурс 2022 года «Проведение фундаментальных научных исследований и поисковых научных исследований отдельными научными группами».

Область знания, основной код классификатора 01 - Математика, информатика и науки о системах, 01-202 - Интеллектуальный анализ данных и распознавание образов

Ключевые словаинтеллектуальный анализ данных, оптимизация, сетевые модели, приятие решений, неопределенность

Код ГРНТИ27.47.00, 27.47.19, 27.47.23

 

ИНФОРМАЦИЯ ИЗ ЗАЯВКИ

Аннотация
Модели на основе графов в наши дни стал мощным инструментом во многих научных и прикладных областях и особенно в принятии решений и интеллектуальном анализе данных. В литературе разработаны различные алгоритмы интеллектуального анализа данных на основе графовых моделей. Однако, на практике, данные как правило имеют некоторую неопределенность (статистическую или информационную). Неопределенность в данных влечет за собой неопределенность результатов применения методов принятия решений и интеллектуального анализа данных. Оценка неопределенности является, таким образом, важнейшим элементом правильной интерпретации полученных результатов. Для графовых моделей этот аспект пока еще недостаточно изучен. В проекте предполагается масштабное исследование неопределенности актуальных и практически значимых задач. Рассматриваются задачи идентификации графовых структур (graphical model selection) в сетях случайных величин, задачи оптимизации на графах в условиях неопределенности, задачи кластеризации на графах в условиях неопределенности, задачи одновременной группировки объектов и признаков в данных (задачи бикластеризации). Развивается, начатый ранее участниками проекта, новый подход к оценке статистической неопределенности идентификации графовых структур в сетях случайных величин с приложениями к задачам анализа сетей экспрессии генов, сетевых моделей мозга, сетевых моделей наблюдений климата, сетей фондовых рынков и другим. Целью проекта является разработка новых теоретических подходов к построению устойчивых алгоритмов идентификации графовых структур в практически востребованной постановке отсутствия информации о распределениях. Основное внимание будет сосредоточено на двух актуальных задачах: разработка устойчивых алгоритмов идентификации графа концентраций и построение устойчивых процедур обнаружения динамики графовых структур (граф концентраций, отсеченный граф, клики и независимые множества). Исследуются новые, практически значимые, постановки задач комбинаторной оптимизации на графах в условиях вероятностной неопределенности с неизвестными параметрами. В частности, мы предполагаем, что неопределенные параметры (например, стоимости ребер в контексте задачи поиска кратчайшего пути или потребности в контексте задачи маршрутизации транспорта) можно наблюдать только с помощью конечного набора случайных наблюдений. Однако, в отличие от большинства связанных работ, случайные наблюдения также подвержены неопределенности, например, из-за ошибок измерений или специфичной для конкретной проблемы формы исторических данных. Мы используем робастно-стохастический подход к оптимизации, при котором неопределенность параметров задачи описывается набором (или семейством) вероятностных распределений, которые совместимы с имеющейся информацией. В этом случае лицо, принимающее решение, стремится минимизировать свои ожидаемые потери (или некоторую меру риска, если лицо, принимающее решение, склонно к риску) при наихудшем возможном распределении неопределенных параметров. Стандартный подход к построению описанного набора неоднозначностей на основе данных заключается в рассмотрении всех распределений в пределах некоторого заранее определенного расстояния от эмпирического распределения данных. Однако в нашей постановке задачи эмпирическое распределение также подвержено неопределенности, что предполагает построение вспомогательного семейства всех возможных эмпирических распределений. Мы демонстрируем, что при некоторых дополнительных предположениях полученная трехуровневая задача оптимизации может быть переформулирована как задача смешанного целочисленного программирования. Кроме того, мы проводим численные эксперименты, чтобы продемонстрировать преимущества и практическую значимость предлагаемого подхода. В рамках развиваемых подходов рассматриваются актуальные, но пока еще мало изученные, задачи оценки неопределенности алгоритмов интеллектуального анализа данных на графах. В проекте предлагается исследовать эту проблему для алгоритмов кластеризации в сетях случайных величин. Анализируется устойчивость известных алгоритмов кластеризации. Разрабатываются общие подходы к построению устойчивых алгоритмов. Построенные алгоритмы используются для кластеризации в сетях коэкспрессии генов и сетях фондовых рынков. В проекте развиваются новые подходы и разрабатываются новые алгоритмы в задаче бикластеризации. В задаче бикластеризации объекты рассматриваются вместе со своими признаками как единое целое и вычисляется близость между целыми структурами объект-признак. Предлагается новая постановка задачи бикластеризации, как задачи оптимизации с новыми переменными объект-признак. Исследуется связь полученной задачи оптимизации с задачей редактирования бикластеров в графе (Bicluster Graph Editing Problem). Показывается, что предложенный подход дает лучшие результаты в различных областях, включая задачи биоинформатики и задачи о формировании производственных ячеек.

Ожидаемые результаты
В задаче идентификации графовых структур будет развит, разрабатываемый авторами, теоретический подход к оценке неопределенности для новых типов графовых структур в условиях отсутствия информации о распределениях. Для практически важной структуры, графа концентраций, будут построены новые алгоритмы идентификации в различных сетях случайных величин. Будет исследована их неопределенность и устойчивость к изменению распределений и построены устойчивые алгоритмы идентификации c малой неопределенностью (distributionally robust efficient algorithms). Впервые в литературе будет исследована задача обнаружения динамики графовых структур в различных сетях случайных величин. Будут построены тесты на совпадение графовых структур и на обнаружение динамики графовых структур в условиях неопределенности. Будет проведена оценка необходимого для надежного обнаружения динамики времени наблюдения. Полученные результаты будут применены к сетям коэкспрессии генов и сетям фондовых рынков. Для сетей фондовых рынков найденные тесты обнаружения динамики графовых структур будут использованы для анализа общих тенденций изменения рынков. Для задач комбинаторной оптимизации на графах в условиях вероятностной неопределенности будут рассмотрены различные способы формирования вероятностных ограничений из набора данных. Будет получен и исследован широкий класс связанных с ними трехуровневых задач комбинаторной оптимизации с вероятностной неопределенностью. С помощью теории двойственности для задач с вероятностными ограничениями, задача третьего уровня будет сформулирована как конечная задача выпуклого или линейного целочисленного программирования. При некоторых дополнительных предположениях о целевой функции лица, принимающего решения, и семействе распределений будет получена линейная смешанно-целочисленная формулировка (СЦФ) исходной трехуровневой задачи. Будет исследована влияние неточных данных на результат оптимизации. Будет рассмотрена модель динамического дополнения набора данных с использованием зашумленных наблюдений неопределенных параметров. Будет исследован важный компромисс между размером выборки и качеством добавляемых случайных наблюдений. Для анализа этого компромисса, будут проведены численные эксперименты для многих классов задач комбинаторной оптимизации и различных форм исторических данных. Для исследования предлагаемых алгоритмов оптимизации на графах, будут развиты и использованы методы машинного обучения для решения задач оптимизации на графах. Для задачи кластеризации на графах в условиях неопределенности будет разработан новый теоретический подход к анализу неопределенности при кластеризации в сетях случайных величин. Будут разработаны и исследованы эффективные алгоритмы снижения этой неопределенности. Полученные результаты будут применены к анализу алгоритмов поиска кластеров в сетях экспрессии генов и сетях фондовых рынков. Для задач бикластеризации будет выполнен теоретический анализ этих задач в разных постановках и проведен анализ их сложности, включающий анализ NP-трудности. Будут разработаны новые эффективные алгоритмы решения задач бикластеризации. Полученные результаты будут применены к анализу прикладных задачи бикластеризации в производстве, прикладных задачи бикластеризации в биоинформатике, задачи разбиения графа на бикластеры, задачи разбиения графов на квази-клики. Ожидаемые результаты соответствуют мировому уровню исследований в данной области и будут представлены к публикации в международных журналах высокого уровня. По результатам исследований будут сделаны доклады на международных конференциях и семинарах.

 

ОТЧЁТНЫЕ МАТЕРИАЛЫ

Аннотация результатов, полученных в 2022 году
Предложен новый подход к измерению статистической неопределенности процедур идентификации графовых структур по наблюдениям.  Такой подход заключается в: 1) построении верхних и нижних доверительных границ истинных графовых структур; 2) разделении выводов на значимые и незначимые; 3)  определении неопределенности, как разницы между верхней и нижней доверительными границами. Рассмотрен широкий класс комбинаторных задач (в том числе, задач маршрутизации на графах) в условиях вероятностной неопределенности. При этом предполагается, что стоимости ребер/времена в пути являются случайными, а их вероятностное распределение может наблюдаться только с помощью конечной тренировочной выборки. Сформулирована задача робастно-стохастической оптимизации, в которой ожидаемое значение функции потерь оптимизируется по множеству переменных исходной задачи оптимизации в предположении наихудшего (с точки зрения этой же целевой функции) возможного распределения стоимостей ребер. При этом целью работы является разработка способов построения семейства допустимых распределений в случае, когда тренировочная выборка известна неполностью.   Рассмотрено несколько моделей. В первой модели рассматривается многостадийная задача поиска кратчайшего пути, в которой в качестве тренировочных данных могут использоваться интервальные данные для отдельных ребер и данные о суммарной стоимости для некоторых подмножеств ребер. Для этой модели получены линейная смешанно-целочисленная формулировка, а также проведено сравнение с соответствующей одностадийной моделью. Во второй модели мы строится семейство распределений, которое будет учитывать неполные данные (а именно разное число наблюдений для разных компонент вектора стоимостей), и при этом будет оптимально в некотором асимптотическом смысле. Вторая модель при этом оказывается применимой к любой задаче линейного смешанно-целочисленного программирования, а полученные экспериментальные результаты подтверждают целесообразность ее применения при определенных значениях параметров тренировочной выборки.       Развит новый теоретический подход к оценке неопределенности кластеризации в сетях случайных величин. Проведены масштабные, при изменении широкого набора параметров, вычислительные эксперименты оценки неопределенности кластеризации для блок корреляционной модели сети случайных величин. Проведенные эксперименты показывают адекватность предложенного подхода.

 

Публикации

Аннотация результатов, полученных в 2023 году
Развит новый теоретический подход к определению и оценке статистической неопределенности непараметрических процедур идентификации графовых структур. Показано, что процедура, основанная на мере Кендалла, устойчива не только при отклонении распределения от нормального, но и при отклонении от условия независимости. Предложена процедура идентификации слабо коррелированных случайных величин, основанная на мере Кендалла и процедуре Холма. Построены устойчивые процедуры идентификации графовых структур, основанные на тестах Манна-Уитни и модифицированных процедурах одновременной проверки гипотез однородности. Рассмотрен класс задач линейного смешанно-целочисленного программирования (CЦЛП) с неопределенностью в параметрах целевой функции. Предполагается, что параметры образуют случайный вектор, вероятностное распределение которого можно наблюдать только через конечный набор тренировочных данных. В отличие от большинства связанных исследований в литературе, предполагается также неопределенность в лежащем в основе наборе данных. Эта неопределенность описывается множеством линейных ограничений для каждого наблюдения, а неопределенность в распределении (для фиксированной реализации данных) определяется с использованием шара Вассерштейна первого типа с центром в эмпирическом распределении данных. Общая проблема формулируется как проблема трехуровневой робастно-стохастической оптимизации (РСО). Во-первых, доказано, что трехуровневая задача допускает одноуровневую СЦЛП формулировку, если класс функций потерь ограничен биаффинными функциями. Во-вторых, оказывается, что для нескольких конкретных форм неопределенности данных, описанная задача может быть решена достаточно быстро с использованием номинальной СЦЛП задачи. Наконец, проведено вычислительное исследование, в котором численно исследуются качество нашей модели на обучающей выборке и вычислительная сложность СЦЛП формулировки для нескольких областей применения. Проведен анализ неопределенности алгоритмов кластеризации в гауссовских сетях случайных величин для различных мер близости. Проанализировано влияние мер близости (similarity measures) на качество алгоритмов кластеризации для гауссовских распределений случайного вектора. В качестве мер близости использованы различные типы корреляций. Показано преимущество сетей корреляций Кендалла. Рассмотрена задача идентификации графа концентраций в гауссовских сетях случайных величин для различных мер близости. Впервые исследована неопределенность различных алгоритмов идентификации графа концентраций в зависимости от плотности графа. Показано низкое качество алгоритмов при росте плотности. Формулируется и обсуждается задача корректировки параметров алгоритмов при изменении плотности графа.

 

Публикации

1. Аросланкин А.Д., Калягин В.А. Uncertainty of graph clustering in correlation block model Communications in Computer and Information Science, v.1881, pp.353-363 (год публикации - 2023) https://doi.org/10.1007/978-3-031-43257-6_26

2. Калягин В.А., Костылев И.Д. Graph density and uncertainty of graphical model selection algorithms Communications in Computer and Information Science, v.1913 (год публикации - 2024)

3. Кетков С.С. On the Multistage Shortest Path Problem Under Distributional Uncertainty Journal of Optimization Theory and Applications, v.197,pp.277–308 (год публикации - 2023) https://doi.org/10.1007/s10957-023-02175-7

4. Кетков С.С. Distributionally robust mixed-integer programming with Wasserstein metric: on the value of uncertain data European Journal of Operational Research, v.313, issue 2, pp.602-615 (год публикации - 2023) https://doi.org/10.1016/j.ejor.2023.10.018

5. Колданов П.А., Колданов А.П., Семенов Д.П. Confidence bounds for threshold similarity graph in random variable network Statistical Analysis and Data Mining, v.16, Issue 6, pp.583-595 (год публикации - 2023) https://doi.org/10.1002/sam.11642

6. Колданов П.А., Колданов В.А. Непараметрическая процедура сравнения эффективности работы подразделений сетевой организации Бизнес-информатика, Выпуск 1, март 2024 (год публикации - 2024)