Το Perceptron από το μηδέν: τι υπολογίζει ένας νευρώνας

Ένα perceptron παίρνει τις μετρήσεις, πολλαπλασιάζει καθεμία με έναν αριθμό που ελέγχει, τις αθροίζει, προσθέτει έναν ακόμη αριθμό και κοιτάζει το πρόσημο.

Γράψτε τις μετρήσεις ενός εξαρτήματος ως διάνυσμα $\mathbf{x} = (x_1, x_2)$ — πλάτος και βάρος. Το perceptron κρατά ένα διάνυσμα βαρών $\mathbf{w} = (w_1, w_2)$ και ένα bias $b$. Η βαθμολογία του είναι

και η απάντησή του είναι το πρόσημο αυτής της βαθμολογίας: αποδοχή αν $s(\mathbf{x}) \geq 0$, αλλιώς απόρριψη.

Αυτό είναι ολόκληρο το μοντέλο. Όλα όσα θα μάθει ποτέ το perceptron για το εργοστάσιο ζουν σε τρεις αριθμούς.

Αξίζει να σταθούμε στη γεωμετρία, επειδή είναι η εικόνα που συνεχίζει να λειτουργεί για τα επόμενα είκοσι εννέα κεφάλαια ακόμη κι όταν οι εξισώσεις παύουν να χωρούν σε μία γραμμή. Το σύνολο των σημείων όπου $s(\mathbf{x}) = 0$ — όπου το perceptron είναι ακριβώς αναποφάσιστο — είναι μια ευθεία στο επίπεδο. Στη μία πλευρά η βαθμολογία είναι θετική και όλα γίνονται αποδεκτά· στην άλλη είναι αρνητική και όλα απορρίπτονται. Για ένα perceptron, μάθηση σημαίνει μετακίνηση αυτής της γραμμής.

Δύο γεγονότα για αυτή τη γραμμή προκύπτουν απευθείας από την άλγεβρα, και τα δύο θα έχουν σημασία αργότερα:

• Το $\mathbf{w}$ είναι κάθετο σε αυτήν. Το διάνυσμα βαρών δεν βρίσκεται κατά μήκος του ορίου, δείχνει απέναντί του, προς την πλευρά της αποδοχής.
• Το $b$ τη σύρει χωρίς να τη στρέφει. Χωρίς bias, η γραμμή θα αναγκαζόταν να περνά από την αρχή των αξόνων, κάτι που για ένα εργοστάσιο που μετρά χιλιοστά και γραμμάρια θα ήταν ένας παράλογος περιορισμός — θα σήμαινε ότι ένα εξάρτημα μηδενικού πλάτους και μηδενικού βάρους κάθεται ακριβώς πάνω στον φράχτη.

Το perceptron ξεκινά χωρίς να ξέρει τίποτα: $\mathbf{w} = (0, 0)$ και $b = 0$. Κάθε βαθμολογία είναι μηδέν, οπότε αποδέχεται τα πάντα.

Τώρα δείξτε του ένα παράδειγμα κάθε φορά. Επισημάνετε τα αποδεκτά εξαρτήματα ως $y = +1$ και τα απορριπτέα ως $y = -1$. Για κάθε παράδειγμα, κάντε μία ερώτηση: βγήκε σωστό το πρόσημο; Ο συμπαγής τρόπος να γράψετε αυτή την ερώτηση είναι να ελέγξετε αν το $y \cdot s(\mathbf{x})$ είναι θετικό — αν η ετικέτα και η βαθμολογία συμφωνούν στο πρόσημο, το γινόμενό τους είναι θετικό, και αν διαφωνούν είναι αρνητικό.

Αν η απάντηση είναι ναι, δεν αλλάζει τίποτα. Αν η απάντηση είναι όχι, κάντε ένα μικρό σπρώξιμο:

