Как измерить сложность?

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

Интуитивное понимание сложности систем и процессов присуще любому человеку. Например, каждый легко может различить сложность двух рисунков, исходя из непохожести их элементов друг на друга и количества различающихся деталей. Это ключевая информация для человеческого мозга, позволяющая различать объекты примерно одинакового размера и формы. Но как оцифровать представление о сложности объекта и выразить его математически? Ведь потребность в математической характеристике, должным образом отражающей сложность иерархических неслучайных структур, существует во многих областях науки, от физики и геологии до социальных наук.

Схема идеи метода. Фото размером L × L пикселей (I) делится на блоки размером   Λ× Λ пикселей (II). Затем строится «размытое» изображение размером l × l пикселей, где l = L/Λ, которое увеличивается до исходного размера фото (III). Из блоков исходного и «размытого» изображений строятся последовательности A и B (IV) и определяется их перекрытие O. Оно и даёт оценку сложности.

Примеры оценки структурной сложности естественных (A-C) и искусственных (D-F) узоров. Соответствующие сложности равны: (A) 0.078648, (B) 0.135672, (C) 0.272874, (D) 0.107577, (E) 0.276524 и (F) 0.497536.

›

Открыть в полном размере

Исследователи из Уральского федерального университета (УрФУ, Екатеринбург) и Университетов Уппсалы (Швеция) и Радбауд (Нидерланды) разработали универсальный машинный алгоритм, с помощью которого можно количественно, одним числом, оценивать сложность любой двумерной или трехмерной системы. Они успешно применили метод для точного обнаружения фазовых переходов магнитных материалов по разной сложности начального и конечного состояний. Однако алгоритм способен также работать с изображениями, видео, музыкой, квантовыми системами, нейросетевыми алгоритмами распознавания образов и другими системами. Авторы утверждают, что предлагаемая схема намного проще и дешевле стандартных методов, основанных на вычислении корреляционных функций или с использованием методов машинного обучения. Об этом они сообщили в журнале Национальной академии наук США (PNAS). С работой можно ознакомиться на сайте arxiv.org.

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

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

Авторы проверили работу алгоритма на переходе материала из ферромагнитного состояния (магнитные моменты атомов ориентированы в одну сторону) в парамагнитное (моменты ориентированы хаотично). Метод позволяет отследить фазовый переход за очень короткий период времени — порядка нескольких наносекунд. Например, после воздействия лазером.

Кроме того, исследователи смоделировали образование скирмионов во внешнем магнитном поле. Эти мельчайшие вихревые магнитные структуры крайне интересны для развития новых технологий обработки информации. Благодаря их высокой устойчивости к внешним воздействиям скирмионы могут служить очень компактной единицей записи данных на магнитном носителе. Поэтому важно изучить, при каких условиях они формируются. Отслеживая с помощью предложенной методики сложность структуры при увеличении магнитного поля, авторам удалось «поймать» момент перехода к образованию скирмионов.

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

По материалу пресс-службы Уральского федерального университета

Автор: Алексей Понятов