An Algorithm for Learning the Essential Graph

Details An Algorithm for Learning the Essential Graph An Algorithm for Learning the Essential Graph

2010-07-14

arxiv.org/abs/1007.2656v1

Statistics

Computation

55 pages

Scientific paper

This article presents an algorithm for learning the essential graph of a Bayesian network. The basis of the algorithm is the Maximum Minimum Parents and Children algorithm developed by previous authors, with three substantial modifications. The MMPC algorithm is the first stage of the Maximum Minimum Hill Climbing algorithm for learning the directed acyclic graph of a Bayesian network, introduced by previous authors. The MMHC algorithm runs in two phases; firstly, the MMPC algorithm to locate the skeleton and secondly an edge orientation phase. The computationally expensive part is the edge orientation phase. The first modification introduced to the MMPC algorithm, which requires little additional computational cost, is to obtain the immoralities and hence the essential graph. This renders the edge orientation phase, the computationally expensive part, unnecessary, since the entire Markov structure that can be derived from data is present in the essential graph. Secondly, the MMPC algorithm can accept independence statements that are logically inconsistent with those rejected, since with tests for independence, a `do not reject' conclusion for a particular independence statement is taken as `accept' independence. An example is given to illustrate this and a modification is suggested to ensure that the conditional independence statements are logically consistent. Thirdly, the MMHC algorithm makes an assumption of faithfulness. An example of a data set is given that does not satisfy this assumption and a modification is suggested to deal with some situations where the assumption is not satisfied. The example in question also illustrates problems with the `faithfulness' assumption that cannot be tackled by this modification.

Affiliated with

Also associated with

No associations

Rating

An Algorithm for Learning the Essential Graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An Algorithm for Learning the Essential Graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Algorithm for Learning the Essential Graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-121370