Δέντρο Chow–Liu
Στη θεωρία πιθανοτήτων και τη στατιστική , το δέντρο Chow–Liu είναι μια αποτελεσματική μέθοδος για την κατασκευή μιας προσέγγισης γινομένων δεύτερης τάξης μιας κοινής κατανομής πιθανοτήτων, που περιγράφηκε για πρώτη φορά σε μια εργασία από τους Chow & Liu (1968) . Οι στόχοι μιας τέτοιας αποσύνθεσης, όπως με δίκτυα Bayes, μπορεί να αναπαριστά συμπίεση δεδομένων είτε συμπέρασμα (inference).
Η αναπαράσταση Chow–Liu
[Επεξεργασία | επεξεργασία κώδικα]Η μέθοδος Chow–Liu περιγράφει μια κοινή κατανομή πιθανοτήτων ως δεσμευμένο γινόμενο δεύτερης τάξης και οριακές κατανομές. Για παράδειγμα, η εξαδιάστατη κατανομή μπορεί να προσεγγιστεί ως
όπου κάθε νέος όρος στο γινόμενο εισάγει μόνο μία νέα μεταβλητή και το γινόμενο μπορεί να αναπαρασταθεί ως δέντρο εξαρτήσεων πρώτης τάξης, όπως φαίνεται στο σχήμα. Ο αλγόριθμος Chow–Liu (παρακάτω) καθορίζει ποιες δεσμευμένες πιθανότητες θα χρησιμοποιηθούν στην προσέγγιση του προϊόντος. [1] Γενικά, εκτός και αν δεν υπάρχουν αλληλεπιδράσεις τρίτης τάξης ή ανώτερης τάξης, η προσέγγιση Chow–Liu είναι πράγματι μια προσέγγιση και δεν μπορεί να συλλάβει την πλήρη δομή της αρχικής κατανομής. Ο Pearl (1988) παρέχει μια σύγχρονη ανάλυση του δέντρου Chow–Liu ως Bayesian δίκτυο .
Ο αλγόριθμος Chow–Liu
[Επεξεργασία | επεξεργασία κώδικα]Οι Chow και Liu δείχνουν πώς να επιλέγετε όρους δεύτερης τάξης για την προσέγγιση του γινομένου, έτσι ώστε, μεταξύ όλων αυτών των προσεγγίσεων δεύτερης τάξης (δέντρα εξάρτησης πρώτης τάξης), η κατασκευασμένη προσέγγιση έχει την ελάχιστη απόκλιση Kullback–Leibler στην πραγματική κατανομή , και είναι έτσι η πλησιέστερη προσέγγιση με την κλασική έννοια της θεωρίας της πληροφορίας . Η απόκλιση Kullback–Leibler μεταξύ μιας προσέγγισης γινομένου δεύτερης τάξης και της πραγματικής κατανομής φαίνεται να είναι
Δείτε επίσης
[Επεξεργασία | επεξεργασία κώδικα]Παραπομπές
[Επεξεργασία | επεξεργασία κώδικα]- ↑ Permuter, Haim. «Lecture on Tree distribution» (PDF). Αρχειοθετήθηκε από το πρωτότυπο (PDF) στις 27 Αυγούστου 2021. Ανακτήθηκε στις 7 Νοεμβρίου 2022.