Pull to refresh

Comments 58

Спасибо за интересную статью! Было бы интересно почитать статьи на тему практического применения алгоритмической энтропии. И где можно найти книгу [1]?
Благодарю!
По поводу алгоритмической энтропии-она особо не применяется в чистом виде в анализе экспериментальных данных, так как не существует (насколько мне известно) универсального алгоритма вычисления алгоритмической сложности произвольной бинарной последовательности. Но наблюдаются связи между алгоритмической и вероятностной энтропией. Можно еще почитать исходную статью Колмогорова http://www.mathnet.ru/links/33d1dd58ea91b3b7cccac275fe0a8970/ppi68.pdf и тут http://iitp.ru/upload/publications/6123/vyugin_kolm.pdf (ссылки красиво не вставляются, извиняюсь)

Книгу можно найти, скорее всего, в киоске СПбГЭТУ «ЛЭТИ», но это нужно уточнить. На неделе выясню и подскажу подробнее. А вы из какого города? И чем занимаетесь? Может, получится по почте отправить, если нужно.

не существует (насколько мне известно) универсального алгоритма вычисления алгоритмической сложности произвольной бинарной последовательности


Да, в точном математическом смысле колмогоровская сложность невычислима (верно даже более сильное утверждение: любая вычислимая оценка её снизу ограничена). Но можно получить любопытные результаты, подменив её на оценку сверху: длину строки после сжатия bzip2. Не знаю, пошла ли эта идея дальше экспериментов по ссылке.

Вот чего не понял — как из картинки 1.5 получается картинка 1.6?
Исходную последовательность разбиваем на «куски» по 100 отсчетов. По каждому строим эмпирическую плотность распределения вероятности Pi и с ней считаем энтропию Шеннона по формулке.
А можно это раскрыть в виде совершенно конкретного и простого примера?
Ок, получили 100 float-ов. Скорее всего, все разные. Вероятность каждого из исходов — 1/100. Как получается, что ваша формула дает разные числа?
Да, и чем именно 100 отсчетов так уж примечательны? 200 будет лучше или хуже? Почему?
100-так как берется система, каждый 100й отсчет переключающаяся в другое состояние(условно их у нас два в примере). И для каждого из этих состоянии имеет место свое распределение вероятности. Вот оно то и будет влиять на значение расчетной энтропии.
А если нет априорного знания о том, как там система ведёт себя под капотом, откуда взять этот период? И еще раз повторю не отвеченный вопрос — как вы по 100 float-ам распределение вероятности строите? Если строите гистограмму, то какую и из каких соображений выбираете её параметры?
Что касается бинарных последовательностей, до сих еще никто не справились с задачей дать удовлетворительную меру сложности единичного конструктивного объекта в себе, колмогоровская сложность безотносительно машины или языка определена лишь для неограниченно усложняющихся последовательностей таких объектов. Иными словами, если наперед задан объект, то можно предъявить машину, относительно которой его сложность равна нулю, как бы он интуитивно сложен не был, и машину, относительно которой сложность этого объекта будет невероятно большой, даже если он интуитивно прост.
Простите, а какая главная мысль статьи? Второй вопрос — как все-таки строится модель энтропийного передатчика для конкретного процесса, например если процесс на осциллографе — правильная синусоида?
Да, относительность она везде)
Мысль главная-это рассказать о разноплановости энтропии как понятия(не каждый это знает), и отметить некоторые подводные камни. Ну и вдруг кому-то информация пригодится в своих исследованиях.
Насчет второго вопроса уточните, пожалуйста, что вы имеете ввиду под моделью-аналитическое выражение али что то другое?
Если следовать примеру выше и разбить область значений синусоиды на небольшие участки, то получится, что принимая любое значение кроме крайних, почти равновероятен как переход в состояние с большим значением, так и переход в состояние с меньшим. Выходит, что синусоидальный сигнал, будучи полностью предсказуемым, имеет ненулевую энтропийную мощность в качестве марковского передатчика?
Энтропийная мощность марковского передатчика (энтропия Шеннона) — абсолютная не зависящая не от чего величина, применимая всюду, где по крайней мере можно утверждать вероятностный либо статистически устойчивый характер процесса.
К примеру взяв 20 типографских оттисков буквы «а» 15 — буквы «б» и 65 — буквы «в» с помощью энтропийной мощности в отсутствие всякой вероятности Вы можете подсчитать количество различных слов длины 100, составленных из этих оттисков.
А можно текст магистерской где-нибудь наити?
В библиотеке университета(ЛЭТИ) лежит электронная запись, но могу прислать по почте с честным обещанием, что будете ссылаться при использовании)
Буду очень благодарен — sgenie собака gmail com
поделитесь своей работой) ссылки на ваше авторство обещаю)
info@astronomikon.ru
Буду признателен, если поделитесь своей работой)
thinker73@yandex.ru
И мне пожалуйста, очень интересно! danskatov собачка гмейл ком.
и мне, пожалуйста на dimchansky гмайл ком
Можно и мне, пожалуйста? evgen.povt@gmail.com
может напишите ссылку на его работу или пошлете на мою почту? :) turyev.roman@gmail.com
http://www.polytechnics.ru/shop/product-details/370-cvetkov-o-v-entropijnyj-analiz-dannyx-v-fizike-biologii-i-texnike.html
Честно сказать так и не понял зачем было вводить эту чисто статистическую величину когда есть прекрасно зарекомендовавшая себя дисперсия с абсолютно тем же применением что и рассмотренное в статье (поиск корелляции).
В некоторых случаях действительно корреляцией можно обойтись. Но как и отмечала-только в случае линейности связи. Нелинейные она не видит.
Проверяли хотя бы на моделях, одна из которых тут представлена. Энтропия отражает степень связности, а корреляции нет между сигналами вообще(наблюдаемые переменные генерировались на основе независимых скрытых ).
Так что основное преимущество перед дисперсионным методом именно такое.
Например, принцип максимума энтропии используется для определения распределения вероятностей при некоторых известных макро ограничениях. В своё время этот принцип произвел на меня огромное впечатление своей простотой и возможностями. Я очень давно этим не занимался и вряд ли смогу привести какие-то примеры. Можно погуглить maxent.

