View Javadoc

1   /*
2    * Copyright (C) 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.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             // read preprocessed (AUG) file
188             augDoc = DOMUtils.readDocument(augFile, getConfig());
189         } catch (DocumentException de) {
190             // wrap and rethrow
191             throw new ProcessingException(de);
192         }
193 
194         ExtractionContainer myPredictions;
195 
196         if (!matchAll) {
197             // match best mode: discard *predictions* for which a correct answer
198             // was found (and thus no mistake occurred). For *answer keys* we
199             // will do this later (in updateMistakeMatrix), otherwise it would
200             // be impossible to get a full confusion matrix.
201             myPredictions = discardCorrectTypes(predictions, "predictions");
202         } else {
203             myPredictions = predictions;
204         }
205 
206         // match + order predictions and answer keys
207         //Util.LOG.debug("Matching and ordering predictions");
208         myPredictions = extMatcher.matchAndOrderExtractions(myPredictions,
209                 augDoc);
210         //Util.LOG.debug("Matching and ordering (answer keys");
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         // analyse all predictions and answer keys ordered by last index
219         while ((prediction != null) || (answerKey != null)) {
220             if ((prediction != null) && (answerKey != null)) {
221                 if (answerKey.getLastIndex() <= prediction.getLastIndex()) {
222                     // answer key ends earlier/parallel and should be analyzed
223                     if (prediction.getIndex() <= answerKey.getLastIndex()) {
224                         // prediction includes the last token of the answer key
225                         handleAnswerKey(answerKey, prediction);
226                     } else {
227                         handleAnswerKey(answerKey, null);
228                     }
229 
230                     // switch to next answer key
231                     answerKey = ansIter.hasNext() ? ansIter.next() : null;
232                 } else {
233                     // prediction ends earlier and should be analyzed
234                     if (answerKey.getIndex() <= prediction.getLastIndex()) {
235                         // answer key includes the last token of the prediction
236                         handlePrediction(prediction, answerKey);
237                     } else {
238                         handlePrediction(prediction, null);
239                     }
240 
241                     // switch to next prediction
242                     prediction = predIter.hasNext() ? predIter.next() : null;
243                 }
244             } else if (answerKey != null) {
245                 // only answer keys left
246                 handleAnswerKey(answerKey, null);
247                 answerKey = ansIter.hasNext() ? ansIter.next() : null;
248             } else {
249                 // only predictions left
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         // sort into batches based on sources, preserving the original order
273         // of source files
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         // separated and re-evaluate extractions for each batch
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                     // memorize types of correct extractions
311                     correctTypes.add(currentExt.getType());
312                 } else {
313                     // put each extraction into suitable container
314                     if ((currentStatus == EvalStatus.TRUTH)
315                             || (currentStatus == EvalStatus.UNKNOWN)) {
316                         // not supposed to occur in evaluated predictions
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             // evaluate batch
328             analyzeBatch(currentPredictions, currentAnswers, currentSource);
329         }
330 
331         // store + return
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         // read extraction + delegate
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             // prepare serialization of mistake (combination) counts + confusion
372             // matrices, including averages/sums/standard deviations
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             // serialize statistics
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                 // count for logging
438                 discardCount.add(extType);
439             } else {
440                 result.add(ext);
441             }
442         }
443 
444         // build debug message
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         // perform analysis + serialize resulting list of mistakes
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             // determine mistake types
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                 // must not happen if this method was invoked correctly
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             // remember that prediction has been involved in a mistake
512             latestHandledPred = prediction;
513         } else if (answerKey != latestHandledAnsKey) {
514             // answer key hasn't been involved in any mistake
515             mistakes.add(MistakeTypes.CompletelyMissing);
516         }
517 
518         // remember that answer key has been involved in a mistake
519         latestHandledAnsKey = answerKey;
520         // update matrix if necessary
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             // determine mistake types
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                 // must not happen if this method was invoked correctly
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             // remember that answer key has been involved in a mistake
562             latestHandledAnsKey = answerKey;
563         } else if (prediction != latestHandledPred) {
564             // prediction hasn't been involved in any mistake
565             mistakes.add(MistakeTypes.CompletelySpurious);
566         }
567 
568         // remember that prediction has been involved in a mistake
569         latestHandledPred = prediction;
570         // update matrix if necessary
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         // update mistake matrix if mistake set is not empty
589         if (!mistakes.isEmpty()) {
590             if ((!matchAll) && (answerKey != null)
591                     && correctTypes.contains(answerKey.getType())
592                     && (!mistakes.contains(MistakeTypes.WrongType))) {
593 
594                 // answers of correct types are only relevant for confusion
595                 // analysis
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                 // ignore if both are duplicates (or null)
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                 // finally, a real mistake!
629                 matrix.add(new Mistake(answerKey, prediction, mistakes,
630                         source));
631             }
632         }
633     }
634 
635 }