Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI: | http://purl.tuc.gr/dl/dias/55476F57-08D3-4A61-BDA0-DC0CCAC78CCB | ||
| Year | 2001 | ||
| Type of Item | Conference Publication | ||
| License |
|
||
| Bibliographic Citation | A. Deshpande, M. Garofalakis and M. Jordan, "Efficient stepwise selection in decomposable models", in Seventeenth Conference on Uncertainty in Artificial Intelligence, August 2001. | ||
| Appears in Collections |
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
