КАРТОЧКА
ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ
Информация подготовлена на основании данных из Информационно-аналитической системы РНФ, содержательная часть представлена в авторской редакции. Все права принадлежат авторам, использование или перепечатка материалов допустима только с предварительного согласия авторов.
ОБЩИЕ СВЕДЕНИЯ
Номер 22-11-20019
НазваниеАлгебро-логические методы представления данных в задачах машинного обучения, защиты информации и оптимизации
РуководительШевляков Артём Николаевич, Доктор физико-математических наук
Организация финансирования, регион Федеральное государственное бюджетное учреждение науки Институт математики им. С.Л. Соболева Сибирского отделения Российской академии наук, Омская обл
Период выполнения при поддержке РНФ | 2022 г. - 2024 г. |
Конкурс№66 - Конкурс 2022 года «Проведение фундаментальных научных исследований и поисковых научных исследований отдельными научными группами» (региональный конкурс).
Область знания, основной код классификатора 01 - Математика, информатика и науки о системах, 01-102 - Алгебра
Ключевые словауниверсальные теории, теория графов, предикатные алгебраические системы, машинное обучение, искусственный интеллект, атомарная теория моделей, нейронные сети
Код ГРНТИ27.17.00
ИНФОРМАЦИЯ ИЗ ЗАЯВКИ
Аннотация
Проект направлен на применение идей алгебры и теории моделей для построения алгоритмов машинного обучения и искусственного интеллекта. Выбор тематики обусловлен как огромным интересом к проблемам искусственного интеллекта как в науке, так и в экономике и обществе, так и наличием здесь открытых теоретических проблем.
Основной проблемой теории искусственного интеллекта является необходимость доказательства корректной работы модели искусственного интеллекта, ее устойчивость в нестандартных ситуациях, и защита от несанкционированного использования. Данные задачи допускают множественные формализации (на языке теории вероятности, математической статистики, теории оптимизации и других разделов математики). В настоящем проекты мы предлагаем применить к изучению вопросов искусственного интеллекта подход, основанный на идеях алгебры и теории моделей.
Поясним основные преимущества такого подхода. Теория моделей является важнейшей частью современной математической логики и (в общих чертах) изучает определимость множеств с помощью логических формул. Логическая формула - это наиболее естественный объект для моделирования рассуждений и вывода, и поэтому ее использование в анализе моделей машинного обучения и искусственного интеллекта весьма целесообразно и перспективно.
Применение идей алгебры в анализе моделей машинного обучения обусловлено важностью нечисленных представлений данных.
Дело в том, что классические модели искусственного интеллекта (метрические алгоритмы, нейронные сети, байесовские модели) требуют представления обрабатываемых ими данных в виде числовых векторов (матриц). Такой подход хорошо работает, когда анализируемые объекты без потери информации могут быть представлены числовыми векторами (матрицами). Например, картинки (как массивы пикселей) легко могут быть представлены в виде векторов (матриц), и поэтому принципиальных проблем при обработке картинок современными моделями искусственного интеллекта, как правило, не возникает. С другой стороны, для некоторых объектов сложной природы (графы, гиперграфы и другие алгебраические системы предикатного языка) идеальных методов численного представления не существует. Однако важность изучения подобных алгебраических систем в анализе данных достаточна велика. Дело в том, что многие процессы могут быть смоделированы с помощью переходов между вершинами гиперграфа, а также сложные системы отношений между элементами множества могут моделироваться с помощью алгебраических систем предикатного языка.
Всё сказанное выше определяет тематику данного проекта. Планируется изучение нечисленных представлений данных и описание данных (и кластеров данных) с помощью логических формул. Теоретические исследования нечисленных представлений данных позволят реализовать новые модели искусственного интеллекта. В проекте запланировано создание и тренировка моделей искусственного интеллекта (в том числе и нейронных сетей различных классов), решающих как чисто научные, так и практические задачи в области символьных вычислений, кибербезопасности, кластеризации пользователей онлайн-сервисов.
Кроме того, в проекте будет уделено внимание теории вычислимости и теоории сложности для моделей искусственного интеллекта. Это связано с тем, что классические определения алгоритма и его временной сложности не всегда удобны, когда речь идет о моделях искусственного интеллекта. В работе модели искусственного интеллекта допускается определенный процент ошибочно принятых решений. Следовательно, алгоритм (лежащий в основе такой модели) должен работать корректно для "почти всех" . Это делает актуальным изучение в проекте альтернативных видов сложности: сложность в среднем и генерической сложности.
Ожидаемые результаты
1. Изучение нечисленного представления данных и построение моделей машинного обучения, способных анализировать данные с таким представлением. Заметим, что нечисленное представление данных (то есть представление данных не в виде вещественно-значных векторов или матриц, а в виде конечных алгебраических систем) является быстро развивающейся и актуальной дисциплиной машинного обучения. Это связано с тем, что многие процессы естественным образом моделируются с помощью таких алгебраических систем как графы, гиперграфы, матроиды и пр. Таким образом, возникает необходимость в изучении алгебраических систем подобного типа, а также связанных с ними метрик, случайных блужданий и вопросов кластеризации (разбиения на однородные группы) как самих алгебраических систем, так и их элементов. Исследования в данном направлении будут использовать результаты современной теории моделей и теории вероятности (0-1 законы для алгебраических систем), универсальной алгебраической геометрии (при изучении систем отношений между элементами данных), теории групп и полугрупп (при изучении вопросов преобразования данных).
2.Проект имеет сильную практическую направленность, использующую теоретические результаты участников проекта. Ожидается построение моделей искусственного интеллекта, способных обрабатывать данные, имеющие нечисленное представление. Задачи подобного типа возникают как правило при анализе длительных временных процессов, когда история объекта представляется в виде гиперграфа. Здесь планируется решение проблем, связанных с обработкой данных, связанных с действиями пользователей на онлайн-платформах, а также оптимизация и контроль длительных производственных процессов. Сюда же можно отнести применение методов машинного обучения для решения классических задач алгебры и математической логики. Планируется построить модель искусственного интеллекта, решающую уравнения над свободной группой, а также над свободными группами других многообразий.
Возможность практического использования ожидаемых результатов проекта в экономике и социальной сфере региона
Модели искусственного интеллекта (о которых говорится в проекте) могут решать широкий класс задач, в которых данные являются сложноструктурированными объектами. К таким данным относятся профили пользователей онлайн-сервисов и социальных сетей. Реализация настоящего проекта позволит обрабатывать такие типы данных более эффективно, что позволит построить точные модели анализа данных, способных разбивать пользователей (граждан региона) на социально значимые группы, выстраивать более эффективные (индивидуализированные) траектории обучения студентов, оптимизировать процессы взаимодействие граждан и органов власти, оптимизация работы транспорта и эффективность дорожной сети. Кроме того, в проекте запланировано построение нейронных сетей, осуществляющих эффективную защиту информации и препятствующие несанкционорованному вмешательству в их работу - данная тематика полностью относится к вопросам кибербезопасности и защите личных данных.
ОТЧЁТНЫЕ МАТЕРИАЛЫ
Аннотация результатов, полученных в 2022 году
Доказано, что при условии P =/= NP и P=BPP, для проблемы кластеризации графов
с ограничениями на число кластеров не существует полиномиального сильно генерического алгоритма.
Доказано, что при условии P =/= NP и P=BPP, для проблемы разбиения графа на треугольники
не существует полиномиального сильно генерического алгоритма.
Доказано, что проблема равенства генерически разрешима в конечно
порожденных полугруппах S, для которых существует такая
конгруэнция \theta, что полугруппа S/\theta является бесконечным
финитно аппроксимируемым моноидом с сокращениями и с разрешимой проблемой равенства.
Для булевой алгебры формульно определимых подгрупп свободной двуступенно нильпотентной группы была вычислена размерность Вапника-Червоненкиса.
Была предложена атака на криптосистему М.Дурчевой, дающая успех для всех входов.
Исследован вопрос о равномерной определимости
подгрупп в сплетениях абелевых групп и бесконечной циклической. Доказана интерпретируемость кольца целых чисел в таких
группах а также интерпретируемость указанных групп в кольце целых чисел.
Исследована задача кластеризации на графах, в которой размеры кластеров ограничены сверху числом s.
Доказана верхняя оценка сложности кластеризации произвольного графа для случая s=3.
Предложен метод распознавания предаварийных ситуаций при работе нефтегазовых скважин с использованием обучающих выборок в 7 раз меньших по объему, чем в опубликованных ранее работах.
Были описаны все многообразия V полугрупп, в которых каждая полугруппа S является нетеровой по уравнениям
Публикации
1. Каплун В., Шевляков А. Contour pattern recognition with MNIST dataset IEEE, - (год публикации - 2023)
2. Клиновенко С.А.,Сулавко А.Е., Ложников П.С., Плетнев Л.В. Recognition of pre-emergency situations during the operation of oil wells based on convolutional neural networks and a modified Bayes classifier IEEE Explore Digital Library, - (год публикации - 2023)
3. Рыбалов А.Н. О генерической сложности ограниченной проблемы кластеризации графов Прикладная дискретная математика, № 57. C. 91–97. (год публикации - 2022) https://doi.org/10.17223/20710410/57/6
4. Рыбалов А.Н. О генерической сложности проблемы разбиения графа на треугольники Прикладная дискретная математика, № 58. C. 105-111. (год публикации - 2022)
5. Рыбалов А.Н. О генерической сложности проблемы равенства в некоторых полугруппах Алгебра и логика, - (год публикации - 2023)
Аннотация результатов, полученных в 2023 году
Все заявленные в плане на 2023 г. исследования по генерической сложности (Рыбалов А.Н.) выполнены в полном объеме. Сверх того, было проведено исследование генерической сложности проблемы извлечения квадратного
корня по простому модулю. Полученные результаты были опубликованы в одной статье в журнале Сибирские электронные математические известия и в двух статьях в журнале Прикладная дискретная математика.
Полученные результаты были доложены на конференциях:
1) Комбинаторно-вычислительные методы алгебры и логики (26 сентября - 30 сентября, 2023, Омск, Россия).
2) Мальцевские чтения-2023 (13 ноября - 17 ноября 2023, Новосибирск, Россия).
Исследована задача кластеризации на графах, в которой размеры кластеров ограничены сверху числом s. Разработанный в 2022 г. метод доказательства верхних оценок сложности кластеризации произвольного графа в задаче этого типа применен для случая s=4. Отмечены существенные трудности с использованием этого метода при возрастании числа s.
Были исследованы некоторые схемы, основанные на тропических циркулянтных матрицах, которые предложили в своих работах М. Дурчева, Б. Амута и Р. Перумал и Х. Хуан, Ч. Ли и Л. Дэн.
Было показано, что все они являются уязвимыми, Предложена атака, успешная в 100% экспериментов. Для этого были развиты методы ранее предложеные в работах А. Ушакова и М. Котова.
Была написана статья Buchinskiy, I., Kotov, M., and Treier, A. "Analysis of four protocols based on tropical circulant matrices" и отправлена в журнал. Результаты данной работы были доложены на конференциях:
(1) Бучинский И. М., Котов М. В., Трейер А. В. "Об атаке на протокол Диффи-Хеллмана обмена ключами, основанном на max-times и min-times алгебрах", V Всероссийская научная конференция "Омские научные чтения", 2 дек. 2022, Омск.
(2) Котов М. В., Бучинский И. М., Трейер А. В. "Тропический подход в криптографии", Омский алгебраический семинар, 15 дек. 2022, Омск.
(3) Котов М. В., Бучинский И. М., Трейер А. В. "Анализ некоторых схем с тропическими циркулянтными матрицами", Конференция "Комбинаторно-вычислительные методы алгебры и логики", 30 сент. 2023, Омск.
(4) Бучинский И. М., Котов М. В., Трейер А. В. "Анализ некоторых схем с тропическими циркулянтными матрицами", Конференция "Мальцевские чтения", 13 нояб. 2023, Новосибирск.
В работе Б.И. Плоткина был поставлен вопрос об описании многообразий, полностью состоящих из нетеровых по уравнению алгебр. В рамках настоящего проекта (Shevlyakov A.N. "Equationally Noetherian varieties of semigroups and B.Plotkin`s problem", статья опубликована) данная проблема была решена для многообразий полугрупп.
Также Б.И. Плоткиным была поставлена проблема описания нетеровых по уравнениям (соответственно: q_\omega-компактных) сплетений групп. В работе А.Н. Шевлякова "Сплетения полугрупп и проблема Б.И. Плоткина" (принята к печати в журнале "Алгебра и логика") было получено полное описание нетеровых по уравнениям сплетений полугрупп A wr B в случае, когда полугруппа В - бесконечная циклическая. Также в этой работе было доказано, что сплетение полугрупп A wr B в случае, когда полугруппа А содержит 0, а В - бесконечная циклическая, является q_\omega-компактной полугруппой. Данные результаты были доложены на канференции: "Комбинаторно-вычислительные методы алгебры и логики", 30 сент. 2023, Омск.
Публикации
1. Балджанова Р.В, Ильев А.В., Ильев В.П. О сложности кластеризации графа в задаче с ограничениями на размеры кластеров Прикладная дискретная математика, №60, С.76-84 (год публикации - 2023) https://doi.org/10.17223/20710410/60/6
2. Бучинский И., Котов М., Трейер А. An attack on a key exchange protocol based on max-times and min-times algebras Indian Journal of Pure and Applied Mathematics, Indian J Pure Appl Math (2023) (год публикации - 2023) https://doi.org/10.1007/s13226-023-00469-0
3. Ильев А.В., Ильев В.П. Bounds for the Clustering Complexity in a Graph Clustering Problem with Clusters of Bounded Size Journal of Mathematical Sciences, 275 (1), 78-84 (год публикации - 2023) https://doi.org/10.1007/s10958-023-06661-1
4. Рыбалов А.Н. Генерические полиномиальные алгоритмы для проблемы о рюкзаке в некоторых матричных полугруппах Сибирские электронные математические известия, Т. 20, № 1, С.100-109. (год публикации - 2023) https://doi.org/10.33048/semi.2023.20.009
5. Рыбалов А.Н. О генерической сложности проблемы кластеризации графов с ограничениями на размер кластеров Прикладная дискретная математика, № 60, С. 114-119. (год публикации - 2023) https://doi.org/10.17223/20710410/60/10
6. Рыбалов А.Н. О генерической сложности проблемы извлечения квадратного корня по простому модулю Прикладная дискретная математика, № 62, С. 119-123. (год публикации - 2023)
7. Шевляков А.Н. Equationally Noetherian varieties of semigroups and B.Plotkin`s problem Siberian Electronic Mathematical Reports, 20 (2), 724-734 (год публикации - 2023) https://doi.org/10.33048/semi.2023.20.042
8. Шевляков А.Н. Сплетения полугрупп и проблема Б.И. Плоткина Алгебра и логика, - (год публикации - 2024)