1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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
126
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
172 if (judgeReranker != null) {
173 judgeRerank = judgeReranker;
174 } else {
175
176 judgeRerank = new Reranker();
177 }
178
179
180 inner = new TrainableClassifier[layers];
181 for (int i = 0; i < inner.length; i++) {
182
183
184 inner[i] = TrainableClassifier.createClassifier(allValidClasses,
185 runDirectory, null, innerSpec, conf);
186 }
187
188
189 judges = new TrainableClassifier[layers - 1];
190 for (int i = 0; i < judges.length; i++) {
191
192
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
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
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
234
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
243 innerContext = new ContextMap();
244 innerDist = inner[i].doClassify(features, candidateClasses,
245 innerContext);
246 innerContexts[i] = innerContext;
247 innerDists[i] = innerDist;
248
249
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
259 judgement = Util.asBoolean(finalJudgeDist.best().getType());
260 judgements[i] = judgement;
261 }
262
263 i++;
264 }
265
266
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
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
293
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
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
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
333 for (; (judgeIndex < origJudgeDists.length)
334 && (judgeContexts[judgeIndex] != null); judgeIndex++) {
335
336
337 classifierWasRight =
338 targetClass.equals(innerDists[judgeIndex].best().getType());
339 judgeWasWrong = (judgements[judgeIndex] != classifierWasRight);
340
341
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
355 if (judgeWasWrong) {
356 PredictionDistribution newInnerDist, origJudgeDist, finalJudgeDist;
357 boolean judgement;
358 boolean done = false;
359
360
361
362
363 if (innerIndex == judgeIndex) {
364 for (; (innerIndex < inner.length) && !done; innerIndex++) {
365
366 newInnerDist = inner[innerIndex].trainOnError(features,
367 targetClass, candidateClasses);
368
369
370
371 classifierWasRight = (newInnerDist == null);
372
373
374
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
382 judgement =
383 Util.asBoolean(finalJudgeDist.best().getType());
384 judgeWasWrong = (judgement != classifierWasRight);
385
386
387
388 done = (classifierWasRight && !judgeWasWrong);
389
390
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
407
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
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
424
425 return innerShouldTrain;
426 }
427
428 /***
429 * {@inheritDoc}
430 */
431 public void reset() throws ProcessingException {
432
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
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
483 throw new UnsupportedOperationException("MetaClassifier: "
484 + "trainOnErrorHook is not required and thus not supported");
485 }
486
487 }