GBDT Class Reference

#include <GBDT.h>

Inheritance diagram for GBDT:

List of all members.

Public Member Functions
	GBDT ()
	~GBDT ()
virtual void	modelInit ()
virtual void	modelUpdate (REAL *input, REAL *target, uint nSamples, uint crossRun)
virtual void	predictAllOutputs (REAL *rawInputs, REAL *outputs, uint nSamples, uint crossRun)
virtual void	readSpecificMaps ()
virtual void	saveWeights (int cross)
virtual void	loadWeights (int cross)
virtual void	loadMetaWeights (int cross)
Static Public Member Functions
static string	templateGenerator (int id, string preEffect, int nameID, bool blendStop)
Private Member Functions
void	trainSingleTree (node *n, deque< nodeReduced > &largestNodes, REAL *input, REAL *inputTmp, REAL *inputTargetsSort, REAL *singleTarget, bool *usedFeatures, int nSamples, int *sortIndex, int *radixTmp0, REAL *radixTmp1)
void	cleanTree (node *n)
REAL	predictSingleTree (node *n, REAL *input)
void	saveTreeRecursive (node *n, fstream &f)
void	loadTreeRecursive (node *n, fstream &f)
Private Attributes
node ***	m_trees
int	m_epoch
REAL **	m_globalMean
REAL **	m_treeTargets
double **	m_validationPredictions
int	m_featureSubspaceSize
int	m_maxTreeLeafes
bool	m_useOptSplitPoint
bool	m_calculateGlobalMean
double	m_lRate

---

Detailed Description

Gradient boosted decision tree An extention to: Jerome H. Friedman 1999 "Stochastic Gradient Boosting"

The tree is build in a greedy fashion, to minimize the RMSE of the prediction Greedy means that always the largest node gets splitted

Splits can be performed optimally (in terms of RMSE) or random value (uniform sample indices) Subspace size can be selected (number of features considered in a split)

Definition at line 42 of file GBDT.h.

---

Constructor & Destructor Documentation

GBDT::GBDT

(

)

Constructor

Definition at line 20 of file GBDT.cpp.

{
    cout<<"GBDT"<<endl;
    // init member vars
    m_featureSubspaceSize = 0;
    m_maxTreeLeafes = 0;
    m_useOptSplitPoint = true;
    m_lRate = 0.0;
    m_globalMean = 0;
    m_calculateGlobalMean = true;
    m_treeTargets = 0;
}

GBDT::~GBDT

(

)

Destructor

Definition at line 36 of file GBDT.cpp.

{
    cout<<"descructor GBDT"<<endl;
}

---

Member Function Documentation

void GBDT::cleanTree

(

node *

n

)

[private]

Cleans the tree This should be done after training to remove unneccessary information

Parameters:

n

pointer too root node

Definition at line 319 of file GBDT.cpp.

{
    if ( n->m_trainSamples )
    {
        delete[] n->m_trainSamples;
        n->m_trainSamples = 0;
    }
    n->m_nSamples = 0;

    if ( n->m_toSmallerEqual )
        cleanTree ( n->m_toSmallerEqual );
    if ( n->m_toLarger )
        cleanTree ( n->m_toLarger );
}

void GBDT::loadMetaWeights

(

int

cross

)

[virtual]

nothing to do in a gradient-descent based algorithm

Implements StandardAlgorithm.

Definition at line 730 of file GBDT.cpp.

{
    // nothing to do in a gradient-descent based algorithm
}

void GBDT::loadTreeRecursive	(	node *	n,
		fstream &	f
	)			[private]

Load the tree and all nodes

Parameters:

	n	current node
	f	referece to the fstream object

Definition at line 741 of file GBDT.cpp.

{
    f.read ( ( char* ) n, sizeof ( node ) );

    if ( n->m_toSmallerEqual )
    {
        n->m_toSmallerEqual = new node;
        loadTreeRecursive ( n->m_toSmallerEqual, f );
    }
    if ( n->m_toLarger )
    {
        n->m_toLarger = new node;
        loadTreeRecursive ( n->m_toLarger, f );
    }
}

void GBDT::loadWeights

(

int

cross

)

[virtual]

Load the weights and all other parameters and make the model ready to predict

Implements StandardAlgorithm.

Definition at line 693 of file GBDT.cpp.

{
    char buf[1024];
    sprintf ( buf,"%02d",cross );
    string name = m_datasetPath + "/" + m_tempPath + "/" + m_weightFile + "." + buf;
    cout<<"Load:"<<name<<endl;
    fstream f ( name.c_str(), ios::in );
    if ( f.is_open() == false )
        assert ( false );

    // load learnrate
    f.read ( ( char* ) &m_lRate, sizeof ( double ) );

    // load number of epochs
    f.read ( ( char* ) &m_epoch, sizeof ( int ) );

    // load global means
    m_globalMean = new REAL*[m_nCross+1];
    m_globalMean[cross] = new REAL[m_nClass*m_nDomain];
    f.read ( ( char* ) m_globalMean[cross], sizeof ( REAL ) *m_nClass*m_nDomain );

    // allocate and load the trees
    m_trees = new node**[m_nCross+1];
    m_trees[cross] = new node*[m_nClass*m_nDomain];
    for ( uint i=0;i<m_nClass*m_nDomain;i++ )
    {
        m_trees[cross][i] = new node[m_epoch+1];
        for ( uint j=0;j<m_epoch+1;j++ )
            loadTreeRecursive ( & ( m_trees[cross][i][j] ), f );
    }

    f.close();
}

void GBDT::modelInit

(

)

[virtual]

Init the GBDT Model

Implements StandardAlgorithm.

Definition at line 58 of file GBDT.cpp.

{
    // add tunable parameters
    m_epoch = 0;
    paramEpochValues.push_back ( &m_epoch );
    paramEpochNames.push_back ( "epoch" );

    if ( m_featureSubspaceSize > m_nFeatures )
        m_featureSubspaceSize = m_nFeatures;

    // global mean per target and cross run
    m_globalMean = new REAL*[m_nCross+1];
    for ( int i=0;i<m_nCross+1;i++ )
    {
        m_globalMean[i] = new REAL[m_nClass*m_nDomain];
        for ( int j=0;j<m_nClass*m_nDomain;j++ )
            m_globalMean[i][j] = 0.0;
    }

    // used during training to speedup
    m_treeTargets = new REAL*[m_nCross+1];
    for ( int i=0;i<m_nCross;i++ )
        m_treeTargets[i] = new REAL[m_trainSize[i]*m_nClass*m_nDomain];
    m_treeTargets[m_nCross] = new REAL[m_trainSize[m_nCross]*m_nClass*m_nDomain];

    // allocate the trees
    m_trees = new node**[m_nCross+1];
    for ( int i=0;i<m_nCross+1;i++ )
    {
        m_trees[i] = new node*[m_nClass*m_nDomain];
        for ( uint j=0;j<m_nClass*m_nDomain;j++ )
        {
            m_trees[i][j] = new node[m_maxTuninigEpochs];
            for ( uint k=0;k<m_maxTuninigEpochs;k++ )
            {
                m_trees[i][j][k].m_featureNr = -1;
                m_trees[i][j][k].m_value = 1e10;
                m_trees[i][j][k].m_toSmallerEqual = 0;
                m_trees[i][j][k].m_toLarger = 0;
                m_trees[i][j][k].m_trainSamples = 0;
                m_trees[i][j][k].m_nSamples = -1;
            }
        }
    }
    
    // allocate mem for predictions of the probe set
    if(m_validationType == "ValidationSet")
    {
        m_validationPredictions = new double*[1];
        m_validationPredictions[0] = new double[m_nClass*m_nDomain*m_validSize];
        for(int i=0;i<m_nClass*m_nDomain*m_validSize;i++)
            m_validationPredictions[0][i] = 0.0;
    }
    else
    {
        m_validationPredictions = new double*[m_nCross];
        for(int i=0;i<m_nCross;i++)
        {
            m_validationPredictions[i] = new double[m_nClass*m_nDomain*m_probeSize[i]];
            for(int j=0;j<m_nClass*m_nDomain*m_probeSize[i];j++)
                m_validationPredictions[i][j] = 0.0;
        }
    }
    // fix randomness
    srand ( Framework::getRandomSeed() );
}

