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.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         // sort candidate by weight deviation
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             //Util.LOG.debug("Retrieving weights for " + i + "-th candidate");
169             weights = (float[]) candidate.getValue();
170             //Util.LOG.debug("Retrieved weights for candidate");
171             deviation = 0;
172 
173             for (j = 0; j < weights.length; j++) {
174                 deviation += Math.abs(weights[j] - initWeight);
175             }
176 
177             // map from weight deviations to collections of positions in the map
178             sortedMap.put(new Float(deviation), Integer.valueOf(i));
179         }
180 
181         // convert collected values into array; TreeMap sorts them by weight
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         // ensure that we retrieved all candidates
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 }