Μοντέλο πεπερασμένων μιγμάτων βασισμένο στο Dirichlet Distribution

• 12 Μαΐου 2014
• Βασίλης Βρυνιώτης
• . 4 Σχόλια

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

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

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

Συνεπώς, σε αυτό το άρθρο θα παρουσιάσω εν συντομία μερικές σημαντικές κατανομές που θα χρειαστούμε, θα τις χρησιμοποιήσουμε για να κατασκευάσουμε το μοντέλο Dirichlet Prior με Πολυωνυμική Πιθανότητα και μετά θα περάσουμε στο Μοντέλο Πεπερασμένου Μείγματος που βασίζεται στην Κατανομή Dirichlet.

1. Διανομή Beta

Η Διανομή beta είναι μια οικογένεια συνεχών κατανομών που ορίζεται στο διάστημα [0,1]. Παραμετροποιείται από δύο θετικές παραμέτρους a και b και η μορφή του εξαρτάται σε μεγάλο βαθμό από την επιλογή αυτών των δύο παραμέτρων.

Εικόνα 1: Κατανομή Beta για διαφορετικές παραμέτρους a, b

Η κατανομή Beta χρησιμοποιείται συνήθως για τη μοντελοποίηση μιας κατανομής σε πιθανότητες και έχει την ακόλουθη πυκνότητα πιθανότητας:

Εξίσωση 1: Beta PDF

Όπου Γ(x) είναι η συνάρτηση γάμμα και a, b οι παράμετροι της κατανομής. Το βήτα χρησιμοποιείται συνήθως ως κατανομή τιμών πιθανότητας και μας δίνει την πιθανότητα η μοντελοποιημένη πιθανότητα να ισούται με μια συγκεκριμένη τιμή P = p0. Σύμφωνα με τον ορισμό της, η διανομή βήτα είναι σε θέση να μοντελοποιήσει την πιθανότητα δυαδικών αποτελεσμάτων που λαμβάνουν τιμές true ή false. Οι παράμετροι a και b μπορούν να θεωρηθούν ως ψευδομετρήσεις επιτυχίας και αποτυχίας αντίστοιχα. Έτσι, η Διανομή Βήτα μοντελοποιεί την πιθανότητα επιτυχίας με δεδομένες τις επιτυχίες και τις β αποτυχίες.

2. Διανομή Dirichlet

Η Διανομή Dirichlet είναι η γενίκευση της Κατανομής Βήτα για πολλαπλά αποτελέσματα (ή με άλλα λόγια χρησιμοποιείται για γεγονότα με πολλαπλά αποτελέσματα). Παραμετροποιείται με k παραμέτρους α_i που πρέπει να είναι θετικό. Η Κατανομή Dirichlet ισούται με την Κατανομή Βήτα όταν ο αριθμός των μεταβλητών k = 2.

Εικόνα 2: Κατανομή Dirichlet για διάφορα α_i παράμετροι

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

Εξίσωση 2: Dirichlet PDF

Όπου Γ(x) είναι η συνάρτηση γάμμα, το p_i πάρτε τιμές σε [0,1] και Σp_i=1. Η κατανομή Dirichlet μοντελοποιεί την κοινή κατανομή του p_i και δίνει την πιθανότητα του Π₁=p₁,P₂=p₂,….,Π_k-1=p_k-1 με P_k=1 – ΣP_i. Όπως και στην περίπτωση του Beta, το α_i Οι παράμετροι μπορούν να θεωρηθούν ως ψευδομετρήσεις των εμφανίσεων κάθε i συμβάντος. Η κατανομή Dirichlet χρησιμοποιείται για να μοντελοποιήσει την πιθανότητα να συμβούν k ανταγωνιστικά γεγονότα και συχνά συμβολίζεται ως Dirichlet(a).

3. Dirichlet Prior με πολυωνυμική πιθανότητα

Όπως αναφέρθηκε προηγουμένως, η κατανομή Dirichlet μπορεί να θεωρηθεί ως κατανομή επί των κατανομών πιθανοτήτων. Σε περιπτώσεις όπου θέλουμε να μοντελοποιήσουμε την πιθανότητα εμφάνισης k γεγονότων, θα χρησιμοποιούσαμε μια Μπεϋζιανή προσέγγιση Multinomial Likelihood και Dirichlet Priors .

Παρακάτω μπορούμε να δούμε το γραφικό μοντέλο ενός τέτοιου μοντέλου.

Εικόνα 3: Γραφικό μοντέλο Dirichlet Priors με πολυωνυμική πιθανότητα

Στο παραπάνω γραφικό μοντέλο, το α είναι διάνυσμα διαστάσεων ak με τις υπερπαραμέτρους του Dirichlet priors, το p είναι ak διάνυσμα διαστάσεων με τις τιμές πιθανότητας και x_i είναι μια κλιμακωτή τιμή από το 1 έως το k που μας λέει ποιο συμβάν έχει συμβεί. Τέλος να σημειώσουμε ότι το P ακολουθεί την κατανομή Dirichlet παραμετροποιημένη με διάνυσμα α και έτσι P ~ Dirichlet(α), ενώ το x_i Οι μεταβλητές ακολουθούν τη Διακριτή κατανομή (Πολυωνυμική) παραμετροποιημένη με το p διάνυσμα των πιθανοτήτων. Παρόμοια ιεραρχικά μοντέλα μπορούν να χρησιμοποιηθούν στην ταξινόμηση εγγράφων για να αναπαραστήσουν τις κατανομές των συχνοτήτων των λέξεων-κλειδιών για διαφορετικά θέματα.

