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.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 < 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
153 while (predIter.hasNext() && goOn) {
154 pred = (WinnowPrediction) predIter.next();
155
156 if (targetClass.equals(pred.getType())) {
157
158 final float scoreOfTarget = pred.getRawScore();
159
160
161
162 dynamicThreshold =
163 minorThreshold(scoreOfTarget, winnowDist.getRawThreshold());
164 } else {
165 if (!Float.isNaN(dynamicThreshold)
166 && (pred.getRawScore() < dynamicThreshold)) {
167
168 goOn = false;
169 } else {
170
171 errorSet.add(pred.getType());
172 }
173 }
174 }
175
176 if (!errorSet.isEmpty()) {
177
178 classesToPromote.add(targetClass);
179 classesToDemote.addAll(errorSet);
180 }
181 }
182
183 }