From: <jen...@us...> - 2008-02-22 15:16:40
|
Revision: 626 http://dl-learner.svn.sourceforge.net/dl-learner/?rev=626&view=rev Author: jenslehmann Date: 2008-02-22 07:16:02 -0800 (Fri, 22 Feb 2008) Log Message: ----------- implemented lightning fast instance check algorithm Modified Paths: -------------- trunk/lib/components.ini trunk/src/dl-learner/org/dllearner/algorithms/refexamples/ExampleBasedROLearner.java trunk/src/dl-learner/org/dllearner/algorithms/refinement/ROLearner.java trunk/src/dl-learner/org/dllearner/cli/Start.java trunk/src/dl-learner/org/dllearner/core/ReasoningMethodUnsupportedException.java trunk/src/dl-learner/org/dllearner/core/owl/NamedClass.java trunk/src/dl-learner/org/dllearner/core/owl/ObjectProperty.java trunk/src/dl-learner/org/dllearner/examples/Carcinogenesis.java trunk/src/dl-learner/org/dllearner/parser/kb.jj trunk/src/dl-learner/org/dllearner/reasoning/FastInstanceChecker.java trunk/src/dl-learner/org/dllearner/reasoning/FastRetrievalReasoner.java trunk/src/dl-learner/org/dllearner/reasoning/ReasonerType.java trunk/src/dl-learner/org/dllearner/test/junit/ReasonerTests.java Modified: trunk/lib/components.ini =================================================================== --- trunk/lib/components.ini 2008-02-22 12:50:11 UTC (rev 625) +++ trunk/lib/components.ini 2008-02-22 15:16:02 UTC (rev 626) @@ -8,6 +8,7 @@ org.dllearner.reasoning.OWLAPIReasoner org.dllearner.reasoning.DIGReasoner org.dllearner.reasoning.FastRetrievalReasoner +org.dllearner.reasoning.FastInstanceChecker # learning problems org.dllearner.learningproblems.PosNegDefinitionLP org.dllearner.learningproblems.PosNegInclusionLP Modified: trunk/src/dl-learner/org/dllearner/algorithms/refexamples/ExampleBasedROLearner.java =================================================================== --- trunk/src/dl-learner/org/dllearner/algorithms/refexamples/ExampleBasedROLearner.java 2008-02-22 12:50:11 UTC (rev 625) +++ trunk/src/dl-learner/org/dllearner/algorithms/refexamples/ExampleBasedROLearner.java 2008-02-22 15:16:02 UTC (rev 626) @@ -621,6 +621,8 @@ // System.out.println("properness max recursion depth: " + maxRecDepth); // System.out.println("max. number of one-step refinements: " + maxNrOfRefinements); // System.out.println("max. number of children of a node: " + maxNrOfChildren); + System.out.println("subsumption time: " + Helper.prettyPrintNanoSeconds(rs.getSubsumptionReasoningTimeNs())); + System.out.println("instance check time: " + Helper.prettyPrintNanoSeconds(rs.getInstanceCheckReasoningTimeNs())); } if(computeBenchmarkInformation) { Modified: trunk/src/dl-learner/org/dllearner/algorithms/refinement/ROLearner.java =================================================================== --- trunk/src/dl-learner/org/dllearner/algorithms/refinement/ROLearner.java 2008-02-22 12:50:11 UTC (rev 625) +++ trunk/src/dl-learner/org/dllearner/algorithms/refinement/ROLearner.java 2008-02-22 15:16:02 UTC (rev 626) @@ -900,6 +900,8 @@ // System.out.println("properness max recursion depth: " + maxRecDepth); // System.out.println("max. number of one-step refinements: " + maxNrOfRefinements); // System.out.println("max. number of children of a node: " + maxNrOfChildren); + logger.debug("subsumption time: " + Helper.prettyPrintNanoSeconds(rs.getSubsumptionReasoningTimeNs())); + logger.debug("instance check time: " + Helper.prettyPrintNanoSeconds(rs.getInstanceCheckReasoningTimeNs())); } if(showBenchmarkInformation) { Modified: trunk/src/dl-learner/org/dllearner/cli/Start.java =================================================================== --- trunk/src/dl-learner/org/dllearner/cli/Start.java 2008-02-22 12:50:11 UTC (rev 625) +++ trunk/src/dl-learner/org/dllearner/cli/Start.java 2008-02-22 15:16:02 UTC (rev 626) @@ -78,6 +78,7 @@ import org.dllearner.parser.ParseException; import org.dllearner.parser.TokenMgrError; import org.dllearner.reasoning.DIGReasoner; +import org.dllearner.reasoning.FastInstanceChecker; import org.dllearner.reasoning.FastRetrievalReasoner; import org.dllearner.reasoning.OWLAPIReasoner; import org.dllearner.utilities.ConceptComparator; @@ -751,6 +752,8 @@ reasonerClass = OWLAPIReasoner.class; else if (reasonerOption.getStringValue().equals("fastRetrieval")) reasonerClass = FastRetrievalReasoner.class; + else if (reasonerOption.getStringValue().equals("fastInstanceChecker")) + reasonerClass = FastInstanceChecker.class; else { handleError("Unknown value " + reasonerOption.getStringValue() + " for option \"reasoner\"."); Modified: trunk/src/dl-learner/org/dllearner/core/ReasoningMethodUnsupportedException.java =================================================================== --- trunk/src/dl-learner/org/dllearner/core/ReasoningMethodUnsupportedException.java 2008-02-22 12:50:11 UTC (rev 625) +++ trunk/src/dl-learner/org/dllearner/core/ReasoningMethodUnsupportedException.java 2008-02-22 15:16:02 UTC (rev 626) @@ -1,7 +1,44 @@ +/** + * Copyright (C) 2007, Jens Lehmann + * + * This file is part of DL-Learner. + * + * DL-Learner is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 3 of the License, or + * (at your option) any later version. + * + * DL-Learner is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + * + */ package org.dllearner.core; +/** + * Exception indicating that a reasoner implementation cannot support + * the requested operation. Either the operation itself is not implemented + * or does not support certain features, e.g. a reasoner could support + * instance checks but not if the class description contains datatype + * constructs. + * + * @author Jens Lehmann + * + */ public class ReasoningMethodUnsupportedException extends Exception { private static final long serialVersionUID = -7045236443032695475L; + + public ReasoningMethodUnsupportedException() { + super(); + } + + public ReasoningMethodUnsupportedException(String message) { + super(message); + } } Modified: trunk/src/dl-learner/org/dllearner/core/owl/NamedClass.java =================================================================== --- trunk/src/dl-learner/org/dllearner/core/owl/NamedClass.java 2008-02-22 12:50:11 UTC (rev 625) +++ trunk/src/dl-learner/org/dllearner/core/owl/NamedClass.java 2008-02-22 15:16:02 UTC (rev 626) @@ -30,7 +30,7 @@ * @author Jens Lehmann * */ -public class NamedClass extends Description implements NamedKBElement { +public class NamedClass extends Description implements NamedKBElement, Comparable<NamedClass> { String name; @@ -79,4 +79,8 @@ public String toManchesterSyntaxString(String baseURI, Map<String, String> prefixes) { return Helper.getAbbreviatedString(name, baseURI, prefixes); } + + public int compareTo(NamedClass o) { + return name.compareTo(o.name); + } } Modified: trunk/src/dl-learner/org/dllearner/core/owl/ObjectProperty.java =================================================================== --- trunk/src/dl-learner/org/dllearner/core/owl/ObjectProperty.java 2008-02-22 12:50:11 UTC (rev 625) +++ trunk/src/dl-learner/org/dllearner/core/owl/ObjectProperty.java 2008-02-22 15:16:02 UTC (rev 626) @@ -30,7 +30,7 @@ * @author Jens Lehmann * */ -public class ObjectProperty extends ObjectPropertyExpression implements Property, NamedKBElement { +public class ObjectProperty extends ObjectPropertyExpression implements Property, NamedKBElement, Comparable<ObjectProperty> { public ObjectProperty(String name) { super(name); @@ -51,5 +51,9 @@ public void accept(KBElementVisitor visitor) { visitor.visit(this); + } + + public int compareTo(ObjectProperty o) { + return name.compareTo(o.name); } } Modified: trunk/src/dl-learner/org/dllearner/examples/Carcinogenesis.java =================================================================== --- trunk/src/dl-learner/org/dllearner/examples/Carcinogenesis.java 2008-02-22 12:50:11 UTC (rev 625) +++ trunk/src/dl-learner/org/dllearner/examples/Carcinogenesis.java 2008-02-22 15:16:02 UTC (rev 626) @@ -169,6 +169,8 @@ File confTrainFile = new File("examples/carcinogenesis/train.conf"); Files.clearFile(confTrainFile); String confHeader = "import(\"pte.owl\");\n\n"; + confHeader += "refinement.writeSearchTree = true;"; + confHeader += "refinement.searchTreeFile = \"log/carcinogenesis/searchTree.log\""; confHeader += "reasoner = owlAPI;\n"; Files.appendFile(confTrainFile, confHeader); Modified: trunk/src/dl-learner/org/dllearner/parser/kb.jj =================================================================== --- trunk/src/dl-learner/org/dllearner/parser/kb.jj 2008-02-22 12:50:11 UTC (rev 625) +++ trunk/src/dl-learner/org/dllearner/parser/kb.jj 2008-02-22 15:16:02 UTC (rev 626) @@ -36,7 +36,7 @@ public class KBParser { - public static final String internalNamespace = "http://localhost/foo#"; + public static String internalNamespace = "http://localhost/foo#"; // method to give all internal stuff an URI (not necessary for DLs, but for OWL ontologies // and it should be possible to represent the internal KB as OWL ontology) Modified: trunk/src/dl-learner/org/dllearner/reasoning/FastInstanceChecker.java =================================================================== --- trunk/src/dl-learner/org/dllearner/reasoning/FastInstanceChecker.java 2008-02-22 12:50:11 UTC (rev 625) +++ trunk/src/dl-learner/org/dllearner/reasoning/FastInstanceChecker.java 2008-02-22 15:16:02 UTC (rev 626) @@ -19,50 +19,96 @@ */ package org.dllearner.reasoning; -import java.util.HashMap; +import java.io.File; +import java.util.List; import java.util.Map; import java.util.Set; import java.util.SortedSet; +import java.util.TreeMap; +import org.apache.log4j.Logger; import org.dllearner.core.ComponentInitException; +import org.dllearner.core.ComponentManager; import org.dllearner.core.KnowledgeSource; import org.dllearner.core.ReasonerComponent; +import org.dllearner.core.ReasoningMethodUnsupportedException; import org.dllearner.core.ReasoningService; import org.dllearner.core.config.ConfigEntry; import org.dllearner.core.config.InvalidConfigOptionValueException; -import org.dllearner.core.owl.FlatABox; +import org.dllearner.core.owl.Description; import org.dllearner.core.owl.Individual; +import org.dllearner.core.owl.Intersection; import org.dllearner.core.owl.NamedClass; +import org.dllearner.core.owl.Negation; +import org.dllearner.core.owl.Nothing; +import org.dllearner.core.owl.ObjectAllRestriction; import org.dllearner.core.owl.ObjectProperty; +import org.dllearner.core.owl.ObjectPropertyExpression; +import org.dllearner.core.owl.ObjectPropertyHierarchy; +import org.dllearner.core.owl.ObjectSomeRestriction; +import org.dllearner.core.owl.SubsumptionHierarchy; +import org.dllearner.core.owl.Thing; +import org.dllearner.core.owl.Union; +import org.dllearner.kb.OWLFile; +import org.dllearner.parser.KBParser; +import org.dllearner.parser.ParseException; /** * Reasoner for fast instance checks. It works by completely dematerialising the knowledge - * base to speed up later reasoning requests. It + * base to speed up later reasoning requests. It then continues by only considering one + * model of the knowledge base (TODO: more explanation), which is neither correct nor + * complete, but sufficient in many cases. A big advantage of the algorithm is that it + * does not need even need to perform any set modifications (union, intersection, difference), + * so it avoids any object creation, which makes it very fast compared to standard + * reasoners (TODO: maybe add some benchmarks once it is implemented). * + * Note: This algorithm works only on concepts in negation normal form! + * * @author Jens Lehmann * */ public class FastInstanceChecker extends ReasonerComponent { + private static Logger logger = Logger + .getLogger(FastInstanceChecker.class); + private Set<NamedClass> atomicConcepts; private Set<ObjectProperty> atomicRoles; private SortedSet<Individual> individuals; private ReasoningService rs; private ReasonerComponent rc; + private Set<KnowledgeSource> sources; + // we use sorted sets (map indices) here, because they have only log(n) + // complexity for checking whether an element is contained in them // instances of classes - public Map<NamedClass,SortedSet<Individual>> classInstancesPos = new HashMap<NamedClass,SortedSet<Individual>>(); - public Map<NamedClass,SortedSet<Individual>> classInstancesNeg = new HashMap<NamedClass,SortedSet<Individual>>(); - + private Map<NamedClass,SortedSet<Individual>> classInstancesPos = new TreeMap<NamedClass,SortedSet<Individual>>(); + private Map<NamedClass,SortedSet<Individual>> classInstancesNeg = new TreeMap<NamedClass,SortedSet<Individual>>(); // object property mappings - public Map<ObjectProperty,Map<Individual,SortedSet<Individual>>> opPos = new HashMap<ObjectProperty,Map<Individual,SortedSet<Individual>>>(); - public Map<ObjectProperty,Map<Individual,SortedSet<Individual>>> opNeg = new HashMap<ObjectProperty,Map<Individual,SortedSet<Individual>>>(); - + private Map<ObjectProperty,Map<Individual,SortedSet<Individual>>> opPos = new TreeMap<ObjectProperty,Map<Individual,SortedSet<Individual>>>(); + // TODO: datatype properties public FastInstanceChecker(Set<KnowledgeSource> sources) { - rc = new OWLAPIReasoner(sources); + this.sources = sources; + } + + + /* (non-Javadoc) + * @see org.dllearner.core.Component#applyConfigEntry(org.dllearner.core.config.ConfigEntry) + */ + @Override + public <T> void applyConfigEntry(ConfigEntry<T> entry) throws InvalidConfigOptionValueException { + + } + + /* (non-Javadoc) + * @see org.dllearner.core.Component#init() + */ + @Override + public void init() throws ComponentInitException { + rc = new DIGReasoner(sources); try { rc.init(); } catch (ComponentInitException e1) { @@ -77,50 +123,97 @@ // be done (maybe this can be merge again with the FastRetrievalReasoner later) long dematStartTime = System.currentTimeMillis(); - FlatABox aBox = new FlatABox(); for (NamedClass atomicConcept : rs.getAtomicConcepts()) { - // aBox.atomicConceptsPos.put(atomicConcept.getName(), getStringSet(rs - // .retrieval(atomicConcept))); -// Negation negatedAtomicConcept = new Negation(atomicConcept); - // aBox.atomicConceptsNeg.put(atomicConcept.getName(), getStringSet(rs - // .retrieval(negatedAtomicConcept))); - aBox.concepts.add(atomicConcept.getName()); + classInstancesPos.put(atomicConcept, rs.retrieval(atomicConcept)); + Negation negatedAtomicConcept = new Negation(atomicConcept); + classInstancesNeg.put(atomicConcept, rs.retrieval(negatedAtomicConcept)); } for (ObjectProperty atomicRole : rs.getAtomicRoles()) { - // aBox.rolesPos.put(atomicRole.getName(), getStringMap(rs.getRoleMembers(atomicRole))); - aBox.roles.add(atomicRole.getName()); + opPos.put(atomicRole, rs.getRoleMembers(atomicRole)); } - // aBox.domain = getStringSet(rs.getIndividuals()); - // aBox.top = aBox.domain; - - // System.out.println(aBox); - long dematDuration = System.currentTimeMillis() - dematStartTime; - System.out.println("OK (" + dematDuration + " ms)"); + logger.info("TBox dematerialised in " + dematDuration + " ms"); - } - - - /* (non-Javadoc) - * @see org.dllearner.core.Component#applyConfigEntry(org.dllearner.core.config.ConfigEntry) - */ - @Override - public <T> void applyConfigEntry(ConfigEntry<T> entry) throws InvalidConfigOptionValueException { - // TODO Auto-generated method stub - } - /* (non-Javadoc) - * @see org.dllearner.core.Component#init() - */ @Override - public void init() throws ComponentInitException { - // TODO Auto-generated method stub - - } - + public boolean instanceCheck(Description description, Individual individual) throws ReasoningMethodUnsupportedException { + if(description instanceof NamedClass) { + return classInstancesPos.get((NamedClass)description).contains(individual); + } else if(description instanceof Negation) { + Description child = description.getChild(0); + if(child instanceof NamedClass) { + return classInstancesNeg.get((NamedClass)child).contains(individual); + } else { + throw new ReasoningMethodUnsupportedException("Instance check for description " + description + " unsupported. Description needs to be in negation normal form."); + } + } else if(description instanceof Thing) { + return true; + } else if(description instanceof Nothing) { + return false; + } else if(description instanceof Union) { + // if the individual is instance of any of the subdescription of + // the union, we return true + List<Description> children = description.getChildren(); + for(Description child : children) { + if(instanceCheck(child, individual)) + return true; + } + return false; + } else if(description instanceof Intersection) { + // if the individual is instance of all of the subdescription of + // the union, we return true + List<Description> children = description.getChildren(); + for(Description child : children) { + if(!instanceCheck(child, individual)) + return false; + } + return true; + } else if(description instanceof ObjectSomeRestriction) { + ObjectPropertyExpression ope = ((ObjectSomeRestriction)description).getRole(); + if(!(ope instanceof ObjectProperty)) + throw new ReasoningMethodUnsupportedException("Instance check for description " + description + " unsupported. Inverse object properties not supported."); + ObjectProperty op = (ObjectProperty) ope; + Description child = description.getChild(0); + Map<Individual,SortedSet<Individual>> mapping = opPos.get(op);; + if(mapping == null) { + logger.warn("Instance check of a description with an undefinied property (" + op + ")."); + return false; + } + SortedSet<Individual> roleFillers = opPos.get(op).get(individual); + if(roleFillers == null) + return false; + for(Individual roleFiller : roleFillers) { + if(instanceCheck(child, roleFiller)) + return true; + } + return false; + } else if(description instanceof ObjectAllRestriction) { + ObjectPropertyExpression ope = ((ObjectAllRestriction)description).getRole(); + if(!(ope instanceof ObjectProperty)) + throw new ReasoningMethodUnsupportedException("Instance check for description " + description + " unsupported. Inverse object properties not supported."); + ObjectProperty op = (ObjectProperty) ope; + Description child = description.getChild(0); + Map<Individual,SortedSet<Individual>> mapping = opPos.get(op);; + if(mapping == null) { + logger.warn("Instance check of a description with an undefinied property (" + op + ")."); + return true; + } + SortedSet<Individual> roleFillers = opPos.get(op).get(individual); + if(roleFillers == null) + return true; + for(Individual roleFiller : roleFillers) { + if(!instanceCheck(child, roleFiller)) + return false; + } + return true; + } + + throw new ReasoningMethodUnsupportedException("Instance check for description " + description + " unsupported."); + } + /* (non-Javadoc) * @see org.dllearner.core.Reasoner#getAtomicConcepts() */ @@ -146,24 +239,62 @@ * @see org.dllearner.core.Reasoner#getReasonerType() */ public ReasonerType getReasonerType() { - // TODO Auto-generated method stub - return null; + return ReasonerType.FAST_INSTANCE_CHECKER; } /* (non-Javadoc) * @see org.dllearner.core.Reasoner#prepareSubsumptionHierarchy(java.util.Set) */ public void prepareSubsumptionHierarchy(Set<NamedClass> allowedConcepts) { - // TODO Auto-generated method stub + rs.prepareSubsumptionHierarchy(); + } + @Override + public SubsumptionHierarchy getSubsumptionHierarchy() { + return rs.getSubsumptionHierarchy(); + } + + @Override + public void prepareRoleHierarchy(Set<ObjectProperty> allowedRoles) { + rs.prepareRoleHierarchy(allowedRoles); + } + + @Override + public ObjectPropertyHierarchy getRoleHierarchy() { + return rs.getRoleHierarchy(); } - + + @Override + public boolean subsumes(Description superConcept, Description subConcept) { +// Negation neg = new Negation(subConcept); +// Intersection c = new Intersection(neg,superConcept); +// return fastRetrieval.calculateSets(c).getPosSet().isEmpty(); + return rs.subsumes(superConcept, subConcept); + } + /** - * @param args + * Test method for fast instance checker. + * @param args No arguments supported. + * @throws ComponentInitException + * @throws ParseException + * @throws ReasoningMethodUnsupportedException */ - public static void main(String[] args) { - // TODO Auto-generated method stub - + public static void main(String[] args) throws ComponentInitException, ParseException, ReasoningMethodUnsupportedException { + ComponentManager cm = ComponentManager.getInstance(); + OWLFile owl = cm.knowledgeSource(OWLFile.class); + String owlFile = new File("examples/family/father.owl").toURI().toString(); + cm.applyConfigEntry(owl, "url", owlFile); + owl.init(); + ReasonerComponent reasoner = cm.reasoner(FastInstanceChecker.class, owl); + cm.reasoningService(reasoner); + reasoner.init(); + + KBParser.internalNamespace = "http://example.com/father#"; + String query = "(male AND EXISTS hasChild.TOP)"; + Description d = KBParser.parseConcept(query); + System.out.println(d); + Individual i = new Individual("http://example.com/father#markus"); + System.out.println(reasoner.instanceCheck(d, i)); } } Modified: trunk/src/dl-learner/org/dllearner/reasoning/FastRetrievalReasoner.java =================================================================== --- trunk/src/dl-learner/org/dllearner/reasoning/FastRetrievalReasoner.java 2008-02-22 12:50:11 UTC (rev 625) +++ trunk/src/dl-learner/org/dllearner/reasoning/FastRetrievalReasoner.java 2008-02-22 15:16:02 UTC (rev 626) @@ -114,9 +114,10 @@ // C \sqsubseteq D is rewritten to a retrieval for \not C \sqcap D @Override public boolean subsumes(Description superConcept, Description subConcept) { - Negation neg = new Negation(subConcept); - Intersection c = new Intersection(neg,superConcept); - return fastRetrieval.calculateSets(c).getPosSet().isEmpty(); +// Negation neg = new Negation(subConcept); +// Intersection c = new Intersection(neg,superConcept); +// return fastRetrieval.calculateSets(c).getPosSet().isEmpty(); + return rs.subsumes(superConcept, subConcept); } @Override Modified: trunk/src/dl-learner/org/dllearner/reasoning/ReasonerType.java =================================================================== --- trunk/src/dl-learner/org/dllearner/reasoning/ReasonerType.java 2008-02-22 12:50:11 UTC (rev 625) +++ trunk/src/dl-learner/org/dllearner/reasoning/ReasonerType.java 2008-02-22 15:16:02 UTC (rev 626) @@ -4,5 +4,5 @@ package org.dllearner.reasoning; public enum ReasonerType { - KAON2, DIG, FAST_RETRIEVAL, FACT, PELLET + KAON2, DIG, FAST_RETRIEVAL, FACT, PELLET, FAST_INSTANCE_CHECKER } \ No newline at end of file Modified: trunk/src/dl-learner/org/dllearner/test/junit/ReasonerTests.java =================================================================== --- trunk/src/dl-learner/org/dllearner/test/junit/ReasonerTests.java 2008-02-22 12:50:11 UTC (rev 625) +++ trunk/src/dl-learner/org/dllearner/test/junit/ReasonerTests.java 2008-02-22 15:16:02 UTC (rev 626) @@ -88,7 +88,12 @@ for (Class<? extends ReasonerComponent> reasonerClass : reasonerClasses) { ReasonerComponent reasoner = cm.reasoner(reasonerClass, ks); reasoner.init(); - boolean result = reasoner.instanceCheck(d, i); +// long startTime = System.nanoTime(); + boolean result = false; +// for(int n=0; n<10000; n++) { + result = reasoner.instanceCheck(d, i); +// } +// long time = System.nanoTime() - startTime; logger.debug("instance check: " + reasoner + " " + d + " " + i + " " + result); assertTrue(result); } This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |