Το μοντέλο μείγματος διεργασίας Dirichlet

• Ιούνιος 23, 2014
• Βασίλης Βρυνιώτης
• . 2 Σχόλια

Αυτή η ανάρτηση ιστολογίου είναι το τέταρτο μέρος της σειράς Ομαδοποίηση με μοντέλα μείγματος διεργασίας Dirichlet. Σε προηγούμενα άρθρα συζητήσαμε τα μοντέλα πεπερασμένων μιγμάτων Dirichlet και πήραμε το όριο του μοντέλου τους για άπειρες συστάδες που μας οδήγησαν στην εισαγωγή των διεργασιών Dirichlet. Όπως είδαμε, στόχος μας είναι να φτιάξουμε ένα μείγμα μοντέλο που δεν απαιτεί από εμάς να καθορίσουμε τον αριθμό των συστάδων / συστατικών k. Μετά παρουσιάζοντας διαφορετικές αναπαραστάσεις της διαδικασίας Dirichlet, τώρα ήρθε η ώρα να χρησιμοποιήσουμε πραγματικά DPs για να κατασκευάσουμε ένα άπειρο μοντέλο μίξης που μας επιτρέπει να κάνουμε ομαδοποίηση. Ο στόχος αυτού του άρθρου είναι να καθορίσει τα μοντέλα μείγματος διεργασίας Dirichlet και να συζητήσει τη χρήση της διαδικασίας κινεζικής εστιατορίας και της δειγματοληψίας Gibbs Εάν δεν έχετε διαβάσει τις προηγούμενες δημοσιεύσεις, συνιστάται να το κάνετε καθώς το θέμα είναι λίγο θεωρητικό και απαιτεί καλή κατανόηση για την κατασκευή του μοντέλου.

Ενημέρωση: Το Datumbox Machine Learning Framework είναι τώρα ανοιχτού κώδικα και δωρεάν κατεβάσετε. Ρίξτε μια ματιά στο πακέτο com.datumbox.framework.machinelearning.clustering για να δείτε την υλοποίηση Dirichlet Process Mixture Models στην Java.

1. Ορισμός του μοντέλου μείγματος διεργασίας Dirichlet

Η χρήση Dirichlet Processes μας επιτρέπει να έχουμε ένα μείγμα μοντέλου με άπειρα συστατικά που μπορεί να θεωρηθεί ότι παίρνει το όριο του πεπερασμένου μοντέλου για το k έως το άπειρο. Ας υποθέσουμε ότι έχουμε το ακόλουθο μοντέλο:

Εξίσωση 1: Μοντέλο μείγματος διεργασίας Dirichlet

Όπου το G ορίζεται ως και χρησιμοποιείται ως σύντομος συμβολισμός για που είναι μια συνάρτηση δέλτα που παίρνει 1 εάν και 0 αλλού. Η θ_i είναι οι παράμετροι συμπλέγματος που λαμβάνονται από το G. Η γενετική κατανομή F διαμορφώνεται από παραμέτρους συμπλέγματος θ_i και χρησιμοποιείται για τη δημιουργία x_i παρατηρήσεις. Τέλος μπορούμε να ορίσουμε μια κατανομή πυκνότητας η οποία είναι η κατανομή μιγμάτων μας (μετρήσιμο άπειρο μείγμα) με αναλογίες ανάμειξης και ανάμειξη συστατικών .

Σχήμα 1: Γραφικό μοντέλο μοντέλου μείγματος διεργασίας Dirichlet

Πάνω μπορούμε να δούμε το αντίστοιχο Γραφικό Μοντέλο του DPMM. Το G₀ είναι η βασική κατανομή του DP και συνήθως επιλέγεται για σύζευξη πριν από τη γενική κατανομή F μας, προκειμένου να κάνουμε τους υπολογισμούς ευκολότερους και να χρησιμοποιήσουμε τις ελκυστικές μαθηματικές ιδιότητες. Το α είναι το κλιμακωτό υπερπαραμέτρο της διαδικασίας Dirichlet και επηρεάζει τον αριθμό των συστάδων που θα λάβουμε. Όσο μεγαλύτερη είναι η τιμή του α, τόσο περισσότερες είναι οι συστάδες. όσο μικρότερη είναι η α τόσο λιγότερες συστάδες. Πρέπει να σημειώσουμε ότι η τιμή του α εκφράζει η δύναμη της πίστης στο G₀. Μια μεγάλη τιμή δείχνει ότι τα περισσότερα δείγματα θα είναι διακριτά και θα έχουν τιμές συγκεντρωμένες στο G₀. Το G είναι μια τυχαία κατανομή πάνω στον χώρο παραμέτρων Θ που λαμβάνεται ως δείγμα από το DP που εκχωρεί πιθανότητες στις παραμέτρους. Η θ_i είναι ένα διάνυσμα παραμέτρων που αντλείται από την κατανομή G και περιέχει τις παραμέτρους του συμπλέγματος, η κατανομή F παραμετροποιείται από θ_i και x_i είναι το σημείο δεδομένων που δημιουργείται από το Generative Distribution F.