Кстати, там используется именно энтропия Шеннона, в связи с чем очень интересно это:
P.S. При наличии интереса, могу немного подробней поговорить в следующий раз об алгоритмах расчета энтропии и почему энтропию Шеннона сейчас почти не используют.

Я был уверен, что Шенноновская энтропия повсеместно используется.
Скорее некорректно немного сказала, десятилетия два назад появились новые метод расчета, показывающие в ряде задач бОльшую эффективность(аппроксимированная и выборочная в ТОП-ах). Поэтому есть тенденция перехода на них. Но конечно для ряда задач Шенноновская также применима. Подправлю, пожалуй)
То есть, если я правильно понял, вы считаете, что если у вас есть две функции H от распределения вероятностей перехода между состояниями, то они друг с другом как-то «связаны»?
Даже если не говорить про способы влияния количества пиратов на глобальное потепление (ваше определение «связанности» явно означает не причинно-следственную связь), можно легко подобрать случай, когда энтропия одной функции будет в два раза больше или меньше другой, но из первой функции можно будет прекрасно предсказать вторую с любой наперёд указанной точностью, и наоборот.
Всё же одним параметром распределение вероятностей не опишешь.
Спасибо за статью, хотелось побольше узнать о алгоритме вычисления степени связности нескольких процессов с помощью энтропии.
Есть ли где-то в электронном виде «Цветков О.В. Энтропийный анализ данных в физике, биологии и технике»? Тираж, смотрю, совсем небольшой.
http://www.polytechnics.ru/shop/product-details/370-cvetkov-o-v-entropijnyj-analiz-dannyx-v-fizike-biologii-i-texnike.html
Я шо-то не понял… первая формула определяет битовую размерность числа всех возможных исходов?
К примеру, подбрасываем монету, возможных исходов 2, вероятность каждого = 0.5, логарифм = -1, H = -(0.5*-1 + 0.5*-1) = 1. Действительно, можно описать все (два) исхода одним битом, который либо ноль, либо единица.
Или вот, допустим, я выпил йаду -> у меня один исход (смертельный) с вероятностью 1, логарифм = 0, H = 0. Т. е., вообще ни одного бита не нужно, и так всё ясно… Хотя нет, что-то не сходится — формально же исходов всё равно два — умер (вероятность 1)/не умер (вероятность 0), и нужно будет посчитать несуществующий логарифм нуля?..
Если логарифм нуля (минус бесконечность) умножить на ноль, получим в данном случае ноль.
X*ln X -> 0 при X -> 0
Очередная статья про энтропию, написанная сложным языком. Продолжаем ждать простую статью.
Любопытно было бы взглягуть на магистерскую (wissensaft at protonmail dot com), но последняя картинка в статье выглядит так, как будто вы нашли различие по «ЭЭГ» без глазных артефактов и с оными. Подругому взлет энтропии по Fp1/Fp2, при стабильных O1/O2 во время визуальной нагрузки прям и не объяснить :). Шутки в сторону, главная причина имхо по которой энтропия не светится в физиологических журналах приличного импакта (5+), в том что чаще всего данные могут быть объяснены моделью с более тривиальными параметрами: мощность, когерентность и т.п. Ну или не могут быть объяснены вовсе. В статье, на рисинках 1.5 и 1.6., на глаз, амплитудная огибающая тоже вполне себе предсказатель, исчитать в 100 раз дешевле. (На «сравнительных» русунках, кстати, масштаб по абсциссе не соблюден. Я был бы рецензентом — наругался бы.)
На тему энтропии меня давно мучает один вопрос, буду признателен за мысли. Что насчет изменения энтропии Вселенной (да, я читал Хокинга)? А лучше, ее относительно малой части: солнечной системы. Если посмотреть тенденцию: было просто газопылевое облако, появилась звезда, образовались тяжелые элементы и планеты, вода, простые организмы, сложные организмы, разумный человек, цивилизация.

