View Javadoc

1   /*
2    * Copyright (C) 2004 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 library is free software; you can redistribute it and/or
8    * modify it under the terms of the GNU Lesser General Public
9    * License as published by the Free Software Foundation; either
10   * version 2.1 of the License, or (at your option) any later version.
11   *
12   * This library 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 GNU
15   * Lesser General Public License for more details.
16   *
17   * You should have received a copy of the GNU Lesser General Public
18   * License along with this library; if not, visit
19   * http://www.gnu.org/licenses/lgpl.html or write to the Free Software
20   * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
21   */
22  package de.fu_berlin.ties.classify.winnow;
23  
24  import java.util.HashSet;
25  import java.util.Iterator;
26  import java.util.Set;
27  
28  import de.fu_berlin.ties.ProcessingException;
29  import de.fu_berlin.ties.TiesConfiguration;
30  import de.fu_berlin.ties.classify.feature.FeatureTransformer;
31  
32  /***
33   * A combination of Winnow with the "ultraconservative" approach proposed by
34   * Koby Crammer and Yoram Singer. In case of a loss (mistake) the target class
35   * is promoted and all classes whose score is greater than or equal to the
36   * target class (the "error set") are demoted.
37   *
38   * <p>Instances of this class are thread-safe.
39   *
40   * @author Christian Siefkes
41   * @version $Revision: 1.12 $, $Date: 2004/09/06 17:22:20 $, $Author: siefkes $
42   */
43  public class UltraconservativeWinnow extends Winnow {
44  
45      /***
46       * Optional prefix used to give values for the configuration
47       * parameters of this classifier that differ from the values used by Winnow.
48       */
49      public static final String UC_SUFFIX = "uc";
50  
51      /***
52       * Creates a new instance by delegating to the corresponding super
53       * constructor.
54       *
55       * @param allValidClasses the set of all valid classes
56       * @throws IllegalArgumentException if one of the parameters is outside
57       * the allowed range
58       * @throws ProcessingException if an error occurred while creating
59       * the feature transformer(s)
60       */
61      public UltraconservativeWinnow(final Set<String> allValidClasses)
62      throws IllegalArgumentException, ProcessingException {
63          super(allValidClasses, UC_SUFFIX);
64      }
65  
66      /***
67       * Creates a new instance by delegating to the corresponding super
68       * constructor.
69       *
70       * @param allValidClasses the set of all valid classes
71       * @param config contains configuration properties
72       * @throws IllegalArgumentException if one of the parameters is outside
73       * the allowed range
74       * @throws ProcessingException if an error occurred while creating
75       * the feature transformer(s)
76       */
77      public UltraconservativeWinnow(final Set<String> allValidClasses,
78              final TiesConfiguration config)
79      throws IllegalArgumentException, ProcessingException {
80          super(allValidClasses, config, UC_SUFFIX);
81      }
82  
83      /***
84       * Creates a new instance by delegating to the corresponding super
85       * constructor.
86       *
87       * @param allValidClasses the set of all valid classes
88       * @param trans the last transformer in the transformer chain to use, or
89       * <code>null</code> if no feature transformers should be used
90       * @param config contains configuration properties
91       * @throws IllegalArgumentException if one of the parameters is outside
92       * the allowed range
93       * @throws ProcessingException if an error occurred while creating
94       * the feature transformer(s)
95       */
96      public UltraconservativeWinnow(final Set<String> allValidClasses,
97              final FeatureTransformer trans, final TiesConfiguration config)
98      throws IllegalArgumentException, ProcessingException {
99          super(allValidClasses, trans, config, UC_SUFFIX);
100     }
101 
102     /***
103      * Creates a new instance by delegating to the corresponding super
104      * constructor.
105      *
106      * @param allValidClasses the set of all valid classes
107      * @param trans the last transformer in the transformer chain to use, or
108      * <code>null</code> if no feature transformers should be used
109      * @param balance whether to use the Balanced Winnow or the standard
110      * Winnow algorithm
111      * @param promotionFactor the promotion factor used by the algorithm
112      * @param demotionFactor the demotion factor used by the algorithm
113      * @param thresholdThick the thickness of the threshold if the "thick
114      * threshold" heuristic is used (must be &lt; 1.0), 0.0 otherwise
115      * @param config contains configuration properties
116      * @param configSuffix optional suffix appended to the configuration keys
117      * when configuring this instance; might be <code>null</code>
118      * @throws IllegalArgumentException if one of the parameters is outside
119      * the allowed range
120      */
121     public UltraconservativeWinnow(final Set<String> allValidClasses,
122             final FeatureTransformer trans, final boolean balance,
123             final float promotionFactor, final float demotionFactor,
124             final float thresholdThick, final TiesConfiguration config,
125             final String configSuffix) throws IllegalArgumentException {
126         super(allValidClasses, trans, balance, promotionFactor, demotionFactor,
127             thresholdThick, config, configSuffix);
128     }
129 
130     /***
131      * Chooses the classes to promote and the classes to demote. This
132      * "ultraconservative" implementation demotes all classes whose score is
133      * greater than or equal to the target class (the "error set") and promotes
134      * the target class if the error set is not empty.
135      *
136      * @param winnowDist the prediction distribution returned by
137      * {@link de.fu_berlin.ties.classify.TrainableClassifier#classify}
138      * @param targetClass the expected class of this instance; must be
139      * contained in the set of <code>candidateClasses</code>
140      * @param classesToPromote the classes to promote are added to this set
141      * @param classesToDemote the classes to demote are added to this set
142      */
143     protected void chooseClassesToAdjust(final WinnowDistribution winnowDist,
144             final String targetClass, final Set<String> classesToPromote,
145             final Set<String> classesToDemote) {
146         final Iterator predIter = winnowDist.iterator();
147         WinnowPrediction pred;
148         float dynamicThreshold = Float.NaN;
149         boolean goOn = true;
150         final Set<String> errorSet = new HashSet<String>();
151 
152         // classes are sorted according to probability/score in decreasing order
153         while (predIter.hasNext() && goOn) {
154             pred = (WinnowPrediction) predIter.next();
155 
156             if (targetClass.equals(pred.getType())) {
157                 // this is the target class: remember score
158                 final float scoreOfTarget = pred.getRawScore();
159 
160                 // use thick threshold heuristic if configured, dynamically
161                 // calculated from the target score
162                 dynamicThreshold =
163                     minorThreshold(scoreOfTarget, winnowDist.getRawThreshold());
164             } else {
165                 if (!Float.isNaN(dynamicThreshold)
166                         && (pred.getRawScore() < dynamicThreshold)) {
167                     // class with lower score: break loop
168                     goOn = false;
169                 } else {
170                     // score is higher than or equal to dynamic threshold
171                     errorSet.add(pred.getType());
172                 }
173             }
174         }
175 
176         if (!errorSet.isEmpty()) {
177             // promote target class because of erroneous classifications
178             classesToPromote.add(targetClass);
179             classesToDemote.addAll(errorSet);
180         }
181     }
182 
183 }