진화 가능성(컴퓨터 과학)

이 기사는 주요 출처에 대한 언급에 너무 많이 의존하고 있다. 2차 또는 3차 소스를 추가하여 개선하십시오. (2016년 10월) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

진화 가능성이라는 용어는 레슬리 발리언트가 그의 동명의 논문에서 소개하고 아래에 기술한 최근의 컴퓨터 학습의 틀에 사용된다. 이 이론의 목적은 생물학적 진화를 모델링하고 진화가 가능한 메커니즘의 유형을 분류하는 것이다. 진화는 통계 질의에서 PAC 학습과 학습의 연장이다.

제너럴 프레임워크

$F{\displaystyle {}_{}}$ ${\displaystyle n_{}}$ $displaystyle F_{n}\,}$ 및$$ ${\displaystyle R_{}}$ n $displaystyle R_{n}\}$을(를) $n{\displaystyle }$ ${\$ 변수에$$ 대한 함수의 집합으로 두십시오$$. Given an ideal function ${\displaystyle f\in F_{n}}$, the goal is to find by local search a representation ${\displaystyle r\in R_{n}}$ that closely approximates ${\displaystyle f\,}$. This closeness is measured by the performance ${\displaystyle \operatorname {Perf} (f,r)}$ of $$${\displaystyle }$$f{\displaystyle }$ ${\$에 대한 r $[\$ r$\backslash ,\}.$

생물학계에서도 그렇듯이 유전자형과 표현형 사이에는 차이가 있다. 일반적으로 동일한 기능(페노타입)에 해당하는 다중 표현(유형)이 있을 수 있다. That is, for some ${\displaystyle r,r'\in R_{n}}$, with ${\displaystyle r\neq r'\,}$, still ${\displaystyle r(x)=r'(x)\,}$ for all ${\displaystyle x\in X_{n}}$. However, this need not be the case. 그때의 목표는 이상함수의 표현형식과 밀접하게 일치하는 표현을 찾는 것이며, 국소 탐색의 정신은 유전자형의 작은 변화만 허용하는 것이다. 표현 $r{\displaystyle }$ ${\$의 $N{\displaystyle (r}$) ${\$ 주변을 $r{\displaystyle }$ ${\$의 가능한 돌연변이의 집합으로 두십시오$$$.$

단순성을 위해 $X{\displaystyle {}_{}}$ ${\displaystyle n_{}}$=${\displaystyle }${${\displaystyle }$- ${\displaystyle 1}$,${\displaystyle 1}$ ${\displaystyle {}^{}}$ ${\displaystyle n^{}}$ $displaystyle X_{n}=\{-1\}^{n$의 부울 함수를 고려하고, ${\displaystyle {Dn}_{}}$ $displaystyle D_{n}\,$ .$이{\displaystyle {}_{}}$(가${\displaystyle ){}_{}}$ X ${\displaystyle n_{}}$ {\$displaystyle X_{n}$의 확률 분포가 되도록 하십시오$$$.$ 구체적으로 말하자면

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

Note that ${\displaystyle \operatorname {Perf} (f,r)=\operatorname {Prob} (f(x)=r(x))-\operatorname {Prob} (f(x)\neq r(x)).$$}}$ 일반적으로$$ 부울이 아닌 함수의 경우 어느 정도 관계가 있겠지만 그 성능이 함수가 동의할 확률과 직접 일치하지는 않을 것이다.

유기체의 일생 동안, 그것은 제한된 수의 환경만을 경험할 것이기 때문에, 그것의 성능을 정확히 결정할 수 없다. The empirical performance is defined by ${\displaystyle \operatorname {Perf} _{s}(f,r)={\frac {1}{s}}\sum _{x\in S}f(x)r(x),}$ where ${\displaystyle S\,}$ is a multiset of ${\displaystyle s\,}$ independent selections from ${\displaystyle X_{n}\,}$ according to ${\displaystyle D_{n}\,}$. If ${\displaystyle s\,}$ is large enough, evidently ${\displaystyle \operatorname {Perf} _{s}(f,r)}$ will be close to the actual performance ${\displaystyle \operatorname {Perf} (f,r)}$.

Given an ideal function ${\displaystyle f\in F_{n}}$, initial representation ${\displaystyle r\in R_{n}}$, sample size ${\displaystyle s\,}$, and tolerance ${\displaystyle t\,}$, the mutator ${\displaystyle \operatorname {Mut} (f,r,s,t)}$ is a random variable defined는 다음과 같다. 각 $r{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\displaystyle \in }$ ${\displaystyle N}$( ${\displaystyle r}$) ${\displaystyle$ r$'\in N(r)}$은 경험적 성과에 따라 유익성, 중립성 또는 유해성으로 분류된다$$. 구체적으로 말하자면

• ${\displaystyle r^{}}$ ${\displaystyle {\prime }^{}}$ $displaystyle$ r$'\,}$은(는${\displaystyle )}$ ${\displaystyle {\mathrm{Perf}}_{}}$ ${\displaystyle s_{}}$ ${\displaystyle {}_{}(f}$,${\displaystyle }$r${\displaystyle }$)${\displaystyle }$- ${\displaystyle {Perf}_{}}$ ${\displaystyle \operatorname {s} _{s}(f,r$')$_{s$}(f$,r)\geq t$인 경우 유익한 돌연변이다$$.
• ${\displaystyle r^{}}$ ${\displaystyle {\prime }^{}}$ $displaystyle r'\,}$은는) - t< , r )- ( , )< t ${\displaystyle -t<\operf} _{s,r'-\operatorname {Perf} _{s}(f,r$);$r$
• ${\displaystyle r^{}}$ ${\displaystyle {\prime }^{}}$ $displaystyle$ r$'\,}$은(는${\displaystyle )}$ ${\displaystyle {\mathrm{Perf}}_{}}$ ${\displaystyle s_{}}$ ${\displaystyle {}_{}}$(${\displaystyle f,}$ ${\displaystyle r}$)${\displaystyle }$- ${\displaystyle {\mathrm{perf}}_{}(f,}$ r ) ${\displaystyle \le }$- t ${\display$ style $\operatorname {s} _{s}(f$,r)\$s(f,r)\leq -t$

유익한 돌연변이가 있다면 ${\displaystyle \mathrm{Mut}}$mut${\displaystyle }$(${\displaystyle f}$, r${\displaystyle }$, ${\displaystyle s}$, ${\displaystyle t}$) ${\displaystyle \operatorname {Mut} (f,r,s,t)}$은(는) 임의로 이들 중 하나와 같다$$. 유익한 돌연변이가 없다면 ${\displaystyle \mathrm{Mut}}$mut${\displaystyle }$(${\displaystyle f}$, r${\displaystyle }$, ${\displaystyle s}$, ${\displaystyle t}$) ${\displaystyle \operatorname {Mut} (f,r,s,t)}$은 임의의 중립 돌연변이와 같다. 생물학과의 유사성에 비추어 볼 $때{\displaystyle }$ r ${\$ 그$$ 자체는 돌연변이로 이용할 수 있어야 하므로, 항상 적어도 하나의 중립 돌연변이가 있을 것이다.

이 정의의 의도는 진화의 각 단계에서 현재 게놈의 가능한 모든 돌연변이를 환경에서 시험한다는 것이다. 번성하거나 적어도 살아남는 사람들 중에서 다음 단계의 후보자로 선택된다. Given ${\displaystyle r_{0}\in R_{n}}$, we define the sequence ${\displaystyle r_{0},r_{1},r_{2},\ldots }$ by ${\displaystyle r_{i+1}=\operatorname {Mut} (f,r_{i},s,t)}$. Thus ${\displaystyle r_{g}\,}$ is a random variable $r{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ $displaystyle r_{0}\,}$이(가) $g{\displaystyle }$ ${\$ g$\,}$세대로 진화한 것을 나타낸다.

Let ${\displaystyle F\,}$ be a class of functions, ${\displaystyle R\,}$ be a class of representations, and ${\displaystyle D\,}$ a class of distributions on ${\displaystyle X\,}$. We say that ${\displaystyle F\,}$ is evolvable by ${\displaystyle R\,}$ over ${\displaystyle D\,}$ if therE다항식 p{\displaystyle p(\cdot ,\cdot)}(⋅, ⋅), s(⋅, ⋅){\displaystyle s(\cdot ,\cdot)}, 터(⋅, ⋅){\displaystyle t(\cdot ,\cdot)}, g(⋅, ⋅){\displaystyle g(\cdot ,\cdot)}가 모든 n{\displaystyle n\,}과 모든ϵ>0{\displaystyle \epsilon>0\,}, f가 존재하또는 모든 이상적인 함수 $f{\displaystyle }$ ${\displaystyle \in }$ F ${\displaystyle n_{}}$ ${\$ 및$$ 표현 $r{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle R_{}}$ n ${\$ 최소 $1{\displaystyle \mathrm{}}$ -${\displaystyle ϵ}$ ${\$

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

where the sizes of neighborhoods ${\displaystyle N(r)\,}$ for ${\displaystyle r\in R_{n}\,}$ are at most ${\displaystyle p(n,1/\epsilon )\,}$, the sample size is ${\displaystyle s(n,1/\epsilon )\,}$, the tolerance is ${\displaystyle t(1/n,\ep$$silon )\,}$, , 생성 크기는 $g{\displaystyle }$(${\displaystyle n,}$ ${\displaystyle 1}$/ ${\displaystyle ϵ}$) ${\$ 입니다$.$

${\displaystyle }$$F{\displaystyle }$ ${\$은(는) $일부{\displaystyle }$ R {\$displaystyle$R$\,}$에$$의해 D {\$displaystyle$ $D\,}$에 대해 진화가 가능한 경우$$ D ${\$ D\,}에 대해 진화가 가능하다$.$

${\displaystyle F}$ {\$displaystyle$ F$\,}$은(는) 모든 분포 $D{\displaystyle }$ ${\$에 걸쳐 진화가 가능한 경우 진화가 가능하다$.$

결과.

접속사 등급과 분리 등급은 각각 짧은 접속사 및 분리에 대한 균일한 분포에 걸쳐 진화가 가능하다.

패리티 함수의 클래스(특정 리터럴 부분집합에서 참 리터럴 수의 패리티로 평가)는 균일한 분포에서도 진화가 불가능하다.

진화 가능성은 PAC 학습 가능성을 의미한다.

참조

1. Valiant, L. G. (2006), Evolvability, ECCC TR06-120.