Αυτός είναι ολόκληρος ο αλγόριθμος, και αξίζει να καταλάβετε γιατί είναι το σωστό σπρώξιμο αντί να το απομνημονεύσετε. Υποθέστε ότι ένα εξάρτημα έπρεπε να είχε γίνει αποδεκτό ($y = +1$) και η βαθμολογία βγήκε αρνητική. Η προσθήκη του $\mathbf{x}$ στο $\mathbf{w}$ αλλάζει τη βαθμολογία στο ίδιο εξάρτημα κατά

που είναι ένας θετικός αριθμός. Η βαθμολογία στο εξάρτημα που μόλις έκανε λάθος ανεβαίνει, δηλαδή κινείται προς την κατεύθυνση που έπρεπε. Ο κανόνας δεν είναι μια ευρετική που μάντεψε κάποιος· είναι η μικρότερη αλλαγή που αποδεδειγμένα βελτιώνει την περίπτωση μπροστά του. Μπορεί φυσικά να χαλάσει μια άλλη περίπτωση, γι’ αυτό και γυρίζετε ξανά.

Προσέξτε τι απουσιάζει. Δεν υπάρχει πουθενά παράγωγος. Αυτό δεν είναι παράλειψη, και είναι η πρώτη πραγματικά σημαντική ιδέα του μαθήματος.

Αυτό που θα θέλατε να παραγωγίσετε είναι το σφάλμα — ο αριθμός των λανθασμένα ταξινομημένων εξαρτημάτων. Αλλά αυτός ο αριθμός είναι μια σκάλα: μένει επίπεδος στο 4 ενώ σπρώχνετε τη γραμμή, μετά πέφτει στο 3 τη στιγμή που η γραμμή διασχίζει ένα σημείο. Η παράγωγός του είναι μηδέν σχεδόν παντού και απροσδιόριστη στα σκαλοπάτια. Ο λογισμός δεν έχει από πού να πιαστεί. Ο κανόνας του perceptron το παρακάμπτει αυτό μη ζητώντας καθόλου κλίση: ρωτά μόνο «σωστό ή λάθος;» και κινείται σε μια κατεύθυνση που μπορεί να δικαιολογήσει γεωμετρικά.

Αυτό είναι μια γνήσια λύση, και είναι επίσης αδιέξοδο. Στο Κεφάλαιο 2 θα θέλουμε μια loss που να προέρχεται από κάπου αντί να επιλέγεται, στο Κεφάλαιο 4 ένα μοντέλο που να αναφέρει πόσο σίγουρο είναι, και στο Κεφάλαιο 5 κάτι με περισσότερα από ένα επίπεδα — και κανένα από αυτά δεν είναι προσβάσιμο από έναν κανόνα που ξέρει μόνο το «λάθος». Η ανάκτηση μιας χρήσιμης κλίσης είναι αυτό που επιβάλλει τα επόμενα δύο κεφάλαια. Αλλά το perceptron μπορεί να κάνει κάτι που κανένας από τους διαδόχους του δεν μπορεί: να μάθει χωρίς καθόλου λογισμό.

Καθαρή Python, χωρίς NumPy. Λίστες και ένα loop. Το NumPy έρχεται στο επόμενο κεφάλαιο, όπου η αριθμητική παύει να χωρά σε ένα loop που θα θέλατε να διαβάσετε· η εισαγωγή του τώρα θα έκρυβε την αριθμητική πίσω από μια βιβλιοθήκη ακριβώς τη στιγμή που θέλετε να τη δείτε.

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 mm και κάθε απορριπτέο είναι 23 mm ή περισσότερο. Ένας κατακόρυφος φράχτης στα 22 χιλιοστά κάνει τη δουλειά. Άρα το perceptron θα έπρεπε να τον βρει.

Τρέξτε το:

None [-142.1, -13.0] 54.0

Διακόσια epochs, 454 διορθώσεις, και δεν έχει συγκλίνει. Τα βάρη είναι μεγάλα και με λάθος πρόσημο. Κάτι δεν πάει καλά — μόνο που τίποτα δεν πάει στραβά, και ο λόγος είναι το πιο χρήσιμο πράγμα σε αυτό το κεφάλαιο.

