• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Методы и алгоритмы анализа сетевых структур

Приоритетные направления развития: компьютерно-математическое
2019
Руководитель: Калягин Валерий Александрович, Пардалос Панагиотис Ор Панайоте

Цель работы

Существенное продвижение в анализе сетевых структур на основе новых эффективных алгоритмов и технологий, разработанных на базе современных и признанных на мировом уровне подходов. Задачи работы были сгруппированы в техническом задании по четырем научным направлениям:

  1. Исследование сетевых моделей сетей случайных величин.

  2. Исследование алгоритмической сложности задач оптимизации на сетях (графах).

  3. Разработка и реализация эффективных алгоритмов решения задач оптимизации высокой вычислительной сложности.

  4. Разработка моделей и алгоритмов интеллектуального анализа данных.

Используемые методы

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

Эмпирическая база исследования

Эмпирической базой исследований сетей фондовых рынков были данные по фондовым рынкам различных стран из базы yahoo finance.  Эмпирической базой исследований по эффективным алгоритмам оптимизации были общепринятые наборы тестовых примеров (benchmarks) проверки эффективности алгоритмов (открытый доступ). Эмпирической базой исследований по моделям и алгоритмам интеллектуального анализа данных были наборы экспериментальных данных полученных из научной литературы или самостоятельно с помощью проведенных экспериментов. 

Результаты работы

В ходе выполнения технического задания были получены существенные продвижения и новые результаты по всем  научным направлениям. 

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

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

Для положительного целого числа k множество попарно вершинно непересекающихся k -путей графа G называется упаковкой по отношению к k-путям из G. Задача упаковки (k-path packing) состоит в определении упаковки максимальной мощности. Для положительного целого числа k множество вершин графа G, которое пересекает все k-пути G, называется вершинным покрытием G по отношению к k-путям. Задача о вершинном покрытии (k-path vertex cover) состоит в том, чтобы найти минимальное по мощности  вершинное покрытие G по отношению к k-путям. Для данного графа H задачи H-упаковки и H-вершинном покрытии могут быть определены аналогичным образом. Задача о вершинном покрытии  по отношению к k-путям мотивирована прикладными задачами поиска протоколов безопасности в беспроводных сенсорных сетях или задачами оптимальной расстановки видеокамер на дорогах. Известно, что задача паросочетаний (т. е. задача упаковки по отношению к 2-путям) может быть решена за полиномиальное время, но задача упаковки по отношению к графу H является NP-полной для любого графа H, имеющего связную компоненту на трех или более вершинах. В проекте получено полное описание семейства классов графов, на которых задачи k-path packing и k-path vertex cover для k >4 имеют алгоритмы полиномиального времени. Проведено масштабное исследование наследственных классов графов, в которых решения задач об упаковке и вершинном покрытии совпадают (нулевой разрыв двойственности). Это свойство позволяет построить алгоритмы полиномиального времени нахождения минимального вершинного покрытия k-путями и максимальной упаковки k-путями в таких графах. Другой задачей, исследованной в проекте, была задача целочисленной оптимизации (квази)выпуклых функций при условии квази(выпуклых) ограничений. Это направление является известным и интенсивно изучаемым обобщением задачи целочисленного линейного программирования. Известно, что классы выпуклых, строго квазивыпуклых функций, а также класс квазивыпуклых полиномов являются подклассами класса конвик функций. В проекте получены новые прорывные результаты по оптимизации конвик функций и получено решение известной задачи проверки целочисленной непустоты области, заданной любой системой выпуклых, строго квазивыпуклых функций и квазивыпуклых полиномов, алгоритмом с оракульной сложностью . Более того, показано что аналогичная задача минимизации может быть решена рандомизированным алгоритмом с ожидаемой оракульной сложностью .

