Efficient Stepwise Selection in Decomposable Models

2013/01/10 by Amol Deshpande, Deshpande, Amol, Minos Garofalakis +3 · 1 citation
Computer Science · Engineering · Mathematics · #Artificial Intelligence (cs.AI) #Bayesian Modeling and Causal Inference #Control Systems and Identification #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Statistical Methods and Inference

paper · pdf · doi:10.48550/arxiv.1301.2267

openalex publication_date 2013/01/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper, we present an efficient way of performing stepwise selection in the class of decomposable models. The main contribution of the paper is a simple characterization of the edges that canbe added to a decomposable model while keeping the resulting model decomposable and an efficient algorithm for enumerating all such edges for a given model in essentially O(1) time per edge. We also discuss how backward selection can be performed efficiently using our data structures.We also analyze the complexity of the complete stepwise selection procedure, including the complexity of choosing which of the eligible dges to add to (or delete from) the current model, with the aim ofminimizing the Kullback-Leibler distance of the resulting model from the saturated model for the data.

Cited by

• Structure Learning Using Forced Pruning
• Convex Relaxations for Learning Bounded Treewidth Decomposable Graphs

Related

• Shrinkage Strategies for Structure Selection and Identification of\n Piecewise Affine Models
• Efficient Neighborhood Selection for Gaussian Graphical Models
• Towards Fundamentally Scalable Model Selection: Asymptotically Fast Update and Selection
• The Lazy Flipper: MAP Inference in Higher-Order Graphical Models by Depth-limited Exhaustive Search
• Faster feature selection with a Dropping Forward-Backward algorithm