Denetimsiz Ögrenim

Denetimsiz Öğrenme
Dr. Hidayet Takçı
YSA ile Denetimsiz Öğrenim
Üzerinde çalışacağımız örüntüler hakkında daha önceden
bir bilgimizin olmadığı durumlarda denetimsiz öğrenim
yardımıyla örüntüleri sınıflandırır veya gruplarız. YSA,
diğer konularda olduğu gibi denetimsiz öğrenme
konusunda da bize yöntemler sağlayabilmektedir.
Denetimsiz öğrenim türleri
Clustering – Benzerlik tabanlı olarak örüntüler gruplanır
Vector Quantization – S vektörü daha düşük boyutlu vektörlere
2
bölünür.
Feature Extraction – var olan özellikleri kullanarak onlardan
08.04.2011
yeni özellikler çıkarma çalışması.
Ağları Kümelerken Vektörlerin Ağırlıklandırılması
1
2
wk1
wk2
wk3
3
k
wk4
4
• k düğümü giriş vektörlerinin kısmi bir sınıfını sunar, ve ağırlıklar
sınıfın centroid veya prototip değerine göre kodlanır.
• Böylece eğer prototip (class(k)) = [ik1, ik2, ik3, ik4], ise o zaman:
m = 1..4 için wkm = fe(ikm), burada fe kodlama fonksiyonudur.
• Bazı durumlarda kodlama fonksiyonu normalleştirme sağlar. Bu
nedenle wkm = fe(ik1…ik4).
• Ağırlık vektörleri denetimsiz öğrenim fazında öğrenir.
3
08.04.2011
Kümeleme için Ağ tipleri
• Kazanan Hepsini Alır (Winner-Take-All Networks) ağları
– Hamming ağları
– Maxnet
– Basit rekabetçi öğrenim ağları (Hamming ve Maxnet birlikte)
Kazanan & onun komşuları “bazısını alır”
4
08.04.2011
Hamming Ağları
Given: n boyutlu S uzayından m örüntünün bir kümesi.
Create: n giriş düğümü ve m basit doğrusal çıkış düğümü ile bir ağ (her örüntü için
bir tane), burada p’nin n özelliğine dayalı p örüntüsü için çıkış düğümüne gelen
ağırlıklar.
ipj = pth örüntünün jth giriş biti. ipj = 1 veya -1 olabilir.
wpj = ipj/2 değeri atanır
ayrıca her bir çıkış düğümünde -n/2 gibi bir eşik girişi bulunur.
Testing: Bir giriş örüntüsü giriniz (I) ve P’nin hangi üyesinin I’ya en yakın olduğunu
bulunuz. Yakınlık Hamming distance tabanlıdır (# iki örüntüde eşleşmeyen bitlerin
sayısı).
Verilen bir I girişi için, p örüntüsünün çıkış düğümünün çıktı değeri =
n i

n
n 1 n
pk
w pk I k − ≡ ∑
I k − ≡  ∑ i pk I k − n
∑

2 k =1 2
2 2  k =1
k =1
n
= I ve p arasındaki Hamming uzaklığının negatifi
5
08.04.2011
Hamming Networks (2)
Proof: (p çıkış düğümünün çıktısı; p ile giriş vektörü I arasındaki mesafenin
Hamming uzaklığı negatiftir).
Assume: k bit eşleşiyor.
Then: n - k bit eşleşmiyor, ve n-k Hamming uzaklığıdır.
And: p’nin çıkış düğümünün çıktı değeri :
 1
1 n
 ∑ i pk I k − n ≡ ( k − (n − k ) − n) ≡ k − n ≡ −(n − k )
 2
