הפרספטרון מאפס: מה נוירון מחשב

פרספטרון לוקח את המדידות, מכפיל כל אחת במספר שהוא שולט בו, מחבר אותן, מוסיף עוד מספר אחד, ומסתכל על הסימן.

נכתוב את המדידות של חלק אחד כווקטור $\mathbf{x} = (x_1, x_2)$ — רוחב ומשקל. הפרספטרון מחזיק וקטור משקלים $\mathbf{w} = (w_1, w_2)$ והטיה $b$. הציון שלו הוא

והתשובה שלו היא הסימן של הציון הזה: לקבל אם $s(\mathbf{x}) \geq 0$, אחרת לדחות.

זה כל המודל. כל מה שהפרספטרון אי פעם ידע על המפעל חי בשלושה מספרים.

כדאי לעצור רגע על הגאומטריה, כי זו התמונה שממשיכה לעבוד בעשרים ותשעה הפרקים הבאים גם כשהמשוואות כבר לא נכנסות לשורה אחת. קבוצת הנקודות שבהן $s(\mathbf{x}) = 0$ — המקום שבו הפרספטרון בדיוק לא החליט — היא קו ישר במישור. בצד אחד הציון חיובי והכול מתקבל; בצד השני הוא שלילי והכול נדחה. למידה, עבור פרספטרון, פירושה להזיז את הקו הזה.

שתי עובדות על הקו הזה נובעות ישירות מהאלגברה, ושתיהן יהיו חשובות בהמשך:

• $\mathbf{w}$ מאונך לו. וקטור המשקלים אינו שוכב לאורך הגבול; הוא מצביע לרוחבו, לכיוון הצד המתקבל.
• $b$ מזיז אותו בלי לסובב אותו. בלי הטיה, הקו היה מוכרח לעבור דרך הראשית, וזה אילוץ מגוחך עבור מפעל שמודד מילימטרים וגרמים — המשמעות הייתה שחלק ברוחב אפס ובמשקל אפס יושב בדיוק על הגדר.

הפרספטרון מתחיל בלי לדעת כלום: $\mathbf{w} = (0, 0)$ ו-$b = 0$. כל ציון הוא אפס, ולכן הוא מקבל הכול.

עכשיו מראים לו דוגמה אחת בכל פעם. מסמנים את החלקים שהתקבלו ב-$y = +1$ ואת אלה שנדחו ב-$y = -1$. לכל דוגמה שואלים שאלה אחת: האם הסימן יצא נכון? הדרך הקומפקטית לכתוב את השאלה היא לבדוק אם $y \cdot s(\mathbf{x})$ חיובי — אם התווית והציון מסכימים בסימן, המכפלה שלהם חיובית, ואם הם לא מסכימים היא שלילית.

אם התשובה היא כן, לא משנים כלום. אם התשובה היא לא, נותנים דחיפה קטנה:

זה כל האלגוריתם, וכדאי להבין למה זו הדחיפה הנכונה במקום לשנן אותה. נניח שחלק היה אמור להתקבל ($y = +1$) והציון יצא שלילי. הוספת $\mathbf{x}$ ל-$\mathbf{w}$ משנה את הציון על אותו חלק עצמו ב-

וזה מספר חיובי. הציון על החלק שבו הוא בדיוק טעה עולה למעלה, וזה הכיוון שאליו הוא היה צריך לזוז. הכלל אינו היוריסטיקה שמישהו ניחש; הוא השינוי הקטן ביותר שמשפר באופן ניתן להוכחה את המקרה שמולו. הוא כמובן עלול לשבור מקרה אחר, ולכן עוברים שוב.

שימו לב למה שחסר. אין כאן נגזרת בשום מקום. זו לא השמטה, וזה הרעיון החשוב באמת הראשון בקורס.

מה שהייתם רוצים לגזור הוא השגיאה — מספר החלקים שסווגו לא נכון. אבל המספר הזה הוא מדרגות: הוא נשאר שטוח על 4 בזמן שמזיזים מעט את הקו, ואז יורד ל-3 ברגע שהקו חוצה נקודה. הנגזרת שלו היא אפס כמעט בכל מקום ולא מוגדרת במדרגות. לחשבון דיפרנציאלי אין במה להיאחז. כלל הפרספטרון עוקף את זה בכך שהוא בכלל לא מבקש שיפוע: הוא שואל רק "נכון או לא נכון?", וזז בכיוון שהוא יכול להצדיק גאומטרית.

זה פתרון אמיתי, וזה גם מבוי סתום. בפרק 2 נרצה פונקציית הפסד שמגיעה ממקום כלשהו ולא פשוט נבחרת, בפרק 4 מודל שמדווח כמה בטוח הוא, ובפרק 5 משהו עם יותר משכבה אחת — ואף אחד מהם לא נגיש מכלל שיודע רק "לא נכון". החזרת שיפוע שימושי היא מה שמכריח את שני הפרקים הבאים. אבל לפרספטרון מותר לעשות משהו שאף אחד מיורשיו לא יכול: ללמוד בלי חדו״א בכלל.

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 מילימטרים עושה את העבודה. אז הפרספטרון אמור למצוא אותה.

