מכל מלמדײ השכלתי (duchifat) wrote,
מכל מלמדײ השכלתי
duchifat

Еще несколько мыслей по поводу вот этого разговора (http://duchifat.livejournal.com/1518051.html), где chaource утверждает, что колмогоровская сложность бесполезна для обоснования теории вероятности и понятия "случайного".

Когда у меня (лет 20 назад) появился первый компьютер, и мне сказали, что файлы можно сжимать и архивировать программами вроде .rar .zip или .arj, чтобы они влезали на дискету, я не поверил, настолько это казалось контр-интуитивно. Ведь если файл сжать, информация теряется! Как же возможно ее восстановить из ничего? Не может такого быть, архиваторы не могут существовать, вы меня обманываете! Оказалось, что архиваторы отлично работают, а в файлах полно избыточности. Информация, содержащаяся в тексте, оказывается, это совсем не то, чему нас учили в детстве, не количество бит. А сколько же в тексте на самом деле информации?

Второй раз я удивился на эту же тему, когда совсем недавно по чьей-то ссылки прочитал про лекцию Шеня и книгу Верещагина, Успенского и Шеня про коломогоровскую сложность (я по своему невежеству никогда про это не слыхал). Там рассматривается вопрос, чем отличаются последовательности вроде:
0101010101010101
1001011011100110
Первая выглядит упорядоченной, а вторая - случайная последовательность. Но это как посмотреть, с одной точки зрения они совершенно равноправны (01010101 тоже может случайно оказаться результаом случайного процесса, вероятность ее не ниже, чем любой другой конкретной последовательности такой же длины). С другой стороны, первую можно описать короткой программой, а второю нельзя. Под колмогоровской сложностью понимается длина такой программы.

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

Heвозможность точного ответа на вопрос "сколько информации содержится в данной строке" связана с т.н. https://en.wikipedia.org/wiki/Berry_paradox парадоксом Берри, заключенном в предложении «Наименьшее натуральное число, которое нельзя описать менее, чем одиннадцатью словами». Если такое число N есть, то оно уже определено фразой выше из 10 слов, что противоречит определению. В то же время ясно, что числа, которые нельзя определить фразой меньше чем из 11 слов, существуют, и среди них должно быть наименьшее. То есть под любую конкретную последовательность можно придумать специальный ad hoc короткий способ записи (или специальный "язык", включающий такой способ).

Получается, что информация (количество информации в данной конкретной строке или тексте) не существует сама по себе. Она существует только в паре с определенным языком. А язык, ясное дело, существует, если есть субъект, способный воспринимать этот язык (я жутко извиняюсь, сейчас могут прийти атеисты с биологическим образованием и сказать про обскурантизм). :) Почему я так думаю? Адекватный, осмысленный язык, это язык пригодный для субъекта. Адекватность субъективна. Формально или объективно все языки равны. Среди бесконечного множества безумных языков есть такие, в которых фраза 10010110 кодируется проще, чем 01010101. Но нас интересуют "нормальные" языки, а как определить нормальность без субъекта? :)

Но программы архивирования файлов, конечно, работают не поэтому. Большинство реальных файлов (вроде текстов на английском языке в Ворде или фильмов на DVD) содержат большое число повторов. Или, на худой конец, неравномерное частотное распределение символов (еслы в вашем тексте буква "а" встречается чаще, чем буква "ъ", то это уже ведет к избыточности). Если заранее известно, что пользователь будет пытаться архивировать примерно такой структуры файлы, то под такие типы файлов и подбираются программы архивирования. Другими словами, они могут архивировать "нормальные", так сказать, человеческие файлы. При этом о нормальности можно говорить, если есть большой набор файлов (текстов) и в них тем или иным способом выявляется определенного типа избыточность информации. Конечно, это не обязательно созданные людьми файлы, это может быть какая-нибудь там последовательность нуклеотидов ДНК или данные о температуре на Камчатке. Что важно, это уверенность, что архивирующей программе не подсунут вдруг вместо привычных форматов нечто совершенно новое. А вот эта уверенность и основана на том, что программу используют люди для своих субъективных но адекватных целей. Точно так же как если у нас имеется последовательность из тысячи повторений 010101..., мы полагаем субъективно, будто она не случайна, но на деле нет никакой гарантии, что с тысяча первого раза не начнет выпадать нечто неожиданное. Аналогично, если до сих пор сжимали .doc файлы и под них заточен архиватор, нет никакой гарантии, что с 1001 раза безумный юзер не начнет вдруг подсовывать другие файлы. Точнее гарантия есть, но она субъективна, а не объективна, она работает только если мы допускаем наличие рационального субъекта, который будет использовать архиватор для человеческих, а не для случайных, целей. Любой "конструктивный" (подразумевающий вычислимость) подход отталкивается от вычислимости "для нас", а не в абстрактно-объективном смысле для сферического коня в вакууме.
Tags: science
Subscribe

  • (no subject)

    Любопытная статья про то, что скорость звука в твердых материалах ограничена величиной 36 км / с, точнее, V/c= alpha (m_e/2m_p)^1/2, где alpha -…

  • (no subject)

    Нет, я не только про трибоинформатику думаю (хотя и пытаюсь для себя мысленно разобраться со всяческими новомодными вычислительными концепциями,…

  • (no subject)

    Каким образом искусственная нейронная сеть со всего одним промежуточным слоем с 15 нейронами может распознавать (в 95% случаев) неряшливо написанные…

  • Post a new comment

    Error

    Comments allowed for friends only

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 9 comments