TQRF.h

#ifndef __TQRF_H__
#define __TQRF_H__
//
// TQRF
//
 
#include <Logger/Logger/Logger.h>
#include <SerializableObject/SerializableObject/SerializableObject.h>
#include <MedProcessTools/MedProcessTools/MedFeatures.h>
#include <MedMat/MedMat/MedMat.h>
#include <MedTime/MedTime/MedTime.h>
#include <queue>
 
using namespace std;
 
enum TQRF_TreeTypes {
    TQRF_TREE_ENTROPY = 0,
    TQRF_TREE_REGRESSION = 1,
    TQRF_TREE_LIKELIHOOD = 2,
    TQRF_TREE_WEIGHTED_LIKELIHOOD = 3,
    TQRF_TREE_DEV = 4, // free place to use when developing new score ideas
    TQRF_TREE_UNDEFINED = 5
};
 
enum TQRF_Missing_Value_Method {
    TQRF_MISSING_VALUE_MEAN = 0,
    TQRF_MISSING_VALUE_MEDIAN = 1,
    TQRF_MISSING_VALUE_LARGER_NODE = 2,
    TQRF_MISSING_VALUE_LEFT = 3,
    TQRF_MISSING_VALUE_RIGHT = 4,
    TQRF_MISSING_VALUE_RAND_ALL = 5,
    TQRF_MISSING_VALUE_RAND_EACH_SAMPLE = 6,
    TQRF_MISSING_VALUE_NOTHING = 7
};
 
 
enum TQRF_Node_Working_State {
    TQRF_Node_State_Initiated = 0,
    TQRF_Node_State_In_Progress = 1,
    TQRF_Node_State_Done = 2
};
 
enum TQRF_Missing_Direction {
    TQRF_MISSING_DIRECTION_LEFT = 0,
    TQRF_MISSING_DIRECTION_RIGHT = 1,
    TQRF_MISSING_DIRECTION_RAND_EACH_SAMPLE = 2
};
 
#define TQRF_MAX_TIME_SLICE         10000000
#define MIN_ELEMENTS_IN_TIME_SLICE  100
#define UNSET_BETA  ((float)-1e-10)
 
 
//==========================================================================================================================
class TQRF_Params : public SerializableObject {
public:
 
    //========================================================================================================================
    // params list
    //========================================================================================================================
    string init_string = "";            
    string samples_time_unit = "Date";
    int samples_time_unit_i; 
 
    int ncateg = 2;         
 
    // time slices
    string time_slice_unit = "Days";
    int time_slice_unit_i; 
    int time_slice_size = -1;           
    int n_time_slices = 1;              
    vector<int> time_slices = {};       
    
    vector<float> time_slices_wgts ={}; 
    int censor_cases = 0;               
 
    // quantization
    int max_q = 200;                    
    //int max_q_sample = 100000;            /// the max number of values to use when deciding q limits
 
    // trees and stopping criteria
    string tree_type = "";              
    int tree_type_i = -1;               
    int ntrees = 50;                    
    int max_depth = 100;                
    int min_node_last_slice = 10;       
    int min_node = 10;                  
    float random_split_prob = 0;        
 
    // feature sampling
    int ntry = -1;                      
    float ntry_prob = (float)0.1;       
    int nsplits = -1;                   
 
    // speedup by subsample control
    int max_node_test_samples = 50000;  
 
    // bagging control
    int single_sample_per_pid = 1;      
    int bag_with_repeats = 1;           
    float bag_prob = (float)0.5;        
    float bag_ratio = -1;               
    float bag_feat = (float)1.0;        
    int qpoints_per_split = 0;          
 
    // categorial featues
    int nvals_for_categorial = 0;           
    vector<string> categorial_str;      
    vector<string> categorial_tags;     
    //vector<int> categorial;               /// calculated from the above (in learning, once train data is given. In testing - already ready)
 
    // missing value
    float missing_val = MED_MAT_MISSING_VALUE;  
    string missing_method_str = "median";       
    int missing_method = -1;                    
 
    // sanities
    int test_for_inf = 1;               
    int test_for_missing = 0;           
 
    // prediction configuration
    int only_this_categ = -1;           
    int predict_from_slice = -1;        
    int predict_to_slice = -1;
    int predict_sum_times = 0;          
 
 
    // weights
    float case_wgt = 1;                 
 
    // ada boost mode
    int nrounds = 1;                    
    float min_p = (float)0.01;          
    float max_p = (float)0.99;          
    float alpha = 1;                    
    float wgts_pow = 2;                 
 
    // lists
    float tuning_size = 0;              
    int tune_max_depth = 0;             
    int tune_min_node_size = 0;         
 
    // tuning gradient descent parameters
    float gd_rate = (float)0.01;        
    int gd_batch = 1000;                
    float gd_momentum = (float)0.95;    
    float gd_lambda = 0;                
    int gd_epochs = 0;                  
 
    // verbosity
    int verbosity = 0;                  
    int ids_to_print = 30;              
    int debug = 0;                      
 
    //========================================================================================================================
 
 
    int init(map<string, string>& map);
 
    // next are non serialized helpers we keep here as they are common to ALL the forest
    vector<double> log_table;
 
 
    // Serialization
    ADD_CLASS_NAME(TQRF_Params)
    ADD_SERIALIZATION_FUNCS(init_string, samples_time_unit, samples_time_unit_i, ncateg, time_slice_unit, time_slice_unit_i, time_slice_size, n_time_slices,
        time_slices, time_slices_wgts, censor_cases, max_q, tree_type, tree_type_i, ntrees, max_depth, min_node_last_slice, min_node, random_split_prob, ntry, ntry_prob,
        nsplits, max_node_test_samples, single_sample_per_pid, bag_with_repeats, bag_prob, bag_ratio, bag_feat, qpoints_per_split, nvals_for_categorial, categorial_str,
        categorial_tags, missing_val, missing_method_str, missing_method, test_for_inf, test_for_missing, only_this_categ, predict_from_slice, predict_to_slice,
        predict_sum_times, case_wgt, nrounds, min_p, max_p, alpha, wgts_pow, tuning_size, tune_max_depth, tune_min_node_size, gd_rate, gd_batch, gd_momentum,
        gd_lambda, gd_epochs, verbosity, ids_to_print, debug)
 
    //ADD_SERIALIZATION_FUNCS(init_string, samples_time_unit, time_slice_unit, time_slice_size, time_slices, max_q, max_q_sample, tree_type, ntrees, max_depth, min_node_last_slice, min_node, )
};
 
 
//==========================================================================================================================
// contains all the needed data for training including all quantizations (features, time slices) that are needed
//==========================================================================================================================
class Quantized_Feat : public SerializableObject {
 
public:
    vector<vector<short>> qx;       
    vector<vector<float>> q_to_val; 
    const MedFeatures *orig_medf;              
 
    int nfeat = 0;                  
    vector<string> feature_names;   
    int ncateg = 0;                 
    vector<const vector<float> *> orig_data; 
    vector<string> feat_names;         
    vector<float> y;
    vector<int> y_i;
    vector<int> last_time_slice;    
    int n_time_slices;              
    vector<int> slice_counts[2];    
 
    vector<vector<int>> lists;      
 
    vector<int> is_categorial_feat;
 
    // next are pre computed for bagging purposes
    vector<vector<vector<int>>> time_categ_pids;
    vector<vector<vector<int>>> time_categ_idx;
    vector<vector<int>> categ_pids;
    vector<vector<int>> categ_idx;
    unordered_map<int, vector<vector<vector<int>>>> pid2time_categ_idx;
 
    // next are helper arrays used when doind adaboost
    vector<float> wgts;
    vector<float> orig_wgts;
    vector<float> probs;
    vector<float> w_to_sum;
    vector<vector<float>> sum_over_trees;
    float alpha0;
 
    int init(const MedFeatures &medf, TQRF_Params &params);
 
    ~Quantized_Feat() {  pid2time_categ_idx.clear(); }
 
private:
    int quantize_feat(int i_feat, TQRF_Params &params);
    int init_time_slices(const MedFeatures &medf, TQRF_Params &params);
    int init_pre_bagging(TQRF_Params &params);
    int init_lists(const MedFeatures &medf, TQRF_Params &params);
 
};
 
 
//==========================================================================================================================
// a basic node class : currently a single node type serves all trees .... could be changed to 
//==========================================================================================================================
class TQRF_Node : public SerializableObject {
public:
    // Next are must for every node and are ALWAYS serialized
    int node_idx = -1;          
    int i_feat = -1;                
    float bound = (float)-1e10;     
    int is_terminal = 0;
    int left_node = -1;
    int right_node = -1;
    int depth = -1;
    int missing_direction = TQRF_MISSING_DIRECTION_RAND_EACH_SAMPLE;    
 
    // next are needed while learning , and if asked to keep samples in nodes - we keep them always for now
    int from_idx = -1;      
    int to_idx = -1;
    int size() { return to_idx-from_idx+1; }
 
    int node_serialization_mask = 0x1; 
    int beta_idx = -1;
 
    // categorical : mask |= 0x1 , time_categ_count[t][c] : how many counts in this node are in timeslice t and category c
    vector<vector<float>> time_categ_count;
 
    // regression : mask |= 0x2
    //float pred_mean = (float)-1e10;
    //float pred_std = (float)1;
 
    // quantiles: mask |= 0x4
    //vector<pair<float, float>> quantiles;
 
 
    // following are never serialized - only for learn time
    int state = TQRF_Node_State_Initiated; // 0 - created 1 - in process 2 - done with
 
    ADD_CLASS_NAME(TQRF_Node)
    ADD_SERIALIZATION_FUNCS(node_idx, i_feat, bound, is_terminal, left_node, right_node, depth, missing_direction, from_idx, to_idx,
        node_serialization_mask, beta_idx, time_categ_count, state)
};
 
//----------------------------------------------------------------------------------------------------------------------
class TQRF_Node_Categorial : TQRF_Node {
 
};
 
//==========================================================================================================================
// Split_Stat contains the quantized data structures used in order to make a split decision
// Basically : 
// for categorial outcomes:
// for each time slot, for each quanta -> counts for each category
// for regression outcomes:
// for each time slot, for each quanta -> nvals and sum (??)
//==========================================================================================================================
class TQRF_Split_Stat {
 
public:
    // categorial case
    // vector<vector<vector<int>>> counts; /// counts[t][q][c] = how many counts were in time slot t, quanta q, and category c.
 
    // suggestion (categorial case):
    // TQRF_Split will get a node with indexes, and then:
    // (1) Go over all the samples in the node and for each one add +1 to the relevant counts[t][q][c]
    // (2) Will enable going over counts and choose the best q for splitting given some params (score type, minimal size, minimal change, etc)
    //
    // This may allow a very elegant code for a tree in which all the hard stuff is implemented inside.
    // 
    // issues to think about:
    // parallelism over nodes
    // memory allocation - we want it single time
    // tricks for efficient calculation of counts and the scores
 
    virtual ~TQRF_Split_Stat() {};
 
    virtual int init(Quantized_Feat &qf, TQRF_Params &params) { return 0;};
    virtual int prep_histograms(int i_feat, TQRF_Node &node, vector<int> &indexes, Quantized_Feat &qf, TQRF_Params &params) { return 0; };
    virtual int get_best_split(TQRF_Params &params, int &best_q, double &best_score) { return 0; };
 
    int get_q_test_points(int feat_max_q, TQRF_Params &params, vector<int> &qpoints);
 
 
    // helper vector for qpoints
    vector<int> qpoints;
    
    // debug
    virtual void print_histograms() { return; };
 
    // the actual number of q values used (full or after qpoints squeeze if it was done)
    int counts_q = 0;
 
 
    static TQRF_Split_Stat *make_tqrf_split_stat(int tree_type);
};
 
//==========================================================================================================================
class TQRF_Split_Categorial : public TQRF_Split_Stat {
public:
    // categorial case : counts[t][q][c] : time_slice , quanta, category : number of elements
    vector<vector<vector<int>>> counts;
 
    // sums[t][c] = number of samples in time slice t and category c summed on all q vals
    // this is needed for a more efficient computation of scores later
    vector<vector<int>> sums;
 
    // sums_t[t] = number of samples in time slice t (needed later for more efficient calculations)
    vector<int> sums_t;
 
    int total_sum = 0; // sum of the sum_t vector
 
    ~TQRF_Split_Categorial() {};
 
    // next are for easy access
    int ncateg = 0;
    int nslices = 0;
    int maxq = 0; // overall
 
