Greedy Learning of Graphical Models with Small Girth.

摘要

This paper presents three new greedy algorithms for learning discrete graphical models. The original greedy algorithm constructed the neighborhood of each node by sequentially adding nodes (or variable) in each step which currently produced the maximum decrease in its conditional entropy. Though simple, this did not always yield the correct graph when there are short cycles, since a non-neighbor may produce most decrease in the conditional entropy in a step and it gets added to its neighborhood. The new algorithms can overcome this problem in three different ways. The recursive greedy algorithm iteratively runs the greedy algorithm in an inner loop, but each time only includes the last added node in the neighborhood set. On other hand the forward- backward greedy algorithm includes a node deletion step in each iteration, which prunes the incorrect nodes from the neighborhood set that may have been added earlier. Finally the greedy algorithm with pruning runs the greedy algorithm until completion and then removes all the incorrect neighbors. We give both analytical guarantees and empirical results for our algorithms. Running the algorithms with a candidate set of nodes instead of all the nodes and their greedy approach enables them to efficiently learn graphs even with small girth, which the previous greedy and convex optimization based algorithms cannot learn.