Русская Википедия:Сложность (теория информации)

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

Определение

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

Если система имеет <math display="inline">N</math> возможных состояний и вероятности состояний <math display="inline">p_i</math> известны, то её информационная энтропия равна

<math>\Eta = \sum_{i=1}^N p_i I_i = - \sum_{i=1}^N p_i \log p_i,</math>

где <math display="inline">I_i = -\log p_i</math> — это собственная информация о состоянии <math display="inline">i</math>.

Информационно-флуктуационная сложность системы определяется как стандартное отклонение или флуктуация <math display="inline">I</math> от её среднего значения <math display="inline">\Eta</math>:

<math>\sigma_I = \sqrt{\sum_{i=1}^N p_i(I_i - \Eta)^2} = \sqrt{\sum_{i=1}^N p_iI_i^2 - \Eta^2}</math>

или

<math>\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}.</math>

Флуктуация информации о состоянии <math>\sigma_I</math> равна нулю в максимально неупорядоченной системе со всеми <math>p_i = 1/N</math>; система просто имитирует случайные вводы данных. <math>\sigma_I</math> также равна нулю, когда система идеально упорядочена и имеет только одно фиксированное состояние <math>(p_1 = 1)</math>, независимо от вводов. <math>\sigma_I</math> не равна нулю между этими двумя крайностями, когда возможны как состояния с высокой вероятностью, так и состояния с низкой вероятностью, заполняющие пространство состояний.

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

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

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

<math>\Gamma_{ij} = -\log p_{i \rightarrow j} + \log p_{i \leftarrow j}.</math>

Здесь <math display="inline">p_{i \rightarrow j}</math> — прямая условная вероятность того, что если текущим состоянием является <math>i</math>, то следующим состоянием будет <math>j</math> и <math>p_{i \leftarrow j}</math> — обратная условная вероятность того, что если текущим состоянием является <math>j</math>, то предыдущим состоянием было <math>i</math>. Условные вероятности связаны с вероятностью перехода <math>p_{ij}</math>, вероятностью того, что произойдёт переход из состояния <math>i</math> в состояние <math>j</math>, посредством :

<math>p_{ij} = p_i p_{i \rightarrow j} = p_j p_{i \leftarrow j}.</math>

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

<math>\Gamma_{ij} = -\log (p_{ij}/p_i) + \log (p_{ij}/p_j) = \log p_i - \log p_j = I_j - I_i.</math>

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

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

Может быть полезным вычислять стандартное отклонение <math>\Gamma</math> от его среднего значения (которое равно нулю), а именно флуктуацию чистого информационного прироста <math>\sigma_\Gamma</math>, однако <math>\sigma_I</math> учитывает многопереходные циклы памяти в пространстве состояний и поэтому должно быть более точным индикатором вычислительной мощности системы. Более того, <math>\sigma_I</math> вычислить легче, поскольку переходов может быть намного больше, чем состояний.

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

Динамическая система, чувствительная к внешней информации (нестабильная), демонстрирует хаотичное поведение, тогда как система, нечувствительная к внешней информации (стабильная), демонстрирует упорядоченное поведение. Под воздействием богатого источника информации сложная система демонстрирует оба варианта поведения, колеблясь между ними в динамическом балансе. Степень флуктуации количественно измеряется с помощью <math>\sigma_I</math>; она фиксирует чередование преобладания хаоса и порядка в сложной системе по мере её развития во времени.

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

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

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

Элементарное правило клеточного автомата 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 ячеек, чтобы обеспечить случайный внешний стимул, например, Шаблон:Inline block, с тем, чтобы правило могло применяться к двум конечным ячейкам. Затем нужно определить, каково следующее состояние для каждого возможного текущего состояния и для каждой возможной комбинации содержимого ячейки-драйвера, чтобы вычислить прямые условные вероятности.

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

Файл:State diagram for rule 110 with transition probabilities.png

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

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

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

Шаблон:Inline block

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

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

p0	p1	p2	p3	p4	p5	p6	p7
Шаблон:Sfrac	Шаблон:Sfrac	Шаблон:Sfrac	Шаблон:Sfrac	Шаблон:Sfrac	Шаблон:Sfrac	Шаблон:Sfrac	Шаблон:Sfrac

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

Шаблон:Inline block

Шаблон:Inline block

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

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

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

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

Поскольку оба параметра, <math>\Eta</math> и <math>\sigma_I</math>, возрастают с увеличением размера системы, для лучшего сравнения систем разных размеров предложено безразмерное соотношение <math>\sigma_I/\Eta</math>, относительная Информационно-флуктуационная сложность. Заметим, что эмпирические и аналитические результаты согласуются для 3-клеточного автомата.

В работе Бейтса и Шепарда <math>\sigma_I</math> вычисляется для всех правил элементарных клеточных автоматов, и было замечено, что те из них, которые демонстрируют медленно движущиеся «планеры» и, возможно, стационарные объекты, например, правило 110, тесно связаны с большими значениями <math>\sigma_I</math>. Поэтому <math>\sigma_I</math> можно использовать в качестве фильтра при выборе правил, способных к универсальному вычислению, что утомительно доказывать.

Применения

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

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