Thursday, 22 May 2014

Еще раз о строках и распознавании паттернов искусственности

Любой объект может быть представлен в виде своего описания на некотором языке - таково одно из главных предположений математической теории сложности вычислений. 

Рассмотрим различные строки символов кириллического алфавита, дополненного цифрами от 0 до 9 и знаками пунктуации:
  1. "явявявявявявявявявявявявявявявявявявявявявявявяв"
  2. "какцшок сцка даввпргщзгщнйуцучммчымччмм авврора"
  3. "ипм им. келдыша, миусская площадь, 4, 14:00, хоздоговор"
При анализе строк важным понятием является длина (компьютерной) программы (или псевдокода - роли не играет), написанной на некотором языке с целью воспроизвести заданную строку. Длина L программы - это число символов кода. Например, простейший java-метод для вывода на консоль фразы "Hello, world!" выглядит следующим образом:

public void greeting() 
   System.out.println( "Hello, world!" ); 
}

Длина его L = 47 символов, не считая саму строку "Hello, world!" и неважные пробелы. 

Легко понять, что таких программ на определенном заданном языке (например, на том же java) может быть написано очень много - чем сложнее задача программы, тем, соответственно, больше вариантов того, как именно можно добиться цели средствами языка программирования.

Нас будут интересовать лишь программы самой короткой длины K(S)=Lmin, поскольку они будут характеризовать скорее уже саму строку S, чем зависеть от конкретного языка реализации. Величина K(S) называется колмогоровской сложностью строки S. 

Строки типа 1 являются регулярными. Особенностью регулярных строк является их низкая колмогоровская сложность. Действительно, для очень длинной регулярной строки можно написать программу многократного повтора повторяющихся подстрок: "повторить 'яв' 24 раза". Подобные программы будут намного короче самой регулярной строки. В этом случае говорят, что удалось существенно сжать строку. Итак, регулярные строки сильно сжимаемы и поэтому сами они не могут нести достаточно больших количеств информации. 

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

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

Теперь интересно будет отметить вот что. Первое - это наличие подстроки "авврора" в конце строки 2.  А что, если строка 2 вовсе не случайна, а так же, как и строка 3, несет-таки некоторую информацию? Именно этим вопросом в общем случае и занимается теория intelligent design (теория распознавания паттернов искусственности). Возможно ли уловить некие паттерны в строках, имеющих схожие со случайными последовательностями символов частотные характеристики? Классическим примером распознавания является момент из кинофильма "17 мгновений весны", когда Мюллер, имея на руках лишь две различные шифровки Штирлица и не обладая ключом, тем не менее, установил, что за обеими шифровками стоит один и тот же резидент.

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

Физическое обоснование корректности ID состоит в том, что неинтеллектуальные факторы такие, как случайность, некая закономерность или их комбинации, не способны генерировать строки типа 3, колмогоровская сложность которых выше определенной пороговой для данной системы (о конкретных оценках пороговых значений сложности - см. здесь). 

Еще раз подчеркну, что поскольку речь идет о распознавании, то false negatives вполне могут проскакивать на практике. То есть наш метод может не быть достаточно чувствителен для распознавания факта осмысленного существования, скажем, той же подстроки "авврора" в каком-то конкретном случае. Также нельзя исключить возможность интеллектуальной генерации случайных и регулярных строк, что распознать средствами теории ID нельзя без привлечения дополнительной информации. Итак, поскольку распознавание является односторонним (достаточно высокая функциональная сложность → искусственность), то фатальной для ID была бы лишь ситуация, при которой случайная или регулярная по своей природе строка распознавалась бы как искусственная. 

Далее, у Дэвида Абеля в книге "The First Gene" показано, что реальная биологическая функциональность не может задаваться регулярными или случайными строками, но только строками типа 3. В подавляющем большинстве реальных сценариев случайность (например, мутации) разрушает биофункцию, а не создает или модифицирует ее. Единичные случаи, с которыми носятся эволюционисты, представляют собой изменение функции (кооптацию) с потерей информации, то есть с упрощением, а не с усложнением существующей функциональности.

Прошу заметить также, что строки типа 3 могут не содержать явных инструкций в форме глаголов - вычислить, скопировать, обработать и пр. Но эти действия так или иначе предполагаются. Приемник уже о них знает. Иными словами, и отправитель, и приемник функционируют в одном информационном контексте. Именно так и происходит в биологических системах. Контекст - это существование распределенного массово-параллельного процессора из считывающих полимераз, транспортных-РНК, факторов трансляции/транскрипции и пр. Это никак не может отменить того факта, что по своему смыслу строки типа 3 являются инструкциями, или прескриптами. Именно поэтому говорят, что ДНК (РНК) являются шаблонами сборки. Можно представить себе пользователя, заполняющего поля электронной таблицы. Поскольку смысл и порядок полей таблицы обрабатывающий код "знает" наперед, для него важны лишь строки, которые вбивает пользователь. Строка 3 на практике могла быть не только записана в дневнике, но и представлять собой содержимое полей электронной таблицы. 

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

Литература

No comments:

Post a Comment