Алгебро-логические методы представления данных в задачах машинного обучения, защиты информации и оптимизации

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

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

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

Номер проекта 22-11-20019

НазваниеАлгебро-логические методы представления данных в задачах машинного обучения, защиты информации и оптимизации

Руководитель Шевляков Артём Николаевич, Доктор физико-математических наук

Организация финансирования, регион Федеральное государственное бюджетное учреждение науки Институт математики им. С.Л. Соболева Сибирского отделения Российской академии наук , Омская обл

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

Область знания, основной код классификатора 01 - Математика, информатика и науки о системах; 01-102 - Алгебра

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

Код ГРНТИ27.17.00

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

Аннотация
Проект направлен на применение идей алгебры и теории моделей для построения алгоритмов машинного обучения и искусственного интеллекта. Выбор тематики обусловлен как огромным интересом к проблемам искусственного интеллекта как в науке, так и в экономике и обществе, так и наличием здесь открытых теоретических проблем. Основной проблемой теории искусственного интеллекта является необходимость доказательства корректной работы модели искусственного интеллекта, ее устойчивость в нестандартных ситуациях, и защита от несанкционированного использования. Данные задачи допускают множественные формализации (на языке теории вероятности, математической статистики, теории оптимизации и других разделов математики). В настоящем проекты мы предлагаем применить к изучению вопросов искусственного интеллекта подход, основанный на идеях алгебры и теории моделей. Поясним основные преимущества такого подхода. Теория моделей является важнейшей частью современной математической логики и (в общих чертах) изучает определимость множеств с помощью логических формул. Логическая формула - это наиболее естественный объект для моделирования рассуждений и вывода, и поэтому ее использование в анализе моделей машинного обучения и искусственного интеллекта весьма целесообразно и перспективно. Применение идей алгебры в анализе моделей машинного обучения обусловлено важностью нечисленных представлений данных. Дело в том, что классические модели искусственного интеллекта (метрические алгоритмы, нейронные сети, байесовские модели) требуют представления обрабатываемых ими данных в виде числовых векторов (матриц). Такой подход хорошо работает, когда анализируемые объекты без потери информации могут быть представлены числовыми векторами (матрицами). Например, картинки (как массивы пикселей) легко могут быть представлены в виде векторов (матриц), и поэтому принципиальных проблем при обработке картинок современными моделями искусственного интеллекта, как правило, не возникает. С другой стороны, для некоторых объектов сложной природы (графы, гиперграфы и другие алгебраические системы предикатного языка) идеальных методов численного представления не существует. Однако важность изучения подобных алгебраических систем в анализе данных достаточна велика. Дело в том, что многие процессы могут быть смоделированы с помощью переходов между вершинами гиперграфа, а также сложные системы отношений между элементами множества могут моделироваться с помощью алгебраических систем предикатного языка. Всё сказанное выше определяет тематику данного проекта. Планируется изучение нечисленных представлений данных и описание данных (и кластеров данных) с помощью логических формул. Теоретические исследования нечисленных представлений данных позволят реализовать новые модели искусственного интеллекта. В проекте запланировано создание и тренировка моделей искусственного интеллекта (в том числе и нейронных сетей различных классов), решающих как чисто научные, так и практические задачи в области символьных вычислений, кибербезопасности, кластеризации пользователей онлайн-сервисов. Кроме того, в проекте будет уделено внимание теории вычислимости и теоории сложности для моделей искусственного интеллекта. Это связано с тем, что классические определения алгоритма и его временной сложности не всегда удобны, когда речь идет о моделях искусственного интеллекта. В работе модели искусственного интеллекта допускается определенный процент ошибочно принятых решений. Следовательно, алгоритм (лежащий в основе такой модели) должен работать корректно для "почти всех" . Это делает актуальным изучение в проекте альтернативных видов сложности: сложность в среднем и генерической сложности.

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

Публикации

1. Рыбалов А.Н. О генерической сложности проблемы равенства в некоторых полугруппах Алгебра и логика (год публикации - 2023)

2. Рыбалов А.Н. О генерической сложности ограниченной проблемы кластеризации графов Прикладная дискретная математика, № 57. C. 91–97. (год публикации - 2022)
10.17223/20710410/57/6

3. Рыбалов А.Н. О генерической сложности проблемы разбиения графа на треугольники Прикладная дискретная математика, № 58. C. 105-111. (год публикации - 2022)

4. Каплун В., Шевляков А. Contour pattern recognition with MNIST dataset IEEE (год публикации - 2023)

