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.hybridgp;
021
022 import java.util.Random;
023 import java.util.Set;
024 import java.util.SortedMap;
025 import java.util.TreeMap;
026
027 import org.dllearner.algorithms.gp.Program;
028 import org.dllearner.core.AbstractReasonerComponent;
029 import org.dllearner.core.owl.Description;
030 import org.dllearner.learningproblems.PosNegLP;
031 import org.dllearner.learningproblems.ScorePosNeg;
032 import org.dllearner.refinementoperators.PsiDown;
033 import org.dllearner.refinementoperators.PsiUp;
034 import org.dllearner.utilities.owl.ConceptComparator;
035 import org.dllearner.utilities.owl.ConceptTransformation;
036
037 public class Psi implements GeneticRefinementOperator {
038
039 PsiUp pu;
040 PsiDown pd;
041 PosNegLP learningProblem;
042 int nrOfPositiveExamples;
043 int nrOfNegativeExamples;
044 Random random;
045
046 // Cache, damit keine Konzepte doppelt ausgewertet werden
047 ConceptComparator conceptComparator = new ConceptComparator();
048 public SortedMap<Description,ScorePosNeg> evalCache = new TreeMap<Description,ScorePosNeg>(conceptComparator);
049
050 // Cache, damit PsiDown bzw. PsiUp nicht mehrfach für gleiches Konzept
051 // aufgerufen werden
052 public SortedMap<Description,Set<Description>> pdCache = new TreeMap<Description,Set<Description>>(conceptComparator);
053 public SortedMap<Description,Set<Description>> puCache = new TreeMap<Description,Set<Description>>(conceptComparator);
054
055 // Statistiken
056 int conceptCacheHits = 0;
057 int nrOfRequests = 0;
058 int pdCacheHits = 0;
059 private long pdRequests = 0;
060 int puCacheHits = 0;
061 private long puRequests = 0;
062 private long psiApplicationStartTime = 0;
063 private long psiApplicationTimeNs = 0;
064 private long psiReasoningStartTime = 0;
065 private long psiReasoningTimeNs = 0;
066
067 @SuppressWarnings("unused")
068 private long someTimeStart = 0;
069 public long someTime = 0;
070
071 public Psi(PosNegLP learningProblem, AbstractReasonerComponent reasoningService) { //, PsiUp pu, PsiDown pd) {
072 // this.pu = pu;
073 // this.pd = pd;
074 this.learningProblem = learningProblem;
075 pu = new PsiUp(learningProblem, reasoningService);
076 pd = new PsiDown(learningProblem, reasoningService);
077 nrOfPositiveExamples = learningProblem.getPositiveExamples().size();
078 nrOfNegativeExamples = learningProblem.getNegativeExamples().size();
079 random = new Random();
080 }
081
082 public Description applyPsi(Description concept, int coveredPositives, int coveredNegatives) {
083 // Wahrscheinlichkeit für upward refinement berechnen
084 double tmp = coveredNegatives/(double)nrOfNegativeExamples;
085 double tmp2 = coveredPositives/(double)nrOfPositiveExamples;
086
087 double downwardProbability = tmp/(1+tmp-tmp2);
088
089 boolean debug = false;
090 if(debug) {
091 System.out.println("negative percentage covered: " + tmp);
092 System.out.println("positive percentage covered: " + tmp2);
093 // System.out.println("upward probability: upward")
094 }
095
096 if(downwardProbability<0 || downwardProbability>1) {
097
098 // bei Division gibt es Ungenauigkeit, so dass man einen kleinen
099 // Toleranzbereich lassen muss
100 if(downwardProbability < -0.0001)
101 throw new RuntimeException();
102 else if(downwardProbability > 1.0001)
103 throw new RuntimeException();
104 // Rundung auf korrekten Wert
105 else if(downwardProbability<0)
106 downwardProbability = 0d;
107 else
108 downwardProbability = 1d;
109 }
110
111 // System.out.println(upwardProbability);
112
113 boolean downward = (Math.random()<=downwardProbability);
114
115 // someTimeStart = System.nanoTime();
116 // downward oder upward refinement operator anwenden
117 Set<Description> refinements;
118 if(downward) {
119 pdRequests++;
120 // Cache aufrufen
121 refinements = pdCache.get(concept);
122 if(refinements == null) {
123 refinements = pd.refine(concept);
124 pdCache.put(concept, refinements);
125 } else
126 pdCacheHits++;
127 } else {
128 puRequests++;
129 refinements = puCache.get(concept);
130 if(refinements == null) {
131 refinements = pu.refine(concept);
132 puCache.put(concept, refinements);
133 } else
134 puCacheHits++;
135 }
136
137 /*
138 if(puRequests % 500 == 0 && !downward) {
139 System.out.println(concept);
140 for(Concept refinement : refinements)
141 System.out.println(" " + refinement);
142 }*/
143
144
145 // someTime += System.nanoTime() - someTimeStart;
146 // System.out.println(refinements.size());
147
148 String dir = "";
149 int prob = -1;
150 if(debug) {
151 if(downward) {
152 dir = "downward";
153 prob = (int) (100 * downwardProbability);
154 } else {
155 dir = "upward";
156 prob = (int) (100 * (1-downwardProbability));
157 }
158 }
159
160
161 // ein refinement zufällig auswählen
162 Description[] array = refinements.toArray(new Description[0]);
163 // kein refinement gefunden
164 if(array.length==0) {
165 if(debug) {
166 System.out.println("message: no " + dir + " refinement found for " + concept);
167 System.out.println();
168 }
169 // Konzept selbst wird zurückgegeben (also reproduction)
170 return concept;
171 }
172
173 int position = random.nextInt(array.length);
174 Description returnConcept = array[position];
175 ConceptTransformation.cleanConcept(returnConcept);
176
177 // das Rückgabekonzept wird geklont, damit alle parent-Links repariert
178 // werden (damit andere GP-Operatoren korrekt funktionieren)
179 Description returnConceptClone = (Description)returnConcept.clone();
180 returnConceptClone.setParent(null);
181
182 if(debug) {
183 System.out.println(concept + " " + dir + "("+prob+"%) to " + returnConcept);
184 System.out.println();
185 }
186
187 return returnConceptClone;
188 }
189
190 public Program applyOperator(Program program) {
191 psiApplicationStartTime = System.nanoTime();
192 nrOfRequests++;
193
194 Description concept = program.getTree();
195 // es muss sichergestellt sein, dass Konjunktionen nur als MultConjunctions
196 // vorhanden sind (analog bei Disjunktion) => effizienter wäre eine Auslagerung
197 // dieses Codes in die Konzepterzeugung, da die Transformation häufig nichts
198 // bringt; allerdings sollte GP noch kompatibel mit anderen Operatoren bleiben
199 // Concept conceptMod = ConceptTransformation.transformToMulti(concept);
200 // sicherstellen, dass Konstrukte wie NOT TOP, die momentan nicht vom
201 // Operator behandelt werden können, herausfallen (TODO: anschauen, ob es
202 // sich lohnt Operatoren zu definieren, die keine Negationsnormalform
203 // erfordern)
204
205 Description conceptMod = ConceptTransformation.transformToNegationNormalForm(concept);
206 // um mehr Cache Hits zu bekommen, wird noch vereinfach und geordnet
207
208
209 Description conceptModForCache = ConceptTransformation.applyEquivalenceRules(conceptMod);
210 ConceptTransformation.transformToOrderedForm(conceptModForCache, conceptComparator);
211
212 ScorePosNeg score = program.getScore();
213 // Eval-Cache füllen
214 evalCache.put(conceptModForCache, score);
215
216 // System.out.println("covered positives: " + score.getCoveredPositives());
217 // System.out.println("covered negatives: " + score.getCoveredNegatives());
218 int coveredPositives = score.getCoveredPositives().size();
219 int coveredNegatives = score.getCoveredNegatives().size();
220 // someTimeStart = System.nanoTime();
221 Description newConcept = applyPsi(conceptMod, coveredPositives, coveredNegatives);
222 ConceptTransformation.cleanConcept(newConcept);
223 // someTime += System.nanoTime() - someTimeStart;
224 // newConcept.setParent(null);
225
226 /////////// TESTCODE: umwandeln des erhaltenen Konzepts
227 // someTimeStart = System.nanoTime();
228 Description newConceptMod = ConceptTransformation.applyEquivalenceRules(newConcept);
229 ConceptTransformation.transformToOrderedForm(newConceptMod, conceptComparator);
230 // someTime += System.nanoTime() - someTimeStart;
231 ///////////
232
233 // versuchen Reasoner-Cache zu treffen
234 // Problem: Score hängt von Konzeptlänge ab!! => muss hier explizit
235 // reingerechnet werden
236 ScorePosNeg newScore = evalCache.get(newConceptMod);
237
238 if(newScore==null) {
239 psiReasoningStartTime = System.nanoTime();
240 newScore = (ScorePosNeg) learningProblem.computeScore(newConcept);
241 psiReasoningTimeNs += System.nanoTime() - psiReasoningStartTime;
242
243 evalCache.put(newConceptMod, newScore);
244 } else {
245 conceptCacheHits++;
246
247 // ToDo: es muss jetzt explizit ein neues Score-Objekt
248 // erzeugt werden, welches die geänderte Konzeptlänge
249 // berücksichtigt
250 newScore = newScore.getModifiedLengthScore(newConcept.getLength());
251 }
252
253 /*
254 if(nrOfRequests % 1000 == 0) {
255 System.out.println(concept);
256 System.out.println(newConcept);
257 }
258 */
259
260 Program newProgram = new Program(newScore, newConcept);
261 psiApplicationTimeNs += System.nanoTime() - psiApplicationStartTime;
262 return newProgram;
263 }
264
265 // gibt die GröÃe des Caches zurück (gutes Maà um zu sehen, ob überhaupt
266 // neue Konzepte erforscht werden)
267 public int getCacheSize() {
268 return evalCache.size();
269 }
270
271 public int getConceptCacheHits() {
272 return conceptCacheHits;
273 }
274
275 public int getNrOfRequests() {
276 return nrOfRequests;
277 }
278
279 public long getPsiApplicationTimeNs() {
280 return psiApplicationTimeNs;
281 }
282
283 public long getPsiReasoningTimeNs() {
284 return psiReasoningTimeNs;
285 }
286
287 public int getPdCacheHits() {
288 return pdCacheHits;
289 }
290
291 public int getPuCacheHits() {
292 return puCacheHits;
293 }
294
295 public long getPdRequests() {
296 return pdRequests;
297 }
298
299 public long getPuRequests() {
300 return puRequests;
301 }
302
303 public SortedMap<Description, Set<Description>> getPdCache() {
304 return pdCache;
305 }
306
307 public SortedMap<Description, Set<Description>> getPuCache() {
308 return puCache;
309 }
310
311 }