Menu
▾
▴
[DL-Learner SVN] SF.net SVN: dl-learner:[1631] trunk/src/dl-learner/org/dllearner
|
From: <jen...@us...> - 2009-02-25 16:26:19
|
Revision: 1631
http://dl-learner.svn.sourceforge.net/dl-learner/?rev=1631&view=rev
Author: jenslehmann
Date: 2009-02-25 16:26:08 +0000 (Wed, 25 Feb 2009)
Log Message:
-----------
- wrote a method which detects whether a description can be transformed to another one by removing parts of it
- CELOE is guaranteed not to return descriptions with the same accuracy where one can be transformed to the other
- CELOE does not extend correct nodes further than description length
Modified Paths:
--------------
trunk/src/dl-learner/org/dllearner/algorithms/celoe/CELOE.java
trunk/src/dl-learner/org/dllearner/core/configurators/RefinementOperatorConfigurator.java
trunk/src/dl-learner/org/dllearner/core/options/CommonConfigOptions.java
trunk/src/dl-learner/org/dllearner/core/owl/ClassHierarchy.java
trunk/src/dl-learner/org/dllearner/reasoning/FastInstanceChecker.java
trunk/src/dl-learner/org/dllearner/refinementoperators/RhoDRDown.java
trunk/src/dl-learner/org/dllearner/utilities/owl/ConceptTransformation.java
trunk/src/dl-learner/org/dllearner/utilities/owl/DescriptionMinimizer.java
Modified: trunk/src/dl-learner/org/dllearner/algorithms/celoe/CELOE.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/algorithms/celoe/CELOE.java 2009-02-25 13:17:50 UTC (rev 1630)
+++ trunk/src/dl-learner/org/dllearner/algorithms/celoe/CELOE.java 2009-02-25 16:26:08 UTC (rev 1631)
@@ -21,6 +21,7 @@
import java.text.DecimalFormat;
import java.util.Collection;
+import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
@@ -133,7 +134,8 @@
options.add(CommonConfigOptions.valueFreqencyThreshold());
options.add(CommonConfigOptions.useCardinalityRestrictions());
options.add(CommonConfigOptions.cardinalityLimit());
- options.add(CommonConfigOptions.useNegation());
+ // by default, we do not use negation (should be configurable in GUI)
+ options.add(CommonConfigOptions.useNegation(false));
options.add(CommonConfigOptions.useBooleanDatatypes());
options.add(CommonConfigOptions.useDoubleDatatypes());
options.add(CommonConfigOptions.maxExecutionTimeInSeconds(10));
@@ -227,7 +229,7 @@
// highest accuracy so far
double highestAccuracy = 0.0;
- OENode bestNode;
+ OENode nextNode;
addNode(startClass, null);
@@ -242,12 +244,12 @@
}
// chose best node according to heuristics
- bestNode = nodes.last();
- int horizExp = bestNode.getHorizontalExpansion();
+ nextNode = getNextNodeToExpand();
+ int horizExp = nextNode.getHorizontalExpansion();
// apply operator
Monitor mon = MonitorFactory.start("refineNode");
- TreeSet<Description> refinements = refineNode(bestNode);
+ TreeSet<Description> refinements = refineNode(nextNode);
mon.stop();
while(refinements.size() != 0) {
@@ -260,7 +262,7 @@
if(length > horizExp && refinement.getDepth() <= maxDepth) {
Monitor mon2 = MonitorFactory.start("addNode");
- boolean added = addNode(refinement, bestNode);
+ boolean added = addNode(refinement, nextNode);
mon2.stop();
// if refinements have the same length, we apply the operator again
@@ -293,6 +295,23 @@
isRunning = false;
}
+ private OENode getNextNodeToExpand() {
+ // we expand the best node of those, which have not achieved 100% accuracy
+ // already and have a horizontal expansion equalling their length
+ // (rationale: further extension is likely to add irrelevant syntactical constructs)
+ Iterator<OENode> it = nodes.descendingIterator();
+ while(it.hasNext()) {
+ OENode node = it.next();
+ if(node.getAccuracy() < 1.0 || node.getHorizontalExpansion() < node.getDescription().getLength()) {
+ return node;
+ }
+ }
+
+ // this should practically never be called, since for any reasonable learning
+ // task, we will always have at least one node with less than 100% accuracy
+ return nodes.last();
+ }
+
// expand node horizontically
private TreeSet<Description> refineNode(OENode node) {
// we have to remove and add the node since its heuristic evaluation changes through the expansion
@@ -356,7 +375,21 @@
if(isCandidate) {
Description niceDescription = rewriteNode(node);
- bestEvaluatedDescriptions.add(niceDescription, accuracy, learningProblem);
+
+ // another test: none of the other suggested descriptions should be
+ // a subdescription of this one unless accuracy is different
+ boolean shorterDescriptionExists = false;
+ for(EvaluatedDescription ed : bestEvaluatedDescriptions.getSet()) {
+ if(ed.getAccuracy()==accuracy && ConceptTransformation.isSubdescription(niceDescription, ed.getDescription())) {
+ shorterDescriptionExists = true;
+ break;
+ }
+ }
+
+ if(!shorterDescriptionExists) {
+ bestEvaluatedDescriptions.add(niceDescription, accuracy, learningProblem);
+ }
+
}
return true;
@@ -379,8 +412,14 @@
}
toTest.addAll(reasoner.getClassHierarchy().getSuperClasses(d));
}
- return true;
}
+
+ // we do not want to have negations of sibling classes on the outermost level
+ // (they are expressed more naturally by saying that the siblings are disjoint,
+ // so it is reasonable not to include them in solutions)
+ Set<Description> siblingClasses = reasoner.getClassHierarchy().getSiblingClasses(classToDescribe);
+
+ return true;
}
// determine whether a named class occurs on the outermost level, i.e. property depth 0
@@ -405,10 +444,29 @@
return false;
}
+ private boolean occursNegatedOnFirstLevel(Description description, Description clazz) {
+ if(description instanceof NamedClass) {
+ if(description.equals(clazz)) {
+ return true;
+ }
+ }
+
+ if(description instanceof Restriction) {
+ return false;
+ }
+
+ for(Description child : description.getChildren()) {
+ if(occursOnFirstLevel(child, clazz)) {
+ return true;
+ }
+ }
+
+ return false;
+ }
+
// check whether the node is a potential solution candidate
private Description rewriteNode(OENode node) {
Description description = node.getDescription();
-// Description niceDescription = description;
// minimize description (expensive!)
Description niceDescription = minimizer.minimizeClone(description);
// replace \exists r.\top with \exists r.range(r) which is easier to read for humans
@@ -423,7 +481,6 @@
private void reset() {
// set all values back to their default values (used for running
// the algorithm more than once)
-// candidates.clear();
nodes = new TreeSet<OENode>(new OEHeuristicRuntime());
descriptions = new TreeSet<Description>(new ConceptComparator());
bestEvaluatedDescriptions.getSet().clear();
@@ -456,15 +513,11 @@
}
private String getSolutionString() {
-// int max = 10;
int current = 1;
String str = "";
for(EvaluatedDescription ed : bestEvaluatedDescriptions.getSet().descendingSet()) {
str += current + ": " + descriptionToString(ed.getDescription()) + " " + dfPercent.format(ed.getAccuracy()) + "\n";
current++;
-// if(current == max) {
-// break;
-// }
}
return str;
}
Modified: trunk/src/dl-learner/org/dllearner/core/configurators/RefinementOperatorConfigurator.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/core/configurators/RefinementOperatorConfigurator.java 2009-02-25 13:17:50 UTC (rev 1630)
+++ trunk/src/dl-learner/org/dllearner/core/configurators/RefinementOperatorConfigurator.java 2009-02-25 16:26:08 UTC (rev 1631)
@@ -23,10 +23,35 @@
* Common options of refinement operators (manually created interface).
*
* @author Jens Lehmann
- *
+ *
*/
public abstract class RefinementOperatorConfigurator {
public abstract boolean getUseCardinalityRestrictions();
+
+ public abstract boolean getUseNegation();
+
+ public abstract boolean getUseAllConstructor();
+
+ public abstract boolean getUseExistsConstructor();
+
+ public abstract boolean getUseBooleanDatatypes();
+ // below are optional parameters (neutral return values choosen)
+
+ public boolean getUseHasValueConstructor() {
+ return false;
+ }
+
+ public int getValueFrequencyThreshold() {
+ return 3;
+ }
+
+ public int getCardinalityLimit() {
+ return 5;
+ }
+
+ public boolean getUseDoubleDatatypes() {
+ return false;
+ }
}
Modified: trunk/src/dl-learner/org/dllearner/core/options/CommonConfigOptions.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/core/options/CommonConfigOptions.java 2009-02-25 13:17:50 UTC (rev 1630)
+++ trunk/src/dl-learner/org/dllearner/core/options/CommonConfigOptions.java 2009-02-25 16:26:08 UTC (rev 1631)
@@ -147,6 +147,10 @@
return new BooleanConfigOption("useNegation", "specifies whether negation is used in the learning algorothm",useNegationDefault);
}
+ public static BooleanConfigOption useNegation(boolean defaultValue) {
+ return new BooleanConfigOption("useNegation", "specifies whether negation is used in the learning algorothm",defaultValue);
+ }
+
public static BooleanConfigOption useBooleanDatatypes() {
return new BooleanConfigOption("useBooleanDatatypes", "specifies whether boolean datatypes are used in the learning algorothm",useBooleanDatatypesDefault);
}
Modified: trunk/src/dl-learner/org/dllearner/core/owl/ClassHierarchy.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/core/owl/ClassHierarchy.java 2009-02-25 13:17:50 UTC (rev 1630)
+++ trunk/src/dl-learner/org/dllearner/core/owl/ClassHierarchy.java 2009-02-25 16:26:08 UTC (rev 1631)
@@ -89,6 +89,25 @@
}
/**
+ * Computes the siblings of the specified descriptions. Siblings are all those
+ * classes, which are subclasses of a parent of a class and not equal to the
+ * class itself. Note that retrieving siblings is computationally more
+ * expensive than descending/ascending the hierarchy as siblings are computed
+ * when required and not cached.
+ * @param description A named class.
+ * @return A set of named classes, which are siblings of the given class.
+ */
+ public SortedSet<Description> getSiblingClasses(Description description) {
+ Set<Description> superClasses = subsumptionHierarchyUp.get(description);
+ TreeSet<Description> siblingClasses = new TreeSet<Description>(conceptComparator);
+ for(Description superClass : superClasses) {
+ siblingClasses.addAll(subsumptionHierarchyDown.get(superClass));
+ }
+ siblingClasses.remove(description);
+ return siblingClasses;
+ }
+
+ /**
* This method modifies the subsumption hierarchy such that for each class,
* there is only a single path to reach it via upward and downward
* refinement respectively.
Modified: trunk/src/dl-learner/org/dllearner/reasoning/FastInstanceChecker.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/reasoning/FastInstanceChecker.java 2009-02-25 13:17:50 UTC (rev 1630)
+++ trunk/src/dl-learner/org/dllearner/reasoning/FastInstanceChecker.java 2009-02-25 16:26:08 UTC (rev 1631)
@@ -857,7 +857,7 @@
// Negation neg = new Negation(subConcept);
// Intersection c = new Intersection(neg,superConcept);
// return fastRetrieval.calculateSets(c).getPosSet().isEmpty();
- return rc.isSuperClassOf(superConcept, subConcept);
+ return rc.isSuperClassOfImpl(superConcept, subConcept);
}
/**
Modified: trunk/src/dl-learner/org/dllearner/refinementoperators/RhoDRDown.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/refinementoperators/RhoDRDown.java 2009-02-25 13:17:50 UTC (rev 1630)
+++ trunk/src/dl-learner/org/dllearner/refinementoperators/RhoDRDown.java 2009-02-25 16:26:08 UTC (rev 1631)
@@ -191,8 +191,15 @@
this.rs = reasoner;
this.subHierarchy = subHierarchy;
this.startClass = startClass;
+ useAllConstructor = configurator.getUseAllConstructor();
+ useExistsConstructor = configurator.getUseExistsConstructor();
+ useHasValueConstructor = configurator.getUseHasValueConstructor();
+ frequencyThreshold = configurator.getValueFrequencyThreshold();
useCardinalityRestrictions = configurator.getUseCardinalityRestrictions();
- // TODO add more options from configurator object
+ cardinalityLimit = configurator.getCardinalityLimit();
+ useNegation = configurator.getUseNegation();
+ useBooleanDatatypes = configurator.getUseBooleanDatatypes();
+ useDoubleDatatypes = configurator.getUseDoubleDatatypes();
init();
}
Modified: trunk/src/dl-learner/org/dllearner/utilities/owl/ConceptTransformation.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/utilities/owl/ConceptTransformation.java 2009-02-25 13:17:50 UTC (rev 1630)
+++ trunk/src/dl-learner/org/dllearner/utilities/owl/ConceptTransformation.java 2009-02-25 16:26:08 UTC (rev 1631)
@@ -59,6 +59,8 @@
public static long shorteningTimeNs = 0;
private static long shorteningTimeNsStart = 0;
+ private static ConceptComparator descComp = new ConceptComparator();
+
public static void cleanConceptNonRecursive(Description concept) {
// cleaningTimeNsStart = System.nanoTime();
@@ -487,4 +489,85 @@
}
}
+ /**
+ * Tests whether a description is a subdescription in the sense that when
+ * parts of <code>description</code> can be removed to yield <code>subdescription</code>.
+ *
+ * @param description A description.
+ * @param subDescription A potential subdescription.
+ * @return True if <code>subdescription</code> is indeed a sub description and false
+ * otherwise.
+ */
+ public static boolean isSubdescription(Description description, Description subDescription) {
+// if(description instanceof Thing) {
+// return (subDescription instanceof Thing);
+// } else if(description instanceof Nothing) {
+// return (subDescription instanceof Thing);
+// } else if(description instanceof NamedClass) {
+// return ((subDescription instanceof NamedClass) && (((NamedClass)description).getName().equals(((NamedClass)subDescription).getName())));
+// }
+
+ List<Description> children = description.getChildren();
+ List<Description> subChildren = subDescription.getChildren();
+
+ // no children: both have to be equal
+ if(children.size()==0) {
+ return (descComp.compare(description, subDescription)==0);
+ // one child: both have to be of the same class, type, and the first
+ // child has to be sub description of the other child
+ } else if(children.size()==1) {
+ return (subChildren.size() == 1) && description.getClass().equals(subDescription.getClass()) && isSubdescription(children.get(0), subChildren.get(0));
+ // intersection or union
+ } else {
+ // test whether subdescription corresponds to an element of the
+ // intersection/union
+ if(subChildren.size()<2) {
+ for(Description child : children) {
+ if(isSubdescription(child, subDescription)) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ // make sure that both are of the same type and subdescription actually has fewer children
+ if(!description.getClass().equals(subDescription.getClass()) || subChildren.size() > children.size()) {
+ return false;
+ }
+
+ // comparing everything is quadratic; the faster linear variant (below)
+ // using
+
+ for(Description subChild : subChildren) {
+ boolean foundMatch = false;
+ for(Description child : children) {
+ if(isSubdescription(child, subChild)) {
+ foundMatch = true;
+ break;
+ }
+ }
+ if(!foundMatch) {
+ return false;
+ }
+ }
+
+ return true;
+
+// // method core; traverse the descriptions in linear time using ordered
+// // normal form (TODO: does not always work e.g. A2 \sqcap (A1 \sqcup A3)
+ // and A1 \sqcap A2 -> it won't find the A2 match because it has advanced
+ // beyond it already)
+// int j = 0;
+// for(Description child : children) {
+// if(isSubdescription(child, subChildren.get(j))) {
+// j++;
+// }
+// if(j == subChildren.size()) {
+// return true;
+// }
+// }
+// // there is at least one child we could not match
+// return false;
+ }
+ }
}
Modified: trunk/src/dl-learner/org/dllearner/utilities/owl/DescriptionMinimizer.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/utilities/owl/DescriptionMinimizer.java 2009-02-25 13:17:50 UTC (rev 1630)
+++ trunk/src/dl-learner/org/dllearner/utilities/owl/DescriptionMinimizer.java 2009-02-25 16:26:08 UTC (rev 1631)
@@ -32,6 +32,7 @@
import org.dllearner.core.owl.ObjectAllRestriction;
import org.dllearner.core.owl.ObjectMaxCardinalityRestriction;
import org.dllearner.core.owl.ObjectMinCardinalityRestriction;
+import org.dllearner.core.owl.ObjectProperty;
import org.dllearner.core.owl.ObjectSomeRestriction;
import org.dllearner.core.owl.Thing;
import org.dllearner.core.owl.Union;
@@ -51,6 +52,8 @@
private ConceptComparator conceptComparator = new ConceptComparator();
private Map<Description,Map<Description,Boolean>> cachedSubclassOf = new TreeMap<Description,Map<Description,Boolean>>(conceptComparator);
+ private boolean beautify = false;
+
public DescriptionMinimizer(ReasonerComponent reasoner) {
this.reasoner = reasoner;
}
@@ -104,6 +107,12 @@
if(description.getChild(0) instanceof Thing) {
return Thing.instance;
}
+ // we rewrite \forall r.\bot to \neg \exists r.\top
+ // which is longer but easier to understand for humans
+ if(beautify && description.getChild(0) instanceof Nothing) {
+ ObjectProperty p = (ObjectProperty)((ObjectAllRestriction)description).getRole();
+ return new Negation(new ObjectSomeRestriction(p, Thing.instance));
+ }
return description;
} else if(description instanceof Negation) {
// \neg \bot \equiv \top
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