    // API's
    int init(Quantized_Feat &qf, TQRF_Params &params);
    int prep_histograms(int i_feat, TQRF_Node &node, vector<int> &indexes, Quantized_Feat &qf, TQRF_Params &params);
    //virtual int get_best_split(TQRF_Params &params, int &best_q, float &best_score);
 
    void print_histograms();
};
 
 
//==========================================================================================================================
class TQRF_Split_Likelihood : public TQRF_Split_Categorial {
public:
    int get_best_split(TQRF_Params &params, int &best_q, double &best_score);
};
 
 
//==========================================================================================================================
class TQRF_Split_Entropy : public TQRF_Split_Categorial {
public:
    int get_best_split(TQRF_Params &params, int &best_q, double &best_score);
};
 
//==========================================================================================================================
class TQRF_Split_Weighted_Categorial : public TQRF_Split_Stat {
public:
    // categorial case : counts[t][q][c] : time_slice , quanta, category : number of elements
    vector<vector<vector<float>>> counts;
 
    // sums[t][c] = number of samples in time slice t and category c summed on all q vals
    // this is needed for a more efficient computation of scores later
    vector<vector<float>> sums;
 
    // sums_t[t] = number of samples in time slice t (needed later for more efficient calculations)
    vector<float> sums_t;
 
    float total_sum = 0; // sum of the sum_t vector
 
    ~TQRF_Split_Weighted_Categorial() {};
 
    // next are for easy access
    int ncateg = 0;
    int nslices = 0;
    int maxq = 0; // overall
 
                  // API's
    int init(Quantized_Feat &qf, TQRF_Params &params);
    int prep_histograms(int i_feat, TQRF_Node &node, vector<int> &indexes, Quantized_Feat &qf, TQRF_Params &params);
    //virtual int get_best_split(TQRF_Params &params, int &best_q, float &best_score);
 
    void print_histograms();
};
 
//==========================================================================================================================
class TQRF_Split_Weighted_Likelihood : public TQRF_Split_Weighted_Categorial {
public:
    int get_best_split(TQRF_Params &params, int &best_q, double &best_score);
};
 
//==========================================================================================================================
class TQRF_Split_Dev : public TQRF_Split_Categorial {
public:
    ~TQRF_Split_Dev() {};
    int get_best_split(TQRF_Params &params, int &best_q, double &best_score) { return 0; };
};
 
//==========================================================================================================================
class TQRF_Split_Regression : public TQRF_Split_Stat {
public:
    // categorial case
    vector<vector<vector<pair<float,int>>>> sum_num;
 
    int init(Quantized_Feat &qf, TQRF_Params &params) { return 0; };
    int prep_histograms(int i_feat, TQRF_Node &node, vector<int> &indexes, Quantized_Feat &qf, TQRF_Params &params) { return 0; };
    int get_best_split(TQRF_Params &params, int &best_q, double &best_score) { return 0; };
};
 
//==========================================================================================================================
// A tree base class
//==========================================================================================================================
class TQRF_Tree : public SerializableObject {
 
public:
    // next are needed also for predictions, and hence should be serialized
    int tree_type;
    int id;                     // for debug prints - a specific tree identifier
    int keep_indexes = 0;
    vector<int> indexes;        // indexes[i] = an index of a sample in the given Quantized_Feat
    vector<TQRF_Node> nodes;    // this node supports currently all possible nodes for all trees... to save ugly templated code
 
    // next variables are no-need-to-serialize helpers
    vector<int> i_feats;        // feature indexes to be used in this tree (they can be bagged as well)
 
    TQRF_Tree() {};
 
    void init(Quantized_Feat &qfeat, TQRF_Params &params) { _qfeat = &qfeat; _params = &params; }
    int Train(Quantized_Feat &qfeat, TQRF_Params &params) { init(qfeat, params); return Train(); }
 
    const TQRF_Node *Get_Node_for_predict(MedMat<float> &x, int i_row, float missing_val, int &beta_idx) const;
    TQRF_Node *Get_Node(MedMat<float> &x, int i_row, float missing_val);
 
    int Train();
 
    // helpers inside Train:
 
    // get indexes vector ready
    int get_bagged_indexes();
 