Το perceptron έχει μια εγγύηση, αποδεδειγμένη από τον Novikoff το 1962.¹ Αν τα δεδομένα μπορούν έστω και καθόλου να διαχωριστούν από μια γραμμή, ο αλγόριθμος κάνει το πολύ

διορθώσεις πριν σταματήσει να κάνει οποιαδήποτε — όπου $R$ είναι η ακτίνα των δεδομένων, το μήκος του μεγαλύτερου διανύσματος παραδείγματος, και $\gamma$ είναι το περιθώριο: η απόσταση από το διαχωριστικό υπερεπίπεδο έως το κοντινότερο σημείο στον επαυξημένο χώρο όπου το bias είναι μια τρίτη συντεταγμένη. Γι’ αυτό το κεντράρισμα των δεδομένων το αλλάζει, ενώ η απόσταση σε χιλιοστά όχι.

Η εγγύηση είναι άνευ όρων και δεν αναφέρει epochs, learning rates ή τύχη. Επίσης δεν αναφέρει χρόνο, και αυτή η παράλειψη είναι το θέμα.

Βάλτε τους αριθμούς μας. Μετρημένοι απευθείας από τα οκτώ εξαρτήματα, με το bias διπλωμένο ως σταθερό χαρακτηριστικό:

Το θεώρημα δεν παραβιάστηκε ποτέ. Τρέξτε την ακατέργαστη εκδοχή αρκετά και όντως συγκλίνει — στο epoch 11,976, μετά από 29,870 διορθώσεις — άνετα μέσα στο όριό της των 2,633,550, και αυτό το χάσμα είναι και το ίδιο το θέμα: το θεώρημα φράζει τη χειρότερη περίπτωση, όχι την τυπική. Απλώς χρειαζόταν εξήντα φορές περισσότερα epochs απ’ όσα θα άντεχε να περιμένει κανείς.

Η δεύτερη γραμμή είναι τα ίδια οκτώ εξαρτήματα, οι ίδιες είκοσι γραμμές κώδικα, με τρεις γραμμές προστιθέμενες για να αφαιρούν το μέσο πλάτος και το μέσο βάρος από κάθε μέτρηση. Αυτό είναι όλο. Αυτή είναι ολόκληρη η αλλαγή. Μετακινεί το νέφος σημείων ώστε να αγκαλιάζει την αρχή των αξόνων αντί να αιωρείται στο (22, 57), και η επίδραση στο όριο είναι ένας παράγοντας δεκαπέντε χιλιάδων, επειδή και οι δύο όροι βελτιώνονται ταυτόχρονα: το $R$ πέφτει από 74 σε 13 επειδή τα σημεία δεν μετρώνται πλέον από μια μακρινή αρχή, και το $\gamma$ ανεβαίνει από 0.045 σε 0.989 επειδή το περιθώριο μετριέται απέναντι σε ένα διάνυσμα βαρών που δεν χρειάζεται πια να κουβαλά ένα τεράστιο bias για να φτάσει τα δεδομένα.

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 με τα προγράμματα learning-rate, και στο Κεφάλαιο 13 με την κβαντοποίηση: τα μαθηματικά λένε ότι το πράγμα είναι δυνατό, και η μηχανική αποφασίζει αν είναι πρακτικό. Ένα μάθημα που σας διδάσκει μόνο το θεώρημα σας δίνει ένα μοντέλο που εκπαιδεύεται για τρεις ημέρες και κατηγορεί εσάς.

Τώρα η αποτυχία που έκλεισε την πρώτη εποχή των νευρωνικών δικτύων, και χωρά σε τέσσερις γραμμές.

Ξεχάστε το εργοστάσιο. Πάρτε δύο εισόδους που είναι καθεμία είτε 0 είτε 1, και ζητήστε η απάντηση να είναι $+1$ όταν ακριβώς μία από αυτές είναι 1:

