Re: LS Algorithm - which Lambda message to use?

Subject:

Comments:
: Yes, I think this is the case. Also please notice that the a child's S may be found in more than one previous cliques, you can just select any one of them as its parent. : -hpguo : : Okay - so once S & R are computed based on the initial clique ordering, we then say that a node is a child iff all nodes in the child's S are found in the parent, right? : : If that's the case, then I'll have to modify Laura's code slightly so it will do this. : : : My understanding is that first we get S , then we use S to decide who is its parent. S is defined as the intersection of itself with all previous nodes. your understanding looks like you first get the child-parent relitionship for all nodes, then compute S for each node. I think it's not correct. : : : -hpguo : : : : Take a look at definition 7.2, page 253 in the neopolitan book - it defines S as the intersection of itself with all of its parents / grandparents. Either I'm interpreting that wrong, or else child nodes can have nodes in S that are not in its direct parent as long as the nodes are somewhere upstream. : : : : -Ben : : : : : : : : : I think your assumption is not correct. A child node CANNOT have nodes in S that are NOT in its direct parents' clique. : : : : : I'm not sure how the child-parent relationships are computed in your program after the order of these cliques are determined, but I guess there may be something wrong with that parents-finding process. Please take a look at Definition 3.22 at page 102 in Neapolitan's book and the following example. : : : : : Also please look at Step D and E on page 280. : : : : : In your example problem, S5 is {e, l} so its parent should be C3 instead of C4. Because S5 is a subset of C3 instead of C4. According to the difinition, C3 should be its parent. : : : : : -hpguo : : : : : : Assuming that it is okay to have child cliques have nodes in the S group that do not belong to the immediate parent, then how should ambiguous lambda messages be treated? : : : : : : For example, clique 5 in the previous thread has nodes 'C' and 'E' in the S group. The lambda messages are L(c1, e1), L(c1, e2), L(c2, e1), and L(c2, e2). When it sends the messages back up to the parent (clique 4), the parent goes through all of its phi values and multiplies them by the corresponding lambda messages. It does this by seeing which node in the current cliqueset matches one of the lambda messages. (the key word being "one"). However, because clique 4 doesn't contain node 'E', the lambda messages are no longer on a one-to-one correspondence and thus can have two possible lambda messages (ex: c1, e1 and c1, e2 both correspond to c1). Which one (or do we sum all possible values) should we use? : : : : : : Again, this is assuming that it is okay for children to have nodes in S that are NOT in its direct parent's clique.

Optional Link URL:
Link Title:
Optional Image URL: