Perceptron dari Nol: Apa yang Dihitung Neuron

Sebuah perceptron mengambil pengukuran, mengalikan masing-masing dengan angka yang ia kendalikan, menjumlahkannya, menambahkan satu angka lagi, lalu melihat tandanya.

Tulis pengukuran satu komponen sebagai vektor $\mathbf{x} = (x_1, x_2)$ — lebar dan berat. Perceptron menyimpan vektor bobot $\mathbf{w} = (w_1, w_2)$ dan bias $b$. Skornya adalah

dan jawabannya adalah tanda dari skor itu: terima jika $s(\mathbf{x}) \geq 0$, tolak jika tidak.

Itulah seluruh modelnya. Semua yang akan pernah diketahui perceptron tentang pabrik hidup dalam tiga angka.

Geometrinya layak dihentikan sejenak, karena gambar inilah yang tetap bekerja untuk dua puluh sembilan bab berikutnya, bahkan ketika persamaannya tidak lagi muat dalam satu baris. Himpunan titik tempat $s(\mathbf{x}) = 0$ — tempat perceptron tepat tidak bisa memutuskan — adalah garis lurus di bidang. Di satu sisi, skornya positif dan semuanya diterima; di sisi lain, skornya negatif dan semuanya ditolak. Bagi perceptron, belajar berarti memindahkan garis itu.

Dua fakta tentang garis itu langsung mengikuti dari aljabarnya, dan keduanya penting nanti:

• $\mathbf{w}$ tegak lurus terhadapnya. Vektor bobot tidak terletak sepanjang batas; ia menunjuk melintasinya, ke arah sisi yang diterima.
• $b$ menggesernya tanpa memutarnya. Tanpa bias, garis itu akan dipaksa melewati titik asal, yang bagi pabrik yang mengukur milimeter dan gram merupakan batasan absurd — itu berarti komponen dengan lebar nol dan berat nol duduk tepat di pagar.

Perceptron mulai tanpa tahu apa pun: $\mathbf{w} = (0, 0)$ dan $b = 0$. Setiap skor adalah nol, jadi ia menerima semuanya.

Sekarang tunjukkan satu contoh pada satu waktu. Beri label komponen yang diterima $y = +1$ dan yang ditolak $y = -1$. Untuk setiap contoh, ajukan satu pertanyaan: apakah tandanya keluar benar? Cara ringkas untuk menuliskan pertanyaan itu adalah memeriksa apakah $y \cdot s(\mathbf{x})$ positif — jika label dan skor sepakat dalam tanda, hasil kalinya positif, dan jika tidak sepakat, hasilnya negatif.

Jika jawabannya ya, jangan ubah apa pun. Jika jawabannya tidak, geser sedikit:

Itulah seluruh algoritmanya, dan penting untuk memahami kenapa geseran itu benar, bukan sekadar menghafalnya. Misalkan sebuah komponen seharusnya diterima ($y = +1$) tetapi skornya keluar negatif. Menambahkan $\mathbf{x}$ ke $\mathbf{w}$ mengubah skor pada komponen yang sama sebesar

yang merupakan angka positif. Skor pada komponen yang baru saja salah itu naik, yaitu arah yang memang dibutuhkan. Aturan ini bukan heuristik yang ditebak seseorang; ini adalah perubahan terkecil yang terbukti memperbaiki kasus di depannya. Tentu saja ia bisa merusak kasus lain, itulah sebabnya kamu mengulang lagi.

Perhatikan apa yang tidak ada. Tidak ada turunan di mana pun. Ini bukan kelalaian, dan ini adalah ide pertama yang benar-benar penting dalam kursus ini.

Hal yang ingin kamu turunkan adalah error — jumlah komponen yang salah klasifikasi. Tetapi jumlah itu berbentuk tangga: ia diam datar di 4 saat kamu menggeser garis, lalu turun ke 3 tepat ketika garis melewati sebuah titik. Turunannya nol hampir di mana-mana dan tidak terdefinisi di anak tangga. Kalkulus tidak punya pegangan. Aturan perceptron bekerja mengitari itu dengan tidak meminta kemiringan sama sekali: ia hanya bertanya "benar atau salah?", lalu bergerak ke arah yang bisa ia benarkan secara geometris.

