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.extract;
23  
24  import java.util.Collection;
25  import java.util.Iterator;
26  import java.util.LinkedHashSet;
27  
28  import org.apache.commons.lang.builder.ToStringBuilder;
29  
30  import de.fu_berlin.ties.TiesConfiguration;
31  import de.fu_berlin.ties.classify.PredictionComparator;
32  import de.fu_berlin.ties.eval.EvalStatus;
33  import de.fu_berlin.ties.eval.MultiFMetrics;
34  import de.fu_berlin.ties.eval.MultiFMetricsView;
35  
36  /***
37   * An extraction container that evaluates containers of predicted extractions
38   * against containers of true extractions (answer keys) and merges their
39   * contents, setting the {@linkplain de.fu_berlin.ties.eval.EvalStatus
40   * evaluation states} accordingly. Extractions in both containers are marked as
41   * {@link de.fu_berlin.ties.eval.EvalStatus#CORRECT} (true positives),
42   * extractions found only in the container of predictions are marked as
43   * {@link de.fu_berlin.ties.eval.EvalStatus#SPURIOUS} (false positives), while
44   * those occurring only in the answer keys are
45   * {@link de.fu_berlin.ties.eval.EvalStatus#MISSING} (false negatives).
46   *
47   * <p><a name="match-modes">Two <strong>match modes</strong> are supported:</a>
48   * in <em>match-all mode</em>, all extractions are evaluated.
49   * In <em>match-best mode</em>, only the recognition with the highest
50   * probability of each type is evaluated (in each batch), while the others are
51   * {@linkplain de.fu_berlin.ties.eval.EvalStatus#IGNORED ignored} and not
52   * counted; it is thus suffienct to match (or fail to match) a single answer key
53   * -- the other answer keys are marked as
54   * {@link de.fu_berlin.ties.eval.EvalStatus#ALTERNATIVE}s and not counted.
55   *
56   * @author Christian Siefkes
57   * @version $Revision: 1.13 $, $Date: 2006/10/21 16:04:13 $, $Author: siefkes $
58   */
59  public class EvaluatedExtractionContainer extends ExtractionContainer {
60  
61      /***
62       * Configuration key: whether to use <em>match-all</em> or
63       * <em>match-best</em> as <a href="#match-modes">match mode</a>.
64       */
65      public static final String CONFIG_MATCH_ALL = "eval.match.all";
66  
67      /***
68       * Configuration key for {@link #isMatchingPosition()}.
69       */
70      public static final String CONFIG_MATCH_POSITION = "eval.match.pos";
71  
72      /***
73       * Counts the true positives (correct extractions), false negatives (missing
74       * extractions) and false positives (spurious extractions) stored in this
75       * container of each type as well as for all types; calculates appropriate
76       * statistics.
77       */
78      private final MultiFMetrics multiMetrics = new MultiFMetrics();
79  
80      /***
81       * The <a href="#match-modes">match mode</a>: <code>true</code> for
82       * <em>match-all mode</em>, <code>false</code> for <em>match-best mode</em>.
83       */
84      private final boolean matchingAll;
85  
86      /***
87       * If <code>true</code>, the positions of extraction and answer keys must
88       * match; otherwise only their contents must match (string compare).
89       */
90      private final boolean matchingPosition;
91  
92      /***
93       * Used to compare the pR values resp. probabilities of predictions.
94       */
95      private final PredictionComparator predComp = new PredictionComparator();
96  
97      /***
98       * Creates a new instance.
99       *
100      * @param targetStruct the target structure specifying the classes to
101      * recognize
102      * @param config used to configure this instance
103      */
104     public EvaluatedExtractionContainer(final TargetStructure targetStruct,
105             final TiesConfiguration config) {
106         this(targetStruct, config.getBoolean(CONFIG_MATCH_ALL),
107                 config.getBoolean(CONFIG_MATCH_POSITION));
108     }
109 
110     /***
111      * Creates a new instance.
112      *
113      * @param targetStruct the target structure specifying the classes to
114      * recognize
115      * @param matchAll sets the <a href="#match-modes">match mode</a>:
116      * <code>true</code> for <em>match-all mode</em>, <code>false</code> for
117      * <em>match-best mode</em>
118      * @param matchPosition if <code>true</code>, the positions of extraction
119      * and answer keys must match; otherwise only their contents must match
120      * (string compare)
121      */
122     public EvaluatedExtractionContainer(final TargetStructure targetStruct,
123             final boolean matchAll, final boolean matchPosition) {
124         super(targetStruct);
125         matchingAll = matchAll;
126         matchingPosition = matchPosition;
127     }
128 
129     /***
130      * Adds an extraction to this container. Only <em>evaluated</em> extractions
131      * can be added to this container, i.e., the evaluation states
132      * {@link EvalStatus#UNKNOWN} and {@link EvalStatus#TRUTH} are not allowed.
133      * The evaluation states {@link EvalStatus#IGNORED} and
134      * {@link EvalStatus#ALTERNATIVE} are only allowed in <em>match-best
135      * <a href="#match-modes">mode</a></em>; in <em>match-all mode</em>
136      * ({@link #isMatchingAll()} == <code>true</code>) they don't make sense
137      * and are thus rejected.
138      *
139      * @param extraction the extraction to add
140      * @throws IllegalArgumentException if the extraction's {@linkplain
141      * de.fu_berlin.ties.classify.Prediction#getEvalStatus() evaluation status}
142      * is invalid (cf. above); or if the class of the extraction is not
143      * in the set of classes accepted by this container
144      */
145     public void add(final Extraction extraction)
146             throws IllegalArgumentException {
147         final EvalStatus evalStatus = extraction.getEvalStatus();
148 
149         // check argument
150         if ((evalStatus == EvalStatus.UNKNOWN)
151                 || (evalStatus == EvalStatus.TRUTH)) {
152             throw new IllegalArgumentException("Illegal eval status: "
153                 + evalStatus);
154         }
155         if (isMatchingAll() && ((evalStatus == EvalStatus.IGNORED)
156                 || (evalStatus == EvalStatus.ALTERNATIVE))) {
157             throw new IllegalArgumentException(
158                 "Illegal eval status for match-all mode: " + evalStatus);
159         }
160 
161         // delegate to super
162         super.add(extraction);
163 
164         // update statistics
165         if (evalStatus == EvalStatus.CORRECT) {
166             multiMetrics.incTruePos(extraction.getType());
167         } else if (evalStatus == EvalStatus.MISSING) {
168             multiMetrics.incFalseNeg(extraction.getType());
169         } else if (evalStatus == EvalStatus.SPURIOUS) {
170             multiMetrics.incFalsePos(extraction.getType());
171         }
172     }
173 
174     /***
175      * Helper method that adds a bunch of extractions, setting their evaluation
176      * status and source as specified.
177      *
178      * @param extractionColl a collection of {@link Extraction}s to add; the
179      * collection will be {@linkplain Collection#clear() cleared} by this
180      * method, i.e., it will be empty after the method returned
181      * @param status the status of all extractions in the collection will be
182      * set to this value prior to adding them
183      * @param source the
184      * {@linkplain de.fu_berlin.ties.classify.Prediction#getSource() source} to
185      * set for all extractions in the collection; ignored if <code>null</code>
186      */
187     protected void addAllAndClear(final Collection extractionColl,
188             final EvalStatus status, final String source) {
189         final Iterator iter = extractionColl.iterator();
190         Extraction currentExtraction;
191 
192         while (iter.hasNext()) {
193             currentExtraction = (Extraction) iter.next();
194 
195             // adjust values
196             currentExtraction.setEvalStatus(status);
197             if (source != null) {
198                 currentExtraction.setSource(source);
199             }
200 
201             // add extraction
202             add(currentExtraction);
203         }
204 
205         // reset collection
206         extractionColl.clear();
207     }
208 
209     /***
210      * Evaluates a container of predicted extractions against a container of
211      * true extractions (answer keys) and adds them to this instance.
212      * In <em>match-best mode</em>, only the extraction with the highest
213      * pR resp. probability of each type in this batch is evaluated.
214      * 
215      * <p><strong>Warning: If positions are ignored for matching (see
216      * {@linkplain #EvaluatedExtractionContainer(TargetStructure, boolean,
217      * boolean) constructor}), the two given containers are modified
218      * by {@linkplain ExtractionContainer#unsetPositions() unsetting the
219      * positions} of all extractions and removing duplicates (extractions with
220      * same type + text but different positions).</strong>
221      *
222      * @param predicted the container of predicted extractions
223      * @param expected the container of expected extractions (answer keys)
224      * @param source the
225      * {@linkplain de.fu_berlin.ties.classify.Prediction#getSource() source}
226      * to add to add extractions of this batch; ignored if <code>null</code>
227      * @throws IllegalArgumentException if the
228      * {@linkplain ExtractionContainer#getTargetStructure() target structures}
229      * of the two containers differ from the target structure of this one
230      */
231     public void evaluateBatch(final ExtractionContainer predicted,
232             final ExtractionContainer expected, final String source)
233             throws IllegalArgumentException {
234         // check arguments
235         if (!predicted.getTargetStructure().equals(getTargetStructure())) {
236             throw new IllegalArgumentException(
237                 "Target structures of predictions differ: "
238                 + predicted.getTargetStructure() + "; "
239                 + getTargetStructure());
240         }
241         if (!expected.getTargetStructure().equals(getTargetStructure())) {
242             throw new IllegalArgumentException(
243                 "Target structures of answer keys differs: "
244                 + expected.getTargetStructure() + "; "
245                 + getTargetStructure());
246         }
247 
248         if (!matchingPosition) {
249             // unset positions (remove resulting duplicates) in both containers
250             predicted.unsetPositions();
251             expected.unsetPositions();
252         }
253 
254         // compare containers and store results for each accepted class
255         final Iterator acceptedIter =
256             getTargetStructure().getClassNames().iterator();
257         String currentClassName;
258         Iterator extractionIter;
259         Extraction currentExtraction;
260 
261         // temporary sets of extractions with different states
262         final LinkedHashSet<Extraction> correct =
263             new LinkedHashSet<Extraction>();
264         final LinkedHashSet<Extraction> missing =
265             new LinkedHashSet<Extraction>();
266         final LinkedHashSet<Extraction> spurious =
267             new LinkedHashSet<Extraction>();
268 
269         // sets + variables used in match-best mode
270         final LinkedHashSet<Extraction> altern =
271             matchingAll ? null : new LinkedHashSet<Extraction>();
272         final LinkedHashSet<Extraction> ignored =
273             matchingAll ? null : new LinkedHashSet<Extraction>();
274         final LinkedHashSet<Extraction> temp =
275             matchingAll ? null : new LinkedHashSet<Extraction>();
276         Iterator<Extraction> tempIter;
277         Extraction bestExtraction = null;
278         boolean gotMatch = false;
279 
280         while (acceptedIter.hasNext()) {
281             currentClassName = (String) acceptedIter.next();
282 
283             // iterate all predictions of this class
284             extractionIter = predicted.iterator(currentClassName);
285             while (extractionIter.hasNext()) {
286                 currentExtraction = (Extraction) extractionIter.next();
287 
288                 if (matchingAll) {
289                     // match-all mode: initially consider all spurious
290                     spurious.add(currentExtraction);
291                 } else {
292                     // match-best mode: find best (most likely) extraction
293                     if ((bestExtraction == null) || predComp.compare(
294                                     bestExtraction, currentExtraction) < 0) {
295                         // most probable extraction seen to far
296                         bestExtraction = currentExtraction;
297                     }
298                     temp.add(currentExtraction);
299                 }
300             }
301 
302             if (!matchingAll) {
303                 // match-best mode: consider best as spurious (initially)
304                 if (bestExtraction != null) {
305                     spurious.add(bestExtraction);
306                     temp.remove(bestExtraction);
307                 }
308 
309                 // ignore all others + reset variables
310                 ignored.addAll(temp);
311                 bestExtraction = null;
312                 temp.clear();
313             }
314 
315             // iterate all expected extractions (answer keys)
316             extractionIter = expected.iterator(currentClassName);
317             while (extractionIter.hasNext()) {
318                 currentExtraction = (Extraction) extractionIter.next();
319 
320                 if (spurious.contains(currentExtraction)) {
321                     // got a match: move from spurious to correct
322                     spurious.remove(currentExtraction);
323                     correct.add(currentExtraction);
324                     gotMatch = true;
325                 } else {
326                     if (matchingAll) {
327                         // match-all mode: extraction is missing
328                         missing.add(currentExtraction);
329                     } else {
330                         // match-best: collect extractions to see if we got one
331                         temp.add(currentExtraction);
332                     }
333                 }
334             }
335 
336             if (!matchingAll) { // match-best mode
337                 if (!gotMatch) {
338                     // no match: mark first one as missing
339                     tempIter = temp.iterator();
340                     if (tempIter.hasNext()) {
341                         currentExtraction = tempIter.next();
342                         temp.remove(currentExtraction);
343                         missing.add(currentExtraction);
344                     }
345                 }
346 
347                 // mark others as alternatives + reset variables
348                 altern.addAll(temp);
349                 gotMatch = false;
350                 temp.clear();
351             }
352 
353             // add all extractions, setting their eval states + resetting sets
354             addAllAndClear(correct, EvalStatus.CORRECT, source);
355             addAllAndClear(missing, EvalStatus.MISSING, source);
356             addAllAndClear(spurious, EvalStatus.SPURIOUS, source);
357 
358             if (!matchingAll) { // match-best mode
359                 addAllAndClear(altern, EvalStatus.ALTERNATIVE, source);
360                 addAllAndClear(ignored, EvalStatus.IGNORED, source);
361             }
362         }
363     }
364 
365     /***
366      * Returns the <a href="#match-modes">match mode</a>.
367      *
368      * @return <code>true</code> for <em>match-all mode</em>,
369      * <code>false</code> for <em>match-best mode</em>
370      */
371     public boolean isMatchingAll() {
372         return matchingAll;
373     }
374 
375     /***
376      * If <code>true</code>, the positions of extraction and answer keys must
377      * match; otherwise only their contents must match (string compare).
378      *
379      * @return the value of the attribute
380      */
381     public boolean isMatchingPosition() {
382         return matchingPosition;
383     }
384 
385     /***
386      * Returns a string representation of this object.
387      * @return a textual representation
388      */
389     public String toString() {
390         return new ToStringBuilder(this)
391             .appendSuper(super.toString())
392             .append("match-all mode", matchingAll)
393             .append("matching positions", matchingPosition)
394             .append("statistics", multiMetrics)
395             .toString();
396     }
397 
398     /***
399      * Returns a read-only view of the counts of true positives (correct
400      * extractions), false negatives (missing extractions) and false positives
401      * (spurious extractions) stored in this container of each type as well as
402      * for all types; and the metrics that can be calculated from these values.
403      * This is not a snapshot but will change whenever the container is changed.
404      *
405      * @return a view of the counts and evaluation metrics
406      */
407     public MultiFMetricsView viewMetrics() {
408         return multiMetrics;
409     }
410 
411 }