void GBDT::modelUpdate	(	REAL *	input,
		REAL *	target,
		uint	nSamples,
		uint	crossRun
	)			[virtual]

Make a model update, set the new cross validation set or set the whole training set for retraining

Parameters:

	input	Pointer to input (can be cross validation set, or whole training set) (rows x nFeatures)
	target	The targets (can be cross validation targets)
	nSamples	The sample size (rows) in input
	crossRun	The cross validation run (for training)

Implements StandardAlgorithm.

Definition at line 204 of file GBDT.cpp.

{
    REAL* singleTarget = new REAL[nSamples];
    REAL* inputTmp = new REAL[nSamples*m_featureSubspaceSize];
    REAL* inputTargetsSort = new REAL[nSamples*m_featureSubspaceSize];
    bool* usedFeatures = new bool[m_nFeatures];
    int* sortIndex = new int[nSamples];
    int* radixTmp0 = new int[nSamples];
    REAL* radixTmp1 = new REAL[nSamples];

    if ( crossRun == m_nCross && m_validationType != "ValidationSet")
        m_epoch = 0;

    uint loopEnd = 1;
    if(crossRun==m_nCross && m_validationType != "ValidationSet")
        loopEnd = m_epochParamBest[0]+1;
    
    for ( uint boostLoop=0;boostLoop < loopEnd;boostLoop++ )
    {
        time_t t0 = time ( 0 );
        if ( crossRun == m_nCross && m_validationType != "ValidationSet" )
            cout<<"epoch:"<<m_epoch<<" "<<flush;

        // train the model here
        for ( uint i=0;i<m_nClass*m_nDomain;i++ ) // for each target
        {
            // calc the global mean
            if ( m_epoch == 0 )
            {
                double sum = 0.0;
                if ( m_calculateGlobalMean )
                {
                    for ( uint j=0;j<nSamples;j++ )
                        sum += target[j*m_nClass*m_nDomain+i];
                    sum /= ( double ) nSamples;
                }
                m_globalMean[crossRun][i] = sum;
                cout<<"globalMean:"<<sum<<" "<<flush;

                for ( uint j=0;j<nSamples;j++ )
                    m_treeTargets[crossRun][i*nSamples+j] = target[j*m_nClass*m_nDomain+i] - sum;
            }

            for ( uint j=0;j<nSamples;j++ )
                singleTarget[j] = m_treeTargets[crossRun][i*nSamples+j];

            deque<nodeReduced> largestNodes;
            for ( uint j=0;j<m_nFeatures;j++ )
                usedFeatures[j] = false;

            // root node has all examples in the training list
            m_trees[crossRun][i][m_epoch].m_trainSamples = new int[nSamples];
            m_trees[crossRun][i][m_epoch].m_nSamples = nSamples;
            int* ptr = m_trees[crossRun][i][m_epoch].m_trainSamples;
            for ( uint j=0;j<nSamples;j++ )
                ptr[j] = j;

            nodeReduced firstNode;
            firstNode.m_node = & ( m_trees[crossRun][i][m_epoch] );
            firstNode.m_size = nSamples;
            largestNodes.push_back ( firstNode );
            push_heap ( largestNodes.begin(), largestNodes.end(), compareNodeReduced );

            // train the tree loop wise
            // call trainSingleTree recursive for the largest node
            for ( int j=0;j<m_maxTreeLeafes;j++ )
            {
                node* largestNode = largestNodes[0].m_node;
                trainSingleTree ( largestNode, largestNodes, input, inputTmp, inputTargetsSort, singleTarget, usedFeatures, nSamples, sortIndex, radixTmp0, radixTmp1 );
            }

            //cout<<"["<<(int)largestNodes.size()<<"|"<<flush;

            // delete the train lists per node, they are not necessary for prediction
            cleanTree ( & ( m_trees[crossRun][i][m_epoch] ) );

            // update the targets/residuals and calc train error
            double trainRMSE = 0.0;
            //fstream f("tmp/a0.txt",ios::out);
            for ( uint j=0;j<nSamples;j++ )
            {
                REAL p = predictSingleTree ( & ( m_trees[crossRun][i][m_epoch] ), input+j*m_nFeatures );
                //f<<p<<endl;
                m_treeTargets[crossRun][i*nSamples+j] -= m_lRate * p;
                double err = m_treeTargets[crossRun][i*nSamples+j];
                trainRMSE += err * err;
            }

            if ( crossRun == m_nCross )
                cout<<"tRMSE["<<i<<"]:"<<sqrt ( trainRMSE/ ( double ) nSamples ) <<" "<<flush;
            //f.close();
        }

        if ( crossRun == m_nCross && boostLoop < m_epochParamBest[0] && m_validationType != "ValidationSet")
        {
            cout<<time ( 0 )-t0<<"[s]"<<endl;
            m_epoch++;
        }
    }
    delete[] usedFeatures;
    delete[] singleTarget;
    delete[] inputTmp;
    delete[] inputTargetsSort;
    delete[] sortIndex;
    delete[] radixTmp0;
    delete[] radixTmp1;

}

