Сложность (теория информации)

Информационно-флуктуационная сложность — теоретико-информационная величина, определяемая как флуктуация информации по отношению к информационной энтропии. Она выводится из флуктуаций преобладания порядка и хаоса в динамической системе и используется в различных областях знания для измерения сложности. Теория была представлена в работе Бейтса и Шепарда в 1993 году^[1].

Определение

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

Если система имеет ${\textstyle N}$ возможных состояний и вероятности состояний ${\textstyle p_{i}}$ известны, то её информационная энтропия равна

${\displaystyle \mathrm {H} =\sum _{i=1}^{N}p_{i}I_{i}=-\sum _{i=1}^{N}p_{i}\log p_{i},}$

где ${\textstyle I_{i}=-\log p_{i}}$ — это собственная информация о состоянии ${\textstyle i}$.

Информационно-флуктуационная сложность системы определяется как стандартное отклонение или флуктуация ${\textstyle I}$ от её среднего значения ${\textstyle \mathrm {H} }$:

${\displaystyle \sigma _{I}={\sqrt {\sum _{i=1}^{N}p_{i}(I_{i}-\mathrm {H} )^{2}}}={\sqrt {\sum _{i=1}^{N}p_{i}I_{i}^{2}-\mathrm {H} ^{2}}}}$

или

${\displaystyle \sigma _{I}={\sqrt {\sum _{i=1}^{N}p_{i}\log ^{2}p_{i}-{\Biggl (}\sum _{i=1}^{N}p_{i}\log p_{i}{\Biggr )}^{2}}}.}$

Флуктуация информации о состоянии ${\displaystyle \sigma _{I}}$ равна нулю в максимально неупорядоченной системе со всеми ${\displaystyle p_{i}=1/N}$; система просто имитирует случайные вводы данных. ${\displaystyle \sigma _{I}}$ также равна нулю, когда система идеально упорядочена и имеет только одно фиксированное состояние ${\displaystyle (p_{1}=1)}$, независимо от вводов. ${\displaystyle \sigma _{I}}$ не равна нулю между этими двумя крайностями, когда возможны как состояния с высокой вероятностью, так и состояния с низкой вероятностью, заполняющие пространство состояний.

Флуктуации информации обеспечивают память и вычисления

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

Получение или потеря информации, сопутствующие переходам между состояниями, могут быть связаны с собственной информацией о состоянии. Чистый информационный прирост при переходе из состояния ${\displaystyle i}$ в состояние ${\displaystyle j}$ — это информация, полученная при выходе из состояния ${\displaystyle i}$, за вычетом потери информации при входе в состояние ${\displaystyle j}$:

${\displaystyle \Gamma _{ij}=-\log p_{i\rightarrow j}+\log p_{i\leftarrow j}.}$

Здесь ${\textstyle p_{i\rightarrow j}}$ — прямая условная вероятность того, что если текущим состоянием является ${\displaystyle i}$, то следующим состоянием будет ${\displaystyle j}$ и ${\displaystyle p_{i\leftarrow j}}$ — обратная условная вероятность того, что если текущим состоянием является ${\displaystyle j}$, то предыдущим состоянием было ${\displaystyle i}$. Условные вероятности связаны с вероятностью перехода ${\displaystyle p_{ij}}$, вероятностью того, что произойдёт переход из состояния ${\displaystyle i}$ в состояние ${\displaystyle j}$, посредством :

${\displaystyle p_{ij}=p_{i}p_{i\rightarrow j}=p_{j}p_{i\leftarrow j}.}$

Устраненив условные вероятности, получим:

${\displaystyle \Gamma _{ij}=-\log(p_{ij}/p_{i})+\log(p_{ij}/p_{j})=\log p_{i}-\log p_{j}=I_{j}-I_{i}.}$

Поэтому чистая информация, полученная системой в результате перехода, зависит только от увеличения информации о состоянии от начального до конечного состояния. Можно показать, что это верно даже для нескольких последовательных переходов^[1].

