001 /**
002 * Copyright (C) 2007-2011, Jens Lehmann
003 *
004 * This file is part of DL-Learner.
005 *
006 * DL-Learner is free software; you can redistribute it and/or modify
007 * it under the terms of the GNU General Public License as published by
008 * the Free Software Foundation; either version 3 of the License, or
009 * (at your option) any later version.
010 *
011 * DL-Learner is distributed in the hope that it will be useful,
012 * but WITHOUT ANY WARRANTY; without even the implied warranty of
013 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
014 * GNU General Public License for more details.
015 *
016 * You should have received a copy of the GNU General Public License
017 * along with this program. If not, see <http://www.gnu.org/licenses/>.
018 */
019
020 package org.dllearner.algorithms.el;
021
022 import java.util.Collection;
023 import java.util.LinkedList;
024 import java.util.List;
025 import java.util.TreeSet;
026
027 import org.apache.log4j.Logger;
028 import org.dllearner.core.ComponentInitException;
029 import org.dllearner.core.EvaluatedDescription;
030 import org.dllearner.core.AbstractCELA;
031 import org.dllearner.core.AbstractLearningProblem;
032 import org.dllearner.core.AbstractReasonerComponent;
033 import org.dllearner.core.configurators.Configurator;
034 import org.dllearner.core.configurators.ELLearningAlgorithmConfigurator;
035 import org.dllearner.core.options.CommonConfigOptions;
036 import org.dllearner.core.options.ConfigOption;
037 import org.dllearner.core.owl.Description;
038 import org.dllearner.core.owl.Thing;
039 import org.dllearner.learningproblems.EvaluatedDescriptionPosNeg;
040 import org.dllearner.learningproblems.PosNegLP;
041 import org.dllearner.learningproblems.ScorePosNeg;
042 import org.dllearner.refinementoperators.ELDown2;
043 import org.dllearner.utilities.owl.EvaluatedDescriptionSet;
044
045 /**
046 * A learning algorithm for EL, which will be based on a (hopefully)
047 * ideal refinement operator.
048 *
049 * TODO redundancy check
050 *
051 * @author Jens Lehmann
052 *
053 */
054 public class ELLearningAlgorithm extends AbstractCELA {
055
056 private static Logger logger = Logger.getLogger(ELLearningAlgorithm.class);
057 private ELLearningAlgorithmConfigurator configurator;
058
059 private ELDown2 operator;
060
061 private boolean isRunning = false;
062 private boolean stop = false;
063
064 private double treeSearchTimeSeconds = 1.0;
065 private long treeStartTime;
066
067 // a set with limited size (currently the ordering is defined in the class itself)
068 private EvaluatedDescriptionSet bestEvaluatedDescriptions = new EvaluatedDescriptionSet(AbstractCELA.MAX_NR_OF_RESULTS);
069
070 private SearchTreeNode startNode;
071 private ELHeuristic heuristic;
072 private TreeSet<SearchTreeNode> candidates;
073
074 public ELLearningAlgorithm(PosNegLP problem, AbstractReasonerComponent reasoner) {
075 super(problem, reasoner);
076 configurator = new ELLearningAlgorithmConfigurator(this);
077 }
078
079 public static String getName() {
080 return "standard EL learning algorithm";
081 }
082
083 public static Collection<Class<? extends AbstractLearningProblem>> supportedLearningProblems() {
084 Collection<Class<? extends AbstractLearningProblem>> problems = new LinkedList<Class<? extends AbstractLearningProblem>>();
085 problems.add(PosNegLP.class);
086 return problems;
087 }
088
089 // we can assume a PosNegLP, because it is the only supported one
090 private PosNegLP getLearningProblem() {
091 return (PosNegLP) learningProblem;
092 }
093
094 @Override
095 public ELLearningAlgorithmConfigurator getConfigurator() {
096 return configurator;
097 }
098
099 public static Collection<ConfigOption<?>> createConfigOptions() {
100 Collection<ConfigOption<?>> options = new LinkedList<ConfigOption<?>>();
101 // options.add(CommonConfigOptions.getNoisePercentage());
102 // options.add(new StringConfigOption("startClass", "the named class which should be used to start the algorithm (GUI: needs a widget for selecting a class)"));
103 options.add(CommonConfigOptions.getInstanceBasedDisjoints());
104 return options;
105 }
106
107 @Override
108 public void init() throws ComponentInitException {
109 // currently we use the stable heuristic
110 heuristic = new StableHeuristic();
111 candidates = new TreeSet<SearchTreeNode>(heuristic);
112
113 operator = new ELDown2(reasoner, configurator.getInstanceBasedDisjoints());
114 }
115
116 @Override
117 public void start() {
118 stop = false;
119 isRunning = true;
120 reset();
121 treeStartTime = System.nanoTime();
122
123 // create start node
124 ELDescriptionTree top = new ELDescriptionTree(reasoner, Thing.instance);
125 addDescriptionTree(top, null);
126
127 // main loop
128 int loop = 0;
129 while(!stop && !stoppingCriteriaSatisfied()) {
130 // pick the best candidate according to the heuristic
131 SearchTreeNode best = candidates.pollLast();
132 // apply operator
133 List<ELDescriptionTree> refinements = operator.refine(best.getDescriptionTree());
134 // add all refinements to search tree, candidates, best descriptions
135 for(ELDescriptionTree refinement : refinements) {
136 // System.out.println("refinement: " + refinement);
137 addDescriptionTree(refinement, best);
138 }
139 loop++;
140 // logging
141 if(logger.isTraceEnabled()) {
142 logger.trace("Choosen node " + best);
143 logger.trace(startNode.getTreeString());
144 logger.trace("Loop " + loop + " completed.");
145 }
146 }
147
148 // print solution(s)
149 logger.info("solution : " + bestEvaluatedDescriptions.getBest());
150
151 isRunning = false;
152 }
153
154 // evaluates a description in tree form
155 private void addDescriptionTree(ELDescriptionTree descriptionTree, SearchTreeNode parentNode) {
156
157 // create search tree node
158 SearchTreeNode node = new SearchTreeNode(descriptionTree);
159
160 // convert tree to standard description
161 Description description = descriptionTree.transformToDescription();
162
163 // double accuracy = getLearningProblem().getAccuracyOrTooWeak(description, 0);
164 int negCovers = getLearningProblem().coveredNegativeExamplesOrTooWeak(description);
165 if(negCovers == -1) {
166 // if(accuracy == -1) {
167 node.setTooWeak();
168 } else {
169 node.setCoveredNegatives(negCovers);
170 }
171
172 // link to parent (unless start node)
173 if(parentNode == null) {
174 startNode = node;
175 } else {
176 parentNode.addChild(node);
177 }
178
179 // System.out.println("TEST");
180
181 if(!node.isTooWeak()) {
182 // add as candidate
183 candidates.add(node);
184
185 // System.out.println("TEST2");
186
187 // check whether we want to add it to the best evaluated descriptions;
188 // to do this we pick the worst considered evaluated description
189 // (remember that the set has limited size, so it's likely not the worst overall);
190 // the description has a chance to make it in the set if it has
191 // at least as high accuracy - if not we can save the reasoner calls
192 // for fully computing the evaluated description
193 if(bestEvaluatedDescriptions.size() == 0 || ((EvaluatedDescriptionPosNeg)bestEvaluatedDescriptions.getWorst()).getCoveredNegatives().size() >= node.getCoveredNegatives()) {
194 ScorePosNeg score = (ScorePosNeg) learningProblem.computeScore(description);
195 EvaluatedDescriptionPosNeg ed = new EvaluatedDescriptionPosNeg(description, score);
196 bestEvaluatedDescriptions.add(ed);
197 }
198
199 }
200
201 }
202
203 private boolean stoppingCriteriaSatisfied() {
204 // in some cases, there could be no candidate left ...
205 if(candidates.isEmpty()) {
206 // System.out.println("EMPTY");
207 return true;
208 }
209
210 // stop when max time is reached
211 long runTime = System.nanoTime() - treeStartTime;
212 double runTimeSeconds = runTime / (double) 1000000000;
213
214 if(runTimeSeconds >= treeSearchTimeSeconds) {
215 return true;
216 }
217
218 // stop if we have a node covering all positives and none of the negatives
219 SearchTreeNode bestNode = candidates.last();
220 return (bestNode.getCoveredNegatives() == 0);
221 }
222
223 private void reset() {
224 // set all values back to their default values (used for running
225 // the algorithm more than once)
226 candidates.clear();
227 bestEvaluatedDescriptions.getSet().clear();
228 }
229
230 @Override
231 public void stop() {
232 stop = true;
233 }
234
235 @Override
236 public boolean isRunning() {
237 return isRunning;
238 }
239
240 @Override
241 public Description getCurrentlyBestDescription() {
242 return getCurrentlyBestEvaluatedDescription().getDescription();
243 }
244
245 @Override
246 public List<Description> getCurrentlyBestDescriptions() {
247 return bestEvaluatedDescriptions.toDescriptionList();
248 }
249
250 @Override
251 public EvaluatedDescription getCurrentlyBestEvaluatedDescription() {
252 return bestEvaluatedDescriptions.getSet().last();
253 }
254
255 @Override
256 public TreeSet<? extends EvaluatedDescription> getCurrentlyBestEvaluatedDescriptions() {
257 return bestEvaluatedDescriptions.getSet();
258 }
259
260 /**
261 * @return the startNode
262 */
263 public SearchTreeNode getStartNode() {
264 return startNode;
265 }
266
267 }