mns2012

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

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

Здесь я постараюсь довести наши исследования о распознавании дизайна до логического конца.

Мы занимаемся распознаванием дизайна в статистической постановке (см. Проверка статистических гипотез). Базовой рабочей (так называемой нулевой) гипотезой H₀ является утверждение о случайном возникновении наблюдаемой конфигурации материи X в рамках заданной стохастической модели P. Наша задача состоит в выявлении условий и свойств Х, позволяющих отклонить нулевую гипотезу.

Мы будем опираться на предыдущие шаги, в которых мы достаточно подробно рассмотрели вопросы сложности и специфичности. Для начала напомню, что мы установили:

Сложность связана с понятием шенноновской информационной энтропии и степенью сжимаемости данных без потери информации (lossless compression);

Специфичность отражает то, сколь компактно можно описать наблюдаемую конфигурацию материи; точнее какова длина кратчайшей программы, выдающей описание наблюдаемого в соответствующим образом поставленной математической задаче (вводится язык описания и анализируются строки описания наблюдений). В дальнейшем, чтобы не утяжелять текст, мы не будем различать Х и описание Х, считая, что конфигурация Х является строкой символов фиксированного алфавита, например булевого {0,1}.

Спецификацией Х выступает та или иная программа, которая в определённом контексте (вычислительной среде) выдаёт Х и останавливается.

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

Однако перед нами встала новая проблема: мы видели, что достаточно короткая программа (например, клеточный автомат правило 30) может создавать сложный (то есть очень плохо сжимаемый) паттерн. Клеточный автомат в этом случае является краткой спецификацией сложного паттерна. Достаточно краткая программа типа правила 30 может возникнуть спонтанно в уже сформированной вычислительной среде. Не опровергает ли это наши выводы о специфической сложности как надёжной в смысле отбраковки нулевой гипотезы метрике? Я отметил в предыдущих записях, что существование самой вычислительной среды, в которой возможно спонтанное возникновение коротких программ, само по себе указывает на дизайн. Но это было лишь краткое замечание. Теперь необходимо разобраться с этой проблемой более подробно.

В этом нам будет помогать Gemini, обученный на соответствующей литературе (работы У.Дембского, Р.Маркса, У.Юэрта, С.Майера и других авторов, разработавших и популяризирующих методологию распознавания дизайна в природе).

Понятие алгоритмической сложности (ASC)

Алгоритмическая сложность (Algorithmic Specified Complexity) вводится для тройки:

{конфигурация Х, информационный контекст С, стохастическая модель P}

как разность информации (информационной ценности, сложности) конфигурации X, и колмогоровской сложности Х в контексте С:

ASC(X,C,P) = I(X) - K(X|C),

где:

X — наблюдаемое, например, битовая строка или последовательность аминокислот.

I(X) = −log₂P(X) — информация (self-information), или сложность; измеряется степень неожиданности (surprisal) наблюдения Х при данном распределении P вероятностей. Низкие значения вероятности соответствуют высокой степени неожиданности (сложности) Х.
- Пример. Бросаем честную (сбалансированную) монету 1000 раз. Если в рамках стохастической модели принять, что броски независимы друг от друга и что каждый бросок может завершиться только решкой или орлом, то вероятность выпадения орла или решки в каждом броске составит 1/2 и с каждым броском наблюдатель получит −log₂P(X) = −log₂(1/2) = 1 бит информации. Результаты бросков можно представить в виде битовой строки из нулей (решка) и единиц (орёл). Таким образом, фиксированная строка представляет собой запись результатов бросков. Её длина равна 1000. Вероятность любой фиксированной строки длиной 1000 равна (1/2)¹⁰⁰⁰. Количество информации в строке длиной 1000 равно −log₂P(X) = −log₂(1/2)¹⁰⁰⁰ = 1000 бит. Оно не зависит от конкретной последовательности нулей и единиц. Оно зависит лишь от длины строки и принятого распределения вероятностей P возможных исходов бросков. Однако специфичность строк 1111111111... (1000 орлов подряд) и 0000000000... (1000 решек подряд) выше специфичности любой другой последовательности нулей и единиц той же длины.

