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.eval;
23
24 import java.io.File;
25 import java.io.IOException;
26 import java.io.Reader;
27 import java.io.Writer;
28 import java.util.Collection;
29 import java.util.HashSet;
30 import java.util.Iterator;
31 import java.util.LinkedHashMap;
32 import java.util.Set;
33 import java.util.SortedSet;
34 import java.util.TreeSet;
35
36 import org.apache.commons.collections.Bag;
37 import org.apache.commons.collections.bag.HashBag;
38 import org.dom4j.Document;
39 import org.dom4j.DocumentException;
40
41 import de.fu_berlin.ties.Closeable;
42 import de.fu_berlin.ties.ContextMap;
43 import de.fu_berlin.ties.ProcessingException;
44 import de.fu_berlin.ties.TextProcessor;
45 import de.fu_berlin.ties.TiesConfiguration;
46 import de.fu_berlin.ties.eval.Mistake.MistakeTypes;
47 import de.fu_berlin.ties.extract.EvaluatedExtractionContainer;
48 import de.fu_berlin.ties.extract.Extraction;
49 import de.fu_berlin.ties.extract.ExtractionContainer;
50 import de.fu_berlin.ties.extract.ExtractionMatcher;
51 import de.fu_berlin.ties.extract.TargetStructure;
52 import de.fu_berlin.ties.io.FieldContainer;
53 import de.fu_berlin.ties.io.IOUtils;
54 import de.fu_berlin.ties.preprocess.PreProcessor;
55 import de.fu_berlin.ties.util.MultiValueMap;
56 import de.fu_berlin.ties.util.Util;
57 import de.fu_berlin.ties.xml.dom.DOMUtils;
58
59 /***
60 * Reads an {@link de.fu_berlin.ties.extract.EvaluatedExtractionContainer}
61 * (in DSV format) and analyses the types of prediction errors that occurred.
62 * Detects misplaced borders (early or late start or end), type confusion
63 * (e.g. "end-time" instead of "start-time") and some other kinds of errors.
64 *
65 * <p>Neads access to the preprocessed ("augmented") input files. The directory
66 * containing these files can the specified using the {@link #CONFIG_AUG_DIR}
67 * configuration key.
68 *
69 * <p>Instances of this type are <em>not</em> thread-safe.
70 *
71 * @author Christian Siefkes
72 * @version $Revision: 1.20 $, $Date: 2006/10/21 16:04:11 $, $Author: siefkes $
73 */
74 public class MistakeAnalyzer extends TextProcessor implements Closeable {
75
76 /***
77 * Configuration key: the directory containing the augmented (preprocessed)
78 * input texts, relative to the current working directory.
79 */
80 public static final String CONFIG_AUG_DIR = "analyzer.aug-dir";
81
82 /***
83 * Stores all analyzed results, mapped from the local name. Used by the
84 * {@link #close(int)} method to print statistics.
85 */
86 private final LinkedHashMap<String, MistakeMatrix> allResults =
87 new LinkedHashMap<String, MistakeMatrix>();
88
89 /***
90 * The directory containing the augmented (preprocessed) input texts.
91 */
92 private final File augDir;
93
94 /***
95 * Whether all answer keys should have been matched or only the best one,
96 * see {@link EvaluatedExtractionContainer#isMatchingAll()}.
97 */
98 private final boolean matchAll;
99
100 /***
101 * The set of extraction types for which a correction prediction was made
102 * (within the current {@link #source} document).
103 */
104 private final Set<String> correctTypes = new HashSet<String>();
105
106 /***
107 * Matcher for answer keys and predictions.
108 */
109 private final ExtractionMatcher extMatcher;
110
111 /***
112 * The latest answer key that has been involved in a mistake.
113 */
114 private Extraction latestHandledAnsKey = null;
115
116 /***
117 * The latest prediction that has been involved in a mistake.
118 */
119 private Extraction latestHandledPred = null;
120
121 /***
122 * Keeps track of the mistakes encountered.
123 */
124 private MistakeMatrix matrix = null;
125
126 /***
127 * The {@linkplain de.fu_berlin.ties.classify.Prediction#getSource() source}
128 * document which is currently analyzed.
129 */
130 private String source = null;
131
132 /***
133 * Creates a new instance, using a default extension and the
134 * {@linkplain TiesConfiguration#CONF standard configuration}.
135 */
136 public MistakeAnalyzer() {
137 this("mistakes");
138 }
139
140 /***
141 * Creates a new instance, using the
142 * {@linkplain TiesConfiguration#CONF standard configuration}.
143 *
144 * @param outExt the extension to use for output files
145 */
146 public MistakeAnalyzer(final String outExt) {
147 this(outExt, TiesConfiguration.CONF);
148 }
149
150 /***
151 * Creates a new instance.
152 *
153 * @param outExt the extension to use for output files
154 * @param conf the configuration to use
155 */
156 public MistakeAnalyzer(final String outExt, final TiesConfiguration conf) {
157 super(outExt, conf);
158 augDir = new File(conf.getString(CONFIG_AUG_DIR));
159 extMatcher = new ExtractionMatcher(conf);
160 matchAll = conf.getBoolean(
161 EvaluatedExtractionContainer.CONFIG_MATCH_ALL);
162 }
163
164
165 /***
166 * Analyses a batch of predictions and answer keys for a specific source
167 * file, determining the types of mistakes that occurred.
168 *
169 * @param predictions the container of predicted extractions
170 * @param answers the container of expected extractions (answer keys)
171 * @param batchSource the
172 * {@linkplain de.fu_berlin.ties.classify.Prediction#getSource() source}
173 * of extractions of this batch
174 * @throws IOException if an I/O error occurs while reading the source (AUG)
175 * file
176 * @throws ProcessingException if an error occurs during processing
177 */
178 public void analyzeBatch(final ExtractionContainer predictions,
179 final ExtractionContainer answers, final String batchSource)
180 throws IOException, ProcessingException {
181 source = batchSource;
182 final File augFile = new File(augDir,
183 source + '.' + PreProcessor.FILE_EXT);
184 final Document augDoc;
185
186 try {
187
188 augDoc = DOMUtils.readDocument(augFile, getConfig());
189 } catch (DocumentException de) {
190
191 throw new ProcessingException(de);
192 }
193
194 ExtractionContainer myPredictions;
195
196 if (!matchAll) {
197
198
199
200
201 myPredictions = discardCorrectTypes(predictions, "predictions");
202 } else {
203 myPredictions = predictions;
204 }
205
206
207
208 myPredictions = extMatcher.matchAndOrderExtractions(myPredictions,
209 augDoc);
210
211 final ExtractionContainer myAnswers =
212 extMatcher.matchAndOrderExtractions(answers, augDoc);
213 final Iterator<Extraction> predIter = myPredictions.iterator();
214 final Iterator<Extraction> ansIter = myAnswers.iterator();
215 Extraction prediction = predIter.hasNext() ? predIter.next() : null;
216 Extraction answerKey = ansIter.hasNext() ? ansIter.next() : null;
217
218
219 while ((prediction != null) || (answerKey != null)) {
220 if ((prediction != null) && (answerKey != null)) {
221 if (answerKey.getLastIndex() <= prediction.getLastIndex()) {
222
223 if (prediction.getIndex() <= answerKey.getLastIndex()) {
224
225 handleAnswerKey(answerKey, prediction);
226 } else {
227 handleAnswerKey(answerKey, null);
228 }
229
230
231 answerKey = ansIter.hasNext() ? ansIter.next() : null;
232 } else {
233
234 if (answerKey.getIndex() <= prediction.getLastIndex()) {
235
236 handlePrediction(prediction, answerKey);
237 } else {
238 handlePrediction(prediction, null);
239 }
240
241
242 prediction = predIter.hasNext() ? predIter.next() : null;
243 }
244 } else if (answerKey != null) {
245
246 handleAnswerKey(answerKey, null);
247 answerKey = ansIter.hasNext() ? ansIter.next() : null;
248 } else {
249
250 handlePrediction(prediction, null);
251 prediction = predIter.hasNext() ? predIter.next() : null;
252 }
253 }
254 }
255
256 /***
257 * Analyses an evaluated extraction container, determining the types of
258 * mistakes that occurred.
259 *
260 * @param extractions the container of evaluated extractions
261 * @param localName how to refer to this run (will be used for statistics
262 * calculated by the {@link #close(int)} method)
263 * @return a {@link MistakeMatrix} giving details and statistics on the
264 * mistakes that occured
265 * @throws IOException if an I/O error occurs while reading the source (AUG)
266 * file
267 * @throws ProcessingException if an error occurs during processing
268 */
269 public MistakeMatrix analyzeMistakes(final ExtractionContainer extractions,
270 final String localName)
271 throws IOException, ProcessingException {
272
273
274 final MultiValueMap<String, Extraction> batchMap =
275 new MultiValueMap<String, Extraction>(new
276 LinkedHashMap<String, Collection<Extraction>>());
277 final Iterator extIter = extractions.iterator();
278 Extraction currentExt;
279
280 while (extIter.hasNext()) {
281 currentExt = (Extraction) extIter.next();
282 batchMap.put(currentExt.getSource(), currentExt);
283 }
284
285 ExtractionContainer currentPredictions;
286 ExtractionContainer currentAnswers;
287 final Iterator<String> batchIter = batchMap.keySet().iterator();
288 String currentSource;
289 Collection<Extraction> currentColl;
290 Iterator<Extraction> collIter;
291 EvalStatus currentStatus;
292 matrix = new MistakeMatrix();
293
294
295 while (batchIter.hasNext()) {
296 currentSource = batchIter.next();
297 currentColl = batchMap.get(currentSource);
298 currentPredictions =
299 new ExtractionContainer(extractions.getTargetStructure());
300 currentAnswers =
301 new ExtractionContainer(extractions.getTargetStructure());
302 collIter = currentColl.iterator();
303 correctTypes.clear();
304
305 while (collIter.hasNext()) {
306 currentExt = collIter.next();
307 currentStatus = currentExt.getEvalStatus();
308
309 if ((currentStatus == EvalStatus.CORRECT)) {
310
311 correctTypes.add(currentExt.getType());
312 } else {
313
314 if ((currentStatus == EvalStatus.TRUTH)
315 || (currentStatus == EvalStatus.UNKNOWN)) {
316
317 Util.LOG.warn("Unexpected eval status " + currentStatus
318 + " of " + currentExt);
319 } else if (currentStatus.isAnswerState()) {
320 currentAnswers.add(currentExt);
321 } else if (currentStatus.isPredictionState()) {
322 currentPredictions.add(currentExt);
323 }
324 }
325 }
326
327
328 analyzeBatch(currentPredictions, currentAnswers, currentSource);
329 }
330
331
332 allResults.put(IOUtils.getBaseName(localName), matrix);
333 return matrix;
334 }
335
336 /***
337 * Analyses an serialized contents of an evaluated extraction container
338 * and determines the types of mistakes that occurred,
339 * delegating to
340 * {@link #analyzeMistakes(ExtractionContainer, String)}.
341 *
342 * @param reader reader containg the extractions to analyse in
343 * {@link de.fu_berlin.ties.io.DelimSepValues} format; not closed by this
344 * method
345 * @param localName how to refer to this run (will be used for statistics
346 * calculated by the {@link #close(int)} method)
347 * @return a {@link MistakeMatrix} giving details and statistics on the
348 * mistakes that occured
349 * @throws IOException if an I/O error occurs while reading the extractions
350 * or a corresponding the source (AUG) file
351 * @throws ProcessingException if an error occurs during processing
352 */
353 public MistakeMatrix analyzeMistakes(final Reader reader,
354 final String localName)
355 throws IOException, ProcessingException {
356
357 final FieldContainer fContainer =
358 FieldContainer.createFieldContainer(getConfig());
359 fContainer.read(reader);
360 final ExtractionContainer extraction =
361 new ExtractionContainer(new TargetStructure(getConfig()),
362 fContainer);
363 return analyzeMistakes(extraction, localName);
364 }
365
366 /***
367 * {@inheritDoc}
368 */
369 public void close(final int errorCount) throws IOException {
370 if (errorCount == 0) {
371
372
373 final Iterator<String> resultsIter = allResults.keySet().iterator();
374 String name;
375 MistakeMatrix currentMatrix;
376 final ValueSummary mistakeStats = new ValueSummary();
377 final ValueSummary mistakeCombiStats = new ValueSummary();
378 final ValueSummary exactConfusionStats = new ValueSummary();
379 final ValueSummary roughConfusionStats = new ValueSummary();
380
381 while (resultsIter.hasNext()) {
382 name = resultsIter.next();
383 currentMatrix = allResults.get(name);
384 mistakeStats.add(name, currentMatrix.viewMistakeCount());
385 mistakeCombiStats.add(name,
386 currentMatrix.viewMistakeCombinationCount());
387 roughConfusionStats.add(name,
388 currentMatrix.viewRoughConfusionMatrix());
389 exactConfusionStats.add(name,
390 currentMatrix.viewExactConfusionMatrix());
391 }
392
393
394 final File outDir = IOUtils.determineOutputDirectory(getConfig());
395 final File mistakeFile = FieldContainer.storeContainerInFile(
396 mistakeStats, outDir, "mistakes", "count", getConfig());
397 final File mistakeCombiFile = FieldContainer.storeContainerInFile(
398 mistakeCombiStats, outDir, "mistakes", "combined",
399 getConfig());
400 final File roughConfusionFile = FieldContainer.storeContainerInFile(
401 roughConfusionStats, outDir, "confusion-matrix", "rough",
402 getConfig());
403 final File exactConfusionFile = FieldContainer.storeContainerInFile(
404 exactConfusionStats, outDir, "confusion-matrix", "exact",
405 getConfig());
406
407 Util.LOG.info("Stored mistake counts in " + mistakeFile + " and "
408 + mistakeCombiFile + "; confusion matrix in "
409 + roughConfusionFile + " and " + exactConfusionFile);
410 }
411 }
412
413 /***
414 * Copies all predictions from given extraction container to another one,
415 * except for those whose types are given in the {@link #correctTypes} set.
416 *
417 * @param orgExtractions the original container of extractions to process
418 * @param logName how to refer to the extractions (used for logging)
419 * @return a new container containing all extractions from the original
420 * container <em>except</em> those whose types are listed in the
421 * {@link #correctTypes} set
422 */
423 private ExtractionContainer discardCorrectTypes(
424 final ExtractionContainer orgExtractions, final String logName) {
425 final ExtractionContainer result =
426 new ExtractionContainer(orgExtractions.getTargetStructure());
427 final Iterator<Extraction> extIter = orgExtractions.iterator();
428 final Bag discardCount = new HashBag();
429 Extraction ext;
430 String extType;
431
432 while (extIter.hasNext()) {
433 ext = extIter.next();
434 extType = ext.getType();
435
436 if (correctTypes.contains(extType)) {
437
438 discardCount.add(extType);
439 } else {
440 result.add(ext);
441 }
442 }
443
444
445 final StringBuffer msg = new StringBuffer("Discarded ").append(logName)
446 .append(" from ").append(source).append(": ");
447 final Iterator<String> typeIter = correctTypes.iterator();
448 String type;
449
450 while (typeIter.hasNext()) {
451 type = typeIter.next();
452 msg.append(Integer.toString(discardCount.getCount(type)))
453 .append("*").append(type);
454
455 if (typeIter.hasNext()) {
456 msg.append(", ");
457 }
458 }
459 Util.LOG.debug(msg.toString());
460
461 return result;
462 }
463
464 /***
465 * {@inheritDoc}
466 */
467 protected void doProcess(final Reader reader, final Writer writer,
468 final ContextMap context) throws IOException, ProcessingException {
469
470 final String localName = (String) context.get(KEY_LOCAL_NAME);
471 final MistakeMatrix result = analyzeMistakes(reader, localName);
472 result.printMistakes(writer);
473 }
474
475 /***
476 * Helper method that analyses the mistakes involving a given answer key.
477 *
478 * @param answerKey the answer key to analyse
479 * @param prediction a prediction with includes the <em>last token</em>
480 * of the answer key (starts before/at and ends after/at this token),
481 * or <code>null</code> if there is no such prediction
482 */
483 private void handleAnswerKey(final Extraction answerKey,
484 final Extraction prediction) {
485 final SortedSet<MistakeTypes> mistakes = new TreeSet<MistakeTypes>();
486
487 if (prediction != null) {
488
489 if (prediction.getIndex() < answerKey.getIndex()) {
490 mistakes.add(MistakeTypes.EarlyStart);
491 } else if (prediction.getIndex() > answerKey.getIndex()) {
492 mistakes.add(MistakeTypes.LateStart);
493 }
494
495 if (prediction.getLastIndex() > answerKey.getLastIndex()) {
496 mistakes.add(MistakeTypes.LateEnd);
497 } else if (prediction.getLastIndex() < answerKey.getLastIndex()) {
498
499 throw new RuntimeException("Implementation error: prediction "
500 + prediction + " ended prior to analyzed answer key "
501 + answerKey);
502 }
503
504 if (prediction.getEvalStatus() == EvalStatus.IGNORED) {
505 mistakes.add(MistakeTypes.Ignored);
506 }
507 if (!answerKey.getType().equals(prediction.getType())) {
508 mistakes.add(MistakeTypes.WrongType);
509 }
510
511
512 latestHandledPred = prediction;
513 } else if (answerKey != latestHandledAnsKey) {
514
515 mistakes.add(MistakeTypes.CompletelyMissing);
516 }
517
518
519 latestHandledAnsKey = answerKey;
520
521 updateMistakeMatrix(answerKey, prediction, mistakes);
522 }
523
524 /***
525 * Helper method that analyses the mistakes involving a given prediction.
526 *
527 * @param prediction the prediction to analyse
528 * @param answerKey an answer key with ends after the prediction and
529 * includes the <em>last token</em> of the prediction (starts before/at and
530 * ends after this token), or <code>null</code> if no such answer key exists
531 */
532 private void handlePrediction(final Extraction prediction,
533 final Extraction answerKey) {
534 final SortedSet<MistakeTypes> mistakes = new TreeSet<MistakeTypes>();
535
536 if (answerKey != null) {
537
538 if (prediction.getIndex() < answerKey.getIndex()) {
539 mistakes.add(MistakeTypes.EarlyStart);
540 } else if (prediction.getIndex() > answerKey.getIndex()) {
541 mistakes.add(MistakeTypes.LateStart);
542 }
543
544 if (prediction.getLastIndex() < answerKey.getLastIndex()) {
545 mistakes.add(MistakeTypes.EarlyEnd);
546 } else {
547
548 throw new RuntimeException("Implementation error: answer key "
549 + answerKey
550 + " doesn't extend after analyzed prediction "
551 + prediction);
552 }
553
554 if (prediction.getEvalStatus() == EvalStatus.IGNORED) {
555 mistakes.add(MistakeTypes.Ignored);
556 }
557 if (!answerKey.getType().equals(prediction.getType())) {
558 mistakes.add(MistakeTypes.WrongType);
559 }
560
561
562 latestHandledAnsKey = answerKey;
563 } else if (prediction != latestHandledPred) {
564
565 mistakes.add(MistakeTypes.CompletelySpurious);
566 }
567
568
569 latestHandledPred = prediction;
570
571 updateMistakeMatrix(answerKey, prediction, mistakes);
572 }
573
574 /***
575 * Helper method that will add a new mistake to the mistake matrix if
576 * appropriate.
577 *
578 * @param answerKey the answer key involved in the mistake
579 * (might be <code>null</code>)
580 * @param prediction the prediction involved in the mistake
581 * (might be <code>null</code>
582 * @param mistakes the set of mistake types that occurred -- if empty, no
583 * mistake will be added
584 */
585 private void updateMistakeMatrix(final Extraction answerKey,
586 final Extraction prediction,
587 final SortedSet<MistakeTypes> mistakes) {
588
589 if (!mistakes.isEmpty()) {
590 if ((!matchAll) && (answerKey != null)
591 && correctTypes.contains(answerKey.getType())
592 && (!mistakes.contains(MistakeTypes.WrongType))) {
593
594
595
596 Util.LOG.debug("Match-best mode: Won't add mistake since answer"
597 +" key type (" + answerKey.getType()
598 + ") is from the correct types set for "
599 + source + " and no confusion occurred (mistake types: "
600 + Mistake.flatten(mistakes) + ")");
601
602 } else if ((answerKey == null || answerKey.hasProperty(
603 ExtractionMatcher.PROP_DUPLICATE))
604 && (prediction == null || prediction.hasProperty(
605 ExtractionMatcher.PROP_DUPLICATE))) {
606
607
608 Util.LOG.debug("Won't add duplicate mistake (answer key is "
609 + (answerKey == null ? "null" : "duplicate")
610 + " and prediction is "
611 + (prediction == null ? "null" : "duplicate") + ")");
612
613 } else if (mistakes.first() == MistakeTypes.CompletelyMissing
614 && answerKey.getEvalStatus() != EvalStatus.MISSING) {
615
616 Util.LOG.debug("It's not a mistake for "
617 + answerKey.getEvalStatus()
618 + " answer keys to be completely missing");
619
620 } else if (mistakes.first() == MistakeTypes.CompletelySpurious
621 && prediction.getEvalStatus() != EvalStatus.SPURIOUS) {
622
623 Util.LOG.debug("It's not a mistake for "
624 + prediction.getEvalStatus()
625 + " predictions to be completely spurious");
626
627 } else {
628
629 matrix.add(new Mistake(answerKey, prediction, mistakes,
630 source));
631 }
632 }
633 }
634
635 }