پرسپترون از صفر: یک نورون چه چیزی محاسبه می‌کند

یک perceptron اندازه‌گیری‌ها را می‌گیرد، هر کدام را در عددی که خودش کنترل می‌کند ضرب می‌کند، آن‌ها را با هم جمع می‌زند، یک عدد دیگر هم اضافه می‌کند، و به علامت نگاه می‌کند.

اندازه‌گیری‌های یک قطعه را به صورت بردار $\mathbf{x} = (x_1, x_2)$ بنویسید — عرض و وزن. perceptron یک بردار وزن $\mathbf{w} = (w_1, w_2)$ و یک بایاس $b$ نگه می‌دارد. امتیاز آن این است:

و پاسخ آن علامت همان امتیاز است: اگر $s(\mathbf{x}) \geq 0$ قبول کن، وگرنه رد کن.

کل مدل همین است. هر چیزی که perceptron هرگز درباره کارخانه خواهد دانست، در سه عدد زندگی می‌کند.

ارزش دارد روی هندسه آن مکث کنیم، چون این همان تصویری است که در بیست‌ونه فصل بعد هم همچنان کار می‌کند، حتی وقتی معادله‌ها دیگر در یک خط جا نمی‌شوند. مجموعه نقاطی که در آن‌ها $s(\mathbf{x}) = 0$ — جایی که perceptron دقیقاً مردد است — یک خط راست در صفحه است. در یک سمت، امتیاز مثبت است و همه چیز قبول می‌شود؛ در سمت دیگر، منفی است و همه چیز رد می‌شود. یادگیری، برای یک perceptron، یعنی جابجا کردن آن خط.

دو واقعیت درباره آن خط مستقیماً از جبر به دست می‌آیند، و هر دو بعداً مهم‌اند:

• $\mathbf{w}$ بر آن عمود است. بردار وزن در امتداد مرز قرار نمی‌گیرد؛ از آن عبور می‌کند و به سمت ناحیه پذیرفته‌شده اشاره دارد.
• $b$ خط را بدون چرخاندن جابه‌جا می‌کند. بدون بایاس، خط مجبور می‌شد از مبدأ بگذرد، که برای کارخانه‌ای که میلی‌متر و گرم اندازه می‌گیرد محدودیتی مضحک بود — یعنی قطعه‌ای با عرض صفر و وزن صفر دقیقاً روی مرز تصمیم قرار دارد.

perceptron در ابتدا هیچ چیز نمی‌داند: $\mathbf{w} = (0, 0)$ و $b = 0$. هر امتیازی صفر است، پس همه چیز را قبول می‌کند.

حالا هر بار یک مثال به آن نشان دهید. قطعات پذیرفته‌شده را $y = +1$ و ردشده‌ها را $y = -1$ برچسب بزنید. برای هر مثال، یک سؤال بپرسید: آیا علامت درست درآمد؟ روش فشرده برای نوشتن این سؤال این است که بررسی کنیم آیا $y \cdot s(\mathbf{x})$ مثبت است یا نه — اگر برچسب و امتیاز از نظر علامت موافق باشند، حاصل‌ضربشان مثبت است، و اگر مخالف باشند، منفی است.

اگر پاسخ بله است، هیچ چیز را تغییر نده. اگر پاسخ نه است، کمی هل بده:

کل الگوریتم همین است، و ارزش دارد بفهمید چرا این هل دادن درست است، نه اینکه فقط آن را حفظ کنید. فرض کنید قطعه‌ای باید پذیرفته می‌شد ($y = +1$) و امتیاز منفی درآمد. اضافه کردن $\mathbf{x}$ به $\mathbf{w}$ امتیاز همان قطعه را به اندازه زیر تغییر می‌دهد:

