Κατιούσα κλίση — αλγόριθμος, ρυθμός μάθησης και παραλλαγές

Η κατιούσα κλίση είναι ένας αλγόριθμος για την ελαχιστοποίηση μιας παραγωγίσιμης συνάρτησης, κάνοντας επαναλαμβανόμενα βήματα προς την κατεύθυνση που τη μειώνει περισσότερο τοπικά. Αν ψάχνεις «τι είναι η κατιούσα κλίση», η βασική ιδέα είναι απλή: υπολόγισε την κλίση, κινήσου λίγο προς τα κάτω και επανάλαβε.

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

Σε μία μεταβλητή, ο κανόνας ενημέρωσης είναι

$$x_{k+1} = x_k - \eta f'(x_k),$$

και σε πολλές μεταβλητές γίνεται

$$\mathbf{x}_{k+1} = \mathbf{x}_k - \eta \nabla f(\mathbf{x}_k),$$

όπου $\eta > 0$ είναι ο ρυθμός μάθησης. Ο ρυθμός μάθησης ελέγχει πόσο μακριά πηγαίνει κάθε βήμα, άρα επηρεάζει άμεσα το αν ο αλγόριθμος συγκλίνει, κολλάει ή υπερπηδά το ελάχιστο.

Διαίσθηση για την κατιούσα κλίση

Η κλίση δείχνει προς τα πάνω. Αν ο στόχος σου είναι η ελαχιστοποίηση, η φυσική τοπική κίνηση είναι να πας προς την αντίθετη κατεύθυνση.

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

Πώς λειτουργεί ο αλγόριθμος της κατιούσας κλίσης

Κάθε επανάληψη χρησιμοποιεί την τρέχουσα πληροφορία της κλίσης, ενημερώνει το σημείο και ελέγχει αν πρέπει να συνεχίσει.

1. Ξεκίνα με μια αρχική εκτίμηση $x_0$ ή $\mathbf{x}_0$.
2. Υπολόγισε την παράγωγο ή την κλίση στο τρέχον σημείο.
3. Ενημέρωσε αφαιρώντας $\eta$ φορές αυτή την παράγωγο ή κλίση.
4. Σταμάτα όταν η κλίση είναι μικρή, οι ενημερώσεις γίνουν πολύ μικρές ή φτάσεις σε ένα προκαθορισμένο όριο επαναλήψεων.

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

Γιατί ο ρυθμός μάθησης έχει σημασία στην κατιούσα κλίση

Ο ρυθμός μάθησης $\eta$ είναι το μέγεθος βήματος.

Αν το $\eta$ είναι πολύ μικρό, η κατιούσα κλίση συνήθως κινείται προς τη σωστή κατεύθυνση αλλά μπορεί να είναι βασανιστικά αργή. Αν το $\eta$ είναι πολύ μεγάλο, οι ενημερώσεις μπορεί να υπερπηδούν το ελάχιστο, να πηγαίνουν μπρος-πίσω ή ακόμη και να αποκλίνουν.

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

Λυμένο παράδειγμα: κατιούσα κλίση σε τετραγωνική συνάρτηση

Θεώρησε

$$f(x) = (x-3)^2.$$

Αυτή η συνάρτηση έχει ελάχιστο στο $x=3$. Η παράγωγός της είναι

$$f'(x) = 2(x-3).$$

Χρησιμοποίησε κατιούσα κλίση με ρυθμό μάθησης $\eta = 0.1$ και αρχικό σημείο $x_0 = 0$.

Τότε ο κανόνας ενημέρωσης είναι

$$x_{k+1} = x_k - 0.1 \cdot 2(x_k-3) = x_k - 0.2(x_k-3).$$

Ξεκινώντας από $x_0 = 0$:

$$x_1 = 0 - 0.2(0-3) = 0.6.$$

Έπειτα

$$x_2 = 0.6 - 0.2(0.6-3) = 1.08.$$

και

$$x_3 = 1.08 - 0.2(1.08-3) = 1.464.$$

Κάθε βήμα σε φέρνει πιο κοντά στο $3$, και η τιμή της συνάρτησης μειώνεται κάθε φορά. Αυτό είναι το βασικό μοτίβο που πρέπει να προσέξεις: η κατιούσα κλίση δεν πηδά κατευθείαν στην απάντηση. Βελτιώνει την εκτίμηση με επαναλαμβανόμενες τοπικές διορθώσεις.

Συνήθεις παραλλαγές της κατιούσας κλίσης

Batch Gradient Descent

Η batch gradient descent χρησιμοποιεί ολόκληρο το σύνολο δεδομένων για να υπολογίσει κάθε ενημέρωση. Για μια σταθερή αντικειμενική συνάρτηση, αυτό δίνει ένα ντετερμινιστικό βήμα, αλλά μπορεί να είναι ακριβό όταν το σύνολο δεδομένων είναι μεγάλο.

Stochastic Gradient Descent

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

Mini-Batch Gradient Descent

Η mini-batch gradient descent χρησιμοποιεί μια μικρή ομάδα δειγμάτων σε κάθε βήμα. Αυτό είναι συχνά ένας πρακτικός συμβιβασμός, επειδή μειώνει τον θόρυβο σε σχέση με τις καθαρά στοχαστικές ενημερώσεις, ενώ παραμένει πολύ φθηνότερη από τις ενημερώσεις πλήρους batch.

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

Συνηθισμένα λάθη με την κατιούσα κλίση

Να θεωρείς τον ρυθμό μάθησης κάτι επιφανειακό

Η αλλαγή του $\eta$ αλλάζει τη συμπεριφορά του ίδιου του αλγορίθμου. Μια μέθοδος που συγκλίνει για έναν ρυθμό μάθησης μπορεί να αποτύχει για έναν άλλο.

Να υποθέτεις ότι η κατιούσα κλίση βρίσκει πάντα το ολικό ελάχιστο

Αυτό το συμπέρασμα χρειάζεται προϋποθέσεις. Για παράδειγμα, η κυρτότητα δίνει πολύ ισχυρότερες εγγυήσεις από ένα γενικό μη κυρτό τοπίο.

Να αγνοείς την κλίμακα των χαρακτηριστικών σε εφαρμοσμένα προβλήματα

Σε προβλήματα βελτιστοποίησης με κακώς κλιμακωμένες μεταβλητές, μία κατεύθυνση μπορεί να αλλάζει πολύ πιο γρήγορα από μια άλλη. Τότε η κατιούσα κλίση μπορεί να κάνει ζιγκ-ζαγκ και να συγκλίνει αργά, εκτός αν το πρόβλημα αναδιατυπωθεί ή κλιμακωθεί πιο προσεκτικά.

Να σταματάς μόνο επειδή η κλίση δεν είναι ακριβώς μηδέν

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

Πότε χρησιμοποιείται η κατιούσα κλίση

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

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

Δοκίμασε ένα παρόμοιο πρόβλημα

Δοκίμασε τη δική σου εκδοχή με $f(x) = (x-5)^2$ και αρχικό σημείο $x_0 = 12$. Τρέξε μία περίπτωση με $\eta = 0.1$ και μία άλλη με $\eta = 1.2$. Αν δεις μία σταθερή εκτέλεση και μία ασταθή, ο ρόλος του ρυθμού μάθησης γίνεται πολύ πιο ξεκάθαρος από ό,τι μόνο με τον τύπο.