K(X|C) — колмогоровская сложность Х, то есть длина кратчайшей программы, генерирующей Х в заданном информационном контексте С и останавливающейся. K(X|C) измеряет паттерн, или регулярность в Х.
- Пример. Строка из 1000 символов 1111111111... может быть получена короткой программой: напечатать '1' 1000 раз, тогда как программа выдачи на печать случайной последовательности символов 0 и 1 той же длины без какого-либо паттерна будет значительно длиннее: напечатать "0010111...", то есть всю строку целиком символ за символом, поскольку случайную строку, лишённую какого бы то ни было паттерна (повторов блоков символов), сжать без потери информации невозможно. Таким образом, в первом случае величина K будет меньше, чем во втором. В нашем примере с бросками монеты любая строка, включая 1111111111..., является случайной, однако максимальной специфичностью характеризуются лишь строки из одних нулей или единиц. Ниже мы увидим, что редкость специфичных строк в определённом контексте может быть столь велика, что гипотеза о случайном появлении таких строк на практике может быть отклонена.
- Почему важен контекст? Длины кратчайших программ могут быть существенно различными в разных контекстах. Например, процедура, использующая внешний подключаемый модуль, имеет длину L₁, а программа, включающая и процедуру, и модуль, имеет длину L₂ > L₁. Эта разница существенна и не зависит от того, насколько компактно написан код и на каком языке реализован.
- Пример. Предположим теперь, что кто-то говорит нам: "Я осуществил 1000 бросков монетки и у меня выпали одни орлы". В таком случае с достаточной на практике уверенностью можно сказать, что это не случайность: слишком велико несоответствие между нашей стохастической моделью и тем, что нам сообщили. Таким образом, здесь имеет место либо закономерность (например, монетка была несбалансированная), либо дизайн (например, если этот человек нам соврал). Этот наш вывод, разумеется, делается в статистической постановке и может оказаться ошибочным. Однако далее мы увидим, что это несоответствие между реальностью и принятой стохастической моделью можно измерить, и что чем больше это несоответствие, тем с большей уверенностью мы сможем отклонить предположение о случайности на практике (тем меньше вероятность нашей ошибки).
- Пример. Я прихожу к себе в комнату и вижу: ёлочка горит. В данном контексте вероятность самопроизвольного движения электронов по цепи от батарейки к огонькам хотя и отлична от нуля, но мала настолько, что имеется статистическое обоснование отклонения этой гипотезы. Поскольку также на данный момент у нас нет наблюдений закономерного включения ёлочек, мы приходим к выводу о дизайне: кто-то включил огоньки. В другом контексте достаточного статистического основания для отклонения гипотезы о спонтанном возникновении электрического тока в заданной области пространства могло и не оказаться, например, если у меня был бы прибор, случайно включающий ёлочку.

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

Алгоритмическую сложность делает полезной ограниченность вероятности наблюдения объектов, для которых величина ASC больше или равна α бит:

Pr[ASC(X,C,P) ≥ α] ≤ 2^−α

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

Таким образом, если наблюдаемая конфигурация Х характеризуется алгоритмической сложностью в 100 бит, то случайная генерация Х стохастическим процессом P чрезвычайно маловероятна. С ростом ASC наступает такой момент, когда вероятность случайного появления Х в системе становится статистически пренебрежимо малой. Иными словами, относительно высокие значения алгоритмической сложности являются практически надёжным обоснованием отклонения гипотезы о случайной генерации Х. А это, в свою очередь, при дополнительном условии отсутствия наблюдений закономерной генерации Х эквивалентно утверждению, что альтернативная гипотеза представляет собой утверждение:

Х — дизайн.

Случай относительно простой программы-генератора высокоэнтропийных паттернов

А теперь рассмотрим частое возражение: как быть с простыми программами (клеточными автоматами), которые производят высокоэнтропийные паттерны?