که عددی مثبت است. امتیاز قطعه‌ای که همین حالا اشتباه گرفته بود بالا می‌رود، یعنی دقیقاً در جهتی که باید می‌رفت. این قانون یک heuristic حدسی نیست؛ کوچک‌ترین تغییری است که می‌توان ثابت کرد مورد پیشِ رو را بهتر می‌کند. البته ممکن است یک مورد دیگر را خراب کند، و به همین دلیل دوباره دور می‌زنید.

به چیزی که غایب است توجه کنید. هیچ مشتقی هیچ‌جا وجود ندارد. این یک سهل‌انگاری نیست، و اولین ایده واقعاً مهم این دوره است.

چیزی که می‌خواستید مشتق بگیرید خطاست — تعداد قطعاتی که نادرست دسته‌بندی شده‌اند. اما این تعداد مثل یک پله است: وقتی خط را کمی هل می‌دهید روی 4 صاف می‌ماند، و درست در لحظه‌ای که خط از روی یک نقطه رد می‌شود به 3 سقوط می‌کند. مشتقش تقریباً همه‌جا صفر است و روی پله‌ها تعریف نشده. حساب دیفرانسیل چیزی برای چنگ زدن ندارد. قانون perceptron با دور زدن این مسئله کار می‌کند: اصلاً شیب نمی‌خواهد، فقط می‌پرسد «درست یا غلط؟»، و در جهتی حرکت می‌کند که بتواند هندسی توجیهش کند.

این یک راه‌حل واقعی است، و هم‌زمان یک بن‌بست. در فصل 2 به lossی نیاز خواهیم داشت که از جایی بیاید نه اینکه صرفاً انتخاب شده باشد، در فصل 4 مدلی می‌خواهیم که گزارش کند چقدر مطمئن است، و در فصل 5 چیزی با بیش از یک لایه — و هیچ‌کدام از قانونی که فقط «غلط» را می‌شناسد به دست نمی‌آیند. بازگرداندن یک شیب قابل استفاده همان چیزی است که دو فصل بعدی را ناگزیر می‌کند. اما perceptron کاری می‌کند که هیچ‌یک از جانشینانش نمی‌توانند: یادگیری بدون هیچ حساب دیفرانسیلی.

Python خالص، بدون NumPy. فهرست‌ها و یک حلقه. NumPy در فصل بعد می‌آید، جایی که حساب‌وکتاب دیگر در حلقه‌ای که بخواهید بخوانید جا نمی‌شود؛ معرفی کردنش در اینجا، دقیقاً در لحظه‌ای که می‌خواهید محاسبه را ببینید، آن را پشت یک کتابخانه پنهان می‌کرد.

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

چهار خط برجسته‌شده همان الگوریتم‌اند. بقیه فقط حساب‌داری است.

و نوار نقاله، با هشت قطعه‌ای که از روی آن اندازه‌گیری شده‌اند — چهار تا که ارسال شدند و چهار تا که برگشتند:

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)

این هشت قطعه با یک خط راست جداشدنی هستند — هر قطعه پذیرفته‌شده زیر 22 میلی‌متر است و هر قطعه ردشده 23 میلی‌متر یا بیشتر. یک حصار عمودی در 22 میلی‌متر کار را انجام می‌دهد. پس perceptron باید آن را پیدا کند.

اجرا کنید:

None [-142.1, -13.0] 54.0

دویست epoch، 454 تصحیح، و هنوز همگرا نشده است. وزن‌ها بزرگ‌اند و علامت اشتباه دارند. چیزی غلط است — جز اینکه هیچ چیز غلط نیست، و دلیلش مفیدترین چیز این فصل است.

perceptron یک تضمین دارد که Novikoff در 1962 آن را ثابت کرد.¹ اگر داده‌ها اصلاً با یک خط قابل جداسازی باشند، الگوریتم پیش از آنکه دیگر هیچ تصحیحی انجام ندهد، حداکثر این تعداد تصحیح انجام می‌دهد:

که در آن $R$ شعاع داده است، یعنی طول بلندترین بردار مثال، و $\gamma$ margin است: فاصله از hyperplane جداکننده تا نزدیک‌ترین نقطه در فضای افزوده‌ای که بایاس در آن مختصات سوم است. به همین دلیل مرکززدایی داده آن را تغییر می‌دهد، در حالی که فاصله بر حسب میلی‌متر تغییر نمی‌کند.

تضمین بی‌قیدوشرط است و هیچ اشاره‌ای به epochها، نرخ‌های یادگیری، یا شانس ندارد. همچنین هیچ اشاره‌ای به زمان ندارد، و نکته همین حذف است.

عددهای خودمان را بگذارید. مستقیماً از هشت قطعه اندازه‌گیری شده، با بایاس که به صورت یک feature ثابت درون داده تا شده است:

قضیه هرگز نقض نشده بود. نسخه خام را به اندازه کافی طولانی اجرا کنید و همگرا می‌شود — در epoch 11,976، پس از 29,870 تصحیح — کاملاً داخل کران 2,633,550 خودش، و همین فاصله خودش نکته است: قضیه بدترین حالت را کران‌گذاری می‌کند، نه حالت معمول را. فقط به شصت برابر epoch بیشتر از چیزی نیاز داشت که هر کسی حاضر باشد منتظرش بماند.

سطر دوم همان هشت قطعه است، همان بیست خط کد، با سه خط اضافه برای کم کردن میانگین عرض و میانگین وزن از هر اندازه‌گیری. همین. کل تغییر همین است. ابر نقاط را جابه‌جا می‌کند تا به جای اینکه دور از مبدأ در (22, 57) شناور باشد، دو سوی مبدأ را دربر بگیرد، و اثرش روی کران ضریبی برابر با پانزده هزار است، چون هر دو جمله هم‌زمان بهتر می‌شوند: $R$ از 74 به 13 می‌افتد چون نقاط دیگر از مبدأیی دوردست اندازه‌گیری نمی‌شوند، و $\gamma$ از 0.045 به 0.989 بالا می‌رود چون margin نسبت به بردار وزنی اندازه‌گیری می‌شود که دیگر مجبور نیست برای رسیدن به داده‌ها یک بایاس عظیم حمل کند.

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

در دو epoch همگرا شد، در حالی که دقیقاً یک‌بار خودش را تصحیح کرد.

اینجا یک درس واقعی وجود دارد و آن درس «یادتان باشد ورودی‌ها را normalize کنید» نیست، هرچند باید این کار را بکنید. درس این است که تضمین درباره اینکه یک الگوریتم تمام می‌شود، هیچ چیز درباره اینکه شما هنگام تمام شدنش آنجا خواهید بود نمی‌گوید، و فاصله میان این دو معمولاً هندسه است. این نخستین ظهور الگویی است که در فصل 6 با مقداردهی اولیه، در فصل 10 با زمان‌بندی‌های نرخ یادگیری، و در فصل 13 با quantisation دوباره خواهید دید: ریاضیات می‌گوید چیزی ممکن است، و مهندسی تصمیم می‌گیرد عملی هست یا نه. دوره‌ای که فقط قضیه را به شما یاد بدهد، مدلی تحویلتان می‌دهد که سه روز train می‌شود و شما را مقصر می‌داند.

حالا شکستی که به دوران اول شبکه‌های عصبی پایان داد، و در چهار سطر جا می‌شود.

کارخانه را فراموش کنید. دو ورودی بگیرید که هر کدام یا 0 هستند یا 1، و بخواهید پاسخ وقتی دقیقاً یکی از آن‌ها 1 است $+1$ باشد:

این XOR است — یاِ انحصاری. قبل از ادامه خواندن، چهار نقطه را روی کاغذ بکشید: سه گوشه یک مربع واحد و گوشه چهارم. دو گوشه قطری $(0,1)$ و $(1,0)$ را به عنوان accept علامت بزنید، و $(0,0)$ و $(1,1)$ را به عنوان reject. حالا یک خط راست بکشید که دو نقطه پذیرفته‌شده در یک سمت آن و دو نقطه ردشده در سمت دیگر باشند.

