The Exploration of Greedy Hill-climbing Search in Markov Equivalence Class Space

摘要

The greedy Hill-climbing search in the Markov Equivalence Class space (E-space) can overcome the drawback of falling into local maximum in Directed Acyclic Graph space (DAG space) caused by the score equivalent property of Bayesian scoring junction, and one representative algorithm is Greedy Equivalence Search algorithm (GES algorithm) which is inclusion optimal in the large sample size, but not parameter optimal. In fact GES algorithm does not comply with the inclusion boundary condition which is a guarantee of gaining the highest score, but the unrestricted form of GES algorithm (UGES algorithm) complies with the inclusion boundary condition approximately. However, the greedy Hill-climbing search both in the DAG space and in the E-space has the drawback of time-consuming. The idea of confining the search using the constraint-based method is a good solution for the time-consuming drawback. This paper conducts experiments to compare the effects of greedy Hill-climbing search algorithm in DAG space (GS algorithm), GES algorithm and UGES algorithm both without the restriction of the parents and children sets and with the restriction of parents and children sets, and finds that GS/GES/UGES with the restriction have achieved improvement in time-efficiency and structure difference, with a little reduction in Bayesian scoring function.