Estimation of Distribution Algorithms
Petr Pošík
Prezentace pro předmětKognitivní procesy
6. dubna 2006
Úvod
Machine Learning & Softcomputing3 / XX
Black-box optimalizace (BBO)Black-box optimalizace (BBO)
Optimalizace typu „černá skříňka“:
Vstupy: Jak vypadají potenciální řešení problému? Jak se ohodnocuje kvalita potenciálního řešení?
Výstup: Co nejlepší řešení (ve smyslu ohodnocení)
Apriorní znalosti o hodnotící funkci: žádné! může být nediferencovatelná, nespojitá,
mulitmodální, zašuměná, můžeme mít několik měřítek kvality (i protichůdných), ...
Úvod >
Machine Learning & Softcomputing4 / XX
Řešení BBOŘešení BBO
Hill-climbing, simulované žíhání, ...
Genetické algoritmy (GA) jsou skvělé, ale mohly by být ještě lepší!
GA jsou oblíbené, protože se snadno používají, lze je aplikovat bez apriorních znalostí, lze je snadno paralelizovat, ...
Problémy s tradičními operátory GA adaptace (mohly by problém řešit, ale nevyřeší) flexibilita (složité interakce)
Úvod >
Machine Learning & Softcomputing5 / XX
Genetický algoritmusGenetický algoritmus
1. Initialization: Inicializuj a ohodnoť populaci
2. Selection: Vyber rodiče
3. Crossover: Proveď křížení
4. Mutation: Proveď mutaci
5. Evalutation: Ohodnoť potomky
6. Replacement: Zařaď potomky do populace
7. Go to 2.
Úvod >
Machine Learning & Softcomputing6 / XX
Rekombinace Rekombinace Pravděpodobnostní modelPravděpodobnostní model
Nepoužívejte jednobodové nebo rovnoměrné křížení...
Naučte pstní model a vzorkujte z něj! vyšší flexibilita schopnost adaptace
Estimation of Distribution Algorithms (EDAs) přesně tohle dělají!
Úvod >
Machine Learning & Softcomputing7 / XX
Estimation of Distribution AlgorithmEstimation of Distribution Algorithm
1. Initialization: Inicializuj a ohodnoť populaci
2. Selection: Vyber rodiče
3. Learning: Nauč se pstní model
4. Sampling: Navzorkuj potomky z modelu
5. Evalutation: Ohodnoť potomky
6. Replacement: Zařaď potomky do populace
7. Go to 2.
Úvod >
Machine Learning & Softcomputing8 / XX
NázvyNázvy
EDAs mají různé názvy: EDAs
Estimation of Distribution AlgorithmsAlgoritmy odhadující rozdělení
PMBGAsProbabilistic Model-Building Genetic AlgorithmsGenetické algoritmy vytvářející pravděpodobnostní modely
IDEAsIterated Density Estimation AlgorithmsAlgoritmy s iterovaným odhadováním rozdělení
Úvod >
Machine Learning & Softcomputing9 / XX
Obsah přednášekObsah přednášek
1. EDAs pro vektory diskrétních hodnot (např. binární)
Motivační příklad Bez interakcí Párové interakce Vyšší interakce
2. EDAs pro vektory reálných čísel Evoluční strategie Histogramy Gaussovo rozdělení a jeho směsi
Úvod >
EDA pro binární řetězce
Machine Learning & Softcomputing11 / XX
Motivační příkladMotivační příklad
5-bitový OneMax problém Optimum: 11111, fitness: 5
Algoritmus: Univariate Marginal Distribution Alg. (UMDA) Velikost populace: N=6 Párová turnajová selekce Model: vektor pravděpodobností
každý je pravděpodobnost, že se na daném místě nachází 1
Učení modelu: vypočti ze slibných řešení
Vzorkování z modelu: vygeneruj 1 na d-té pozici s pstí
Binární řetězce >
Dppp ,,1 dp
p
dp
Machine Learning & Softcomputing12 / XX
SelekceSelekce
Binární řetězce > Motivační příklad
11001 (3)00010 (1)11101 (4)10111 (4)00001 (1)10010 (2)
Původní populace
11101 (4) vs. 10111 (4)10111 (4) vs. 11101 (4) 11101 (4) vs. 00001 (1)10010 (2) vs. 00010 (1)00010 (1) vs. 00010 (1)00010 (1) vs. 11001 (3)
Vybrané turnaje
Machine Learning & Softcomputing13 / XX
RekombinaceRekombinace
Binární řetězce > Motivační příklad
11101 (4)10111 (4)11101 (4)10010 (2)00010 (1)11001 (3)
Vybraní rodiče
10100 (2) 10101 (3)11011 (4) 00011 (2)10001 (2)10011 (3)
Populace potomků
5 3 3 3 4- - - - -6 6 6 6 6
Pravděpodobnostní vektor
Vzorkování
Machine Learning & Softcomputing14 / XX
„1“ jsou průměrně lepší než „0“...... selekce zvyšuje podíl „1“
Rekombinace zachovává a kombinuje „1“...... podíl „1“ v průběhu času stoupá
Když máme hodně „1“ v populaci, nemůžeme optimum minout
Chování UMDA pro OneMax problémChování UMDA pro OneMax problém
Binární řetězce > Motivační příklad
Machine Learning & Softcomputing15 / XX
UMDA a 50-bitový OneMax problémUMDA a 50-bitový OneMax problém
Binární řetězce > Motivační příklad
Machine Learning & Softcomputing16 / XX
UMDA a UMDA a DD-bitový OneMax problém-bitový OneMax problém
Binární řetězce > Motivační příklad
Počet ohodnocení pro spolehlivou konvergenci:
UMDA:
Ostatní: Hill-climber: GA s rovnoměrným křížením: přibl. GA s 1-bodovým křížením: o trochu pomalejší
UMDA se chová přibližně stejně jako GA s rovnoměrným křížením!
DDO ln
DDO ln DDO ln
Machine Learning & Softcomputing17 / XX
Bude to fungovat vždycky?Bude to fungovat vždycky?
Binární řetězce > Motivační příklad
Asi vás zklamu, ale nebude.
Problém: Spojené 5-bitové pastičky
Pastička je definována jako
),,,,(),,,,( 10987654321 xxxxxtrapxxxxxtrapf
jinakxones
xonespokudxtrap
)(4
5)(5)(
Machine Learning & Softcomputing18 / XX
5-bitová pastička5-bitová pastička
Binární řetězce > Motivační příklad
Machine Learning & Softcomputing19 / XX
UMDA selhává na spojených pastičkáchUMDA selhává na spojených pastičkách
Binární řetězce > Motivační příklad
OneMax Optimum v bodě 1111...1 „1“ jsou průměrně lepší než „0“
Pastičky Optimum v bodě 1111...1 Ale
Jednorozměrné psti vedou GA špatným směrem!
Exponenciálně se zvyšující velikost populace, jinak GA nenalezne optimum!
375.1*)***1(
2*)***0(
trap
trap
Machine Learning & Softcomputing20 / XX
UMDA a 10 5-bitových pastičekUMDA a 10 5-bitových pastiček
Binární řetězce > Motivační příklad
Machine Learning & Softcomputing21 / XX
Jak to napravit?Jak to napravit?
Binární řetězce > Motivační příklad
Pastička je klamná funkce: Statistiky nad 1**** a 0**** nevedou k cíli Podobně i statistiky na 11*** a 00***, 111** a
000**, 1111* a 0000*
Ale: ... 11111 bude průměrně lepší než 00000
5-bitové statistiky by pro 5-bitové pastičky měly fungovat stejně, jako 1-bitové statistiky pro OneMax problém
)11111()00000( traptrap
Machine Learning & Softcomputing22 / XX
Řešení spojených pastičekŘešení spojených pastiček
Binární řetězce > Motivační příklad
Připomeňme:
Učení modelu: pro všechny pětice bitů zvlášť vypočítat p(00000), p(00001), ... , p(11111)
Vzorkování Každá pětice se generuje nezávisle Vygeneruj 00000 s pstí p(00000), 00001 s pstí
p(00001), atd.
),,,,(),,,,( 10987654321 xxxxxtrapxxxxxtrapf
),,,,( 54321 xxxxx
Machine Learning & Softcomputing23 / XX
Dobré statistiky a pastičky jsou snadnéDobré statistiky a pastičky jsou snadné
Binární řetězce > Motivační příklad
Machine Learning & Softcomputing24 / XX
Dobré zprávyDobré zprávy
Binární řetězce > Motivační příklad
Dobré statistiky fungují skvěle! Optimum nalezeno za ohodnocení Stejné jako u OneMax problému
Ostatní: Hill-climber: , k=5 GA s rovnoměrným křížením: přibl. GA s 1-bodovým křížením: podobně jako s
rovnoměrným křížením
)ln( DDO
)ln( DDO k
)2( DO
Machine Learning & Softcomputing25 / XX
Co stojí před námi?Co stojí před námi?
Binární řetězce > Motivační příklad
Pokud budeme umět najít dobré statistiky s malou režií a využít je v rámci UMDA,
pak budeme umět řešit separabilní problémy řádu k za maximálně O(D2) ohodnocení a takových problémů není málo
Řešení problému se úzce vztahuje k tzv. linkage learning, tj. hledání vazeb mezi proměnnými
Machine Learning & Softcomputing26 / XX
Diskrétní EDAs: přehledDiskrétní EDAs: přehled
Binární řetězce >
1. Přehled1. Jednorozměrné (bez interakcí)2. Dvojrozměrné (párové interakce)3. Mnoharozměrné (interakce vyšších řádů)
2. Závěry a praktická doporučení
Machine Learning & Softcomputing27 / XX
EDAs bez interakcíEDAs bez interakcí
Binární řetězce >
1. Population-based incremental learning (PBIL) Baluja, 1994
2. Univariate marginal distribution alg. (UMDA) Muehlenbein, Paass, 1996
3. Compact genetic algorithm (cGA) Harik, Lobo, Goldberg, 1998
Machine Learning & Softcomputing28 / XX
PorovnáníPorovnání
Binární řetězce > Bez interakcí
Podobnosti: všechny používají vektor pravděpodobností
Rozdíly: PBIL a cGA nepoužívají populaci, jen vektor p;
UMDA používá populaci PBIL a cGA používají odlišná pravidla pro
adaptaci vektoru p
Machine Learning & Softcomputing29 / XX
SouhrnSouhrn
Binární řetězce > Bez interakcí
Výhody: Jednoduchost Rychlost Jednoduše se simulují veliké populace
Omezení Spolehlivě řeší pouze problémy rozložitelné na
podproblémy řádu 1
Machine Learning & Softcomputing30 / XX
Diskrétní EDAs: přehledDiskrétní EDAs: přehled
Binární řetězce >
1. Přehled1. Jednorozměrné (bez interakcí)2. Dvojrozměrné (párové interakce)3. Mnoharozměrné (interakce vyšších řádů)
2. Závěry a praktická doporučení
Machine Learning & Softcomputing31 / XX
Od jednotlivých bitů k párovým modelůmOd jednotlivých bitů k párovým modelům
Binární řetězce > Párové interakce
Jak posuzovat dvě pozice dohromady?
Dát je do souvislosti pomocí závislosti
A B
A B
),( BAp
)(Ap
)(
),()|(
AP
BAPABp
Machine Learning & Softcomputing32 / XX
Příklad párového modelu: strom závislostíPříklad párového modelu: strom závislostí
Binární řetězce > Párové interakce
Dependency tree
Uzly jsou jednotlivé binární proměnné (pozice chromozomu)
Hrany vyjadřují závislost mezi proměnnými
Vlastnosti:1. Každý uzel závisí maximálně na 1 dalším uzlu2. Graf neobsahuje cykly3. Graf je souvislý
Machine Learning & Softcomputing33 / XX
Učení struktury stromu závislostíUčení struktury stromu závislostí
Binární řetězce > Párové interakce
Významnost hrany = vzájemná informace
Algoritmus pro hledání maximální kostry grafu (Prim, 1957)1. Ohodnoťte hrany vzájemnou informací
2. Začněte stavět strom z libovolného uzlu3. K hranám a uzlům již zařazeným do kostry
přidejte vždy ten uzel, který je k nim připojen nejlépe ohodnocenou hranou
yx ypxp
yxpyxpYXI
, )()(
),(log),(),(
Machine Learning & Softcomputing34 / XX
Strom závislostí: Příklad 1Strom závislostí: Příklad 1
Binární řetězce > Párové interakce
Machine Learning & Softcomputing35 / XX
Strom závislostí: pravděpodobnostiStrom závislostí: pravděpodobnosti
Binární řetězce > Párové interakce
)( 1Xp
)|( 14 XXp
)|( 45 XXp
)|( 23 XXp
)|( 42 XXp
Machine Learning & Softcomputing36 / XX
Algoritmy s modely párových interakcíAlgoritmy s modely párových interakcí
Binární řetězce > Párové interakce
1. MIMIC Mutual Information Maximization for
Input Clustering de Bonet et al., 1996 Řetězce
2. COMIT Combining Optimizers with Mutual
Information Trees Baluja & Davies, 1997 Stromy
3. BMDA Bivariate Marginal Distribution
Algorithm Pelikan & Muehlenbein, 1998 Lesy
Machine Learning & Softcomputing37 / XX
ShrnutíShrnutí
Binární řetězce > Párové interakce
Výhody Stále ještě jednoduchost Stále ještě rychlost Umí se něco naučit o struktuře
Omezení Spolehlivě řeší pouze problémy rozložitelné na
podproblémy maximálně řádu 2
Machine Learning & Softcomputing38 / XX
Diskrétní EDAs: přehledDiskrétní EDAs: přehled
Binární řetězce >
1. Přehled1. Jednorozměrné (bez interakcí)2. Dvojrozměrné (párové interakce)3. Mnoharozměrné (interakce vyšších řádů)
2. Závěry a praktická doporučení
Machine Learning & Softcomputing39 / XX
Extended Compact GAExtended Compact GA
Binární řetězce > Interakce vyšších řádů
ECGA (Harik, 1999)
Využívá tzv. součin marginálních modelů (MPM) Skupiny proměnných jsou považovány za celky Skupiny se hledají adaptivně v průběhu evoluce Skupiny jsou považovány za vzájemně nezávislé Každá skupina se modeluje sdruženou hustotou psti OneMax: [1][2][3][4][5][6][7][8][9][10] Trap: [1 2 3 4 5][6 7 8 9 10]
Machine Learning & Softcomputing40 / XX
ECGAECGA: U: Učení strukturyčení struktury
Binární řetězce > Interakce vyšších řádů
Dvě součásti1. Hodnotící metrika:
Minimum Description Length (MDL)2. Prohledávací procedura: Hladový algoritmus
Prohledávací procedura Začíná se skupinami o 1 proměnné (1 bitu)
jako PBIL Provede spojení dvou skupin, které přinese
největší užitek Končí, pokud žádné spojení není užitečné
Machine Learning & Softcomputing41 / XX
ECGAECGA: : Hodnocení strukturyHodnocení struktury
Binární řetězce > Interakce vyšších řádů
MDL: minimální délka popisu Minimalizuj počet bitů potřebných k uložení modelu a dat
Délka popisu modelu: Každá skupina g má |g| rozměrů, tj. 2|g| četností, které mohou
nabývat hodnoty až N
Délka popisu populace při daném modelu: Definována pomocí entropie marginálních distribucí, Xg je |g|-
rozměrný náhodný vektor, xg je jeho realizace
DataModel DLDLDataModelDL ),(
Gg
gModel NDL )12(log
Gg x
ggggGg
gData
g
xXpxXpNXhNDL )(log)()(
Machine Learning & Softcomputing42 / XX
Bayesian Optimization AlgorithmBayesian Optimization Algorithm
Binární řetězce > Interakce vyšších řádů
BOA (Pelikan, Goldberg, Cantú-Paz, 1998)
Využívá Bayesovské sítě Podmíněné závislosti místo skupin Řetězec, strom, les – spec. případy Bayes. sítí Trap:
Stejný model byl nezávisle použit také v: EBNA – Estimation of Bayesian Network Alg. (Etxeberria et al.,
1999) LFDA – Learning Factorized Density Alg. (Muehlenbein et al., 1999)
Machine Learning & Softcomputing43 / XX
BOABOA: U: Učení strukturyčení struktury
Binární řetězce > Interakce vyšších řádů
Dvě součásti1. Hodnotící metrika:
Bayesian-Dirichlet nebo Bayes. inf. kritérium (BIC)
2. Prohledávací procedura: Hladový algoritmus
Prohledávací procedura Začni s prázdným grafem Aplikuj tu z následujících operací, která nejvíc
zlepšuje hodnocení (skonči, pokud nelze zlepšit) Přidej hranu
Odstraň hranu
Otoč hranu
Machine Learning & Softcomputing44 / XX
BOABOA: : VlastnostiVlastnosti
Binární řetězce > Interakce vyšších řádů
Teorie (Pelikan, Goldberg, Harik a další): Velikost populace:
Počáteční přísun, správné rozhodnutí mezi část. řešeními, drift, učení modelu
Počet generací do konvergence Rovnoměrné a exponenciální škálování
BOA řeší problémy rozložitelné na podproblémy řádu k za méně než O(D2) ohodnocení!
)()( 05.1DOažDON
)()( 5.0 DOažDOI
)()( 255.1 DOažDOnevals
Machine Learning & Softcomputing45 / XX
Porovnání modelůPorovnání modelů
Binární řetězce > Interakce vyšších řádů
BMDA ECGA BOA, EBNA, LFDA
Flexibilita modelů se zvyšuje
Machine Learning & Softcomputing46 / XX
SouhrnSouhrn
Binární řetězce > Interakce vyšších řádů
Modely Bayesovské sítě jsou nejobecnější Mnoharozměrné modely se hůře učí Jsou ovšem mnohem schopnější
Omezení Řeší problémy rozložitelné na podproblémy
omezeného řádu Neumí uspokojivě řešit problémy, které nejsou
rozložitelné na podproblémy logaritmické velikosti
Machine Learning & Softcomputing47 / XX
Doporučení pro diskrétní EDADoporučení pro diskrétní EDA
Binární řetězce >
Jednoduché problémy PBIL, UMDA, cGA
Složitější problémy MIMIC, COMIT, BMDA
Složité problémy BOA, ECGA, EBNA, LFDA
Ještě složitější problémy hBOA (Hierarchical BOA)