Perceptron

Ο νευρώνας Perceptron ή Αντίληπτρο είναι ένα είδος τεχνητού νευρωνικού δικτύου που εφευρέθηκε το 1957 στο Αεροναυτικό Εργαστήριο του Κορνέλλ (Cornell Aeronautical Laboratory) από τον Φρανκ Ρόζενμπλαττ (Frank Rosenblatt). Μπορεί να χαρακτηριστεί ώς ένα απλό είδος ενός εμπροσθοτροφοδοτούμενου (feed-forward) νευρωνικού δικτύου: ένας γραμμικός ταξινομητής (linear classifier).

Ορισμός

Ο Perceptron είναι ένας δυαδικός ταξινομητής, δηλαδή μία συνάρτηση η οποία απεικονίζει την είσοδο $x$ (ένα διάνυσμα με πραγματικές τιμές) σε μία τιμή εξόδου $f(x)$ (μία και μοναδική δυαδική τιμή).

$f(x)={\begin{cases}1&{\text{if }}w\cdot x b>0\\0&{\text{else}}\end{cases}}$

όπου $w$ είναι ένα διάνυσμα από βάρη με πραγματικές τιμές και $w\cdot x$ είναι το εσωτερικό γινόμενο μεταξύ των διανυσμάτων $w$ και $x$ (Υπολογίζεται δηλαδή ένα βεβαρημένο άθροισμα). To $b$ είναι το 'bias', ένας σταθερός όρος ο οποίος δεν εξαρτάται από καμία τιμή εισόδου.

Η τιμή της $f(x)$ (0 ή 1) χρησιμοποιείται για να ταξινομήσει το $x$ είτε ως θετικό ή αρνητικό στιγμιότυπο, στην περίπτωση ενός δυαδικού προβλήματος ταξινόμησης. Το bias χρησιμοποιείται για την μετατόπιση της συνάρτησης ενεργοποίησης ή για να δώσει στον νευρώνα εξόδου ένα βασικό επίπεδο δραστηριότητας. Αν το $b$ είναι αρνητικό τότε ο βεβαρημένος συνδυασμός των εισόδων πρέπει να παραγάγει μία θετική τιμή μεγαλύτερη του $-b$ έτσι ώστε να αναγκάσει τον νευρώνα που ταξινομεί να έχει τιμή άνω του κατωφλίου 0. Χωρικά, το bias μεταβάλει την θέση (αλλά όχι τον προσανατολισμό) του συνόρου απόφασης.

Εφόσον οι είσοδοι τροφοδοτούνται στο δίκτυο άμεσα μέσω των βεβαρημένων συνδέσεων, ο νευρώνας μπορεί να θεωρηθεί ως ένα απλό είδος νευρωνικού δικτύου εμπρός τροφοδότησης.

Αλγόριθμος Μάθησης

Ο αλγόριθμος μάθησης (αγγλικά: learning algorithm) είναι ίδιος για όλους τους νευρώνες, έτσι αυτά που ακολουθούν εφαρμόζονται σε έναν νευρώνα σε απομόνωση. Πρώτα όμως παρουσιάζεται ο ορισμός κάποιων μεταβλητών:

• $x(j)$ είναι το j-οστό στοιχείο του διανύσματος εισόδου
• $w(j)$ είναι το j-οστό στοιχείο του διανύσματος βαρών
• $y$ είναι το αποτέλεσμα του νευρώνα
• $\delta$ είναι το επιθυμητό αποτέλεσμα
• $\alpha$ είναι μια σταθερά όπου $0<\alpha <1$ (ρυθμός μάθησης)

Τα βάρη (W₁, W₂,..., W_n) εφαρμόζονται στις εισόδους (i₁, i₂, ...), τα οποία περνιούνται στην συνάρτηση f, η οποία παράγει την έξοδο o.

Τα βάρη ενημερώνονται μετά από κάθε είσοδο με βάση τον παρακάτω κανόνα ενημέρωσης:

• $w(j)'=w(j) \alpha (\delta -y)x(j)$

Με αυτόν τον τρόπο, η εκμάθηση μοντελοποιείται καθώς το διάνυσμα με τα βάρη ενημερώνεται μετά από μία επανάληψη, η οποία θα πραγματοποιηθεί μόνο αν η έξοδος $y$ είναι διαφορετική από το επιθυμητό αποτέλεσμα $\delta$.

