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

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

11.11.2020

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

Определение

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

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

H = ∑ i = 1 N p i I i = − ∑ i = 1 N p i log ⁡ p i , {displaystyle mathrm {H} =sum _{i=1}^{N}p_{i}I_{i}=-sum _{i=1}^{N}p_{i}log p_{i},}

где I i = − log ⁡ p i { extstyle I_{i}=-log p_{i}} — это собственная информация о состоянии i { extstyle i} .

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

σ I = ∑ i = 1 N p i ( I i − H ) 2 = ∑ i = 1 N p i I i 2 − H 2 {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}}}}

или

σ I = ∑ i = 1 N p i log 2 ⁡ p i − ( ∑ i = 1 N p i log ⁡ p i ) 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}}}.}

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

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

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

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

Γ i j = − log ⁡ p i → j + log ⁡ p i ← j . {displaystyle Gamma _{ij}=-log p_{i ightarrow j}+log p_{ileftarrow j}.}

Здесь p i → j { extstyle p_{i ightarrow j}} — прямая условная вероятность того, что если текущим состоянием является i {displaystyle i} , то следующим состоянием будет j {displaystyle j} и p i ← j {displaystyle p_{ileftarrow j}} — обратная условная вероятность того, что если текущим состоянием является j {displaystyle j} , то предыдущим состоянием было i {displaystyle i} . Условные вероятности связаны с вероятностью перехода p i j {displaystyle p_{ij}} , вероятностью того, что произойдёт переход из состояния i {displaystyle i} в состояние j {displaystyle j} , посредством :

p i j = p i p i → j = p j p i ← j . {displaystyle p_{ij}=p_{i}p_{i ightarrow j}=p_{j}p_{ileftarrow j}.}

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

Γ i j = − log ⁡ ( p i j / p i ) + log ⁡ ( p i j / p j ) = log ⁡ p i − log ⁡ p j = I j − I i . {displaystyle Gamma _{ij}=-log(p_{ij}/p_{i})+log(p_{ij}/p_{j})=log p_{i}-log p_{j}=I_{j}-I_{i}.}

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

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

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

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

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

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

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

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

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

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

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

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

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

p j = ∑ i = 0 7 p i p i → j {displaystyle p_{j}=sum _{i=0}^{7}p_{i}p_{i ightarrow j}} и ∑ i = 0 7 p i = 1. {displaystyle sum _{i=0}^{7}p_{i}=1.}

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

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

H = − ∑ i = 0 7 p i log 2 ⁡ p i = 2.86 {displaystyle mathrm {H} =-sum _{i=0}^{7}p_{i}log _{2}p_{i}=2.86} бита, σ I = ∑ i = 0 7 p i log 2 2 ⁡ p i − H 2 = 0.56 {displaystyle sigma _{I}={sqrt {sum _{i=0}^{7}p_{i}log _{2}^{2}p_{i}-mathrm {H} ^{2}}}=0.56} бита.

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

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

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

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

Применения

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

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