search

ruteee / K2-Algorithm

Python implementation of the K2 algorithm for structural learning of Bayesian Networks.
5 stars 1 forks source link

Weird K2 implementation #1

Open ThomasHoppe opened 2 years ago

ThomasHoppe commented 2 years ago

Hmmh, actually the implementation of the K2 function is a bit weird. Besides the data it takes a dictionary as input. In the supplied example the dictionary already contains the tree ! Thus, if in the for-loop of the K2 function for each node only the supplied parents of the node (tree_xi) are taken as input for the further computation, only the supplied tree can be reproduced.

The original paper of Cooper & Herskovitz says: "Input: A set of n nodes, an ordering on the nodes, an upper bound u on the number of parents a node may have, and a database D containing m cases."

Thus, instead of a dictionary containing the ordering, an ordered set resp. a list needs to be used in order to avoid to inform the algorithm about the structure of the tree. Of course, then the upper bound on the number of parents needs to be supplied to.

ruteee commented 2 years ago

As you quoted we must provide an ordering of the nodes. The dictionary is, exactly, this ordering. Passing this ordering as a dictionary or a list does not have an influence on the result of the algorithm. It is just a swap of data structure.

If you pass the actual ordering of the nodes it is obvious the algorithm will understand that this is the true tree. However, you can pass any ordering on the nodes and the algorithm will function as well. This was just an example.

ThomasHoppe commented 2 years ago

Hmmh, shall the fake_tree dictionary just represent a list? Or shall it represent a real tree?

Unfortunately, if you use for each node as option for the parents xi just ances from the tree_xi, the algorithm has no chance to determine whether a different - previously processed - node would give a better f_ch.

Another point is that: alpha and get_N are just limited to binary attributes ! This is hard coded as [0,1] in these functions. The computation of math.factorial( alfa[ 2*j + i]) seems to depend on this binary assumption, too.

It would be much helpful if you make these assumptions in the description of the repo more clear.

By the way, I am currently trying to get rid of the implicite assumption of binar attributes. But couldn't figure out yet, what the correct base instead of 2 needs to be in math.factorial( alfa[ 2*j + i])

alpha returns an index, right? How ist it computed?