Menu
▾
▴
[DL-Learner SVN] SF.net SVN: dl-learner: [418] trunk
|
From: <jen...@us...> - 2008-01-23 12:05:50
|
Revision: 418
http://dl-learner.svn.sourceforge.net/dl-learner/?rev=418&view=rev
Author: jenslehmann
Date: 2008-01-23 04:05:44 -0800 (Wed, 23 Jan 2008)
Log Message:
-----------
Started new learning algorithm implementation, based on the refinement operator approach, to test various ideas for improvements. In particular, the goal will be to use more knowledge about the specific examples in the algorithm run.
[algorithm is not working yet]
Modified Paths:
--------------
trunk/lib/components.ini
trunk/src/dl-learner/org/dllearner/cli/Start.java
Added Paths:
-----------
trunk/src/dl-learner/org/dllearner/algorithms/refexamples/
trunk/src/dl-learner/org/dllearner/algorithms/refexamples/ExampleBasedHeuristic.java
trunk/src/dl-learner/org/dllearner/algorithms/refexamples/ExampleBasedNode.java
trunk/src/dl-learner/org/dllearner/algorithms/refexamples/ExampleBasedROComponent.java
trunk/src/dl-learner/org/dllearner/algorithms/refexamples/ExampleBasedROLearner.java
trunk/src/dl-learner/org/dllearner/algorithms/refexamples/FlexibleHeuristic.java
trunk/src/dl-learner/org/dllearner/algorithms/refexamples/LexicographicHeuristic.java
trunk/src/dl-learner/org/dllearner/algorithms/refexamples/NodeComparatorStable.java
trunk/src/dl-learner/org/dllearner/algorithms/refexamples/package.html
Modified: trunk/lib/components.ini
===================================================================
--- trunk/lib/components.ini 2008-01-23 11:15:31 UTC (rev 417)
+++ trunk/lib/components.ini 2008-01-23 12:05:44 UTC (rev 418)
@@ -17,4 +17,4 @@
org.dllearner.algorithms.RandomGuesser
org.dllearner.algorithms.BruteForceLearner
org.dllearner.algorithms.refinement.ROLearner
-org.dllearner.algorithms.gp.GP
+org.dllearner.algorithms.refinement2.ExampleBasedROLearnerComponent
\ No newline at end of file
Added: trunk/src/dl-learner/org/dllearner/algorithms/refexamples/ExampleBasedHeuristic.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/algorithms/refexamples/ExampleBasedHeuristic.java (rev 0)
+++ trunk/src/dl-learner/org/dllearner/algorithms/refexamples/ExampleBasedHeuristic.java 2008-01-23 12:05:44 UTC (rev 418)
@@ -0,0 +1,35 @@
+/**
+ * Copyright (C) 2007-2008, 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.algorithms.refexamples;
+
+import java.util.Comparator;
+
+/**
+ * Marker interface for heuristics in the refinement operator
+ * based learning approach. A heuristic implements a method
+ * to decide which one of two given nodes seems to be more
+ * promising with respect to the learning problem we consider.
+ *
+ * @author Jens Lehmann
+ *
+ */
+public interface ExampleBasedHeuristic extends Comparator<ExampleBasedNode>{
+
+}
Added: trunk/src/dl-learner/org/dllearner/algorithms/refexamples/ExampleBasedNode.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/algorithms/refexamples/ExampleBasedNode.java (rev 0)
+++ trunk/src/dl-learner/org/dllearner/algorithms/refexamples/ExampleBasedNode.java 2008-01-23 12:05:44 UTC (rev 418)
@@ -0,0 +1,194 @@
+/**
+ * Copyright (C) 2007-2008, 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.algorithms.refexamples;
+
+import java.util.Set;
+import java.util.TreeSet;
+
+import org.dllearner.core.dl.Concept;
+import org.dllearner.core.dl.Individual;
+import org.dllearner.utilities.ConceptComparator;
+
+/**
+ *
+ * Represents a node in the search tree. A node consists of
+ * the following parts:
+ *
+ * ... (see paper) ...
+ *
+ * @author Jens Lehmann
+ *
+ */
+public class ExampleBasedNode {
+
+ // TODO: add example based variables here
+ @SuppressWarnings({"unused"})
+ private Set<Individual> coveredPositives;
+
+ // TOP ist einfach das TOP-Konzept, also das einzige welches nicht evaluiert wird
+ public enum QualityEvaluationMethod { TOP, REASONER, TOO_WEAK_LIST, OVERLY_GENERAL_LIST };
+
+ private QualityEvaluationMethod qualityEvaluationMethod = QualityEvaluationMethod.TOP;
+
+ // alle Eigenschaften eines Knotens im Suchbaum
+ private Concept concept;
+ private int horizontalExpansion;
+ private int coveredNegativeExamples;
+ private boolean isTooWeak;
+ private boolean isQualityEvaluated;
+ private boolean isRedundant;
+
+ private static ConceptComparator conceptComparator = new ConceptComparator();
+ private static NodeComparatorStable nodeComparator = new NodeComparatorStable();
+
+ // Einbettung in Suchbaum
+ private ExampleBasedNode parent = null;
+ // private Set<Node> children = new HashSet<Node>();
+ private Set<ExampleBasedNode> children = new TreeSet<ExampleBasedNode>(nodeComparator);
+ // es wird auch eine Liste von Kindern gehalten
+ private Set<Concept> childConcepts = new TreeSet<Concept>(conceptComparator);
+
+ // verwendeter Operator für Expansion des Knotens
+ // private RefinementOperator operator;
+
+ public ExampleBasedNode(Concept concept) {
+ this.concept = concept;
+ horizontalExpansion = 0;
+ isQualityEvaluated = false;
+ }
+
+ public void setCoveredNegativeExamples(int coveredNegativeExamples) {
+ if(isQualityEvaluated)
+ throw new RuntimeException("Cannot set quality of a node more than once.");
+ this.coveredNegativeExamples = coveredNegativeExamples;
+ isQualityEvaluated = true;
+ }
+
+ public void setHorizontalExpansion(int horizontalExpansion) {
+ this.horizontalExpansion = horizontalExpansion;
+ }
+
+ public void setRedundant(boolean isRedundant) {
+ this.isRedundant = isRedundant;
+ }
+
+ public void setTooWeak(boolean isTooWeak) {
+ if(isQualityEvaluated)
+ throw new RuntimeException("Cannot set quality of a node more than once.");
+ this.isTooWeak = isTooWeak;
+ isQualityEvaluated = true;
+ }
+
+ public boolean addChild(ExampleBasedNode child) {
+ // child.setParent(this);
+ child.parent = this;
+ childConcepts.add(child.concept);
+ return children.add(child);
+ }
+
+ public Concept getConcept() {
+ return concept;
+ }
+ public int getCoveredNegativeExamples() {
+ return coveredNegativeExamples;
+ }
+ public int getHorizontalExpansion() {
+ return horizontalExpansion;
+ }
+ public boolean isQualityEvaluated() {
+ return isQualityEvaluated;
+ }
+ public boolean isRedundant() {
+ return isRedundant;
+ }
+ public boolean isTooWeak() {
+ return isTooWeak;
+ }
+
+ @Override
+ public String toString() {
+ String ret = concept.toString() + " [q:";
+ if(isTooWeak)
+ ret += "tw";
+ else
+ ret += coveredNegativeExamples;
+ ret += ", he:" + horizontalExpansion + ", children:" + children.size() + "]";
+ return ret;
+ }
+
+ // gibt die Refinement-Chain zurück, die zu dem Knoten geführt hat
+ public String getRefinementChainString() {
+ if(parent!=null) {
+ String ret = parent.getRefinementChainString();
+ ret += " => " + concept.toString();
+ return ret;
+ } else {
+ return concept.toString();
+ }
+ }
+
+ public String getTreeString() {
+ return getTreeString(0).toString();
+ }
+
+ private StringBuilder getTreeString(int depth) {
+ StringBuilder treeString = new StringBuilder();
+ for(int i=0; i<depth-1; i++)
+ treeString.append(" ");
+ if(depth!=0)
+ // treeString.append("|-→ ");
+ treeString.append("|--> ");
+ treeString.append(getShortDescription()+"\n");
+ for(ExampleBasedNode child : children) {
+ treeString.append(child.getTreeString(depth+1));
+ }
+ return treeString;
+ }
+
+ private String getShortDescription() {
+ String ret = concept.toString() + " [q:";
+
+ if(isTooWeak)
+ ret += "tw";
+ else
+ ret += coveredNegativeExamples;
+
+ ret += " ("+qualityEvaluationMethod+"), he:" + horizontalExpansion + "]";
+ return ret;
+ }
+
+ public Set<ExampleBasedNode> getChildren() {
+ return children;
+ }
+
+ public Set<Concept> getChildConcepts() {
+ return childConcepts;
+ }
+
+ public QualityEvaluationMethod getQualityEvaluationMethod() {
+ return qualityEvaluationMethod;
+ }
+
+ public void setQualityEvaluationMethod(QualityEvaluationMethod qualityEvaluationMethod) {
+ this.qualityEvaluationMethod = qualityEvaluationMethod;
+ }
+
+}
Added: trunk/src/dl-learner/org/dllearner/algorithms/refexamples/ExampleBasedROComponent.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/algorithms/refexamples/ExampleBasedROComponent.java (rev 0)
+++ trunk/src/dl-learner/org/dllearner/algorithms/refexamples/ExampleBasedROComponent.java 2008-01-23 12:05:44 UTC (rev 418)
@@ -0,0 +1,325 @@
+/**
+ * Copyright (C) 2007-2008, 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.algorithms.refexamples;
+
+import java.io.File;
+import java.util.Collection;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Set;
+
+import org.dllearner.algorithms.refinement.RhoDown;
+import org.dllearner.core.LearningAlgorithm;
+import org.dllearner.core.LearningProblem;
+import org.dllearner.core.ReasoningService;
+import org.dllearner.core.Score;
+import org.dllearner.core.config.BooleanConfigOption;
+import org.dllearner.core.config.CommonConfigMappings;
+import org.dllearner.core.config.CommonConfigOptions;
+import org.dllearner.core.config.ConfigEntry;
+import org.dllearner.core.config.ConfigOption;
+import org.dllearner.core.config.DoubleConfigOption;
+import org.dllearner.core.config.InvalidConfigOptionValueException;
+import org.dllearner.core.config.StringConfigOption;
+import org.dllearner.core.dl.AtomicConcept;
+import org.dllearner.core.dl.AtomicRole;
+import org.dllearner.core.dl.Concept;
+import org.dllearner.learningproblems.PosNegLP;
+import org.dllearner.learningproblems.PosOnlyDefinitionLP;
+import org.dllearner.utilities.Files;
+import org.dllearner.utilities.Helper;
+
+/**
+ * The DL-Learner learning algorithm component for the example
+ * based refinement operator approach. It handles all
+ * configuration options, creates the corresponding objects and
+ * passes them to the actual refinement operator, heuristic, and
+ * learning algorithm implementations.
+ *
+ * Note: The component is not working yet.
+ *
+ * Note: The options supported by the ROLearner component and this
+ * one are not equal. Options that have been dropped for now:
+ * - horizontal expansion factor: The goal of the algorithm will
+ * be to (hopefully) be able to learn long and complex concepts
+ * more efficiently.
+ * A horizontal expansion factor has its benefits, but limits
+ * the length of concepts learnable in reasonable time to
+ * about 15 with its default value of 0.6 and a small sized
+ * background knowledge base. We hope to get more fine-grained
+ * control of whether it makes sense to extend a node with
+ * more sophisticated heuristics.
+ * Dropping the horizontal expansion factor means that the
+ * completeness of the algorithm depends on the heuristic.
+ *
+ * @author Jens Lehmann
+ *
+ */
+public class ExampleBasedROComponent extends LearningAlgorithm {
+
+ // actual algorithm
+ private ExampleBasedROLearner algorithm;
+
+ // learning problem to solve and background knowledge
+ private ReasoningService rs;
+ private LearningProblem learningProblem;
+
+ // configuration options
+ private boolean writeSearchTree;
+ private File searchTreeFile;
+ private boolean replaceSearchTree = false;
+ private static String defaultSearchTreeFile = "log/searchTree.txt";
+ private String heuristic = "lexicographic";
+ Set<AtomicConcept> allowedConcepts;
+ Set<AtomicRole> allowedRoles;
+ Set<AtomicConcept> ignoredConcepts;
+ Set<AtomicRole> ignoredRoles;
+ // these are computed as the result of the previous four settings
+ Set<AtomicConcept> usedConcepts;
+ Set<AtomicRole> usedRoles;
+ private boolean applyAllFilter = true;
+ private boolean applyExistsFilter = true;
+ private boolean useTooWeakList = true;
+ private boolean useOverlyGeneralList = true;
+ private boolean useShortConceptConstruction = true;
+ private boolean improveSubsumptionHierarchy = true;
+ private boolean useAllConstructor = true;
+ private boolean useExistsConstructor = true;
+ private boolean useNegation = true;
+
+ // Variablen zur Einstellung der Protokollierung
+ // boolean quiet = false;
+ boolean showBenchmarkInformation = false;
+ // boolean createTreeString = false;
+ // String searchTree = new String();
+
+ // Konfiguration des Algorithmus
+ // Faktor für horizontale Erweiterung (notwendig für completeness)
+ // double horizontalExpansionFactor = 0.6;
+
+ // soll später einen Operator und eine Heuristik entgegennehmen
+ // public ROLearner(LearningProblem learningProblem, LearningProblem learningProblem2) {
+ public ExampleBasedROComponent(PosNegLP learningProblem, ReasoningService rs) {
+ this.learningProblem = learningProblem;
+ this.rs = rs;
+ }
+
+ public ExampleBasedROComponent(PosOnlyDefinitionLP learningProblem, ReasoningService rs) {
+ this.learningProblem = learningProblem;
+ this.rs = rs;
+ }
+
+ public static Collection<Class<? extends LearningProblem>> supportedLearningProblems() {
+ Collection<Class<? extends LearningProblem>> problems = new LinkedList<Class<? extends LearningProblem>>();
+ problems.add(PosNegLP.class);
+ problems.add(PosOnlyDefinitionLP.class);
+ return problems;
+ }
+
+ public static Collection<ConfigOption<?>> createConfigOptions() {
+ Collection<ConfigOption<?>> options = new LinkedList<ConfigOption<?>>();
+ options.add(new BooleanConfigOption("writeSearchTree", "specifies whether to write a search tree", false));
+ options.add(new StringConfigOption("searchTreeFile","file to use for the search tree", defaultSearchTreeFile));
+ options.add(new BooleanConfigOption("replaceSearchTree","specifies whether to replace the search tree in the log file after each run or append the new search tree", false));
+ StringConfigOption heuristicOption = new StringConfigOption("heuristic", "specifiy the heuristic to use", "lexicographic");
+ heuristicOption.setAllowedValues(new String[] {"lexicographic", "flexible"});
+ options.add(heuristicOption);
+ options.add(new BooleanConfigOption("applyAllFilter", "usage of equivalence ALL R.C AND ALL R.D = ALL R.(C AND D)", true));
+ options.add(new BooleanConfigOption("applyExistsFilter", "usage of equivalence EXISTS R.C OR EXISTS R.D = EXISTS R.(C OR D)", true));
+ options.add(new BooleanConfigOption("useTooWeakList", "try to filter out too weak concepts without sending them to the reasoner", true));
+ options.add(new BooleanConfigOption("useOverlyGeneralList", "try to find overly general concept without sending them to the reasoner", true));
+ options.add(new BooleanConfigOption("useShortConceptConstruction", "shorten concept to see whether they already exist", true));
+ DoubleConfigOption horizExp = new DoubleConfigOption("horizontalExpansionFactor", "horizontal expansion factor (see publication for description)", 0.6);
+ horizExp.setLowerLimit(0.0);
+ horizExp.setUpperLimit(1.0);
+ options.add(horizExp);
+ options.add(new BooleanConfigOption("improveSubsumptionHierarchy", "simplify subsumption hierarchy to reduce search space (see publication for description)", true));
+ // allowed/ignored concepts/roles could also be a reasoner option (?)
+ options.add(CommonConfigOptions.allowedConcepts());
+ options.add(CommonConfigOptions.ignoredConcepts());
+ options.add(CommonConfigOptions.allowedRoles());
+ options.add(CommonConfigOptions.ignoredRoles());
+ options.add(CommonConfigOptions.useAllConstructor());
+ options.add(CommonConfigOptions.useExistsConstructor());
+ options.add(CommonConfigOptions.useNegation());
+ return options;
+ }
+
+ /* (non-Javadoc)
+ * @see org.dllearner.core.Component#applyConfigEntry(org.dllearner.core.ConfigEntry)
+ */
+ @Override
+ @SuppressWarnings({"unchecked"})
+ public <T> void applyConfigEntry(ConfigEntry<T> entry) throws InvalidConfigOptionValueException {
+ String name = entry.getOptionName();
+ if(name.equals("writeSearchTree"))
+ writeSearchTree = (Boolean) entry.getValue();
+ else if(name.equals("searchTreeFile"))
+ searchTreeFile = new File((String)entry.getValue());
+ else if(name.equals("replaceSearchTree"))
+ replaceSearchTree = (Boolean) entry.getValue();
+ else if(name.equals("heuristic")) {
+ String value = (String) entry.getValue();
+ if(value.equals("lexicographic"))
+ heuristic = "lexicographic";
+ else
+ heuristic = "flexible";
+ } else if(name.equals("allowedConcepts")) {
+ allowedConcepts = CommonConfigMappings.getAtomicConceptSet((Set<String>)entry.getValue());
+ } else if(name.equals("allowedRoles")) {
+ allowedRoles = CommonConfigMappings.getAtomicRoleSet((Set<String>)entry.getValue());
+ } else if(name.equals("ignoredConcepts")) {
+ ignoredConcepts = CommonConfigMappings.getAtomicConceptSet((Set<String>)entry.getValue());
+ } else if(name.equals("ignoredRoles")) {
+ ignoredRoles = CommonConfigMappings.getAtomicRoleSet((Set<String>)entry.getValue());
+ } else if(name.equals("applyAllFilter")) {
+ applyAllFilter = (Boolean) entry.getValue();
+ } else if(name.equals("applyExistsFilter")) {
+ applyExistsFilter = (Boolean) entry.getValue();
+ } else if(name.equals("useTooWeakList")) {
+ useTooWeakList = (Boolean) entry.getValue();
+ } else if(name.equals("useOverlyGeneralList")) {
+ useOverlyGeneralList = (Boolean) entry.getValue();
+ } else if(name.equals("useShortConceptConstruction")) {
+ useShortConceptConstruction = (Boolean) entry.getValue();
+ } else if(name.equals("improveSubsumptionHierarchy")) {
+ improveSubsumptionHierarchy = (Boolean) entry.getValue();
+ } else if(name.equals("useAllConstructor")) {
+ useAllConstructor = (Boolean) entry.getValue();
+ } else if(name.equals("useExistsConstructor")) {
+ useExistsConstructor = (Boolean) entry.getValue();
+ } else if(name.equals("useNegation")) {
+ useNegation = (Boolean) entry.getValue();
+ }
+
+ }
+
+ /* (non-Javadoc)
+ * @see org.dllearner.core.Component#init()
+ */
+ @Override
+ public void init() {
+ if(searchTreeFile == null)
+ searchTreeFile = new File(defaultSearchTreeFile);
+
+ if(writeSearchTree)
+ Files.clearFile(searchTreeFile);
+
+ // adjust heuristic
+ ExampleBasedHeuristic algHeuristic;
+
+ if(heuristic == "lexicographic")
+ algHeuristic = new LexicographicHeuristic();
+ else {
+ if(learningProblem instanceof PosOnlyDefinitionLP) {
+ throw new RuntimeException("does not work with positive examples only yet");
+ }
+ algHeuristic = null;
+ // algHeuristic = new FlexibleHeuristic(learningProblem.getNegativeExamples().size(), learningProblem.getPercentPerLengthUnit());
+ }
+
+ // compute used concepts/roles from allowed/ignored
+ // concepts/roles
+ if(allowedConcepts != null) {
+ // sanity check to control if no non-existing concepts are in the list
+ Helper.checkConcepts(rs, allowedConcepts);
+ usedConcepts = allowedConcepts;
+ } else if(ignoredConcepts != null) {
+ usedConcepts = Helper.computeConceptsUsingIgnoreList(rs, ignoredConcepts);
+ } else {
+ usedConcepts = Helper.computeConcepts(rs);
+ }
+
+ if(allowedRoles != null) {
+ Helper.checkRoles(rs, allowedRoles);
+ usedRoles = allowedRoles;
+ } else if(ignoredRoles != null) {
+ Helper.checkRoles(rs, ignoredRoles);
+ usedRoles = Helper.difference(rs.getAtomicRoles(), ignoredRoles);
+ } else {
+ usedRoles = rs.getAtomicRoles();
+ }
+
+ // prepare subsumption and role hierarchies, because they are needed
+ // during the run of the algorithm
+ rs.prepareSubsumptionHierarchy(usedConcepts);
+ if(improveSubsumptionHierarchy)
+ rs.getSubsumptionHierarchy().improveSubsumptionHierarchy();
+ rs.prepareRoleHierarchy(usedRoles);
+
+ // create a refinement operator and pass all configuration
+ // variables to it
+ RhoDown operator = new RhoDown(
+ rs,
+ applyAllFilter,
+ applyExistsFilter,
+ useAllConstructor,
+ useExistsConstructor,
+ useNegation
+ );
+
+ // create an algorithm object and pass all configuration
+ // options to it
+ algorithm = new ExampleBasedROLearner(
+ learningProblem,
+ operator,
+ algHeuristic,
+ usedConcepts,
+ usedRoles,
+ writeSearchTree,
+ replaceSearchTree,
+ searchTreeFile,
+ useTooWeakList,
+ useOverlyGeneralList,
+ useShortConceptConstruction
+ );
+ }
+
+ public static String getName() {
+ return "example driven refinement operator based learning algorithm [not working]";
+ }
+
+ @Override
+ public void start() {
+ algorithm.start();
+ }
+
+ @Override
+ public Score getSolutionScore() {
+ return algorithm.getSolutionScore();
+ }
+
+ @Override
+ public Concept getBestSolution() {
+ return algorithm.getBestSolution();
+ }
+
+ @Override
+ public synchronized List<Concept> getBestSolutions(int nrOfSolutions) {
+ return algorithm.getBestSolutions(nrOfSolutions);
+ }
+
+ @Override
+ public void stop() {
+ algorithm.stop();
+ }
+
+}
Added: trunk/src/dl-learner/org/dllearner/algorithms/refexamples/ExampleBasedROLearner.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/algorithms/refexamples/ExampleBasedROLearner.java (rev 0)
+++ trunk/src/dl-learner/org/dllearner/algorithms/refexamples/ExampleBasedROLearner.java 2008-01-23 12:05:44 UTC (rev 418)
@@ -0,0 +1,839 @@
+/**
+ * Copyright (C) 2007-2008, 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.algorithms.refexamples;
+
+import java.io.File;
+import java.text.DecimalFormat;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Set;
+import java.util.SortedSet;
+import java.util.TreeSet;
+
+import org.dllearner.algorithms.refinement.RefinementOperator;
+import org.dllearner.algorithms.refinement.RhoDown;
+import org.dllearner.core.LearningProblem;
+import org.dllearner.core.ReasoningService;
+import org.dllearner.core.Score;
+import org.dllearner.core.dl.AtomicConcept;
+import org.dllearner.core.dl.AtomicRole;
+import org.dllearner.core.dl.Concept;
+import org.dllearner.core.dl.MultiConjunction;
+import org.dllearner.core.dl.MultiDisjunction;
+import org.dllearner.core.dl.Top;
+import org.dllearner.learningproblems.PosNegLP;
+import org.dllearner.learningproblems.PosOnlyDefinitionLP;
+import org.dllearner.utilities.ConceptComparator;
+import org.dllearner.utilities.ConceptTransformation;
+import org.dllearner.utilities.Files;
+import org.dllearner.utilities.Helper;
+
+/**
+ * Implements the example based refinement operator learning
+ * approach.
+ *
+ * @author Jens Lehmann
+ *
+ */
+public class ExampleBasedROLearner {
+
+ // all configuration options, which were passed to the
+ // learning algorithms
+ private boolean writeSearchTree;
+ private File searchTreeFile;
+ private boolean replaceSearchTree = false;
+ Set<AtomicConcept> allowedConcepts;
+ Set<AtomicRole> allowedRoles;
+ Set<AtomicConcept> ignoredConcepts;
+ Set<AtomicRole> ignoredRoles;
+ // these are computed as the result of the previous four settings
+ Set<AtomicConcept> usedConcepts;
+ Set<AtomicRole> usedRoles;
+
+ private boolean useTooWeakList = true;
+ private boolean useOverlyGeneralList = true;
+ private boolean useShortConceptConstruction = true;
+ private double horizontalExpansionFactor = 0.6;
+
+
+ private boolean quiet = false;
+
+ private boolean stop = false;
+
+ private ReasoningService rs;
+
+ private PosNegLP learningProblem;
+ private PosOnlyDefinitionLP posOnlyLearningProblem;
+ private boolean posOnly = false;
+
+ // non-configuration variables
+
+ // Lösungen protokollieren
+ boolean solutionFound = false;
+ List<Concept> solutions = new LinkedList<Concept>();
+
+ // verwendeter Refinement-Operator (momentan werden für Statistik RhoDown-spezifische
+ // Sachen abgefragt)
+ // RefinementOperator operator;
+ RhoDown operator;
+
+ // Variablen zur Einstellung der Protokollierung
+ // boolean quiet = false;
+ boolean showBenchmarkInformation = false;
+ // boolean createTreeString = false;
+ // String searchTree = new String();
+
+ // Konfiguration des Algorithmus
+ // Faktor für horizontale Erweiterung (notwendig für completeness)
+ // double horizontalExpansionFactor = 0.6;
+
+
+
+ private Comparator<ExampleBasedNode> nodeComparator;
+ private NodeComparatorStable nodeComparatorStable = new NodeComparatorStable();
+ private ConceptComparator conceptComparator = new ConceptComparator();
+ DecimalFormat df = new DecimalFormat();
+
+ // Menge von Kandidaten für Refinement
+ // (wird für Direktzugriff auf Baumknoten verwendet)
+ private TreeSet<ExampleBasedNode> candidates;
+ // während eines Durchlaufs neu gefundene Knoten
+ private List<ExampleBasedNode> newCandidates = new LinkedList<ExampleBasedNode>();
+ // stabiles candidate set, da sich die Knoten nach dem einfügen nicht
+ // verschieben können => das Set enthält nicht die aktuellen horizontal
+ // expansions, es dient nur dazu die besten Konzepte zu speichern; hat also
+ // keine Funktion im Algorithmus
+ private TreeSet<ExampleBasedNode> candidatesStable = new TreeSet<ExampleBasedNode>(nodeComparatorStable);
+ // vorhandene Konzepte, die irgendwann als proper eingestuft worden
+ private SortedSet<Concept> properRefinements = new TreeSet<Concept>(conceptComparator);
+ // speichert Konzept und deren Evaluierung, um sie leicht wiederzufinden für
+ // Strategien wie Konzeptverkürzung etc.
+ // Zahl = covered negatives, -1 = too weak
+ // private Map<Concept, Integer> evaluationCache = new TreeMap<Concept, Integer>(conceptComparator);
+ // Blacklists
+ private SortedSet<Concept> tooWeakList = new TreeSet<Concept>(conceptComparator);
+ private SortedSet<Concept> overlyGeneralList = new TreeSet<Concept>(conceptComparator);
+
+ TreeSet<ExampleBasedNode> expandedNodes = new TreeSet<ExampleBasedNode>(nodeComparatorStable);
+
+ // statistische Variablen
+ private int maxRecDepth = 0;
+ private int maxNrOfRefinements = 0;
+ private int maxNrOfChildren = 0;
+ private int redundantConcepts = 0;
+ int maximumHorizontalExpansion;
+ int minimumHorizontalExpansion;
+ // private int propernessTests = 0;
+ private int propernessTestsReasoner = 0;
+ private int propernessTestsAvoidedByShortConceptConstruction = 0;
+ private int propernessTestsAvoidedByTooWeakList = 0;
+ private int conceptTestsTooWeakList = 0;
+ private int conceptTestsOverlyGeneralList = 0;
+ private int conceptTestsReasoner = 0;
+
+ // Zeitvariablen
+ private long algorithmStartTime;
+ private long propernessCalcTimeNs = 0;
+ private long propernessCalcReasoningTimeNs = 0;
+ private long childConceptsDeletionTimeNs = 0;
+ private long refinementCalcTimeNs = 0;
+ private long redundancyCheckTimeNs = 0;
+ private long evaluateSetCreationTimeNs = 0;
+ private long improperConceptsRemovalTimeNs = 0;
+ long someTimeNs = 0;
+ int someCount = 0;
+
+ public ExampleBasedROLearner(
+ LearningProblem learningProblem,
+ RefinementOperator operator,
+ ExampleBasedHeuristic heuristic,
+ Set<AtomicConcept> allowedConcepts,
+ Set<AtomicRole> allowedRoles,
+ boolean writeSearchTree,
+ boolean replaceSearchTree,
+ File searchTreeFile,
+ boolean useTooWeakList,
+ boolean useOverlyGeneralList,
+ boolean useShortConceptConstruction
+ ) {
+ if(learningProblem instanceof PosNegLP) {
+ this.learningProblem = (PosNegLP) learningProblem;
+ posOnly = false;
+ } else if(learningProblem instanceof PosOnlyDefinitionLP) {
+ this.posOnlyLearningProblem = (PosOnlyDefinitionLP) learningProblem;
+ posOnly = true;
+ }
+
+ // candidate sets entsprechend der gewählten Heuristik initialisieren
+ candidates = new TreeSet<ExampleBasedNode>(nodeComparator);
+ // newCandidates = new TreeSet<Node>(nodeComparator);
+ }
+
+ public void start() {
+ // Suche wird mit Top-Konzept gestartet
+ Top top = new Top();
+ ExampleBasedNode topNode = new ExampleBasedNode(top);
+ // int coveredNegativeExamples = learningProblem.coveredNegativeExamplesOrTooWeak(top);
+ // aus Top folgen immer alle negativen Beispiele, d.h. es ist nur eine Lösung, wenn
+ // es keine negativen Beispiele gibt
+ int coveredNegativeExamples = getNumberOfNegatives();
+ topNode.setCoveredNegativeExamples(coveredNegativeExamples);
+ // topNode.setHorizontalExpansion(1); // die 0 ist eigentlich richtig, da keine Refinements
+ // der Länge 1 untersucht wurden
+ candidates.add(topNode);
+ candidatesStable.add(topNode);
+ // Abbruchvariable => beachten, dass bereits TOP eine Lösung sein kann
+ solutionFound = (coveredNegativeExamples == 0);
+ solutions = new LinkedList<Concept>();
+ if(solutionFound)
+ solutions.add(top);
+
+ int loop = 0;
+
+ // Voreinstellung für horizontal expansion
+ maximumHorizontalExpansion = 0;
+ minimumHorizontalExpansion = 0;
+
+ algorithmStartTime = System.nanoTime();
+
+ // TODO: effizienter Traversal der Subsumption-Hierarchie
+ // TODO: Äquivalenzen nutzen
+ // TODO: Gibt es auch eine andere Abbruchbedingung? Es könnte sein, dass irgendwann keine
+ // proper refinements mehr gefunden werden, aber wie stelle man das fest?
+ while(!solutionFound && !stop) {
+
+ if(!quiet)
+ printStatistics(false);
+
+ // besten Knoten nach Heuristik auswählen
+ ExampleBasedNode bestNode = candidates.last();
+ // besten Knoten erweitern
+ // newCandidates = new TreeSet<Node>(nodeComparator);
+ newCandidates.clear();
+ candidates.remove(bestNode);
+ extendNodeProper(bestNode, bestNode.getHorizontalExpansion()+1);
+ candidates.add(bestNode);
+ candidates.addAll(newCandidates);
+ candidatesStable.addAll(newCandidates);
+
+ // minimum horizontal expansion berechnen
+ if(bestNode.getHorizontalExpansion()>maximumHorizontalExpansion)
+ maximumHorizontalExpansion = bestNode.getHorizontalExpansion();
+ minimumHorizontalExpansion = (int) Math.floor(horizontalExpansionFactor*maximumHorizontalExpansion);
+
+ // neu: es werden solange Knoten erweitert bis wirklich jeder Knoten die
+ // notwendige minimum horizontal expansion hat
+ boolean nodesExpanded;
+ do {
+ nodesExpanded = false;
+
+
+ // es darf nicht candidatesStable geklont werden, da diese Menge nicht
+ // aktualisiert wird, also die falschen horizontal expansions vorliegen
+ // TODO: bei Tests war die Performance der clone-Operation ganz gut, aber
+ // es skaliert natürlich nicht so gut mit größer werdenden candidate set
+ // => Lösung ist vielleicht einfach einen Iterator zu verwenden und das
+ // aktuelle Konzept gleich hier zu löschen (wird dann bei expansion wieder
+ // hinzugefügt)
+ // TreeSet<Node> candidatesClone = (TreeSet<Node>) candidates.clone();
+ newCandidates.clear();
+
+
+ // for(Node candidate : candidatesClone) {
+ Iterator<ExampleBasedNode> it = candidates.iterator();
+ List<ExampleBasedNode> changedNodes = new LinkedList<ExampleBasedNode>();
+ while(it.hasNext()){
+ ExampleBasedNode candidate = it.next();
+ // alle Kandidaten, die nicht too weak sind und unter minimumHorizontalExpansion
+ // liegen, werden erweitert
+ if(!candidate.isTooWeak() && candidate.getHorizontalExpansion()<minimumHorizontalExpansion) {
+ // Vorsicht, falls candidates irgendwann in extendProper benutzt
+ // werden sollten! Es könnten auf diese Weise Knoten fehlen
+ // (momentan wird candidates nur zur Auswahl des besten Knotens
+ // benutzt).
+ it.remove();
+
+ extendNodeProper(candidate, minimumHorizontalExpansion);
+ nodesExpanded = true;
+
+ changedNodes.add(candidate);
+ }
+ }
+
+ long someTimeStart = System.nanoTime();
+ someCount++;
+ // geänderte temporär entfernte Knoten wieder hinzufügen
+ candidates.addAll(changedNodes);
+ // neu gefundene Knoten hinzufügen
+ candidates.addAll(newCandidates);
+ candidatesStable.addAll(newCandidates);
+ someTimeNs += System.nanoTime() - someTimeStart;
+
+ } while(nodesExpanded && !stop);
+
+ //System.out.println("candidate set:");
+ //for(Node n : candidates) {
+ // System.out.println(n);
+ //}
+
+ if(writeSearchTree) {
+ // String treeString = "";
+ String treeString = "best expanded node: " + bestNode+ "\n";
+ if(expandedNodes.size()>1) {
+ treeString += "all expanded nodes:\n"; // due to minimum horizontal expansion:\n";
+ for(ExampleBasedNode n : expandedNodes) {
+ treeString += " " + n + "\n";
+ }
+ }
+ expandedNodes.clear();
+ treeString += "horizontal expansion: " + minimumHorizontalExpansion + " to " + maximumHorizontalExpansion + "\n";
+ treeString += topNode.getTreeString();
+ treeString += "\n";
+ // System.out.println(treeString);
+ // searchTree += treeString + "\n";
+ // TODO: ev. immer nur einen search tree speichern und den an die
+ // Datei anhängen => spart Speicher
+ if(replaceSearchTree)
+ Files.createFile(searchTreeFile, treeString);
+ else
+ Files.appendFile(searchTreeFile, treeString);
+ }
+
+ // Anzahl Schleifendurchläufe
+ loop++;
+
+ if(!quiet)
+ System.out.println("--- loop " + loop + " finished ---");
+
+ }
+
+ // Suchbaum in Datei schreiben
+// if(writeSearchTree)
+// Files.createFile(searchTreeFile, searchTree);
+
+ // Ergebnisausgabe
+ /*
+ System.out.println("candidate set:");
+ for(Node n : candidates) {
+ System.out.println(n);
+ }*/
+
+ // Set<Concept> solutionsSorted = new TreeSet(conceptComparator);
+ // solutionsSorted.addAll(solutions);
+
+ // System.out.println("retrievals:");
+ // for(Concept c : ReasoningService.retrievals) {
+ // System.out.println(c);
+ // }
+
+ if(solutionFound) {
+ System.out.println();
+ System.out.println("solutions:");
+ for(Concept c : solutions) {
+ System.out.println(" " + c + " (length " + c.getLength() +", depth " + c.getDepth() + ")");
+ }
+ }
+ System.out.println("horizontal expansion: " + minimumHorizontalExpansion + " to " + maximumHorizontalExpansion);
+ System.out.println("size of candidate set: " + candidates.size());
+ printStatistics(true);
+
+ if(stop)
+ System.out.println("Algorithm stopped.");
+ else
+ System.out.println("Algorithm terminated succesfully.");
+ }
+
+ private void extendNodeProper(ExampleBasedNode node, int maxLength) {
+ // Rekursionsanfang ist das Konzept am Knoten selbst; danach wird der Operator
+ // so lange darauf angewandt bis alle proper refinements bis zu maxLength
+ // gefunden wurden
+ long propCalcNsStart = System.nanoTime();
+
+ if(writeSearchTree)
+ expandedNodes.add(node);
+
+ if(node.getChildren().size()>maxNrOfChildren)
+ maxNrOfChildren = node.getChildren().size();
+
+ // Knoten in instabiler Menge muss aktualisiert werden
+ // => wird jetzt schon vom Algorithmus entfernt
+ /*
+ boolean remove = candidates.remove(node);
+
+ if(!remove) {
+ System.out.println(candidates);
+ System.out.println(candidatesStable);
+ System.out.println(node);
+
+ throw new RuntimeException("remove failed");
+ }*/
+
+ extendNodeProper(node, node.getConcept(), maxLength, 0);
+ node.setHorizontalExpansion(maxLength);
+
+ // wird jetzt schon im Kernalgorithmus hinzugefügt
+ /*
+ boolean add = candidates.add(node);
+ if(!add) {
+ throw new RuntimeException("add failed");
+ }*/
+
+ // Knoten wird entfernt und wieder hinzugefügt, da sich seine
+ // Position geändert haben könnte => geht noch nicht wg. ConcurrentModification
+ // falls Knoten wg. min. horiz. exp. expandiert werden
+ // candidates.remove(node);
+ // candidates.add(node);
+ propernessCalcTimeNs += (System.nanoTime()-propCalcNsStart);
+ }
+
+
+
+ // für alle proper refinements von concept bis maxLength werden Kinderknoten
+ // für node erzeugt;
+ // recDepth dient nur zur Protokollierung
+ private void extendNodeProper(ExampleBasedNode node, Concept concept, int maxLength, int recDepth) {
+
+ // führe Methode nicht aus, wenn Algorithmus gestoppt wurde (alle rekursiven Funktionsaufrufe
+ // werden nacheinander abgebrochen, so dass ohne weitere Reasoninganfragen relativ schnell beendet wird)
+ if(stop)
+ return;
+
+ if(recDepth > maxRecDepth)
+ maxRecDepth = recDepth;
+
+ // Refinements berechnen => hier dürfen dürfen refinements <= horizontal expansion
+ // des Konzepts nicht gelöscht werden!
+ long refinementCalcTimeNsStart = System.nanoTime();
+ Set<Concept> refinements = operator.refine(concept, maxLength, null);
+ refinementCalcTimeNs += System.nanoTime() - refinementCalcTimeNsStart;
+
+ if(refinements.size()>maxNrOfRefinements)
+ maxNrOfRefinements = refinements.size();
+
+ long childConceptsDeletionTimeNsStart = System.nanoTime();
+ // entferne aus den refinements alle Konzepte, die bereits Kinder des Knotens sind
+ // for(Node n : node.getChildren()) {
+ // refinements.remove(n.getConcept());
+ // }
+
+ // das ist viel schneller, allerdings bekommt man ein anderes candidate set(??)
+ refinements.removeAll(node.getChildConcepts());
+
+ childConceptsDeletionTimeNs += System.nanoTime() - childConceptsDeletionTimeNsStart;
+
+ long evaluateSetCreationTimeNsStart = System.nanoTime();
+
+ // alle Konzepte, die länger als horizontal expansion sind, müssen ausgewertet
+ // werden
+ Set<Concept> toEvaluateConcepts = new TreeSet<Concept>(conceptComparator);
+ Iterator<Concept> it = refinements.iterator();
+ // for(Concept refinement : refinements) {
+ while(it.hasNext()) {
+ Concept refinement = it.next();
+ if(refinement.getLength()>node.getHorizontalExpansion()) {
+ // TODO: an dieser Stelle könnte man Algorithmen ansetzen lassen, die
+ // versuchen properness-Anfragen zu vermeiden:
+ // 1. Konzept kürzen und schauen, ob es Mutterkonzept entspricht
+ // 2. Blacklist, die überprüft, ob Konzept too weak ist
+ // (dann ist es auch proper)
+
+ // sagt aus, ob festgestellt wurde, ob refinement proper ist
+ // (sagt nicht aus, dass das refinement proper ist!)
+ boolean propernessDetected = false;
+
+ // 1. short concept construction
+ if(useShortConceptConstruction) {
+ // kurzes Konzept konstruieren
+ Concept shortConcept = ConceptTransformation.getShortConcept(refinement, conceptComparator);
+ int n = conceptComparator.compare(shortConcept, concept);
+
+ // Konzepte sind gleich also Refinement improper
+ if(n==0) {
+ propernessTestsAvoidedByShortConceptConstruction++;
+ propernessDetected = true;
+ }
+ }
+
+ // 2. too weak test
+ if(!propernessDetected && useTooWeakList) {
+ if(refinement instanceof MultiConjunction) {
+ boolean tooWeakElement = containsTooWeakElement((MultiConjunction)refinement);
+ if(tooWeakElement) {
+ propernessTestsAvoidedByTooWeakList++;
+ conceptTestsTooWeakList++;
+ propernessDetected = true;
+ tooWeakList.add(refinement);
+
+ // Knoten wird direkt erzeugt (es ist buganfällig zwei Plätze
+ // zu haben, an denen Knoten erzeugt werden, aber es erscheint
+ // hier am sinnvollsten)
+ properRefinements.add(refinement);
+ tooWeakList.add(refinement);
+
+ ExampleBasedNode newNode = new ExampleBasedNode(refinement);
+ newNode.setHorizontalExpansion(refinement.getLength()-1);
+ newNode.setTooWeak(true);
+ newNode.setQualityEvaluationMethod(ExampleBasedNode.QualityEvaluationMethod.TOO_WEAK_LIST);
+ node.addChild(newNode);
+
+ // Refinement muss gelöscht werden, da es proper ist
+ it.remove();
+ }
+ }
+ }
+
+ // properness konnte nicht vorher ermittelt werden
+ if(!propernessDetected)
+ toEvaluateConcepts.add(refinement);
+
+
+ }
+ }
+ evaluateSetCreationTimeNs += System.nanoTime() - evaluateSetCreationTimeNsStart;
+
+ // System.out.println(toEvaluateConcepts.size());
+
+ Set<Concept> improperConcepts = null;
+ if(toEvaluateConcepts.size()>0) {
+ // Test aller Konzepte auf properness (mit DIG in nur einer Anfrage)
+ long propCalcReasoningStart = System.nanoTime();
+ improperConcepts = rs.subsumes(toEvaluateConcepts, concept);
+ propernessTestsReasoner+=toEvaluateConcepts.size();
+ // boolean isProper = !learningProblem.getReasoningService().subsumes(refinement, concept);
+ propernessCalcReasoningTimeNs += System.nanoTime() - propCalcReasoningStart;
+ }
+
+ long improperConceptsRemovalTimeNsStart = System.nanoTime();
+ // die improper Konzepte werden von den auszuwertenden gelöscht, d.h.
+ // alle proper concepts bleiben übrig (einfache Umbenennung)
+ if(improperConcepts != null)
+ toEvaluateConcepts.removeAll(improperConcepts);
+ Set<Concept> properConcepts = toEvaluateConcepts;
+ // alle proper concepts von refinements löschen
+ refinements.removeAll(properConcepts);
+ improperConceptsRemovalTimeNs += System.nanoTime() - improperConceptsRemovalTimeNsStart;
+
+ for(Concept refinement : properConcepts) {
+ long redundancyCheckTimeNsStart = System.nanoTime();
+ boolean nonRedundant = properRefinements.add(refinement);
+ redundancyCheckTimeNs += System.nanoTime() - redundancyCheckTimeNsStart;
+
+ if(!nonRedundant)
+ redundantConcepts++;
+
+ // es wird nur ein neuer Knoten erzeugt, falls das Konzept nicht
+ // schon existiert
+ if(nonRedundant) {
+
+ // Knoten erzeugen
+ ExampleBasedNode newNode = new ExampleBasedNode(refinement);
+ // die -1 ist wichtig, da sonst keine gleich langen Refinements
+ // für den neuen Knoten erlaubt wären z.B. person => male
+ newNode.setHorizontalExpansion(refinement.getLength()-1);
+
+
+ // hier finden Tests statt, die Retrieval-Anfrage vermeiden sollen
+ /*
+ Integer n = evaluationCache.get(concept);
+ // Konzept gefunden
+ if(n!=null) {
+ // Knoten erzeugen
+ Node newNode = new Node(refinement);
+ newNode.setHorizontalExpansion(refinement.getLength()-1);
+ node.addChild(newNode);
+
+ // too weak
+ if(n==-1) {
+ newNode.setTooWeak(true);
+ // nicht too weak
+ } else {
+ // feststellen, ob proper => geht so nicht
+ // gleiche covered negatives bedeutet nicht improper
+ boolean proper = (n==node.getCoveredNegativeExamples());
+ newNode.setCoveredNegativeExamples(n);
+
+ }
+ // Konzept nicht gefunden => muss ausgewertet werden
+ } else {
+ toEvaluateConcepts.add(refinement);
+ }
+ */
+
+ boolean qualityKnown = false;
+ int quality = -2;
+
+ // overly general list verwenden
+ if(useOverlyGeneralList && refinement instanceof MultiDisjunction) {
+ if(containsOverlyGeneralElement((MultiDisjunction)refinement)) {
+ conceptTestsOverlyGeneralList++;
+ quality = getNumberOfNegatives();
+ qualityKnown = true;
+ newNode.setQualityEvaluationMethod(ExampleBasedNode.QualityEvaluationMethod.OVERLY_GENERAL_LIST);
+ }
+ }
+
+ // Qualität des Knotens auswerten
+ if(!qualityKnown) {
+ long propCalcReasoningStart2 = System.nanoTime();
+ conceptTestsReasoner++;
+ quality = coveredNegativesOrTooWeak(refinement);
+ propernessCalcReasoningTimeNs += System.nanoTime() - propCalcReasoningStart2;
+ newNode.setQualityEvaluationMethod(ExampleBasedNode.QualityEvaluationMethod.REASONER);
+ }
+
+ if(quality == -1) {
+ newNode.setTooWeak(true);
+ // Blacklist für too weak concepts
+ tooWeakList.add(refinement);
+ } else {
+ // Lösung gefunden
+ if(quality == 0) {
+ solutionFound = true;
+ solutions.add(refinement);
+ }
+
+ newNode.setCoveredNegativeExamples(quality);
+ newCandidates.add(newNode);
+ // candidates.add(newNode);
+ // candidatesStable.add(newNode);
+
+
+ if(quality == getNumberOfNegatives())
+ overlyGeneralList.add(refinement);
+
+ // System.out.print(".");
+ }
+
+ node.addChild(newNode);
+ }
+ }
+
+
+ /*
+ Iterator<Concept> it = refinements.iterator();
+ while(it.hasNext()) {
+ Concept refinement = it.next();
+ if(refinement.getLength()>node.getHorizontalExpansion()) {
+ // Test auf properness
+ long propCalcReasoningStart = System.nanoTime();
+ boolean isProper = !learningProblem.getReasoningService().subsumes(refinement, concept);
+ propernessCalcReasoningTimeNs += System.nanoTime() - propCalcReasoningStart;
+
+ if(isProper) {
+ long redundancyCheckTimeNsStart = System.nanoTime();
+ boolean nonRedundant = properRefinements.add(refinement);
+ redundancyCheckTimeNs += System.nanoTime() - redundancyCheckTimeNsStart;
+
+ if(!nonRedundant)
+ redundantConcepts++;
+
+ // es wird nur ein neuer Knoten erzeugt, falls das Konzept nicht
+ // schon existiert
+ if(nonRedundant) {
+
+ // Knoten erzeugen
+ Node newNode = new Node(refinement);
+ // die -1 ist wichtig, da sonst keine gleich langen Refinements
+ // für den neuen Knoten erlaubt wären z.B. person => male
+ newNode.setHorizontalExpansion(refinement.getLength()-1);
+ node.addChild(newNode);
+
+ // Qualität des Knotens auswerten
+ long propCalcReasoningStart2 = System.nanoTime();
+ int quality = learningProblem.coveredNegativeExamplesOrTooWeak(refinement);
+ propernessCalcReasoningTimeNs += System.nanoTime() - propCalcReasoningStart2;
+
+ if(quality == -1) {
+ newNode.setTooWeak(true);
+ } else {
+ // Lösung gefunden
+ if(quality == 0) {
+ solutionFound = true;
+ solutions.add(refinement);
+ }
+
+ newNode.setCoveredNegativeExamples(quality);
+ newCandidates.add(newNode);
+
+ // System.out.print(".");
+ }
+ }
+
+ // jedes proper Refinement wird gelöscht
+ it.remove();
+
+ }
+ }
+ }
+ */
+
+
+
+ // es sind jetzt noch alle Konzepte übrig, die improper refinements sind
+ // auf jedem dieser Konzepte wird die Funktion erneut aufgerufen, da sich
+ // proper refinements ergeben könnten
+ for(Concept refinement : refinements) {
+ // for(int i=0; i<=recDepth; i++)
+ // System.out.print(" ");
+ // System.out.println("call: " + refinement + " [maxLength " + maxLength + "]");
+ extendNodeProper(node, refinement, maxLength, recDepth+1);
+ // for(int i=0; i<=recDepth; i++)
+ // System.out.print(" ");
+ // System.out.println("finished: " + refinement + " [maxLength " + maxLength + "]");
+ }
+ }
+
+ private void printStatistics(boolean finalStats) {
+ // TODO: viele Tests haben ergeben, dass man nie 100% mit der Zeitmessung abdecken
+ // kann (zum einen weil Stringausgabe verzögert erfolgt und zum anderen weil
+ // Funktionsaufrufe, garbage collection, Zeitmessung selbst auch Zeit benötigt);
+ // es empfiehlt sich folgendes Vorgehen:
+ // - Messung der Zeit eines Loops im Algorithmus
+ // - Messung der Zeit für alle node extensions innerhalb eines Loops
+ // => als Normalisierungsbasis empfehlen sich dann die Loopzeit statt
+ // Algorithmuslaufzeit
+ // ... momentan kann es aber auch erstmal so lassen
+
+ long algorithmRuntime = System.nanoTime() - algorithmStartTime;
+
+ if(!finalStats) {
+ // Refinementoperator auf Konzept anwenden
+ String bestNodeString = "currently best node: " + candidatesStable.last();
+ // searchTree += bestNodeString + "\n";
+ System.out.println(bestNodeString);
+ String expandedNodeString = "next expanded node: " + candidates.last();
+ // searchTree += expandedNodeString + "\n";
+ System.out.println(expandedNodeString);
+ System.out.println("algorithm runtime " + Helper.prettyPrintNanoSeconds(algorithmRuntime));
+ String expansionString = "horizontal expansion: " + minimumHorizontalExpansion + " to " + maximumHorizontalExpansion;
+ // searchTree += expansionString + "\n";
+ System.out.println(expansionString);
+ System.out.println("size of candidate set: " + candidates.size());
+ // 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);
+ }
+
+ if(showBenchmarkInformation) {
+
+
+ long reasoningTime = rs.getOverallReasoningTimeNs();
+ double reasoningPercentage = 100 * reasoningTime/(double)algorithmRuntime;
+ long propWithoutReasoning = propernessCalcTimeNs-propernessCalcReasoningTimeNs;
+ double propPercentage = 100 * propWithoutReasoning/(double)algorithmRuntime;
+ double deletionPercentage = 100 * childConceptsDeletionTimeNs/(double)algorithmRuntime;
+ long subTime = rs.getSubsumptionReasoningTimeNs();
+ double subPercentage = 100 * subTime/(double)algorithmRuntime;
+ double refinementPercentage = 100 * refinementCalcTimeNs/(double)algorithmRuntime;
+ double redundancyCheckPercentage = 100 * redundancyCheckTimeNs/(double)algorithmRuntime;
+ double evaluateSetCreationTimePercentage = 100 * evaluateSetCreationTimeNs/(double)algorithmRuntime;
+ double improperConceptsRemovalTimePercentage = 100 * improperConceptsRemovalTimeNs/(double)algorithmRuntime;
+ double mComputationTimePercentage = 100 * operator.mComputationTimeNs/(double)algorithmRuntime;
+ double topComputationTimePercentage = 100 * operator.topComputationTimeNs/(double)algorithmRuntime;
+ double cleanTimePercentage = 100 * ConceptTransformation.cleaningTimeNs/(double)algorithmRuntime;
+ double onnfTimePercentage = 100 * ConceptTransformation.onnfTimeNs/(double)algorithmRuntime;
+ double shorteningTimePercentage = 100 * ConceptTransformation.shorteningTimeNs/(double)algorithmRuntime;
+
+ // nur temporär
+ double someTimePercentage = 100 * someTimeNs/(double)algorithmRuntime;
+
+ System.out.println("reasoning percentage: " + df.format(reasoningPercentage) + "%");
+ System.out.println(" subsumption check time: " + df.format(subPercentage) + "%");
+ System.out.println("proper calculation percentage (wo. reasoning): " + df.format(propPercentage) + "%");
+ System.out.println(" deletion time percentage: " + df.format(deletionPercentage) + "%");
+ System.out.println(" refinement calculation percentage: " + df.format(refinementPercentage) + "%");
+ System.out.println(" some time percentage: " + df.format(someTimePercentage) + "% " + Helper.prettyPrintNanoSeconds(someTimeNs) + " " + someCount + " times");
+ System.out.println(" m calculation percentage: " + df.format(mComputationTimePercentage) + "%");
+ System.out.println(" top calculation percentage: " + df.format(topComputationTimePercentage) + "%");
+ System.out.println(" redundancy check percentage: " + df.format(redundancyCheckPercentage) + "%");
+ System.out.println(" evaluate set creation time percentage: " + df.format(evaluateSetCreationTimePercentage) + "%");
+ System.out.println(" improper concepts removal time percentage: " + df.format(improperConceptsRemovalTimePercentage) + "%");
+ System.out.println("clean time percentage: " + df.format(cleanTimePercentage) + "%");
+ System.out.println("onnf time percentage: " + df.format(onnfTimePercentage) + "%");
+ System.out.println("shortening time percentage: " + df.format(shorteningTimePercentage) + "%");
+ }
+ System.out.println("properness tests (reasoner/short concept/too weak list): " + propernessTestsReasoner + "/" + propernessTestsAvoidedByShortConceptConstruction
+ + "/" + propernessTestsAvoidedByTooWeakList);
+ System.out.println("concept tests (reasoner/too weak list/overly general list/redundant concepts): " + conceptTestsReasoner + "/"
+ + conceptTestsTooWeakList + "/" + conceptTestsOverlyGeneralList + "/" + redundantConcepts);
+ }
+
+ private int coveredNegativesOrTooWeak(Concept concept) {
+ if(posOnly)
+ return posOnlyLearningProblem.coveredPseudoNegativeExamplesOrTooWeak(concept);
+ else
+ return learningProblem.coveredNegativeExamplesOrTooWeak(concept);
+ }
+
+ private int getNumberOfNegatives() {
+ if(posOnly)
+ return posOnlyLearningProblem.getPseudoNegatives().size();
+ else
+ return learningProblem.getNegativeExamples().size();
+ }
+
+ private boolean containsTooWeakElement(MultiConjunction mc) {
+ for(Concept child : mc.getChildren()) {
+ if(tooWeakList.contains(child))
+ return true;
+ }
+ return false;
+ }
+
+ private boolean containsOverlyGeneralElement(MultiDisjunction md) {
+ for(Concept child : md.getChildren()) {
+ if(overlyGeneralList.contains(child))
+ return true;
+ }
+ return false;
+ }
+
+ public void stop() {
+
+ }
+
+ public Concept getBestSolution() {
+ return candidatesStable.last().getConcept();
+ }
+
+ public synchronized List<Concept> getBestSolutions(int nrOfSolutions) {
+ List<Concept> best = new LinkedList<Concept>();
+ int i=0;
+ for(ExampleBasedNode n : candidatesStable.descendingSet()) {
+ best.add(n.getConcept());
+ if(i==nrOfSolutions)
+ return best;
+ i++;
+ }
+ return best;
+ }
+
+ public Score getSolutionScore() {
+ if(posOnly)
+ return posOnlyLearningProblem.computeScore(getBestSolution());
+ else
+ return learningProblem.computeScore(getBestSolution());
+ }
+
+
+
+}
Added: trunk/src/dl-learner/org/dllearner/algorithms/refexamples/FlexibleHeuristic.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/algorithms/refexamples/FlexibleHeuristic.java (rev 0)
+++ trunk/src/dl-learner/org/dllearner/algorithms/refexamples/FlexibleHeuristic.java 2008-01-23 12:05:44 UTC (rev 418)
@@ -0,0 +1,93 @@
+/**
+ * Copyright (C) 2007-2008, 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.algorithms.refexamples;
+
+import org.dllearner.utilities.ConceptComparator;
+
+/**
+ * This heuristic compares two nodes by computing a score
+ * using the number of covered negatives and the horizontal
+ * expansion factor of a node as input. Using this score
+ * it decides which one of the nodes seems to be more promising.
+ * The heuristic is flexible, because it offers a tradeoff
+ * between accurary and horizontal expansion (concept length).
+ * In contrast to the lexicographic heuristic this means that
+ * it sometimes prefers worse classifiers with low horizontal
+ * expansion over a better classifier with high horizontal
+ * expansion.
+ *
+ * It can be configured by using the "percentPerLenghtUnit"
+ * constructor argument. A higher
+ * value means that the algorithm is more likely to search in
+ * unexplored areas (= low horizontal expansion) of the search
+ * space vs. looking in promising but already explored (= high
+ * horizontal expansion) areas of the search space.
+ *
+ * @author Jens Lehmann
+ *
+ */
+public class FlexibleHeuristic implements ExampleBasedHeuristic {
+
+ // Vergleich von Konzepten, falls alle anderen Kriterien fehlschlagen
+ private ConceptComparator conceptComparator = new ConceptComparator();
+ private int nrOfNegativeExamples;
+ private double percentPerLengthUnit;
+
+ // 5% sind eine Verlängerung um 1 wert
+ // double percentPerLengthUnit = 0.05;
+
+ public FlexibleHeuristic(int nrOfNegativeExamples, double percentPerLengthUnit) {
+ this.nrOfNegativeExamples = nrOfNegativeExamples;
+ this.percentPerLengthUnit = percentPerLengthUnit;
+ }
+
+ // implementiert einfach die Definition in der Diplomarbeit
+ public int compare(ExampleBasedNode n1, ExampleBasedNode n2) {
+
+ // sicherstellen, dass Qualität ausgewertet wurde
+ if(n1.isQualityEvaluated() && n2.isQualityEvaluated() && !n1.isTooWeak() && !n2.isTooWeak()) {
+
+ // alle scores sind negativ, größere scores sind besser
+ double score1 = -n1.getCoveredNegativeExamples()/(double)nrOfNegativeExamples;
+ score1 -= percentPerLengthUnit * n1.getConcept().getLength();
+
+ double score2 = -n2.getCoveredNegativeExamples()/(double)nrOfNegativeExamples;
+ score2 -= percentPerLengthUnit * n2.getConcept().getLength();
+
+ double diff = score1 - score2;
+
+ if(diff>0)
+ return 1;
+ else if(diff<0)
+ return -1;
+ else
+ return conceptComparator.compare(n1.getConcept(), n2.getConcept());
+ }
+
+ throw new RuntimeException("Cannot compare nodes, which have no evaluated quality or are too weak.");
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ return (o instanceof FlexibleHeuristic);
+ }
+
+}
Added: trunk/src/dl-learner/org/dllearner/algorithms/refexamples/LexicographicHeuristic.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/algorithms/refexamples/LexicographicHeuristic.java (rev 0)
+++ trunk/src/dl-learner/org/dllearner/algorithms/refexamples/LexicographicHeuristic.java 2008-01-23 12:05:44 UTC (rev 418)
@@ -0,0 +1,115 @@
+/**
+ * Copyright (C) 2007-2008, 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
+ * th...
[truncated message content] |