Как Вы считатете, каждый следующий шаг «ожидаем»?
Если да, то в основу реальности вшит механизм обеспечения ее эволюции на всех уровнях (не только биологическом), если нет — значит энтропия мира падает (за счет чего?).
А почему вы считаете солнечную систему замкнутой или изолированной? Теперь пропало противоречие? Помимо этого с термодинамической точки зрения все «нормально» даже в наших масштабах — солнце постепенно остывает, планета напротив нагревается…
1. Думаю, что изолированных систем в природе вообще нет, речь об относительной изолированности. В трудах Н.А. Козырева упоминались галактики, расстояния между которыми столь огромны, что их слабым взаимодействием в данном вопросе можно пренебречь. Второе начало термодинамики применимо только к абсолютно замкнутой системе? Если таковых в реальности не существует, значит это правило в природе не работает? Если допускается некоторая открытость — какова мера? Какую систему можно считать достаточно замкнутой?

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

Относитесь к энтропии не как к мере хаоса, а как к мере непредсказуемости.
Чьё поведение сложнее предсказать, кипящего океана или человеческого социума? Если второе, значит энтропия со временем выросла.
Тогда я окончательно запутался. Вселенная становится сложнее и организованнее со временем? Если это сопровождается ростом энтропии, тогда она является чем-то противоположным мере беспорядка.
Я в ваших репликах прослеживаю какие-то этические нотки. Вроде как сложность — это хорошо, порядок это хорошо, хаос это плохо. Тогда какая энтропия? Она определяет сложность (т.е. «хорошая») или хаос (т.е. «плохая»)?

Но этика тут перпендикулярна физике. Для энтропии важно лишь, сколько у системы возможных состояний и как сложно нам предсказать состояние, не наблюдая её некоторое время.

Представьте себе школьника. Его энтропия S. Но когда он закончил ВУЗ и набил голову всякой информацией, энтропия выросла. Стал он сложнее? Да. Стал он организованнее? Да. Хаотичнее? Не знаю, может, да.
Хорошо, возьмем пример: музыка. Есть симфония Моцарта, и есть белый шум. Каждый следующий звук симфонии легче предсказать (за счет повторяемости ритмов, мотивов). Я не уверен, как формально это описать правильно, но чисто на «бытовом» уровне, симфония — более организована, структурирована, сложна. Где энтропия выше?
У белого шума. То есть на одной симфонии энтропия понижается, но в мире все другие произведения не исчезают. Поэтому при создании симфонии суммарная энтропия не уменьшается.
Про сумму не очень понял. Если симфония уменьшила энтропию, то где-то она должна увеличиться, разве нет? Как иначе суммарная энтропия может остаться на прежнем уровне?

Если организация хаотичных звуков в закономерные регулярные последовательности — снижение энтропии, разве не то же самое происходит с материей во Вселенной со времен большого взрыва? Все-таки энтропия падает?
Моя ошибка, утверждение «на одной симфонии энтропия понижается» верно при замене шума на симфонию, по факту же шум где-то остаётся.

Т.е. правильнее «при создании симфонии энтропия не так сильно выросла, как при создании шума».
Это же информационная энтропия? Может она и не должна расти как термодинамическая? Сложно представить как написание симфонии может физически влиять на Вселенную…
Скорее всего, влияние происходит так: меняется энтропия сознания, состояния мозга, который тоже часть Вселенной.