По третьему направлению исследования были посвящены алгоритмам решения задач би-кластеризации в постановке задачи о производственных ячейках. Одним из важнейших результатов проекта является доказательство NP-полноты для задачи формирования ячеек (CFP) с целевой дробно-линейной функцией эффективности. В проекте предложено оригинальное полиномиальное сведение CFP с дробно-линейной функцией эффективности к CFP с линейной целевой функцией. Наряду с NP-статусом  изучены  важные связи задачи CFP с задачей бикластерного редактирования графа BGEP и задачей 3E3CP. Такие связи могут быть использованы для "переноса" известных теоретических свойств, эффективных алгоритмов, полиномиальных случаев и других особенностей хорошо изученных задач редактирования графов и точного покрытия в CFP. В проекте получены также существенные продвижения  в задачах оптимизации в условиях неопределенности и в задачах оптимизации на графах с неполной информацией и обучением.  При этом была исследована  задача минимизации отношения двух липшицевых функций на множестве общей геометрической структуры. Предложен численный алгоритм решения задачи минимизации, основанный на дихотомии и техниках липшицевой оптимизации. Для алгоритма доказана корректность, приведены условия применимости, а также особенности практической реализации.

По четвертому направлению исследований были рассмотрены современные практические задачи контроля качества голосовой записи, сокращения времени распознавания изображений с использованием глубоких нейронных сетей. Для задач обработки аудио сигналов разработана технология автоматического контроля качества голосовой записи, основанный на ее разбиении на короткие фрагменты и оценки вариативности частоты основного тона каждого фрагмента. Для ее оценки разработан новый алгоритм, в котором за счет частотной селекции вокализованных отрезков речевого сигнала c цифровым фильтром межпериодного накопления достигнуты высокое быстродействие и устойчивость к фоновому шуму от 10 дБ и выше. Технология реализована в виде компьютерной программы, которая в режиме реального времени измеряет стабильность произношения относительно среднего уровня и может использоваться для сбора голосовой биометрии в повседневных условиях. Кроме того, для систем голосового управления разработан алгоритм распознавания речи, в котором каждому входному сегменту ставится в соответствие нечеткое множество фонем. За счет применения операции вероятностной треугольной нормы для нечетких множеств, соответствующих входному фрейму и ближайшей к нему эталонной фонемы на 1,5–5% снижается вероятность ошибочного распознавания по сравнению с известными аналогами. Так как для вычисления степеней принадлежности нечетких множеств в разработанном алгоритме используются спектральные оценки максимума энтропии с использованием авторегрессионной модели речевого сигнала, рассмотрена задача оценивания порядка линейной авторегрессии. Дано строгое теоретическое обоснование критерия с последовательным выбором порядка при регулируемом уровне значимости. 

Идеи последовательного анализа также были использованы для понижения времени распознавания изображений, описываемыми признаками высокой размерности, в 1,5-10 раз по сравнению с обычными классификаторами. Предложен новый иерархический алгоритм, который отличается от известных подходов тем, что для последовательного анализа более детализированного уровня описания (с большей размерностью вектора признаков) ищет ближайших соседей только среди эталонных изображений наиболее надежных классов, выделенных на предыдущем уровне. При этом на каждом этапе сопоставляются главные компоненты, число которых выбирается, исходя из фиксированной доли объясненной дисперсии. Кроме того, рассмотрены методы сжатия рекуррентных LSTM-сетей для языкового моделирования с акцентом на большую размерность выходного пространства (большое число слов в словаре). Наконец, еще один способ повышения вычислительной эффективности связан с применением единой нейросетевой модели для одновременного решения сразу нескольких близких задач. Показано, что даже модель, предназначенная для мобильных приложений, может достичь качества кластеризации лиц, сравнимого с аналогами, а пол и возраст человека с ее помощью можно распознать по фотографии точнее, чем свободно распространяемые специализированные глубокие нейронные сети.

Степень внедрения, рекомендации по внедрению или итоги внедрения результатов НИР

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

Публикации по проекту:


