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.Collection;
25 import java.util.Iterator;
26 import java.util.Map;
27 import java.util.TreeMap;
28
29 import org.apache.commons.lang.builder.ToStringBuilder;
30
31 import de.fu_berlin.ties.TiesConfiguration;
32 import de.fu_berlin.ties.util.AdaptableLRUMap;
33 import de.fu_berlin.ties.util.MultiValueMap;
34 import de.fu_berlin.ties.util.Pruner;
35
36 /***
37 * Feature store used by {@link Winnow}. Controls the number of stored
38 * features and implements pruning based on the LRU (least recently used)
39 * principle.
40 *
41 * <p>Instances of this class are synchronized externally by Winnow.
42 *
43 * @author Christian Siefkes
44 * @version $Revision: 1.15 $, $Date: 2004/12/06 17:58:06 $, $Author: siefkes $
45 */
46 public class WinnowStore implements Pruner {
47
48 /***
49 * The initial weight of each feature. This implementation prunes
50 * the one of the candidate features whose weights deviate least from this
51 * initial weight.
52 */
53 private final float initWeight;
54
55 /***
56 * Map storing the feature weights. Uses the hash codes (Integer) of
57 * features as keys and an array of floats storing the weight for each
58 * class as values.
59 */
60 private final AdaptableLRUMap store;
61
62 /***
63 * Creates a new instance.
64 *
65 * @param initialWeight The initial weight of each feature -- this
66 * implementation prunes features whose weights deviate least from this
67 * initial weight
68 * @param config Used to configure this instance
69 * @param configSuffix Optional suffix appended to the configuration keys
70 * when configuring this instance; might be <code>null</code>
71 */
72 public WinnowStore(final float initialWeight,
73 final TiesConfiguration config,
74 final String configSuffix) {
75 this(initialWeight,
76 config.getInt(config.adaptKey(
77 "classifier.winnow.features", configSuffix)),
78 config.getInt(config.adaptKey(
79 "prune.candidates", configSuffix)),
80 config.getInt(config.adaptKey(
81 "prune.num", configSuffix)));
82 }
83
84 /***
85 * Creates a new instance.
86 *
87 * @param initialWeight The initial weight of each feature -- this
88 * implementation prunes features whose weights deviate least from this
89 * initial weight
90 * @param featureNum The number of features to store
91 * @param candidates The number of candidates to consider for each pruning
92 * operation
93 * @param pruneNum The number of elements to remove by each pruning
94 * operation, must not be larger than <code>candidates</code>
95 */
96 public WinnowStore(final float initialWeight, final int featureNum,
97 final int candidates, final int pruneNum) {
98 super();
99 initWeight = initialWeight;
100 store = new AdaptableLRUMap(featureNum, this, candidates, pruneNum);
101 }
102
103 /***
104 * Returns the weights of a feature.
105 *
106 * @param featureHash The hash code integer identifying the feature
107 * @return The weights of this feature
108 */
109 public float[] getWeights(final Integer featureHash) {
110 return (float[]) store.get(featureHash);
111 }
112
113 /***
114 * Returns the maximum number of features that can be stored by this
115 * instance.
116 *
117 * @return the value of the attribute
118 */
119 public int maxSize() {
120 return store.maxSize();
121 }
122
123 /***
124 * Stores new weights for a feature.
125 *
126 * @param featureHash The hash code integer identifying the feature
127 * @param weights The new weights of this feature
128 */
129 public void putWeights(final Integer featureHash, final float[] weights) {
130 store.put(featureHash, weights);
131 }
132
133 /***
134 * Resets the store, completely deleting the prediction model.
135 */
136 public void reset() {
137 store.clear();
138 }
139
140 /***
141 * Returns the number of features currently stored by this instance.
142 *
143 * @return the value of the attribute
144 */
145 public int size() {
146 return store.size();
147 }
148
149 /***
150 * {@inheritDoc}
151 * This implementation sorts the candidate by the deviation of their weights
152 * from the initial weights, so candidates with lower deviation will be
153 * pruned first. This are candidates that were involved in fewer unbalanced
154 * promotions and demotions than the other candidate.
155 */
156 public Map.Entry[] sortForPruning(final Map.Entry[] candidates) {
157
158 Map.Entry candidate;
159 float[] weights;
160 float deviation;
161 int j;
162 MultiValueMap<Float, Integer> sortedMap =
163 new MultiValueMap<Float, Integer>(
164 new TreeMap<Float, Collection<Integer>>());
165
166 for (int i = 0; i < candidates.length; i++) {
167 candidate = candidates[i];
168
169 weights = (float[]) candidate.getValue();
170
171 deviation = 0;
172
173 for (j = 0; j < weights.length; j++) {
174 deviation += Math.abs(weights[j] - initWeight);
175 }
176
177
178 sortedMap.put(new Float(deviation), Integer.valueOf(i));
179 }
180
181
182 final Collection<Integer> sortedValues = sortedMap.values();
183 Iterator<Integer> valueIter = sortedValues.iterator();
184 final Map.Entry[] result = new Map.Entry[candidates.length];
185 int i = 0;
186
187 while (valueIter.hasNext()) {
188 result[i] = candidates[valueIter.next().intValue()];
189 i++;
190 }
191
192
193 if (i != candidates.length) {
194 throw new RuntimeException("Implementation error: Retrieved "
195 + i + " pruning candidates " + " instead of "
196 + candidates.length + " ones");
197 }
198
199 return result;
200 }
201
202 /***
203 * Returns a string representation of this object.
204 *
205 * @return a textual representation
206 */
207 public String toString() {
208 return new ToStringBuilder(this)
209 .append("current size", size())
210 .append("maximum size", maxSize())
211 .append("prune number", store.getPruneNumber())
212 .append("prune candidates", store.getCandidateNumber())
213 .toString();
214 }
215
216 }