Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
EN  |  EL

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

Efficient stepwise selection in decomposable models

Deshpande Amol, Garofalakis Minos, Jordan Michael I.

Πλήρης Εγγραφή


URI: http://purl.tuc.gr/dl/dias/55476F57-08D3-4A61-BDA0-DC0CCAC78CCB
Έτος 2001
Τύπος Δημοσίευση σε Συνέδριο
Άδεια Χρήσης
Λεπτομέρειες
Βιβλιογραφική Αναφορά A. Deshpande, M. Garofalakis and M. Jordan, "Efficient stepwise selection in decomposable models", in Seventeenth Conference on Uncertainty in Artificial Intelligence, August 2001.
Εμφανίζεται στις Συλλογές

Περίληψη

In this paper, we present an efficient algorithmfor performing stepwise selection inthe class of decomposable models. We focuson the forward selection procedure, butwe also discuss how backward selection andthe combination of the two can be performedefficiently. The main contributions of thispaper are (1) a simple characterization forthe edges that can be added to a decomposablemodel while retaining its decomposabilityand (2) an efficient algorithm for enumeratingall such edges for a given decomposablemodel in O(n2) time, where n is the numberof variables in the model.We also analyze the complexity of the overallstepwise selection procedure (which includesthe complexity of enumerating eligible edgesas well as the complexity of deciding how to“progress”). We use the KL divergence ofthe model from the saturated model as ourmetric, but the results we present here extendto many other metrics as well.

Υπηρεσίες

Στατιστικά