void GBDT::predictAllOutputs	(	REAL *	rawInputs,
		REAL *	outputs,
		uint	nSamples,
		uint	crossRun
	)			[virtual]

Prediction for outside use, predicts outputs based on raw input values

Parameters:

	rawInputs	The input feature, without normalization (raw)
	outputs	The output value (prediction of target)
	nSamples	The input size (number of rows)
	crossRun	Number of cross validation run (in training)

Implements StandardAlgorithm.

Definition at line 133 of file GBDT.cpp.

{
    bool mode = Framework::getFrameworkMode();
    // predict all values in: REAL* outputs
    for ( uint i=0;i<nSamples;i++ )
    {
        REAL* ptr = rawInputs + i * m_nFeatures;

        // all REAL targets
        for ( uint j=0;j<m_nClass*m_nDomain;j++ )
        {
            if((crossRun >= m_nCross && m_validationType != "ValidationSet") || mode)
            {
                double sum = m_globalMean[crossRun][j];
                // for every boosting epoch : CORRECT, but slower
                for ( int k=0;k<m_epoch+1;k++ )
                {
                    REAL v = predictSingleTree ( & ( m_trees[crossRun][j][k] ), ptr );
                    sum += m_lRate * v;  // this is gradient boosting
                }
                outputs[i*m_nClass*m_nDomain + j] = sum;
            }
            else
            {
                // prediction from previous trees
                double sum = m_validationPredictions[crossRun][i*m_nClass*m_nDomain + j];
                double v = predictSingleTree ( & ( m_trees[crossRun][j][m_epoch] ), ptr );
                sum += m_lRate * v;  // this is gradient boosting
                m_validationPredictions[crossRun][i*m_nClass*m_nDomain + j] = sum;
                outputs[i*m_nClass*m_nDomain + j] = sum + (double)m_globalMean[crossRun][j];
            }
        }
    }
}

REAL GBDT::predictSingleTree	(	node *	n,
		REAL *	input
	)			[private]

Make a prediction from a tree

Parameters:

	n	The pointer to the root node
	input	input feature

Returns:

prediction value

Definition at line 175 of file GBDT.cpp.

{
    // here, on a leaf: predict the constant value
    if ( n->m_toSmallerEqual == 0 && n->m_toLarger == 0 )
        return n->m_value;

    int nr = n->m_featureNr;
    /*if(nr < 0 || nr >= m_nFeatures)
    {
        cout<<endl<<"Feature nr: "<<nr<<" (max:"<<m_nFeatures<<")"<<endl;
        assert(false);
    }*/
    REAL thresh = n->m_value;
    REAL feature = input[nr];

    if ( feature <= thresh )
        return predictSingleTree ( n->m_toSmallerEqual, input );
    return predictSingleTree ( n->m_toLarger, input );
}

