Gibbs Sampling: Μια αποδοτική μέθοδος MCMC

Η δειγματοληψία Gibbs είναι ένας από τους πιο διαδεδομένους αλγόριθμους Markov Chain Monte Carlo (MCMC).

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

---

1. Η βασική ιδέα

Σκοπός είναι να παραγάγουμε μια ακολουθία τυχαίων δειγμάτων $(x^{(1)}, x^{(2)}, \dots)$ από μια πολυδιάστατη κατανομή πιθανότητας $p(x_1, x_2, \dots, x_n)$.

Σε πολλές περιπτώσεις, η κοινή κατανομή είναι δύσκολο να δειγματοληφθεί άμεσα, αλλά οι υπό συνθήκη κατανομές (conditional distributions) κάθε μεταβλητής είναι πολύ απλούστερες.

Η ιδέα του Gibbs είναι να εκμεταλλευτούμε αυτή την απλότητα:

• Αντί να δειγματοληπτούμε όλες τις μεταβλητές μαζί,

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

---

2. Ο αλγόριθμος βήμα-βήμα

Έστω ότι θέλουμε να δειγματοληπτούμε από την κατανομή $p(x_1,x_2,\dots,x_n)$:

1. Αρχικοποίηση
   Επιλέγουμε μια τυχαία αρχική τιμή $(x_1^{(0)}, x_2^{(0)}, \dots, x_n^{(0)})$.

2. Επανάληψη για κάθε βήμα $t = 1, 2, \dots, T$:

   • Δειγματοληπτούμε:

     $$x_1^{(t)}\sim p(x_1\mid x_2^{(t-1)},x_3^{(t-1)},\dots ,x_n^{(t-1)})$$

   • Έπειτα:

     $$x_2^{(t)}\sim p(x_2\mid x_1^{(t)},x_3^{(t-1)},\dots ,x_n^{(t-1)})$$

   • Συνεχίζουμε ανάλογα για όλες τις μεταβλητές.

3. Σύγκλιση
   Για μεγάλο αριθμό επαναλήψεων, τα δείγματα $(x_1^{(t)}, \dots, x_n^{(t)})$ προσεγγίζουν την πραγματική κατανομή $p(x_1,\dots,x_n)$.

---

3. Παράδειγμα με δύο μεταβλητές

Έστω ότι έχουμε μια διδιάστατη κατανομή $p(x,y)$.
Ο αλγόριθμος Gibbs δουλεύει ως εξής:

1. Επιλέγουμε τυχαία αρχικές τιμές $x^{(0)}, y^{(0)}$.

2. Για κάθε βήμα $t$:

   • Υπολογίζουμε:

     $$x^{(t)}\sim p(x\mid y^{(t-1)})$$

   • Έπειτα:

     $$y^{(t)}\sim p(y\mid x^{(t)})$$

3. Επαναλαμβάνουμε.

Έπειτα από αρκετά βήματα, τα σημεία $(x^{(t)}, y^{(t)})$ κατανέμονται όπως η αρχική $p(x,y)$.

---

4. Γιατί δουλεύει;

Η δειγματοληψία Gibbs βασίζεται στο ότι:

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

• Η αλυσίδα Markov που δημιουργείται έχει μοναδική στάσιμη κατανομή, που είναι η ζητούμενη $p$.

• Με αρκετές επαναλήψεις, ο αλγόριθμος συγκλίνει στην πραγματική κατανομή.

---

5. Εφαρμογές

Η δειγματοληψία Gibbs έχει ευρύτατη χρήση σε στατιστική και μηχανική μάθηση:

• Βαϊζιανή συμπερασματολογία — υπολογισμός posterior όταν η αναλυτική λύση είναι δύσκολη.

• Topic Modeling — μοντέλα όπως το LDA χρησιμοποιούν εκτενώς Gibbs sampling.

• Εκπαίδευση Restricted Boltzmann Machines (RBMs) στη μηχανική μάθηση.

• Βιοστατιστική, επεξεργασία εικόνας, γενετική ανάλυση και οικονομετρία.

---

6. Πλεονεκτήματα και μειονεκτήματα

Πλεονεκτήματα ✅

• Απλός στην υλοποίηση.

• Ιδανικός για υψηλές διαστάσεις.

• Συχνά οι συνθήκες έχουν κλειστή μορφή.

Μειονεκτήματα ⚠️

• Αργή σύγκλιση αν οι μεταβλητές έχουν μεγάλη συσχέτιση.

• Απαιτεί να μπορούμε να υπολογίζουμε εύκολα τις υπό συνθήκη κατανομές.

• Μπορεί να «κολλήσει» σε τοπικές περιοχές αν η κατανομή είναι πολύπλοκη.

---

Συμπέρασμα

Η δειγματοληψία Gibbs είναι ένα από τα ισχυρότερα εργαλεία της MCMC.

Μας επιτρέπει να δουλεύουμε με πολύπλοκες κατανομές, ακόμη και σε υψηλές διαστάσεις, όταν η άμεση δειγματοληψία είναι ανέφικτη.