Δέντρο Chow–Liu

Στη θεωρία πιθανοτήτων και τη στατιστική , το δέντρο Chow–Liu είναι μια αποτελεσματική μέθοδος για την κατασκευή μιας προσέγγισης γινομένων δεύτερης τάξης μιας κοινής κατανομής πιθανοτήτων, που περιγράφηκε για πρώτη φορά σε μια εργασία από τους  . Οι στόχοι μιας τέτοιας αποσύνθεσης, όπως με δίκτυα Bayes, μπορεί να αναπαριστά συμπίεση δεδομένων είτε συμπέρασμα (inference).

Η αναπαράσταση Chow–Liu 
Η μέθοδος Chow–Liu περιγράφει μια κοινή κατανομή πιθανοτήτων  ως δεσμευμένο γινόμενο δεύτερης τάξης και οριακές κατανομές. Για παράδειγμα, η εξαδιάστατη κατανομή  μπορεί να προσεγγιστεί ως

 

όπου κάθε νέος όρος στο γινόμενο εισάγει μόνο μία νέα μεταβλητή και το γινόμενο μπορεί να αναπαρασταθεί ως δέντρο εξαρτήσεων πρώτης τάξης, όπως φαίνεται στο σχήμα. Ο αλγόριθμος Chow–Liu (παρακάτω) καθορίζει ποιες δεσμευμένες πιθανότητες θα χρησιμοποιηθούν στην προσέγγιση του προϊόντος.  Γενικά, εκτός και αν δεν υπάρχουν αλληλεπιδράσεις τρίτης τάξης ή ανώτερης τάξης, η προσέγγιση Chow–Liu είναι πράγματι μια προσέγγιση και δεν μπορεί να συλλάβει την πλήρη δομή της αρχικής κατανομής. Ο  παρέχει μια σύγχρονη ανάλυση του δέντρου Chow–Liu ως Bayesian δίκτυο .

Ο αλγόριθμος Chow–Liu 
Οι Chow και Liu δείχνουν πώς να επιλέγετε όρους δεύτερης τάξης για την προσέγγιση του γινομένου, έτσι ώστε, μεταξύ όλων αυτών των προσεγγίσεων δεύτερης τάξης (δέντρα εξάρτησης πρώτης τάξης), η κατασκευασμένη προσέγγιση  έχει την ελάχιστη απόκλιση Kullback–Leibler στην πραγματική κατανομή , και είναι έτσι η πλησιέστερη προσέγγιση με την κλασική έννοια της θεωρίας της πληροφορίας . Η απόκλιση Kullback–Leibler μεταξύ μιας προσέγγισης γινομένου δεύτερης τάξης και της πραγματικής κατανομής φαίνεται να είναι

Δείτε επίσης 
 Μπεϋζιανό δίκτυο

Παραπομπές

Αναπαράσταση γνώσης