Perceptron’u sıfırdan kurmak: Bir nöron ne hesaplar?

Bir perceptron ölçümleri alır, her birini kontrol ettiği bir sayıyla çarpar, toplar, bir sayı daha ekler ve işarete bakar.

Bir parçanın ölçümlerini $\mathbf{x} = (x_1, x_2)$ vektörü olarak yaz — genişlik ve ağırlık. Perceptron bir ağırlık vektörü $\mathbf{w} = (w_1, w_2)$ ve bir bias $b$ tutar. Skoru şudur:

ve cevabı bu skorun işaretidir: $s(\mathbf{x}) \geq 0$ ise kabul et, aksi halde reddet.

Modelin tamamı bu. Perceptron’un fabrika hakkında bileceği her şey üç sayının içinde yaşar.

Geometri üzerinde durmaya değer, çünkü denklemler tek satıra sığmayı bıraktığında bile önümüzdeki yirmi dokuz bölüm boyunca çalışmaya devam eden resim budur. $s(\mathbf{x}) = 0$ olan noktalar kümesi — perceptron’un tam olarak kararsız kaldığı yer — düzlemde bir doğru oluşturur. Bir tarafta skor pozitiftir ve her şey kabul edilir; diğer tarafta negatiftir ve her şey reddedilir. Bir perceptron için öğrenme, o doğruyu hareket ettirmek demektir.

Bu doğru hakkında cebirden doğrudan çıkan iki gerçek vardır ve ikisi de sonra önemli olur:

• $\mathbf{w}$ ona diktir. Ağırlık vektörü sınır boyunca uzanmaz; sınırın karşısına, kabul edilen tarafa doğru işaret eder.
• $b$ onu döndürmeden kaydırır. Bias olmasa doğru orijinden geçmek zorunda kalırdı; milimetre ve gram ölçen bir fabrika için bu saçma bir kısıt olurdu — sıfır genişlikte ve sıfır ağırlıkta bir parçanın tam sınırda durduğu anlamına gelirdi.

Perceptron hiçbir şey bilmeden başlar: $\mathbf{w} = (0, 0)$ ve $b = 0$. Her skor sıfırdır, bu yüzden her şeyi kabul eder.

Şimdi ona her seferinde bir örnek göster. Kabul edilen parçaları $y = +1$, reddedilenleri $y = -1$ ile etiketle. Her örnek için tek bir soru sor: işaret doğru çıktı mı? Bu soruyu kompakt biçimde yazmanın yolu, $y \cdot s(\mathbf{x})$ pozitif mi diye kontrol etmektir — etiket ve skor işarette anlaşıyorsa çarpımları pozitiftir; anlaşmıyorsa negatiftir.

Cevap evetse hiçbir şeyi değiştirme. Cevap hayırsa hafifçe it:

Algoritmanın tamamı bu ve bunu ezberlemek yerine neden doğru itme olduğunu anlamaya değer. Diyelim ki bir parça kabul edilmeliydi ($y = +1$) ama skor negatif çıktı. $\mathbf{w}$ üzerine $\mathbf{x}$ eklemek, aynı parça üzerindeki skoru şu kadar değiştirir:

Bu pozitif bir sayıdır. Az önce yanlış yaptığı parçanın skoru yukarı çıkar; gitmesi gereken yön de buydu. Kural, birinin tahmin ettiği bir heuristic değildir; önündeki durumu kanıtlanabilir biçimde iyileştiren en küçük değişikliktir. Elbette başka bir durumu bozabilir; bu yüzden tekrar dönersin.

Eksik olana dikkat et. Hiçbir yerde türev yok. Bu bir gözden kaçırma değil ve kursun gerçekten önemli ilk fikri bu.

Türevini almak isteyeceğin şey hatadır — yanlış sınıflandırılan parça sayısı. Ama bu sayı bir merdivendir: doğruyu hafifçe iterken 4’te düz durur, doğru bir noktayı geçtiği anda 3’e düşer. Türevi neredeyse her yerde sıfırdır ve basamaklarda tanımsızdır. Calculus’un tutunacak yeri yoktur. Perceptron kuralı bunun etrafından dolaşır: hiç eğim istemez; yalnızca «doğru mu yanlış mı?» diye sorar ve geometrik olarak savunabileceği bir yönde hareket eder.

Bu gerçek bir çözümdür ve aynı zamanda çıkmaz sokaktır. Bölüm 2’de seçilmek yerine bir yerden gelen bir loss isteyeceğiz, Bölüm 4’te modelin ne kadar emin olduğunu bildirmesini isteyeceğiz ve Bölüm 5’te birden fazla katmanı olan bir şey isteyeceğiz — ve bunların hiçbiri yalnızca «yanlış» bilen bir kuraldan ulaşılamaz. Kullanılabilir bir eğimi geri kazanmak, sonraki iki bölümü zorunlu kılan şeydir. Ama perceptron’un ardıllarının hiçbirinin yapamayacağı bir şey yapma hakkı vardır: calculus olmadan öğrenmek.

Saf Python, NumPy yok. Listeler ve bir döngü. NumPy bir sonraki bölümde geliyor; aritmetik, okumak isteyeceğin bir döngüye sığmayı orada bırakıyor. Onu şimdi tanıtmak, aritmetiği tam da görmek istediğin anda bir kütüphanenin arkasına saklardı.

def score(w, b, x):
    return w[0] * x[0] + w[1] * x[1] + b


def predict(w, b, x):
    return 1 if score(w, b, x) >= 0 else -1


def train(data, epochs=200):
    """Returns (w, b, epoch_it_converged) — or None for the epoch if it never did."""
    w, b = [0.0, 0.0], 0.0
    for epoch in range(epochs):
        mistakes = 0
        for x, y in data:
            if y * score(w, b, x) <= 0:          
                w[0] += y * x[0]                 
                w[1] += y * x[1]                 
                b += y                           
                mistakes += 1
        if mistakes == 0:
            return w, b, epoch + 1
    return w, b, None

Vurgulanan dört satır algoritmadır. Geri kalan her şey kayıt tutma.

Ve banttan ölçülmüş sekiz parça — dördü sevk edilmiş, dördü geri gelmiş:

BELT = [
    ((18.0, 47.0), +1), ((19.5, 52.0), +1), ((20.2, 49.0), +1), ((21.0, 55.0), +1),
    ((24.0, 61.0), -1), ((25.5, 66.0), -1), ((23.0, 70.0), -1), ((26.0, 58.0), -1),
]

w, b, epoch = train(BELT, epochs=200)
print(epoch, w, b)

Bu sekiz parça düz bir doğruyla ayrılabilir — kabul edilen her parça 22 mm’nin altında, reddedilenlerin her biri 23 mm veya daha fazla. 22 milimetrede dikey bir çit işi görür. Yani perceptron’un bunu bulması gerekir.

Çalıştır:

None [-142.1, -13.0] 54.0

İki yüz epoch, 454 düzeltme ve hâlâ converge etmedi. Ağırlıklar büyük ve işaret yanlış. Bir şey ters — ama aslında hiçbir şey ters değil; nedeni de bu bölümdeki en faydalı şey.

Perceptron’un, Novikoff tarafından 1962’de kanıtlanan bir garantisi vardır.¹ Eğer veri herhangi bir doğruyla ayrılabiliyorsa, algoritma durmadan önce en fazla

düzeltme yapar — burada $R$ verinin yarıçapı, yani en uzun örnek vektörünün uzunluğu; $\gamma$ ise margin’dir: ayıran hyperplane ile en yakın nokta arasındaki mesafe, bias’ın üçüncü koordinat olduğu genişletilmiş uzayda. Veriyi merkezlemenin bunu değiştirmesi, milimetre cinsinden mesafeyi değiştirmemesinin nedeni budur.

Garanti koşulsuzdur ve epoch’lardan, learning rate’lerden ya da şanstan söz etmez. Ayrıca zamandan da söz etmez; mesele de bu eksikliktir.

Sayılarımızı yerine koyalım. Bias sabit bir feature olarak içeri katılmış halde, sekiz parçadan doğrudan ölçüldüğünde:

Teorem hiçbir zaman ihlal edilmedi. Ham sürümü yeterince uzun çalıştırırsan o da converge eder — epoch 11.976’da, 29.870 düzeltmeden sonra — 2.633.550’lik sınırının rahatça içinde. Bu farkın kendisi de meselenin parçası: teorem tipik durumu değil, en kötü durumu sınırlar. Sadece kimsenin bekleyip izlemeyeceği kadar, altmış kat daha fazla epoch’a ihtiyaç duydu.

İkinci satır aynı sekiz parça, aynı yirmi satır kod; her ölçümden ortalama genişliği ve ortalama ağırlığı çıkarmak için üç satır eklenmiş hali. Hepsi bu. Bütün değişiklik bu. Nokta bulutunu (22, 57) civarında havada durmak yerine orijini iki yanına alacak şekilde taşır; bunun sınıra etkisi on beş bin kat olur, çünkü iki terim aynı anda iyileşir: $R$ 74’ten 13’e düşer, çünkü noktalar artık uzaktaki bir orijinden ölçülmüyordur; $\gamma$ ise 0,045’ten 0,989’a çıkar, çünkü margin artık veriye ulaşmak için devasa bir bias taşımak zorunda olmayan bir ağırlık vektörüne göre ölçülüyordur.