    // initialize root node
    int init_root_node();
 
    // get the next node to work on
    int get_next_node(int curr_node);
 
    // get the list of features to work on
    int get_feats_to_test(vector<int> &feats_to_test);
 
    // init the vector for splits: to nfeat, right sizes, and right type + a free mem api
    int init_split_stats(vector<TQRF_Split_Stat *> &tqs);
    void free_split_stats(vector<TQRF_Split_Stat *> &tqs);
 
    // close work on current node and make the split if needed
    int node_splitter(int i_curr_node, int i_best, int q_best);
 
    // once a node is finalized : prepares its internal counts (with or without taking weights into account)
    float prep_node_counts(int i_curr_node, int use_wgts_flag);
 
 
    void pre_serialization() { if (keep_indexes == 0) indexes.clear(); }
    ADD_CLASS_NAME(TQRF_Tree)
    ADD_SERIALIZATION_FUNCS(tree_type, id, keep_indexes, indexes, nodes)
 
private:
    Quantized_Feat *_qfeat;
    TQRF_Params *_params;
 
    // next used to manage nodes while building
    int n_nodes_in_process = 0;
    int i_last_node_in_process = 0;
 
    int bag_chooser(float p, int _t, int _c, /* OUT APPEND */ vector<int> &_indexes);
    int bag_chooser(int choose_with_repeats, int single_sample_per_id, float p, vector<int> &pids, vector<int> &idx, unordered_map<int, vector<int>> &pid2idx, /* OUT APPEND */ vector<int> &_indexes);
 
 
};
 
 
 
//==========================================================================================================================
class TQRF_Forest : public SerializableObject {
 
public:
 
    TQRF_Params params;
    vector<TQRF_Tree> trees;
    vector<float> alphas;
    vector<float> betas;
 
    int init(map<string, string>& map) { return params.init(map); }
    int init_from_string(string init_string) { params.init_string = init_string; return SerializableObject::init_from_string(init_string); }
 
    void init_tables(Quantized_Feat &qfeat);
 
    int Train(const MedFeatures &medf, const MedMat<float> &Y);
    int Train(const MedFeatures &medf) { MedMat<float> dummy; return Train(medf, dummy); }
 
    int Train_AdaBoost(const MedFeatures &medf, const MedMat<float> &Y);
    int update_counts(vector<vector<float>> &sample_counts, MedMat<float> &x, Quantized_Feat &qf, int zero_counts, int round);
 
    int tune_betas(Quantized_Feat &qfeat);
    int solve_betas_gd(MedMat<float>& C, MedMat<float>& S, vector<float> &b);
 
    int Predict(MedMat<float> &x, vector<float> &preds) const;
    int n_preds_per_sample() const;
 
    int Predict_Categorial(MedMat<float> &x, vector<float> &preds) const; // currently like this... with time should consider inheritance to do it right.
 
    // print average bagging reports
    void print_average_bagging(int _n_time_slices, int _n_categ);
 
    // simple helpers
    static int get_tree_type(const string &str);
    static int get_missing_value_method(const string &str);
 
    ADD_CLASS_NAME(TQRF_Forest)
    ADD_SERIALIZATION_FUNCS(params, trees, alphas, betas)
 
private:
 
};
 
// helper struct
struct TreeNodeIdx {
    int i_tree = -1;
    int i_node = -1;
    TreeNodeIdx(int i_t, int i_n) { i_tree = i_t; i_node = i_n; }
};
 
 
class AllIndexes : public SerializableObject {
 
public:
 
    vector<vector<int>> all_indexes;
 
    void init_all_indexes(vector<TQRF_Tree> &trees) {
        for (auto &tree : trees)
            all_indexes.push_back(tree.indexes);
    }
 
    ADD_CLASS_NAME(AllIndexes)
    ADD_SERIALIZATION_FUNCS(all_indexes)
};
 
//========================================
// Join the serialization Waggon
//========================================
MEDSERIALIZE_SUPPORT(TQRF_Params);
MEDSERIALIZE_SUPPORT(TQRF_Node);
MEDSERIALIZE_SUPPORT(TQRF_Tree);
MEDSERIALIZE_SUPPORT(TQRF_Forest);
MEDSERIALIZE_SUPPORT(AllIndexes)
 
#endif