dl-learner-svn Mailing List for DL-Learner (Page 100)

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.




2007	Jan	Feb	Mar	Apr	May	Jun	Jul	Aug (120)	Sep (36)	Oct (116)	Nov (17)	Dec (44)
2008	Jan (143)	Feb (192)	Mar (74)	Apr (84)	May (105)	Jun (64)	Jul (49)	Aug (120)	Sep (159)	Oct (156)	Nov (51)	Dec (28)
2009	Jan (17)	Feb (55)	Mar (33)	Apr (57)	May (54)	Jun (28)	Jul (6)	Aug (16)	Sep (38)	Oct (30)	Nov (26)	Dec (52)
2010	Jan (7)	Feb (91)	Mar (65)	Apr (2)	May (14)	Jun (25)	Jul (38)	Aug (48)	Sep (80)	Oct (70)	Nov (75)	Dec (77)
2011	Jan (68)	Feb (53)	Mar (51)	Apr (35)	May (65)	Jun (101)	Jul (29)	Aug (230)	Sep (95)	Oct (49)	Nov (110)	Dec (63)
2012	Jan (41)	Feb (42)	Mar (25)	Apr (46)	May (51)	Jun (44)	Jul (45)	Aug (29)	Sep (12)	Oct (9)	Nov (17)	Dec (2)
2013	Jan (12)	Feb (14)	Mar (7)	Apr (16)	May (54)	Jun (27)	Jul (11)	Aug (5)	Sep (85)	Oct (27)	Nov (37)	Dec (32)
2014	Jan (8)	Feb (29)	Mar (5)	Apr (3)	May (22)	Jun (3)	Jul (4)	Aug (3)	Sep	Oct	Nov	Dec

dl-learner-svn Mailing List for DL-Learner (Page 100)

dl-learner-svn — DL-Learner Subversion commits