Κατανόηση της Στοχαστικής Μέσης Κλίσης

Το Gradient descent είναι η πιο δημοφιλής τεχνική βελτιστοποίησης στη μοντελοποίηση μηχανικής μάθησης (ML). Ο αλγόριθμος ελαχιστοποιεί το σφάλμα μεταξύ των προβλεπόμενων τιμών και της βασικής αλήθειας. Εφόσον η τεχνική θεωρεί ότι κάθε σημείο δεδομένων κατανοεί και ελαχιστοποιεί το σφάλμα, η απόδοσή της εξαρτάται από το μέγεθος των δεδομένων εκπαίδευσης. Τεχνικές όπως η Στοχαστική Κάθοδος Κλίσης (SGD) έχουν σχεδιαστεί για να βελτιώνουν την απόδοση υπολογισμού αλλά με κόστος την ακρίβεια σύγκλισης.

Το Stochastic Average Gradient εξισορροπεί την κλασική προσέγγιση, γνωστή ως Full Gradient Descent και SGD, και προσφέρει και τα δύο οφέλη. Αλλά πριν μπορέσουμε να χρησιμοποιήσουμε τον αλγόριθμο, πρέπει πρώτα να κατανοήσουμε τη σημασία του για τη βελτιστοποίηση του μοντέλου.

Βελτιστοποίηση στόχων μηχανικής μάθησης με βαθμίδωση

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

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

Ο αλγόριθμος ελαχιστοποίησης χρησιμοποιεί gradient descent για να διασχίσει τη συνάρτηση απώλειας και να βρει ένα συνολικό ελάχιστο. Κάθε βήμα διέλευσης περιλαμβάνει την ενημέρωση των βαρών του αλγορίθμου για τη βελτιστοποίηση της παραγωγής.

Κάθοδος απλής κλίσης

Ο συμβατικός αλγόριθμος gradient descent χρησιμοποιεί τον μέσο όρο όλων των διαβαθμίσεων που υπολογίζονται σε ολόκληρο το σύνολο δεδομένων. Ο κύκλος ζωής ενός μεμονωμένου παραδείγματος εκπαίδευσης μοιάζει με τον ακόλουθο:

Η εξίσωση ενημέρωσης βάρους έχει την εξής μορφή:

Όπου W αντιπροσωπεύει τα βάρη του μοντέλου και dJ/dW είναι η παράγωγος της συνάρτησης απώλειας σε σχέση με το βάρος του μοντέλου. Η συμβατική μέθοδος έχει υψηλό ποσοστό σύγκλισης, αλλά καθίσταται υπολογιστικά ακριβή όταν ασχολείται με μεγάλα σύνολα δεδομένων που περιλαμβάνουν εκατομμύρια σημεία δεδομένων.

Στοχαστική κλίση κάθοδος (SGD)

Η μεθοδολογία SGD παραμένει η ίδια με την απλή GD, αλλά αντί να χρησιμοποιεί ολόκληρο το σύνολο δεδομένων για τον υπολογισμό των κλίσεων, χρησιμοποιεί μια μικρή παρτίδα από τις εισόδους. Η μέθοδος είναι πολύ πιο αποτελεσματική, αλλά μπορεί να πηδήξει πάρα πολύ γύρω από τα καθολικά ελάχιστα δεδομένου ότι κάθε επανάληψη χρησιμοποιεί μόνο ένα μέρος των δεδομένων για μάθηση.

Στοχαστική μέση κλίση

Η προσέγγιση της Στοχαστικής Μέσης Διαβάθμισης (SAG) εισήχθη ως η μέση λύση μεταξύ GD και SGD. Επιλέγει ένα τυχαίο σημείο δεδομένων και ενημερώνει την τιμή του με βάση τη διαβάθμιση σε αυτό το σημείο και έναν σταθμισμένο μέσο όρο των προηγούμενων διαβαθμίσεων που έχουν αποθηκευτεί για το συγκεκριμένο σημείο δεδομένων.

Παρόμοια με το SGD, το SAG μοντελοποιεί κάθε πρόβλημα ως ένα πεπερασμένο άθροισμα κυρτών, διαφοροποιήσιμων συναρτήσεων. Σε κάθε δεδομένη επανάληψη, χρησιμοποιεί τις παρούσες κλίσεις και τον μέσο όρο των προηγούμενων κλίσεων για την ενημέρωση βάρους. Η εξίσωση έχει την ακόλουθη μορφή:

Ποσοστό Σύγκλισης

Μεταξύ των δύο δημοφιλών αλγορίθμων, της πλήρους διαβάθμισης (FG) και της στοχαστικής διαβάθμισης (SGD), ο αλγόριθμος FG έχει καλύτερο ρυθμό σύγκλισης αφού χρησιμοποιεί ολόκληρο το σύνολο δεδομένων κατά τη διάρκεια κάθε επανάληψης για υπολογισμό.