מריצים:

None [-142.1, -13.0] 54.0

מאתיים epochs, 454 תיקונים, והוא לא התכנס. המשקלים גדולים ובסימן הלא נכון. משהו לא בסדר — חוץ מזה ששום דבר לא לא בסדר, והסיבה היא הדבר הכי שימושי בפרק הזה.

לפרספטרון יש הבטחה, שנוביקוף הוכיח ב-1962.¹ אם אפשר להפריד את הנתונים בקו בכלל, האלגוריתם יבצע לכל היותר

תיקונים לפני שיפסיק לבצע תיקונים — כאשר $R$ הוא רדיוס הנתונים, האורך של וקטור הדוגמה הארוך ביותר, ו-$\gamma$ הוא ה-margin: המרחק מההיפר-מישור המפריד לנקודה הקרובה ביותר במרחב המורחב שבו ההטיה היא קואורדינטה שלישית. זו הסיבה שמרכוז הנתונים משנה אותו, בעוד שהמרחק במילימטרים לא משתנה.

ההבטחה אינה מותנית והיא לא מזכירה epochs, קצבי למידה או מזל. היא גם לא מזכירה זמן, וההשמטה הזאת היא העניין.

נציב את המספרים שלנו. במדידה ישירה משמונת החלקים, כשההטיה מקופלת פנימה כמאפיין קבוע:

המשפט מעולם לא הופר. הריצו את הגרסה הגולמית מספיק זמן והיא כן מתכנסת — ב-epoch 11,976, אחרי 29,870 תיקונים — בנוחות בתוך החסם שלה, 2,633,550, והפער הזה הוא עצמו העניין: המשפט חוסם את המקרה הגרוע ביותר, לא את הטיפוסי. הוא פשוט היה צריך פי שישים יותר epochs ממה שמישהו היה יושב לחכות לו.