Itu solusi nyata, dan juga jalan buntu. Di Bab 2 kita akan menginginkan loss yang berasal dari suatu tempat, bukan sekadar dipilih; di Bab 4 model yang melaporkan seberapa yakin ia; dan di Bab 5 sesuatu dengan lebih dari satu layer — dan tidak satu pun bisa dijangkau dari aturan yang hanya tahu "salah". Mendapatkan kembali kemiringan yang bisa dipakai adalah hal yang memaksa dua bab berikutnya. Tetapi perceptron boleh melakukan sesuatu yang tidak bisa dilakukan penerusnya: belajar tanpa kalkulus sama sekali.

Python murni, tanpa NumPy. List dan loop. NumPy datang di bab berikutnya, ketika aritmetikanya tidak lagi muat dalam loop yang ingin kamu baca; memperkenalkannya sekarang akan menyembunyikan aritmetika di balik library tepat pada momen ketika kamu ingin melihatnya.

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

Empat baris yang disorot adalah algoritmanya. Semua yang lain adalah pembukuan.

Dan ban berjalan itu, dengan delapan komponen yang diukur darinya — empat yang dikirim dan empat yang dikembalikan:

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)

Delapan komponen ini memang bisa dipisahkan oleh garis lurus — setiap komponen yang diterima lebarnya di bawah 22 mm dan setiap yang ditolak lebarnya 23 mm atau lebih. Pagar vertikal di 22 milimeter menyelesaikan tugasnya. Jadi perceptron seharusnya menemukannya.

Jalankan:

None [-142.1, -13.0] 54.0

Dua ratus epoch, 454 koreksi, dan ia belum konvergen. Bobotnya besar dan tandanya salah. Ada yang salah — kecuali tidak ada yang salah, dan alasannya adalah hal paling berguna di bab ini.

Perceptron punya jaminan, dibuktikan oleh Novikoff pada 1962.¹ Jika data bisa dipisahkan oleh garis sama sekali, algoritma melakukan paling banyak

koreksi sebelum berhenti membuat koreksi apa pun — dengan $R$ sebagai radius data, panjang vektor contoh terpanjang, dan $\gamma$ sebagai margin: jarak dari hyperplane pemisah ke titik terdekat di ruang teraugmentasi tempat bias menjadi koordinat ketiga. Itulah kenapa memusatkan data mengubahnya, sementara jarak dalam milimeter tidak.

Jaminannya tanpa syarat dan tidak menyebut epoch, learning rate, atau keberuntungan. Ia juga tidak menyebut waktu, dan penghilangan itulah intinya.

Masukkan angka kita. Diukur langsung dari delapan komponen, dengan bias dilipat sebagai fitur konstan:

Teorema itu tidak pernah dilanggar. Jalankan versi mentah cukup lama dan ia memang konvergen — pada epoch 11.976, setelah 29.870 koreksi — masih nyaman di dalam batas 2.633.550, dan selisih itu sendiri adalah intinya: teorema membatasi kasus terburuk, bukan kasus tipikal. Ia hanya membutuhkan epoch enam puluh kali lebih banyak daripada yang akan ditunggu siapa pun.

Baris kedua adalah delapan komponen yang sama, dua puluh baris kode yang sama, dengan tiga baris ditambahkan untuk mengurangkan lebar rata-rata dan berat rata-rata dari setiap pengukuran. Itu saja. Itulah seluruh perubahannya. Ia memindahkan awan titik sehingga mengapit titik asal, bukan mengambang jauh di (22, 57), dan efeknya terhadap batas adalah faktor lima belas ribu, karena kedua suku membaik sekaligus: $R$ turun dari 74 ke 13 karena titik-titik tidak lagi diukur dari titik asal yang jauh, dan $\gamma$ naik dari 0,045 ke 0,989 karena margin diukur terhadap vektor bobot yang tidak lagi harus memikul bias besar untuk mencapai data.

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

Konvergen dalam dua epoch, setelah mengoreksi dirinya tepat sekali.