5. Клиновенко С.А.,Сулавко А.Е., Ложников П.С., Плетнев Л.В. 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)

6. Рыбалов А.Н. О генерической сложности проблемы извлечения квадратного корня по простому модулю Прикладная дискретная математика, № 62, С. 119-123. (год публикации - 2023)

7. Рыбалов А.Н. Генерические полиномиальные алгоритмы для проблемы о рюкзаке в некоторых матричных полугруппах Сибирские электронные математические известия, Т. 20, № 1, С.100-109. (год публикации - 2023)
10.33048/semi.2023.20.009

8. Рыбалов А.Н. О генерической сложности проблемы кластеризации графов с ограничениями на размер кластеров Прикладная дискретная математика, № 60, С. 114-119. (год публикации - 2023)
10.17223/20710410/60/10

9. Шевляков А.Н. Equationally Noetherian varieties of semigroups and B.Plotkin`s problem Siberian Electronic Mathematical Reports, 20 (2), 724-734 (год публикации - 2023)
10.33048/semi.2023.20.042

10. Шевляков А.Н. Сплетения полугрупп и проблема Б.И. Плоткина Алгебра и логика (год публикации - 2024)

11. Бучинский И., Котов М., Трейер А. 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)
10.1007/s13226-023-00469-0

12. Балджанова Р.В, Ильев А.В., Ильев В.П. О сложности кластеризации графа в задаче с ограничениями на размеры кластеров Прикладная дискретная математика, №60, С.76-84 (год публикации - 2023)
10.17223/20710410/60/6

13. Ильев А.В., Ильев В.П. Bounds for the Clustering Complexity in a Graph Clustering Problem with Clusters of Bounded Size Journal of Mathematical Sciences, 275 (1), 78-84 (год публикации - 2023)
10.1007/s10958-023-06661-1

14. Рыбалов А.Н. О генерической сложности проблемы вычисления функции Эйлера Прикладная дискретная математика, № 65. C. 110-117 (год публикации - 2024)
10.17223/20710410/65/6

15. Бучинский И.М., Котов М.В., Трейер А.В. Analysis of four protocols based on tropical circulant matrices Indian Journal of Pure and Applied Mathematics (год публикации - 2025)

16. Рыбалов А.Н. О генерической сложности проблемы дискретного логарифма в последовательностях Люка Прикладная дискретная математика, № 66. C. 116–122 (год публикации - 2024)
10.17223/20710410/66/10

17. Ильев А.В., Ильев В.П. Clustering Complexity and an Approximation Algorithm for a Version of the Cluster Editing Problem Lecture Notes in Computer Science, Vol. 14766, pp. 103–115. (год публикации - 2024)
10.1007/978-3-031-62792-7_7

18. Рыбалов А.Н. О генерической сложности диофантовой проблемы в параметрическом виде Алгебра и логика (год публикации - 2025)

Публикации

4. Каплун В., Шевляков А. Contour pattern recognition with MNIST dataset IEEE (год публикации - 2023)

10. Шевляков А.Н. Сплетения полугрупп и проблема Б.И. Плоткина Алгебра и логика (год публикации - 2024)

Аннотация результатов, полученных в 2024 году
1. Доказано, что, для проблемы дискретного логарифма в группах последовательностей Люка по целому модулю не существует генерического полиномиального алгоритма, при условии при условии ее трудноразрешимости в худшем случае и P=BPP. Последовательности Люка - это последовательности натуральных чисел, задаваемые некоторыми линейными рекуррентными соотношениями, которые могут быть реализованы как целые точки на кривых второго порядка. Если при этом рассматривать элементы по некоторому модулю, то возникает конечная группа с операцией сложения. В проекте изучены генерические свойства таких групп (то есть свойства, выполненные для почти всех элементов группы), в частности трудность нахождения дискретного логарифма для "почти всех" элементов группы, построенной по последовательности Люка. Эта проблема была использована в 1990-е годы новозеландским криптографом П. Смитом для создания аналога классического протокола Диффи-Хеллмана, в котором возведение в степень по целому модулю заменяется на операцию сложения элементов последовательности Люка. Таким образом, этот результат обосновывает применение данной алгоритмической проблемы в криптографии с открытым ключом, где важна генерическая трудноразрешимость, то есть трудноразрешимость для почти всех входов. 2. Доказано, что, для проблемы вычисления функции Эйлера не существует сильно генерического полиномиального алгоритма, при условии при условии ее трудноразрешимости в худшем случае и P=BPP. Классическая функция Эйлера ф(x), определяющая число натуральных чисел, меньших x и взаимно простых с x, играет важную роль в современной криптографии. Для ее вычисления до сих пор неизвестно эффективных (полиномиальных) алгоритмов. Этот факт, среди прочего, используется для обоснования стойкости знаменитого алгоритм шифрования с открытым ключом RSA. Проблема вычисления функции Эйлера тесно связана с известной проблемой факторизации (разложения на множители) целых чисел: если бы существовал полиномиальный алгоритм для проблемы факторизации, то его можно было бы использовать для эффективного вычисления функции Эйлера. В современной криптографии интересны такие алгоритмические проблемы, которые, являясь (гипотетически) трудными в классическом смысле, остаются трудными и в генерическом смысле, т.е. для почти всех входов. Это объясняется тем, что при случайной генерации ключей в криптографическом алгоритме происходит генерация входа некоторой трудной алгоритмической проблемы, лежащей в основе криптостойкости алгоритма. Если проблема будет легкоразрешимой почти всегда, то для почти всех таких входов ее можно будет быстро решить и ключи почти всегда будут нестойкими. Поэтому проблема должна быть трудной для почти всех входов. Для сильно генерического полиномиального алгоритма нет эффективного метода случайной генерации входов, на которых этот алгоритм не может решить проблему. Таким образом, полученный результат обосновывает применение проблемы вычисления функции Эйлера в криптографии с открытым ключом. 3. Изучена генерическая сложность диофантовой проблемы в параметрическом виде. Из отрицательного решения десятой проблемы Гильберта следует, что существуют многочлены p(a, x_1,…, x_n) с целыми коэффициентами такие, что нет алгоритма, который по любому натуральному числу a определял бы, разрешимо ли в целых числах уравнение p(a, x_1, …, x_n) = 0. Профессор В.А.Романьков поставил вопрос о генерической разрешимости такой диофантовой проблемы в параметрическом виде. Генерические алгоритмы решают проблемы на множествах почти всех входов, выдавая неопределенный ответ для остальных редких входов. Доказано, что для некоторых многочленов p данная проблема, будучи неразрешимой в классическом смысле, является генерически разрешимой, а для других остается и генерически неразрешимой. Также построен многочлен p, для которого эта проблема разрешима, но не является генерически разрешимой за полиномиальное время. 4. В 2024 году совместно с А. Понмахешкумаром (A. Ponmaheshkumar) и Р. Перумалом (R. Perumal) были исследованы системы квадратичных полиномиальных уравнений специального вида (SUM)_{i, j} a_{kij} (x) x_i (x) y_j = b_k, k = 1,..., m, над цифровыми матричными полукольцами, где (SUM) -- суммирование в этом полукольце, а (x) -- умножение. Доказана теорема о полиномиальной сводимости проблемы решения системы уравнений такого вида к проблеме 3-SAT. Данные полукольца являются структурами похожими на тропические полукольца, и в настоящий момент исследуется их применимость в криптографии. Исследован протокол обмена ключами, основанный на цифровых матричных полукольцах, предложенный в работе Хуанга и др. в 2024 г. Показана ограниченная применимость метода ветвей и границ в этом случае. Проведены компьютерные эксперименты. Результаты оформлены в виде статьи A. Ponmaheshkumar, M. Kotov, R. Perumal, "Cryptanalysis of a key exchange protocol based on a digital semiring", которая отправлена в журнал "Communications in Algebra". 5. В этом году для задачи кластеризации на графах, в которой размеры кластеров ограничены сверху числом s, доказана достижимая верхняя оценка сложности кластеризации произвольного n-вершинного графа G для случая s=5 при n>5. С ее помощью гипотеза об оценке сложности кластеризации в общем случае была опровергнута на примере полного двудольного графа K_33, так что на настоящий момент полученная оценка является лучшей оценкой сложности кластеризации и для любого s>5. Кроме того, поскольку при использовании примененного метода доказательства оценок сложности кластеризации в задачах этого типа неизбежны объективные трудности с ростом s, то возникает естественный вопрос об усовершенствовании данного метода для случаев больших s. Ответ на него подразумевает существенное усложнение проблемы поиска таких оценок и предполагает наличие отдельной небольшой группы исследователей.

Публикации

4. Каплун В., Шевляков А. Contour pattern recognition with MNIST dataset IEEE (год публикации - 2023)

10. Шевляков А.Н. Сплетения полугрупп и проблема Б.И. Плоткина Алгебра и логика (год публикации - 2024)