Αυτό είναι το XOR — αποκλειστικό ή. Πριν συνεχίσετε, σχεδιάστε τα τέσσερα σημεία σε χαρτί: τρεις γωνίες ενός μοναδιαίου τετραγώνου και την τέταρτη. Σημειώστε τις δύο διαγώνιες γωνίες $(0,1)$ και $(1,0)$ ως αποδοχή, και τις $(0,0)$ και $(1,1)$ ως απόρριψη. Τώρα σχεδιάστε μία ευθεία γραμμή με τα δύο αποδεκτά σημεία στη μία πλευρά και τα δύο απορριπτέα στην άλλη.

Δεν μπορείτε. Δεν είναι ότι είναι δύσκολο, ή ότι χρειάζεστε έναν εξυπνότερο αλγόριθμο· είναι ότι η γραμμή δεν υπάρχει. Τρεις γραμμές άλγεβρας δείχνουν γιατί. Αν ένα 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

Δεν αποκλίνει, και δεν ταλαντεύεται γύρω από μια αξιοπρεπή απάντηση. Κάνει κύκλο: περπατά έναν σύντομο βρόχο μέσα στον χώρο των βαρών και επιστρέφει ακριβώς εκεί από όπου ξεκίνησε, για πάντα, πετυχαίνοντας δύο από τα τέσσερα — αυτό που θα πετυχαίνατε και με μαντεψιά. Εκατό χιλιάδες epochs και εκατό είναι δυσδιάκριτα, επειδή ο αλγόριθμος δεν κάνει πρόοδο που μια μεγαλύτερη εκτέλεση θα μπορούσε να ολοκληρώσει. Συγκρίνετέ το με τον ιμάντα, που έμοιαζε κολλημένος στα 200 epochs και στην πραγματικότητα άλεθε προς μια πραγματική απάντηση. Απ’ έξω, τα δύο μοιάζουν παρόμοια τα πρώτα λίγα δευτερόλεπτα. Το να τα ξεχωρίσετε, χωρίς το θεώρημα, είναι αδύνατο — που είναι ένα ακόμη επιχείρημα υπέρ του να γνωρίζετε το θεώρημα.

Το 1969 οι Marvin Minsky και Seymour Papert δημοσίευσαν το Perceptrons, μια μαθηματική μελέτη σε έκταση βιβλίου για το τι ακριβώς μπορεί και δεν μπορεί να αναπαραστήσει αυτό το μοντέλο.² Το XOR είναι το πιο συχνά αναφερόμενο αποτέλεσμά του, και η αναφορά συνήθως χρησιμοποιείται ως κατηγορία: ότι το βιβλίο σκότωσε την έρευνα στα νευρωνικά δίκτυα για δεκαπέντε χρόνια από αντιζηλία ή κακία.

Τα μαθηματικά στο βιβλίο είναι σωστά, και είναι πιο ενδιαφέροντα από το παράδειγμα XOR. Οι Minsky και Papert δεν ενδιαφέρονταν κυρίως για το αν ένα μόνο perceptron μπορούσε να κάνει XOR· ενδιαφέρονταν για το τι συμβαίνει όταν στα perceptrons δίνονται περιορισμένα δεκτικά πεδία — κάθε μονάδα να βλέπει μόνο μέρος της εισόδου — και απέδειξαν ότι ορισμένες καθολικές ιδιότητες μιας εικόνας, όπως το αν ένα σχήμα είναι συνδεδεμένο, δεν μπορούν να υπολογιστούν έτσι ανεξάρτητα από το πόσες μονάδες χρησιμοποιείτε. Αυτό είναι ένα πραγματικά βαθύ αποτέλεσμα για την τοπικότητα, και δεν έχει καμία σχέση με τη δημοφιλή ιστορία.