Ada pelajaran nyata di sini, dan bukan "ingat untuk menormalisasi input", meskipun kamu memang harus melakukannya. Pelajarannya adalah jaminan bahwa sebuah algoritma akan selesai tidak memberi tahu apa pun tentang apakah kamu masih akan ada di sana saat itu terjadi, dan celah antara keduanya biasanya adalah geometri. Ini kemunculan pertama pola yang akan kamu temui lagi di Bab 6 dengan inisialisasi, di Bab 10 dengan jadwal learning rate, dan di Bab 13 dengan kuantisasi: matematika mengatakan sesuatu itu mungkin, dan engineering memutuskan apakah itu praktis. Kursus yang hanya mengajarkan teorema memberimu model yang training tiga hari lalu menyalahkanmu.

Sekarang kegagalan yang mengakhiri era pertama neural network, dan ia muat dalam empat baris.

Lupakan pabrik. Ambil dua input yang masing-masing bernilai 0 atau 1, dan minta jawabannya menjadi $+1$ ketika tepat salah satunya bernilai 1:

Ini XOR — exclusive or. Sebelum lanjut membaca, gambar empat titik itu di kertas: tiga sudut bujur sangkar satuan dan sudut keempatnya. Tandai dua sudut diagonal $(0,1)$ dan $(1,0)$ sebagai terima, dan $(0,0)$ serta $(1,1)$ sebagai tolak. Sekarang gambar satu garis lurus dengan dua titik yang diterima di satu sisi dan dua titik yang ditolak di sisi lain.

Kamu tidak bisa. Bukan karena sulit, atau karena kamu butuh algoritma yang lebih pintar; garis itu memang tidak ada. Tiga baris aljabar menunjukkan alasannya. Jika sebuah perceptron membuat keempatnya benar, maka membaca empat baris secara berurutan memberi

Jumlahkan dua pertidaksamaan tengah: $w_1 + w_2 + 2b \geq 0$, jadi $w_1 + w_2 \geq -2b$. Yang terakhir mengatakan $w_1 + w_2 < -b$. Bersama-sama: $-2b \leq w_1 + w_2 < -b$, yang membutuhkan $-2b < -b$, yang membutuhkan $b > 0$. Dan pertidaksamaan pertama mengatakan $b < 0$. Tidak ada $b$ seperti itu, jadi tidak ada bobot seperti itu. Tidak ada perceptron, dengan angka apa pun, yang mengklasifikasikan XOR.

Tetap jalankan, karena melihat algoritma gagal lebih berharga daripada diberi tahu bahwa ia akan gagal:

     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

Ia tidak divergen, dan tidak meronta-ronta di sekitar jawaban yang lumayan. Ia berputar dalam siklus: berjalan melalui loop pendek di ruang bobot dan kembali tepat ke tempat ia mulai, selamanya, mendapatkan dua dari empat benar — sama seperti menebak. Seratus ribu epoch dan seratus epoch tidak bisa dibedakan, karena algoritma tidak membuat kemajuan yang bisa diselesaikan dengan run yang lebih panjang. Bandingkan dengan ban berjalan, yang terlihat macet pada 200 epoch dan sebenarnya sedang menggerinda menuju jawaban nyata. Dari luar, keduanya tampak mirip selama beberapa detik pertama. Membedakannya, tanpa teorema, mustahil — yang menjadi satu argumen lagi untuk mengetahui teoremanya.

Pada 1969 Marvin Minsky dan Seymour Papert menerbitkan Perceptrons, studi matematis sepanjang buku tentang persis apa yang bisa dan tidak bisa direpresentasikan model ini.² XOR adalah hasilnya yang paling sering dikutip, dan kutipan itu biasanya dipakai sebagai tuduhan: bahwa buku tersebut membunuh riset neural network selama lima belas tahun karena rivalitas atau kedengkian.

