Сложность флуктуации информации - Information fluctuation complexity

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

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

Диаграмма состояний с 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.}$

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

п0	п1	п2	п3	п4	п5	п6	п7
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{\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]

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

1. Бейтс, Джон Э .; Шепард, Харви К. (1993-01-18). «Измерение сложности с использованием колебаний информации». Письма о физике A. 172 (6): 416–425. Дои:10.1016 / 0375-9601 (93) 90232-О. ISSN  0375-9601.
2. Бейтс, Джон Э. (30 марта 2020 г.). «Измерение сложности с использованием флуктуации информации: учебное пособие». Исследовательские ворота.
3. Атманспахер, Харальд (сентябрь 1997 г.). «Декартово разрезание, разрез Гейзенберга и концепция сложности». Мировые фьючерсы. 49 (3–4): 333–355. Дои:10.1080/02604027.1997.9972639. ISSN  0260-4027.
4. Shalizi, Cosma Rohilla (2006), Deisboeck, Thomas S .; Креш, Дж. Яша (ред.), "Методы и методы изучения сложных систем: обзор", Комплексная системная наука в биомедицине, Topics in Biomedical Engineering International Book Series, Springer, США, стр. 33–114, arXiv:nlin / 0307015, Дои:10.1007/978-0-387-33532-2_2, ISBN  978-0-387-33532-2, S2CID  11972113
5. Вакербауэр, Ренате (1 ноября 1995 г.). «Шумовая стабилизация системы Лоренца». Физический обзор E. 52 (5): 4745–4749. Дои:10.1103 / PhysRevE.52.4745. PMID  9963970.
6. Сингх, Виджай П. (10 января 2013 г.). Теория энтропии и ее применение в экологии и гидротехнике. Джон Вили и сыновья. ISBN  978-1-118-42860-3.
7. Паррот, Лаэль (01.11.2010). «Измерение экологической сложности». Экологические показатели. 10 (6): 1069–1076. Дои:10.1016 / j.ecolind.2010.03.014. ISSN  1470–160X.
8. Ланге, Хольгер (2006), «Анализ временных рядов в экологии», eLS, Американское онкологическое общество, Дои:10.1038 / npg.els.0003276, ISBN  978-0-470-01590-2
9. Ван, Чаоцзюнь; Чжао, Хунжуй (2019-04-18). «Анализ данных временных рядов дистанционного зондирования для обеспечения устойчивости экосистемы: использование временной информационной энтропии». Международный журнал дистанционного зондирования. 40 (8): 2880–2894. Дои:10.1080/01431161.2018.1533661. ISSN  0143-1161. S2CID  135003743.
10. Клемм, Отто; Ланге, Хольгер (1999-12-01). «Тенденции загрязнения воздуха в горах Фихтельгебирге, Бавария». Экология и исследования загрязнения окружающей среды. 6 (4): 193–199. Дои:10.1007 / BF02987325. ISSN  1614-7499. PMID  19005662. S2CID  35043.
11. Ван, Канг; Линь, Чжунбин (2018). «Характеристика неточечных источников загрязнения реки в различных пространственных масштабах». Журнал "Вода и окружающая среда". 32 (3): 453–465. Дои:10.1111 / wej.12345. ISSN  1747-6593.
12. Лабат, Дэвид (25 ноября 2005 г.). «Последние достижения в вейвлет-анализе: Часть 1. Обзор концепций». Журнал гидрологии. 314 (1): 275–288. Дои:10.1016 / j.jhydrol.2005.04.003. ISSN  0022-1694.
13. Пачепский, Яков; Губер, Андрей; Жак, Дидерик; Симунек, Иржи; Van Genuchten, Marthinus Th .; Николсон, Томас; Кэди, Ральф (01.10.2006). «Информативность и сложность моделирования потоков почвенных вод». Геодермия. Фрактальная геометрия применительно к почве и связанным с ней иерархическим системам - фракталы, сложность и неоднородность. 134 (3): 253–266. Дои:10.1016 / j.geoderma.2006.03.003. ISSN  0016-7061.
14. Kumar, Sujay V .; Дирмейер, Пол А .; Peters-Lidard, Christa D .; Биндлиш, Раджат; Болтен, Джон (01.01.2018). «Информационно-теоретическая оценка спутникового определения влажности почвы». Дистанционное зондирование окружающей среды. 204: 392–400. Дои:10.1016 / j.rse.2017.10.016. HDL:2060/20180003069. ISSN  0034-4257. ЧВК  7340154. PMID  32636571.
15. Хаус, Майкл; Ланге, Хольгер (2008). «Классификация стока в верховьях водосборов: физическая проблема?». География Компас. 2 (1): 235–254. Дои:10.1111 / j.1749-8198.2007.00075.x. ISSN  1749-8198.
16. Лю, Мэн; Лю, Донг; Лю, Ле (01.09.2013). «Исследование сложности региональных рядов глубин подземных вод на основе многомасштабной энтропии: тематическое исследование бюро филиала Цзянсаньцзян в Китае». Экологические науки о Земле. 70 (1): 353–361. Дои:10.1007 / s12665-012-2132-у. ISSN  1866-6299. S2CID  128958458.
17. Син, Цзин; Мэннинг, Кэрол А. (апрель 2005 г.). «Сложность и автоматизация дисплеев управления воздушным движением: обзор и анализ литературы».
18. Ван, Канг; Ли, Ли (ноябрь 2008 г.). «Характеризация неоднородных структур потоков с использованием информационных измерений». 2008 Первая международная конференция по интеллектуальным сетям и интеллектуальным системам: 654–657. Дои:10.1109 / ICINIS.2008.110. S2CID  8867649.
19. Джавахери Джавид, Мохаммед Али; Альгамди, Ваджди; Циммер, Роберт; аль-Рифаи, Мохаммад Маджид (2016), Би, Яксин; Капур, Суприя; Бхатия, Рахул (ред.), «Сравнительный анализ обнаружения симметрий в тороидальной топологии» (PDF), Интеллектуальные системы и приложения: расширенные и избранные результаты конференции SAI по интеллектуальным системам (IntelliSys) 2015 г., Исследования в области вычислительного интеллекта, Springer International Publishing, стр. 323–344, Дои:10.1007/978-3-319-33386-1_16, ISBN  978-3-319-33386-1
20. Он, Кайджиан; Лу, Синцзин; Цзоу, Инчао; Кеунг Лай, Кин (01.09.2015). «Прогнозирование цен на металлы с использованием многомасштабной методологии на основе кривой». Политика ресурсов. 45: 144–150. Дои:10.1016 / j.resourpol.2015.03.011. ISSN  0301-4207.
21. Он, Кайджиан; Сюй, Ян; Цзоу, Инчао; Тан, Лин (2015-05-01). «Прогнозы цен на электроэнергию с использованием подхода Curvelet, основанного на шумоподавлении». Physica A: Статистическая механика и ее приложения. 425: 1–9. Дои:10.1016 / j.physa.2015.01.012. ISSN  0378-4371.
22. Ши Сюцзянь; Сунь Чжицян; Ли Лонг; Се Хунвэй (2009). "Анализ когнитивной сложности человека в транспортных системах". Логистика. Труды: 4361–4368. Дои:10.1061/40996(330)637. ISBN  9780784409961.
23. Чжан, Шутао; Цянь, Цзиньву; Шен, Линьюн; Ву, Си; Ху, Сяову (октябрь 2015 г.). «Анализ сложности походки и частотного содержания пациентов с болезнью Паркинсона». 2015 Международный симпозиум по биоэлектронике и биоинформатике (ISBB): 87–90. Дои:10.1109 / ISBB.2015.7344930. ISBN  978-1-4673-6609-0. S2CID  2891655.
24. Ван, Джисон; Но, Гю-Чжон; Чой, Бён-Мун; Ку, Сын Ву; Джу, Пангю; Юнг, Ву-Сон; Ким, Сынхван; Ли, Хонсоо (13.07.2017). «Подавление нервной сложности во время бессознательного состояния, вызванного кетамином и пропофолом». Письма о неврологии. 653: 320–325. Дои:10.1016 / j.neulet.2017.05.045. ISSN  0304-3940. PMID  28572032. S2CID  13767209.
25. Бола, Михал; Орловский, Павел; Пломецкая, Мартина; Марчевка, Артур (30.01.2019). «Разнообразие сигналов ЭЭГ во время седации пропофолом: увеличение у пациентов с седативным эффектом, но с ответом, уменьшение у пациентов с седативным и невосприимчивым действием». bioRxiv: 444281. Дои:10.1101/444281. S2CID  214726084.
26. Fan Yingle; У Чуанян; Ли И; Панг Цюань (15 декабря 2006 г.). «Исследование по применению измерения сложности флуктуации в обнаружении конечных точек речи». Аэрокосмическая медицина и медицинская инженерия. 19 (6). ISSN  1002-0837.
27. Дилгер, Александр (01.01.2012). «Эндогенная сложность, специализация и общее образование». На горизонте. 20 (1): 49–53. Дои:10.1108/10748121211202062. ISSN  1074-8121.
28. Иванюк, Вера Алексеевна (2015). «Динамическая модель управления стратегическим инвестиционным портфелем». elibrary.ru.
29. Джавахери Джавид, Мохаммед Али (30 ноября 2019 г.). Эстетические автоматы: синтез и моделирование эстетического поведения в клеточных автоматах (докторская диссертация). Ювелиры, Лондонский университет. Дои:10.25602 / золото.00027681.