نمی‌توانید. مسئله این نیست که سخت است، یا اینکه به الگوریتمی هوشمندتر نیاز دارید؛ مسئله این است که چنین خطی وجود ندارد. سه خط جبر نشان می‌دهد چرا. اگر یک perceptron هر چهار مورد را درست می‌گرفت، خواندن چهار سطر به ترتیب می‌داد:

دو نامساوی وسط را جمع کنید: $w_1 + w_2 + 2b \geq 0$، پس $w_1 + w_2 \geq -2b$. آخری می‌گوید $w_1 + w_2 < -b$. با هم: $-2b \leq w_1 + w_2 < -b$، که نیازمند $-2b < -b$ است، که نیازمند $b > 0$ است. و نامساوی اول می‌گوید $b < 0$. چنین $b$ی وجود ندارد، پس چنین وزن‌هایی هم وجود ندارند. هیچ perceptronی، با هیچ عددی، XOR را دسته‌بندی نمی‌کند.

با این حال اجرا کنید، چون دیدن شکست یک الگوریتم از شنیدن اینکه شکست می‌خورد ارزشمندتر است:

     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

واگرا نمی‌شود، و نزدیک یک پاسخ قابل‌قبول هم دست‌وپا نمی‌زند. چرخه می‌زند: یک حلقه کوتاه را در فضای وزن طی می‌کند و دقیقاً به جایی که شروع کرده بود برمی‌گردد، برای همیشه، و دو مورد از چهار مورد را درست می‌گیرد — همان چیزی که با حدس زدن هم به دست می‌آوردید. صد هزار epoch و صد epoch غیرقابل‌تشخیص‌اند، چون الگوریتم پیشرفتی نمی‌کند که اجرای طولانی‌تر بتواند تمامش کند. این را با نوار نقاله مقایسه کنید که در 200 epoch گیرکرده به نظر می‌رسید و در واقع داشت به سمت یک پاسخ واقعی سایش پیدا می‌کرد. از بیرون، این دو در چند ثانیه اول شبیه هم‌اند. تشخیصشان از هم، بدون قضیه، ناممکن است — و این یک دلیل دیگر برای دانستن قضیه است.

در 1969 ماروین مینسکی و سیمور پاپرت Perceptrons را منتشر کردند، مطالعه‌ای ریاضی و کتاب‌طول درباره اینکه این مدل دقیقاً چه چیزهایی را می‌تواند و نمی‌تواند نمایش دهد.² XOR نقل‌شده‌ترین نتیجه آن است، و معمولاً از این نقل‌قول به عنوان اتهام استفاده می‌شود: اینکه کتاب از سر رقابت یا کینه پژوهش شبکه‌های عصبی را برای پانزده سال کشت.

ریاضیات کتاب درست است، و از مثال XOR جالب‌تر است. مینسکی و پاپرت در درجه اول علاقه‌مند نبودند که آیا یک perceptron تنها می‌تواند XOR انجام دهد یا نه؛ آن‌ها به این علاقه داشتند که وقتی به perceptronها میدان‌های دریافتی محدود داده می‌شود چه رخ می‌دهد — هر واحد فقط بخشی از ورودی را می‌بیند — و ثابت کردند که برخی ویژگی‌های سراسری یک تصویر، مثل اینکه آیا یک شکل متصل است یا نه، با این روش فارغ از تعداد واحدهایی که استفاده می‌کنید قابل محاسبه نیست. این نتیجه‌ای واقعاً عمیق درباره locality است، و هیچ ربطی به روایت مشهور ندارد.

