leaf_splits.hpp 4.95 KB
Newer Older
1
2
3
4
/*!
 * Copyright (c) 2016 Microsoft Corporation. All rights reserved.
 * Licensed under the MIT License. See LICENSE file in the project root for license information.
 */
Guolin Ke's avatar
Guolin Ke committed
5
6
7
#ifndef LIGHTGBM_TREELEARNER_LEAF_SPLITS_HPP_
#define LIGHTGBM_TREELEARNER_LEAF_SPLITS_HPP_

Guolin Ke's avatar
Guolin Ke committed
8
#include <LightGBM/config.h>
9
#include <LightGBM/meta.h>
10
#include <LightGBM/utils/threading.h>
11

12
#include <limits>
Guolin Ke's avatar
Guolin Ke committed
13
14
#include <vector>

15
16
#include "data_partition.hpp"

Guolin Ke's avatar
Guolin Ke committed
17
18
19
namespace LightGBM {

/*!
Qiwei Ye's avatar
Qiwei Ye committed
20
* \brief used to find split candidates for a leaf
Guolin Ke's avatar
Guolin Ke committed
21
22
*/
class LeafSplits {
Nikita Titov's avatar
Nikita Titov committed
23
 public:
Guolin Ke's avatar
Guolin Ke committed
24
25
  LeafSplits(data_size_t num_data, const Config* config)
    :config_(config), num_data_in_leaf_(num_data), num_data_(num_data),
Belinda Trotta's avatar
Belinda Trotta committed
26
    data_indices_(nullptr), weight_(0) {
Guolin Ke's avatar
Guolin Ke committed
27
  }
Guolin Ke's avatar
Guolin Ke committed
28
29
30
31
  void ResetNumData(data_size_t num_data) {
    num_data_ = num_data;
    num_data_in_leaf_ = num_data;
  }
Guolin Ke's avatar
Guolin Ke committed
32
33
34
35
  ~LeafSplits() {
  }

  /*!
Qiwei Ye's avatar
Qiwei Ye committed
36
  * \brief Init split on current leaf on partial data. 
Guolin Ke's avatar
Guolin Ke committed
37
38
39
40
41
  * \param leaf Index of current leaf
  * \param data_partition current data partition
  * \param sum_gradients
  * \param sum_hessians
  */
Belinda Trotta's avatar
Belinda Trotta committed
42
43
  void Init(int leaf, const DataPartition* data_partition, double sum_gradients,
            double sum_hessians, double weight) {
Guolin Ke's avatar
Guolin Ke committed
44
    leaf_index_ = leaf;
Guolin Ke's avatar
Guolin Ke committed
45
    data_indices_ = data_partition->GetIndexOnLeaf(leaf, &num_data_in_leaf_);
Guolin Ke's avatar
Guolin Ke committed
46
47
    sum_gradients_ = sum_gradients;
    sum_hessians_ = sum_hessians;
Belinda Trotta's avatar
Belinda Trotta committed
48
    weight_ = weight;
49
50
51
52
53
54
55
56
57
58
59
60
  }

  /*!
  * \brief Init split on current leaf on partial data.
  * \param leaf Index of current leaf
  * \param sum_gradients
  * \param sum_hessians
  */
  void Init(int leaf, double sum_gradients, double sum_hessians) {
    leaf_index_ = leaf;
    sum_gradients_ = sum_gradients;
    sum_hessians_ = sum_hessians;
Guolin Ke's avatar
Guolin Ke committed
61
62
  }

Guolin Ke's avatar
Guolin Ke committed
63
  /*!
64
65
66
67
   * \brief Init splits on the current leaf, it will traverse all data to sum up the results
   * \param gradients
   * \param hessians
   */
68
  void Init(const score_t* gradients, const score_t* hessians) {
Guolin Ke's avatar
Guolin Ke committed
69
70
71
    num_data_in_leaf_ = num_data_;
    leaf_index_ = 0;
    data_indices_ = nullptr;
Guolin Ke's avatar
Guolin Ke committed
72
73
    double tmp_sum_gradients = 0.0f;
    double tmp_sum_hessians = 0.0f;
Guolin Ke's avatar
Guolin Ke committed
74
#pragma omp parallel for schedule(static, 512) reduction(+:tmp_sum_gradients, tmp_sum_hessians) if (num_data_in_leaf_ >= 1024 && !config_->deterministic)
Guolin Ke's avatar
Guolin Ke committed
75
76
77
    for (data_size_t i = 0; i < num_data_in_leaf_; ++i) {
      tmp_sum_gradients += gradients[i];
      tmp_sum_hessians += hessians[i];
78
    }
Guolin Ke's avatar
Guolin Ke committed
79
80
    sum_gradients_ = tmp_sum_gradients;
    sum_hessians_ = tmp_sum_hessians;
Guolin Ke's avatar
Guolin Ke committed
81
82
83
  }