void GBDT::readSpecificMaps

(

)

[virtual]

Read the Algorithm specific values from the description file

Implements StandardAlgorithm.

Definition at line 45 of file GBDT.cpp.

{
    m_featureSubspaceSize = m_intMap["featureSubspaceSize"];
    m_maxTreeLeafes = m_intMap["maxTreeLeafes"];
    m_useOptSplitPoint = m_boolMap["useOptSplitPoint"];
    m_calculateGlobalMean = m_boolMap["calculateGlobalMean"];
    m_lRate = m_doubleMap["lRate"];
}

void GBDT::saveTreeRecursive	(	node *	n,
		fstream &	f
	)			[private]

Save the tree and all nodes

Parameters:

	n	current node
	f	referece to the fstream object

Definition at line 680 of file GBDT.cpp.

{
    f.write ( ( char* ) n, sizeof ( node ) );
    if ( n->m_toSmallerEqual )
        saveTreeRecursive ( n->m_toSmallerEqual, f );
    if ( n->m_toLarger )
        saveTreeRecursive ( n->m_toLarger, f );
}

void GBDT::saveWeights

(

int

cross

)

[virtual]

Save the weights and all other parameters for load the complete prediction model

Implements StandardAlgorithm.

Definition at line 648 of file GBDT.cpp.

{
    char buf[1024];
    sprintf ( buf,"%02d",cross );
    string name = m_datasetPath + "/" + m_tempPath + "/" + m_weightFile + "." + buf;
    if ( m_inRetraining )
        cout<<"Save:"<<name<<endl;
    fstream f ( name.c_str(), ios::out );

    // save learnrate
    f.write ( ( char* ) &m_lRate, sizeof ( double ) );

    // save number of epochs
    f.write ( ( char* ) &m_epoch, sizeof ( int ) );

    // save global means
    f.write ( ( char* ) m_globalMean[cross], sizeof ( REAL ) *m_nClass*m_nDomain );

    // save trees
    for ( int i=0;i<m_nClass*m_nDomain;i++ )
        for ( int j=0;j<m_epoch+1;j++ )
            saveTreeRecursive ( & ( m_trees[cross][i][j] ), f );

    f.close();
}

string GBDT::templateGenerator	(	int	id,
		string	preEffect,
		int	nameID,
		bool	blendStop
	)			[static]

Generates a template of the description file

Returns:

The template string

Definition at line 762 of file GBDT.cpp.

{
    stringstream s;
    s<<"ALGORITHM=GBDT"<<endl;
    s<<"ID="<<id<<endl;
    s<<"TRAIN_ON_FULLPREDICTOR="<<preEffect<<endl;
    s<<"DISABLE=0"<<endl;
    s<<endl;
    s<<"[int]"<<endl;
    s<<"minTuninigEpochs=20"<<endl;
    s<<"maxTuninigEpochs=100"<<endl;
    s<<"featureSubspaceSize=10"<<endl;
    s<<"maxTreeLeafs=100"<<endl;
    s<<endl;
    s<<"[double]"<<endl;
    s<<"initMaxSwing=1.0"<<endl;
    s<<"lRate=0.1"<<endl;
    s<<endl;
    s<<"[bool]"<<endl;
    s<<"calculateGlobalMean=1"<<endl;
    s<<"useOptSplitPoint=1"<<endl;
    s<<"enableClipping=0"<<endl;
    s<<"enableTuneSwing=0"<<endl;
    s<<endl;
    s<<"minimzeProbe="<< ( !blendStop ) <<endl;
    s<<"minimzeProbeClassificationError=0"<<endl;
    s<<"minimzeBlend="<<blendStop<<endl;
    s<<"minimzeBlendClassificationError=0"<<endl;
    s<<endl;
    s<<"[string]"<<endl;
    s<<"weightFile="<<"GBDT_"<<nameID<<"_weights.dat"<<endl;
    s<<"fullPrediction=GBDT_"<<nameID<<".dat"<<endl;

    return s.str();
}