Η δημοφιλής ιστορία είναι επίσης λάθος ιστορικά. Οι Minsky και Papert συζητούν ρητά τα πολυεπίπεδα perceptrons και λένε ότι το ερώτημα της ισχύος τους είναι ανοιχτό — υποψιάζονταν ότι η επέκταση της θεωρίας θα ήταν «στείρα», που είναι πρόβλεψη, όχι απόδειξη, και ήταν λάθος. Αυτό που έλειπε το 1969 δεν ήταν η ιδέα της στοίβαξης επιπέδων· ήταν ένας τρόπος να εκπαιδευτεί μια στοίβα. Ο κανόνας του perceptron δεν μπορεί να το κάνει: χρειάζεται να ξέρει πόσο λάθος είναι κάθε μονάδα, και για μια μονάδα θαμμένη στη μέση δεν υπάρχει ετικέτα για να συγκριθεί. Αυτό το κενό έμεινε ανοιχτό μέχρι να διαδοθεί το backpropagation το 1986,³ και το κλείσιμό του είναι αυτό που κάνει το Κεφάλαιο 5.

Άρα η έντιμη σύνοψη είναι αυτή. Το βιβλίο απέδειξε έναν πραγματικό περιορισμό ενός πραγματικού μοντέλου. Η κατάρρευση της χρηματοδότησης του πεδίου τη δεκαετία του εβδομήντα είχε πολλές αιτίες, μία από τις οποίες ήταν ότι οι υποσχέσεις που είχαν δοθεί για τα perceptrons στις αρχές της δεκαετίας του εξήντα ήταν υπερβολικές. Και το τεχνικό εμπόδιο ήταν επιλύσιμο, αλλά κανείς δεν είχε ακόμη το εργαλείο.

Το perceptron είναι εξήντα οκτώ ετών και μόλις γράψατε ένα. Αξίζει να είμαστε ακριβείς για το ποια μέρη του εξακολουθούν να υπάρχουν στη μηχανή με την οποία θα τελειώσετε αυτό το μάθημα, επειδή η απάντηση είναι: περισσότερα απ’ όσα θα μαντεύατε.

Το perceptron κόλλησε σε δύο πράγματα ταυτόχρονα, και αποδεικνύεται ότι είναι το ίδιο πράγμα.

Δεν μπορεί να αναπαραστήσει το XOR, επειδή μία γραμμή δεν αρκεί. Η διόρθωση αυτού σημαίνει στοίβαξη επιπέδων — ένα πρώτο επίπεδο που λυγίζει τον χώρο, ένα δεύτερο που σχεδιάζει τη γραμμή στον λυγισμένο χώρο. Αυτό είναι το Κεφάλαιο 5.

Αλλά δεν μπορείτε να εκπαιδεύσετε μια στοίβα με τον κανόνα του perceptron, επειδή ξέρει μόνο το «λάθος», και μια μονάδα στη μέση ενός δικτύου δεν έχει δική της ετικέτα για να κάνει λάθος σε σχέση με αυτήν. Για να εκπαιδεύσετε μια στοίβα πρέπει να ξέρετε πόσο λάθος, και προς ποια κατεύθυνση, για κάθε βάρος — χρειάζεστε μια κλίση. Και η συνάρτηση σφάλματος του perceptron, η σκάλα, δεν έχει.

Άρα πριν από τη στοίβα πρέπει να υπάρξει μια loss function με χρήσιμη παράγωγο. Όχι μία που επιλέγεται επειδή είναι βολική στην παραγώγιση, επίσης: μία που προέρχεται από κάπου, που λέει κάτι αληθινό για τα δεδομένα, και της οποίας το 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, που παράγει την ίδια ενημέρωση με διαφορετική έμφαση· και τα κεφάλαια 2 και 3 του Mathematics for Machine Learning των Deisenroth, Faisal και Ong για τη γραμμική άλγεβρα, αν το παραπάνω πλαίσιο σας άφησε να θέλετε περισσότερα απ’ όσα έδωσε.