Thread: [DL-Learner SVN] SF.net SVN: dl-learner:[1808] trunk (Page 4)

SourceForge Headquarters 225 Broadway Suite 1600 San Diego, CA 92101 +1 (858) 422-6466

Revision: 1808
          http://dl-learner.svn.sourceforge.net/dl-learner/?rev=1808&view=rev
Author:   jenslehmann
Date:     2009-06-25 10:17:14 +0000 (Thu, 25 Jun 2009)

Log Message:
-----------
started algorithm for learning disjunctions of EL trees

Modified Paths:
--------------
    trunk/lib/components.ini
    trunk/src/dl-learner/org/dllearner/algorithms/el/SearchTreeNode.java
    trunk/src/dl-learner/org/dllearner/cli/ConfMapper.java
    trunk/src/dl-learner/org/dllearner/scripts/evaluation/OntologyEngineering.java

Added Paths:
-----------
    trunk/src/dl-learner/org/dllearner/algorithms/el/DisjunctiveHeuristic.java
    trunk/src/dl-learner/org/dllearner/algorithms/el/ELLearningAlgorithmDisjunctive.java

Modified: trunk/lib/components.ini
===================================================================

--- trunk/lib/components.ini	2009-06-18 13:37:47 UTC (rev 1807)
+++ trunk/lib/components.ini	2009-06-25 10:17:14 UTC (rev 1808)
@@ -23,4 +23,5 @@
 org.dllearner.algorithms.refinement2.ROLComponent2
 org.dllearner.algorithms.gp.GP
 org.dllearner.algorithms.el.ELLearningAlgorithm
+org.dllearner.algorithms.el.ELLearningAlgorithmDisjunctive
 org.dllearner.algorithms.celoe.CELOE

Added: trunk/src/dl-learner/org/dllearner/algorithms/el/DisjunctiveHeuristic.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/algorithms/el/DisjunctiveHeuristic.java	                        (rev 0)
+++ trunk/src/dl-learner/org/dllearner/algorithms/el/DisjunctiveHeuristic.java	2009-06-25 10:17:14 UTC (rev 1808)
@@ -0,0 +1,16 @@
+package org.dllearner.algorithms.el;
+
+public class DisjunctiveHeuristic implements ELHeuristic {
+
+	ELDescriptionTreeComparator edt = new ELDescriptionTreeComparator();
+	
+	public int compare(SearchTreeNode tree1, SearchTreeNode tree2) {
+		double diff = tree1.getScore()-tree2.getScore();
+		if(diff < 0.00001 && diff > -0.00001) {
+			return edt.compare(tree1.getDescriptionTree(), tree2.getDescriptionTree());
+		} else {
+			return (int)Math.signum(diff);
+		}
+	}
+
+}

Added: trunk/src/dl-learner/org/dllearner/algorithms/el/ELLearningAlgorithmDisjunctive.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/algorithms/el/ELLearningAlgorithmDisjunctive.java	                        (rev 0)
+++ trunk/src/dl-learner/org/dllearner/algorithms/el/ELLearningAlgorithmDisjunctive.java	2009-06-25 10:17:14 UTC (rev 1808)
@@ -0,0 +1,340 @@
+/**
+ * Copyright (C) 2007-2009, 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.el;
+
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.SortedSet;
+import java.util.TreeSet;
+
+import org.apache.log4j.Logger;
+import org.dllearner.core.ComponentInitException;
+import org.dllearner.core.EvaluatedDescription;
+import org.dllearner.core.LearningAlgorithm;
+import org.dllearner.core.LearningProblem;
+import org.dllearner.core.ReasonerComponent;
+import org.dllearner.core.configurators.Configurator;
+import org.dllearner.core.configurators.ELLearningAlgorithmConfigurator;
+import org.dllearner.core.options.CommonConfigOptions;
+import org.dllearner.core.options.ConfigOption;
+import org.dllearner.core.options.StringConfigOption;
+import org.dllearner.core.owl.Description;
+import org.dllearner.core.owl.Individual;
+import org.dllearner.core.owl.Thing;
+import org.dllearner.core.owl.Union;
+import org.dllearner.learningproblems.PosNegLP;
+import org.dllearner.refinementoperators.ELDown2;
+
+/**
+ * A learning algorithm for EL, which will based on an
+ * ideal refinement operator.
+ * 
+ * The algorithm learns disjunctions of EL trees as follows:
+ * - given pos. and neg. examples, noise in %, min coverage per tree x %
+ * - it searches for an EL tree, which covers at least x % of all positive examples
+ *   and at most (coverage_on_positives * noise) negative examples
+ * - the covered examples are removed from the pos. and neg. examples
+ * - termination: all(?) positive examples covered
+ * 
+ * ev. besser: feste Suchzeiten pro Baum => es wird dann jeweils der beste Baum gewählt
+ * => Terminierung, wenn alles gecovered ist oder kein Baum mit ausreichender Qualität
+ * in dem Zeitfenster gefunden wird
+ * 
+ * In contrast to many other algorithms, only one solution is returned. Additionally,
+ * the algorithm is not really an anytime algorithm, since the solution is constructed
+ * stepwise as a set of trees. 
+ * 
+ * TODO redundancy check
+ * 
+ * @author Jens Lehmann
+ *
+ */
+public class ELLearningAlgorithmDisjunctive extends LearningAlgorithm {
+
+	private static Logger logger = Logger.getLogger(ELLearningAlgorithmDisjunctive.class);	
+	private ELLearningAlgorithmConfigurator configurator;
+	
+	private ELDown2 operator;
+	
+	private boolean isRunning = false;
+	private boolean stop = false;
+	
+	private SearchTreeNode startNode;
+	private ELHeuristic heuristic;
+	private TreeSet<SearchTreeNode> candidates;
+	
+	// tree search
+	private List<ELDescriptionTree> currentSolution = new LinkedList<ELDescriptionTree>();
+	private EvaluatedDescription bestEvaluatedDescription;
+	// how important not cover
+	private double posWeight = 5;
+	private int startPosExamplesSize;
+	private int startNegExamplesSize;
+	private SortedSet<Individual> currentPosExamples;
+	private SortedSet<Individual> currentNegExamples;
+	private ELDescriptionTree bestCurrentTree;
+	private double bestCurrentScore = 0;
+	private long treeStartTime;
+	
+	public ELLearningAlgorithmDisjunctive(PosNegLP problem, ReasonerComponent reasoner) {
+		super(problem, reasoner);
+	}
+	
+	public static String getName() {
+		return "disjunctive EL learning algorithm";
+	}	
+	
+	public static Collection<Class<? extends LearningProblem>> supportedLearningProblems() {
+		Collection<Class<? extends LearningProblem>> problems = new LinkedList<Class<? extends LearningProblem>>();
+		problems.add(PosNegLP.class);
+		return problems;
+	}
+	
+	
+	public static Collection<ConfigOption<?>> createConfigOptions() {
+		Collection<ConfigOption<?>> options = new LinkedList<ConfigOption<?>>();
+		options.add(CommonConfigOptions.getNoisePercentage());
+		options.add(new StringConfigOption("startClass", "the named class which should be used to start the algorithm (GUI: needs a widget for selecting a class)"));
+		return options;
+	}	
+	
+	// we can assume a PosNegLP, because it is the only supported one
+	private PosNegLP getLearningProblem() {
+		return (PosNegLP) learningProblem;
+	}
+	
+	@Override
+	public Configurator getConfigurator() {
+		return configurator;
+	}	
+	
+	@Override
+	public void init() throws ComponentInitException {
+		heuristic = new DisjunctiveHeuristic();
+		candidates = new TreeSet<SearchTreeNode>(heuristic);
+		
+		operator = new ELDown2(reasoner);
+	}	
+	
+	@Override
+	public void start() {
+		stop = false;
+		isRunning = true;
+		reset();
+		int treeCount = 0;
+		
+		while(!stop && !stoppingCriteriaSatisfied()) {
+			
+			treeStartTime = System.nanoTime();
+			// create start node
+			ELDescriptionTree top = new ELDescriptionTree(reasoner, Thing.instance);
+			addDescriptionTree(top, null);
+			bestCurrentTree = top;
+			bestCurrentScore = Double.NEGATIVE_INFINITY;
+			
+			// main loop
+			int loop = 0;
+			while(!stop && !treeCriteriaSatisfied()) {
+				// pick the best candidate according to the heuristic
+				SearchTreeNode best = candidates.pollLast();
+				// apply operator
+				List<ELDescriptionTree> refinements = operator.refine(best.getDescriptionTree());
+				// add all refinements to search tree, candidates, best descriptions
+				for(ELDescriptionTree refinement : refinements) {
+					addDescriptionTree(refinement, best);
+				}
+				loop++;
+				// logging
+				if(logger.isTraceEnabled()) {
+					logger.trace("Choosen node " + best);
+					logger.trace(startNode.getTreeString());
+					logger.trace("Loop " + loop + " completed.");
+				}
+			}
+			
+			// we found a tree (partial solution)
+			currentSolution.add(bestCurrentTree);
+			Description bestDescription = bestCurrentTree.transformToDescription();
+			// form union of trees found so far with 
+			if(treeCount==0) {
+				bestEvaluatedDescription = learningProblem.evaluate(bestDescription);
+			} else {
+				Union union = new Union(bestEvaluatedDescription.getDescription(), bestDescription);
+				bestEvaluatedDescription = learningProblem.evaluate(union);
+			}
+			
+			// remove already covered examples
+			Iterator<Individual> it = currentPosExamples.iterator();
+			int posCov = 0;
+			while(it.hasNext()) {
+				Individual ind = it.next();
+				if(reasoner.hasType(bestDescription, ind)) {
+					it.remove();
+					posCov++;
+				}
+			}
+			it = currentNegExamples.iterator();
+			int negCov = 0;
+			while(it.hasNext()) {
+				Individual ind = it.next();
+				if(reasoner.hasType(bestDescription, ind)) {
+					it.remove();
+					negCov++;
+				}
+			}
+			logger.info("tree found: " + bestDescription + " (" + posCov + " pos covered, " + currentPosExamples.size() + " remaining, " + negCov + " neg covered, " + currentNegExamples.size() + " remaining");
+			
+			treeCount++;
+		}
+		
+		// print solution
+		logger.info("solution : " + bestEvaluatedDescription);
+		
+		isRunning = false;
+	}
+
+	// evaluates a description in tree form
+	private void addDescriptionTree(ELDescriptionTree descriptionTree, SearchTreeNode parentNode) {
+		
+		// create search tree node
+		SearchTreeNode node = new SearchTreeNode(descriptionTree);
+		
+		// compute score
+		double score = getTreeScore(descriptionTree);
+		node.setScore(score);
+		
+		// link to parent (unless start node)
+		if(parentNode == null) {
+			startNode = node;
+		} else {
+			parentNode.addChild(node);
+		}
+		
+		// TODO: define "too weak" as a coverage on negative examples, which is
+		// too high for the tree to be considered
+		
+		candidates.add(node);
+		
+		// check whether this is the best tree
+		if(score > bestCurrentScore) {
+			bestCurrentTree = descriptionTree;
+			bestCurrentScore = score;
+		}
+	}
+	
+	private double getTreeScore(ELDescriptionTree tree) {
+		
+		Description d = tree.transformToDescription();
+		
+		double score = 0;
+		
+		// test coverage on current positive examples
+		int posCovered = 0;
+		for(Individual ind : currentPosExamples) {
+			if(reasoner.hasType(d, ind)) {
+				posCovered++;
+				score += 1;
+			}
+		}
+//		double posPercentage = posCovered/(double)currentPosExamples.size();
+		
+		// penalty if a minimum coverage is not achieved (avoids too many trees where
+		// each tree has only little impact)
+		if(startPosExamplesSize > 10 && posCovered<3 || posCovered < 1) {
+			score -= 10;
+		}
+		
+		// test coverage on current negative examples
+		int negCovered = 0;
+		for(Individual ind : currentNegExamples) {
+			if(reasoner.hasType(d, ind)) {
+				negCovered++;
+				score -= posWeight;
+			}
+		}
+//		double negPercentage = negCovered/(double)currentNegExamples.size();
+		
+		// length penalty
+		score -= 0.1*tree.getSize();
+		
+		return score;
+	}
+	
+	private boolean treeCriteriaSatisfied() {
+		long runTime = System.nanoTime() - treeStartTime;
+		// more than one second has passed
+		if(runTime / 1000000000 > 1) {
+			return true;
+		} else {
+			return false;
+		}
+	}
+	
+	private boolean stoppingCriteriaSatisfied() {
+		// stop if we have a node covering all positives and none of the negatives
+//		SearchTreeNode bestNode = candidates.last();
+//		return (bestNode.getCoveredNegatives() == 0);
+		
+		// stop whan all positive examples have been covered
+		return (currentPosExamples.size()==0);
+	}
+	
+	private void reset() {
+		// set all values back to their default values (used for running
+		// the algorithm more than once)
+		candidates.clear();
+		currentSolution.clear();
+		bestEvaluatedDescription = learningProblem.evaluate(Thing.instance);
+		currentPosExamples = getLearningProblem().getPositiveExamples();
+		currentNegExamples = getLearningProblem().getNegativeExamples();
+		startPosExamplesSize = currentPosExamples.size();
+		startNegExamplesSize = currentNegExamples.size();
+	}
+	
+	@Override
+	public void stop() {
+		stop = true;
+	}
+	
+	@Override
+	public boolean isRunning() {
+		return isRunning;
+	}	
+	
+	@Override
+	public Description getCurrentlyBestDescription() {
+		return bestEvaluatedDescription.getDescription();
+	}
+	
+	@Override
+	public EvaluatedDescription getCurrentlyBestEvaluatedDescription() {
+		return bestEvaluatedDescription;
+	}			
+	
+	/**
+	 * @return the startNode
+	 */
+	public SearchTreeNode getStartNode() {
+		return startNode;
+	}	
+
+}

