recursive computation of SHAP values for a decision tree
| 667 | |
| 668 | // recursive computation of SHAP values for a decision tree |
| 669 | void Tree::TreeSHAP(const double *feature_values, double *phi, |
| 670 | int node, int unique_depth, |
| 671 | PathElement *parent_unique_path, double parent_zero_fraction, |
| 672 | double parent_one_fraction, int parent_feature_index) const { |
| 673 | // extend the unique path |
| 674 | PathElement* unique_path = parent_unique_path + unique_depth; |
| 675 | if (unique_depth > 0) std::copy(parent_unique_path, parent_unique_path + unique_depth, unique_path); |
| 676 | ExtendPath(unique_path, unique_depth, parent_zero_fraction, |
| 677 | parent_one_fraction, parent_feature_index); |
| 678 | |
| 679 | // leaf node |
| 680 | if (node < 0) { |
| 681 | for (int i = 1; i <= unique_depth; ++i) { |
| 682 | const double w = UnwoundPathSum(unique_path, unique_depth, i); |
| 683 | const PathElement &el = unique_path[i]; |
| 684 | phi[el.feature_index] += w*(el.one_fraction - el.zero_fraction)*leaf_value_[~node]; |
| 685 | } |
| 686 | |
| 687 | // internal node |
| 688 | } else { |
| 689 | const int hot_index = Decision(feature_values[split_feature_[node]], node); |
| 690 | const int cold_index = (hot_index == left_child_[node] ? right_child_[node] : left_child_[node]); |
| 691 | const double w = data_count(node); |
| 692 | const double hot_zero_fraction = data_count(hot_index) / w; |
| 693 | const double cold_zero_fraction = data_count(cold_index) / w; |
| 694 | double incoming_zero_fraction = 1; |
| 695 | double incoming_one_fraction = 1; |
| 696 | |
| 697 | // see if we have already split on this feature, |
| 698 | // if so we undo that split so we can redo it for this node |
| 699 | int path_index = 0; |
| 700 | for (; path_index <= unique_depth; ++path_index) { |
| 701 | if (unique_path[path_index].feature_index == split_feature_[node]) break; |
| 702 | } |
| 703 | if (path_index != unique_depth + 1) { |
| 704 | incoming_zero_fraction = unique_path[path_index].zero_fraction; |
| 705 | incoming_one_fraction = unique_path[path_index].one_fraction; |
| 706 | UnwindPath(unique_path, unique_depth, path_index); |
| 707 | unique_depth -= 1; |
| 708 | } |
| 709 | |
| 710 | TreeSHAP(feature_values, phi, hot_index, unique_depth + 1, unique_path, |
| 711 | hot_zero_fraction*incoming_zero_fraction, incoming_one_fraction, split_feature_[node]); |
| 712 | |
| 713 | TreeSHAP(feature_values, phi, cold_index, unique_depth + 1, unique_path, |
| 714 | cold_zero_fraction*incoming_zero_fraction, 0, split_feature_[node]); |
| 715 | } |
| 716 | } |
| 717 | |
| 718 | double Tree::ExpectedValue() const { |
| 719 | if (num_leaves_ == 1) return LeafOutput(0); |