4. Μοντέλο πεπερασμένου μίγματος με κατανομή Dirichlet

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

Εξίσωση 3: Μοντέλο πεπερασμένου μίγματος με κατανομή Dirichlet

Το παραπάνω μοντέλο προϋποθέτει τα εξής: Έχουμε ένα σύνολο δεδομένων X με n παρατηρήσεις και θέλουμε να κάνουμε ανάλυση συμπλέγματος σε αυτό. Το k είναι ένας σταθερός πεπερασμένος αριθμός που δείχνει τον αριθμό των συστάδων/συστατικών που θα χρησιμοποιήσουμε. Το γ_i Οι μεταβλητές αποθηκεύουν την ανάθεση συμπλέγματος της παρατήρησης Χ_i, παίρνουν τιμές από 1 έως k και ακολουθούν τη Διακριτή Κατανομή με την παράμετρο p που είναι οι πιθανότητες ανάμειξης των συστατικών. Το F είναι η γενετική κατανομή του Χ μας και παραμετροποιείται με μια παράμετρο που εξαρτάται από την ανάθεση συστάδας κάθε παρατήρησης. Συνολικά έχουμε κ μοναδικά παραμέτρους ίσες με τον αριθμό των συστάδων μας. ο Η μεταβλητή αποθηκεύει τις παραμέτρους που παραμετροποιούν την παραγωγική Κατανομή F και υποθέτουμε ότι ακολουθεί μια βάση G₀ διανομή. Η μεταβλητή p αποθηκεύει τα ποσοστά του μείγματος για κάθε ένα από τα k συμπλέγματα και ακολουθεί το Dirichlet με τις παραμέτρους α/k. Τέλος το α είναι διάνυσμα διαστάσεων ak με τις υπερπαραμέτρους (ψευδομετρήσεις) της κατανομής Dirichlet [2].

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

Ένας απλούστερος και λιγότερο μαθηματικός τρόπος για να εξηγήσετε το μοντέλο είναι ο ακόλουθος. Υποθέτουμε ότι τα δεδομένα μας μπορούν να ομαδοποιηθούν σε k clusters. Κάθε σύμπλεγμα έχει τις δικές του παραμέτρους και αυτές οι παράμετροι χρησιμοποιούνται για τη δημιουργία των δεδομένων μας. Οι παράμετροι υποτίθεται ότι ακολουθούν κάποια κατανομή G₀. Κάθε παρατήρηση αναπαρίσταται με ένα διάνυσμα x_i και ακ_i τιμή που υποδεικνύει το σύμπλεγμα στο οποίο ανήκει. Κατά συνέπεια το γ_i μπορεί να θεωρηθεί ως μια μεταβλητή που ακολουθεί τη Διακριτή Κατανομή με μια παράμετρο p που δεν είναι παρά οι πιθανότητες του μείγματος, δηλαδή η πιθανότητα εμφάνισης κάθε συστάδας. Δεδομένου ότι χειριζόμαστε το πρόβλημά μας με τρόπο Bayes, δεν αντιμετωπίζουμε την παράμετρο p ως ένα σταθερό άγνωστο διάνυσμα. Αντίθετα, υποθέτουμε ότι το P ακολουθεί το Dirichlet το οποίο παραμετροποιείται από τις υπερπαραμέτρους α/k.

5. Εργασία με άπειρα k συμπλέγματα

Το προηγούμενο μοντέλο μίξης μας επιτρέπει να εκτελούμε μάθηση χωρίς επίβλεψη, ακολουθεί μια Μπεϋζιανή προσέγγιση και μπορεί να επεκταθεί ώστε να έχουμε μια ιεραρχική δομή. Ωστόσο, είναι ένα πεπερασμένο μοντέλο επειδή χρησιμοποιεί έναν σταθερό προκαθορισμένο k αριθμό συστάδων. Ως αποτέλεσμα, απαιτεί από εμάς να ορίσουμε τον αριθμό των στοιχείων πριν από την εκτέλεση της Ανάλυσης συμπλέγματος και, όπως συζητήσαμε νωρίτερα στις περισσότερες εφαρμογές, αυτό είναι άγνωστο και δεν μπορεί να εκτιμηθεί εύκολα.

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

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

Στο επόμενο άρθρο θα εστιάσουμε ακριβώς σε αυτές τις ερωτήσεις: θα ορίσουμε τη Διαδικασία Dirichlet, θα παρουσιάσουμε τις διάφορες αναπαραστάσεις της DP και τέλος θα επικεντρωθούμε στη Διαδικασία του Κινέζικου Εστιατορίου που είναι ένας διαισθητικός και αποτελεσματικός τρόπος κατασκευής μιας διαδικασίας Dirichlet.

Ελπίζω να σας φάνηκε χρήσιμη αυτή η ανάρτηση. Εάν το κάνατε, αφιερώστε λίγο χρόνο για να μοιραστείτε το άρθρο στο Facebook και στο Twitter. 🙂