Modified: trunk/src/dl-learner/org/dllearner/algorithms/el/SearchTreeNode.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/algorithms/el/SearchTreeNode.java	2009-06-18 13:37:47 UTC (rev 1807)
+++ trunk/src/dl-learner/org/dllearner/algorithms/el/SearchTreeNode.java	2009-06-25 10:17:14 UTC (rev 1808)
@@ -37,6 +37,8 @@
 	private int coveredNegatives;
 	private boolean tooWeak = false;
 	
+	private double score;
+	
 	public SearchTreeNode(ELDescriptionTree descriptionTree) {
 		this.descriptionTree = descriptionTree;
 	}
@@ -96,6 +98,7 @@
 		else
 			ret += coveredNegatives;
 		ret += ", children:" + children.size() + "]";
+		ret += " score: " + score;
 		return ret;
 	}
 	
@@ -114,6 +117,14 @@
 			treeString.append(child.getTreeString(depth+1));
 		}
 		return treeString;
+	}
+
+	public double getScore() {
+		return score;
+	}
+
+	public void setScore(double score) {
+		this.score = score;
 	}	
 	
 }

Modified: trunk/src/dl-learner/org/dllearner/cli/ConfMapper.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/cli/ConfMapper.java	2009-06-18 13:37:47 UTC (rev 1807)
+++ trunk/src/dl-learner/org/dllearner/cli/ConfMapper.java	2009-06-25 10:17:14 UTC (rev 1808)
@@ -30,6 +30,7 @@
 import org.dllearner.algorithms.RandomGuesser;
 import org.dllearner.algorithms.celoe.CELOE;
 import org.dllearner.algorithms.el.ELLearningAlgorithm;
