fastentropy.h

   1
   2 //////////////////////////////////////////////////////////////////////////////////
   3 // This program is free software: you can redistribute it and/or modify         //
   4 // it under the terms of the version 3 of the GNU General Public License        //
   5 // as published by the Free Software Foundation.                                //
   6 //                                                                              //
   7 // This program is distributed in the hope that it will be useful, but          //
   8 // WITHOUT ANY WARRANTY; without even the implied warranty of                   //
   9 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU             //
  10 // General Public License for more details.                                     //
  11 //                                                                              //
  12 // You should have received a copy of the GNU General Public License            //
  13 // along with this program. If not, see <http://www.gnu.org/licenses/>.         //
  14 //                                                                              //
  15 // Written by Francois Fleuret                                                  //
  16 // Copyright (C) Ecole Polytechnique Federale de Lausanne                       //
  17 // Contact <francois.fleuret@epfl.ch> for comments & bug reports                //
  18 //////////////////////////////////////////////////////////////////////////////////
  19
  20 // $Id: fastentropy.h,v 1.3 2007-08-23 08:36:50 fleuret Exp $
  21
  22 #ifndef FASTENTROPY_H
  23 #define FASTENTROPY_H
  24
  25 #include <stdint.h>
  26
  27 // Lookup tables to speed up the training
  28
  29 extern int fe_nb_bits[65536];
  30 extern double fe_logn[65536], fe_nlogn[65536];
  31
  32 void fe_init_tables();
  33
  34 inline void fe_set_bit(int k, uint32_t *a, int v) {
  35   if(v) a[k/32] = a[k/32] |  (1 << (k%32));
  36   else  a[k/32] = a[k/32] & ~(1 << (k%32));
  37 }
  38
  39 inline int fe_get_bit(int k, uint32_t *a) {
  40   return a[k/32] & (1 << (k%32));
  41 }
  42
  43 inline int fe_count_and(int n, uint32_t *a, uint32_t *b) {
  44   uint16_t *aa = (uint16_t *) a, *bb = (uint16_t *) b;
  45   int t = 0;
  46   for(int k = 0; k < n/16; k++) t += fe_nb_bits[*aa++ & *bb++];
  47   if(n%16 > 0) t += fe_nb_bits[(65535 >> (16-(n%16))) & *aa & *bb];
  48   return t;
  49 }
  50
  51 inline int fe_count_and_not(int n, uint32_t *a, uint32_t *b) {
  52   uint16_t *aa = (uint16_t *) a,  *bb = (uint16_t *) b;
  53   int t = 0;
  54   for(int k = 0; k < n/16; k++) t += fe_nb_bits[*aa++ & ~*bb++];
  55   if(n%16 > 0) t += fe_nb_bits[(65535 >> (16-(n%16))) & *aa & ~*bb];
  56   return t;
  57 }
  58
  59 inline int fe_count_and_not_not(int n, uint32_t *a, uint32_t *b) {
  60   uint16_t *aa = (uint16_t *) a, *bb = (uint16_t *) b;
  61   int t = 0;
  62   for(int k = 0; k < n/16; k++) t += fe_nb_bits[65535 & ~*aa++ & ~*bb++];
  63   if(n%16 > 0) t += fe_nb_bits[(65535 >> (16-(n%16))) & ~*aa & ~*bb];
  64   return t;
  65 }
  66
  67 // This selection maximises the conditional mutual information between
  68 // the features and the class to predict, given any feature already
  69 // picked. Call fe_init_tables() beforehand.
  70
  71 void fe_selection_cmim(int nb_samples,
  72                        int nb_total_features, uint32_t **x, uint32_t *y,
  73                        int nb_selected, int *selected);
  74
  75 // This selection maximises the mutual information between the
  76 // features and the class to predict, without taking care of the
  77 // redundancy. Call fe_init_tables() beforehand.
  78
  79 void fe_selection_mim(int nb_samples,
  80                       int nb_total_features, uint32_t **x, uint32_t *y,
  81                       int nb_selected, int *selected);
  82
  83 #endif