Menu
▾
▴
[DL-Learner SVN] SF.net SVN: dl-learner:[1558] trunk/src/dl-learner/org/dllearner
|
From: <jen...@us...> - 2008-12-17 15:20:34
|
Revision: 1558
http://dl-learner.svn.sourceforge.net/dl-learner/?rev=1558&view=rev
Author: jenslehmann
Date: 2008-12-17 15:20:27 +0000 (Wed, 17 Dec 2008)
Log Message:
-----------
fixed some EL refinement operator bugs
Modified Paths:
--------------
trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionNode.java
trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionTree.java
trunk/src/dl-learner/org/dllearner/algorithms/el/ELLearningAlgorithm.java
trunk/src/dl-learner/org/dllearner/learningproblems/PosNegInclusionLP.java
trunk/src/dl-learner/org/dllearner/refinementoperators/ELDown2.java
trunk/src/dl-learner/org/dllearner/refinementoperators/Utility.java
trunk/src/dl-learner/org/dllearner/test/junit/ELDescriptionTreeTests.java
trunk/src/dl-learner/org/dllearner/test/junit/ELDownTests.java
trunk/src/dl-learner/org/dllearner/test/junit/SimulationTests.java
Modified: trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionNode.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionNode.java 2008-12-17 15:05:28 UTC (rev 1557)
+++ trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionNode.java 2008-12-17 15:20:27 UTC (rev 1558)
@@ -91,6 +91,11 @@
this(tree, new TreeSet<NamedClass>());
}
+ // convenience constructor
+ public ELDescriptionNode(ELDescriptionTree tree, NamedClass... label) {
+ this(tree, new TreeSet<NamedClass>(Arrays.asList(label)));
+ }
+
/**
* Constructs an EL description tree given its root label.
* @param label Label of the root node.
Modified: trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionTree.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionTree.java 2008-12-17 15:05:28 UTC (rev 1557)
+++ trunk/src/dl-learner/org/dllearner/algorithms/el/ELDescriptionTree.java 2008-12-17 15:20:27 UTC (rev 1558)
@@ -161,7 +161,7 @@
ELDescriptionNode node1 = edges.get(j).getNode();
ELDescriptionNode node2 = edges.get(k).getNode();
// check simulation condition
- if(node1.in.contains(node2) || node2.in.contains(node1)) {
+ if(node1.in.contains(node2)) { // || node2.in.contains(node1)) {
// node1 is simulated by node2, i.e. we could remove one
// of them, so the tree is not minimal
return false;
@@ -433,6 +433,14 @@
node2.out.remove(node1);
}
+ public String toSimulationString() {
+ String str = "";
+ for(ELDescriptionNode node : nodes) {
+ str += node.toSimulationString() + "\n";
+ }
+ return str;
+ }
+
public String toSimulationString(Map<ELDescriptionNode,String> nodeNames) {
String str = "";
for(Entry<ELDescriptionNode,String> entry : nodeNames.entrySet()) {
@@ -514,7 +522,14 @@
// update global tree
treeClone.rootNode = newRoot;
treeClone.maxLevel = maxLevel;
- treeClone.nodes = new HashSet<ELDescriptionNode>(nodes);
+
+ // nodes
+ treeClone.nodes = new HashSet<ELDescriptionNode>();
+ for(ELDescriptionNode oldNode : nodes) {
+ treeClone.nodes.add(cloneMap.get(oldNode));
+ }
+
+ // level node mapping
for(int i=1; i<=maxLevel; i++) {
Set<ELDescriptionNode> oldNodes = levelNodeMapping.get(i);
Set<ELDescriptionNode> newNodes = new HashSet<ELDescriptionNode>();
Modified: trunk/src/dl-learner/org/dllearner/algorithms/el/ELLearningAlgorithm.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/algorithms/el/ELLearningAlgorithm.java 2008-12-17 15:05:28 UTC (rev 1557)
+++ trunk/src/dl-learner/org/dllearner/algorithms/el/ELLearningAlgorithm.java 2008-12-17 15:20:27 UTC (rev 1558)
@@ -38,7 +38,6 @@
import org.dllearner.core.owl.Description;
import org.dllearner.core.owl.Thing;
import org.dllearner.learningproblems.PosNegLP;
-import org.dllearner.refinementoperators.ELDown;
import org.dllearner.refinementoperators.ELDown2;
import org.dllearner.utilities.owl.EvaluatedDescriptionSet;
Modified: trunk/src/dl-learner/org/dllearner/learningproblems/PosNegInclusionLP.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/learningproblems/PosNegInclusionLP.java 2008-12-17 15:05:28 UTC (rev 1557)
+++ trunk/src/dl-learner/org/dllearner/learningproblems/PosNegInclusionLP.java 2008-12-17 15:20:27 UTC (rev 1558)
@@ -29,10 +29,8 @@
import org.dllearner.core.owl.Description;
import org.dllearner.core.owl.Individual;
import org.dllearner.core.owl.Negation;
-import org.dllearner.reasoning.FastInstanceChecker;
import org.dllearner.utilities.Helper;
import org.dllearner.utilities.datastructures.SetManipulation;
-import org.dllearner.utilities.owl.ConceptTransformation;
/**
* The aim of this learning problem is to find an appropriate inclusion axiom
Modified: trunk/src/dl-learner/org/dllearner/refinementoperators/ELDown2.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/refinementoperators/ELDown2.java 2008-12-17 15:05:28 UTC (rev 1557)
+++ trunk/src/dl-learner/org/dllearner/refinementoperators/ELDown2.java 2008-12-17 15:20:27 UTC (rev 1558)
@@ -107,6 +107,7 @@
*/
@Override
public Set<Description> refine(Description concept) {
+ System.out.println("refining " + concept);
ELDescriptionTree tree = new ELDescriptionTree(rs, concept);
Set<ELDescriptionTree> refinementTrees = refine(tree);
Set<Description> refinements = new HashSet<Description>();
@@ -125,20 +126,24 @@
* @return Set of refined EL description trees.
*/
public Set<ELDescriptionTree> refine(ELDescriptionTree tree) {
+ System.out.println("applying \\rho on " + tree.toDescriptionString());
+
Set<ELDescriptionTree> refinements = new HashSet<ELDescriptionTree>();
// loop over all nodes of the tree and perform one of the
// transformations on it (we make a copy of all nodes, because
// the transformations can, of course, add new nodes)
Set<ELDescriptionNode> nodes = new HashSet<ELDescriptionNode>(tree.getNodes());
for(ELDescriptionNode v : nodes) {
+ System.out.println("picked node v: " + v);
+
// the position of the node within the tree (needed for getting
// the corresponding node in a cloned tree)
int[] position = v.getCurrentPosition();
// perform operations
refinements.addAll(extendLabel(tree, v, position));
- refinements.addAll(refineLabel(tree, v, position));
- refinements.addAll(refineEdge(tree, v, position));
+// refinements.addAll(refineLabel(tree, v, position));
+// refinements.addAll(refineEdge(tree, v, position));
refinements.addAll(attachSubtree(tree, v, position));
}
@@ -160,8 +165,10 @@
// call ncc (see paper)
Set<NamedClass> candidates = utility.getClassCandidates(index, v.getLabel());
+// System.out.println("label: " + v.getLabel());
for(NamedClass nc : candidates) {
+// System.out.println("candidate: " + nc);
// clone operation
ELDescriptionTree clonedTree = tree.clone();
ELDescriptionNode clonedNode = clonedTree.getNode(position);
@@ -246,14 +253,11 @@
SortedSet<ObjectProperty> appOPs = utility.computeApplicableObjectProperties(index);
Set<ObjectProperty> mgr = utility.computeMgr(appOPs);
- // TODO: in as ist ein baum t nicht definiert; ersetzen durch t_{C'}
- // TODO: Einrückung in as nach pick element nicht notwendig
-
// loop through most general roles
for(ObjectProperty op : mgr) {
+ System.out.println("pick most general role: " + op);
// a list of subtrees (stored as edges i.e. role + root node which points to tree)
- // TODO: Do we need to store m at all?
LinkedList<ELDescriptionEdge> m = new LinkedList<ELDescriptionEdge>();
// create tree corresponding to top node
@@ -266,20 +270,29 @@
while(!m.isEmpty()) {
// pick and remove first element
ELDescriptionEdge edge = m.pollFirst();
+ System.out.println("picked first element of M: " + edge);
ObjectProperty r = edge.getLabel();
// tp = t' in algorithm description (p stands for prime)
ELDescriptionTree tp = edge.getNode().getTree();
// merge tree into main tree
ELDescriptionTree mergedTree = mergeTrees(tree, v, position, r, tp);
+ ELDescriptionNode vClone = mergedTree.getNode(position);
+ System.out.println("merged to t_{C'}: \n" + mergedTree);
+
+// System.out.println(mergedTree.toSimulationString());
+
// we check equivalence by a minimality test (TODO: can we still do this?)
if(mergedTree.isMinimal()) {
+ System.out.println("Merged tree is minimal, i.e. not equivalent.");
// it is not equivalent, i.e. we found a refinement
refinements.add(mergedTree);
} else {
- // perform complex check
- boolean check = asCheck(v);
+ System.out.println("Merged tree is not minimal, i.e. equivalent.");
+ // perform complex check in merged tree
+ boolean check = asCheck(vClone);
+ System.out.println("Result of complex check: " + check);
if(check) {
// refine property
@@ -287,12 +300,17 @@
m.add(new ELDescriptionEdge(subRole, tp.getRootNode()));
}
// refine tree using recursive operator call
+ System.out.println("Recursive Call");
Set<ELDescriptionTree> recRefs = refine(tp);
+ System.out.println("Recursive Call Done");
for(ELDescriptionTree tpp : recRefs) {
+// System.out.println("aa " + tpp.toDescriptionString());
m.add(new ELDescriptionEdge(r, tpp.getRootNode()));
}
}
- }
+ }
+
+ System.out.println("M: " + m);
}
}
@@ -301,11 +319,17 @@
// create a new tree which is obtained by attaching the new tree at the given node in the tree via role r
private ELDescriptionTree mergeTrees(ELDescriptionTree tree, ELDescriptionNode node, int[] position, ObjectProperty r, ELDescriptionTree newTree) {
+// System.out.println("merge start");
+// System.out.println(tree);
+// System.out.println(newTree);
// merged tree = tree + new node with role pointing to a new node
ELDescriptionTree mergedTree = tree.clone();
ELDescriptionNode clonedNode = mergedTree.getNode(position);
// ELDescriptionNode nodeNew = new ELDescriptionNode(clonedNode, r);
+// System.out.println("node: " + node);
+// System.out.println("cloned node: " + clonedNode);
+
// create a list of nodes we still need to process
LinkedList<ELDescriptionNode> toProcess = new LinkedList<ELDescriptionNode>();
toProcess.add(newTree.getRootNode());
@@ -322,7 +346,7 @@
ELDescriptionNode vp;
if(v.isRoot()) {
// root is connected to main tree via role r
- vp = new ELDescriptionNode(clonedNode, r);
+ vp = new ELDescriptionNode(clonedNode, r, newTree.getRootNode().getLabel());
} else {
ELDescriptionNode parent = cloneMap.get(v.getParent());
ObjectProperty role = v.getParentEdge().getLabel();
@@ -337,6 +361,8 @@
}
}
+// System.out.println(mergedTree);
+// System.out.println("merge end");
return mergedTree;
}
@@ -351,16 +377,16 @@
// go through all edges
for(ELDescriptionEdge piVEdge : piVEdges) {
- // collect (w,s,w')
+ // collect (w,r',w')
ELDescriptionNode wp = piVEdge.getNode();
- ObjectProperty s = piVEdge.getLabel();
+ ObjectProperty rp = piVEdge.getLabel();
ELDescriptionNode w = wp.getParent();
// go through all (w,s,w'') - TODO: s or a new s' ?
for(ELDescriptionEdge wEdge : w.getEdges()) {
- ObjectProperty sp = wEdge.getLabel();
+ ObjectProperty rpp = wEdge.getLabel();
ELDescriptionNode wpp = wEdge.getNode();
- if(s.equals(sp) && wp != wpp) {
+ if(wp != wpp && opHierarchy.isSubpropertyOf(rp, rpp)) {
if(wp.getIn().contains(wpp)) {
return false;
}
Modified: trunk/src/dl-learner/org/dllearner/refinementoperators/Utility.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/refinementoperators/Utility.java 2008-12-17 15:05:28 UTC (rev 1557)
+++ trunk/src/dl-learner/org/dllearner/refinementoperators/Utility.java 2008-12-17 15:20:27 UTC (rev 1558)
@@ -123,11 +123,11 @@
// not satisfied
// check1: disjointness with index
// check3: no superclass exists already
- if(!isDisjoint(candidate,index) || !checkSubClasses(existingClasses,candidate)) {
+ if(!isDisjoint(candidate,index) && checkSubClasses(existingClasses,candidate)) {
// check whether the class is meaningful, i.e. adds something to the index
// to do this, we need to make sure that the class is not a superclass of the
// index (otherwise we get nothing new)
- if(!isDisjoint(new Negation(candidate),index) || !checkSuperClasses(existingClasses,candidate)) {
+ if(!isDisjoint(new Negation(candidate),index) && checkSuperClasses(existingClasses,candidate)) {
// candidate went successfully through all checks
candidates.add(candidate);
} else {
@@ -140,17 +140,19 @@
return candidates;
}
- // returns true of the candidate is not subclass of an existing class,
+ // returns true if the candidate is not subclass of an existing class,
// false otherwise (check 3)
private boolean checkSubClasses(Set<NamedClass> existingClasses, NamedClass candidate) {
for(NamedClass nc : existingClasses) {
- if(sh.isSubclassOf(candidate, nc))
+// System.out.println("csc: " + nc + candidate);
+ if(sh.isSubclassOf(candidate, nc)) {
return false;
+ }
}
return true;
}
- // returns true of the candidate is not superclass of an existing class,
+ // returns true if the candidate is not superclass of an existing class,
// false otherwise (check 4)
private boolean checkSuperClasses(Set<NamedClass> existingClasses, NamedClass candidate) {
for(NamedClass nc : existingClasses) {
Modified: trunk/src/dl-learner/org/dllearner/test/junit/ELDescriptionTreeTests.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/test/junit/ELDescriptionTreeTests.java 2008-12-17 15:05:28 UTC (rev 1557)
+++ trunk/src/dl-learner/org/dllearner/test/junit/ELDescriptionTreeTests.java 2008-12-17 15:20:27 UTC (rev 1558)
@@ -85,7 +85,7 @@
ConceptTransformation.cleanConcept(d);
ELDescriptionTree tree = new ELDescriptionTree(rs, d);
// clone performance (false for simple unit test, true for clone performance test)
- boolean testPerformance = false;
+ boolean testPerformance = true;
ELDescriptionTree treeCloned = null;
if(testPerformance) {
int runs = 1000000;
Modified: trunk/src/dl-learner/org/dllearner/test/junit/ELDownTests.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/test/junit/ELDownTests.java 2008-12-17 15:05:28 UTC (rev 1557)
+++ trunk/src/dl-learner/org/dllearner/test/junit/ELDownTests.java 2008-12-17 15:20:27 UTC (rev 1558)
@@ -28,7 +28,7 @@
import org.dllearner.core.owl.Description;
import org.dllearner.parser.KBParser;
import org.dllearner.parser.ParseException;
-import org.dllearner.refinementoperators.ELDown;
+import org.dllearner.refinementoperators.ELDown2;
import org.dllearner.test.junit.TestOntologies.TestOntology;
import org.dllearner.utilities.Helper;
import org.dllearner.utilities.owl.ConceptComparator;
@@ -61,7 +61,7 @@
// TODO For this test, we need to turn instance based disjoints
// off! (We do not have any instances here.)
- ELDown operator = new ELDown(rs);
+ ELDown2 operator = new ELDown2(rs);
// desired refinements as strings
Set<String> desiredString = new TreeSet<String>();
Modified: trunk/src/dl-learner/org/dllearner/test/junit/SimulationTests.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/test/junit/SimulationTests.java 2008-12-17 15:05:28 UTC (rev 1557)
+++ trunk/src/dl-learner/org/dllearner/test/junit/SimulationTests.java 2008-12-17 15:20:27 UTC (rev 1558)
@@ -32,6 +32,7 @@
import org.dllearner.core.ReasonerComponent;
import org.dllearner.core.owl.NamedClass;
import org.dllearner.core.owl.ObjectProperty;
+import org.dllearner.core.owl.Thing;
import org.dllearner.parser.KBParser;
import org.dllearner.test.junit.TestOntologies.TestOntology;
import org.junit.Test;
@@ -662,6 +663,25 @@
}
+ @Test
+ public void test7() {
+ ReasonerComponent rs = TestOntologies.getTestOntology(TestOntology.SIMPLE);
+ ELDescriptionTree tree = new ELDescriptionTree(rs);
+
+ ObjectProperty has = new ObjectProperty(uri("has"));
+ ObjectProperty hasChild = new ObjectProperty(uri("hasChild"));
+ NamedClass human = new NamedClass(uri("human"));
+ NamedClass animal = new NamedClass(uri("animal"));
+
+ ELDescriptionNode v1 = new ELDescriptionNode(tree, human);
+ new ELDescriptionNode(v1, has, animal);
+ new ELDescriptionNode(v1, hasChild);
+
+// System.out.println(tree.toSimulationString());
+
+ assertTrue(tree.isMinimal());
+ }
+
// display a simulation as debug log
@SuppressWarnings("unused")
private void log(String message, ELDescriptionTree tree, Map<ELDescriptionNode,String> nodeNames) {
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