Формула ${\displaystyle \Gamma =\Delta I}$ напоминает связь между силой и потенциальной энергией. ${\displaystyle I}$ подобна потенциальной энергии ${\displaystyle E_{p}}$, а ${\displaystyle \Gamma }$ — силе ${\displaystyle \mathbf {F} }$ в формуле ${\displaystyle \mathbf {F} ={\nabla E_{p}}}$. Внешняя информация «толкает» систему «вверх», в состояние с более высоким информационным потенциалом для сохранения памяти, подобно тому, как толкание тела с некоторой массой в гору, в состояние с более высоким гравитационным потенциалом, приводит к накоплению энергии. Количество накопленной энергии зависит только от конечной высоты, а не от пути в гору. Аналогично, объём хранящейся информации не зависит от пути перехода между двумя состояниями. Как только система достигает редкого состояния с высоким информационным потенциалом, она может «упасть» до обычного состояния, потеряв хранившуюся ранее информацию.

Может быть полезным вычислять стандартное отклонение ${\displaystyle \Gamma }$ от его среднего значения (которое равно нулю), а именно флуктуацию чистого информационного прироста ${\displaystyle \sigma _{\Gamma }}$^[1], однако ${\displaystyle \sigma _{I}}$ учитывает многопереходные циклы памяти в пространстве состояний и поэтому должно быть более точным индикатором вычислительной мощности системы. Более того, ${\displaystyle \sigma _{I}}$ вычислить легче, поскольку переходов может быть намного больше, чем состояний.

Хаос и порядок

Динамическая система, чувствительная к внешней информации (нестабильная), демонстрирует хаотичное поведение, тогда как система, нечувствительная к внешней информации (стабильная), демонстрирует упорядоченное поведение. Под воздействием богатого источника информации сложная система демонстрирует оба варианта поведения, колеблясь между ними в динамическом балансе. Степень флуктуации количественно измеряется с помощью ${\displaystyle \sigma _{I}}$; она фиксирует чередование преобладания хаоса и порядка в сложной системе по мере её развития во времени.

Пример: вариант элементарного клеточного автомата по правилу 110

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

Рассмотрим группу из трёх смежных ячеек клеточного автомата, которые подчиняются правилу 110: конец-центр-конец. Следующее состояние центральной ячейки зависит от её текущего состояния и конечных ячеек, как указано в правиле:

Элементарное правило клеточного автомата 110

3-ячеечная группа	1-1-1	1-1-0	1-0-1	1-0-0	0-1-1	0-1-0	0-0-1	0-0-0
следующая ячейка центра	0	1	1	0	1	1	1	0

Чтобы рассчитать информационно-флуктуационную сложность этой системы, нужно прикрепить ячейку-драйвер к каждому концу группы из 3 ячеек, чтобы обеспечить случайный внешний стимул, например, драйвер→конец-центр-конец←драйвер, с тем, чтобы правило могло применяться к двум конечным ячейкам. Затем нужно определить, каково следующее состояние для каждого возможного текущего состояния и для каждой возможной комбинации содержимого ячейки-драйвера, чтобы вычислить прямые условные вероятности.

Диаграмма состояний этой системы изображена ниже. В ней кружки представляют состояния, а стрелки — переходы между состояниями. Восемь состояний этой системы, от 1-1-1 до 0-0-0 пронумерованы восьмеричными эквивалентами 3-битного содержимого группы из 3 ячеек: от 7 до 0. Возле стрелок переходов показаны значения прямых условных вероятностей. На схеме видна изменчивость в расхождении и схождении стрелок, что соответствует изменчивости в хаосе и порядке, чувствительности и нечувствительности, приобретении и потере внешней информации от ячеек-драйверов.

Диаграмма состояний для трёх ячеек элементарного клеточного автомата по правилу 110, показывающая прямые условные вероятности переходов при случайной стимуляции.

Прямые условные вероятности определяются пропорцией возможного содержимого ячейки-драйвера, что управляет конкретным переходом. Например, для четырёх возможных комбинаций содержимого двух ячеек-драйверов состояние 7 приводит к состояниям 5, 4, 1 и 0, поэтому ${\displaystyle p_{7\rightarrow 5}}$, ${\displaystyle p_{7\rightarrow 4}}$, ${\displaystyle p_{7\rightarrow 1}}$ и ${\displaystyle p_{7\rightarrow 0}}$ составляют ¼ или 25 %. Аналогично, состояние 0 приводит к состояниям 0, 1, 0 и 1, поэтому ${\displaystyle p_{0\rightarrow 1}}$ и ${\displaystyle p_{0\rightarrow 0}}$ соответствуют ½ или 50 %. И так далее.

Вероятности состояния связаны формулой

${\displaystyle p_{j}=\sum _{i=0}^{7}p_{i}p_{i\rightarrow j}}$ и ${\displaystyle \sum _{i=0}^{7}p_{i}=1.}$

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

Правило 110 вероятностей состояния для 3-ячеечной группы автомата со случайной стимуляцией

p0	p1	p2	p3	p4	p5	p6	p7
2/17	2/17	1/34	5/34	2/17	2/17	2/17	4/17

Информационная энтропия и сложность могут быть рассчитаны из вероятностей состояния:

${\displaystyle \mathrm {H} =-\sum _{i=0}^{7}p_{i}\log _{2}p_{i}=2.86}$ бита,

${\displaystyle \sigma _{I}={\sqrt {\sum _{i=0}^{7}p_{i}\log _{2}^{2}p_{i}-\mathrm {H} ^{2}}}=0.56}$ бита.

Следует отметить, что максимально возможная энтропия для восьми состояний равна ${\displaystyle \log _{2}8=3}$ бита, что соответствует случаю, когда все восемь состояний одинаково вероятны, с вероятностями ⅛ (хаотичность). Следовательно, правило 110 имеет относительно высокую энтропию или использование состояния в 2,86 бит. Однако, это не исключает существенную флуктуацию информации о состоянии по отношению к энтропии и, следовательно, высокую величину сложности. Тогда как максимальная энтропия исключила бы сложность.

Для получения вероятностей состояния в случае, когда аналитический метод, описанный выше, неосуществим, может быть использован альтернативный метод. Он состоит в том, чтобы управлять системой через её входы (ячейки-драйверы) с помощью случайного источника в течение многих поколений и наблюдать за вероятностями состояния эмпирически. Когда это сделано с помощью компьютерного моделирования для 10 миллионов поколений, результаты выглядят следующим образом:^[2]

Информационные переменные для элементарного клеточного автомата по правилу 110

количество ячеек	3	4	5	6	7	8	9	10	11	12	13
${\displaystyle \mathrm {H} }$ (бит)	2.86	3.81	4.73	5.66	6.56	7.47	8.34	9.25	10.09	10.97	11.78
${\displaystyle \sigma _{I}}$(бит)	0.56	0.65	0.72	0.73	0.79	0.81	0.89	0.90	1.00	1.01	1.15
${\displaystyle \sigma _{I}/\mathrm {H} }$	0.20	0.17	0.15	0.13	0.12	0.11	0.11	0.10	0.10	0.09	0.10

Поскольку оба параметра, ${\displaystyle \mathrm {H} }$ и ${\displaystyle \sigma _{I}}$, возрастают с увеличением размера системы, для лучшего сравнения систем разных размеров предложено безразмерное соотношение ${\displaystyle \sigma _{I}/\mathrm {H} }$, относительная Информационно-флуктуационная сложность. Заметим, что эмпирические и аналитические результаты согласуются для 3-клеточного автомата.

В работе Бейтса и Шепарда^[1] ${\displaystyle \sigma _{I}}$ вычисляется для всех правил элементарных клеточных автоматов, и было замечено, что те из них, которые демонстрируют медленно движущиеся «планеры» и, возможно, стационарные объекты, например, правило 110, тесно связаны с большими значениями ${\displaystyle \sigma _{I}}$. Поэтому ${\displaystyle \sigma _{I}}$ можно использовать в качестве фильтра при выборе правил, способных к универсальному вычислению, что утомительно доказывать.

Применения

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

На протяжении многих лет на оригинальную статью^[1] ссылались исследователи из множества различных областей: теория сложности^[3], наука о сложных системах^[4], сложные сети^[5], хаотическая динамика^[6], запутанность для локализации многих тел^[7], инженерия окружающей среды^[8], экологическая сложность^[9], экологический анализ временных рядов^[10], устойчивость экосистем^[11], загрязнение воздуха^[12] и воды^[13], гидрологический вейвлет анализ^[14], моделирование потоков воды в почве^[15], влажность почвы^[16], сток в водосборах^[17], глубина подземных вод^[18], управление воздушным движением^[19], рисунок потоков^[20], наводнения^[21], топология^[22], экономика^[23], рыночное прогнозирование цен на металлы^[24] и электричество^[25], информатика здоровья^[26], человеческое познание^[27], кинематика походки человека^[28], неврология^[29], анализ ЭЭГ^[30], образование^[31], инвестирование^[32], фразеология языка^[33], искусственная жизнь^[34], эстетика^[35].