xgboost

tree_model.h
Go to the documentation of this file.
1
7 #ifndef XGBOOST_TREE_MODEL_H_
8 #define XGBOOST_TREE_MODEL_H_
9
10 #include <dmlc/io.h>
11 #include <dmlc/parameter.h>
12
13 #include <xgboost/base.h>
14 #include <xgboost/data.h>
15 #include <xgboost/logging.h>
16 #include <xgboost/feature_map.h>
17 #include <xgboost/model.h>
18
19 #include <limits>
20 #include <vector>
21 #include <string>
22 #include <cstring>
23 #include <algorithm>
24 #include <tuple>
25 #include <stack>
26
27 namespace xgboost {
28
29 struct PathElement; // forward declaration
30
31 class Json;
32 // FIXME(trivialfis): Once binary IO is gone, make this parameter internal as it should
33 // not be configured by users.
35 struct TreeParam : public dmlc::Parameter<TreeParam> {
37 int deprecated_num_roots;
39 int num_nodes;
41 int num_deleted;
43 int deprecated_max_depth;
45 int num_feature;
50 int size_leaf_vector;
52 int reserved[31];
54 TreeParam() {
55 // assert compact alignment
56 static_assert(sizeof(TreeParam) == (31 + 6) * sizeof(int),
57 "TreeParam: 64 bit align");
58 std::memset(this, 0, sizeof(TreeParam));
59 num_nodes = 1;
60 deprecated_num_roots = 1;
61 }
62
63 // Swap byte order for all fields. Useful for transporting models between machines with different
64 // endianness (big endian vs little endian)
65 inline TreeParam ByteSwap() const {
66 TreeParam x = *this;
67 dmlc::ByteSwap(&x.deprecated_num_roots, sizeof(x.deprecated_num_roots), 1);
68 dmlc::ByteSwap(&x.num_nodes, sizeof(x.num_nodes), 1);
69 dmlc::ByteSwap(&x.num_deleted, sizeof(x.num_deleted), 1);
70 dmlc::ByteSwap(&x.deprecated_max_depth, sizeof(x.deprecated_max_depth), 1);
71 dmlc::ByteSwap(&x.num_feature, sizeof(x.num_feature), 1);
72 dmlc::ByteSwap(&x.size_leaf_vector, sizeof(x.size_leaf_vector), 1);
73 dmlc::ByteSwap(x.reserved, sizeof(x.reserved[0]), sizeof(x.reserved) / sizeof(x.reserved[0]));
74 return x;
75 }
76
77 // declare the parameters
78 DMLC_DECLARE_PARAMETER(TreeParam) {
79 // only declare the parameters that can be set by the user.
80 // other arguments are set by the algorithm.
81 DMLC_DECLARE_FIELD(num_nodes).set_lower_bound(1).set_default(1);
82 DMLC_DECLARE_FIELD(num_feature)
83 .describe("Number of features used in tree construction.");
84 DMLC_DECLARE_FIELD(num_deleted);
85 DMLC_DECLARE_FIELD(size_leaf_vector).set_lower_bound(0).set_default(0)
86 .describe("Size of leaf vector, reserved for vector tree");
87 }
88
89 bool operator==(const TreeParam& b) const {
90 return num_nodes == b.num_nodes &&
91 num_deleted == b.num_deleted &&
92 num_feature == b.num_feature &&
93 size_leaf_vector == b.size_leaf_vector;
94 }
95 };
96
98 struct RTreeNodeStat {
100 bst_float loss_chg;
102 bst_float sum_hess;
104 bst_float base_weight;
106 int leaf_child_cnt {0};
107
108 RTreeNodeStat() = default;
109 RTreeNodeStat(float loss_chg, float sum_hess, float weight) :
110 loss_chg{loss_chg}, sum_hess{sum_hess}, base_weight{weight} {}
111 bool operator==(const RTreeNodeStat& b) const {
112 return loss_chg == b.loss_chg && sum_hess == b.sum_hess &&
113 base_weight == b.base_weight && leaf_child_cnt == b.leaf_child_cnt;
114 }
115 // Swap byte order for all fields. Useful for transporting models between machines with different
116 // endianness (big endian vs little endian)
117 inline RTreeNodeStat ByteSwap() const {
118 RTreeNodeStat x = *this;
119 dmlc::ByteSwap(&x.loss_chg, sizeof(x.loss_chg), 1);
120 dmlc::ByteSwap(&x.sum_hess, sizeof(x.sum_hess), 1);
121 dmlc::ByteSwap(&x.base_weight, sizeof(x.base_weight), 1);
122 dmlc::ByteSwap(&x.leaf_child_cnt, sizeof(x.leaf_child_cnt), 1);
123 return x;
124 }
125 };
126
131 class RegTree : public Model {
132 public:
133 using SplitCondT = bst_float;
134 static constexpr bst_node_t kInvalidNodeId {-1};
135 static constexpr uint32_t kDeletedNodeMarker = std::numeric_limits<uint32_t>::max();
136 static constexpr bst_node_t kRoot { 0 };
137
139 class Node {
140 public:
141 XGBOOST_DEVICE Node() {
142 // assert compact alignment
143 static_assert(sizeof(Node) == 4 * sizeof(int) + sizeof(Info),
144 "Node: 64 bit align");
145 }
146 Node(int32_t cleft, int32_t cright, int32_t parent,
147 uint32_t split_ind, float split_cond, bool default_left) :
148 parent_{parent}, cleft_{cleft}, cright_{cright} {
149 this->SetParent(parent_);
150 this->SetSplit(split_ind, split_cond, default_left);
151 }
152
154 XGBOOST_DEVICE int LeftChild() const {
155 return this->cleft_;
156 }
158 XGBOOST_DEVICE int RightChild() const {
159 return this->cright_;
160 }
162 XGBOOST_DEVICE int DefaultChild() const {
163 return this->DefaultLeft() ? this->LeftChild() : this->RightChild();
164 }
166 XGBOOST_DEVICE unsigned SplitIndex() const {
167 return sindex_ & ((1U << 31) - 1U);
168 }
170 XGBOOST_DEVICE bool DefaultLeft() const {
171 return (sindex_ >> 31) != 0;
172 }
174 XGBOOST_DEVICE bool IsLeaf() const {
175 return cleft_ == kInvalidNodeId;
176 }
178 XGBOOST_DEVICE bst_float LeafValue() const {
179 return (this->info_).leaf_value;
180 }
182 XGBOOST_DEVICE SplitCondT SplitCond() const {
183 return (this->info_).split_cond;
184 }
186 XGBOOST_DEVICE int Parent() const {
187 return parent_ & ((1U << 31) - 1);
188 }
190 XGBOOST_DEVICE bool IsLeftChild() const {
191 return (parent_ & (1U << 31)) != 0;
192 }
194 XGBOOST_DEVICE bool IsDeleted() const {
195 return sindex_ == kDeletedNodeMarker;
196 }
198 XGBOOST_DEVICE bool IsRoot() const { return parent_ == kInvalidNodeId; }
203 XGBOOST_DEVICE void SetLeftChild(int nid) {
204 this->cleft_ = nid;
205 }
210 XGBOOST_DEVICE void SetRightChild(int nid) {
211 this->cright_ = nid;
212 }
219 XGBOOST_DEVICE void SetSplit(unsigned split_index, SplitCondT split_cond,
220 bool default_left = false) {
221 if (default_left) split_index |= (1U << 31);
222 this->sindex_ = split_index;
223 (this->info_).split_cond = split_cond;
224 }
231 XGBOOST_DEVICE void SetLeaf(bst_float value, int right = kInvalidNodeId) {
232 (this->info_).leaf_value = value;
233 this->cleft_ = kInvalidNodeId;
234 this->cright_ = right;
235 }
237 XGBOOST_DEVICE void MarkDelete() {
238 this->sindex_ = kDeletedNodeMarker;
239 }
241 XGBOOST_DEVICE void Reuse() {
242 this->sindex_ = 0;
243 }
244 // set parent
245 XGBOOST_DEVICE void SetParent(int pidx, bool is_left_child = true) {
246 if (is_left_child) pidx |= (1U << 31);
247 this->parent_ = pidx;
248 }
249 bool operator==(const Node& b) const {
250 return parent_ == b.parent_ && cleft_ == b.cleft_ &&
251 cright_ == b.cright_ && sindex_ == b.sindex_ &&
252 info_.leaf_value == b.info_.leaf_value;
253 }
254
255 inline Node ByteSwap() const {
256 Node x = *this;
257 dmlc::ByteSwap(&x.parent_, sizeof(x.parent_), 1);
258 dmlc::ByteSwap(&x.cleft_, sizeof(x.cleft_), 1);
259 dmlc::ByteSwap(&x.cright_, sizeof(x.cright_), 1);
260 dmlc::ByteSwap(&x.sindex_, sizeof(x.sindex_), 1);
261 dmlc::ByteSwap(&x.info_, sizeof(x.info_), 1);
262 return x;
263 }
264
265 private:
270 union Info{
271 bst_float leaf_value;
272 SplitCondT split_cond;
273 };
274 // pointer to parent, highest bit is used to
275 // indicate whether it's a left child or not
276 int32_t parent_{kInvalidNodeId};
277 // pointer to left, right
278 int32_t cleft_{kInvalidNodeId}, cright_{kInvalidNodeId};
279 // split feature index, left split or right split depends on the highest bit
280 uint32_t sindex_{0};
281 // extra info
282 Info info_;
283 };
284
290 void ChangeToLeaf(int rid, bst_float value) {
291 CHECK(nodes_[nodes_[rid].LeftChild() ].IsLeaf());
292 CHECK(nodes_[nodes_[rid].RightChild()].IsLeaf());
293 this->DeleteNode(nodes_[rid].LeftChild());
294 this->DeleteNode(nodes_[rid].RightChild());
295 nodes_[rid].SetLeaf(value);
296 }
302 void CollapseToLeaf(int rid, bst_float value) {
303 if (nodes_[rid].IsLeaf()) return;
304 if (!nodes_[nodes_[rid].LeftChild() ].IsLeaf()) {
305 CollapseToLeaf(nodes_[rid].LeftChild(), 0.0f);
306 }
307 if (!nodes_[nodes_[rid].RightChild() ].IsLeaf()) {
308 CollapseToLeaf(nodes_[rid].RightChild(), 0.0f);
309 }
310 this->ChangeToLeaf(rid, value);
311 }
312
314 TreeParam param;
316 RegTree() {
317 param.num_nodes = 1;
318 param.num_deleted = 0;
319 nodes_.resize(param.num_nodes);
320 stats_.resize(param.num_nodes);
321 split_types_.resize(param.num_nodes, FeatureType::kNumerical);
322 split_categories_segments_.resize(param.num_nodes);
323 for (int i = 0; i < param.num_nodes; i ++) {
324 nodes_[i].SetLeaf(0.0f);
325 nodes_[i].SetParent(kInvalidNodeId);
326 }
327 }
329 Node& operator[](int nid) {
330 return nodes_[nid];
331 }
333 const Node& operator[](int nid) const {
334 return nodes_[nid];
335 }
336
338 const std::vector<Node>& GetNodes() const { return nodes_; }
339
341 const std::vector<RTreeNodeStat>& GetStats() const { return stats_; }
342
344 RTreeNodeStat& Stat(int nid) {
345 return stats_[nid];
346 }
348 const RTreeNodeStat& Stat(int nid) const {
349 return stats_[nid];
350 }
351
356 void Load(dmlc::Stream* fi);
361 void Save(dmlc::Stream* fo) const;
362
363 void LoadModel(Json const& in) override;
364 void SaveModel(Json* out) const override;
365
366 bool operator==(const RegTree& b) const {
367 return nodes_ == b.nodes_ && stats_ == b.stats_ &&
368 deleted_nodes_ == b.deleted_nodes_ && param == b.param;
369 }
370 /* \brief Iterate through all nodes in this tree.
371 *
372 * \param Function that accepts a node index, and returns false when iteration should
373 * stop, otherwise returns true.
374 */
375 template <typename Func> void WalkTree(Func func) const {
376 std::stack<bst_node_t> nodes;
377 nodes.push(kRoot);
378 auto &self = *this;
379 while (!nodes.empty()) {
380 auto nidx = nodes.top();
381 nodes.pop();
382 if (!func(nidx)) {
383 return;
384 }
385 auto left = self[nidx].LeftChild();
386 auto right = self[nidx].RightChild();
387 if (left != RegTree::kInvalidNodeId) {
388 nodes.push(left);
389 }
390 if (right != RegTree::kInvalidNodeId) {
391 nodes.push(right);
392 }
393 }
394 }
401 bool Equal(const RegTree& b) const;
402
420 void ExpandNode(bst_node_t nid, unsigned split_index, bst_float split_value,
421 bool default_left, bst_float base_weight,
422 bst_float left_leaf_weight, bst_float right_leaf_weight,
423 bst_float loss_change, float sum_hess, float left_sum,
424 float right_sum,
425 bst_node_t leaf_right_child = kInvalidNodeId);
426
442 void ExpandCategorical(bst_node_t nid, unsigned split_index,
443 common::Span<uint32_t> split_cat, bool default_left,
444 bst_float base_weight, bst_float left_leaf_weight,
445 bst_float right_leaf_weight, bst_float loss_change,
446 float sum_hess, float left_sum, float right_sum);
447
452 int GetDepth(int nid) const {
453 int depth = 0;
454 while (!nodes_[nid].IsRoot()) {
455 ++depth;
456 nid = nodes_[nid].Parent();
457 }
458 return depth;
459 }
460
465 int MaxDepth(int nid) const {
466 if (nodes_[nid].IsLeaf()) return 0;
467 return std::max(MaxDepth(nodes_[nid].LeftChild())+1,
468 MaxDepth(nodes_[nid].RightChild())+1);
469 }
470
474 int MaxDepth() {
475 return MaxDepth(0);
476 }
477
479 int NumExtraNodes() const {
480 return param.num_nodes - 1 - param.num_deleted;
481 }
482
483 /* \brief Count number of leaves in tree. */
484 bst_node_t GetNumLeaves() const;
485 bst_node_t GetNumSplitNodes() const;
486
491 struct FVec {
496 void Init(size_t size);
501 void Fill(const SparsePage::Inst& inst);
502
507 void Drop(const SparsePage::Inst& inst);
512 size_t Size() const;
518 bst_float GetFvalue(size_t i) const;
524 bool IsMissing(size_t i) const;
525 bool HasMissing() const;
526
527
528 private:
533 union Entry {
534 bst_float fvalue;
535 int flag;
536 };
537 std::vector<Entry> data_;
538 bool has_missing_;
539 };
545 template <bool has_missing = true>
546 int GetLeafIndex(const FVec& feat) const;
547
555 void CalculateContributions(const RegTree::FVec& feat,
556 bst_float* out_contribs, int condition = 0,
557 unsigned condition_feature = 0) const;
572 void TreeShap(const RegTree::FVec& feat, bst_float* phi, unsigned node_index,
573 unsigned unique_depth, PathElement* parent_unique_path,
574 bst_float parent_zero_fraction, bst_float parent_one_fraction,
575 int parent_feature_index, int condition,
576 unsigned condition_feature, bst_float condition_fraction) const;
577
583 void CalculateContributionsApprox(const RegTree::FVec& feat,
584 bst_float* out_contribs) const;
591 template <bool has_missing = true>
592 inline int GetNext(int pid, bst_float fvalue, bool is_unknown) const;
600 std::string DumpModel(const FeatureMap& fmap,
601 bool with_stats,
602 std::string format) const;
606 void FillNodeMeanValues();
612 FeatureType NodeSplitType(bst_node_t nidx) const {
613 return split_types_.at(nidx);
614 }
618 std::vector<FeatureType> const &GetSplitTypes() const { return split_types_; }
619 common::Span<uint32_t const> GetSplitCategories() const { return split_categories_; }
620 auto const& GetSplitCategoriesPtr() const { return split_categories_segments_; }
621
622 // The fields of split_categories_segments_[i] are set such that
623 // the range split_categories_[beg:(beg+size)] stores the bitset for
624 // the matching categories for the i-th node.
625 struct Segment {
626 size_t beg {0};
627 size_t size {0};
628 };
629
630 private:
631 void LoadCategoricalSplit(Json const& in);
632 void SaveCategoricalSplit(Json* p_out) const;
633 // vector of nodes
634 std::vector<Node> nodes_;
635 // free node space, used during training process
636 std::vector<int> deleted_nodes_;
637 // stats of nodes
638 std::vector<RTreeNodeStat> stats_;
639 std::vector<bst_float> node_mean_values_;
640 std::vector<FeatureType> split_types_;
641
642 // Categories for each internal node.
643 std::vector<uint32_t> split_categories_;
644 // Ptr to split categories of each node.
645 std::vector<Segment> split_categories_segments_;
646
647 // allocate a new node,
648 // !!!!!! NOTE: may cause BUG here, nodes.resize
649 bst_node_t AllocNode() {
650 if (param.num_deleted != 0) {
651 int nid = deleted_nodes_.back();
652 deleted_nodes_.pop_back();
653 nodes_[nid].Reuse();
654 --param.num_deleted;
655 return nid;
656 }
657 int nd = param.num_nodes++;
658 CHECK_LT(param.num_nodes, std::numeric_limits<int>::max())
659 << "number of nodes in the tree exceed 2^31";
660 nodes_.resize(param.num_nodes);
661 stats_.resize(param.num_nodes);
662 split_types_.resize(param.num_nodes, FeatureType::kNumerical);
663 split_categories_segments_.resize(param.num_nodes);
664 return nd;
665 }
666 // delete a tree node, keep the parent field to allow trace back
667 void DeleteNode(int nid) {
668 CHECK_GE(nid, 1);
669 auto pid = (*this)[nid].Parent();
670 if (nid == (*this)[pid].LeftChild()) {
671 (*this)[pid].SetLeftChild(kInvalidNodeId);
672 } else {
673 (*this)[pid].SetRightChild(kInvalidNodeId);
674 }
675
676 deleted_nodes_.push_back(nid);
677 nodes_[nid].MarkDelete();
678 ++param.num_deleted;
679 }
680 bst_float FillNodeMeanValue(int nid);
681 };
682
683 inline void RegTree::FVec::Init(size_t size) {
684 Entry e; e.flag = -1;
685 data_.resize(size);
686 std::fill(data_.begin(), data_.end(), e);
687 has_missing_ = true;
688 }
689
690 inline void RegTree::FVec::Fill(const SparsePage::Inst& inst) {
691 size_t feature_count = 0;
692 for (auto const& entry : inst) {
693 if (entry.index >= data_.size()) {
694 continue;
695 }
696 data_[entry.index].fvalue = entry.fvalue;
697 ++feature_count;
698 }
699 has_missing_ = data_.size() != feature_count;
700 }
701
702 inline void RegTree::FVec::Drop(const SparsePage::Inst& inst) {
703 for (auto const& entry : inst) {
704 if (entry.index >= data_.size()) {
705 continue;
706 }
707 data_[entry.index].flag = -1;
708 }
709 has_missing_ = true;
710 }
711
712 inline size_t RegTree::FVec::Size() const {
713 return data_.size();
714 }
715
716 inline bst_float RegTree::FVec::GetFvalue(size_t i) const {
717 return data_[i].fvalue;
718 }
719
720 inline bool RegTree::FVec::IsMissing(size_t i) const {
721 return data_[i].flag == -1;
722 }
723
724 inline bool RegTree::FVec::HasMissing() const {
725 return has_missing_;
726 }
727
728 template <bool has_missing>
729 inline int RegTree::GetLeafIndex(const RegTree::FVec& feat) const {
730 bst_node_t nid = 0;
731 while (!(*this)[nid].IsLeaf()) {
732 unsigned split_index = (*this)[nid].SplitIndex();
733 nid = this->GetNext<has_missing>(nid, feat.GetFvalue(split_index),
734 has_missing && feat.IsMissing(split_index));
735 }
736 return nid;
737 }
738
740 template <bool has_missing>
741 inline int RegTree::GetNext(int pid, bst_float fvalue, bool is_unknown) const {
742 if (has_missing) {
743 if (is_unknown) {
744 return (*this)[pid].DefaultChild();
745 } else {
746 if (fvalue < (*this)[pid].SplitCond()) {
747 return (*this)[pid].LeftChild();
748 } else {
749 return (*this)[pid].RightChild();
750 }
751 }
752 } else {
753 // 35% speed up due to reduced miss branch predictions
754 // The following expression returns the left child if (fvalue < split_cond);
755 // the right child otherwise.
756 return (*this)[pid].LeftChild() + !(fvalue < (*this)[pid].SplitCond());
757 }
758 }
759
760 } // namespace xgboost
761 #endif // XGBOOST_TREE_MODEL_H_
xgboost::RegTree::Segment::beg
size_t beg
Definition: tree_model.h:626
xgboost::RegTree::param
TreeParam param
model parameter
Definition: tree_model.h:314
xgboost::RegTree::Node
tree node
Definition: tree_model.h:139
xgboost::RegTree::Node::IsLeftChild
XGBOOST_DEVICE bool IsLeftChild() const
whether current node is left child
Definition: tree_model.h:190
xgboost::RegTree::FVec::Size
size_t Size() const
returns the size of the feature vector
Definition: tree_model.h:712
xgboost::TreeParam::deprecated_max_depth
int deprecated_max_depth
maximum depth, this is a statistics of the tree
Definition: tree_model.h:43
xgboost::TreeParam::DMLC_DECLARE_PARAMETER
DMLC_DECLARE_PARAMETER(TreeParam)
Definition: tree_model.h:78
xgboost::RegTree::Load
void Load(dmlc::Stream *fi)
load model from stream
xgboost::RegTree::kRoot
static constexpr bst_node_t kRoot
Definition: tree_model.h:136
xgboost::TreeParam::size_leaf_vector
int size_leaf_vector
leaf vector size, used for vector tree used to store more than one dimensional information in tree
Definition: tree_model.h:50
model.h
Defines the abstract interface for different components in XGBoost.
xgboost::TreeParam::operator==
bool operator==(const TreeParam &b) const
Definition: tree_model.h:89
xgboost::RegTree::Stat
const RTreeNodeStat & Stat(int nid) const
get node statistics given nid
Definition: tree_model.h:348
xgboost::RegTree::FVec
dense feature vector that can be taken by RegTree and can be construct from sparse feature vector.
Definition: tree_model.h:491
xgboost::RTreeNodeStat::loss_chg
bst_float loss_chg
loss change caused by current split
Definition: tree_model.h:100
xgboost::TreeParam::reserved
int reserved[31]
reserved part, make sure alignment works for 64bit
Definition: tree_model.h:52
xgboost::RegTree::Node::SetSplit
XGBOOST_DEVICE void SetSplit(unsigned split_index, SplitCondT split_cond, bool default_left=false)
set split condition of current node
Definition: tree_model.h:219
xgboost::RegTree::LoadModel
void LoadModel(Json const &in) override
load the model from a json object
xgboost::RegTree::DumpModel
std::string DumpModel(const FeatureMap &fmap, bool with_stats, std::string format) const
dump the model in the requested format as a text string
xgboost::RegTree::Node::IsLeaf
XGBOOST_DEVICE bool IsLeaf() const
whether current node is leaf node
Definition: tree_model.h:174
xgboost::RegTree::FVec::HasMissing
bool HasMissing() const
Definition: tree_model.h:724
xgboost::RegTree::Node::SetLeftChild
XGBOOST_DEVICE void SetLeftChild(int nid)
set the left child
Definition: tree_model.h:203
xgboost::RegTree::WalkTree
void WalkTree(Func func) const
Definition: tree_model.h:375
xgboost::RTreeNodeStat::operator==
bool operator==(const RTreeNodeStat &b) const
Definition: tree_model.h:111
xgboost::TreeParam::ByteSwap
TreeParam ByteSwap() const
Definition: tree_model.h:65
xgboost::RegTree::GetSplitTypes
const std::vector< FeatureType > & GetSplitTypes() const
Get split types for all nodes.
Definition: tree_model.h:618
xgboost::RegTree::operator[]
Node & operator[](int nid)
get node given nid
Definition: tree_model.h:329
xgboost::RegTree::Node::IsRoot
XGBOOST_DEVICE bool IsRoot() const
whether current node is root
Definition: tree_model.h:198
xgboost::RegTree::Node::MarkDelete
XGBOOST_DEVICE void MarkDelete()
mark that this node is deleted
Definition: tree_model.h:237
xgboost::RegTree::FVec::Fill
void Fill(const SparsePage::Inst &inst)
fill the vector with sparse vector
Definition: tree_model.h:690
base.h
defines configuration macros of xgboost.
xgboost::RegTree::Node::Reuse
XGBOOST_DEVICE void Reuse()
Reuse this deleted node.
Definition: tree_model.h:241
feature_map.h
Feature map data structure to help visualization and model dump.
xgboost::RegTree::Node::SetParent
XGBOOST_DEVICE void SetParent(int pidx, bool is_left_child=true)
Definition: tree_model.h:245
xgboost::RegTree::Node::Parent
XGBOOST_DEVICE int Parent() const
get parent of the node
Definition: tree_model.h:186
xgboost::RegTree::Node::DefaultChild
XGBOOST_DEVICE int DefaultChild() const
index of default child when feature is missing
Definition: tree_model.h:162
xgboost::RegTree::Node::RightChild
XGBOOST_DEVICE int RightChild() const
index of right child
Definition: tree_model.h:158
xgboost::RegTree::GetNext
int GetNext(int pid, bst_float fvalue, bool is_unknown) const
get next position of the tree given current pid
Definition: tree_model.h:741
xgboost::RegTree::MaxDepth
int MaxDepth(int nid) const
get maximum depth
Definition: tree_model.h:465
xgboost::FeatureMap
Feature map data structure to help text model dump. TODO(tqchen) consider make it even more lightweig...
Definition: feature_map.h:22
xgboost::RegTree::FVec::Drop
void Drop(const SparsePage::Inst &inst)
drop the trace after fill, must be called after fill.
Definition: tree_model.h:702
xgboost::RegTree::RegTree
RegTree()
constructor
Definition: tree_model.h:316
xgboost::RegTree::operator[]
const Node & operator[](int nid) const
get node given nid
Definition: tree_model.h:333
xgboost::RegTree::Segment::size
size_t size
Definition: tree_model.h:627
xgboost::Model
Definition: model.h:17
xgboost::RegTree::kInvalidNodeId
static constexpr bst_node_t kInvalidNodeId
Definition: tree_model.h:134
xgboost::RegTree::Node::SetLeaf
XGBOOST_DEVICE void SetLeaf(bst_float value, int right=kInvalidNodeId)
set the leaf value of the node
Definition: tree_model.h:231
xgboost::RegTree::FVec::GetFvalue
bst_float GetFvalue(size_t i) const
get ith value
Definition: tree_model.h:716
xgboost::RegTree::MaxDepth
int MaxDepth()
get maximum depth
Definition: tree_model.h:474
xgboost::RTreeNodeStat
node statistics used in regression tree
Definition: tree_model.h:98
xgboost::RegTree::GetDepth
int GetDepth(int nid) const
get current depth
Definition: tree_model.h:452
xgboost::RegTree::Segment
Definition: tree_model.h:625
xgboost::TreeParam::deprecated_num_roots
int deprecated_num_roots
(Deprecated) number of start root
Definition: tree_model.h:37
xgboost::RegTree::SaveModel
void SaveModel(Json *out) const override
saves the model config to a json object
xgboost::RegTree::Node::ByteSwap
Node ByteSwap() const
Definition: tree_model.h:255
xgboost::RegTree::GetNumSplitNodes
bst_node_t GetNumSplitNodes() const
xgboost::RegTree::Node::LeafValue
XGBOOST_DEVICE bst_float LeafValue() const
Definition: tree_model.h:178
xgboost::RTreeNodeStat::RTreeNodeStat
RTreeNodeStat(float loss_chg, float sum_hess, float weight)
Definition: tree_model.h:109
xgboost::bst_node_t
int32_t bst_node_t
Type for tree node index.
Definition: base.h:132
xgboost::RegTree::Node::Node
Node(int32_t cleft, int32_t cright, int32_t parent, uint32_t split_ind, float split_cond, bool default_left)
Definition: tree_model.h:146
xgboost::RegTree
define regression tree to be the most common tree model. This is the data structure used in xgboost's...
Definition: tree_model.h:131
xgboost::FeatureType::kNumerical
@ kNumerical
xgboost::RTreeNodeStat::sum_hess
bst_float sum_hess
sum of hessian values, used to measure coverage of data
Definition: tree_model.h:102
xgboost::RegTree::GetLeafIndex
int GetLeafIndex(const FVec &feat) const
get the leaf index
Definition: tree_model.h:729
xgboost::TreeParam
meta parameters of the tree
Definition: tree_model.h:35
xgboost::RTreeNodeStat::base_weight
bst_float base_weight
weight of current node
Definition: tree_model.h:104
xgboost::RegTree::CollapseToLeaf
void CollapseToLeaf(int rid, bst_float value)
collapse a non leaf node to a leaf node, delete its children
Definition: tree_model.h:302
xgboost::RegTree::Node::LeftChild
XGBOOST_DEVICE int LeftChild() const
index of left child
Definition: tree_model.h:154
xgboost::TreeParam::num_deleted
int num_deleted
number of deleted nodes
Definition: tree_model.h:41
xgboost::FeatureType
FeatureType
Definition: data.h:37
xgboost::RegTree::GetSplitCategoriesPtr
auto const & GetSplitCategoriesPtr() const
Definition: tree_model.h:620
xgboost::RegTree::Node::Node
XGBOOST_DEVICE Node()
Definition: tree_model.h:141
xgboost::RegTree::FillNodeMeanValues
void FillNodeMeanValues()
calculate the mean value for each node, required for feature contributions
xgboost::RegTree::kDeletedNodeMarker
static constexpr uint32_t kDeletedNodeMarker
Definition: tree_model.h:135
xgboost::RegTree::SplitCondT
bst_float SplitCondT
Definition: tree_model.h:133
xgboost::common::Span
span class implementation, based on ISO++20 span<T>. The interface should be the same.
Definition: span.h:137
xgboost::RegTree::CalculateContributions
void CalculateContributions(const RegTree::FVec &feat, bst_float *out_contribs, int condition=0, unsigned condition_feature=0) const
calculate the feature contributions (https://arxiv.org/abs/1706.06060) for the tree
xgboost::RegTree::Stat
RTreeNodeStat & Stat(int nid)
get node statistics given nid
Definition: tree_model.h:344
data.h
The input data structure of xgboost.
xgboost::RegTree::Node::SplitCond
XGBOOST_DEVICE SplitCondT SplitCond() const
Definition: tree_model.h:182
xgboost::RTreeNodeStat::RTreeNodeStat
RTreeNodeStat()=default
xgboost::RTreeNodeStat::ByteSwap
RTreeNodeStat ByteSwap() const
Definition: tree_model.h:117
xgboost::RegTree::GetNumLeaves
bst_node_t GetNumLeaves() const
xgboost::RegTree::NodeSplitType
FeatureType NodeSplitType(bst_node_t nidx) const
Get split type for a node.
Definition: tree_model.h:612
xgboost::RegTree::GetSplitCategories
common::Span< uint32_t const > GetSplitCategories() const
Definition: tree_model.h:619
xgboost::RegTree::GetNodes
const std::vector< Node > & GetNodes() const
get const reference to nodes
Definition: tree_model.h:338
xgboost::RegTree::FVec::IsMissing
bool IsMissing(size_t i) const
check whether i-th entry is missing
Definition: tree_model.h:720
xgboost::RegTree::Node::DefaultLeft
XGBOOST_DEVICE bool DefaultLeft() const
when feature is unknown, whether goes to left child
Definition: tree_model.h:170
xgboost::RegTree::NumExtraNodes
int NumExtraNodes() const
number of extra nodes besides the root
Definition: tree_model.h:479
xgboost::RegTree::ChangeToLeaf
void ChangeToLeaf(int rid, bst_float value)
change a non leaf node to a leaf node, delete its children
Definition: tree_model.h:290
xgboost::RegTree::Node::SplitIndex
XGBOOST_DEVICE unsigned SplitIndex() const
feature index of split condition
Definition: tree_model.h:166
xgboost::RegTree::TreeShap
void TreeShap(const RegTree::FVec &feat, bst_float *phi, unsigned node_index, unsigned unique_depth, PathElement *parent_unique_path, bst_float parent_zero_fraction, bst_float parent_one_fraction, int parent_feature_index, int condition, unsigned condition_feature, bst_float condition_fraction) const
Recursive function that computes the feature attributions for a single tree.
xgboost::RegTree::ExpandCategorical
void ExpandCategorical(bst_node_t nid, unsigned split_index, common::Span< uint32_t > split_cat, bool default_left, bst_float base_weight, bst_float left_leaf_weight, bst_float right_leaf_weight, bst_float loss_change, float sum_hess, float left_sum, float right_sum)
Expands a leaf node with categories.
xgboost::TreeParam::TreeParam
TreeParam()
constructor
Definition: tree_model.h:54
xgboost::RegTree::Node::SetRightChild
XGBOOST_DEVICE void SetRightChild(int nid)
set the right child
Definition: tree_model.h:210
xgboost::Json
Data structure representing JSON format.
Definition: json.h:345
xgboost::RegTree::CalculateContributionsApprox
void CalculateContributionsApprox(const RegTree::FVec &feat, bst_float *out_contribs) const
calculate the approximate feature contributions for the given root
xgboost::RegTree::Save
void Save(dmlc::Stream *fo) const
save model to stream
xgboost::RegTree::GetStats
const std::vector< RTreeNodeStat > & GetStats() const
get const reference to stats
Definition: tree_model.h:341
xgboost::TreeParam::num_feature
int num_feature
number of features used for tree construction
Definition: tree_model.h:45
xgboost::RegTree::FVec::Init
void Init(size_t size)
initialize the vector with size vector
Definition: tree_model.h:683
xgboost::RTreeNodeStat::leaf_child_cnt
int leaf_child_cnt
number of child that is leaf node known up to now
Definition: tree_model.h:106
xgboost::RegTree::Equal
bool Equal(const RegTree &b) const
Compares whether 2 trees are equal from a user's perspective. The equality compares only non-deleted ...
xgboost::RegTree::ExpandNode
void ExpandNode(bst_node_t nid, unsigned split_index, bst_float split_value, bool default_left, bst_float base_weight, bst_float left_leaf_weight, bst_float right_leaf_weight, bst_float loss_change, float sum_hess, float left_sum, float right_sum, bst_node_t leaf_right_child=kInvalidNodeId)
Expands a leaf node into two additional leaf nodes.
XGBOOST_DEVICE
#define XGBOOST_DEVICE
Tag function as usable by device.
Definition: base.h:84
xgboost::RegTree::operator==
bool operator==(const RegTree &b) const
Definition: tree_model.h:366
xgboost::TreeParam::num_nodes
int num_nodes
total number of nodes
Definition: tree_model.h:39
xgboost::RegTree::Node::operator==
bool operator==(const Node &b) const
Definition: tree_model.h:249
xgboost::RegTree::Node::IsDeleted
XGBOOST_DEVICE bool IsDeleted() const
whether this node is deleted
Definition: tree_model.h:194
xgboost
namespace of xgboost
Definition: base.h:110
xgboost::bst_float
float bst_float
float type, used for storing statistics
Definition: base.h:119