void GBDT::trainSingleTree	(	node *	n,
		deque< nodeReduced > &	largestNodes,
		REAL *	input,
		REAL *	inputTmp,
		REAL *	inputTargetsSort,
		REAL *	singleTarget,
		bool *	usedFeatures,
		int	nSamples,
		int *	sortIndex,
		int *	radixTmp0,
		REAL *	radixTmp1
	)			[private]

Train a single tree with determine split criteria etc.

Parameters:

	n	current node
	largestNodes	reference to the largest nodes deque
	input	input feature
	inputTmp	input feature array (tmp usage)
	inputTargetsSort	sorted targets (tmp usage)
	singleTarget	one target
	usedFeatures	feature mask, used for random feature subspace
	nSamples	number of samples
	sortIndex	randomized indices

Definition at line 347 of file GBDT.cpp.

{
    // break criteria: tree size limit or too less training samples
    int nS = largestNodes.size();
    if ( nS >= m_maxTreeLeafes || n->m_nSamples <= 1 )
        return;

    // delete the current node (is currently the largest element in the heap)
    if ( largestNodes.size() > 0 )
    {
        //largestNodes.pop_front();
        pop_heap ( largestNodes.begin(),largestNodes.end(),compareNodeReduced );
        largestNodes.pop_back();
    }

    // the number of training samples in this node
    int nNodeSamples = n->m_nSamples;

    // this tmp array is used to fast drawing a random subset
    int *randFeatureIDs = new int[m_featureSubspaceSize];
    if ( m_featureSubspaceSize < m_nFeatures ) // select a random feature subset
    {
        for ( uint i=0;i<m_featureSubspaceSize;i++ )
        {
            uint idx = rand() % m_nFeatures;
            while ( usedFeatures[idx] )
                idx = rand() % m_nFeatures;
            randFeatureIDs[i] = idx;
            usedFeatures[idx] = true;
        }
    }
    else  // take all features
        for ( uint i=0;i<m_featureSubspaceSize;i++ )
            randFeatureIDs[i] = i;

    // precalc sums and squared sums of targets
    double sumTarget = 0.0, sum2Target = 0.0;
    for ( uint j=0;j<nNodeSamples;j++ )
    {
        REAL v = singleTarget[n->m_trainSamples[j]];
        sumTarget += v;
        sum2Target += v*v;
    }

    int bestFeature = -1, bestFeaturePos = -1;
    double bestFeatureRMSE = 1e10;
    REAL bestFeatureLow = 1e10, bestFeatureHi = 1e10;
    REAL optFeatureSplitValue = 1e10;

    // search optimal split point in all tmp input features
    for ( int i=0;i<m_featureSubspaceSize;i++ )
    {
        // search the optimal split value, which reduce the RMSE the most
        REAL optimalSplitValue = 0.0;
        double rmseBest = 1e10;
        REAL meanLowBest = 1e10, meanHiBest = 1e10;
        int bestPos = -1;
        double sumLow = 0.0, sum2Low = 0.0, sumHi = sumTarget, sum2Hi = sum2Target, cntLow = 0.0, cntHi = nNodeSamples;
        REAL* ptrInput = inputTmp + i * nNodeSamples;
        REAL* ptrTarget = inputTargetsSort + i * nNodeSamples;

        // copy
        int nr = randFeatureIDs[i];
        for ( int j=0;j<nNodeSamples;j++ )
            ptrInput[j] = input[nr+n->m_trainSamples[j]*m_nFeatures];

        if ( m_useOptSplitPoint == false ) // random threshold value
        {
            for ( int j=0;j<nNodeSamples;j++ )
                ptrTarget[j] = singleTarget[n->m_trainSamples[j]];

            REAL* ptrInput = inputTmp + i * nNodeSamples;
            bestPos = rand() % nNodeSamples;
            optimalSplitValue = ptrInput[bestPos];
            sumLow = 0.0;
            sum2Low = 0.0;
            cntLow = 0.0;
            sumHi = 0.0;
            sum2Hi = 0.0;
            cntHi = 0.0;
            for ( int j=0;j<nNodeSamples;j++ )
            {
                REAL v = ptrInput[j];
                REAL t = ptrTarget[j];
                if ( ptrInput[j] <= optimalSplitValue )
                {
                    sumLow += t;
                    sum2Low += t*t;
                    cntLow += 1.0;
                }
                else
                {
                    sumHi += t;
                    sum2Hi += t*t;
                    cntHi += 1.0;
                }
            }
            rmseBest = ( sum2Low/cntLow - ( sumLow/cntLow ) * ( sumLow/cntLow ) ) *cntLow;
            rmseBest += ( sum2Hi/cntHi - ( sumHi/cntHi ) * ( sumHi/cntHi ) ) *cntHi;
            rmseBest = sqrt ( rmseBest/ ( cntLow+cntHi ) );
            meanLowBest = sumLow/cntLow;
            meanHiBest = sumHi/cntHi;
        }
        else  // search for the optimal threshold value, goal: best RMSE reduction split
        {
            // fast sort of the input dimension
            for ( int j=0;j<nNodeSamples;j++ )
                sortIndex[j] = j;
            
            //SORT_ASCEND_I ( ptrInput, sortIndex, nNodeSamples );
            //for ( int j=0;j<nNodeSamples;j++ )
            //    ptrTarget[j] = singleTarget[n->m_trainSamples[sortIndex[j]]];
            
            /*vector<pair<REAL,int> > list(nNodeSamples);
            for(int j=0;j<nNodeSamples;j++)
            {
                list[j].first = ptrInput[j];
                list[j].second = sortIndex[j];
            }
            sort(list.begin(),list.end());
            for(int j=0;j<nNodeSamples;j++)
            {
                ptrInput[j] = list[j].first;
                sortIndex[j] = list[j].second;
            }
            for ( int j=0;j<nNodeSamples;j++ )
                ptrTarget[j] = singleTarget[n->m_trainSamples[sortIndex[j]]];
            */
            
            SORT_ASCEND_RADIX_I ( ptrInput, sizeof(REAL), sortIndex, radixTmp0, nNodeSamples);
            for(int j=0;j<nNodeSamples;j++)
                radixTmp1[j] = ptrInput[j];
            for(int j=0;j<nNodeSamples;j++)
            {
                int idx = sortIndex[j];
                ptrInput[j] = radixTmp1[idx];
                ptrTarget[j] = singleTarget[n->m_trainSamples[idx]];
            }
            
            int j = 0;
            while ( j < nNodeSamples-1 )
            {
                REAL t = ptrTarget[j];
                sumLow += t;
                sum2Low += t*t;
                sumHi -= t;
                sum2Hi -= t*t;
                cntLow += 1.0;
                cntHi -= 1.0;

                REAL v0 = ptrInput[j], v1 = 1e10;
                if ( j < nNodeSamples -1 )
                    v1 = ptrInput[j+1];
                if ( v0 == v1 ) // skip equal successors
                {
                    j++;
                    continue;
                }

                double rmse = ( sum2Low/cntLow - ( sumLow/cntLow ) * ( sumLow/cntLow ) ) *cntLow;
                rmse += ( sum2Hi/cntHi   - ( sumHi/cntHi ) * ( sumHi/cntHi ) ) *cntHi;
                rmse = sqrt ( rmse/ ( cntLow+cntHi ) );

                if ( rmse < rmseBest )
                {
                    optimalSplitValue = v0;
                    rmseBest = rmse;
                    bestPos = j+1;
                    meanLowBest = sumLow/cntLow;
                    meanHiBest = sumHi/cntHi;
                }

                j++;
            }
        }

        if ( rmseBest < bestFeatureRMSE )
        {
            bestFeature = i;
            bestFeaturePos = bestPos;
            bestFeatureRMSE = rmseBest;
            optFeatureSplitValue = optimalSplitValue;
            bestFeatureLow = meanLowBest;
            bestFeatureHi = meanHiBest;
        }
    }

    // unmark the selected inputs
    for ( uint i=0;i<m_nFeatures;i++ )
        usedFeatures[i] = false;

    n->m_featureNr = randFeatureIDs[bestFeature];
    n->m_value = optFeatureSplitValue;

    delete[] randFeatureIDs;

    if ( n->m_featureNr < 0 || n->m_featureNr >= m_nFeatures )
    {
        cout<<"f="<<n->m_featureNr<<endl;
        assert ( false );
    }

    // count the samples of the low node
    int cnt = 0;
    for ( int i=0;i<nNodeSamples;i++ )
    {
        int nr = n->m_featureNr;
        if ( input[nr + n->m_trainSamples[i]*m_nFeatures] <= optFeatureSplitValue )
            cnt++;
    }

    int* lowList = new int[cnt];
    int* hiList = new int[nNodeSamples-cnt];
    if ( cnt == 0 )
        lowList = 0;
    if ( nNodeSamples-cnt == 0 )
        hiList = 0;

    int lowCnt = 0, hiCnt = 0;
    double lowMean = 0.0, hiMean = 0.0;
    for ( int i=0;i<nNodeSamples;i++ )
    {
        int nr = n->m_featureNr;
        if ( input[nr + n->m_trainSamples[i]*m_nFeatures] <= optFeatureSplitValue )
        {
            lowList[lowCnt] = n->m_trainSamples[i];
            lowMean += singleTarget[n->m_trainSamples[i]];
            lowCnt++;
        }
        else
        {
            hiList[hiCnt] = n->m_trainSamples[i];
            hiMean += singleTarget[n->m_trainSamples[i]];
            hiCnt++;
        }
    }
    lowMean /= lowCnt;
    hiMean /= hiCnt;

    if ( hiCnt+lowCnt != nNodeSamples || lowCnt != cnt )
        assert ( false );

    //cout<<"  #low:"<<lowCnt<<"  #hi:"<<hiCnt<<"  lowMean:"<<lowMean<<"  highMean:"<<hiMean<<endl;

    // break, if too less samples
    if ( lowCnt < 1 || hiCnt < 1 )
    {
        n->m_featureNr = -1;
        n->m_value = lowCnt < 1 ? hiMean : lowMean;
        n->m_toSmallerEqual = 0;
        n->m_toLarger = 0;
        if ( n->m_trainSamples )
            delete[] n->m_trainSamples;
        n->m_trainSamples = 0;
        n->m_nSamples = 0;

        nodeReduced currentNode;
        currentNode.m_node = n;
        currentNode.m_size = 0;
        largestNodes.push_back ( currentNode );
        push_heap ( largestNodes.begin(), largestNodes.end(), compareNodeReduced );

        return;
    }

    // prepare first new node
    n->m_toSmallerEqual = new node;
    n->m_toSmallerEqual->m_featureNr = -1;
    n->m_toSmallerEqual->m_value = lowMean;
    n->m_toSmallerEqual->m_toSmallerEqual = 0;
    n->m_toSmallerEqual->m_toLarger = 0;
    n->m_toSmallerEqual->m_trainSamples = lowList;
    n->m_toSmallerEqual->m_nSamples = lowCnt;

    // prepare second new node
    n->m_toLarger = new node;
    n->m_toLarger->m_featureNr = -1;
    n->m_toLarger->m_value = hiMean;
    n->m_toLarger->m_toSmallerEqual = 0;
    n->m_toLarger->m_toLarger = 0;
    n->m_toLarger->m_trainSamples = hiList;
    n->m_toLarger->m_nSamples = hiCnt;

    // add the new two nodes to the heap
    nodeReduced lowNode, hiNode;
    lowNode.m_node = n->m_toSmallerEqual;
    lowNode.m_size = lowCnt;
    hiNode.m_node = n->m_toLarger;
    hiNode.m_size = hiCnt;

    largestNodes.push_back ( lowNode );
    push_heap ( largestNodes.begin(), largestNodes.end(), compareNodeReduced );

    largestNodes.push_back ( hiNode );
    push_heap ( largestNodes.begin(), largestNodes.end(), compareNodeReduced );
}

---

The documentation for this class was generated from the following files:

• ELF/GBDT.h
• ELF/GBDT.cpp