Θεωρώντας ακόμη έναν μοναδικό νευρώνα αλλά προσπαθώντας να πραγματοποιήσουμε πολλές επαναλήψεις, ας ορίσουμε μερικές ακόμη μεταβλητές:

• $x_{i}$ είναι το διάνυσμα εισόδου για την i-οστή επανάληψη
• $w_{i}$ είναι το διάνυσμα με τα βάρη για την i-οστή επανάληψη
• $y_{i}$ είναι η έξοδος για την i-οστή επανάληψη
• $D_{m}=\{(x_{1},y_{1}),\dots ,(x_{m},y_{m})\}$ είναι ένα σύνολο εκμάθησης $m$ επαναλήψεων

Για ευκολία υποθέτουμε δυαδικές τιμές για τα επιθυμητά αποτελέσματα $y_{i}$:

• $y_{i}=1$ για θετικές επαναλήψεις
• $y_{i}=0$ για αρνητικές επαναλήψεις

Σε κάθε επανάληψη το διάνυσμα με τα βάρη ενημερώνεται ως ακολούθως:

• Για κάθε $(x,y)$ ζευγάρι στο σύνολο $D_{m}=\{(x_{1},y_{1}),\dots ,(x_{m},y_{m})\}$
• Πέρασε το $(x_{i},y_{i},w_{i})$ στον κανόνα ενημέρωσης $w(j)'=w(j) \alpha (\delta -y)x(j)$

Το Perceptron μπορεί να εκπαιδευτεί με ένα απλό επί γραμμής (on-line) αλγόριθμο εκμάθησης, στον οποίο παραδείγματα παρουσιάζονται επαναληπτικά και διορθώσεις στα διανύσματα βάρους γίνονται κάθε φορά που εμφανίζεται ένα λαθος (εκμάθηση με παραδείγματα). Όταν γίνεται ένα λάθος, το διάνυσμα με τα βάρη διαρθώνεται με τον εξής τρόπο: $w_{k 1}\leftarrow w_{k} \eta \ y_{i}x_{i}$ και ο όρος bias με τον εξής: $b_{k 1}\leftarrow b_{k} \eta \ y_{i}R^{2}$, όπου το $\eta \$ είναι ο ρυθμός εκμάθησης (ο οποίος μπορεί να φαίνεται ασυσχέτιστος) και το $R$ είναι το μέγιστο μέτρο του διανύσματος εισόδου.

Το σύνολο εκμαθησησς $D_{m}$ λέγεται γραμμικώς διαχωρίσιμο αν υπάρχει μια θετική σταθερά $\gamma$ και ένα διάνυσμα βαρών $w$ τέτοια ώστε $y_{i}\cdot \left(\langle w,x_{i}\rangle b\right)>\gamma$ για άλα τα i. Ο Νόβικοφ (Novikoff 1962) απέδειξε ότι ο αλγόριθμος εκμάθησης του Perceptron συγκλίνει μετά από έναν πεπερασμένο αριθμό επαναλήψεων εάν το σύνολο δεδομένων είναι γραμμικώς διαχωρίσιμο και το άνω φράγμα του αριθμού σφαλμάτων είναι ίσο με $\left({\frac {2R}{\gamma }}\right)^{2}$. Ωστόσο, αν το σύνολο εκμάθησης δεν είναι γραμμικώς διαχωρίσιμο, δεν είναι εγγυημένο ότι ο παραπάνω επί γραμμής αλγόριθμος θα συγκλίνει.

Ιστορία