Лет 8 назад Jeffrey Shallit показал мне статью, в которой как раз это моделировалось: были представлены результаты численного моделирования того, как из "первобытного супа" вычислительных элементов самособирается что-то сложное и функциональное. Это было что-то аналогичное алгоритму Р. Докинза, который начинал вычисления со случайного набора букв и сходился на цитате из "Гамлета": ME THINKS ITS LIKE A WEASEL. В докинзовском алгоритме всё дело было в том, что он был неявно наделён информацией о желаемом результате: необязательно именно об этой фиксированной фразе, но о характеристиках целевого состояния, то есть того состояния, к которому разработчику алгоритма нужно было стремиться (см. здесь). Проблема, таким образом, была в том, что само это наделение алгоритма ключевой информацией не соответствовало задаче моделирования, если, конечно, исследователь ставил цель промоделировать абиогенез или биологическую эволюцию. Почему? Потому что неживая природа не стремится к жизни. Эволюция по своей природе также никуда не направлена и не имеет цели. Как только явно или неявно в численном эксперименте вводится целевое состояние, то, что замысливалось как модель эволюции, становится моделью искусственной селекции, искусственной разработки, или дизайна. То же самое было и в случае со статьёй о самособирающихся вычислителях с той лишь разницей, что импорт информации о желаемом результате происходил менее явно. Я даже ответил на эту статью отдельной записью (первоначальный отклик на английском от 2017 г. бы опубликован американским сайтом UncommonDescent.com). Это была ещё одна прекрасная иллюстрация принципа, известного каждому разработчику программного обеспечения: Garbage In — Garbage Out, "что заложишь, то и получишь". Заложишь мусор — мусор и получишь на выходе. Сообщишь необходимую информацию поисковому алгоритму — получишь нетривиальные, как говорят, интересные решения. В закладываемых предположениях о том, как задаётся целевая функция, какие ресурсы используются, как направляется поиск, как формируется окрестность текущего состояния, как осуществляется отбор или переход из текущего состояния в следующее, как отбрасываются бесперспективные промежуточные результаты и пр., в информационный контекст могут быть неявно импортированы настройки поискового алгоритма на искусственную селекцию, то есть фактически на дизайн. В случае же, если численный эксперимент проводится корректно, без внесения удобных разработчику предположений, а модель отражает реальное положение вещей, ничего "интересного" не возникает. Количество информационного импорта, т. наз. активную информацию, привносимую разработчиком в информационный контекст поиска, можно измерить. Но обо всём по порядку.

Если в нашей стохастической модели P используется равномерное распределение вероятностей для каждого бита в строке при оценке паттерна, который производится, скажем, правилом 30 или другим относительно простым клеточным автоматом, ASC действительно будет очень высоким: I(X) ≫ K(X∣C). Тем не менее, о чём говорит высокое значение ASC? Лишь о несоответствии стохастической модели P конфигурации Х. Метрика ASC выполняет свою роль: гипотеза о случайном происхождении Х в данном случае должна быть отклонена, коль скоро существует простое правило, объясняющее появление Х. При этом от ответа на вопрос о возможности случайного появления самого этого правила в данном контексте С при данной стохастической модели P зависит то, какой вердикт мы вынесем по поводу Х: дизайн это или не дизайн?

Закон сохранения информации

Авторы W.Dembski, W.Ewert, R.Marks, предложившие данную метрику, утверждают, что даже если существует простое правило, объясняющее сложный паттерн, проблема специфической сложности никуда не исчезла, она просто перенесена в контекст С. Dembski et al. называют это утверждение законом сохранения информации, в чём можно видеть своеобразное подтверждение правила: Garbage In — Garbage Out:

Если простое правило производит высокоэнтропийную конфигурацию, неожиданность (информативность, surprisal) переместилась в контекст С, в которым возникает и функционирует данное правило.

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

Функциональные спецификации

ASC измеряет, насколько наблюдаемый паттерн отклоняется от принятой стохастической модели P. Таких объектов в реальности существует множество, включая неинтересные для нас случаи, не являющиеся дизайнами (кристаллы, фракталы, клеточные автоматы, производящие сложные неспецифичные паттерны, и пр.). Для того, чтобы их исключить при распознавании дизайна, можно ввести дополнительные условия на спецификацию. Например, рассматривают только функциональные паттерны: скажем, нуклеотидные строки, кодирующие функциональные белки; стартовые конфигурации клеточных автоматов, производящих функциональные паттерны типа Gosper Glider Gun, и т.д.

В статье 2015 г. "Algorithmic Complexity in the Game of Life" W.Dembski, W.Ewert, R.Marks применяют ASC к функциональным структурам. В работе утверждается, что сложные функциональные паттерны (например, то, что самовоспроизводится или движется в пространстве игры) характеризуются высокими значениями ASC не потому, что их спецификациями являются простые математические правила, но вследствие того, что они производятся сложными автоматами, нацеленными на генерацию таких паттернов.

