Эволюционируемость (информатика) - Evolvability (computer science)

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

Общие рамки

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

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

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

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

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

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

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

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

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

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

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

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

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

${displaystyle F,}$ является может развиваться ${displaystyle D,}$ если это может развиться некоторыми ${displaystyle R,}$ над ${displaystyle D,}$.

${displaystyle F,}$ является эволюционируемый если он может развиваться по всем дистрибутивам ${displaystyle D,}$.

Полученные результаты

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

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

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

Рекомендации

1. Валиант, Л.Г. (2006), Эволюционируемость, ECCC  TR06-120.