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.