Belief Networks
(Kanı Ağları)
Süleyman Kıvanç Ekici
13.12.2010
Ege Universitesi
Bilgisayar Mühendisliği Yüksek Lisans
1
Belief Networks
•
•
•
•
•
•
•
•
•
Tanım ve kullanıldığı alanlar
Kanı ağının elemanları
Durumsal Bağımsızlık (Conditional Independence)
Kanı ağı oluşturma
Birleşik Olasılık Dağılımı (Joint Probability
Distribution)
Kanı Ağlarında Çıkarsama
Kanı Ağlarında Öğrenme
Restricted Boltzman Machine
Örnek Sayı Tanıma Modeli
2
Belief Networks
• Kanı ağları : bir grup rastgele değişkeni ve aralarındaki
durumsal bağımlılıkları bir yönlü düz ağaç yapısı ile gösteren
grafiksel bir modeldir.
• Judea Pearl tarafından ilk olarak 1985’te Bayesian Networks
deyimi ile ortaya konmuştur. Son 10 yılda ise çok popüler
bir konu haline gelerek bir çok alanda kullanılmaktadır.
• A Bayesian network, belief network or directed acyclic
graphical model is a probabilistic graphical model that
represents a set of random variables and their conditional
dependencies via a directed acyclic graph (DAG)
3
Belief Networks 2
• Kanı ağları ile çıkarsama ve öğrenme ile ilgili
etkin algoritmalar vardır.
– Çıkarsama Algoritmaları : Variable elimination,
clique tree propagation, recursive conditioning,
AND/OR search, importance sampling, minibucket elimination, loopy belief
propagation, generalized belief propagation
– Öğrenme Algoritmaları : Gaussian distributions,
maximum likelihood, expectation-maximization
algorithm
4
Kullanıldığı Alanlar
• Kanı ağları takip den alanlarda bilgi
modelleme amaçlı kullanılmaktadır:
– Bioinformatik (gen düzenleme ağları, protein
yapıları, gen analizi ), Tıp, doküman sınıflandırma,
bilgi getirme, resim işleme, veri birleşimi, karar
destek sistemleri, mühendislik, oyunlar, ve hukuk.
5
Belief Networks 2
• Kanı ağlarının elemanları
– Düğümler (Nodes) : Rastgele değişkenler kümesi
– Yönlü ilişkiler (Directed links) : X düğümünden Y
düğümüne giden bir ilişki X elemanının Y elemanı
üzerinde direkt bir etkiye sahip olduğunu gösterir
– Durumsal olasılık tablosu (Conditional probability
table): Her düğümde bulunur. Ebeveyn düğümlerin
düğüm üzerindeki etkisinin miktarını belirler.
• Kanı ağları yönlü bir döngü içermez. (directed
cycles)
6
Belief Networks 3
• Örnek:
• Diğer adları Bayesian Networks, Graph
Models, Casual Networks ...
7
Durumsal Bağımsızlık (Conditional Independence)
•
Rastgele değişken C biliniyorken iki rastgele değişken A ve B durumsal bağımsızdır
eğer:
–
•
tüm a, b, c değerleri için P(a, b | c) = P(a | c) P(b | c)
Başka bir deyişle P(a | b, c) = P(a | c) eşitliği bize eğer “c” yi biliyorsak “b” yi
öğrenmek “a” nın olasılığı ile ilgili bir değişikliğe yol açmaz.
•
İkiden fazla değişken içinde uyarlanabilir
–
Örneğin X1, X2, … XK semptomlar ve C hastalık olsun.
–
P(X1, X2,…. XK | C) = P P(Xi | C)
8
Örnekler 1
A
B
C
Marjinal bağımsızlık:
p(A,B,C) = p(A) p(B) p(C)
9
Örnekler 2
Durumsal bağımsız etki :
p(A,B,C) = p(B|A)p(C|A)p(A)
A
B ve C elde A varken durumsal bağımsızdır
B
C
10
Örnekler 3
A
B
Bağımsız sebebler:
p(A,B,C) = p(C|A,B)p(A)p(B)
C
“Explaining away” etkisi:
Elde C ile A nın gözlemlenmesi B yi daha az olası
hale getiriyor.
A ve B bağımsızdır ancak C bilindikten sonra bağımlı
hale gelirler
11
Örnekler 4
A
B
C
Markov bağımlılığı :
p(A,B,C) = p(C|B) p(B|A)p(A)
12
Kanı ağı oluşturma
• Alanı tanımlayan ilgili değişkenler (Xi) belirlenir
• Değişkenlerin bir sıralaması seçilir. (Önemli
adım)
• Tüm değişkenler eklenene kadar
– Bir değişken seç ve bunun için bir düğüm ekle
– Daha önce eklenmiş düğümlerden durumsal
bağımsızlık özelliğini sağlayacak şekilde ebeveyn
düğümleri seç
– Düğüm için durumsal olasılık tablosunu oluştur.
13
Kanı ağı oluşturma 2
• Evde bir hırsız alarmı var
– Güvenilir bir şekilde hırsızlıkları tespit edebiliyor.
– Bazen küçük depremlerede alarm verebiliyor.
• İki komşu John ve Mary alarmı duyunca polisi
arıyorlar.
– John alarmı duyunca polisi arıyor ama bazen
telefon zilini alarmla karıştırarak polisi arıyor.
– Mary yüksek sesli müzik sevdiği için alarmı bazen
hiç duymuyor.
14
Kanı ağı oluşturma 3
• Değişkenleri sıralayalım J,M,A,E,B
• P(J, M, A, E, B) = P(J, M | A, E, B) P(A| E, B) P(E, B)
~ P(J, M | A)
P(A| E, B) P(E) P(B)
~ P(J | A) P(M | A) P(A| E, B) P(E) P(B)
15
Kanı ağı oluşturma 3
16
Birleşik Olasılık Dağılımı (Joint
Probability Distribution)
• JPD şu genel formül ile gösterilmektedir:
17
Birleşik Olasılık Dağılımı
P ( J  M  A  B   E )
 P( J | A) P(M | A) P(A | B  E) P(B) P(E)
 0.9 * 0.7 * 0.001* 0.999* 0.998
 0.00062