Παρ'όλο που το Perceptron έμοιαζε πολλά υποσχόμενο στην αρχή, εν τέλει αποδείχθηκε ότι τα Perceptrons δεν μπορούν να εκπαιδευθούν για να αναγνωρίζουν πολλές κατηγορίες προτύπων. Αυτό είχε ως αποτέλεσμα η έρευνα στα νευρωνικά δίκτυα να τελματώσει για πολλά χρόνια, προτού βρεθεί ότι ένα εμπροσθοτροφοδοτούμενο νευρωνικό δίκτυο με δύο ή περισσότερα επίπεδα (αποκαλούμενο επίσης ως πολυεπίπεδο ή πολυστρωματικό εμπροσθοτροφοδοτούμενο νευρωνικό δίκτυο) έχει πολύ περισσότερη επεξεργαστική ισχύ από ένα Perceptron ενός επιπέδου. Perceptrons ενός επιπέδου είναι ικανά για την εκμάθηση γραμμικώς διαχωρίσιμων προτύπων μόνο. Το 1969, ένα διάσημο βιβλίο με τίτλο Perceptrons, από τον Μάρβιν Μίνσκυ (Marvin Minsky) και τον Σέιμουρ Πέιπερτ (Seymour Papert), παρουσίαζε ότι είναι αδύνατο για τέτοιυ είδους δίκτυα να μάθουν μία συνάρτηση XOR. Είκασαν (εσφαλμένως) ότι ένα παρόμοιο αποτέλεσμα θα ισχύει και για ένα Perceptron με τρία ή περισσότερα επίπεδα. Τρία χρόνια αργότερρα, ο Στίβεν Γκρόσσμπεργκ (Stephen Grossberg) δημοσίευσε μία σειρά διατριβών στις οποίες παρουσίαζε δίκτυα ικανά να μοντελοποιήσουν συναρτήσεις διαφορικές, βελτίωσης αντίθεσης και XOR. (Οι διατριβές δημοσιεύθηκαν το 1972 και 1973, δείτε π.χ.: Grossberg, Contour enhancement, short-term memory, constancies in reverberating neural networks. Studies in Applied Mathematics, 52 (1973), 213-257, online [1]). Μολαταύτα, το συχνά αναφερόμενο βιβλίο του Μίνσκυ και Πέιπερτ προκάλεσε σημαντική μείωση στο ενδιαφέρον και τη χρηματοδότηση ερευνών πάνω στα νευρωνικά δίκτυα. Χρειάστηκαν ακόμη δέκα χρόνια μέχρις ότου να ανακάμψει η έρευνα στα νευρωνικά δίκτυα, στα μέσα της δεκαετίας του 1980. Το διάσημο βιβλίο επανεκτυπώθηκε το 1987 ως "Perceptrons - Expanded Edition" (Perceptrons - Διευρυμένη Έκδοση), όπου κάποια λάθη στο αρχικό κείμενο διορθώθηκαν. Προσφάτως, το ενδιαφέρον πάνω στον αλγόριθμο εκμάθησης ενός Perceptron έχει αναθερμανθεί μετά την παρουσίαση (Freund & Schapire 1998) ενός αλγορίθμου οποίος χρησιμοποιεί μία μέθοδο ψηφοφορίας.

Αναφορές

• Freund, Y. and Schapire, R. E. 1998. Large margin classification using the perceptron algorithm. In Proceedings of the 11th Annual Conference on Computational Learning Theory (COLT' 98). ACM Press.
• Rosenblatt, Frank (1958), The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain, Cornell Aeronautical Laboratory, Psychological Review, v65, No. 6, pp. 386–408.
• Minsky M L and Papert S A 1969 Perceptrons (Cambridge, MA: MIT Press)
• Novikoff, A. B. (1962). On convergence proofs on perceptrons. Symposium on the Mathematical Theory of Automata, 12, 615-622. Polytechnic Institute of Brooklyn.
• Widrow, B., Lehr, M.A., "30 years of Adaptive Neural Networks: Perceptron, Madaline, and Backpropagation," Proc. IEEE, vol 78, no 9, pp. 1415–1442, (1990).

Εξωτερικές Συνδέσεις

• Κεφάλαιο 3, Βεβαρημένα δίκτυα - το Perceptron, and κεφάλαιο 4, Perceptron εκμάθηση, του Νευρωνικά Δίκτυα - Μία Συστηματική Εισαγωγή από τον Ραούλ Ρόχας (Raúl Rojas) (ISBN 978-3540605058)
• Υλοποίηση ενός Perceptron σε C#
• Ιστορία των Perceptrons
• Μαθηματικά των Perceptrons
• Μικροεφαρμογή (applet) με την αναπαράσταση ενός Perceptron και εισαγωγή με παραδείγματα