+import org.dllearner.algorithms.el.ELLearningAlgorithmDisjunctive;
 import org.dllearner.algorithms.gp.GP;
 import org.dllearner.algorithms.refinement.ROLearner;
 import org.dllearner.algorithms.refinement2.ROLComponent2;
@@ -101,6 +102,7 @@
 		learningAlgorithmMapping.put("refinement", ROLearner.class);
 		learningAlgorithmMapping.put("refexamples", ROLComponent2.class);
 		learningAlgorithmMapping.put("el", ELLearningAlgorithm.class);
+		learningAlgorithmMapping.put("disjunctiveEL", ELLearningAlgorithmDisjunctive.class);
 		learningAlgorithmMapping.put("celoe", CELOE.class);
 		
 		// you do not need to edit anything below

Modified: trunk/src/dl-learner/org/dllearner/scripts/evaluation/OntologyEngineering.java
===================================================================
--- trunk/src/dl-learner/org/dllearner/scripts/evaluation/OntologyEngineering.java	2009-06-18 13:37:47 UTC (rev 1807)
+++ trunk/src/dl-learner/org/dllearner/scripts/evaluation/OntologyEngineering.java	2009-06-25 10:17:14 UTC (rev 1808)
@@ -78,10 +78,10 @@
 	private static DecimalFormat df = new DecimalFormat();
 
 	// for performance measurements and development
-	private static boolean autoMode = false;
+	private static boolean autoMode = true;
 	private static boolean useFastInstanceChecker = true;
-	private static boolean useApproximations = true;
-	private static boolean computeApproxDiff = false;
+	private static boolean useApproximations = false;
+	private static boolean computeApproxDiff = true;
 	
 	@SuppressWarnings("unchecked")
 	public static void main(String[] args) throws ComponentInitException,


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.




Thread: [DL-Learner SVN] SF.net SVN: dl-learner:[1808] trunk (Page 4)

dl-learner-svn