Questions about subsumption/refinement operators

YPares commented 8 years ago

Hi! I have a question related to graph vs. tree version of refinement operators and subsumption when using a PartialOrder to anti-unify (for instance POTransSubsumption vs. TreePOTransSubsumption and POTransRefinement vs. TreePOTransRefinement)

Should I use the Tree version :

when the PartialOrder is a actually defined as a tree
when DLGs to anti-unify are TreeDLGs
when all of the above are trees?

santiontanon commented 8 years ago

Hi YPares!

When DLGs to anti-unify are TreeDLGs.

I should probably create some documentation for the library, shouldn't I? :)

YPares commented 8 years ago

@santiontanon Thanks! Indeed, I wouldn't say no to some doc ^^ In the meatime, I'm reading the papers you published, notably the companion paper http://arxiv.org/pdf/1604.06954.pdf

YPares commented 8 years ago

Small question while I'm at it, when anti-unfifying two DAGs (basically trees but with some transversal links to order some set-valued features) which are structurally identical (but one vertex has a different sort), I notice that in the output of singleAntiunification, the corresponding vertices are labeled differently (V2 instead of V0 for instance). Given DAGs aren't rooted, do I have a way to figure out the correspondences between anti-unification and original DAGs?

santiontanon commented 8 years ago

Good question! the easiest way would be to exploit the fact that subsumption calculates the mapping between the vertices of the two graphs being tested. So: 1) Given the two DAGs: d1, d2 2) Call anti-unification to obtain au1 3) Call subsumption between au1 and d1 (this will give you the mapping from vertices of au1 to vertices of d1). This mapping is returned in the form of an array, that has one position per vertex in au1, and each position contains the index of the corresponding vertex in d1. 4) Call subsumption between au1 and d2 (this will give you the mapping from vertices of au1 to vertices of d2)

It wouldn't be hard to modify anti-unification to cache these mappings and return them though. So, if it would be of help, I don't mind implementing this functionality and adding it to the library :)

YPares commented 8 years ago

@santiontanon Well, if you don't mind then, I think it'd be a great addition, yes! Thank you!

YPares commented 8 years ago

(Continuing with the questions) What's the effect of the objectIdentity param in POSubsumption? Does it mean with true that it compares e.g labels not by value but by reference? (In the unit tests it doesn't seem to be so)

santiontanon commented 8 years ago

Hi YPares,

I have already added the functionality in AntiUnification to return the mapping through which the anti-unifier subsumes the original terms (see the function singleAntiunificationWithMappings of the AntiUnification class).
About the "object identity" parameter. It is not about value versus reference. What it does is the following. When checking if a graph G1 subsumes another graph G2, if objectIdentity = true, mappings where different vertexes from G1 are mapped to the same vertex in G2 are not allowed. (see Section 1.3.1 of https://arxiv.org/pdf/1604.06954v1.pdf ).

Does that make sense? I could add a couple more examples to the PDF file to clarify.

YPares commented 8 years ago

When checking if a graph G1 subsumes another graph G2, if objectIdentity = true, mappings where different vertexes from G1 are mapped to the same vertex in G2 are not allowed

Ah, I get it. I think that it's very interesting for me. Indeed, I might need to be able to consider several vertices as "subclassing" (sorry, OWL/DL parlance) one vertex (as part of a subsumption link). But from what I noticed, deactivating OI seems to make AU much slower. I'll keep experimenting, thanks!

2016-09-01 21:50 GMT+02:00 santiontanon notifications@github.com:

When checking if a graph G1 subsumes another graph G2, if objectIdentity = true, mappings where different vertexes from G1 are mapped to the same vertex in G2 are not allowed

santiontanon commented 8 years ago

Yes, without object identity (OI), things are slower because OI basically imposes an additional restriction over the set of mappings subsumption has to search over, and thus reduces the search space.

YPares commented 8 years ago

@santiontanon I'm having a look at what singleAntiunificationWithMappings is producing. I'm a bit at a loss regarding how to interpret the result. In the case of the graphs I exposed in https://github.com/santiontanon/RHOG/issues/4 it produces the following list of two arrays: ([0, 1, 3, 2], [0, 2, 1, 3])

Does it mean vertices 1, 3 & 2 in original DLGs are mapped respectively to vertices 2, 1 & 3 in resulting antiunification DLG?

YPares commented 8 years ago

Ok, I understood it, arrays should actually be read position-wise. If my two DLGs to unify are D1 and D2, then if I get ([0, 1, 3, 2], [0, 2, 1, 3]):

First array [0,1,3,2] is for D1. It means that V0 in AU is V0 in D1, V1 in AU is V1 in D1, V2 in AU is V3 in D1, and V3 in AU is V2 in D1
And second array [0, 2, 1, 3] is the same for D2.

Okay, interpreted like that, it makes sense :) And having the mappings makes it easier to find out how to structure my feature terms. Thanks!

santiontanon commented 8 years ago

Exactly! that's correct :)

santiontanon / RHOG

Questions about subsumption/refinement operators #3