mean_w = sum(x[0] for x, _ in BELT) / len(BELT)   # 22.15
mean_g = sum(x[1] for x, _ in BELT) / len(BELT)   # 57.25
CENTRED = [(((x[0] - mean_w), (x[1] - mean_g)), y) for x, y in BELT]

w, b, epoch = train(CENTRED, epochs=200)
print(epoch, w, b)

2 [-4.15, -10.25] 1.0

İki epoch’ta converge etti ve kendini tam olarak bir kez düzeltti.

Burada gerçek bir ders var ve bu ders «input’larını normalize etmeyi unutma» değil; bunu yapmalısın, o ayrı. Ders şu: bir algoritmanın bitip bitmeyeceğine dair garanti, bittiğinde senin orada olup olmayacağına dair hiçbir şey söylemez; bu ikisinin arasındaki fark da genellikle geometridir. Bu, Bölüm 6’da initialisation ile, Bölüm 10’da learning-rate schedule’larıyla ve Bölüm 13’te quantisation ile tekrar karşılaşacağın bir örüntünün ilk görünümü: matematik bir şeyin mümkün olduğunu söyler, mühendislik ise pratik olup olmadığına karar verir. Sana yalnızca teoremi öğreten bir kurs, üç gün boyunca train olan ve suçu sana atan bir model verir.

Şimdi neural network’lerin ilk dönemini bitiren başarısızlık; dört satıra sığıyor.

Fabrikayı unut. Her biri 0 veya 1 olabilen iki input al ve tam olarak biri 1 olduğunda cevabın $+1$ olmasını iste:

Bu XOR’dur — exclusive or. Devam etmeden önce dört noktayı kâğıda çiz: birim karenin üç köşesi ve dördüncüsü. Köşegen üzerindeki iki köşeyi, $(0,1)$ ve $(1,0)$, kabul olarak; $(0,0)$ ve $(1,1)$ noktalarını reddet olarak işaretle. Şimdi kabul edilen iki nokta bir tarafta, reddedilen iki nokta diğer tarafta kalacak şekilde tek bir düz doğru çiz.

Çizemezsin. Zor olduğundan ya da daha akıllı bir algoritmaya ihtiyaç duyduğundan değil; böyle bir doğru yok. Üç satır cebir nedenini gösterir. Bir perceptron dördünü de doğru yapsaydı, dört satırı sırayla okumak şunu verirdi:

Ortadaki iki eşitsizliği topla: $w_1 + w_2 + 2b \geq 0$, yani $w_1 + w_2 \geq -2b$. Sonuncusu $w_1 + w_2 < -b$ der. Birlikte: $-2b \leq w_1 + w_2 < -b$; bu $-2b < -b$ gerektirir, o da $b > 0$ gerektirir. İlk eşitsizlik ise $b < 0$ der. Böyle bir $b$ yoktur, dolayısıyla böyle ağırlıklar da yoktur. Herhangi sayılarla olursa olsun, hiçbir perceptron XOR’u sınıflandıramaz.

Yine de çalıştır, çünkü bir algoritmanın başarısız olduğunu izlemek, sana başarısız olacağının söylenmesinden daha değerlidir:

     100 epochs -> converged=None  w=[0.0, 0.0] b=0.0  correct=2/4
   1,000 epochs -> converged=None  w=[0.0, 0.0] b=0.0  correct=2/4
 100,000 epochs -> converged=None  w=[0.0, 0.0] b=0.0  correct=2/4

Diverge etmez ve makul bir cevabın yakınında çırpınmaz. Döngüye girer: ağırlık uzayında kısa bir loop yürür ve başladığı yere aynen geri gelir, sonsuza dek; dörtten ikisini doğru yapar — tahmin ederek elde edeceğin sonuç da budur. Yüz bin epoch ile yüz epoch ayırt edilemez, çünkü algoritma daha uzun bir koşunun bitirebileceği bir ilerleme kaydetmiyordur. Bunu, 200 epoch’ta takılmış gibi görünen ama aslında gerçek bir cevaba doğru ağır ağır ilerleyen bant örneğiyle karşılaştır. Dışarıdan bakınca ilk birkaç saniye ikisi benzer görünür. Teorem olmadan onları ayırmak imkânsızdır — teoremi bilmek için bir argüman daha.

1969’da Marvin Minsky ve Seymour Papert, bu modelin tam olarak neyi temsil edip edemeyeceğine dair kitap uzunluğunda matematiksel bir çalışma olan Perceptrons’ı yayımladı.² XOR en çok alıntılanan sonucudur ve alıntı genellikle bir suçlama olarak kullanılır: kitabın rekabet ya da kin yüzünden neural network araştırmasını on beş yıl öldürdüğü söylenir.

