"Efficient Stepwise Selection in Decomposable Models"
by
Amol Deshpande,
Minos Garofalakis, and
Michael I. Jordan.
Proceedings of UAI'2001,
Seattle, Washington, August 2001.
Abstract
In this paper, we present an efficient algorithm for performing stepwise selection
in the class of decomposable models. We focus on the forward selection
procedure, but we also discuss how backward selection and the combination
of the two can be performed efficiently. The main contributions of this paper
are (1) a simple characterization for the edges that can be added to a
decomposable model while retaining its decomposability and (2) an efficient
algorithm for enumerating all such edges for a given decomposable model in
O(n^2) time, where n is the number of variables in the model.
We also analyze the complexity of the overall stepwise selection procedure
(which includes the complexity of enumerating eligible edges as well as
the complexity of deciding how to "progress").
We use the KL divergence of the model from the saturated model as our
metric, but the results we present here extend to many other
metrics as well.
Copyright © 2001, Morgan-Kaufmann Publishers, San Francisco, CA.