  /*!
84
85
86
87
88
89
90
91
   * \brief Init splits on current leaf of partial data.
   * \param leaf Index of current leaf
   * \param data_partition current data partition
   * \param gradients
   * \param hessians
   */
  void Init(int leaf, const DataPartition* data_partition,
            const score_t* gradients, const score_t* hessians) {
Guolin Ke's avatar
Guolin Ke committed
92
    leaf_index_ = leaf;
Guolin Ke's avatar
Guolin Ke committed
93
    data_indices_ = data_partition->GetIndexOnLeaf(leaf, &num_data_in_leaf_);
Guolin Ke's avatar
Guolin Ke committed
94
95
    double tmp_sum_gradients = 0.0f;
    double tmp_sum_hessians = 0.0f;
Guolin Ke's avatar
Guolin Ke committed
96
#pragma omp parallel for schedule(static, 512) reduction(+:tmp_sum_gradients, tmp_sum_hessians) if (num_data_in_leaf_ >= 1024 && !config_->deterministic)
Guolin Ke's avatar
Guolin Ke committed
97
98
99
100
    for (data_size_t i = 0; i < num_data_in_leaf_; ++i) {
      const data_size_t idx = data_indices_[i];
      tmp_sum_gradients += gradients[idx];
      tmp_sum_hessians += hessians[idx];
101
    }
Guolin Ke's avatar
Guolin Ke committed
102
103
    sum_gradients_ = tmp_sum_gradients;
    sum_hessians_ = tmp_sum_hessians;
Guolin Ke's avatar
Guolin Ke committed
104
105
106
107
108
109
110
111
  }


  /*!
  * \brief Init splits on current leaf, only update sum_gradients and sum_hessians
  * \param sum_gradients
  * \param sum_hessians
  */
Guolin Ke's avatar
Guolin Ke committed
112
  void Init(double sum_gradients, double sum_hessians) {
Guolin Ke's avatar
Guolin Ke committed
113
114
115
116
117
118
119
120
121
122
    leaf_index_ = 0;
    sum_gradients_ = sum_gradients;
    sum_hessians_ = sum_hessians;
  }

  /*!
  * \brief Init splits on current leaf
  */
  void Init() {
    leaf_index_ = -1;
Guolin Ke's avatar
Guolin Ke committed
123
124
    data_indices_ = nullptr;
    num_data_in_leaf_ = 0;
Guolin Ke's avatar
Guolin Ke committed
125
126
127
128
  }


  /*! \brief Get current leaf index */
129
  int leaf_index() const { return leaf_index_; }
Guolin Ke's avatar
Guolin Ke committed
130
131
132
133
134

  /*! \brief Get numer of data in current leaf */
  data_size_t num_data_in_leaf() const { return num_data_in_leaf_; }

  /*! \brief Get sum of gradients of current leaf */
Guolin Ke's avatar
Guolin Ke committed
135
  double sum_gradients() const { return sum_gradients_; }
136

Guolin Ke's avatar
Guolin Ke committed
137
  /*! \brief Get sum of hessians of current leaf */
Guolin Ke's avatar
Guolin Ke committed
138
  double sum_hessians() const { return sum_hessians_; }
Guolin Ke's avatar
Guolin Ke committed
139
140

  /*! \brief Get indices of data of current leaf */
Guolin Ke's avatar
Guolin Ke committed
141
  const data_size_t* data_indices() const { return data_indices_; }
Guolin Ke's avatar
Guolin Ke committed
142

Belinda Trotta's avatar
Belinda Trotta committed
143
144
145
146
  /*! \brief Get weight of current leaf */
  double weight() const { return weight_; }


Guolin Ke's avatar
Guolin Ke committed
147

Nikita Titov's avatar
Nikita Titov committed
148
 private:
Guolin Ke's avatar
Guolin Ke committed
149
  const Config* config_;
Guolin Ke's avatar
Guolin Ke committed
150
151
152
153
154
155
156
  /*! \brief current leaf index */
  int leaf_index_;
  /*! \brief number of data on current leaf */
  data_size_t num_data_in_leaf_;
  /*! \brief number of all training data */
  data_size_t num_data_;
  /*! \brief sum of gradients of current leaf */
Guolin Ke's avatar
Guolin Ke committed
157
  double sum_gradients_;
Guolin Ke's avatar
Guolin Ke committed
158
  /*! \brief sum of hessians of current leaf */
Guolin Ke's avatar
Guolin Ke committed
159
  double sum_hessians_;
Guolin Ke's avatar
Guolin Ke committed
160
  /*! \brief indices of data of current leaf */
Guolin Ke's avatar
Guolin Ke committed
161
  const data_size_t* data_indices_;
Belinda Trotta's avatar
Belinda Trotta committed
162
163
  /*! \brief weight of current leaf */
  double weight_;
Guolin Ke's avatar
Guolin Ke committed
164
165
166
};

}  // namespace LightGBM
Guolin Ke's avatar
Guolin Ke committed
167
#endif   // LightGBM_TREELEARNER_LEAF_SPLITS_HPP_