M5Tree.hh

Go to the documentation of this file.

#ifndef _M5TREE_HH_
#define _M5TREE_HH_

#include <rl_common/Random.h>
#include <rl_common/core.hh>
#include <vector>
#include <set>
#include <map>

#define N_M5_EXP 200000
#define N_M5_NODES 2500

#define BUILD_EVERY 0
#define BUILD_ON_ERROR 1
#define BUILD_EVERY_N 2
#define BUILD_ON_TERMINAL 3
#define BUILD_ON_TERMINAL_AND_ERROR 4

class M5Tree: public Classifier {

public:

  M5Tree(int id, int trainMode, int trainFreq, int m, 
         float featPct, bool simple, bool allowAllFeats, 
         float min_sdr, Random rng);

  M5Tree(const M5Tree&);

  virtual M5Tree* getCopy();

  ~M5Tree();

  // structs to be defined
  struct tree_node;
  struct tree_experience;
  
    
  struct tree_node {
    int id;

    // split criterion
    int dim;
    float val;
    bool leaf;

    // next nodes in tree
    tree_node *l;
    tree_node *r;
    
    // set of all outputs seen at this leaf/node
    int nInstances;

    // for regression model
    float constant;
    std::vector<float> coefficients;

  };

  struct tree_experience {
    std::vector<float> input;
    float output;
  };
  
  void copyTree(tree_node* newNode, tree_node* origNode);

  virtual bool trainInstance(classPair &instance);
  virtual bool trainInstances(std::vector<classPair> &instances);
  virtual void testInstance(const std::vector<float> &input, std::map<float, float>* retval);
  virtual float getConf(const std::vector<float> &input);

  void buildTree(tree_node* node, const std::vector<tree_experience*> &instances,  bool changed);

  // helper functions
  void initTree();

  void rebuildTree();

  void initTreeNode(tree_node* node);

  tree_node* traverseTree(tree_node* node, const std::vector<float> &input);

  tree_node* getCorrectChild(tree_node* node, const std::vector<float> &input);

  bool passTest(int dim, float val, const std::vector<float> &input);

  float calcSDR(int dim, float val, 
                       const std::vector<tree_experience*> &instances, float sd,
                        std::vector<tree_experience*> &left,
                        std::vector<tree_experience*> &right);

  float* sortOnDim(int dim, const std::vector<tree_experience*> &instances);

  std::set<float> getUniques(int dim, const std::vector<tree_experience*> &instances, float & minVal, float& maxVal);

  void deleteTree(tree_node* node);

  float calcSDforSet(const std::vector<tree_experience*> &instances);

  void printTree(tree_node *t, int level);

  void testPossibleSplits(const std::vector<tree_experience*> &instances, 
                          float *bestSDR, int *bestDim, 
                          float *bestVal, 
                          std::vector<tree_experience*> *bestLeft, 
                          std::vector<tree_experience*> *bestRight);
  
  void implementSplit(tree_node* node, 
                      const std::vector<tree_experience*> &instances,
                      float bestSDR, int bestDim,
                      float bestVal, 
                      const std::vector<tree_experience*> &left, 
                      const std::vector<tree_experience*> &right,
                      bool changed);
  
  void compareSplits(float sdr, int dim, float val, 
                     const std::vector<tree_experience*> &left, 
                     const std::vector<tree_experience*> &right,
                     int *nties, float *bestSDR, int *bestDim, 
                     float *bestVal, 
                     std::vector<tree_experience*> *bestLeft, 
                     std::vector<tree_experience*> *bestRight);
  
  void leafPrediction(tree_node *t, const std::vector<float> &in, std::map<float, float>* retval);
  
  void makeLeaf(tree_node* node);

  void removeChildren(tree_node* node);

  void pruneTree(tree_node* node, const std::vector<tree_experience*> &instances);
  
  int fitLinearModel(tree_node* node, const std::vector<tree_experience*> &instances,
                     std::vector<bool> featureMask, int nFeats, float* resSum);

  int fitSimpleLinearModel(tree_node* node, const std::vector<tree_experience*> &instances,
                     std::vector<bool> featureMask, int nFeats, float* resSum);

  void getFeatsUsed(tree_node* node, std::vector<bool> *featsUsed);

  tree_node* allocateNode();
  
  void deallocateNode(tree_node* node);
  
  void initNodes();

  bool INCDEBUG;
  bool DTDEBUG;
  bool LMDEBUG;
  bool SPLITDEBUG;
  bool STOCH_DEBUG;
  bool NODEDEBUG;
  bool COPYDEBUG;
  int nExperiences;

  float SPLIT_MARGIN;

private:

  const int id;
  
  const int mode;
  const int freq;
  const int M;
  float featPct; 
  const bool SIMPLE;
  const bool ALLOW_ALL_FEATS;
  const float MIN_SDR;

  Random rng;

  int nfeat;

  int nOutput;
  int nnodes;
  bool hadError;
  int totalnodes;
  int maxnodes;

  // INSTANCES
  std::vector<tree_experience*> experiences;
  
  tree_experience allExp[N_M5_EXP];
  
  tree_node allNodes[N_M5_NODES];
  std::vector<int> freeNodes;

  // TREE
  tree_node* root;
  tree_node* lastNode;

};


#endif