View Javadoc

1   /*
2    * Copyright (C) 2004-2006 Christian Siefkes <christian@siefkes.net>.
3    * Development of this software is supported by the German Research Society,
4    * Berlin-Brandenburg Graduate School in Distributed Information Systems
5    * (DFG grant no. GRK 316).
6    *
7    * This program is free software; you can redistribute it and/or modify
8    * it under the terms of the GNU General Public License as published by
9    * the Free Software Foundation; either version 2 of the License, or
10   * (at your option) any later version.
11   *
12   * This program is distributed in the hope that it will be useful,
13   * but WITHOUT ANY WARRANTY; without even the implied warranty of
14   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15   * GNU General Public License for more details.
16   *
17   * You should have received a copy of the GNU General Public License
18   * along with this program; if not, visit
19   * http://www.gnu.org/licenses/gpl.html or write to the Free Software
20   * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
21   */
22  package de.fu_berlin.ties.classify;
23  
24  import java.io.File;
25  import java.util.Set;
26  
27  import org.apache.commons.lang.ArrayUtils;
28  import org.apache.commons.lang.builder.ToStringBuilder;
29  
30  import de.fu_berlin.ties.ContextMap;
31  import de.fu_berlin.ties.ProcessingException;
32  import de.fu_berlin.ties.TiesConfiguration;
33  import de.fu_berlin.ties.classify.feature.FeatureTransformer;
34  import de.fu_berlin.ties.classify.feature.FeatureVector;
35  import de.fu_berlin.ties.filter.TrainableFilter;
36  import de.fu_berlin.ties.io.ObjectElement;
37  import de.fu_berlin.ties.util.Util;
38  
39  /***
40   * A meta classifier combines several layers of classifiers. For each layer
41   * (except the last one), there is a "judge" that decides whether or not the
42   * decision of this classifier is likely to be correct. If the judge decides
43   * that it is likely to be wrong, the next layer is invoked to correct the
44   * decision.
45   *
46   * <p><b>This classifier supports <em>only</em> error-driven training since it
47   * necessary to TOE train each classifier to decide whether to train the next
48   * one. Thus you always have to use the
49   * {@link #trainOnError(FeatureVector, String, Set)} method. Trying to
50   * call the {@link
51   * de.fu_berlin.ties.classify.TrainableClassifier#train(FeatureVector, String)}
52   * method instead will result in an
53   * {@link java.lang.UnsupportedOperationException}.</b>
54   *
55   * <p>Instances of this class are thread-safe if and only if instances of the
56   * wrapped classifier are.
57   *
58   * @author Christian Siefkes
59   * @version $Revision: 1.15 $, $Date: 2006/10/21 16:03:54 $, $Author: siefkes $
60   */
61  public class MetaClassifier extends TrainableClassifier {
62  
63      /***
64       * Key used to store the contexts of the inner classifiers.
65       */
66      private static final String KEY_INNER_CONTEXTS = "inner-context";
67  
68      /***
69       * Key used to store the prediction distributions returned by the inner
70       * classifiers.
71       */
72      private static final String KEY_INNER_DISTS = "inner-dist";
73  
74      /***
75       * Key used to store the contexts of the judges.
76       */
77      private static final String KEY_JUDGE_CONTEXTS = "judge-context";
78  
79      /***
80       * Key used to store the prediction distributions returned by jthe udges.
81       */
82      private static final String KEY_JUDGE_DISTS = "judge-dist";
83  
84      /***
85       * Key used to store the decisions made by the judges.
86       */
87      private static final String KEY_JUDGE_DECISIONS = "judge-decision";
88  
89  
90      /***
91       * The array of inner classifiers managed by this instance.
92       */
93      private final TrainableClassifier[] inner;
94  
95      /***
96       * The array of judges managed by this instance.
97       */
98      private final TrainableClassifier[] judges;
99  
100     /***
101      * Used the rerank the predictions of the judges.
102      */
103     private final Reranker judgeRerank;
104 
105     /***
106      * Creates a new instance.
107      *
108      * @param allValidClasses the set of all valid classes
109      * @param trans the last transformer in the transformer chain to use, or
110      * <code>null</code> if no feature transformers should be used
111      * @param runDirectory optional run directory passed to inner classifiers
112      * of the {@link ExternalClassifier} type
113      * @param innerSpec the specification used to initialize the inner
114      * classifiers, passed to the
115      * {@link TrainableClassifier#createClassifier(Set, File,
116      * FeatureTransformer, String[], TiesConfiguration)} factory method
117      * @param conf used to configure this instance and the inner classifiers
118      * @throws ProcessingException if an error occurred while creating this
119      * classifier or one of the wrapped classifiers
120      */
121     public MetaClassifier(final Set<String> allValidClasses,
122             final FeatureTransformer trans, final File runDirectory,
123             final String[] innerSpec, final TiesConfiguration conf)
124     throws ProcessingException {
125         // configure reranker from "classifier.meta" prefix
126         // (e.g. classifier.meta.bias.true = 1.01)
127         this(allValidClasses, trans, runDirectory, innerSpec,
128                 conf.getInt("classifier.meta.layers"),
129                 conf.getStringArray("classifier.meta.judge"),
130                 new Reranker(conf.subset("classifier.meta")),
131                 conf);
132     }
133 
134     /***
135      * Creates a new instance.
136      *
137      * @param allValidClasses the set of all valid classes
138      * @param trans the last transformer in the transformer chain to use, or
139      * <code>null</code> if no feature transformers should be used
140      * @param runDirectory optional run directory passed to inner classifiers
141      * of the {@link ExternalClassifier} type
142      * @param innerSpec the specification used to initialize the inner
143      * classifiers, passed to the
144      * {@link TrainableClassifier#createClassifier(Set, File,
145      * FeatureTransformer, String[], TiesConfiguration)} factory method
146      * @param layers the number of layers to use, must be at least one
147      * @param judgeSpec the specification used to initialize the judges,
148      * passed to the {@link TrainableClassifier#createClassifier(Set, File,
149      * FeatureTransformer, String[], TiesConfiguration)} factory method
150      * @param judgeReranker used the rerank the predictions of the judges;
151      * might be <code>null</code>
152      * @param conf used to configure this instance as well as the inner
153      * classifiers and judges
154      * @throws ProcessingException if an error occurred while creating this
155      * classifier or one of the wrapped classifiers
156      */
157     public MetaClassifier(final Set<String> allValidClasses,
158             final FeatureTransformer trans, final File runDirectory,
159             final String[] innerSpec, final int layers,
160             final String[] judgeSpec, final Reranker judgeReranker,
161             final TiesConfiguration conf)
162     throws ProcessingException {
163         super(allValidClasses, trans, conf);
164 
165         if (layers < 1) {
166             throw new IllegalArgumentException(
167                 "MetaClassifier requires at least 1 layer instead of "
168                     + layers);
169         }
170 
171         // init reranker
172         if (judgeReranker != null) {
173             judgeRerank = judgeReranker;
174         } else {
175             // create a dummy reranker that always returne the orig. dist.
176             judgeRerank = new Reranker();
177         }
178 
179         // init classifiers for each layer
180         inner = new TrainableClassifier[layers];
181         for (int i = 0; i < inner.length; i++) {
182             // Transformer is set to null because features shouldn't be
183             // transformed twice
184             inner[i] = TrainableClassifier.createClassifier(allValidClasses,
185                 runDirectory, null, innerSpec, conf);
186         }
187 
188         // init judges for each layer except the very last one
189         judges = new TrainableClassifier[layers - 1];
190         for (int i = 0; i < judges.length; i++) {
191             // Judges classify between "true" and "false".
192             // Transformer is set to null, as above
193             judges[i] = TrainableClassifier.createClassifier(
194                     TrainableFilter.BOOLEAN_CLASSES, runDirectory, null,
195                     judgeSpec, conf);
196         }
197     }
198 
199     /***
200      * {@inheritDoc}
201      */
202     public void destroy() throws ProcessingException {
203         // destroy all layers and judges
204         for (int i = 0; i < inner.length; i++) {
205             inner[i].destroy();
206         }
207         for (int i = 0; i < judges.length; i++) {
208             judges[i].destroy();
209         }
210     }
211 
212     /***
213      * {@inheritDoc}
214      */
215     protected PredictionDistribution doClassify(final FeatureVector features,
216             final Set candidateClasses, final ContextMap context)
217             throws ProcessingException {
218         // Used to populate the context
219         final PredictionDistribution[] innerDists =
220             new PredictionDistribution[inner.length];
221         final ContextMap[] innerContexts = new ContextMap[inner.length];
222         final PredictionDistribution[] origJudgeDists =
223             new PredictionDistribution[judges.length];
224         final ContextMap[] judgeContexts = new ContextMap[judges.length];
225         final boolean[] judgements = new boolean[judges.length];
226 
227         PredictionDistribution innerDist = null;
228         PredictionDistribution origJudgeDist, finalJudgeDist;
229         ContextMap innerContext, judgeContext;
230         boolean judgement = false;
231         int i = 0;
232 
233         // invoke inner classifier until judge trusts a decision to be correct
234         // or all layers are exhausted
235         while ((i < inner.length) && !judgement) {
236             if (i > 0) {
237                 Util.LOG.debug("Invoking layer " + i
238                         + " classifier since decision of previous layer was "
239                         + "judged to be incorrect");
240             }
241 
242             // invoke i-th inner classifier
243             innerContext = new ContextMap();
244             innerDist = inner[i].doClassify(features, candidateClasses,
245                     innerContext);
246             innerContexts[i] = innerContext;
247             innerDists[i] = innerDist;
248 
249             // call judge if available (not for last layer)
250             if (i < judges.length) {
251                 judgeContext = new ContextMap();
252                 origJudgeDist = judges[i].doClassify(features,
253                         judges[i].getAllClasses(), judgeContext);
254                 judgeContexts[i] = judgeContext;
255                 origJudgeDists[i] = origJudgeDist;
256                 finalJudgeDist = judgeRerank.rerank(origJudgeDist);
257 
258                 // convert best class to boolean
259                 judgement = Util.asBoolean(finalJudgeDist.best().getType());
260                 judgements[i] = judgement;
261             }
262 
263             i++;
264         }
265 
266         // store judgements, distributions, and contexts
267         context.put(KEY_INNER_CONTEXTS, innerContexts);
268         context.put(KEY_INNER_DISTS, innerDists);
269         context.put(KEY_JUDGE_CONTEXTS, judgeContexts);
270         context.put(KEY_JUDGE_DISTS, origJudgeDists);
271         context.put(KEY_JUDGE_DECISIONS, judgements);
272 
273         // return decision of last invoked layer
274         return innerDist;
275     }
276 
277     /***
278      * <b>This classifier supports <em>only</em> error-driven training, so you
279      * always have to use the {@link #trainOnError(FeatureVector, String, Set)}
280      * method instead of this one. Trying to call this method instead will
281      * result in an{@link java.lang.UnsupportedOperationException}.</b>
282      *
283      * @param features ignored by this method
284      * @param targetClass ignored by this method
285      * @param context ignored by this method
286      * @throws UnsupportedOperationException always thrown by this method;
287      * use {@link #trainOnError(FeatureVector, String, Set)} instead
288      */
289     protected void doTrain(final FeatureVector features,
290             final String targetClass, final ContextMap context)
291     throws UnsupportedOperationException {
292         // we cannot support this method because we need to TOE train each
293         // classifier to decide whether to train the next one
294         throw new UnsupportedOperationException("MetaClassifier supports only "
295             + "error-driven training -- call trainOnError instead of train");
296     }
297 
298     /***
299      * {@inheritDoc}
300      */
301     protected boolean doTrainOnError(final PredictionDistribution predDist,
302             final FeatureVector features, final String targetClass,
303             final Set candidateClasses, final ContextMap context)
304             throws ProcessingException {
305         // retrieve objects stored in context
306         final PredictionDistribution[] innerDists =
307             (PredictionDistribution[]) context.get(KEY_INNER_DISTS);
308         final ContextMap[] innerContexts =
309             (ContextMap[]) context.get(KEY_INNER_CONTEXTS);
310         final PredictionDistribution[] origJudgeDists =
311             (PredictionDistribution[]) context.get(KEY_JUDGE_DISTS);
312         final ContextMap[] judgeContexts =
313             (ContextMap[]) context.get(KEY_JUDGE_CONTEXTS);
314         final boolean[] judgements =
315             (boolean[]) context.get(KEY_JUDGE_DECISIONS);
316 
317         boolean innerShouldTrain = true;
318         int innerIndex = 0;
319 
320         // delegate to doTrainOnError method of each invoked classifier
321         for (; (innerIndex < innerDists.length)
322                 && (innerContexts[innerIndex] != null); innerIndex++) {
323             innerShouldTrain = inner[innerIndex].doTrainOnError(
324                     innerDists[innerIndex], features, targetClass,
325                     candidateClasses, innerContexts[innerIndex]);
326         }
327 
328         boolean classifierWasRight;
329         boolean judgeWasWrong = true;
330         int judgeIndex = 0;
331 
332         // delegate to doTrainOnError method of each invoked judge
333         for (; (judgeIndex < origJudgeDists.length)
334                 && (judgeContexts[judgeIndex] != null); judgeIndex++) {
335             // check if the classifier was right
336             // -- this is the target state for the judge
337             classifierWasRight =
338                 targetClass.equals(innerDists[judgeIndex].best().getType());
339             judgeWasWrong = (judgements[judgeIndex] != classifierWasRight);
340 
341             // log if judge misjudged the classifier
342             if (judgeWasWrong) {
343                 Util.LOG.debug("Judge misjudged the decision of layer "
344                         + judgeIndex + " to be " + judgements[judgeIndex]
345                         + " while it was " + classifierWasRight);
346             }
347 
348             judges[judgeIndex].doTrainOnError(origJudgeDists[judgeIndex],
349                     features, Boolean.toString(classifierWasRight),
350                     judges[judgeIndex].getAllClasses(),
351                     judgeContexts[judgeIndex]);
352         }
353 
354         // check if we have to train further layers
355         if (judgeWasWrong) {
356             PredictionDistribution newInnerDist, origJudgeDist, finalJudgeDist;
357             boolean judgement;
358             boolean done =  false;
359 
360             // if there are remaining layers and the last judge was wrong:
361             // invoke next layer + judge until a layer is correct AND judged
362             // to be correct or all layers are exhausted
363             if (innerIndex == judgeIndex) {
364                 for (; (innerIndex < inner.length) && !done; innerIndex++) {
365                     // delegate to trainOnError method of remaining classifier
366                     newInnerDist = inner[innerIndex].trainOnError(features,
367                             targetClass, candidateClasses);
368 
369                     // returned prediction distribution is null
370                     // iff classify was correct
371                     classifierWasRight = (newInnerDist == null);
372 
373                     // delegate to trainOnError method of corresponding judge,
374                     // if exists (not for last layer)
375                     if (innerIndex < judges.length) {
376                         origJudgeDist = judges[innerIndex].trainOnError(
377                                 features, Boolean.toString(classifierWasRight),
378                                 judges[innerIndex].getAllClasses());
379                         finalJudgeDist = judgeRerank.rerank(origJudgeDist);
380 
381                         // check whether the final judgement is accurate
382                         judgement =
383                             Util.asBoolean(finalJudgeDist.best().getType());
384                         judgeWasWrong = (judgement != classifierWasRight);
385 
386                         // we're done if a layer was correct
387                         // AND judged to be correct
388                         done = (classifierWasRight && !judgeWasWrong);
389 
390                         // log if done or if  judge misjudged the classifier
391                         if (done) {
392                             Util.LOG.debug("MetaClassifier: training is done "
393                                     + "since judge correctly judged the "
394                                     + "decision of layer " + innerIndex
395                                     + " to be correct");
396                         }
397                         if (judgeWasWrong) {
398                             Util.LOG.debug("Additional training: "
399                                     + "Judge misjudged the decision of layer "
400                                     + innerIndex + " to be " + judgement
401                                     + " while it was " + classifierWasRight);
402                         }
403                     }
404                 }
405             } else {
406                 // no judge for last invoked classifier: should better be last
407                 // layer, otherwise something would be very wrong
408                 if (!((innerIndex == inner.length)
409                         && (judgeIndex == judges.length))) {
410                     throw new RuntimeException(
411                             "Implementation error: classify invoked "
412                             + innerIndex + " layers but " + judgeIndex
413                             + " judges");
414                 }
415             }
416         } else {
417             // last judge was right
418             Util.LOG.debug("MetaClassifier: No need for further training since"
419                     + " decision of last queried judge " + (judgeIndex - 1)
420                     + " was correct");
421         }
422 
423         // return shouldTrain statement of last inner classifier invoked during
424         // classification
425         return innerShouldTrain;
426     }
427 
428     /***
429      * {@inheritDoc}
430      */
431     public void reset() throws ProcessingException {
432         // reset all layers and judges
433         for (int i = 0; i < inner.length; i++) {
434             inner[i].reset();
435         }
436         for (int i = 0; i < judges.length; i++) {
437             judges[i].reset();
438         }
439     }
440 
441     /***
442      * {@inheritDoc}
443      */
444     protected boolean shouldTrain(final String targetClass,
445             final PredictionDistribution predDist, final ContextMap context) {
446         // method should never be called since is not used by doTrainOnError
447         throw new UnsupportedOperationException("MetaClassifier: "
448                 + "shouldTrain is not required and thus not supported");
449     }
450 
451     /***
452      * {@inheritDoc} Currently, this classifier does not support XML
453      * serialization, throwing an {@link UnsupportedOperationException} instead.
454      *
455      * @throws UnsupportedOperationException always thrown by this
456      * implementation
457      */
458     public ObjectElement toElement() throws UnsupportedOperationException {
459             throw new UnsupportedOperationException(
460                     "XML serialization is not supported by MetaClassifier");
461     }
462 
463     /***
464      * Returns a string representation of this object.
465      *
466      * @return a textual representation
467      */
468     public String toString() {
469         return new ToStringBuilder(this)
470             .appendSuper(super.toString())
471             .append("inner classifiers", ArrayUtils.toString(inner))
472             .append("judges", ArrayUtils.toString(judges))
473             .toString();
474     }
475 
476     /***
477      * {@inheritDoc}
478      */
479     protected boolean trainOnErrorHook(final PredictionDistribution predDist,
480             final FeatureVector features, final String targetClass,
481             final Set candidateClasses, final ContextMap context) {
482         // method should never be called since is not used by doTrainOnError
483         throw new UnsupportedOperationException("MetaClassifier: "
484                 + "trainOnErrorHook is not required and thus not supported");
485     }
486 
487 }