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;
021
022 import java.util.Collection;
023 import java.util.HashMap;
024 import java.util.LinkedList;
025 import java.util.List;
026 import java.util.Map;
027
028 import org.dllearner.core.AbstractCELA;
029 import org.dllearner.core.AbstractLearningProblem;
030 import org.dllearner.core.AbstractReasonerComponent;
031 import org.dllearner.core.configurators.BruteForceLearnerConfigurator;
032 import org.dllearner.core.options.CommonConfigOptions;
033 import org.dllearner.core.options.ConfigEntry;
034 import org.dllearner.core.options.ConfigOption;
035 import org.dllearner.core.options.IntegerConfigOption;
036 import org.dllearner.core.options.InvalidConfigOptionValueException;
037 import org.dllearner.core.owl.Description;
038 import org.dllearner.core.owl.Intersection;
039 import org.dllearner.core.owl.NamedClass;
040 import org.dllearner.core.owl.Negation;
041 import org.dllearner.core.owl.Nothing;
042 import org.dllearner.core.owl.ObjectAllRestriction;
043 import org.dllearner.core.owl.ObjectProperty;
044 import org.dllearner.core.owl.ObjectSomeRestriction;
045 import org.dllearner.core.owl.Thing;
046 import org.dllearner.core.owl.Union;
047 import org.dllearner.learningproblems.EvaluatedDescriptionPosNeg;
048 import org.dllearner.learningproblems.ScorePosNeg;
049
050 /**
051 * A brute force learning algorithm.
052 *
053 * The algorithm works by generating all concepts starting with the shortest
054 * ones.
055 *
056 * @author Jens Lehmann
057 *
058 */
059 public class BruteForceLearner extends AbstractCELA {
060
061 private BruteForceLearnerConfigurator configurator;
062 @Override
063 public BruteForceLearnerConfigurator getConfigurator(){
064 return configurator;
065 }
066
067
068 private AbstractLearningProblem learningProblem;
069 private AbstractReasonerComponent rs;
070
071 private Description bestDefinition;
072 private ScorePosNeg bestScore;
073
074 //changing this wont have any effect any more
075 private Integer maxLength = 7;
076 private String returnType;
077
078 private boolean stop = false;
079 private boolean isRunning = false;
080
081 // list of all generated concepts sorted by length
082 private Map<Integer,List<Description>> generatedDefinitions = new HashMap<Integer,List<Description>>();
083
084 public BruteForceLearner(AbstractLearningProblem learningProblem, AbstractReasonerComponent rs) {
085 super(learningProblem, rs);
086 this.learningProblem = learningProblem;
087 this.rs = rs;
088 this.configurator = new BruteForceLearnerConfigurator(this);
089 }
090
091 public static String getName() {
092 return "brute force learning algorithm";
093 }
094
095 public static Collection<Class<? extends AbstractLearningProblem>> supportedLearningProblems() {
096 Collection<Class<? extends AbstractLearningProblem>> problems = new LinkedList<Class<? extends AbstractLearningProblem>>();
097 problems.add(AbstractLearningProblem.class);
098 return problems;
099 }
100
101 public static Collection<ConfigOption<?>> createConfigOptions() {
102 Collection<ConfigOption<?>> options = new LinkedList<ConfigOption<?>>();
103 options.add(new IntegerConfigOption("maxLength", "maximum length of generated concepts", 7));
104 options.add(CommonConfigOptions.getReturnType());
105 return options;
106 }
107
108 /* (non-Javadoc)
109 * @see org.dllearner.core.Component#applyConfigEntry(org.dllearner.core.ConfigEntry)
110 */
111 @Override
112 public <T> void applyConfigEntry(ConfigEntry<T> entry) throws InvalidConfigOptionValueException {
113 String name = entry.getOptionName();
114 if(name.equals("maxLength"))
115 maxLength = (Integer) entry.getValue();
116 else if(name.equals("returnType"))
117 returnType = (String) returnType;
118 }
119
120 // public Object getConfigValue(String optionName) throws UnknownConfigOptionException {
121 // if(optionName.equals("maxLength"))
122 // return maxLength;
123 // else
124 // throw new UnknownConfigOptionException(getClass(), optionName);
125 // }
126
127 /* (non-Javadoc)
128 * @see org.dllearner.core.Component#init()
129 */
130 @Override
131 public void init() {
132
133 }
134
135 @Override
136 public void start() {
137 isRunning = true;
138 // FlatABox abox = FlatABox.getInstance();
139
140 System.out.print("Generating definitions up to length " + maxLength + " ... ");
141 long generationStartTime = System.currentTimeMillis();
142
143 for(int i=1; i<=maxLength; i++)
144 generatePrograms(i);
145
146 if(stop)
147 return;
148
149 long generationTime = System.currentTimeMillis() - generationStartTime;
150 System.out.println("OK (" + generationTime + " ms)");
151
152 testGeneratedDefinitions(maxLength);
153
154 // System.out.println("test duration: " + testDuration + " ms");
155 System.out.println();
156 System.out.println("Best definition found: \n" + bestDefinition);
157
158 System.out.println();
159 System.out.println("Classification results:");
160 System.out.println(bestScore);
161 //System.out.println("false positives: " + Helper.intersection(bestDefPosSet,negExamples));
162 //System.out.println("false negatives: " + Helper.intersection(bestDefNegSet,posExamples));
163 //System.out.print("Score: " + bestScore + " Max: " + maxScore + " Difference: " + (maxScore-bestScore));
164 //System.out.println(" Accuracy: " + df.format((double)bestScore/maxScore*100) + "%");
165 isRunning = false;
166 }
167
168 private void testGeneratedDefinitions(int maxLength) {
169 long testStartTime = System.currentTimeMillis();
170 // maxScore = posExamples.size() + negExamples.size();
171 bestDefinition = generatedDefinitions.get(1).get(0);
172 double bestScorePoints = Double.NEGATIVE_INFINITY;
173 int overallCount = 0;
174 int count = 0;
175 ScorePosNeg tmp;
176 double score;
177
178 for(int i=1; i<=maxLength && !stop; i++) {
179 long startTime = System.currentTimeMillis();
180 System.out.print("Testing definitions of length " + i + " ... ");
181 count = 0;
182 for(Description program : generatedDefinitions.get(i)) {
183 // stop testing further when algorithm is stopped
184 if(stop)
185 break;
186
187 // if a return type is already given an appropriate tree is
188 // generated here
189 Description newRoot;
190 if(returnType != null) {
191 newRoot = new Intersection(new NamedClass(returnType),program);
192 } else
193 newRoot = program;
194
195 tmp = (ScorePosNeg) learningProblem.computeScore(newRoot);
196 score = tmp.getScoreValue();
197
198 // TODO: find termination criterion
199 if(score > bestScorePoints) {
200 bestDefinition = newRoot;
201 bestScorePoints = score;
202 bestScore = tmp;
203 }
204 count++;
205 }
206 long duration = System.currentTimeMillis() - startTime;
207 System.out.println(count + " definitions tested (" + duration + " ms)");
208 overallCount += count;
209 }
210
211 long testDuration = System.currentTimeMillis() - testStartTime;
212 System.out.println("Overall: " + overallCount + " definitions tested (" + testDuration + " ms)");
213 }
214
215 private void generatePrograms(int length) {
216 generatedDefinitions.put(length,new LinkedList<Description>());
217 if(length==1) {
218 generatedDefinitions.get(1).add(new Thing());
219 generatedDefinitions.get(1).add(new Nothing());
220 for(NamedClass atomicConcept : rs.getNamedClasses()) {
221 generatedDefinitions.get(1).add(atomicConcept);
222 }
223 }
224
225 if(length>1) {
226 // negation
227 for(Description childNode : generatedDefinitions.get(length-1)) {
228 Description root = new Negation(childNode);
229 generatedDefinitions.get(length).add(root);
230 }
231 }
232
233 // minimum length 3, otherwise conjunctions and disjunctions cannot be
234 // constructed
235 if(length>2) {
236 // choose conjunction or disjunction
237 for(int i=0; i<=1; i++) {
238 // let variable run from 1 to (length-1)/2 (rounded down)
239 // = length of left subtree
240 for(int z=1; z<=Math.floor(0.5*(length-1)); z++) {
241
242 // cycle through all concepts of length z (left subtree)
243 for(Description leftChild : generatedDefinitions.get(z)) {
244 // cycle thorugh all concept of lengt "length-z-1" (right subtree)
245 for(Description rightChild : generatedDefinitions.get(length-z-1)) {
246 // create concept tree
247 Description root;
248 if(i==0) {
249 root = new Union(leftChild,rightChild);
250 } else {
251 root = new Intersection(leftChild,rightChild);
252 }
253
254 // Please not that we only set links here, i.e.:
255 // 1. Every modification of a generated concept can influence
256 // other concepts.
257 // 2. It is not specified where the parent link of a concept
258 // points to, because one node can be child of several nodes.
259 //
260 // For the currently implemented reasoning algorithms this
261 // does not matter, because they do not modify concepts and
262 // do not care about the parent link.
263 //
264 // This way we save space (1 new concept in the brute force
265 // learner consumes space for only one tree node).
266 // root.addChild(leftChild);
267 // root.addChild(rightChild);
268 // System.out.println(root);
269
270 generatedDefinitions.get(length).add(root);
271 }
272 }
273 }
274 }
275
276 // EXISTS and ALL
277 for(Description childNode : generatedDefinitions.get(length-2)) {
278 for(ObjectProperty atomicRole : rs.getObjectProperties()) {
279 Description root1 = new ObjectSomeRestriction(atomicRole,childNode);
280 generatedDefinitions.get(length).add(root1);
281
282 Description root2 = new ObjectAllRestriction(atomicRole,childNode);
283 generatedDefinitions.get(length).add(root2);
284 }
285 }
286 }
287 }
288
289 // @Override
290 public ScorePosNeg getSolutionScore() {
291 return bestScore;
292 }
293
294 @Override
295 public Description getCurrentlyBestDescription() {
296 return bestDefinition;
297 }
298
299 @Override
300 public EvaluatedDescriptionPosNeg getCurrentlyBestEvaluatedDescription() {
301 return new EvaluatedDescriptionPosNeg(bestDefinition,bestScore);
302 }
303
304 @Override
305 public void stop() {
306 stop = true;
307 }
308
309 /* (non-Javadoc)
310 * @see org.dllearner.core.LearningAlgorithm#isRunning()
311 */
312 @Override
313 public boolean isRunning() {
314 return isRunning;
315 }
316
317 }