Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
Πολυτεχνείο Κρήτης
EN
|
EL
| 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.
Copyright © DIAS 2013