Είναι σημαντικό να σημειωθεί ότι το θ_i είναι στοιχεία του χώρου παραμέτρων Θ και «διαμορφώνουν» τις συστάδες μας. Μπορούν επίσης να θεωρηθούν ως λανθάνουσες μεταβλητές στο x_i που μας λένε από ποιο στοιχείο / σύμπλεγμα το x_i προέρχεται και ποιες είναι οι παράμετροι αυτού του στοιχείου. Έτσι για κάθε x_i που παρατηρούμε, σχεδιάζουμε ένα θ_i από τη διανομή G. Με κάθε κλήρωση, η διανομή αλλάζει ανάλογα με τις προηγούμενες επιλογές. Όπως είδαμε στο σχήμα δοχείου Blackwell-MacQueen, η διανομή G μπορεί να ενσωματωθεί και οι μελλοντικές μας επιλογές θ_i εξαρτάται μόνο από το G₀: . Η εκτίμηση των παραμέτρων θi από τον προηγούμενο τύπο δεν είναι πάντοτε εφικτή, επειδή πολλές εφαρμογές (όπως η Κινέζικη διαδικασία εστιατορίων) περιλαμβάνουν την απαρίθμηση μέσω του αυξανόμενα εκθετικά στοιχεία k. Έτσι χρησιμοποιούνται κατά προσέγγιση υπολογιστικές μέθοδοι όπως η δειγματοληψία Gibbs. Τέλος, πρέπει να σημειώσουμε ότι παρόλο που οι συστάδες k είναι άπειρες, ο αριθμός των ενεργών συστάδων είναι . Έτσι το θ_i θα επαναλάβει και θα εμφανίσει ένα αποτέλεσμα συμπλέγματος.

2. Χρήση της διαδικασίας κινέζικου εστιατορίου για τον καθορισμό ενός μοντέλου άπειρου μείγματος

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

Μια εναλλακτική προσέγγιση είναι να χρησιμοποιήσετε τη διαδικασία κινέζικου εστιατορίου για να μοντελοποιήσετε τις λανθάνουσες μεταβλητές z_i των αντιστοιχίσεων συμπλέγματος. Με αυτόν τον τρόπο αντί να χρησιμοποιείτε θ_i για να δηλώσουμε τόσο τις παραμέτρους συμπλέγματος όσο και τις αντιστοιχίσεις συμπλέγματος, χρησιμοποιούμε τη λανθάνουσα μεταβλητή z_i για να υποδείξετε το αναγνωριστικό συμπλέγματος και, στη συνέχεια, χρησιμοποιήστε αυτήν την τιμή για να αντιστοιχίσετε τις παραμέτρους συμπλέγματος. Ως αποτέλεσμα, δεν χρειάζεται πλέον να κάνουμε δειγματοληψία θ κάθε φορά που λαμβάνουμε μια νέα παρατήρηση, αλλά αντ 'αυτού λαμβάνουμε την ανάθεση συμπλέγματος με δειγματοληψία z_i από CRP. Με αυτό το σχήμα γίνεται δειγματοληψία ενός νέου θ μόνο όταν πρέπει να δημιουργήσουμε ένα νέο σύμπλεγμα. Παρακάτω παρουσιάζουμε το μοντέλο αυτής της προσέγγισης:

Εξίσωση 2: Μοντέλο μείγματος με CRP

Τα παραπάνω είναι ένα γενετικό μοντέλο που περιγράφει τον τρόπο με τον οποίο τα δεδομένα x_i και οι συστάδες δημιουργούνται. Για να πραγματοποιήσουμε την ανάλυση συμπλέγματος πρέπει να χρησιμοποιήσουμε τις παρατηρήσεις x_i και εκτιμήστε τις αναθέσεις συμπλέγματος z_i.

3. Συμπεράσματα μοντέλου μίγματος και δειγματοληψία Gibbs

Δυστυχώς, δεδομένου ότι οι διεργασίες Dirichlet δεν είναι παραμετρικές, εμείς δεν μπορώ να χρησιμοποιήσω τον αλγόριθμο EM για να εκτιμήσετε τις λανθάνουσες μεταβλητές που αποθηκεύουν τις αναθέσεις συμπλέγματος. Για να εκτιμήσουμε τις εργασίες θα χρησιμοποιήσουμε το Σύμπτυξη δειγματοληψίας Gibbs.

Το Collapsed Gibbs Sampling είναι ένας απλός αλγόριθμος Markov Chain Monte Carlo (MCMC). Είναι γρήγορο και μας επιτρέπει να ενσωματώσουμε κάποιες μεταβλητές κατά τη δειγματοληψία μιας άλλης μεταβλητής. Ωστόσο, αυτοί οι αλγόριθμοι απαιτούν να επιλέξουμε ένα G₀ που είναι ένα συζυγές πριν από την κατανομή γενεαλογικών F, ώστε να είναι σε θέση να επιλύει αναλυτικά τις εξισώσεις και να μπορεί να δειγματοληψεί απευθείας από .

Τα βήματα της δειγματοληψίας Collapsed Gibbs που θα χρησιμοποιήσουμε για την εκτίμηση των αντιστοιχίσεων συμπλέγματος είναι τα εξής:

• Αρχικοποιήστε το z_i αναθέσεις συστάδων τυχαία
• Επαναλάβετε μέχρι τη σύγκλιση
• Επιλέξτε τυχαία τσεκούρι_i
  
• Κρατήστε το άλλο z_j καθορίζεται για κάθε j ≠ i:
• Εκχωρήστε μια νέα τιμή στο z_i υπολογίζοντας την "πιθανότητα CRP" που εξαρτάται από το z_j και x_j όλων των j ≠ i:

Στο επόμενο άρθρο θα επικεντρωθούμε στον τρόπο εκτέλεσης ανάλυσης συμπλέγματος χρησιμοποιώντας μοντέλα Dirichlet Process Mixture. Θα ορίσουμε δύο διαφορετικά μοντέλα μείγματος διεργασίας Dirichlet που χρησιμοποιούν τη διαδικασία κινέζικου εστιατορίου και τη δειγματοληψία Collapsed Gibbs προκειμένου να πραγματοποιήσουν ομαδοποίηση σε συνεχή σύνολα δεδομένων και έγγραφα.