השורה השנייה היא אותם שמונה חלקים, אותן עשרים שורות קוד, עם שלוש שורות שנוספו כדי להחסיר את רוחב הממוצע ואת משקל הממוצע מכל מדידה. זהו. זה כל השינוי. הוא מזיז את ענן הנקודות כך שהוא חוצה את הראשית במקום לצוף סביב (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

התכנס בשני epochs, אחרי שתיקן את עצמו בדיוק פעם אחת.

יש כאן שיעור אמיתי, והוא לא "זכרו לנרמל את הקלטים שלכם", אף שכדאי לעשות זאת. הוא שהבטחה לגבי השאלה אם אלגוריתם יסיים לא אומרת לכם כלום לגבי השאלה אם תהיו שם כשהוא יסיים, ושהפער בין השניים הוא בדרך כלל גאומטריה. זו ההופעה הראשונה של דפוס שתפגשו שוב בפרק 6 עם אתחול, בפרק 10 עם לוחות זמנים לקצב למידה, ובפרק 13 עם קוונטיזציה: המתמטיקה אומרת שהדבר אפשרי, וההנדסה מחליטה אם הוא מעשי. קורס שמלמד אתכם רק את המשפט נותן לכם מודל שמתאמן שלושה ימים ומאשים אתכם.

עכשיו הכישלון שסיים את העידן הראשון של רשתות נוירונים, והוא נכנס בארבע שורות.

עזבו את המפעל. קחו שני קלטים שכל אחד מהם הוא 0 או 1, ובקשו שהתשובה תהיה $+1$ כאשר בדיוק אחד מהם הוא 1:

זה XOR — או בלעדי. לפני שממשיכים, ציירו את ארבע הנקודות על נייר: שלוש פינות של ריבוע יחידה ואת הרביעית. סמנו את שתי הפינות האלכסוניות $(0,1)$ ו-$(1,0)$ כקבלה, ואת $(0,0)$ ו-$(1,1)$ כדחייה. עכשיו ציירו קו ישר אחד עם שתי הנקודות שהתקבלו בצד אחד ושתי הנקודות שנדחו בצד השני.

אי אפשר. זה לא שקשה, או שצריך אלגוריתם חכם יותר; הקו פשוט לא קיים. שלוש שורות של אלגברה מראות למה. אם פרספטרון היה מסווג נכון את כל הארבע, אז קריאת ארבע השורות לפי הסדר נותנת

חברו את שני אי-השוויונים האמצעיים: $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$ כזה, ולכן אין משקלים כאלה. שום פרספטרון, עם מספרים כלשהם, לא מסווג 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

הוא לא מתבדר, והוא לא משתולל ליד תשובה סבירה. הוא מחזורי: הוא הולך בלולאה קצרה במרחב המשקלים וחוזר בדיוק למקום שבו התחיל, לנצח, עם שתיים מתוך ארבע נכונות — מה שהייתם מקבלים בניחוש. מאה אלף epochs ומאה נראים אותו דבר, כי האלגוריתם לא מתקדם באופן שריצה ארוכה יותר יכולה להשלים. השוו זאת למסוע, שנראה תקוע ב-200 epochs ולמעשה חרק בדרכו לתשובה אמיתית. מבחוץ השניים נראים דומים בשניות הראשונות. להבדיל ביניהם, בלי המשפט, בלתי אפשרי — וזה עוד טיעון בעד להכיר את המשפט.

ב-1969 פרסמו מרווין מינסקי וסימור פייפרט את Perceptrons, מחקר מתמטי באורך ספר על בדיוק מה המודל הזה יכול ולא יכול לייצג.² XOR הוא התוצאה המצוטטת ביותר שלו, והציטוט בדרך כלל משמש כהאשמה: שהספר הרג את המחקר ברשתות נוירונים לחמש עשרה שנה מתוך יריבות או זדון.

המתמטיקה בספר נכונה, והיא מעניינת יותר מדוגמת XOR. מינסקי ופייפרט לא התעניינו בעיקר בשאלה אם פרספטרון יחיד יכול לבצע XOR; הם התעניינו במה שקורה כאשר לפרספטרונים נותנים שדות קליטה מוגבלים — כל יחידה רואה רק חלק מהקלט — והם הוכיחו שתכונות גלובליות מסוימות של תמונה, למשל האם צורה מחוברת, לא ניתנות לחישוב כך בלי קשר למספר היחידות שבהן משתמשים. זו תוצאה עמוקה באמת על מקומיות, ואין לה שום קשר לסיפור הפופולרי.

הסיפור הפופולרי גם שגוי היסטורית. מינסקי ופייפרט דנים במפורש בפרספטרונים מרובי שכבות ואומרים ששאלת הכוח שלהם פתוחה — הם חשדו שהרחבת התאוריה תהיה "עקרה", וזו תחזית, לא הוכחה, והיא הייתה שגויה. מה שהיה חסר ב-1969 לא היה רעיון ערימת השכבות; זו הייתה דרך לאמן ערימה. כלל הפרספטרון לא יכול לעשות זאת: הוא צריך לדעת עד כמה כל יחידה טועה, וליחידה שקבורה באמצע אין תווית להשוות מולה. הפער הזה נשאר פתוח עד ש-backpropagation נהפך לנפוץ ב-1986,³ וסגירתו היא מה שפרק 5 עושה.

אז הסיכום ההוגן הוא זה. הספר הוכיח מגבלה אמיתית של מודל אמיתי. לקריסת המימון של התחום בשנות השבעים היו סיבות רבות, שאחת מהן הייתה שההבטחות שניתנו לפרספטרונים בתחילת שנות השישים היו מופרזות. והמכשול הטכני היה פתיר, אבל לאף אחד עדיין לא היה הכלי.

הפרספטרון בן שישים ושמונה, והרגע כתבתם אחד. כדאי לדייק אילו חלקים ממנו עדיין נמצאים במכונה שתסיימו איתה את הקורס, כי התשובה היא: יותר ממה שהייתם מנחשים.

הפרספטרון נתקע על שני דברים בבת אחת, ומתברר שהם אותו הדבר.

הוא לא יכול לייצג XOR, כי קו אחד לא מספיק. כדי לתקן את זה צריך לערום שכבות — שכבה ראשונה שמכופפת את המרחב, שכבה שנייה שמציירת את הקו במרחב המכופף. זה פרק 5.

אבל אי אפשר לאמן ערימה עם כלל הפרספטרון, כי הוא יודע רק "לא נכון", וליחידה באמצע רשת אין תווית משלה שעליה היא יכולה לטעות. כדי לאמן ערימה צריך לדעת כמה לא נכון, ובאיזה כיוון, עבור כל משקל — צריך שיפוע. ולפונקציית השגיאה של הפרספטרון, גרם המדרגות, אין כזה.

אז לפני הערימה חייבת להיות פונקציית הפסד עם נגזרת שימושית. וגם לא כזו שנבחרה כי נוח לגזור אותה: כזו שמגיעה ממקום כלשהו, שאומרת משהו אמיתי על הנתונים, ושהגרדיאנט שלה נובע מהמשמעות הזאת במקום להיות מהונדס לאחור כדי להיראות מסודר.

זה פרק 2, והוא מתחיל בשאלה שהפרספטרון מעולם לא היה צריך לענות עליה: לא "האם החלק הזה טוב?", אלא "עד כמה סבירות המדידות האלה, אם זו האמת?"

כדאי לקרוא לצד הפרק הזה גם את המאמר המקורי של רוזנבלט, The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain (Psychological Review 65(6), 1958), שהוא קריא יותר מהמוניטין שלו; את McCulloch and Pitts, A Logical Calculus of the Ideas Immanent in Nervous Activity (Bulletin of Mathematical Biophysics 5, 1943), המאמר שמידל לראשונה נוירון כסף מעל סכום משוקלל; את פרק הפרספטרון ב-A Course in Machine Learning של Hal Daumé III, שמגזר את אותו עדכון עם דגש אחר; ואת פרקים 2 ו-3 ב-Mathematics for Machine Learning של Deisenroth, Faisal and Ong לאלגברה הלינארית, אם התיבה למעלה השאירה אתכם רוצים יותר ממה שנתנה.