Для формализации функциональных спецификаций на контекст С налагают дополнительные ограничения. Так, Kirk Durston, Jack Szostak, например, используют при задании контекста понятие функциональной цели (functional target): требование существования любого простого описания (программы) паттерна заменяется требованием, чтобы конфигурация обеспечивала заданную функцию (например, связывала кислород). Таким образом, если доля конфигураций, обеспечивающих заданную фиксированную функцию f, в пространстве возможных конфигураций мала, то значение I(X) будет велико. Если при этом конфигурация Х попадает в множество целевых конфигураций, то она является функционально-сложной и отвечает функциональной спецификации.

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

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

Активная информация

Таким понятием является активная информация. Она вводится следующим образом:

I₊ = log₂(p_target/q_target),

где:

q_target — вероятность нахождения целевой конфигурации (например, обеспечивающей заданную функцию) вслепую;

p_target — вероятность нахождения целевой конифигурации с использованием информационного контекста С (например, поискового алгоритма или правила 30).

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

Пример. Оценим количество активной информации для правила 30. Без этого правила, вероятность угадывания паттерна составляет 2^−N для N клеток (с двумя состояниями: on и off). С помощью правила 30 вероятность нахождения паттерна равна 1. Таким образом, количество активной информации составляет: I₊ = log₂(p_target/q_target) = log₂(1/2^−N) = N бит.

Поиск поиска: в случае простых программ проблема сдвигается в сторону контекста

Активная информация имеет смысл, так как информация сохраняется. Если тот или иной алгоритм позволяет легко отыскивать маловероятную (для нахождения слепым поиском) целевую конфигурацию, сам этот алгоритм должен быть редок на множестве возможных алгоритмов. Таким образом, имеем:

Объект/конфигурация Х: высокая сложность, малая вероятность.

Поиск/правило/контекст С: эффективное нахождение конфигурации (низкая time complexity).

Поиск поиска: вопрос "Как был сформирован контекст С?".

Если мы говорим, что правило 30 или ему подобное возникло спонтанно, мы должны посмотреть на размер пространства поиска правил. Отыскать как таковое правило, производящее сложный неспецифичный паттерн, достаточно легко. Однако отыскание правила, производящего функциональный паттерн (например, сложный самовоспроизводящийся клеточный автомат) экспоненциально труднее. Скажем, количество активной информации, требуемой для выбора правила, которое строит рибосому, в пространстве всевозможных физических закономерностей астрономических размеров очень велико.

Пример. В классе одномерных клеточных автоматов, правило определяет состояние (цвет) клетки, основываясь на текущем состоянии самой клетки, а также на состояниях двух её соседей. Поскольку у каждой клетки имеется всего два возможных состояния (on/off, чёрный и белый цвет), существует всего 2³ = 8 текущих конфигураций состояний клетки и двух её соседей в текущий момент времени. Состояние клетки в следующий момент времени зависит от того, какая из 8 возможных конфигураций имеет место в текущий момент. Состояний у клетки всего два. Поэтому всего существует 2^2³ = 256 правил для одномерных автоматов. Если мы выбираем вслепую одно правило из 256 возможных, мы получаем 256 бит информации. Из этих 256 правил лишь 30 производят что-то "интересное": сложное и неповторяющееся. Правило 30 — одно из них. Поэтому q_target = 30/256. Каждое из них находит определённое таким образом "интересное" с вероятностью 1. Поэтому количество активной информации в этом случае составляет log₂(p_target/q_target) = log₂(1/(30/256)) ≈ 3.1 бит. Количество активной информации с ростом сложности функции возрастает; пространство поиска вырастает до гигантских размеров, так что необходимо учитывать не только непосредственных соседей клетки в игре, да и одномерные автоматы нам уже не помогают. Число состояний клетки также возрастает. А вот число конфигураций, способных делать что-то специфически сложное, например, строить рибосому, чрезвычайно мало, потому что чем сложнее функция, тем реже она встречается в пространстве конфигураций и тем меньше у неё синонимов. Об этом мы уже говорили здесь.

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

