1
Bayesian Optimization Algorithm (BOA)
zarys
Piotr Lipiński
Sieć bayesowska
Sieć bayesowska to acykliczny graf skierowany, w
którym wierzchołki reprezentują zmienne losowe, a
krawędzie odpowiadają zależnościom między tymi
zmiennymi.
Zwrot krawędzi reprezentuje "kierunek patrzenia" na zależności między
zmiennymi losowymi (zmienna w węźle końcowym zależy od tej w węźle
początkowym). Brak krawędzi między dwoma wierzchołkami oznacza, że
zmienne losowe reprezentowane przez te wierzchołki są niezależne.
X
0
X
3
X
2
X
1
Sieć bayesowska
Przez
Π
Π
Π
Π
i
oznaczmy zbiór "rodziców" wierzchołka X
i
.
Wówczas łączny rozkład prawdopodobieństaw wektora
losowego X = (X
0
, X
1
, ..., X
n-1
)’ można przedstawić jako
Sieć bayesowska, przykład
Sieci bayesowskie są używane do reprezentowania
zależności między genami w chromosomie.
Rozpatrzmy chromosom X o długości 4.
Wartość każdego genu X
0
, X
1
, X
2
, X
3
można
traktować jako wartość pewnej zmiennej losowej.
Poniższa sieć bayesowska może więc reprezentować
zależności między genami w takim chromosomie.
X
0
X
3
X
2
X
1
Sieć bayesowska, przykład
Interpretacja takiej sieci jest następująca:
- wartość genu X
0
jest niezależna od wartości
pozostałych genów,
- wartość genu X
1
zależy od wartości genu X
0
,
- wartość genu X
2
zależy od wartości genu X
0
i wartości genu X
1
,
- wartość genu X
3
zależy od wartości genu X
1
.
X
0
X
3
X
2
X
1
Sieć bayesowska, przykład
Łączny rozkład prawdopodobieństwa wektora
losowego X = (X
0
, X
1
, X
2
, X
3
)’ można więc
przedstawić jako
P( X = x ) = P( X
0
= x
0
)
P( X
1
= x
1
| X
0
= x
0
)
P( X
2
= x
2
| X
0
= x
0
, X
1
= x
1
)
P( X
3
= x
3
| X
1
= x
1
)
dla x = (x
0
, x
1
, x
2
, x
3
)’.
Ten wzór można zastosować przy generowaniu
nowych osobników wg modelu zadanego przez sieć
bayesowską.
2
Sieć bayesowska, przykład
Najpierw zajmujemy się zmienną niezależną.
Znając prawdopodobieństwa P(X
0
= 0) i P(X
0
= 1) z
jakimi zmienna niezależna X
0
przyjmuje odpowiednio
wartości 0 i 1, losujemy wartość genu X
0
.
Jeśli byłyby inne zmienne niezależne, postępujemy z
nimi w taki sam sposób. Kolejność rozpatrywania tych
zmiennych jest nieistotna.
X
0
X
3
X
2
X
1
?
?
?
?
1
?
?
?
Sieć bayesowska, przykład
W kolejnych krokach zajmujemy się zmiennymi,
których rodzice mają już ustalone wartości. Kolejność
rozpatrywania tych zmiennych jest nieistotna.
Znając prawdopodobieństwa P(X
1
= 0 | X
0
= 1)
i P(X
1
= 1 | X
0
= 1), losujemy wartość genu X
1
.
X
0
X
3
X
2
X
1
1
?
?
?
1
0
?
?
Sieć bayesowska, przykład
Mając ustalone wartości genów X
0
i X
1
, możemy
losować wartości genów X
2
i X
3
.
Zajmijmy się najpierw zmienną X
3
. Znając
prawdopodobieństwa P(X
3
= 0 | X
1
= 0)
i P(X
3
= 1 | X
1
= 0), losujemy wartość genu X
3
.
Na koniec zajmijmy się zmienną X
2
. Znając
prawdopodobieństwa P(X
2
= 0 | X
0
= 1, X
1
= 0)
i P(X
3
= 1 | X
0
= 1, X
1
= 0), losujemy
wartość genu X
1
.
X
0
X
3
X
2
X
1
1
0
?
1
1
0
0
1
Algorytm BOA
Bayesian Optimization Algorithm:
Algorytm BOA
Wyjaśnienia wymaga krok (3) czyli sposób tworzenia
sieci bayesowskiej oraz estymacji prawdopodobieństw
używanych m.in. przy generowaniu nowej populacji
losowych osobników wg modelu zadanego przez sieć
bayesowską.
Bayesian Dirichlet Metric
Jakość sieci określa się różnymi miarami. Jedną z
najpopularniejszych jest Bayesian Dirichlet Metric:
gdzie
iloczyn po
π
xi
jest po wszystkich konfiguracjach rodziców wierzchołka X
i
iloczyn po x
i
jest po wszystkich wartościach wierzchołka X
i
D
zbiór danych (populacja)
B sieć bayesowska
ξ
ewentualna dodatkowa informacja
m(
π
xi
)
liczba osobników w D, w których rodzice wierzchołka X
i
mają konfigurację
π
xi
m(x
i
,
π
xi
)
liczba osobników w D, w których wierzchołek X
i
ma
wartość x
i
, a jego rodzice mają konfigurację
π
xi
p(B|
ξ
), m’(…) prior information
3
K2 Metric
W praktyce często używa się prostszej metryki, zwanej
K2 Metric, w której wszystkie parametry m’(
x
i
,
π
xi
) są
równe 1.
Przykład
Rozpatrzmy dwie zmienne X
0
i X
1
tworzące
chromosom oraz populację D = { 00, 00, 00, 11 }
Policzmy K2 dla sieci B
empty
bez żadnych krawędzi:
Ponieważ m’(
x
i
,
π
xi
) = 1, to m’(
π
xi
) = 2.
Łatwo wyliczyć, że
Zatem
Przykład
Policzmy K2 dla sieci B
0->1
z krawędzią od X
0
do X
1
:
Ponieważ m’(
x
i
,
π
xi
) = 1, to m’(
π
xi
) = 2.
Łatwo wyliczyć, że
Zatem
Konstrukcja sieci bayesowskiej
Naturalne podejście to sprawdzenie wszystkich
możliwych sieci bayesowskich i wybór najlepszej.
Liczba wszystkich możliwych sieci bayesowskich dla
zadanego chromosomu jest bardzo duża.
Nie sposób ocenić ich wszystkich, dlatego ogranicza
się ich liczbę przez wprowadzenie ograniczenia na
maksymalny stopień wierzchołka k.
W praktyce przyjmuje się k = 1 lub k = 2.
W praktyce nie sprawdza się wszystkich możliwych
sieci bayesowskich dla zadanego chromosomu
(nawet przy ograniczeniu maksymalnego stopnia
wierzchołka), lecz używa się heurystycznych metod
konstrukcji sieci optymalnej.
Konstrukcja sieci bayesowskiej
Popularny jest algorytm, który rozpoczyna
działanie z siecią bayesowską bez krawędzi,
a następnie w każdym kroku ewolucji używa
algorytmu zachłannego, który próbuje
poprawić sieć bayesowską przez
wykonywanie następujących operacji:
dodanie losowej krawędzi
usunięcie losowej krawędzi
zmiana kierunku losowej krawędzi
Estymacja prawdopodobieństw
Prawdopodobieństwa używane m.in. przy
generowaniu nowej populacji losowych osobników wg
modelu zadanego przez sieć bayesowską są
estymowane na podstawie aktualnej populacji w
naturalny sposób.
Przykład:
P( X
2
= 1 | X
0
= 0, X
1
= 0 ) = m / M
gdzie
M
liczba osobników, w których X
0
= 0 oraz X
1
= 0
m
liczba osobników, w których X
0
= 0, X
1
= 0
oraz X
2
= 1
4
Literatura
Martin Pelikan, David Goldberg, Erick Cantu-Paz, Linkage Problem,
Distribution Estimation, and Bayesian Networks, IlliGAL Report No 98013,
1998.
Martin Pelikan, David Goldberg, Erick Cantu-Paz, BOA: The Bayesian
Optimization Algorithm, IlliGAL Report No 99003, 1999.