2  k =1
k eşleşme, burada her bir eşleşme (1)(1) veya (-1)(-1) = 1
Neg. Hamming uzaklığı
n-k eşleşmeme, burada herbir (-1)(1) veya (1)(-1) = -1 verir
I için en büyük negatif Hamming uzaklığını veren p* örüntüsü, I için en yakın örüntü
olacaktır (I’ya en yakın). Böylece, p* örüntüsünü sunan çıkış düğümü bütün çıkış
düğümleri içinde en yüksek çıkış değerine sahip olacaktır: o kazanır (it wins!)
08.04.2011
6
Hamming Network Example
P = {(1 1 1), (-1 -1 -1), (1 -1 1)} = 3 patterns of length 3
Inputs
Outputs
i1
p1
i2
p2
wgt = 1/2
wgt = -1/2
wgt = -n/2 = -3/2
i3
p3
1
Given: giriş örüntüsü I = (-1 1 1)
Output (p1) = -1/2 + 1/2 + 1/2 - 3/2 = -1 (Winner)
Output (p2) = 1/2 - 1/2 - 1/2 - 3/2 = -2
Output (p3) = -1/2 - 1/2 + 1/2 - 3/2 = -2
7
08.04.2011
Simple Competitive Learning
Hamming benzeri bir ağ ile Maxnet ağının girişten çıkışa ağırlıkların öğrenimi ile
bir kombinasyonu.
Girişler gerçek değerler olabilir.
Böylece Hamming yerine Euclidean veya Manhattan kullanılabilir.
Her bir çıkış düğümü kazanan giriş örüntüleri için bir centroid sunar.
Öğrenim: kazanan düğümün gelen ağırlıkları giriş vektörüne daha yakın
olabilmek için güncellenir.
Euclidean
Maxnet
8
08.04.2011
Winning & Learning
``kazanma her şey değildir…o sadece bir şeydir” - Vince Lombardi
Sadece kazanan düğümün gelen ağırlıkları düzeltilir.
Kazanan (Winner) = gelen ağırlıkları giriş vektörüne en kısa Euclidean mesafede
bulunan düğümler çıkış düğümleridir.
n
∑ (I
i =1
i − wki )
2
= k çıkış düğümünün gelen ağırlıkları tarafından sunulan
vektör ile giriş vektörü I arasındaki Euclidean uzaklık
Güncelleme formülü : eğer j kazanan çıkış düğümü ise:
∀i : w ji ( new) = w ji (old ) + η ( I i − w ji (old ))
1
2
wk1
wk2
wk3
3
9
4
k
wk4
08.04.2011
SCL Examples (1)
6 Cases:
(0 1 1)
(0.2 0.2 0.2)
(0.4 0.6 0.5)
(1 1 0.5)
(0.5 0.5 0.5)
(0 0 0)
Learning Rate: 0.5
Initial Randomly-Generated Weight Vectors:
[ 0.14 0.75 0.71 ]
[ 0.99 0.51 0.37 ]
bu yüzden, öğrenilecek 3 sınıf vardır
[ 0.73 0.81 0.87 ]
Training on Input
Input vector # 1:
Winning weight
Updated weight
Input vector # 2:
Winning weight
Updated weight
10
Vectors
[ 0.00 1.00 1.00 ]
vector # 1: [ 0.14 0.75 0.71 ] Distance:
vector: [ 0.07 0.87 0.85 ]
[ 1.00 1.00 0.50 ]
vector # 3: [ 0.73 0.81 0.87 ] Distance:
vector: [ 0.87 0.90 0.69 ]
0.41
0.50
08.04.2011
SCL Examples (2)
Input vector # 3:
[ 0.20
0.20
0.20 ]
Winning weight vector # 2: [ 0.99
Updated weight vector: [ 0.59
Input vector # 4:
[ 0.50
0.50
0.36
Input vector # 5:
[ 0.40
0.60
Input vector # 6:
[ 0.00
0.00
0.36
0.29 ] Distance:
0.27
0.39 ]
0.50 ]
0.43
0.51
0.39 ] Distance:
0.25
0.45 ]
0.00 ]
Winning weight vector # 2: [ 0.47
Updated weight vector: [ 0.24
0.86
0.29 ]
0.43
Winning weight vector # 2: [ 0.55
Updated weight vector: [ 0.47
0.37 ] Distance:
0.50 ]
Winning weight vector # 2: [ 0.59
Updated weight vector: [ 0.55
0.51
0.26
0.51
0.45 ] Distance:
0.83
0.22 ]
Weight Vectors after epoch 1:
11
[ 0.07
0.87
0.85 ]
[ 0.24
0.26
0.22 ]
[ 0.87
0.90
0.69 ]
08.04.2011
SCL Examples (3)
Clusters after epoch 1:
Weight vector # 1: [ 0.07 0.87 0.85 ]
Input vector # 1:
[ 0.00 1.00 1.00
Weight vector # 2: [ 0.24 0.26 0.22 ]
Input vector # 3:
[ 0.20 0.20 0.20
Input vector # 4:
[ 0.50 0.50 0.50
Input vector # 5:
[ 0.40 0.60 0.50
Input vector # 6:
[ 0.00 0.00 0.00
Weight vector # 3: [ 0.87 0.90 0.69 ]
Input vector # 2:
[ 1.00 1.00 0.50
]
]
]
]
]
]
Weight Vectors after epoch 2:
[ 0.03 0.94 0.93 ]
[ 0.19 0.24 0.21 ]
[ 0.93 0.95 0.59 ]
Clusters after epoch 2:
unchanged.
12
08.04.2011
SCL Examples (4)
6 Cases
(0.9 0.9 0.9)
(0.8 0.9 0.8)
(1 0.9 0.8)
(1 1 1)
(0.9 1 1.1)
(1.1 1 0.7)
Other parameters:
Initial Weights from Set: {0.8
1.0
1.2}
Learning rate: 0.5
# Epochs: 10
13
Aynı örnek verileri ikinci kez bu sefer farklı başlangıç
değerleri ile eğitilmiş ve görülmüştür ki bulunan küme
merkezleri ve kümelere düşen elemanlar farklıdır. Dolayısıyla
denetimsiz öğrenimde başlangıç ağırlıklarının tespiti önemli
bir konudur.
08.04.2011
SCL Examples (5)
Initial Weight Vectors:
[ 1.20 1.00 1.00 ]
[ 1.20 1.00 1.20 ]
[ 1.00 1.00 1.00 ]
* All weights are medium to high
Clusters after 10 epochs:
Weight vector # 1: [ 1.07 0.97 0.73 ]
Input vector # 3:
[ 1.00 0.90 0.80
Input vector # 6:
[ 1.10 1.00 0.70
Weight vector # 2: [ 1.20 1.00 1.20 ]
Weight vector # 3: [ 0.91 0.98 1.02 ]
Input vector # 1:
[ 0.90 0.90 0.90
Input vector # 2:
[ 0.80 0.90 0.80
Input vector # 4:
[ 1.00 1.00 1.00
Input vector # 5:
[ 0.90 1.00 1.10
]
]
]
]
]
]
** Weight vector #3 is the big winner & #2 loses completely!!
14
08.04.2011
SCL Examples (6)
Initial Weight Vectors:
[ 1.00 0.80 1.00 ]
[ 0.80 1.00 1.20 ]
[ 1.00 1.00 0.80 ]
* Better balance of initial weights
Clusters after 10 epochs:
Weight vector # 1: [ 0.83 0.90 0.83 ]
Input vector # 1:
[ 0.90 0.90 0.90
Input vector # 2:
[ 0.80 0.90 0.80
Weight vector # 2: [ 0.93 1.00 1.07 ]
Input vector # 4:
[ 1.00 1.00 1.00
Input vector # 5:
[ 0.90 1.00 1.10
Weight vector # 3: [ 1.07 0.97 0.73 ]
Input vector # 3:
[ 1.00 0.90 0.80
Input vector # 6:
[ 1.10 1.00 0.70
** 3 clusters of equal size!!
15
]
]
]
]
]
]
Note: All of these SCL examples were run by a simple piece of
code that had NO neural-net model, but merely a list of weight
08.04.2011
vectors that was continually updated.
SCL Variations
Normalize Edilmiş Ağırlıklar & Giriş Vektörleri
n
∑ (I
Distance =
i =1
− wki ) =
2
i
n
∑I
i =1
2
i
n
− 2 I i wki + wki = 2 − 2∑ I i wki
2
i =1
Uzaklığı minimize etmek için:
n
∑I w
i =1
i
n
i =1
I ve W normal vektörler olduğunda (Length = 1) ve
cosθ = I • W
n
Normalizasyon
∑ I i = ∑ wki = 1 yüzünden
ki
2
2
i =1
θ = IW angle
Normalization of I = < i1 i2…in> . W = < w1 w2…wn> normalized similarly.
L = i1 + i2 + ... + in
2
2
2
i i
i
~
I =< 1 , 2 ,... n >
L L L
Bütün normaliz edilmiş vektörleri kullanarak iki vektör arasındaki açıdan o vektörlerin
benzerliklerini elde edebiliriz. Böylece, giriş vektörüne en benzer düğüm elde edilmiş
olacaktır.
16
08.04.2011
Maxnet
wgt = −ε
wgt = θ
e.g.
1
θ = 1∧ ε ≤
n
En büyük başlangıç giriş değerli düğümü bulmak için basit ağ.
Topology: küçük pozitif değerli (ateşleyici) kendi kendine bağlantılar, ve küçük negatif
değerli (frenleyici) harici bağlantılar.
Nodes:Transfer fonksiyonu fT = max(sum, 0)
Algorithm:
Başlangıç değerlerini yükle
Repeat:
Eşzamanlı olarak bütün düğümleri fT değeriyle güncelle
Until: biri hariç tüm düğümlerin değeri 0
Kazanan= değeri 0 olmayan düğüm
17
08.04.2011
Maxnet Examples
Input values: (1, 2, 4, 5, 3) with epsilon = 1/5 and theta = 1
0.000
0.000
3.000
1.800
0.600
0.000
0.000
2.520
1.080
0.000
0.000
0.000
2.304
0.576
0.000
0.000
0.000
2.189
0.115
0.000
0.000
0.000
2.166
0.000
0.000
0.000
0.000
2.166
0.000
0.000
= (1)5 - (0.2)(1+2+4+3)
Stable attractor
18
Input values: (1, 2, 5, 4.5, 4.7) with epsilon = 1/5 and theta = 1
0.000
0.000
0.000
0.000
2.560
1.728
1.960
1.008
2.200
1.296
0.000
0.000
1.267
0.403
0.749
0.000
0.000
1.037
0.000
0.415
0.000
0.000
0.954
0.000
0.207
0.000
0.000
0.912
0.000
0.017
0.000
0.000
0.909
0.000
0.000
0.000
0.000
0.909
0.000
0.000
08.04.2011
Stable attractor
Maxnet Examples (2)
Input values: (1, 2, 5, 4, 3) with epsilon = 1/10 and theta = 1
0.000
0.700
4.000
2.900
1.800
0.000
0.000
3.460
2.250
1.040
0.000
0.000
3.131
1.800
0.469
0.000
0.000
2.904
1.440
0.000
0.000
0.000
2.760
1.150
0.000
0.000
0.000
2.645
0.874
0.000
0.000
0.000
2.558
0.609
0.000
0.000
0.000
2.497
0.353
0.000
0.000
0.000
2.462
0.104
0.000
0.000
0.000
0.000
0.000
2.451
2.451
0.000
0.000
0.000
0.000
Stable attractor
Input values: (1, 2, 5, 4, 3) with epsilon = 1/2 and theta = 1
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
Stable attractor
* Epsilon > 1/n with theta = 1 => too much inhibition
19
08.04.2011