p.s. т.е. информационная и термодинамическая энтропия — это не просто разные подходы к ее трактовке, а принципиально разные величины?
Есть общий принцип: энтропия это длина описания, т.е. логарифм от кол-ва состояний.
Но в физике описываются заранее заданные величины (импульс, координата, скорость), а в энтропии по Шеннону заранее известен алфавит источника и описывается частота появления символов, при условии что они друг с другом не связаны. В общем случае можно построить любую модель наблюдаемого объекта и посчитать энтропию как свободу поведения объекта в её рамках.
Сложно представить как написание симфонии может физически влиять на Вселенную
Симфония же записана на каком-то носителе. Более регулярная запись — меньше произвола в расположении атомов носителя ))
На эту тему вспоминается книга «Физика процессов эволюции» и книги по самоорганизации Хакена. Я правда их очень давно читал и ничего не помню ) Кстати, у Хакена не плохо описан принцип максимума информационной энтропии.

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

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

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

Так же и со вселенной. Она постепенно остывает. Но при этом происходят разные нелинейные процессы, в которых возникают точки неустойчивости, в которых малейшие флюктуации могут приводить к появлению разных пространственных и временных структур.
Такой «переборный» метод организации пространства-времени не был бы столь эффективный, мы бы видели множество неудачных, наполовину готовых планет, живых организмов и пр. Я твердо уверен в том, что эволюция на всех уровнях — основной закон природы. Конечно, эта концепция выходит за рамки науки, она не верифицируема, и относится скорее к натурфилософии, т.е. это подход к пониманию мироустройства, увы, слаюо распространненный в современном естествознании (не смотря на развитие эволюционных теорий в биологии, космологии, работ по синергетике и пр.).
Лет 100-150 назад во времена классической ньютоновской физики вселенная представлялась как огромный и очень сложный, но полностью детерминированный часовой механизм. Конечно, сам по себе, случайным образом или в результате перебора такой механизм не мог возникнуть. Поэтому были развиты различные креационистские идеи, что кто-то или что-то создали и запустили этот механизм. Но с развитием некласической физики стало видно, что достаточно сложные структуры могут возникать просто в результате самоорганизации.

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

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

PS: Забыл к чему я все это писал :) Я думаю, что ваш принцип эволюции на всех уровнях и принципы, лежащие в основе синергетики и т.п. — одно и то же.
Согласен с Вами. Я не пытаюсь объяснить существование сложно организованного мира креационистскими идеями. Как бы он ни появился, в него встроены механизмы эволюции — называйте это самоорганизацией. Смущает, конечно, приставка «само», оно (если быть честными) смахивает на попытку спрятать то, что мы не понимаем. Само ничего не происходит, у любого процесса есть причина, внешняя или внутренняя. Но мы спорим о терминах. Как ни называть это, если в основе становления и развития Вселенной находятся некие законы самоорганизации, приводящие к универсальному строению материи (как Вы подметили схожесть планет, звездных систем и пр.) — почему нет теории эволюции? Если этот принцип настолько фундаментален, что охватывает множество уровней материи (в смысле этапы развития частиц, звездных систем и планет, химических элементов, биосферы, социума) — разве он не заслуживает изучения? Почему теории, называемые фундаментальными, даже не затрагивают наиболее фундаментальный принцип — всеобщую самоорганизацию материи?
Есть синергетика, всякие теории хаоса, бифуркаций, катастроф, динамических систем. Люди активно занимаются этим общим принципом. Кроме Г. Хакена и В. Эбелинга ещё читал когда-то Малинецкого Г.Г., Чернавского Д.С. У них много примеров из совершенно разных областей: химия, физика, биология, экономика и т.п.
Да есть конечно, но мало, это всего лишь отдельные узкие теории. А концептуальная основа науки по-прежнему не содержит понятия эволюции. Да, пусть с точки зрения науки это этический, философский момент, но ведь именно философия лежит в основе естествознания. Представьте, как бы изменился мир, если философия науки приняла бы эволюцию Вселенной как фундаментальную универсальную концепцию!
Потому что развитие численно не могут измерить.
Так, чтобы сказать «за последний час система X эволюционировала на N попугаев».

Поэтому всё на уровне манифестов. Если их принятие и изменит мир, то не так, как это сделала Ньютоновская механика, с возможностью что-то посчитать, а скорее как христианство, оно тоже сильно изменило мир, но для науки не принесло пользу.

У меня ощущение, что мир сейчас на грани какого-то фундаментального открытия, которое позволит формально выделять любой смысл и оперировать им, как напряжением или температурой. А из этой теории появится и ИИ, и числовой подсчёт количества эволюции.
YuliyaCl, спасибо за статью и магистерскую. Очень интересно.
Для меня остался непонятным поправочный коэффициент.
Какова его природа и как он вычисляется?
Sign up to leave a comment.

Articles