Vyvinutelnost (počítačová věda) - Evolvability (computer science)

Termín vyvíjitelnost se používá pro nedávný rámec výpočetního učení zavedený Leslie Valiant ve svém příspěvku se stejným názvem a popsaném níže. Cílem této teorie je modelovat biologickou evoluci a kategorizovat, které typy mechanismů jsou vyvíjitelné. Evoluce je rozšířením PAC učení a učit se ze statistických dotazů.

Obecný rámec

Nechat ${displaystyle F_ {n},}$ a ${displaystyle R_ {n},}$ být kolekce funkcí na ${displaystyle n,}$ proměnné. Vzhledem k ideální funkce ${displaystyle fin F_ {n}}$ , cílem je najít pomocí místního vyhledávání a zastoupení ${displaystyle rin R_ {n}}$ který se blíží ${displaystyle f,}$ . Tato blízkost se měří pomocí výkon ${displaystyle operatorname {Perf} (f, r)}$ z ${displaystyle r,}$ s ohledem na ${displaystyle f,}$ .

Stejně jako v biologickém světě existuje rozdíl mezi genotypem a fenotypem. Obecně může existovat více reprezentací (genotypů), které odpovídají stejné funkci (fenotyp). To je pro některé ${displaystyle r, r'in R_ {n}}$ , s ${displaystyle req r ',}$ , ještě pořád ${displaystyle r (x) = r '(x),}$ pro všechny ${displaystyle xin X_ {n}}$ . To však nemusí být pravda. Cílem pak je najít reprezentaci, která se velmi podobá fenotypu ideální funkce, a duchem lokálního hledání je umožnit pouze malé změny v genotypu. Nech sousedství ${displaystyle N (r),}$ reprezentace ${displaystyle r,}$ být soubor možných mutací ${displaystyle r,}$ .

Pro jednoduchost zvažte booleovské funkce ${displaystyle X_ {n} = {- 1,1} ^ {n},}$ a nechte ${displaystyle D_ {n},}$ být rozdělení pravděpodobnosti na ${displaystyle X_ {n},}$ . Definujte výkon v tomto smyslu. Konkrétně

{displaystyle operatorname {Perf} (f, r) = součet _ {xin X_ {n}} f (x) r (x) D_ {n} (x).}

Všimněte si, že ${displaystyle operatorname {Perf} (f, r) = operatorname {Prob} (f (x) = r (x)) - operatorname {Prob} (f (x) eq r (x)).}$ Obecně platí, že u jiných než booleovských funkcí nebude výkon přímo odpovídat pravděpodobnosti, že se funkce dohodnou, i když bude mít určitý vztah.

Během života organismu zažije pouze omezený počet prostředí, takže jeho výkon nelze přesně určit. The empirický výkon je definováno ${displaystyle operatorname {Perf} _ {s} (f, r) = {frac {1} {s}} součet _ {xin S} f (x) r (x),}$ kde ${displaystyle S,}$ je multiset z ${displaystyle s,}$ nezávislé výběry z ${displaystyle X_ {n},}$ podle ${displaystyle D_ {n},}$ . Li ${displaystyle s,}$ je zjevně dostatečně velká ${displaystyle operatorname {Perf} _ {s} (f, r)}$ bude blízký skutečnému výkonu ${displaystyle operatorname {Perf} (f, r)}$ .

Vzhledem k ideální funkci ${displaystyle fin F_ {n}}$ , počáteční reprezentace ${displaystyle rin R_ {n}}$ , velikost vzorku ${displaystyle s,}$ , a tolerance ${displaystyle t,}$ , mutátor ${displaystyle operatorname {Mut} (f, r, s, t)}$ je náhodná proměnná definovaná následovně. Každý ${displaystyle r'in N (r)}$ je klasifikován jako prospěšný, neutrální nebo škodlivý v závislosti na jeho empirickém výkonu. Konkrétně

${displaystyle r ',}$ je prospěšná mutace, pokud ${displaystyle operatorname {Perf} _ {s} (f, r ') - operatorname {Perf} _ {s} (f, r) geq t}$ ;
${displaystyle r ',}$ je neutrální mutace, pokud ${displaystyle -t$ ;
${displaystyle r ',}$ je škodlivá mutace, pokud ${displaystyle operatorname {Perf} _ {s} (f, r ') - operatorname {Perf} _ {s} (f, r) leq -t}$ .

Pokud existují nějaké prospěšné mutace, pak ${displaystyle operatorname {Mut} (f, r, s, t)}$ se rovná jednomu z těchto náhodně. Pokud neexistují žádné prospěšné mutace, pak ${displaystyle operatorname {Mut} (f, r, s, t)}$ se rovná náhodné neutrální mutaci. S ohledem na podobnost s biologií ${displaystyle r,}$ sama o sobě musí být dostupná jako mutace, takže vždy bude existovat alespoň jedna neutrální mutace.

Záměrem této definice je, aby v každé fázi evoluce byly v prostředí testovány všechny možné mutace současného genomu. Z těch, kterým se daří nebo alespoň přežívá, je jeden vybrán jako kandidát do další fáze. Dáno ${displaystyle r_ {0} v R_ {n}}$ , definujeme sekvenci ${displaystyle r_ {0}, r_ {1}, r_ {2}, ldots}$ podle ${displaystyle r_ {i + 1} = operatorname {Mut} (f, r_ {i}, s, t)}$ . Tím pádem ${displaystyle r_ {g},}$ je náhodná proměnná představující co ${displaystyle r_ {0},}$ se vyvinul do ${displaystyle g,}$ generace.

Nechat ${displaystyle F,}$ být třídou funkcí, ${displaystyle R,}$ být třídou zastoupení a ${displaystyle D,}$ třída distribucí na ${displaystyle X,}$ . Říkáme to ${displaystyle F,}$ je vyvíjející se ${displaystyle R,}$ přes ${displaystyle D,}$ pokud existují polynomy ${displaystyle p (cdot, cdot)}$ , ${displaystyle s (cdot, cdot)}$ , ${displaystyle t (cdot, cdot)}$ , a ${displaystyle g (cdot, cdot)}$ takové, že pro všechny ${displaystyle n,}$ a všechno ${displaystyle epsilon> 0,}$ , pro všechny ideální funkce ${displaystyle fin F_ {n}}$ a reprezentace ${displaystyle r_ {0} v R_ {n}}$ alespoň s pravděpodobností ${displaystyle 1-epsilon,}$ ,

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

kde jsou velikosti čtvrtí ${displaystyle N (r),}$ pro ${displaystyle rin R_ {n},}$ jsou nanejvýš ${displaystyle p (n, 1 / epsilon),}$ , velikost vzorku je ${displaystyle s (n, 1 / epsilon),}$ , tolerance je ${displaystyle t (1 / n, epsilon),}$ a velikost generace je ${displaystyle g (n, 1 / epsilon),}$ .

${displaystyle F,}$ je evoluční ${displaystyle D,}$ pokud je některými vyvíjitelný ${displaystyle R,}$ přes ${displaystyle D,}$ .

${displaystyle F,}$ je vyvíjející se pokud je vyvíjitelný ve všech distribucích ${displaystyle D,}$ .

Výsledek

Třída spojek a třída disjunkcí jsou vyvíjeny přes jednotné rozdělení pro krátké spojky a disjunkce.

Třída paritních funkcí (které se hodnotí na paritu počtu skutečných literálů v dané podmnožině literálů) nelze vyvíjet, a to ani pro jednotné rozdělení.

Evoluční schopnost znamená Učitelnost PAC.

Reference

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