Matematika dalam buku itu benar, dan lebih menarik daripada contoh XOR. Minsky dan Papert tidak terutama tertarik pada apakah satu perceptron bisa melakukan XOR; mereka tertarik pada apa yang terjadi ketika perceptron diberi limited receptive fields — setiap unit hanya melihat sebagian input — dan mereka membuktikan bahwa properti global tertentu dari gambar, seperti apakah sebuah figur tersambung, tidak dapat dihitung dengan cara itu berapa pun jumlah unit yang kamu gunakan. Itu hasil yang benar-benar dalam tentang lokalitas, dan tidak ada hubungannya dengan cerita populer.

Cerita populer juga salah secara sejarah. Minsky dan Papert secara eksplisit membahas perceptron multi-layer dan mengatakan bahwa pertanyaan tentang kekuatannya masih terbuka — mereka menduga memperluas teorinya akan "steril", yang merupakan prediksi, bukan bukti, dan prediksi itu salah. Yang hilang pada 1969 bukanlah gagasan menumpuk layer; yang hilang adalah cara untuk training sebuah tumpukan. Aturan perceptron tidak bisa melakukannya: ia perlu tahu seberapa salah tiap unit, dan untuk unit yang terkubur di tengah tidak ada label untuk dibandingkan. Celah itu tetap terbuka sampai backpropagation dipopulerkan pada 1986,³ dan menutup celah itulah yang dilakukan Bab 5.

Jadi ringkasan jujurnya begini. Buku itu membuktikan batasan nyata dari model nyata. Runtuhnya pendanaan bidang ini pada tahun tujuh puluhan punya banyak penyebab, salah satunya adalah janji-janji untuk perceptron pada awal tahun enam puluhan yang terlalu berlebihan. Dan rintangan teknisnya bisa diselesaikan, tetapi belum ada yang memiliki alatnya.

Perceptron berusia enam puluh delapan tahun dan kamu baru saja menulis satu. Penting untuk presisi tentang bagian mana darinya yang masih ada di mesin yang akan kamu selesaikan di kursus ini, karena jawabannya: lebih banyak daripada yang kamu kira.

Perceptron tersangkut pada dua hal sekaligus, dan ternyata keduanya adalah hal yang sama.

Ia tidak bisa merepresentasikan XOR, karena satu garis tidak cukup. Memperbaikinya berarti menumpuk layer — layer pertama yang membengkokkan ruang, layer kedua yang menggambar garis di ruang yang sudah dibengkokkan. Itulah Bab 5.

Tetapi kamu tidak bisa melatih tumpukan dengan aturan perceptron, karena ia hanya tahu "salah", dan unit di tengah network tidak punya label sendiri untuk disalahkan. Untuk melatih tumpukan, kamu perlu tahu seberapa salah, dan ke arah mana, untuk setiap bobot — kamu butuh kemiringan. Dan error function perceptron, si tangga itu, tidak memilikinya.

Jadi sebelum tumpukan, harus ada loss function dengan turunan yang bisa dipakai. Bukan yang dipilih karena nyaman diturunkan, melainkan yang berasal dari suatu tempat, yang mengatakan sesuatu yang benar tentang data, dan yang gradient-nya keluar dari makna itu, bukan direkayasa balik agar terlihat rapi.

Itulah Bab 2, dan ia dimulai dengan mengajukan pertanyaan yang tidak pernah perlu dijawab perceptron: bukan "apakah komponen ini bagus?", melainkan "seberapa mungkin pembacaan ini, jika ini kebenarannya?"

Juga layak dibaca bersama bab ini: makalah asli Rosenblatt, The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain (Psychological Review 65(6), 1958), yang lebih mudah dibaca daripada reputasinya; McCulloch dan Pitts, A Logical Calculus of the Ideas Immanent in Nervous Activity (Bulletin of Mathematical Biophysics 5, 1943), makalah yang pertama kali memodelkan neuron sebagai ambang di atas jumlah berbobot; bagian perceptron dari A Course in Machine Learning karya Hal Daumé III, yang menurunkan update yang sama dengan penekanan berbeda; serta bab 2 dan 3 dari Mathematics for Machine Learning karya Deisenroth, Faisal, dan Ong untuk aljabar linear, jika kotak di atas membuatmu menginginkan lebih banyak daripada yang diberikannya.