Kitaptaki matematik doğrudur ve XOR örneğinden daha ilginçtir. Minsky ve Papert’in asıl ilgisi tek bir perceptron’un XOR yapıp yapamayacağı değildi; perceptron’lara sınırlı receptive field’lar verildiğinde — her unit input’un yalnızca bir kısmını gördüğünde — ne olduğuyla ilgileniyorlardı. Bir şeklin bağlantılı olup olmadığı gibi bir görüntünün bazı global özelliklerinin, kaç unit kullanırsan kullan, bu şekilde hesaplanamayacağını kanıtladılar. Bu, locality hakkında gerçekten derin bir sonuçtur ve popüler hikâyeyle ilgisi yoktur.

Popüler hikâye tarih konusunda da yanlıştır. Minsky ve Papert çok katmanlı perceptron’ları açıkça tartışır ve güçleri hakkındaki sorunun açık olduğunu söyler — teoriyi genişletmenin «steril» olacağından şüphelenmişlerdi; bu bir tahmindir, kanıt değil, ve yanlıştı. 1969’da eksik olan şey katmanları üst üste koyma fikri değildi; bir yığını train etmenin yoluydu. Perceptron kuralı bunu yapamaz: her unit’in ne kadar yanlış olduğunu bilmesi gerekir ve ortalarda gömülü bir unit için karşılaştırılacak bir etiket yoktur. Bu boşluk, backpropagation 1986’da popülerleşene kadar açık kaldı,³ ve onu kapatmak Bölüm 5’in yaptığı şeydir.

Yani dürüst özet şu. Kitap gerçek bir modelin gerçek bir sınırını kanıtladı. Alanın yetmişlerde yaşadığı fonlama çöküşünün birçok nedeni vardı; bunlardan biri, altmışların başında perceptron’lar için verilen vaatlerin aşırı gösterişli olmasıydı. Teknik engel çözülebilirdi, ama henüz kimsenin aracı yoktu.

Perceptron altmış sekiz yaşında ve sen az önce bir tane yazdın. Kursu bitirdiğinde elindeki makinede onun hangi parçalarının hâlâ bulunduğu konusunda net olmak değerli, çünkü cevap şu: tahmin edeceğinden daha fazlası.

Perceptron aynı anda iki şeye takıldı ve bunların aynı şey olduğu ortaya çıkıyor.

XOR’u temsil edemez, çünkü tek doğru yeterli değildir. Bunu düzeltmek katmanları üst üste koymak demektir — uzayı büken bir ilk katman, bükülmüş uzayda doğruyu çizen bir ikinci katman. Bu Bölüm 5’tir.

Ama bir yığını perceptron kuralıyla train edemezsin, çünkü o yalnızca «yanlış» bilir; bir network’ün ortasındaki unit’in yanlış olabileceği kendine ait bir etiketi yoktur. Bir yığını train etmek için her ağırlık için ne kadar yanlış olduğunu ve hangi yönde olduğunu bilmen gerekir — bir eğime ihtiyacın vardır. Perceptron’un hata fonksiyonu, yani merdiven, buna sahip değildir.

Bu yüzden yığından önce kullanılabilir türevi olan bir loss function gelmeli. Üstelik sadece türevini almak kolay diye seçilmiş olanı değil: bir yerden gelen, veri hakkında doğru bir şey söyleyen ve gradient’i düzenli görünsün diye tersine mühendislik yapılmış değil, anlamından kendiliğinden çıkan bir loss function.

Bu Bölüm 2’dir ve perceptron’un hiç cevaplamak zorunda kalmadığı bir soruyla başlar: «bu parça iyi mi?» değil, «eğer gerçek buysa, bu ölçümlerin olasılığı ne kadar?»

Bu bölümle birlikte okumaya değer diğer metinler: Rosenblatt’ın özgün makalesi, The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain (Psychological Review 65(6), 1958); ününün ima ettiğinden daha okunabilirdir. McCulloch ve Pitts, A Logical Calculus of the Ideas Immanent in Nervous Activity (Bulletin of Mathematical Biophysics 5, 1943); bir nöronu ilk kez ağırlıklı toplam üzerinde eşik olarak modelleyen makale. Hal Daumé III’ün A Course in Machine Learning kitabındaki perceptron bölümü; aynı güncellemeyi farklı bir vurguyla türetir. Ve yukarıdaki kutu sana verdiğinden fazlasını istemene yol açtıysa doğrusal cebir için Deisenroth, Faisal ve Ong’un Mathematics for Machine Learning kitabının 2. ve 3. bölümleri.