Gradient Descent

Εισαγωγή

Φανταστείτε ότι έχουμε μια συνάρτηση $f(x)$ και θα θέλαμε να βρούμε το ελάχιστο της. Τι θα έκανες ;

Απλό σωστά; Χρειάζεται μόνο να λύσουμε την ακόλουθη εξίσωση:

$f'(x) = 0$

Το θέμα είναι ότι η εύρεση της φόρμουλας του $f'$ δεν είναι πάντα εύκολη καθώς τείνουν να είναι εξαιρετικά περίπλοκες ειδικά στη βαθιά εκμάθηση όπου έχουμε να κάνουμε με πολύπλοκες συναρτήσεις. Πρέπει λοιπόν να βρούμε μια άλλη μέθοδο που μπορεί να μας παρέχει το ελάχιστο μιας συνάρτησης χωρίς να χρειάζεται να βρούμε τον τύπο της παραγώγου $f'$.

Ας χτίσουμε λίγη διαίσθηση

Ας υποθέσουμε ότι έχουμε μια συνάρτηση f με το αντίστοιχο γράφημα:

Ας ξεκινήσουμε με ένα τυχαίο σημείο $x_{0}$. Ο στόχος είναι να μετακινήσετε αυτό το σημείο και να το κάνετε όλο και πιο κοντά στο $x*$ έτσι ώστε $f'($x*$) = 0$. Το πρόβλημα λοιπόν μπορεί να χωριστεί σε δύο μέρη:

• Προς ποια κατεύθυνση πρέπει να μετακινήσουμε το σημείο $x$; Αριστερά ή δεξιά ;

• Πόσο να το μετακινήσουμε;

Η κατεύθυνση

Ας δημιουργήσουμε λίγη διαίσθηση για να απαντήσουμε στην πρώτη ερώτηση. Ρίξτε μια ματιά στο παρακάτω σημείο:

Σημειώστε ότι:

• όταν το σημείο $x_{0}$ βρίσκεται στα δεξιά του βέλτιστου σημείου $x*$, η εφαπτομένη του ανεβαίνει.

• όταν το σημείο $x_{0}$ βρίσκεται στα δεξιά του βέλτιστου σημείου $x*$, η εφαπτομένη του κατεβαίνει.

Η κατεύθυνση μιας γραμμής καθορίζεται από το πρόσημο της κλίσης της:

• Μια γραμμή ανεβαίνει $\υποδηλώνει$ η κλίση $a$ είναι θετική.

• Μια γραμμή κατεβαίνει $\υποδηλώνει$ η κλίση $a$ είναι αρνητική.

Σημειώστε ότι: \

Η κλίση της εφαπτομένης μιας συνάρτησης σε ένα ορισμένο σημείο $x_{0}$ δεν είναι μεγαλύτερη από την παράγωγο σε αυτό το σημείο $f'(x_{0})$:

$tangent(x*{0}): g(x) = f'(x*{0}).(x-x*{0}) + f(x*{0})$

Ως απάντηση λοιπόν στην ερώτηση "Πού πρέπει να μετακινήσουμε $x_{0}$ ?":

• $f'(x_{0}) < 0$ $\implies$ $x_{0}$ στα δεξιά του $x*$ $\implies$ Πρέπει να μετακινήσουμε το $x_{0}$ προς τα αριστερά.

• $f'(x_{0}) > 0$ $\implies$ $x_{0}$ στα αριστερά του $x*$ $\implies$ Πρέπει να μετακινήσουμε το $x_{0}$ προς τα δεξιά.

Τα βήματα

Τώρα για τη δεύτερη ερώτηση, Πόσο πρέπει να μετακινήσουμε $x_{0}$ ?

Ρίξτε μια ματιά στα ακόλουθα παραδείγματα:

Μπορούμε να συμπεράνουμε ότι:

• $x_{0}$ είναι κοντά στο $x*$ => Η κλίση της εφαπτομένης είναι μικρή => η $f'(x_{0})$ είναι μικρή.

• Η $x_{0}$ απέχει από την $x*$ => Η κλίση της εφαπτομένης είναι μεγάλη => η $f'(x_{0})$ είναι μεγάλη.

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

Κλίση κατάβασης

Το Gradient descent είναι η διατύπωση των απαντήσεων των δύο προηγούμενων ερωτήσεων. Είναι ένας επαναληπτικός αλγόριθμος βελτιστοποίησης που προσεγγίζει το ελάχιστο $x*$ της συνάρτησης ξεκινώντας από ένα τυχαίο αρχικό σημείο $x_{0}$. Ο αλγόριθμος δηλώνεται ως εξής:

$x*{n+1} = x*{n} - lr \times \frac{\mathrm{d} f}{\mathrm{d} x\_{n}}$

που:

• $\frac{\mathrm{d} f}{\mathrm{d} x*{n}}$ δεν είναι περισσότερο από την παράγωγο του $f$ στο σημείο $x*{n}$.

• Το $lr$ είναι μια θετική σταθερά που καθορίζει πόσο μεγάλα θα είναι τα βήματα.

Σημειώσε ότι:

• Το $x_{n}$ βρίσκεται στα δεξιά του $x*$ => $\frac{\mathrm{d} f}{\mathrm{d} x_{n}} > 0$ => $x_{n+ 1} = x_{n} - θετικό$ => $x_{n}$ μετακινείται προς τα αριστερά.

• Το $x_{n}$ βρίσκεται στα αριστερά του $x*$ => $\frac{\mathrm{d} f}{\mathrm{d} x_{n}} < 0$ => $x*{n +1} = x*{n} + θετικό$ => $x_{n}$ μετακινείται προς τα δεξιά.

• $x_{n}$ κοντά στο $x*$ => $\frac{\mathrm{d} f}{\mathrm{d} x_{n}}$ κοντά στο $0$ => Μικρή ενημέρωση σε $x_{ n}$.

Κουίζ

• Πότε σταματά η επανάληψη της κλίσης κατάβασης:

• Όταν το $x_{n}$ είναι αρκετά μικρό.

• Όταν το $x_{n}$ είναι κοντά στο $x_{0}$ .

• Όταν $\frac{\mathrm{d} f}{\mathrm{d} x\_{n}} = 0$. XXX

• Πώς επιλέγουμε $x_{0}$:

• Το επιλέγουμε τυχαία. XXX

• Το παίρνουμε στη γειτονιά των $x{n}$.

• Εξαρτάται από το πρόβλημα.

• Γιατί χρειαζόμαστε κλίση κατάβασης:

• Επειδή οι υπολογιστές δεν είναι αρκετά ισχυροί για τον υπολογισμό των παραγώγων.

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

• Επειδή οι συναρτήσεις έχουν περισσότερα από ένα τοπικά ελάχιστα.