Итак, правильно ли утверждать, что высокое значение ASC у паттерна, который был получен правилом 30, — это ложноотрицательный результат, с точки зрения распознавания дизайна? Не совсем. Мы должны ещё ответить на вопрос: "А откуда взялся контекст С, в котором возможно появление и функционирование правила 30?":

Высокие значения I₊: специфичные правила, настроенные на производство функциональных конфигураций (специфический ансамбль физических констант, совместимый с жизнью на основе углерода; сложная биологическая функция, например, белковая). Случай дизайна.

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

Связь активной информации с алгоритмической сложностью

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

ASC(X,P,C) = I(X) − K(X|C) = −log₂q − (−log₂p), где p = 2^−K.

ASC(X,P,C) = log₂p − log₂q = log₂(p/q) = I₊

Тот факт, что ASC составляет α бит, означает, что в контекст С былo сообщено α бит активной информации.

Связь активной информации с NFL-теоремами

Теоретический аппарат распознавания дизайна разработан У.Дебским, У.Юэртом, Р.Марксом и др. на основе теорем с довольно неформальным, но выразительным названием No Free Lunch ("халявы не бывает", или "за плюшки приходится платить"). NFL-теоремы (их две, но они говорят об одном и том же) утверждают следующее: ни один поисковый алгоритм на пространстве всех возможных поисковых задач не является наилучшим. Эквивалентная формулировка: ни один поисковый алгоритм в среднем по всем возможным поисковым задачам не лучше случайного поиска. Таким образом, если отдельно взятый алгоритм (контекст С) более эффективен, чем случайный поиск, то это так потому, что он был настроен на решение конкретного типа задач. Отсюда, кстати, видна важность знаний конкретной предметной области (domain knowledge), что никогда не выведет за скобки человеческий интеллект и опыт, так сказать, знание важных исключений из правил. Активная информация выражает численно степень этой настроенности: сколь глубоким явлился дизайн информационного контекста, позволяющего появляться тем или иным конфигурациям (тому же правилу 30, например).

Математическое обоснование ASC

Алгоритмическая сложность хорошо определена: информативность (surprisal) конфигурации Х с ростом длины строки, представляющей Х, растёт быстрее, чем длина программы генерации Х (неформально говоря, чем длина описания Х). Цель спецификации — сжать данные.

При равномерном распределении P символов в строке, для битовой строки длиной n, количество информации I(X) составляет ровно n бит. Таким образом, функция I(X) монотонно возрастает с ростом длины строки: O(n).

Величина K(X|C) для случайных строк также монотонно возрастает с ростом n как O(n), так как случайную строку сжать без потери информации невозможно. Поэтому для случайных строк с ростом длины строки ASC как разность информации в Х и длины описания Х не изменяется, оставаясь на нуле. Однако в случае сложных паттернов с ростом длины строки K(X|C) растёт как O(log₂n). Поэтому предел отношения K(X|C)/I(X) при n → ∞ = 0.

Почему K(X|C) ≤ I(X)? Во-первых, длина кратчайшей программы, выводящей Х и останавливающейся, ограничена сверху величиной n + константа. Значение K(X|C) для произвольной конфигурации Х не может быть больше n, потому что для любой Х всегда можно вывести саму конфигурацию Х без сжатия. Во-вторых, математический смысл спецификации заключается в том, что конфигурация должна быть Х сжимаема относительно контекста С. По смыслу понятия специфичности, для специфичных Х должен существовать "зазор" I(X) ≫ K(X∣C), величина "зазора" соответствует величине активной информации, о которой мы говорили выше. Если K(X|C) ≈ I(X), то конфигурация Х неспецифична. Если же K(X|C) > I(X), то сам контекст не может использоваться для задания спецификации, так как в этом случае контекст привёл к тому, что конфигурацию Х описать или задать труднее, чем без него (предположим, нужна карта Лондона, а нам дали карту Москвы).

Итог всего-всего-всего

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

$Если конфигурация Х сложна, а контекст С представляет собой дешёвое правило, которое легко отыскать случайным поиском, количество активной информации для всей системы с учётом контекста невелико;$

$Напротив, если конфигурация Х сложна и функциональна, а в качестве контекста С выступает относительно редкое правило (алгоритм), которое трудно отыскать случайным поиском, количество активной информации для системы велико и гипотетический вывод о дизайне такой системы имеет серьёзное статистическое обоснование.$