random.h

Go to the documentation of this file.

 
#ifndef XGBOOST_COMMON_RANDOM_H_
#define XGBOOST_COMMON_RANDOM_H_
 
#include <rabit/rabit.h>
#include <xgboost/logging.h>
#include <algorithm>
#include <functional>
#include <vector>
#include <limits>
#include <map>
#include <memory>
#include <numeric>
#include <random>
#include <utility>
 
#include "xgboost/host_device_vector.h"
#include "common.h"
 
namespace xgboost {
namespace common {
using RandomEngine = std::mt19937;
 
#if XGBOOST_CUSTOMIZE_GLOBAL_PRNG
 
class CustomGlobalRandomEngine {
 public:
  using result_type = uint32_t;
  inline static constexpr result_type min() {
    return 0;
  }
  inline static constexpr result_type max() {
    return std::numeric_limits<result_type>::max();
  }
  void seed(result_type val);
  result_type operator()();
};
 
typedef CustomGlobalRandomEngine GlobalRandomEngine;
 
#else
 
using GlobalRandomEngine = RandomEngine;
#endif  // XGBOOST_CUSTOMIZE_GLOBAL_PRNG
 
GlobalRandomEngine& GlobalRandom(); // NOLINT(*)
 
/*
 * Original paper:
 * Weighted Random Sampling (2005; Efraimidis, Spirakis)
 *
 * Blog:
 * https://timvieira.github.io/blog/post/2019/09/16/algorithms-for-sampling-without-replacement/
*/
template <typename T>
std::vector<T> WeightedSamplingWithoutReplacement(
    std::vector<T> const &array, std::vector<float> const &weights, size_t n) {
  // ES sampling.
  CHECK_EQ(array.size(), weights.size());
  std::vector<float> keys(weights.size());
  std::uniform_real_distribution<float> dist;
  auto& rng = GlobalRandom();
  for (size_t i = 0; i < array.size(); ++i) {
    auto w = std::max(weights.at(i), kRtEps);
    auto u = dist(rng);
    auto k = std::log(u) / w;
    keys[i] = k;
  }
  auto ind = ArgSort<size_t>(Span<float>{keys}, std::greater<>{});
  ind.resize(n);
 
  std::vector<T> results(ind.size());
  for (size_t k = 0; k < ind.size(); ++k) {
    auto idx = ind[k];
    results[k] = array[idx];
  }
  return results;
}
 
class ColumnSampler {
  std::shared_ptr<HostDeviceVector<bst_feature_t>> feature_set_tree_;
  std::map<int, std::shared_ptr<HostDeviceVector<bst_feature_t>>> feature_set_level_;
  std::vector<float> feature_weights_;
  float colsample_bylevel_{1.0f};
  float colsample_bytree_{1.0f};
  float colsample_bynode_{1.0f};
  GlobalRandomEngine rng_;
 
 public:
  std::shared_ptr<HostDeviceVector<bst_feature_t>> ColSample(
      std::shared_ptr<HostDeviceVector<bst_feature_t>> p_features, float colsample);
  explicit ColumnSampler(uint32_t seed) {
    rng_.seed(seed);
  }
 
  ColumnSampler() {
    uint32_t seed = common::GlobalRandom()();
    rabit::Broadcast(&seed, sizeof(seed), 0);
    rng_.seed(seed);
  }
 
  void Init(int64_t num_col, std::vector<float> feature_weights, float colsample_bynode,
            float colsample_bylevel, float colsample_bytree) {
    feature_weights_ = std::move(feature_weights);
    colsample_bylevel_ = colsample_bylevel;
    colsample_bytree_ = colsample_bytree;
    colsample_bynode_ = colsample_bynode;
 
    if (feature_set_tree_ == nullptr) {
      feature_set_tree_ = std::make_shared<HostDeviceVector<bst_feature_t>>();
    }
    Reset();
 
    feature_set_tree_->Resize(num_col);
    std::iota(feature_set_tree_->HostVector().begin(), feature_set_tree_->HostVector().end(), 0);
 
    feature_set_tree_ = ColSample(feature_set_tree_, colsample_bytree_);
  }
 
  void Reset() {
    feature_set_tree_->Resize(0);
    feature_set_level_.clear();
  }
 
  std::shared_ptr<HostDeviceVector<bst_feature_t>> GetFeatureSet(int depth) {
    if (colsample_bylevel_ == 1.0f && colsample_bynode_ == 1.0f) {
      return feature_set_tree_;
    }
 
    if (feature_set_level_.count(depth) == 0) {
      // Level sampling, level does not yet exist so generate it
      feature_set_level_[depth] = ColSample(feature_set_tree_, colsample_bylevel_);
    }
    if (colsample_bynode_ == 1.0f) {
      // Level sampling
      return feature_set_level_[depth];
    }
    // Need to sample for the node individually
    return ColSample(feature_set_level_[depth], colsample_bynode_);
  }
};
 
}  // namespace common
}  // namespace xgboost
#endif  // XGBOOST_COMMON_RANDOM_H_