Savchenko V. V., Savchenko A. Method for Measuring the Indicator of Acoustic Quality of Audio Recordings Prepared for Registration and Processing in the Unified Biometric System / Пер. с рус. // Measurement Techniques. 2020. Vol. 62. No. 12. P. 1071-1078. doi
Sokolova A., Savchenko A. Fast Nearest-Neighbor Classifier based on Sequential Analysis of Principal Components, in: Analysis of Images, Social Networks and Texts. 8th International Conference, AIST 2019, Lecture Notes in Computer Science, Revised Selected Papers / Ed. by W. M. van der Aalst, V. Batagelj, D. I. Ignatov, M. Y. Khachay, V. Kuskova, A. Kutuzov, S. Kuznetsov, I. A. Lomazova, N. Loukachevitch, A. Napoli, P. M. Pardalos, M. Pelillo, A. Savchenko, E. Tutubalina. Vol. 11832. Cham : Springer, 2019. doi Ch. 7. P. 73-80. doi
Mikhail V. Batsyn, Ekaterina K. Batsyna, Ilya S. Bychkov. NP-completeness of cell formation problem with grouping efficacy objective // International Journal of Production Research. 2020. No. DOI: 10.1080/00207543.2019.1668072. P. 1-14. doi
Savchenko A. Probabilistic Neural Network With Complex Exponential Activation Functions in Image Recognition // IEEE Transactions on Neural Networks and Learning Systems. 2020. Vol. 31. No. 2. P. 651-660. doi
Chirkov A. Y., Gribanov D., Malyshev D., Pardalos P. M., Veselov S. I., Zolotykh N. On the complexity of quasiconvex integer minimization problem // Journal of Global Optimization. 2019. Vol. 73. No. 4. P. 761-788. doi
Koldanov P. Statistics of individual tests for market graph identification in market network // Advances in Computer Science Research. 2019. P. 50-55. doi
Sergey S. Ketkov, Oleg A. Prokopyev. On Greedy and Strategic Evaders in Sequential Interdiction Settings with Incomplete Information // Omega. 2020. Vol. 92. P. 102161. doi
Granata I., Guarracino M. R., Kalyagin V. A., Maddalena L., Manipur I., Pardalos P. M. Supervised Classification of Metabolic Networks, in: Proceedings 2018 IEEE International Conference on Bioinformatics and Biomedicine. Madrid : IEEE, 2018. P. 2688-2693. doi
Granata I., Guarracino M. R., Kalyagin V. A., Maddalena L., Manipur I., Pardalos P. M. Model simplification for supervised classification of metabolic networks // Annals of Mathematics and Artificial Intelligence. 2019. P. 1-14. doi
Kalyagin V. A., Slashchinin S. Impact of error in parameter estimations on large scale portfolio optimization // Springer Optimization and Its Applications. 2019. Vol. 145. P. 151-184. doi
Gribanov D., Malyshev D. Integer Conic Function Minimization Based on the Comparison Oracle, in: Mathematical Optimization Theory and Operations Research, 18th International Conference, MOTOR 2019 Ekaterinburg, Russia, July 8–12, 2019 / Ed. by М. Ю. Хачай, Ю. А. Кочетов, P. M. Pardalos. Vol. 11548. Springer, 2019. P. 218-231. doi
Savchenko L.V., Savchenko A.V. Fuzzy Phonetic Encoding of Speech Signals in Voice Processing Systems / Пер. с рус. // Journal of Communications Technology and Electronics. 2019. Vol. 64. No. 3. P. 238-244. doi
Grachev A., Ignatov D. I., Savchenko A. Compression of recurrent neural networks for efficient language modeling // Applied Soft Computing Journal. 2019. Vol. 79. P. 354-362. doi
Savchenko A., Savchenko V. V. A Method for Measuring the Pitch Frequency of Speech Signals for the Systems of Acoustic Speech Analysis / Пер. с рус. // Measurement Techniques. 2019. Vol. 62. No. 3. P. 282-288. doi
Malyshev D., Mokeev D. B. Konig graphs with respect to the 4-path and Its spanning supergraphs / Пер. с рус. // Journal of Applied and Industrial Mathematics. 2019. Vol. 13. No. 1. P. 85-92. doi
Anton Kocheturov, Pardalos P. M., Karakitsiou A. Massive datasets and machine learning for computational biomedicine: trends and challenges // Annals of Operations Research. 2019. Vol. 276. No. 1-2. P. 5-34. doi
Zare M. H., Borrero J., Zeng B., Prokopyev O. A Note on Linearized Reformulations for a Class of Bilevel Linear Integer Problems // Annals of Operations Research. 2019. Vol. 272. No. 1-2. P. 99-117. doi
Pardalos P. M., Souravlias D., Kotsireas I. S., Parsopoulos K. E. Parallel algorithm portfolios with performance forecasting // Optimization Methods and Software. 2019. Vol. 34. No. 6. P. 1231-1250. doi

См. также

Ключевые слова