Эволюционность (информатика)

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

Общие рамки

Позволять $F_{n}\,$ и $R_{n}\,$ быть коллекциями функций на $n\,$ переменные. Учитывая идеальную функцию $f\in F_{n}$, цель состоит в том, чтобы локальным поиском найти представление $r\in R_{n}$ что близко приближается $f\,$. Эта близость измеряется производительностью $\operatorname {Perf} (f,r)$ из $r\,$ относительно $f\,$.

Как и в биологическом мире, существует разница между генотипом и фенотипом. В общем, может быть несколько представлений (генотипов), соответствующих одной и той же функции (фенотипу). То есть для некоторых $r,r'\in R_{n}$, с $r\neq r'\,$, все еще $r(x)=r'(x)\,$ для всех $x\in X_{n}$. Однако это не обязательно так. Таким образом, цель состоит в том, чтобы найти представление, которое точно соответствует фенотипу идеальной функции, а дух локального поиска состоит в том, чтобы допустить лишь небольшие изменения в генотипе. Пусть окрестности $N(r)\,$ представительства $r\,$ быть набором возможных мутаций $r\,$.

Для простоты рассмотрим булевы функции на $X_{n}=\{-1,1\}^{n}\,$, и пусть $D_{n}\,$ быть распределением вероятностей на $X_{n}\,$. Определите производительность с этой точки зрения. Конкретно,

$\operatorname {Perf} (f,r)=\sum _{x\in X_{n}}f(x)r(x)D_{n}(x).$

Обратите внимание, что $\operatorname {Perf} (f,r)=\operatorname {Prob} (f(x)=r(x))-\operatorname {Prob} (f(x)\neq r(x)).$ В общем, для небулевых функций производительность не будет напрямую соответствовать вероятности согласования функций, хотя она будет иметь некоторую взаимосвязь.

На протяжении всей жизни организм испытывает лишь ограниченное количество сред, поэтому его работоспособность не может быть точно определена. Эмпирическая эффективность определяется $\operatorname {Perf} _{s}(f,r)={\frac {1}{s}}\sum _{x\in S}f(x)r(x),$ где $S\,$ представляет собой мультимножество $s\,$ независимый выбор из $X_{n}\,$ в соответствии с $D_{n}\,$. Если $s\,$ достаточно велик, очевидно $\operatorname {Perf} _{s}(f,r)$ будет близок к реальной производительности $\operatorname {Perf} (f,r)$.

Учитывая идеальную функцию $f\in F_{n}$, исходное представление $r\in R_{n}$, размер выборки $s\,$и толерантность $t\,$, мутатор $\operatorname {Mut} (f,r,s,t)$ является случайной величиной, определяемой следующим образом. Каждый $r'\in N(r)$ классифицируется как полезный, нейтральный или вредный, в зависимости от его эмпирической эффективности. Конкретно,

• $r'\,$ является полезной мутацией, если $\operatorname {Perf} _{s}(f,r')-\operatorname {Perf} _{s}(f,r)\geq t$;
• $r'\,$ является нейтральной мутацией, если $-t<\operatorname {Perf} _{s}(f,r')-\operatorname {Perf} _{s}(f,r)<t$;
• $r'\,$ является вредной мутацией, если $\operatorname {Perf} _{s}(f,r')-\operatorname {Perf} _{s}(f,r)\leq -t$.

Если есть какие-то полезные мутации, то $\operatorname {Mut} (f,r,s,t)$ равно одному из них в случайном порядке. Если нет полезных мутаций, то $\operatorname {Mut} (f,r,s,t)$ равно случайной нейтральной мутации. Ввиду сходства с биологией, $r\,$ сам по себе должен быть доступен в виде мутации, поэтому всегда будет хотя бы одна нейтральная мутация.

Смысл этого определения состоит в том, что на каждом этапе эволюции все возможные мутации текущего генома проверяются в окружающей среде. Из тех, кто преуспевает или, по крайней мере, выживает, один выбирается кандидатом на следующий этап. Данный $r_{0}\in R_{n}$, определим последовательность $r_{0},r_{1},r_{2},\ldots$ к $r_{i+1}=\operatorname {Mut} (f,r_{i},s,t)$. Таким образом $r_{g}\,$ это случайная величина, представляющая то, что $r_{0}\,$ развился до того, как $g\,$ поколения .

Позволять $F\,$ быть классом функций, $R\,$ быть классом представлений, и $D\,$ класс распределений на $X\,$. Мы говорим, что $F\,$ развивается путем $R\,$ над $D\,$ если существуют полиномы $p(\cdot ,\cdot )$, $s(\cdot ,\cdot )$, $t(\cdot ,\cdot )$, и $g(\cdot ,\cdot )$ такой, что для всех $n\,$ и все $\epsilon >0\,$, для всех идеальных функций $f\in F_{n}$ и представления $r_{0}\in R_{n}$, с вероятностью по крайней мере $1-\epsilon \,$,

$\operatorname {Perf} (f,r_{g(n,1/\epsilon )})\geq 1-\epsilon ,$

где размеры окрестностей $N(r)\,$ для $r\in R_{n}\,$ самое большее $p(n,1/\epsilon )\,$, размер выборки $s(n,1/\epsilon )\,$, толерантность $t(1/n,\epsilon )\,$, а размер поколения равен $g(n,1/\epsilon )\,$.

$F\,$ эволюционирует над $D\,$ если это может быть развито некоторыми $R\,$ над $D\,$.

$F\,$ является развиваемым, если оно эволюционирует по всем распределениям $D\,$.

Результаты

Класс конъюнкций и класс дизъюнкций развиваются по равномерному распределению для коротких конъюнкций и дизъюнкций соответственно.

Класс функций четности (которые оценивают четность количества истинных литералов в заданном подмножестве литералов) не поддается развитию даже для равномерного распределения.

Эволюционность подразумевает обучаемость PAC .

Ссылки

1. Валиант, LG (2006), Эволюция , ECCC   TR06-120 .