WikiDer > Сложность флуктуации информации - Википедия

Сложность флуктуации информации является теоретико-информационный количество определяется как колебание информации о энтропия. Он является производным от флуктуаций преобладания порядка и хаоса в динамической системе и использовался как мера сложность во многих различных областях. Он был представлен в статье Бейтса и Шепарда в 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_ {я},}$

куда ${ 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_ {я rightarrow j}}$ это условная вероятность вперед что если нынешнее состояние ${ displaystyle i}$ то следующее состояние ${ displaystyle j}$ и ${ displaystyle p_ {я 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 Phi}$ и ${ displaystyle Gamma}$ как сила ${ displaystyle mathbf {F}}$ в ${ Displaystyle mathbf {F} = { nabla Phi}}$. Внешняя информация «подталкивает» систему «вверх» к состоянию с более высоким информационным потенциалом для обеспечения хранения в памяти, подобно тому, как толкает массу вверх в состояние с более высоким гравитационным потенциалом, запасающим энергию. Количество накопленной энергии зависит только от конечной высоты, а не от пути в гору. Точно так же объем хранимой информации не зависит от пути перехода между двумя состояниями в пространстве состояний. Когда система достигает редкого состояния с высоким информационным потенциалом, она может «упасть» в более обычное состояние, теряя ранее сохраненную информацию.

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

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

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

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

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

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

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

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

Диаграмма состояний с 3 ячейками для элементарного клеточного автомата с правилом 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}}$ составляют 1/4 или 25% каждая. Аналогично, состояние 0 приводит к состояниям 0, 1, 0 и 1, поэтому ${ displaystyle p_ {0 rightarrow 1}}$и ${ displaystyle p_ {0 rightarrow 0}}$составляют 1/2 или 50% каждая. И так далее.

Вероятности состояний связаны соотношением

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

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

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

${ displaystyle mathrm {H} = - sum _ {i = 0} ^ {7} p_ {i} log _ {2} p_ {i} = 2,86 { text {bits}},}$

${ displaystyle sigma _ {I} = { sqrt { sum _ {i = 0} ^ {7} p_ {i} log _ {2} ^ {2} p_ {i} - mathrm {H} ^ {2}}} = 0,56 { text {bits}}.}$

Обратите внимание, что максимально возможная энтропия для восьми состояний равна ${ displaystyle log _ {2} 8 = 3 { text {bits}},}$ что было бы так, если бы все восемь состояний были равновероятными с вероятностями 1/8 (случайность). Таким образом, правило 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]

Рекомендации