Perceptron

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μετάβαση σε: πλοήγηση, αναζήτηση

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

Ορισμός[Επεξεργασία | επεξεργασία κώδικα]

O 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 (Yπολογίζεται δηλαδή ένα βεβαρημένο άθροισμα). 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 (ρυθμός μάθησης)
Τα βάρη (w1, w2,...) εφαρμόζονται στις εισόδους (x1, x2, ...), τα οποία περνιούνται στην συνάρτηση f, η οποία παράγει την έξοδο y

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

  • 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).

Σημειώσεις[Επεξεργασία | επεξεργασία κώδικα]

Εξωτερικές Συνδέσεις[Επεξεργασία | επεξεργασία κώδικα]