Почему в случае строковых функций "что ни кинь -- всё клин" не получается

[mns2012]

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

Прежде всего заметим, что функция определена в нашем случае на множестве дискретных переменных.

Функциональная сложность переменной (строки s ∈ Ω) измеряется количеством функциональной информации в строке:

I_f(s) = —log₂(|T_f|/|Ω(A)|),

где:

• Ω(A) -- пространство возможных строк символов алфавита А.


• T_f -- целевое подпространство, включающее лишь строки, доставляющие функцию f.


• |X| -- число элементов множества Х.

Почему функция, определённая в таком пространстве, по необходимости разрежена?

Проиллюстрируем это на простом примере, который мы позаимствуем из замечательной лекции Стивена Майера.

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

Итак, функция кодовой комбинации цифр -- открывать замок. В данном случае:

• А = {0,1,...,9}, |A| = 10.


• |Ω| = 10⁴.


• |T_f| = 1.


• I_f = 4 log₂10 ≈ 13.3 бит.

А теперь представим, что мы увеличили длину L строк на 1 символ, не меняя алфавита. То есть мы купили новый замок, длина кодовой комбинации которого не 4, а 5 цифр. Теперь у нас такая картина:

• |Ω| = 10⁵.


• |T_f| = 1 (число функциональных комбинаций не изменилось).


• I_f = 5 log₂10 ≈ 16.6 бит (количество функциональной информации возросло).

Число функциональных комбинаций осталось тем же самым, а размер пространства увеличился в |A| = 10 раз.

В случае сложных функций размер |T_f| целевого подпространства (то есть фактически число синонимов функциональной строки s) с ростом длины строки L растёт медленнее, чем взрывается размер |Ω| пространства возможных строк:

O(|T_f(L)|) < O(|Ω(L)|).

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

Кстати, Douglas Axe во время оно показал, что для белкового домена средних размеров (если не ошибаюсь, ~150 АА) отдельно взятого белкового семейства (beta-lactamase), редкость функциональных строк оценивается отношением 1 функциональная строка на каждые 10⁷⁷. Причём максимальное число организмов, когда-либо живших за всю историю биосферы, в предположениях, благоприятных для эволюционной парадигмы, Майер оценивает как 10⁴⁰ ≈ 2¹³³ (более оптимистичная для эволюции оценка GPuccio в 2¹⁴⁰ организмов отличается в 2⁷=128 раз). Если использовать оценку Майера, то получается, что доля состояний, которые теоретически могли быть просмотрены эволюцией, за всю её славную и неповторимую историю, в процессе поиска функциональной аминокислотной строки для фермента beta-lactamase, составляет 10⁴⁰/10⁷⁷ = 10^-37. Для осознания масштаба стоящих перед эволюцией задач надо иметь в виду, что размер протеома одноклеточной E.Coli оценивается в 1620-2260 различных типов белков. Как-то многовато для незатейливой схемы RV+NS...

Comments

[staerum.livejournal.com]

Это скорее опровержение мысли, что случайность надо понимать как равномерную. Если пространство структуры реальности неравномерно (а оно очевидно неравномерно), то брать всё пространство возможных строк для таких оценок не вполне корректно. Если взять клавиатуру, руки человека, привычки человека, то генерируемые им "случайные последовательности" будут иметь вполне заметные особенности и даже близко не покроют всё пространство возможных последовательностей равномерными примерами.

[mns2012]

Случайность и функция — две вещи несовместные.

[staerum.livejournal.com]

Контр-пример. rand()

Тут надо как-то обозначит границы этого утверждения. В общем случае это не так.

[mns2012]

Это называется спецификация. Кстати rand — это псевдослучайные числа, как известно. Pure randomness очень сложно получить (если вообще возможно).

[mns2012]

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

[mns2012]

Кстати, утверждение мое — иного плана. Из Randomness невозможно получить ничего функционального. Шум и функция — это антонимы.

[staerum.livejournal.com]

Скажите операторам дронов противника )

Случайность и целесообразность вещи ортогональные. Случайность это функция и ей есть место в реальности.

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

[mns2012]

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

[mns2012]

===Случайность это кроме прочего ещё и метод, я думаю вы прекрасно знаете метод стохастической оптимизации Монте-Карло.===

Ничего подобного. Функция в методе Монте-Карло определяет что и как нужно делать со случайными последовательностями. Сама эта функция отнюдь не случайна.

Википедия:

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

Garbage in -- garbage out.

[mns2012]

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

[staerum.livejournal.com]

Оптимизируемая функция не случайна, конечно. Случайность тут метод.

Но в реальности никто не говорит, что случайна оптимизируемая функция. Нет такой теории. Говорят о случайности как методе.

[mns2012]

С праздником Рождества Богородицы!

[staerum.livejournal.com]

Это вас с праздником! У нас ещё не наступил )

[mns2012]

Метод тоже не случаен отнюдь, даже если на каких-то этапах он предполагает использование случайных чисел или последовательностей.

Посмотрите вот эту статью

[staerum.livejournal.com]

Да, с этим я не спорю.

[mns2012]

Спасибо. Интересно, в какой вы timezone?

[staerum.livejournal.com]

UTC+3

[mns2012]

Тогда почему не наступил, когда у нас наступил (UTC+1)? Праздник с вечера начинается ведь )

[staerum.livejournal.com]

Точно, с вечерни же. Упускаю специфику.