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.HashSet;
25  import java.util.Iterator;
26  import java.util.Set;
27  import java.util.TreeSet;
28  
29  import org.apache.commons.lang.builder.ToStringBuilder;
30  
31  import de.fu_berlin.ties.ContextMap;
32  import de.fu_berlin.ties.ProcessingException;
33  import de.fu_berlin.ties.TiesConfiguration;
34  import de.fu_berlin.ties.classify.PredictionDistribution;
35  import de.fu_berlin.ties.classify.TrainableClassifier;
36  import de.fu_berlin.ties.classify.feature.Feature;
37  import de.fu_berlin.ties.classify.feature.FeatureSet;
38  import de.fu_berlin.ties.classify.feature.FeatureTransformer;
39  import de.fu_berlin.ties.classify.feature.FeatureVector;
40  import de.fu_berlin.ties.util.Util;
41  
42  /***
43   * Classifier implementing the Winnow algorithm (Nick Littlestone). <b>Winnow
44   * supports <em>only</em> error-driven training, so you always have to use the
45   * {@link #trainOnError(FeatureVector, String, Set)} method. Trying to
46   * call the {@link
47   * de.fu_berlin.ties.classify.TrainableClassifier#train(FeatureVector, String)}
48   * method instead will result in an
49   * {@link java.lang.UnsupportedOperationException}.</b>
50   *
51   * <p>Instances of this class are thread-safe.
52   *
53   * @author Christian Siefkes
54   * @version $Revision: 1.34 $, $Date: 2004/11/17 09:16:27 $, $Author: siefkes $
55   */
56  public class Winnow extends TrainableClassifier {
57  
58      /***
59       * Configuration key: How feature frequencies are considered when
60       * calculating strength values.
61       */
62      private static final String CONFIG_STRENGTH_METHOD =
63          "classifier.winnow.strength.frequency";
64  
65      /***
66       * Whether the Balanced Winnow or the standard Winnow algorithm is used.
67       * Balanced Winnow keeps <code>two</code> weights per feature and class,
68       * a positive and a negative one.
69       */
70      private final boolean balanced;
71  
72      /***
73       * The promotion factor used by the algorithm.
74       */
75      private final float promotion;
76  
77      /***
78       * The demotion factor used by the algorithm.
79       */
80      private final float demotion;
81  
82      /***
83       * The thickness of the threshold if the "thick threshold" heuristic is used
84       * (must be &lt; 1.0), 0.0 otherwise.
85       */
86      private final float thresholdThickness;
87  
88      /***
89       * Stores the feature weights, using a variation of the LRU mechanism for
90       * pruning surplus features. Every access should be synchronized on
91       * <strong>this</strong>.
92       */
93      private final WinnowStore store;
94  
95      /***
96       * Creates a new instance based on the
97       * {@linkplain TiesConfiguration#CONF standard configuration}.
98       *
99       * @param allValidClasses the set of all valid classes
100      * @throws IllegalArgumentException if one of the parameters is outside
101      * the allowed range
102      * @throws ProcessingException if an error occurred while creating
103      * the feature transformer(s)
104      */
105     public Winnow(final Set<String> allValidClasses)
106     throws IllegalArgumentException, ProcessingException {
107         this(allValidClasses, (String) null);
108     }
109 
110     /***
111      * Creates a new instance based on the
112      * {@linkplain TiesConfiguration#CONF standard configuration}.
113      *
114      * @param allValidClasses the set of all valid classes
115      * @param configSuffix optional suffix appended to the configuration keys
116      * when configuring this instance; might be <code>null</code>
117      * @throws IllegalArgumentException if one of the parameters is outside
118      * the allowed range
119      * @throws ProcessingException if an error occurred while creating
120      * the feature transformer(s)
121      */
122     protected Winnow(final Set<String> allValidClasses, final String configSuffix)
123     throws IllegalArgumentException, ProcessingException {
124         this(allValidClasses, TiesConfiguration.CONF, configSuffix);
125     }
126 
127     /***
128      * Creates a new instance based on the provided configuration.
129      *
130      * @param allValidClasses the set of all valid classes
131      * @param config contains configuration properties
132      * @throws IllegalArgumentException if one of the parameters is outside
133      * the allowed range
134      * @throws ProcessingException if an error occurred while creating
135      * the feature transformer(s)
136      */
137     public Winnow(final Set<String> allValidClasses,
138             final TiesConfiguration config)
139     throws IllegalArgumentException, ProcessingException {
140         this(allValidClasses, config, null);
141     }
142 
143     /***
144      * Creates a new instance based on the provided configuration.
145      *
146      * @param allValidClasses the set of all valid classes
147      * @param config contains configuration properties
148      * @param configSuffix optional suffix appended to the configuration keys
149      * when configuring this instance; might be <code>null</code>
150      * @throws IllegalArgumentException if one of the parameters is outside
151      * the allowed range
152      * @throws ProcessingException if an error occurred while creating
153      * the feature transformer(s)
154      */
155     protected Winnow(final Set<String> allValidClasses,
156             final TiesConfiguration config, final String configSuffix)
157     throws IllegalArgumentException, ProcessingException {
158         this(allValidClasses, FeatureTransformer.createTransformer(config),
159             config, configSuffix);
160     }
161 
162     /***
163      * Creates a new instance based on the provided configuration.
164      *
165      * @param allValidClasses the set of all valid classes
166      * @param trans the last transformer in the transformer chain to use, or
167      * <code>null</code> if no feature transformers should be used
168      * @param config contains configuration properties
169      * @throws IllegalArgumentException if one of the parameters is outside
170      * the allowed range
171      * @throws ProcessingException if an error occurred while creating
172      * the feature transformer(s)
173      */
174     public Winnow(final Set<String> allValidClasses,
175             final FeatureTransformer trans, final TiesConfiguration config)
176     throws IllegalArgumentException, ProcessingException {
177         this(allValidClasses, trans, config, null);
178     }
179 
180     /***
181      * Creates a new instance based on the provided configuration.
182      *
183      * @param allValidClasses the set of all valid classes
184      * @param trans the last transformer in the transformer chain to use, or
185      * <code>null</code> if no feature transformers should be used
186      * @param config contains configuration properties
187      * @param configSuffix optional suffix appended to the configuration keys
188      * when configuring this instance; might be <code>null</code>
189      * @throws IllegalArgumentException if one of the parameters is outside
190      * the allowed range
191      * @throws ProcessingException if an error occurred while creating
192      * the feature transformer(s)
193      */
194     protected Winnow(final Set<String> allValidClasses,
195             final FeatureTransformer trans, final TiesConfiguration config,
196             final String configSuffix)
197     throws IllegalArgumentException, ProcessingException {
198         this(allValidClasses, trans,
199             config.getBoolean(
200                 config.adaptKey("classifier.winnow.balanced", configSuffix)),
201             config.getFloat(
202                 config.adaptKey("classifier.winnow.promotion", configSuffix)),
203             config.getFloat(
204                 config.adaptKey("classifier.winnow.demotion", configSuffix)),
205             config.getFloat(config.adaptKey(
206                 "classifier.winnow.threshold.thickness", configSuffix)),
207             config, configSuffix);
208     }
209 
210     /***
211      * Creates a new instance.
212      *
213      * @param allValidClasses the set of all valid classes
214      * @param trans the last transformer in the transformer chain to use, or
215      * <code>null</code> if no feature transformers should be used
216      * @param balance whether to use the Balanced Winnow or the standard
217      * Winnow algorithm
218      * @param promotionFactor the promotion factor used by the algorithm;
219      * must be &gt; 1.0
220      * @param demotionFactor the demotion factor used by the algorithm; must
221      * be &lt; 1.0
222      * @param thresholdThick the thickness of the threshold if the "thick
223      * threshold" heuristic is used (must be &lt; 1.0), 0.0 otherwise
224      * @param config contains configuration properties
225      * @param configSuffix optional suffix appended to the configuration keys
226      * when configuring this instance; might be <code>null</code>
227      * @throws IllegalArgumentException if one of the parameters is outside
228      * the allowed range
229      */
230     public Winnow(final Set<String> allValidClasses,
231             final FeatureTransformer trans, final boolean balance,
232             final float promotionFactor, final float demotionFactor,
233             final float thresholdThick, final TiesConfiguration config,
234             final String configSuffix) throws IllegalArgumentException {
235         // wrap classes in a tree set to ensure that they are sorted
236         super(new TreeSet<String>(allValidClasses), trans, config);
237 
238         // check arguments
239         if ((promotionFactor <= 1.0)) {
240             throw new IllegalArgumentException("Promotion factor must be > 1: "
241                 + promotionFactor);
242         }
243         if ((demotionFactor >= 1.0) || (demotionFactor <= 0.0)) {
244             throw new IllegalArgumentException(
245                 "Demotion factor must be in ]0, 1[ range:" + demotionFactor);
246         }
247         if ((thresholdThick >= 1.0) || (thresholdThick < 0.0)) {
248             throw new IllegalArgumentException("Threshold thickness must be "
249                 + "in [0, 1[ range: " + thresholdThick);
250         }
251 
252         // store arguments + initialize feature cache of specified size
253         balanced = balance;
254         promotion = promotionFactor;
255         demotion = demotionFactor;
256         thresholdThickness = thresholdThick;
257         store = new WinnowStore(initWeight(), config, configSuffix);
258     }
259 
260     /***
261      * Adjusts the weights of a feature for all classes. This method should be
262      * called in a synchronized context.
263      *
264      * @param feature the feature to process
265      * @param directions an array specifying for each class (in alphabetic
266      * order) whether it should be promoted (positive value), demoted (negative
267      * value) or left unmodified (0)
268      */
269     protected void adjustWeights(final Feature feature,
270             final short[] directions) {
271         // use hashcode of feature to retrieve weights
272         final Integer featureHash = new Integer(feature.hashCode());
273         float[] weights = store.getWeights(featureHash);
274         final int length = getAllClasses().size();
275 
276         // check argument
277         if (directions.length != length) {
278             throw new IllegalArgumentException("Array of directions has "
279                 + directions.length + " members instead of one for each of the "
280                 + length + " classes");
281         }
282 
283         if (weights == null) {
284             // initialize and store weights
285             weights = initWeightArray();
286             store.putWeights(featureHash, weights);
287         }
288 
289         // promote/demote (positive) weights as specified
290         // (stored in fields from 0 to n-1)
291         for (int i = 0; i < length; i++) {
292             if (directions[i] < 0) {
293                 // demote (positive) weight
294                 weights[i] *= demotion;
295 
296                 if (balanced) {
297                     // promote negative weight
298                     weights[i + length] *= promotion;
299                 }
300             } else if (directions[i] > 0) {
301                 // promote positive weight
302                 weights[i] *= promotion;
303 
304                 if (balanced) {
305                     // demote negative weight
306                     weights[i + length] *= demotion;
307                 }
308             }
309             // otherwise (0) there is nothing to do
310         }
311     }
312 
313     /***
314      * Chooses the classes to promote and the classes to demote. This class
315      * chooses the <code>targetClass</code> for promotion if its score is
316      * less or equal to the {@linkplain #threshold(float) threshold}.
317      * It chooses all other classes for demotion if their score is greather
318      * than the threshold.
319      *
320      * @param winnowDist the prediction distribution returned by
321      * {@link #classify(FeatureVector, Set)}
322      * @param targetClass the expected class of this instance; must be
323      * contained in the set of <code>candidateClasses</code>
324      * @param classesToPromote the classes to promote are added to this set
325      * @param classesToDemote the classes to demote are added to this set
326      */
327     protected void chooseClassesToAdjust(final WinnowDistribution winnowDist,
328             final String targetClass, final Set<String> classesToPromote,
329             final Set<String> classesToDemote) {
330         final Iterator predIter = winnowDist.iterator();
331         WinnowPrediction pred;
332 
333         // use thick threshold heuristic if configured
334         final float minorThreshold = minorThreshold(winnowDist.getThreshold(),
335             winnowDist.getRawThreshold());
336         final float majorThreshold = majorThreshold(winnowDist.getThreshold(),
337             winnowDist.getRawThreshold());
338 
339 /*        // tracing for Bill
340         Util.LOG.debug("Threshold=" + winnowDist.getThreshold()
341                 + " (minor=" + minorThreshold
342                 + " major=" + majorThreshold + ')'); */
343 
344         while (predIter.hasNext()) {
345             pred = (WinnowPrediction) predIter.next();
346 
347             if (targetClass.equals(pred.getType())) {
348                 // this is the target class
349                 if (pred.getRawScore() <= majorThreshold) {
350                     classesToPromote.add(pred.getType());
351                 }
352             } else {
353                 if (pred.getRawScore() > minorThreshold) {
354                     // this class should be demoted
355                     classesToDemote.add(pred.getType());
356                 }
357             }
358         }
359     }
360 
361     /***
362      * Converts a {@linkplain #sigmoid(float, float, float) sigmoid activation
363      * value} into a confidence estimate.
364      *
365      * @param sigmoid the {@linkplain #sigmoid(float, float, float) sigmoid
366      * activation value} to convert
367      * @param sum the sum of all sigmoid activation values
368      * @return the estimated confidence: <code>sigmoid / sum</code>
369      */
370     protected double confidence(final float sigmoid, final float sum) {
371         return (double) sigmoid / sum;
372     }
373 
374     /***
375      * Returns the default weight to use if a feature is unknown. This
376      * implementation returns 0.0 in case of {@link #isBalanced() Balanced
377      * Winnow} (where positive and negative weights should cancel each other
378      * out), {@link #initWeight()} otherwise.
379      *
380      * @return the default weight
381      */
382     protected float defaultWeight() {
383         if (balanced) {
384             return 0.0f;
385         } else {
386             return initWeight();
387         }
388     }
389 
390     /***
391      * {@inheritDoc}
392      */
393     protected PredictionDistribution doClassify(final FeatureVector features,
394             final Set candidateClasses, final ContextMap context) {
395         // convert to (multi-)set if required
396         final FeatureSet featureSet = featureSet(features);
397         final float[] scores = initScores();
398         final Iterator featureIter = featureSet.iterator();
399         Feature currentFeature;
400 
401 /*        // tracing for Bill
402         Util.LOG.debug("Unique OSB features: " + featureSet.size());
403         Util.LOG.debug("Stored features: " + store.size()); */
404 
405         synchronized (this) {
406             // iterate over all feature to calculate score for each class
407             while (featureIter.hasNext()) {
408                 currentFeature = (Feature) featureIter.next();
409                 updateScores(currentFeature, features.strength(currentFeature),
410                         scores);
411             }
412         }
413 
414         // calculate threshold and sigmoid activation values
415         final float rawThreshold = rawThreshold(featureSet);
416         final float threshold = threshold(rawThreshold);
417         final float[] sigmoids = new float[scores.length];
418         float sigmoidSum = 0.0f;
419         int i;
420 
421         for (i = 0; i < scores.length; i++) {
422             sigmoids[i] = sigmoid(scores[i], threshold, rawThreshold);
423             sigmoidSum += sigmoids[i];
424         }
425 
426         // create winnow distribution to store results
427         final WinnowDistribution result =
428             new WinnowDistribution(threshold, rawThreshold);
429 
430         // add WinnowPredictions in alphabetic order; the will be automatically
431         // sorted according to the confidence values
432         final Iterator classIter = candidateClasses.iterator();
433         String className;
434         i = 0;
435 
436         while (classIter.hasNext()) {
437             className = (String) classIter.next();
438             result.add(new WinnowPrediction(className,
439                 confidence(sigmoids[i], sigmoidSum), scores[i], sigmoids[i]));
440             i++;
441         }
442 
443 /*        // tracing for Bill
444         final StringBuilder scoreTrace = new StringBuilder("Scores:");
445         final Iterator predIter = result.iterator();
446         WinnowPrediction pred;
447         while (predIter.hasNext()) {
448             pred = (WinnowPrediction) predIter.next();
449             scoreTrace.append(' ' + pred.getType() + '=' + pred.getRawScore());            
450         }
451         Util.LOG.debug(scoreTrace.toString()); */
452 
453         return result;
454     }
455 
456     /***
457      * <b>Winnow supports <em>only</em> error-driven training, so you always
458      * have to use the {@link #trainOnError(FeatureVector, String, Set)} method
459      * instead of this one. Trying to call this method instead will result in an
460      * {@link java.lang.UnsupportedOperationException}.</b>
461      *
462      * @param features ignored by this method
463      * @param targetClass ignored by this method
464      * @param context ignored by this method
465      * @throws UnsupportedOperationException always thrown by this method;
466      * use {@link #trainOnError(FeatureVector, String, Set)} instead
467      */
468     protected void doTrain(final FeatureVector features,
469             final String targetClass, final ContextMap context)
470     throws UnsupportedOperationException {
471         // we cannot support this method because we need to know all
472         // candidate classes for updating
473         throw new UnsupportedOperationException("Winnow supports only "
474             + "error-driven training -- call trainOnError instead of train");
475     }
476 
477     /***
478      * Converts a feature vector into a {@link FeatureSet} (a multi-set of
479      * features). If the provided vector already is a <code>FeatureSet</code>
480      * instance, it is casted and returned. Otherwise a new
481      * <code>FeatureSet</code> with the same contents is created, reading the
482      * used method for considering feature frequencies in strength values
483      * from the "classifier.winnow.strength.frequency" configuration key.
484      *
485      * @param fv the feature vector to convert
486      * @return a feature set with the same contents as the provided vector
487      */
488     protected FeatureSet featureSet(final FeatureVector fv) {
489         final FeatureSet result;
490 
491         if (fv instanceof FeatureSet) {
492             result = (FeatureSet) fv;
493         } else {
494             result = new FeatureSet(getConfig().getString(
495                 CONFIG_STRENGTH_METHOD));
496             result.addAll(fv);
497         }
498 
499         return result;
500     }
501 
502     /***
503      * Returns the promotion factor used by the algorithm.
504      *
505      * @return the value of the attribute
506      */
507     public float getDemotion() {
508         return demotion;
509     }
510 
511     /***
512      * Returns the demotion factor used by the algorithm.
513      *
514      * @return the value of the attribute
515      */
516     public float getPromotion() {
517         return promotion;
518     }
519 
520     /***
521      * Whether the Balanced Winnow or the standard Winnow algorithm is used.
522      * Balanced Winnow keeps <em>two</em> weights per feature and class,
523      * a positive and a negative one.
524      *
525      * @return the value of the attribute
526      */
527     public boolean isBalanced() {
528         return balanced;
529     }
530 
531     /***
532      * Initializes the score (activation values) to use for all classes.
533      *
534      * @return an array of floats containing the initial score for each class;
535      * the value of each float will be 0.0
536      */
537     protected float[] initScores() {
538         // each float is automatically initialized to 0.0
539         final float[] result = new float[getAllClasses().size()];
540         return result;
541     }
542 
543     /***
544      * Returns the thickness of the threshold if the "thick threshold"
545      * heuristic is used.
546      *
547      * @return the value of the attribute, will be &lt; 1.0; 0.0 if no
548      * thick threshold is used
549      */
550     public float getThresholdThickness() {
551         return thresholdThickness;
552     }
553 
554     /***
555      * Returns the initial weight to use for each feature per class. This
556      * implementation returns 1.0.
557      *
558      * @return the initial weight
559      */
560     protected float initWeight() {
561         return 1.0f;
562     }
563 
564     /***
565      * Returns the initial weight array to use for a feature for all classes.
566      * The array returns by this implementation fill contain one weight for
567      * each class in case of normal Winnow, two weights in case of
568      * {@link #isBalanced() Balanced} Winnow. Each element is initialized to
569      * {@link #initWeight()}.
570      *
571      * @return the initial weight array
572      */
573     protected float[] initWeightArray() {
574         final float[] result;
575 
576         if (balanced) {
577             // store positive and negatives weight for each class
578             result = new float[getAllClasses().size() * 2];
579         } else {
580             // store weight for each class
581             result = new float[getAllClasses().size()];
582         }
583 
584         // initialize each value
585         final float initWeight = initWeight();
586         for (int i = 0; i < result.length; i++) {
587             result[i] = initWeight;
588         }
589 
590         return result;
591     }
592 
593     /***
594      * Calculates the major theshold (<em>theta+</em>) to use for classification
595      * with the "thick threshold" heuristic. This
596      * implementation multiplies <em>theta<sub>r</sub></em> with the
597      * {@linkplain #getThresholdThickness() threshold thickness} and adds
598      * the result to <em>theta</em>. Subclasses can overwrite this method to
599      * calculate the major theshold in a different way.
600      *
601      * @param threshold the {@linkplain #threshold(float) threshold}
602      * <em>theta</em>
603      * @param rawThreshold the {@linkplain #rawThreshold(FeatureSet) raw
604      * threshold} <em>theta<sub>r</sub></em>
605      * @return the major theshold (<em>theta+</em>) to use for classification
606      * @see #minorThreshold(float, float)
607      */
608     protected float majorThreshold(final float threshold,
609             final float rawThreshold) {
610        final float result =  threshold + getThresholdThickness() * rawThreshold;
611        return result;
612     }
613 
614     /***
615      * Calculates the minor theshold (<em>theta-</em>) to use for classification
616      * with the "thick threshold" heuristic. This
617      * implementation multiplies <em>theta<sub>r</sub></em> with the
618      * {@linkplain #getThresholdThickness() threshold thickness} and subtracts
619      * the result from <em>theta</em>. Subclasses can overwrite this method to
620      * calculate the minor theshold in a different way.
621      *
622      * @param threshold the {@linkplain #threshold(float) threshold}
623      * <em>theta</em>
624      * @param rawThreshold the {@linkplain #rawThreshold(FeatureSet) raw
625      * threshold} <em>theta<sub>r</sub></em>
626      * @return the minor theshold (<em>theta-</em>) to use for classification
627      * @see #majorThreshold(float, float)
628      */
629     protected float minorThreshold(final float threshold,
630             final float rawThreshold) {
631         final float result = threshold - getThresholdThickness() * rawThreshold;
632         return result;
633     }
634 
635     /***
636      * Calculates the theshold (theta) to use for classification, based on the
637      * number of active features. This implementation returns the
638      * {@linkplain FeatureVector#getSummedStrength() summed strength} of all
639      * features. Subclasses can overwrite this method to calculate the theshold
640      * in a different way.
641      *
642      * @param features the feature set to consider
643      * @return the raw theshold (theta) to use
644      */
645     protected float rawThreshold(final FeatureSet features) {
646         return (float) features.getSummedStrength();
647     }
648 
649     /***
650      * {@inheritDoc}
651      */
652     public void reset() {
653         store.reset();
654     }
655 
656     /***
657      * Converts the raw <em>score</em> (activation value) to a value in the
658      * range from 0 to 1 via a sigmoid function depending on the threshold
659      * <em>theta</em>. In this implementation this is calculed as follows:
660      *
661      * <ul>
662      * <li>Normal Winnow (not balanced): <em>sigma</em>(<em>score</em>,
663      * <em>theta</em>) = 1 / (1 + (<em>theta</em> / <em>score</em>))</li>
664      * <li>{@linkplain #isBalanced() Balanced} Winnow:
665      * <em>sigma</em>(<em>score</em>, <em>theta</em>,
666      * <em>theta<sub>r</sub></em>) = 1 / (1 +
667      * e^((<em>theta</em> - <em>score</em>) / <em>theta<sub>r</sub></em>))</li>
668      * </ul>
669      *
670      * @param score the raw <em>score</em> (activation value); must be a
671      * positive value in case of normal (non-balanced) Winnow
672      * @param threshold the {@linkplain #threshold(float) threshold}
673      * <em>theta</em> used for this instance
674      * @param rawThreshold the {@linkplain #rawThreshold(FeatureSet) raw
675      * threshold} <em>theta<sub>r</sub></em> used for this instance
676      * @return the sigmoid score calculated as described above; will be in range
677      * from 0 to 1
678      * @throws IllegalArgumentException if normal Winnow is used and
679      * <code>score &lt;= 0</code>
680      */
681     protected float sigmoid(final float score, final float threshold,
682             final float rawThreshold) throws IllegalArgumentException {
683         if (balanced) {
684             return (float) (1.0 / (1.0
685                             + Math.exp((threshold - score) / rawThreshold)));
686         } else {
687             // ensure that the score is positive
688             if (score <= 0.0f) {
689                 throw new IllegalArgumentException(
690                     "Activation value must be positive in normal Winnow: "
691                     + score);
692             }
693 
694             return 1.0f / (1.0f + (threshold / score));
695         }
696     }
697 
698     /***
699      * Calculates the theshold (theta) to use for classification. This
700      * implementation returns the <code>rawThreshold</code> multiplied with
701      * the {@linkplain #defaultWeight() default weight}. Subclasses can
702      * overwrite this method to calculate the theshold in a different way.
703      *
704      * @param rawThreshold the {@linkplain #rawThreshold(FeatureSet) raw
705      * threshold}
706      * @return the theshold (theta) to use for classification
707      */
708     protected float threshold(final float rawThreshold) {
709         return rawThreshold * defaultWeight();
710     }
711 
712     /***
713      * Hook implementing error-driven learning, promoting and demoting weights
714      * as required.
715      *
716      * @param predDist the prediction distribution returned by
717      * {@link #classify(FeatureVector, Set)}; must be a
718      * {@link WinnowDistribution}
719      * @param features the feature vector to consider
720      * @param targetClass the expected class of this feature vector; must be
721      * contained in the set of <code>candidateClasses</code>
722      * @param candidateClasses an set of classes that are allowed for this item
723      * (the actual <code>targetClass</code> must be one of them)
724      * @param context ignored by this implementation
725      * @return this implementation always returns <code>true</code> to signal
726      * that any error-driven learning was already handled
727      * @throws ProcessingException if an error occurs during training
728      */
729     protected boolean trainOnErrorHook(final PredictionDistribution predDist,
730             final FeatureVector features, final String targetClass,
731             final Set candidateClasses, final ContextMap context)
732     throws ProcessingException {
733         // convert to (multi-)set if required
734         final FeatureSet featureSet = featureSet(features);
735 
736         final Set<String> classesToPromote = new HashSet<String>();
737         final Set<String> classesToDemote = new HashSet<String>();
738 
739         // decide which classes to promote and demote
740         chooseClassesToAdjust((WinnowDistribution) predDist, targetClass,
741             classesToPromote, classesToDemote);
742 
743         if (!(classesToPromote.isEmpty() && classesToDemote.isEmpty())) {
744             // there are class(es) to promote/demote
745             Util.LOG.debug("Promoting classes: " + classesToPromote
746                 + "; demoting classes: " + classesToDemote);
747 
748             // iterate classes in alphabetic order to specify directions
749             final short[] directions = new short[getAllClasses().size()];
750             final Iterator classIter = getAllClasses().iterator();
751             String currentClass;
752             int i = 0;
753 
754             while (classIter.hasNext()) {
755                 currentClass = (String) classIter.next();
756                 if (classesToDemote.contains(currentClass)) {
757                     // demote this class
758                     directions[i] = -1;
759                 } else if (classesToPromote.contains(currentClass)) {
760                     // promote this class
761                     directions[i] = 1;
762                 } else {
763                     // don't modify class
764                     directions[i] = 0;
765                 }
766                 i++;
767             }
768 
769             final Iterator featureIter = featureSet.iterator();
770             Feature currentFeature;
771 
772             synchronized (this) {
773                 // iterate over all feature to promote/demote weights
774                 while (featureIter.hasNext()) {
775                     currentFeature = (Feature) featureIter.next();
776                     adjustWeights(currentFeature, directions);
777                 }
778             }
779         }
780 
781         // signal that we handled the training
782         return true;
783     }
784 
785     /***
786      * Returns a string representation of this object.
787      *
788      * @return a textual representation
789      */
790     public String toString() {
791         return new ToStringBuilder(this)
792             .appendSuper(super.toString())
793             .append("balanced", balanced)
794             .append("promotion", promotion)
795             .append("demotion", demotion)
796             .append("threshold thickness", thresholdThickness)
797             .append("frequency-based strength",
798                 getConfig().getString(CONFIG_STRENGTH_METHOD))
799             .append("feature store", store)
800             .toString();
801     }
802 
803     /***
804      * Updates the score (activation values) for all classes by adding the
805      * weights of a feature. This method should be called in a synchronized
806      * context.
807      *
808      * @param feature the feature to process
809      * @param strength the strength of this feature
810      * @param scores an array of floats containing the scores for each
811      * class; will be updated by this method
812      */
813     protected void updateScores(final Feature feature, final double strength,
814                                 final float[] scores) {
815         // use hashcode of feature to retrieve weights
816         final float[] weights =
817             store.getWeights(new Integer(feature.hashCode()));
818         final int length = getAllClasses().size();
819 
820         // check argument
821         if (scores.length != length) {
822             throw new IllegalArgumentException("Array of scores has "
823                 + scores.length + " members instead of one for each of the "
824                 + length + " classes");
825         }
826 
827         if (weights != null) {
828             // add (positive) weighted strength to each score
829             // (weights stored in fields from 0 to n-1)
830             for (int i = 0; i < length; i++) {
831                 scores[i] += weights[i] * strength;
832             }
833 
834             if (balanced) {
835                 // Balanced Winnow: subtract negative weighted strengths
836                 // (weights stored in the fields from n to 2n-1)
837                 for (int i = 0; i < length; i++) {
838                     scores[i] -= weights[i + length] * strength;
839                 }
840             }
841         } else {
842             final float defaultWeight = defaultWeight();
843 
844             // add default weight * strength to each score
845             if (defaultWeight != 0.0f) {
846                 for (int i = 0; i < length; i++) {
847                     scores[i] += defaultWeight * strength;
848                 }
849             }
850         }
851     }
852 
853 }