src/tree/updater_quantile_hist.cc
// enumerate the split values of specific feature
// d_step: +1 or -1, indicating direction at which we scan candidate thresholds in order
// fid: feature for which we seek to pick best threshold
// Returns false if we don't need to enumerate in opposite direction.
//   This is the case if the particular feature (fid) column contains no missing values.
enumerate the split values of specific feature
d_step: +1 or -1, indicating direction at which we scan candidate thresholds in order
fid: feature for which we seek to pick best threshold
Returns false if we don't need to enumerate in opposite direction.
This is the case if the particular feature (fid) column contains no missing values.
enumerate the split values of specific feature d_step : + 1 or - 1 indicating direction at which we scan candidate thresholds in order fid : feature for which we seek to pick best threshold Returns false if we don ' t need to enumerate in opposite direction . This is the case if the particular feature ( fid ) column contains no missing values .
bool QuantileHistMaker::Builder::EnumerateSplit(int d_step,
                                                const GHistIndexMatrix& gmat,
                                                const GHistRow& hist,
                                                const NodeEntry& snode,
                                                const MetaInfo& info,
                                                SplitEntry* p_best,
                                                bst_uint fid,
                                                bst_uint nodeID) {
  CHECK(d_step == +1 || d_step == -1);
  const std::vector<uint32_t>& cut_ptr = gmat.cut.Ptrs();
  const std::vector<bst_float>& cut_val = gmat.cut.Values();
  GradStats c;
  GradStats e;
  SplitEntry best;
  CHECK_LE(cut_ptr[fid],
           static_cast<uint32_t>(std::numeric_limits<int32_t>::max()));
  CHECK_LE(cut_ptr[fid + 1],
           static_cast<uint32_t>(std::numeric_limits<int32_t>::max()));
  const auto imin = static_cast<int32_t>(cut_ptr[fid]);
  int32_t ibegin, iend;
  if (d_step > 0) {
    ibegin = static_cast<int32_t>(cut_ptr[fid]);
    iend = static_cast<int32_t>(cut_ptr[fid + 1]);
  } else {
    ibegin = static_cast<int32_t>(cut_ptr[fid + 1]) - 1;
    iend = static_cast<int32_t>(cut_ptr[fid]) - 1;
  }
  if (d_step == 1) {
    for (int32_t i = ibegin; i < iend; i++) {
      e.Add(hist[i].GetGrad(), hist[i].GetHess());
      if (e.sum_hess >= param_.min_child_weight) {
        c.SetSubstract(snode.stats, e);
        if (c.sum_hess >= param_.min_child_weight) {
          bst_float loss_chg = static_cast<bst_float>(spliteval_->ComputeSplitScore(nodeID,
              fid, e, c) - snode.root_gain);
          bst_float split_pt = cut_val[i];
           best.Update(loss_chg, fid, split_pt, false, e, c);
        }
      }
    }
    p_best->Update(best);
    if (e.GetGrad() == snode.stats.GetGrad() && e.GetHess() == snode.stats.GetHess()) {
      return false;
    }
  } else {
    for (int32_t i = ibegin; i != iend; i--) {
      e.Add(hist[i].GetGrad(), hist[i].GetHess());
      if (e.sum_hess >= param_.min_child_weight) {
        c.SetSubstract(snode.stats, e);
        if (c.sum_hess >= param_.min_child_weight) {
          bst_float split_pt;
          bst_float loss_chg = static_cast<bst_float>(
              spliteval_->ComputeSplitScore(nodeID, fid, c, e) -
              snode.root_gain);
          if (i == imin) {
            split_pt = gmat.cut.MinValues()[fid];
          } else {
            split_pt = cut_val[i - 1];
          }
          best.Update(loss_chg, fid, split_pt, true, c, e);
        }
      }
    }
    p_best->Update(best);
    if (e.GetGrad() == snode.stats.GetGrad() && e.GetHess() == snode.stats.GetHess()) {
      return false;
    }
  }
  return true;
}
bool QuantileHistMaker :: Builder :: EnumerateSplit ( int d_step , const GHistIndexMatrix & gmat , const GHistRow & hist , const NodeEntry & snode , const MetaInfo & info , SplitEntry * p_best , bst_uint fid , bst_uint nodeID ) { CHECK ( d_step == +1 || d_step == -1 ) ; const std :: vector < uint32_t > & cut_ptr = gmat . cut . Ptrs ( ) ; const std :: vector < bst_float > & cut_val = gmat . cut . Values ( ) ; GradStats c ; GradStats e ; SplitEntry best ; CHECK_LE ( cut_ptr [ fid ] , static_cast < uint32_t > ( std :: numeric_limits < int32_t > :: max ( ) ) ) ; CHECK_LE ( cut_ptr [ fid + 1 ] , static_cast < uint32_t > ( std :: numeric_limits < int32_t > :: max ( ) ) ) ; const auto imin = static_cast < int32_t > ( cut_ptr [ fid ] ) ; int32_t ibegin , iend ; if ( d_step > 0 ) { ibegin = static_cast < int32_t > ( cut_ptr [ fid ] ) ; iend = static_cast < int32_t > ( cut_ptr [ fid + 1 ] ) ; } else { ibegin = static_cast < int32_t > ( cut_ptr [ fid + 1 ] ) - 1 ; iend = static_cast < int32_t > ( cut_ptr [ fid ] ) - 1 ; } if ( d_step == 1 ) { for ( int32_t i = ibegin ; i < iend ; i ++ ) { e . Add ( hist [ i ] . GetGrad ( ) , hist [ i ] . GetHess ( ) ) ; if ( e . sum_hess >= param_ . min_child_weight ) { c . SetSubstract ( snode . stats , e ) ; if ( c . sum_hess >= param_ . min_child_weight ) { bst_float loss_chg = static_cast < bst_float > ( spliteval_ -> ComputeSplitScore ( nodeID , fid , e , c ) - snode . root_gain ) ; bst_float split_pt = cut_val [ i ] ; best . Update ( loss_chg , fid , split_pt , false , e , c ) ; } } } p_best -> Update ( best ) ; if ( e . GetGrad ( ) == snode . stats . GetGrad ( ) && e . GetHess ( ) == snode . stats . GetHess ( ) ) { return false ; } } else { for ( int32_t i = ibegin ; i != iend ; i -- ) { e . Add ( hist [ i ] . GetGrad ( ) , hist [ i ] . GetHess ( ) ) ; if ( e . sum_hess >= param_ . min_child_weight ) { c . SetSubstract ( snode . stats , e ) ; if ( c . sum_hess >= param_ . min_child_weight ) { bst_float split_pt ; bst_float loss_chg = static_cast < bst_float > ( spliteval_ -> ComputeSplitScore ( nodeID , fid , c , e ) - snode . root_gain ) ; if ( i == imin ) { split_pt = gmat . cut . MinValues ( ) [ fid ] ; } else { split_pt = cut_val [ i - 1 ] ; } best . Update ( loss_chg , fid , split_pt , true , c , e ) ; } } } p_best -> Update ( best ) ; if ( e . GetGrad ( ) == snode . stats . GetGrad ( ) && e . GetHess ( ) == snode . stats . GetHess ( ) ) { return false ; } } return true ; }
enumerate the split values of specific feature
d_step: +1 or -1, indicating direction at which we scan candidate thresholds in order
fid: feature for which we seek to pick best threshold
Returns false if we don't need to enumerate in opposite direction.
enumerate the split values of specific feature d_step : + 1 or - 1 indicating direction at which we scan candidate thresholds in order fid : feature for which we seek to pick best threshold Returns false if we don ' t need to enumerate in opposite direction .
// aliases // statistics on both sides of split // best split so far // bin boundaries // imin: index (offset) of the minimum value for feature fid //       need this for backward enumeration // ibegin, iend: smallest/largest cut points for feature fid // use int to allow for value -1 // backward enumeration: split at left bound of each bin // for leftmost bin, left bound is the smallest feature value