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.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.16 $, $Date: 2006/10/21 16:03:59 $, $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 ignoreExp exponent used to calculate which features to consider
116      * irrelevant for classification (if any)
117      * @param config contains configuration properties
118      * @param configSuffix optional suffix appended to the configuration keys
119      * when configuring this instance; might be <code>null</code>
120      * @throws IllegalArgumentException if one of the parameters is outside
121      * the allowed range
122      */
123     public UltraconservativeWinnow(final Set<String> allValidClasses,
124             final FeatureTransformer trans, final boolean balance,
125             final float promotionFactor, final float demotionFactor,
126             final float thresholdThick, final int ignoreExp,
127             final TiesConfiguration config, final String configSuffix)
128     throws IllegalArgumentException {
129         super(allValidClasses, trans, balance, promotionFactor, demotionFactor,
130             thresholdThick, ignoreExp, config, configSuffix);
131     }
132 
133     /***
134      * Chooses the classes to promote and the classes to demote. This
135      * "ultraconservative" implementation demotes all classes whose score is
136      * greater than or equal to the target class (the "error set") and promotes
137      * the target class if the error set is not empty.
138      *
139      * @param winnowDist the prediction distribution returned by
140      * {@link de.fu_berlin.ties.classify.TrainableClassifier#classify}
141      * @param targetClass the expected class of this instance; must be
142      * contained in the set of <code>candidateClasses</code>
143      * @param classesToPromote the classes to promote are added to this set
144      * @param classesToDemote the classes to demote are added to this set
145      */
146     protected void chooseClassesToAdjust(final WinnowDistribution winnowDist,
147             final String targetClass, final Set<String> classesToPromote,
148             final Set<String> classesToDemote) {
149         final Iterator predIter = winnowDist.iterator();
150         WinnowPrediction pred;
151         float dynamicThreshold = Float.NaN;
152         boolean goOn = true;
153         final Set<String> errorSet = new HashSet<String>();
154 
155         // classes are sorted according to probability/score in decreasing order
156         while (predIter.hasNext() && goOn) {
157             pred = (WinnowPrediction) predIter.next();
158 
159             if (targetClass.equals(pred.getType())) {
160                 // this is the target class: remember score
161                 final float scoreOfTarget = pred.getRawScore();
162 
163                 // use thick threshold heuristic if configured, dynamically
164                 // calculated from the target score
165                 dynamicThreshold =
166                     minorThreshold(scoreOfTarget, winnowDist.getRawThreshold());
167             } else {
168                 if (!Float.isNaN(dynamicThreshold)
169                         && (pred.getRawScore() < dynamicThreshold)) {
170                     // class with lower score: break loop
171                     goOn = false;
172                 } else {
173                     // score is higher than or equal to dynamic threshold
174                     errorSet.add(pred.getType());
175                 }
176             }
177         }
178 
179         if (!errorSet.isEmpty()) {
180             // promote target class because of erroneous classifications
181             classesToPromote.add(targetClass);
182             classesToDemote.addAll(errorSet);
183         }
184     }
185 
186 }