1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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 < 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
156 while (predIter.hasNext() && goOn) {
157 pred = (WinnowPrediction) predIter.next();
158
159 if (targetClass.equals(pred.getType())) {
160
161 final float scoreOfTarget = pred.getRawScore();
162
163
164
165 dynamicThreshold =
166 minorThreshold(scoreOfTarget, winnowDist.getRawThreshold());
167 } else {
168 if (!Float.isNaN(dynamicThreshold)
169 && (pred.getRawScore() < dynamicThreshold)) {
170
171 goOn = false;
172 } else {
173
174 errorSet.add(pred.getType());
175 }
176 }
177 }
178
179 if (!errorSet.isEmpty()) {
180
181 classesToPromote.add(targetClass);
182 classesToDemote.addAll(errorSet);
183 }
184 }
185
186 }