18
Kanı Ağlarında Çıkarsama
•
Kanı ağlarında bir sorguya cevap verilmesi
–
–
–
•
•
Q = sorgu değişkenlerinin kümesi
e = Kanıtlar
Çıkarsama = P(Q | e) olasılığının hesaplanması
Örnekler
–
P(burglary | alarm)
–
P(earthquake | JCalls, MCalls)
–
P(JCalls, MCalls | burglary, earthquake)
Kanı ağları yapısını bu tür sorgular için etkin olarak kullanabilirmiyiz? Cevap : Evet
19
Kanı Ağlarında Çıkarsama 2
• Tanısal çıkarsama (diagnostic inference) :
Etkilerden sebeplere doğru çıkarsama.
– P(Burglary | JohnCalls) =0.016
• Nedensel çıkarsama (causal inference) :
Sebeplerden etkilere doğru çıkarsama.
– P(JohnCalls | Burglary) =0.86
20
Kanı Ağlarında Çıkarsama 3
• Nedenseller arası çıkarsama (intercausal
inference) :
– Alarmı biliyorsak
• P(Burglary | Alarm) = 0.376
– Alarmı ve depremi biliyorsak
• P(Burglary | Alarm ^ Earthquake)= 0.003
21
Örnek
22
Örnek 2
23
Kanı Ağlarında Öğrenme
• Kanı ağlarında öğrenme için
düğümler arasındaki ilişkiler
ayarlanarak ağın
gözlemlenen veriye uygun
davranmasını sağlamaktır.
• Yaprak düğümlerde
örnekleme yaparak ağın
neye inandığını görebiliriz
ancak arka planda neler
yürüdüğünü göremeyiz.
stochastic
hidden
cause
visible
effect
24
Restricted Boltzman Machine
• Öğrenmeyi kolaylaştırmak adına
Belief Networks bağlantılarında
kısıtlama yapılarak oluşturulmuştur.
• Bir tane gizli katman bulunmaktadır.
• RBM de bütün gizli elemanlar
durumsal olarak bağımsızdır
(conditionally independent) böylece
bir veri vektörü verildiğinde arka
plandaki dağılıma ulaşabiliriz bu da
yönlü kanı ağlarına göre büyük
avantaj sağlar.
hidden
j
i
visible
25
RBM ile öğrenme
50 binary
feature
neurons
50 binary
feature
neurons
Aktif piksel ve aktif bir
özellik arasında
ağırlıkları Azalt
Aktif piksel ve aktif bir
özellik arasında
ağırlıkları Arttır
16 x 16
pixel
16 x 16
pixel
image
image
data
(reality)
reconstruction
(better than reality)
26
RBM ile öğrenme 2
Data
Aktif özellik
nöronlarından
türetilen kopya
Modelin eğitildiği bir
sayı
Data
Aktif özellik
nöronlarından
türetilen kopya
Modelin eğitilmediği bir
sayı (Model bütün şekilleri
2 gibi görmeye çalışıyor)
27
Sayı Tanıma Modeli
2000 top-level neurons
Burada sayıların hangileri olduğu
tutuluyor
10 label
neurons
500 neurons
Model katmanlar arasında sayılar ile
resimlerin kombinasyonlarını öğreniyor.
500 neurons
Tanıma yapmak için etiket nöronlarının
nötr olduğu bir durumda resim verilerini
yukarı doğru geçiriyoruz. Üst seviyedeki
ortak hafıza alanı arasında birkaç tekrar
işlemi yapılıyor
28 x 28
pixel
image
28
Video Gösterimi
• http://www.cs.toronto.edu/~hinton/adi/index.htm
29
Kaynakça
• http://www.cs.toronto.edu/~hinton/
• Ben-Gal I., Bayesian Networks, in Ruggeri F., Faltin F. & Kenett
R., Encyclopedia of Statistics in Quality & Reliability, Wiley &
Sons (2007)
• http://en.wikipedia.org/wiki/Bayesian_network
• http://www.ics.uci.edu/~smyth/courses/cs271/topic11_bayes
ian_networks.ppt
• http://webdocs.cs.ualberta.ca/~lindek/366
• http://www.cs.cmu.edu/afs/cs/Web/People/awm/tutorials
• http://www.niedermayer.ca/papers/bayesian/
30
Teşekkürler
31
Download

Belief Networks Turkce