روایت مشهور از نظر تاریخی هم غلط است. مینسکی و پاپرت صریحاً perceptronهای چندلایه را بحث می‌کنند و می‌گویند پرسش درباره قدرت آن‌ها باز است — آن‌ها حدس می‌زدند گسترش نظریه «عقیم» باشد، که یک پیش‌بینی است، نه اثبات، و اشتباه بود. چیزی که در 1969 کم بود ایده روی هم گذاشتن لایه‌ها نبود؛ راهی برای train کردن یک پشته بود. قانون perceptron نمی‌تواند این کار را بکند: باید بداند هر واحد چقدر اشتباه کرده، و برای واحدی که در میانه دفن شده هیچ برچسبی وجود ندارد که با آن مقایسه شود. این شکاف تا زمانی که backpropagation در 1986 فراگیر شد باز ماند،³ و بستن آن کاری است که فصل 5 انجام می‌دهد.

پس خلاصه صادقانه این است. کتاب یک محدودیت واقعیِ یک مدل واقعی را ثابت کرد. فروپاشی تأمین مالی این حوزه در دهه هفتاد علت‌های زیادی داشت، که یکی از آن‌ها این بود که وعده‌هایی که برای perceptronها در اوایل دهه شصت داده شده بود اغراق‌آمیز بودند. و مانع فنی قابل حل بود، اما هنوز هیچ‌کس ابزارش را نداشت.

perceptron شصت‌وهشت ساله است و شما همین حالا یکی نوشتید. ارزش دارد دقیق باشیم که کدام بخش‌های آن هنوز در ماشینی که این دوره را با آن تمام می‌کنید وجود دارند، چون پاسخ این است: بیشتر از چیزی که حدس می‌زنید.

perceptron هم‌زمان روی دو چیز گیر کرد، و معلوم می‌شود آن دو یک چیزند.

نمی‌تواند XOR را نمایش دهد، چون یک خط کافی نیست. رفع این مشکل یعنی روی هم گذاشتن لایه‌ها — لایه اول فضا را خم می‌کند، لایه دوم خط را در فضای خم‌شده می‌کشد. این فصل 5 است.

اما نمی‌توانید یک پشته را با قانون perceptron train کنید، چون فقط «غلط» را می‌شناسد، و واحدی در میانه یک شبکه برچسب خودش را ندارد که درباره آن اشتباه کرده باشد. برای train کردن یک پشته باید بدانید برای هر وزن چقدر اشتباه است، و در کدام جهت — به یک شیب نیاز دارید. و تابع خطای perceptron، همان پله، چنین چیزی ندارد.

پس پیش از پشته باید یک تابع loss با مشتق قابل استفاده وجود داشته باشد. نه تابعی که فقط چون مشتق گرفتن از آن راحت است انتخاب شده باشد: تابعی که از جایی بیاید، چیزی واقعی درباره داده بگوید، و gradient آن از همان معنا بیرون بیفتد، نه اینکه مهندسی معکوس شده باشد تا مرتب به نظر برسد.

این فصل 2 است، و با پرسشی شروع می‌شود که perceptron هرگز لازم نبود پاسخ دهد: نه «آیا این قطعه خوب است؟»، بلکه «اگر حقیقت این باشد، این خوانش‌ها چقدر محتمل‌اند؟»

خواندن این‌ها در کنار این فصل هم ارزش دارد: مقاله اصلی Rosenblatt، The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain (Psychological Review 65(6), 1958)، که از شهرتش خواندنی‌تر است؛ McCulloch و Pitts، A Logical Calculus of the Ideas Immanent in Nervous Activity (Bulletin of Mathematical Biophysics 5, 1943)، مقاله‌ای که نخستین بار یک نورون را به صورت آستانه‌ای روی یک مجموع وزن‌دار مدل کرد؛ بخش perceptron در A Course in Machine Learning اثر Hal Daumé III، که همان update را با تأکیدی متفاوت استخراج می‌کند؛ و فصل‌های 2 و 3 از Mathematics for Machine Learning اثر Deisenroth، Faisal و Ong برای جبر خطی، اگر کادر بالا کمتر از چیزی بود که می‌خواستید.