Αν και το SAG έχει δομή παρόμοια με το SGD, το ποσοστό σύγκλισής του είναι συγκρίσιμο και μερικές φορές καλύτερο από την προσέγγιση πλήρους κλίσης. Ο Πίνακας 1 παρακάτω συνοψίζει τα αποτελέσματα από τα πειράματα του Schmidt et. al .

Περαιτέρω Τροποποιήσεις

Παρά την εκπληκτική του απόδοση, έχουν προταθεί αρκετές τροποποιήσεις στον αρχικό αλγόριθμο SGD για να βοηθήσουν στη βελτίωση της απόδοσης.

• Επαναστάθμιση στις πρώιμες επαναλήψεις: Η σύγκλιση SAG παραμένει αργή κατά τις πρώτες λίγες επαναλήψεις, καθώς ο αλγόριθμος κανονικοποιεί την κατεύθυνση με n (συνολικός αριθμός σημείων δεδομένων). Αυτό παρέχει μια ανακριβή εκτίμηση, καθώς ο αλγόριθμος δεν έχει δει ακόμη πολλά σημεία δεδομένων. Η τροποποίηση προτείνει την κανονικοποίηση με το m αντί για το n, όπου m είναι ο αριθμός των σημείων δεδομένων που φαίνονται τουλάχιστον μία φορά μέχρι τη συγκεκριμένη επανάληψη.
• Mini-batches: Η προσέγγιση Stochastic Gradient χρησιμοποιεί μίνι-παρτίδες για την ταυτόχρονη επεξεργασία πολλαπλών σημείων δεδομένων. Η ίδια προσέγγιση μπορεί να εφαρμοστεί και στο SAG. Αυτό επιτρέπει τη διανυσματική και παραλληλοποίηση για βελτιωμένη απόδοση του υπολογιστή. Μειώνει επίσης το φορτίο μνήμης, μια σημαντική πρόκληση για τον αλγόριθμο SAG.
• Πειραματισμός Step-Size: Το μέγεθος βήματος που αναφέρθηκε προηγουμένως (116L) παρέχει εκπληκτικά αποτελέσματα, αλλά οι συγγραφείς πειραματίστηκαν περαιτέρω χρησιμοποιώντας το μέγεθος βήματος του 1L. Το τελευταίο παρείχε ακόμη καλύτερη σύγκλιση. Ωστόσο, οι συγγραφείς δεν μπόρεσαν να παρουσιάσουν επίσημη ανάλυση των βελτιωμένων αποτελεσμάτων. Κατέληξαν στο συμπέρασμα ότι το μέγεθος του βήματος πρέπει να πειραματιστεί για να βρεθεί το βέλτιστο για το συγκεκριμένο πρόβλημα.

Τελικές Σκέψεις

Το Gradient descent είναι μια δημοφιλής βελτιστοποίηση που χρησιμοποιείται για τον εντοπισμό των καθολικών ελάχιστων των παρεχόμενων αντικειμενικών συναρτήσεων. Ο αλγόριθμος χρησιμοποιεί τη διαβάθμιση της αντικειμενικής συνάρτησης για να διασχίσει την κλίση της συνάρτησης μέχρι να φτάσει στο χαμηλότερο σημείο.

Το Full Gradient Descent (FG) και το Stochastic Gradient Descent (SGD) είναι δύο δημοφιλείς παραλλαγές του αλγορίθμου. Το FG χρησιμοποιεί ολόκληρο το σύνολο δεδομένων κατά τη διάρκεια κάθε επανάληψης και παρέχει υψηλό ποσοστό σύγκλισης με υψηλό υπολογιστικό κόστος. Σε κάθε επανάληψη, το SGD χρησιμοποιεί ένα υποσύνολο δεδομένων για να εκτελέσει τον αλγόριθμο. Είναι πολύ πιο αποτελεσματικό αλλά με αβέβαιη σύγκλιση.

Το Stochastic Average Gradient (SAG) είναι μια άλλη παραλλαγή που παρέχει τα οφέλη και των δύο προηγούμενων αλγορίθμων. Χρησιμοποιεί τον μέσο όρο των προηγούμενων κλίσεων και ένα υποσύνολο του συνόλου δεδομένων για να παρέχει υψηλό ποσοστό σύγκλισης με χαμηλό υπολογισμό. Ο αλγόριθμος μπορεί να τροποποιηθεί περαιτέρω για να βελτιωθεί η αποτελεσματικότητά του χρησιμοποιώντας διανυσματοποίηση και mini-batches.