001/**
002 * Copyright (c) 2011, The University of Southampton and the individual contributors.
003 * All rights reserved.
004 *
005 * Redistribution and use in source and binary forms, with or without modification,
006 * are permitted provided that the following conditions are met:
007 *
008 *   *  Redistributions of source code must retain the above copyright notice,
009 *      this list of conditions and the following disclaimer.
010 *
011 *   *  Redistributions in binary form must reproduce the above copyright notice,
012 *      this list of conditions and the following disclaimer in the documentation
013 *      and/or other materials provided with the distribution.
014 *
015 *   *  Neither the name of the University of Southampton nor the names of its
016 *      contributors may be used to endorse or promote products derived from this
017 *      software without specific prior written permission.
018 *
019 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
020 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
021 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
022 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
023 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
024 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
025 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
026 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
027 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
028 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
029 */
030package org.openimaj.ml.annotation.evaluation;
031
032import java.util.ArrayList;
033import java.util.Collection;
034import java.util.Collections;
035import java.util.Comparator;
036import java.util.HashMap;
037import java.util.HashSet;
038import java.util.List;
039import java.util.Map;
040import java.util.Map.Entry;
041import java.util.Set;
042
043import org.openimaj.data.dataset.Dataset;
044import org.openimaj.data.identity.Identifiable;
045import org.openimaj.experiment.evaluation.AnalysisResult;
046import org.openimaj.experiment.evaluation.classification.BasicClassificationResult;
047import org.openimaj.experiment.evaluation.classification.ClassificationAnalyser;
048import org.openimaj.experiment.evaluation.classification.ClassificationEvaluator;
049import org.openimaj.experiment.evaluation.classification.ClassificationResult;
050import org.openimaj.experiment.evaluation.classification.Classifier;
051import org.openimaj.experiment.evaluation.retrieval.RetrievalAnalyser;
052import org.openimaj.experiment.evaluation.retrieval.RetrievalEngine;
053import org.openimaj.experiment.evaluation.retrieval.RetrievalEvaluator;
054import org.openimaj.ml.annotation.Annotated;
055import org.openimaj.ml.annotation.Annotator;
056import org.openimaj.ml.annotation.ScoredAnnotation;
057import org.openimaj.util.pair.ObjectDoublePair;
058
059/**
060 * A class to help evaluate the performance of an {@link Annotator} using
061 * standardised classification and/or retrieval evaluation methodologies.
062 * 
063 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
064 * 
065 * @param <OBJECT>
066 *            Type of object being annotated
067 * @param <ANNOTATION>
068 *            Type of annotation.
069 */
070public class AnnotationEvaluator<OBJECT extends Identifiable, ANNOTATION>
071{
072        Annotator<OBJECT, ANNOTATION> annotator;
073        Dataset<? extends Annotated<OBJECT, ANNOTATION>> testData;
074        AnnotationEvaluationEngine<OBJECT, ANNOTATION> engine;
075
076        /**
077         * Construct a new {@link AnnotationEvaluator} with the given annotator and
078         * test data (with ground-truth annotations).
079         * 
080         * @param annotator
081         *            the annotator
082         * @param testData
083         *            the test data with ground-truth annotations.
084         */
085        public AnnotationEvaluator(Annotator<OBJECT, ANNOTATION> annotator,
086                        Dataset<? extends Annotated<OBJECT, ANNOTATION>> testData)
087        {
088                this.annotator = annotator;
089                this.testData = testData;
090                engine = new AnnotationEvaluationEngine<OBJECT, ANNOTATION>(annotator, testData);
091        }
092
093        /**
094         * Make a new {@link ClassificationEvaluator}, backed by the annotations
095         * computed by this {@link AnnotationEvaluator}, with the given
096         * {@link ClassificationAnalyser}.
097         * 
098         * @param <RESULT>
099         *            The type of {@link AnalysisResult} produced by the evaluator
100         * @param analyser
101         *            the ClassificationAnalyser
102         * @return the evaluator
103         */
104        public <RESULT extends AnalysisResult>
105                        ClassificationEvaluator<RESULT, ANNOTATION, OBJECT>
106                        newClassificationEvaluator(ClassificationAnalyser<RESULT, ANNOTATION, OBJECT> analyser)
107        {
108                return new ClassificationEvaluator<RESULT, ANNOTATION, OBJECT>(engine, getObjects(), getActual(), analyser);
109        }
110
111        /**
112         * Make a new {@link RetrievalEvaluator}, backed by the annotations computed
113         * by this {@link AnnotationEvaluator}, with the given
114         * {@link RetrievalAnalyser}.
115         * 
116         * @param <RESULT>
117         *            The type of {@link AnalysisResult} produced by the evaluator
118         * @param analyser
119         *            the RetrievalAnalyser
120         * @return the evaluator
121         */
122        public <RESULT extends AnalysisResult> RetrievalEvaluator<RESULT, OBJECT, ANNOTATION> newRetrievalEvaluator(
123                        RetrievalAnalyser<RESULT, ANNOTATION, OBJECT> analyser)
124        {
125                final Set<ANNOTATION> queries = this.getQueries();
126                final Map<ANNOTATION, Set<OBJECT>> relevant = this.getRelevant(queries);
127
128                return new RetrievalEvaluator<RESULT, OBJECT, ANNOTATION>(engine, relevant, analyser);
129        }
130
131        /**
132         * @return the objects for constructing a {@link ClassificationEvaluator}
133         */
134        private Collection<OBJECT> getObjects() {
135                final List<OBJECT> objects = new ArrayList<OBJECT>();
136
137                for (final Annotated<OBJECT, ANNOTATION> ao : testData) {
138                        objects.add(ao.getObject());
139                }
140
141                return objects;
142        }
143
144        /**
145         * @return the actual classes for constructing a
146         *         {@link ClassificationEvaluator}
147         */
148        private Map<OBJECT, Set<ANNOTATION>> getActual() {
149                final Map<OBJECT, Set<ANNOTATION>> actual = new HashMap<OBJECT, Set<ANNOTATION>>();
150
151                for (final Annotated<OBJECT, ANNOTATION> ao : testData) {
152                        actual.put(ao.getObject(), new HashSet<ANNOTATION>(ao.getAnnotations()));
153                }
154
155                return actual;
156        }
157
158        /**
159         * @return the queries for constructing a {@link RetrievalEvaluator}
160         */
161        private Set<ANNOTATION> getQueries() {
162                final Set<ANNOTATION> testAnnotations = new HashSet<ANNOTATION>();
163
164                for (final Annotated<OBJECT, ANNOTATION> item : testData) {
165                        testAnnotations.addAll(item.getAnnotations());
166                }
167
168                testAnnotations.retainAll(annotator.getAnnotations());
169
170                return testAnnotations;
171        }
172
173        /**
174         * @return the relevant docs for constructing a {@link RetrievalEvaluator}
175         */
176        private Map<ANNOTATION, Set<OBJECT>> getRelevant(Collection<ANNOTATION> queries) {
177                final Map<ANNOTATION, Set<OBJECT>> relevant = new HashMap<ANNOTATION, Set<OBJECT>>();
178
179                for (final ANNOTATION query : queries) {
180                        final HashSet<OBJECT> rset = new HashSet<OBJECT>();
181                        relevant.put(query, rset);
182
183                        for (final Annotated<OBJECT, ANNOTATION> item : testData) {
184                                if (item.getAnnotations().contains(query)) {
185                                        rset.add(item.getObject());
186                                }
187                        }
188                }
189
190                return relevant;
191        }
192
193        static class AnnotationEvaluationEngine<OBJECT extends Identifiable, ANNOTATION>
194                        implements
195                        RetrievalEngine<OBJECT, ANNOTATION>,
196                        Classifier<ANNOTATION, OBJECT>
197        {
198                Map<OBJECT, List<ScoredAnnotation<ANNOTATION>>> results = new HashMap<OBJECT, List<ScoredAnnotation<ANNOTATION>>>();
199
200                public AnnotationEvaluationEngine(Annotator<OBJECT, ANNOTATION> annotator,
201                                Dataset<? extends Annotated<OBJECT, ANNOTATION>> testData)
202                {
203                        for (final Annotated<OBJECT, ANNOTATION> item : testData) {
204                                final OBJECT obj = item.getObject();
205                                results.put(obj, annotator.annotate(obj));
206                        }
207                }
208
209                @Override
210                public List<OBJECT> search(ANNOTATION query) {
211                        final List<ObjectDoublePair<OBJECT>> sr = new ArrayList<ObjectDoublePair<OBJECT>>();
212
213                        for (final Entry<OBJECT, List<ScoredAnnotation<ANNOTATION>>> e : results.entrySet()) {
214                                for (final ScoredAnnotation<ANNOTATION> a : e.getValue()) {
215                                        if (a.annotation.equals(query)) {
216                                                sr.add(ObjectDoublePair.pair(e.getKey(), a.confidence));
217                                                break;
218                                        }
219                                }
220                        }
221
222                        Collections.sort(sr, new Comparator<ObjectDoublePair<OBJECT>>() {
223                                @Override
224                                public int compare(ObjectDoublePair<OBJECT> o1, ObjectDoublePair<OBJECT> o2) {
225                                        if (o1.second == o2.second)
226                                                return 0;
227                                        if (o1.second < o2.second)
228                                                return 1;
229                                        return -1;
230                                }
231                        });
232
233                        return ObjectDoublePair.getFirst(sr);
234                }
235
236                @Override
237                public ClassificationResult<ANNOTATION> classify(OBJECT object) {
238                        final BasicClassificationResult<ANNOTATION> res = new BasicClassificationResult<ANNOTATION>();
239
240                        for (final ScoredAnnotation<ANNOTATION> anno : results.get(object)) {
241                                res.put(anno.annotation, anno.confidence);
242                        }
243
244                        return res;
245                }
246        }
247}