Denetimsiz Ögrenim
Transkript
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